1 /*
   2  * Copyright (c) 1998, 2014, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 // FORMS.CPP - Definitions for ADL Parser Forms Classes
  26 #include "adlc.hpp"
  27 
  28 //==============================Instructions===================================
  29 //------------------------------InstructForm-----------------------------------
  30 InstructForm::InstructForm(const char *id, bool ideal_only)
  31   : _ident(id), _ideal_only(ideal_only),
  32     _localNames(cmpstr, hashstr, Form::arena),
  33     _effects(cmpstr, hashstr, Form::arena),
  34     _is_mach_constant(false),
  35     _needs_constant_base(false),
  36     _has_call(false)
  37 {
  38       _ftype = Form::INS;
  39 
  40       _matrule              = NULL;
  41       _insencode            = NULL;
  42       _constant             = NULL;
  43       _is_postalloc_expand  = false;
  44       _opcode               = NULL;
  45       _size                 = NULL;
  46       _attribs              = NULL;
  47       _predicate            = NULL;
  48       _exprule              = NULL;
  49       _rewrule              = NULL;
  50       _format               = NULL;
  51       _peephole             = NULL;
  52       _ins_pipe             = NULL;
  53       _uniq_idx             = NULL;
  54       _num_uniq             = 0;
  55       _cisc_spill_operand   = Not_cisc_spillable;// Which operand may cisc-spill
  56       _cisc_spill_alternate = NULL;            // possible cisc replacement
  57       _cisc_reg_mask_name   = NULL;
  58       _is_cisc_alternate    = false;
  59       _is_short_branch      = false;
  60       _short_branch_form    = NULL;
  61       _alignment            = 1;
  62 }
  63 
  64 InstructForm::InstructForm(const char *id, InstructForm *instr, MatchRule *rule)
  65   : _ident(id), _ideal_only(false),
  66     _localNames(instr->_localNames),
  67     _effects(instr->_effects),
  68     _is_mach_constant(false),
  69     _needs_constant_base(false),
  70     _has_call(false)
  71 {
  72       _ftype = Form::INS;
  73 
  74       _matrule               = rule;
  75       _insencode             = instr->_insencode;
  76       _constant              = instr->_constant;
  77       _is_postalloc_expand   = instr->_is_postalloc_expand;
  78       _opcode                = instr->_opcode;
  79       _size                  = instr->_size;
  80       _attribs               = instr->_attribs;
  81       _predicate             = instr->_predicate;
  82       _exprule               = instr->_exprule;
  83       _rewrule               = instr->_rewrule;
  84       _format                = instr->_format;
  85       _peephole              = instr->_peephole;
  86       _ins_pipe              = instr->_ins_pipe;
  87       _uniq_idx              = instr->_uniq_idx;
  88       _num_uniq              = instr->_num_uniq;
  89       _cisc_spill_operand    = Not_cisc_spillable; // Which operand may cisc-spill
  90       _cisc_spill_alternate  = NULL;               // possible cisc replacement
  91       _cisc_reg_mask_name    = NULL;
  92       _is_cisc_alternate     = false;
  93       _is_short_branch       = false;
  94       _short_branch_form     = NULL;
  95       _alignment             = 1;
  96      // Copy parameters
  97      const char *name;
  98      instr->_parameters.reset();
  99      for (; (name = instr->_parameters.iter()) != NULL;)
 100        _parameters.addName(name);
 101 }
 102 
 103 InstructForm::~InstructForm() {
 104 }
 105 
 106 InstructForm *InstructForm::is_instruction() const {
 107   return (InstructForm*)this;
 108 }
 109 
 110 bool InstructForm::ideal_only() const {
 111   return _ideal_only;
 112 }
 113 
 114 bool InstructForm::sets_result() const {
 115   return (_matrule != NULL && _matrule->sets_result());
 116 }
 117 
 118 bool InstructForm::needs_projections() {
 119   _components.reset();
 120   for( Component *comp; (comp = _components.iter()) != NULL; ) {
 121     if (comp->isa(Component::KILL)) {
 122       return true;
 123     }
 124   }
 125   return false;
 126 }
 127 
 128 
 129 bool InstructForm::has_temps() {
 130   if (_matrule) {
 131     // Examine each component to see if it is a TEMP
 132     _components.reset();
 133     // Skip the first component, if already handled as (SET dst (...))
 134     Component *comp = NULL;
 135     if (sets_result())  comp = _components.iter();
 136     while ((comp = _components.iter()) != NULL) {
 137       if (comp->isa(Component::TEMP)) {
 138         return true;
 139       }
 140     }
 141   }
 142 
 143   return false;
 144 }
 145 
 146 uint InstructForm::num_defs_or_kills() {
 147   uint   defs_or_kills = 0;
 148 
 149   _components.reset();
 150   for( Component *comp; (comp = _components.iter()) != NULL; ) {
 151     if( comp->isa(Component::DEF) || comp->isa(Component::KILL) ) {
 152       ++defs_or_kills;
 153     }
 154   }
 155 
 156   return  defs_or_kills;
 157 }
 158 
 159 // This instruction has an expand rule?
 160 bool InstructForm::expands() const {
 161   return ( _exprule != NULL );
 162 }
 163 
 164 // This instruction has a late expand rule?
 165 bool InstructForm::postalloc_expands() const {
 166   return _is_postalloc_expand;
 167 }
 168 
 169 // This instruction has a peephole rule?
 170 Peephole *InstructForm::peepholes() const {
 171   return _peephole;
 172 }
 173 
 174 // This instruction has a peephole rule?
 175 void InstructForm::append_peephole(Peephole *peephole) {
 176   if( _peephole == NULL ) {
 177     _peephole = peephole;
 178   } else {
 179     _peephole->append_peephole(peephole);
 180   }
 181 }
 182 
 183 
 184 // ideal opcode enumeration
 185 const char *InstructForm::ideal_Opcode( FormDict &globalNames )  const {
 186   if( !_matrule ) return "Node"; // Something weird
 187   // Chain rules do not really have ideal Opcodes; use their source
 188   // operand ideal Opcode instead.
 189   if( is_simple_chain_rule(globalNames) ) {
 190     const char *src = _matrule->_rChild->_opType;
 191     OperandForm *src_op = globalNames[src]->is_operand();
 192     assert( src_op, "Not operand class of chain rule" );
 193     if( !src_op->_matrule ) return "Node";
 194     return src_op->_matrule->_opType;
 195   }
 196   // Operand chain rules do not really have ideal Opcodes
 197   if( _matrule->is_chain_rule(globalNames) )
 198     return "Node";
 199   return strcmp(_matrule->_opType,"Set")
 200     ? _matrule->_opType
 201     : _matrule->_rChild->_opType;
 202 }
 203 
 204 // Recursive check on all operands' match rules in my match rule
 205 bool InstructForm::is_pinned(FormDict &globals) {
 206   if ( ! _matrule)  return false;
 207 
 208   int  index   = 0;
 209   if (_matrule->find_type("Goto",          index)) return true;
 210   if (_matrule->find_type("If",            index)) return true;
 211   if (_matrule->find_type("CountedLoopEnd",index)) return true;
 212   if (_matrule->find_type("Return",        index)) return true;
 213   if (_matrule->find_type("Rethrow",       index)) return true;
 214   if (_matrule->find_type("TailCall",      index)) return true;
 215   if (_matrule->find_type("TailJump",      index)) return true;
 216   if (_matrule->find_type("Halt",          index)) return true;
 217   if (_matrule->find_type("Jump",          index)) return true;
 218 
 219   return is_parm(globals);
 220 }
 221 
 222 // Recursive check on all operands' match rules in my match rule
 223 bool InstructForm::is_projection(FormDict &globals) {
 224   if ( ! _matrule)  return false;
 225 
 226   int  index   = 0;
 227   if (_matrule->find_type("Goto",    index)) return true;
 228   if (_matrule->find_type("Return",  index)) return true;
 229   if (_matrule->find_type("Rethrow", index)) return true;
 230   if (_matrule->find_type("TailCall",index)) return true;
 231   if (_matrule->find_type("TailJump",index)) return true;
 232   if (_matrule->find_type("Halt",    index)) return true;
 233 
 234   return false;
 235 }
 236 
 237 // Recursive check on all operands' match rules in my match rule
 238 bool InstructForm::is_parm(FormDict &globals) {
 239   if ( ! _matrule)  return false;
 240 
 241   int  index   = 0;
 242   if (_matrule->find_type("Parm",index)) return true;
 243 
 244   return false;
 245 }
 246 
 247 bool InstructForm::is_ideal_negD() const {
 248   return (_matrule && _matrule->_rChild && strcmp(_matrule->_rChild->_opType, "NegD") == 0);
 249 }
 250 
 251 // Return 'true' if this instruction matches an ideal 'Copy*' node
 252 int InstructForm::is_ideal_copy() const {
 253   return _matrule ? _matrule->is_ideal_copy() : 0;
 254 }
 255 
 256 // Return 'true' if this instruction is too complex to rematerialize.
 257 int InstructForm::is_expensive() const {
 258   // We can prove it is cheap if it has an empty encoding.
 259   // This helps with platform-specific nops like ThreadLocal and RoundFloat.
 260   if (is_empty_encoding())
 261     return 0;
 262 
 263   if (is_tls_instruction())
 264     return 1;
 265 
 266   if (_matrule == NULL)  return 0;
 267 
 268   return _matrule->is_expensive();
 269 }
 270 
 271 // Has an empty encoding if _size is a constant zero or there
 272 // are no ins_encode tokens.
 273 int InstructForm::is_empty_encoding() const {
 274   if (_insencode != NULL) {
 275     _insencode->reset();
 276     if (_insencode->encode_class_iter() == NULL) {
 277       return 1;
 278     }
 279   }
 280   if (_size != NULL && strcmp(_size, "0") == 0) {
 281     return 1;
 282   }
 283   return 0;
 284 }
 285 
 286 int InstructForm::is_tls_instruction() const {
 287   if (_ident != NULL &&
 288       ( ! strcmp( _ident,"tlsLoadP") ||
 289         ! strncmp(_ident,"tlsLoadP_",9)) ) {
 290     return 1;
 291   }
 292 
 293   if (_matrule != NULL && _insencode != NULL) {
 294     const char* opType = _matrule->_opType;
 295     if (strcmp(opType, "Set")==0)
 296       opType = _matrule->_rChild->_opType;
 297     if (strcmp(opType,"ThreadLocal")==0) {
 298       fprintf(stderr, "Warning: ThreadLocal instruction %s should be named 'tlsLoadP_*'\n",
 299               (_ident == NULL ? "NULL" : _ident));
 300       return 1;
 301     }
 302   }
 303 
 304   return 0;
 305 }
 306 
 307 
 308 // Return 'true' if this instruction matches an ideal 'If' node
 309 bool InstructForm::is_ideal_if() const {
 310   if( _matrule == NULL ) return false;
 311 
 312   return _matrule->is_ideal_if();
 313 }
 314 
 315 // Return 'true' if this instruction matches an ideal 'FastLock' node
 316 bool InstructForm::is_ideal_fastlock() const {
 317   if( _matrule == NULL ) return false;
 318 
 319   return _matrule->is_ideal_fastlock();
 320 }
 321 
 322 // Return 'true' if this instruction matches an ideal 'MemBarXXX' node
 323 bool InstructForm::is_ideal_membar() const {
 324   if( _matrule == NULL ) return false;
 325 
 326   return _matrule->is_ideal_membar();
 327 }
 328 
 329 // Return 'true' if this instruction matches an ideal 'LoadPC' node
 330 bool InstructForm::is_ideal_loadPC() const {
 331   if( _matrule == NULL ) return false;
 332 
 333   return _matrule->is_ideal_loadPC();
 334 }
 335 
 336 // Return 'true' if this instruction matches an ideal 'Box' node
 337 bool InstructForm::is_ideal_box() const {
 338   if( _matrule == NULL ) return false;
 339 
 340   return _matrule->is_ideal_box();
 341 }
 342 
 343 // Return 'true' if this instruction matches an ideal 'Goto' node
 344 bool InstructForm::is_ideal_goto() const {
 345   if( _matrule == NULL ) return false;
 346 
 347   return _matrule->is_ideal_goto();
 348 }
 349 
 350 // Return 'true' if this instruction matches an ideal 'Jump' node
 351 bool InstructForm::is_ideal_jump() const {
 352   if( _matrule == NULL ) return false;
 353 
 354   return _matrule->is_ideal_jump();
 355 }
 356 
 357 // Return 'true' if instruction matches ideal 'If' | 'Goto' | 'CountedLoopEnd'
 358 bool InstructForm::is_ideal_branch() const {
 359   if( _matrule == NULL ) return false;
 360 
 361   return _matrule->is_ideal_if() || _matrule->is_ideal_goto();
 362 }
 363 
 364 
 365 // Return 'true' if this instruction matches an ideal 'Return' node
 366 bool InstructForm::is_ideal_return() const {
 367   if( _matrule == NULL ) return false;
 368 
 369   // Check MatchRule to see if the first entry is the ideal "Return" node
 370   int  index   = 0;
 371   if (_matrule->find_type("Return",index)) return true;
 372   if (_matrule->find_type("Rethrow",index)) return true;
 373   if (_matrule->find_type("TailCall",index)) return true;
 374   if (_matrule->find_type("TailJump",index)) return true;
 375 
 376   return false;
 377 }
 378 
 379 // Return 'true' if this instruction matches an ideal 'Halt' node
 380 bool InstructForm::is_ideal_halt() const {
 381   int  index   = 0;
 382   return _matrule && _matrule->find_type("Halt",index);
 383 }
 384 
 385 // Return 'true' if this instruction matches an ideal 'SafePoint' node
 386 bool InstructForm::is_ideal_safepoint() const {
 387   int  index   = 0;
 388   return _matrule && _matrule->find_type("SafePoint",index);
 389 }
 390 
 391 // Return 'true' if this instruction matches an ideal 'Nop' node
 392 bool InstructForm::is_ideal_nop() const {
 393   return _ident && _ident[0] == 'N' && _ident[1] == 'o' && _ident[2] == 'p' && _ident[3] == '_';
 394 }
 395 
 396 bool InstructForm::is_ideal_control() const {
 397   if ( ! _matrule)  return false;
 398 
 399   return is_ideal_return() || is_ideal_branch() || _matrule->is_ideal_jump() || is_ideal_halt();
 400 }
 401 
 402 // Return 'true' if this instruction matches an ideal 'Call' node
 403 Form::CallType InstructForm::is_ideal_call() const {
 404   if( _matrule == NULL ) return Form::invalid_type;
 405 
 406   // Check MatchRule to see if the first entry is the ideal "Call" node
 407   int  idx   = 0;
 408   if(_matrule->find_type("CallStaticJava",idx))   return Form::JAVA_STATIC;
 409   idx = 0;
 410   if(_matrule->find_type("Lock",idx))             return Form::JAVA_STATIC;
 411   idx = 0;
 412   if(_matrule->find_type("Unlock",idx))           return Form::JAVA_STATIC;
 413   idx = 0;
 414   if(_matrule->find_type("CallDynamicJava",idx))  return Form::JAVA_DYNAMIC;
 415   idx = 0;
 416   if(_matrule->find_type("CallRuntime",idx))      return Form::JAVA_RUNTIME;
 417   idx = 0;
 418   if(_matrule->find_type("CallLeaf",idx))         return Form::JAVA_LEAF;
 419   idx = 0;
 420   if(_matrule->find_type("CallLeafNoFP",idx))     return Form::JAVA_LEAF;
 421   idx = 0;
 422 
 423   return Form::invalid_type;
 424 }
 425 
 426 // Return 'true' if this instruction matches an ideal 'Load?' node
 427 Form::DataType InstructForm::is_ideal_load() const {
 428   if( _matrule == NULL ) return Form::none;
 429 
 430   return  _matrule->is_ideal_load();
 431 }
 432 
 433 // Return 'true' if this instruction matches an ideal 'LoadKlass' node
 434 bool InstructForm::skip_antidep_check() const {
 435   if( _matrule == NULL ) return false;
 436 
 437   return  _matrule->skip_antidep_check();
 438 }
 439 
 440 // Return 'true' if this instruction matches an ideal 'Load?' node
 441 Form::DataType InstructForm::is_ideal_store() const {
 442   if( _matrule == NULL ) return Form::none;
 443 
 444   return  _matrule->is_ideal_store();
 445 }
 446 
 447 // Return 'true' if this instruction matches an ideal vector node
 448 bool InstructForm::is_vector() const {
 449   if( _matrule == NULL ) return false;
 450 
 451   return _matrule->is_vector();
 452 }
 453 
 454 
 455 // Return the input register that must match the output register
 456 // If this is not required, return 0
 457 uint InstructForm::two_address(FormDict &globals) {
 458   uint  matching_input = 0;
 459   if(_components.count() == 0) return 0;
 460 
 461   _components.reset();
 462   Component *comp = _components.iter();
 463   // Check if there is a DEF
 464   if( comp->isa(Component::DEF) ) {
 465     // Check that this is a register
 466     const char  *def_type = comp->_type;
 467     const Form  *form     = globals[def_type];
 468     OperandForm *op       = form->is_operand();
 469     if( op ) {
 470       if( op->constrained_reg_class() != NULL &&
 471           op->interface_type(globals) == Form::register_interface ) {
 472         // Remember the local name for equality test later
 473         const char *def_name = comp->_name;
 474         // Check if a component has the same name and is a USE
 475         do {
 476           if( comp->isa(Component::USE) && strcmp(comp->_name,def_name)==0 ) {
 477             return operand_position_format(def_name);
 478           }
 479         } while( (comp = _components.iter()) != NULL);
 480       }
 481     }
 482   }
 483 
 484   return 0;
 485 }
 486 
 487 
 488 // when chaining a constant to an instruction, returns 'true' and sets opType
 489 Form::DataType InstructForm::is_chain_of_constant(FormDict &globals) {
 490   const char *dummy  = NULL;
 491   const char *dummy2 = NULL;
 492   return is_chain_of_constant(globals, dummy, dummy2);
 493 }
 494 Form::DataType InstructForm::is_chain_of_constant(FormDict &globals,
 495                 const char * &opTypeParam) {
 496   const char *result = NULL;
 497 
 498   return is_chain_of_constant(globals, opTypeParam, result);
 499 }
 500 
 501 Form::DataType InstructForm::is_chain_of_constant(FormDict &globals,
 502                 const char * &opTypeParam, const char * &resultParam) {
 503   Form::DataType  data_type = Form::none;
 504   if ( ! _matrule)  return data_type;
 505 
 506   // !!!!!
 507   // The source of the chain rule is 'position = 1'
 508   uint         position = 1;
 509   const char  *result   = NULL;
 510   const char  *name     = NULL;
 511   const char  *opType   = NULL;
 512   // Here base_operand is looking for an ideal type to be returned (opType).
 513   if ( _matrule->is_chain_rule(globals)
 514        && _matrule->base_operand(position, globals, result, name, opType) ) {
 515     data_type = ideal_to_const_type(opType);
 516 
 517     // if it isn't an ideal constant type, just return
 518     if ( data_type == Form::none ) return data_type;
 519 
 520     // Ideal constant types also adjust the opType parameter.
 521     resultParam = result;
 522     opTypeParam = opType;
 523     return data_type;
 524   }
 525 
 526   return data_type;
 527 }
 528 
 529 // Check if a simple chain rule
 530 bool InstructForm::is_simple_chain_rule(FormDict &globals) const {
 531   if( _matrule && _matrule->sets_result()
 532       && _matrule->_rChild->_lChild == NULL
 533       && globals[_matrule->_rChild->_opType]
 534       && globals[_matrule->_rChild->_opType]->is_opclass() ) {
 535     return true;
 536   }
 537   return false;
 538 }
 539 
 540 // check for structural rematerialization
 541 bool InstructForm::rematerialize(FormDict &globals, RegisterForm *registers ) {
 542   bool   rematerialize = false;
 543 
 544   Form::DataType data_type = is_chain_of_constant(globals);
 545   if( data_type != Form::none )
 546     rematerialize = true;
 547 
 548   // Constants
 549   if( _components.count() == 1 && _components[0]->is(Component::USE_DEF) )
 550     rematerialize = true;
 551 
 552   // Pseudo-constants (values easily available to the runtime)
 553   if (is_empty_encoding() && is_tls_instruction())
 554     rematerialize = true;
 555 
 556   // 1-input, 1-output, such as copies or increments.
 557   if( _components.count() == 2 &&
 558       _components[0]->is(Component::DEF) &&
 559       _components[1]->isa(Component::USE) )
 560     rematerialize = true;
 561 
 562   // Check for an ideal 'Load?' and eliminate rematerialize option
 563   if ( is_ideal_load() != Form::none || // Ideal load?  Do not rematerialize
 564        is_ideal_copy() != Form::none || // Ideal copy?  Do not rematerialize
 565        is_expensive()  != Form::none) { // Expensive?   Do not rematerialize
 566     rematerialize = false;
 567   }
 568 
 569   // Always rematerialize the flags.  They are more expensive to save &
 570   // restore than to recompute (and possibly spill the compare's inputs).
 571   if( _components.count() >= 1 ) {
 572     Component *c = _components[0];
 573     const Form *form = globals[c->_type];
 574     OperandForm *opform = form->is_operand();
 575     if( opform ) {
 576       // Avoid the special stack_slots register classes
 577       const char *rc_name = opform->constrained_reg_class();
 578       if( rc_name ) {
 579         if( strcmp(rc_name,"stack_slots") ) {
 580           // Check for ideal_type of RegFlags
 581           const char *type = opform->ideal_type( globals, registers );
 582           if( (type != NULL) && !strcmp(type, "RegFlags") )
 583             rematerialize = true;
 584         } else
 585           rematerialize = false; // Do not rematerialize things target stk
 586       }
 587     }
 588   }
 589 
 590   return rematerialize;
 591 }
 592 
 593 // loads from memory, so must check for anti-dependence
 594 bool InstructForm::needs_anti_dependence_check(FormDict &globals) const {
 595   if ( skip_antidep_check() ) return false;
 596 
 597   // Machine independent loads must be checked for anti-dependences
 598   if( is_ideal_load() != Form::none )  return true;
 599 
 600   // !!!!! !!!!! !!!!!
 601   // TEMPORARY
 602   // if( is_simple_chain_rule(globals) )  return false;
 603 
 604   // String.(compareTo/equals/indexOf) and Arrays.equals use many memorys edges,
 605   // but writes none
 606   if( _matrule && _matrule->_rChild &&
 607       ( strcmp(_matrule->_rChild->_opType,"StrComp"    )==0 ||
 608         strcmp(_matrule->_rChild->_opType,"StrEquals"  )==0 ||
 609         strcmp(_matrule->_rChild->_opType,"StrIndexOf" )==0 ||
 610         strcmp(_matrule->_rChild->_opType,"AryEq"      )==0 ))
 611     return true;
 612 
 613   // Check if instruction has a USE of a memory operand class, but no defs
 614   bool USE_of_memory  = false;
 615   bool DEF_of_memory  = false;
 616   Component     *comp = NULL;
 617   ComponentList &components = (ComponentList &)_components;
 618 
 619   components.reset();
 620   while( (comp = components.iter()) != NULL ) {
 621     const Form  *form = globals[comp->_type];
 622     if( !form ) continue;
 623     OpClassForm *op   = form->is_opclass();
 624     if( !op ) continue;
 625     if( form->interface_type(globals) == Form::memory_interface ) {
 626       if( comp->isa(Component::USE) ) USE_of_memory = true;
 627       if( comp->isa(Component::DEF) ) {
 628         OperandForm *oper = form->is_operand();
 629         if( oper && oper->is_user_name_for_sReg() ) {
 630           // Stack slots are unaliased memory handled by allocator
 631           oper = oper;  // debug stopping point !!!!!
 632         } else {
 633           DEF_of_memory = true;
 634         }
 635       }
 636     }
 637   }
 638   return (USE_of_memory && !DEF_of_memory);
 639 }
 640 
 641 
 642 int InstructForm::memory_operand(FormDict &globals) const {
 643   // Machine independent loads must be checked for anti-dependences
 644   // Check if instruction has a USE of a memory operand class, or a def.
 645   int USE_of_memory  = 0;
 646   int DEF_of_memory  = 0;
 647   const char*    last_memory_DEF = NULL; // to test DEF/USE pairing in asserts
 648   const char*    last_memory_USE = NULL;
 649   Component     *unique          = NULL;
 650   Component     *comp            = NULL;
 651   ComponentList &components      = (ComponentList &)_components;
 652 
 653   components.reset();
 654   while( (comp = components.iter()) != NULL ) {
 655     const Form  *form = globals[comp->_type];
 656     if( !form ) continue;
 657     OpClassForm *op   = form->is_opclass();
 658     if( !op ) continue;
 659     if( op->stack_slots_only(globals) )  continue;
 660     if( form->interface_type(globals) == Form::memory_interface ) {
 661       if( comp->isa(Component::DEF) ) {
 662         last_memory_DEF = comp->_name;
 663         DEF_of_memory++;
 664         unique = comp;
 665       } else if( comp->isa(Component::USE) ) {
 666         if( last_memory_DEF != NULL ) {
 667           assert(0 == strcmp(last_memory_DEF, comp->_name), "every memory DEF is followed by a USE of the same name");
 668           last_memory_DEF = NULL;
 669         }
 670         // Handles same memory being used multiple times in the case of BMI1 instructions.
 671         if (last_memory_USE != NULL) {
 672           if (strcmp(comp->_name, last_memory_USE) != 0) {
 673             USE_of_memory++;
 674           }
 675         } else {
 676           USE_of_memory++;
 677         }
 678         last_memory_USE = comp->_name;
 679 
 680         if (DEF_of_memory == 0)  // defs take precedence
 681           unique = comp;
 682       } else {
 683         assert(last_memory_DEF == NULL, "unpaired memory DEF");
 684       }
 685     }
 686   }
 687   assert(last_memory_DEF == NULL, "unpaired memory DEF");
 688   assert(USE_of_memory >= DEF_of_memory, "unpaired memory DEF");
 689   USE_of_memory -= DEF_of_memory;   // treat paired DEF/USE as one occurrence
 690   if( (USE_of_memory + DEF_of_memory) > 0 ) {
 691     if( is_simple_chain_rule(globals) ) {
 692       //fprintf(stderr, "Warning: chain rule is not really a memory user.\n");
 693       //((InstructForm*)this)->dump();
 694       // Preceding code prints nothing on sparc and these insns on intel:
 695       // leaP8 leaP32 leaPIdxOff leaPIdxScale leaPIdxScaleOff leaP8 leaP32
 696       // leaPIdxOff leaPIdxScale leaPIdxScaleOff
 697       return NO_MEMORY_OPERAND;
 698     }
 699 
 700     if( DEF_of_memory == 1 ) {
 701       assert(unique != NULL, "");
 702       if( USE_of_memory == 0 ) {
 703         // unique def, no uses
 704       } else {
 705         // // unique def, some uses
 706         // // must return bottom unless all uses match def
 707         // unique = NULL;
 708       }
 709     } else if( DEF_of_memory > 0 ) {
 710       // multiple defs, don't care about uses
 711       unique = NULL;
 712     } else if( USE_of_memory == 1) {
 713       // unique use, no defs
 714       assert(unique != NULL, "");
 715     } else if( USE_of_memory > 0 ) {
 716       // multiple uses, no defs
 717       unique = NULL;
 718     } else {
 719       assert(false, "bad case analysis");
 720     }
 721     // process the unique DEF or USE, if there is one
 722     if( unique == NULL ) {
 723       return MANY_MEMORY_OPERANDS;
 724     } else {
 725       int pos = components.operand_position(unique->_name);
 726       if( unique->isa(Component::DEF) ) {
 727         pos += 1;                // get corresponding USE from DEF
 728       }
 729       assert(pos >= 1, "I was just looking at it!");
 730       return pos;
 731     }
 732   }
 733 
 734   // missed the memory op??
 735   if( true ) {  // %%% should not be necessary
 736     if( is_ideal_store() != Form::none ) {
 737       fprintf(stderr, "Warning: cannot find memory opnd in instr.\n");
 738       ((InstructForm*)this)->dump();
 739       // pretend it has multiple defs and uses
 740       return MANY_MEMORY_OPERANDS;
 741     }
 742     if( is_ideal_load()  != Form::none ) {
 743       fprintf(stderr, "Warning: cannot find memory opnd in instr.\n");
 744       ((InstructForm*)this)->dump();
 745       // pretend it has multiple uses and no defs
 746       return MANY_MEMORY_OPERANDS;
 747     }
 748   }
 749 
 750   return NO_MEMORY_OPERAND;
 751 }
 752 
 753 
 754 // This instruction captures the machine-independent bottom_type
 755 // Expected use is for pointer vs oop determination for LoadP
 756 bool InstructForm::captures_bottom_type(FormDict &globals) const {
 757   if( _matrule && _matrule->_rChild &&
 758        (!strcmp(_matrule->_rChild->_opType,"CastPP")       ||  // new result type
 759         !strcmp(_matrule->_rChild->_opType,"CastX2P")      ||  // new result type
 760         !strcmp(_matrule->_rChild->_opType,"DecodeN")      ||
 761         !strcmp(_matrule->_rChild->_opType,"EncodeP")      ||
 762         !strcmp(_matrule->_rChild->_opType,"DecodeNKlass") ||
 763         !strcmp(_matrule->_rChild->_opType,"EncodePKlass") ||
 764         !strcmp(_matrule->_rChild->_opType,"LoadN")        ||
 765         !strcmp(_matrule->_rChild->_opType,"LoadNKlass")   ||
 766         !strcmp(_matrule->_rChild->_opType,"CreateEx")     ||  // type of exception
 767         !strcmp(_matrule->_rChild->_opType,"CheckCastPP")  ||
 768         !strcmp(_matrule->_rChild->_opType,"GetAndSetP")   ||
 769         !strcmp(_matrule->_rChild->_opType,"GetAndSetN")   ||
 770         !strcmp(_matrule->_rChild->_opType,"ShenandoahReadBarrier"))) return true;
 771   else if ( is_ideal_load() == Form::idealP )                return true;
 772   else if ( is_ideal_store() != Form::none  )                return true;
 773 
 774   if (needs_base_oop_edge(globals)) return true;
 775 
 776   if (is_vector()) return true;
 777   if (is_mach_constant()) return true;
 778 
 779   return  false;
 780 }
 781 
 782 
 783 // Access instr_cost attribute or return NULL.
 784 const char* InstructForm::cost() {
 785   for (Attribute* cur = _attribs; cur != NULL; cur = (Attribute*)cur->_next) {
 786     if( strcmp(cur->_ident,AttributeForm::_ins_cost) == 0 ) {
 787       return cur->_val;
 788     }
 789   }
 790   return NULL;
 791 }
 792 
 793 // Return count of top-level operands.
 794 uint InstructForm::num_opnds() {
 795   int  num_opnds = _components.num_operands();
 796 
 797   // Need special handling for matching some ideal nodes
 798   // i.e. Matching a return node
 799   /*
 800   if( _matrule ) {
 801     if( strcmp(_matrule->_opType,"Return"   )==0 ||
 802         strcmp(_matrule->_opType,"Halt"     )==0 )
 803       return 3;
 804   }
 805     */
 806   return num_opnds;
 807 }
 808 
 809 const char* InstructForm::opnd_ident(int idx) {
 810   return _components.at(idx)->_name;
 811 }
 812 
 813 const char* InstructForm::unique_opnd_ident(uint idx) {
 814   uint i;
 815   for (i = 1; i < num_opnds(); ++i) {
 816     if (unique_opnds_idx(i) == idx) {
 817       break;
 818     }
 819   }
 820   return (_components.at(i) != NULL) ? _components.at(i)->_name : "";
 821 }
 822 
 823 // Return count of unmatched operands.
 824 uint InstructForm::num_post_match_opnds() {
 825   uint  num_post_match_opnds = _components.count();
 826   uint  num_match_opnds = _components.match_count();
 827   num_post_match_opnds = num_post_match_opnds - num_match_opnds;
 828 
 829   return num_post_match_opnds;
 830 }
 831 
 832 // Return the number of leaves below this complex operand
 833 uint InstructForm::num_consts(FormDict &globals) const {
 834   if ( ! _matrule) return 0;
 835 
 836   // This is a recursive invocation on all operands in the matchrule
 837   return _matrule->num_consts(globals);
 838 }
 839 
 840 // Constants in match rule with specified type
 841 uint InstructForm::num_consts(FormDict &globals, Form::DataType type) const {
 842   if ( ! _matrule) return 0;
 843 
 844   // This is a recursive invocation on all operands in the matchrule
 845   return _matrule->num_consts(globals, type);
 846 }
 847 
 848 
 849 // Return the register class associated with 'leaf'.
 850 const char *InstructForm::out_reg_class(FormDict &globals) {
 851   assert( false, "InstructForm::out_reg_class(FormDict &globals); Not Implemented");
 852 
 853   return NULL;
 854 }
 855 
 856 
 857 
 858 // Lookup the starting position of inputs we are interested in wrt. ideal nodes
 859 uint InstructForm::oper_input_base(FormDict &globals) {
 860   if( !_matrule ) return 1;     // Skip control for most nodes
 861 
 862   // Need special handling for matching some ideal nodes
 863   // i.e. Matching a return node
 864   if( strcmp(_matrule->_opType,"Return"    )==0 ||
 865       strcmp(_matrule->_opType,"Rethrow"   )==0 ||
 866       strcmp(_matrule->_opType,"TailCall"  )==0 ||
 867       strcmp(_matrule->_opType,"TailJump"  )==0 ||
 868       strcmp(_matrule->_opType,"SafePoint" )==0 ||
 869       strcmp(_matrule->_opType,"Halt"      )==0 )
 870     return AdlcVMDeps::Parms;   // Skip the machine-state edges
 871 
 872   if( _matrule->_rChild &&
 873       ( strcmp(_matrule->_rChild->_opType,"AryEq"     )==0 ||
 874         strcmp(_matrule->_rChild->_opType,"StrComp"   )==0 ||
 875         strcmp(_matrule->_rChild->_opType,"StrEquals" )==0 ||
 876         strcmp(_matrule->_rChild->_opType,"StrIndexOf")==0 ||
 877         strcmp(_matrule->_rChild->_opType,"EncodeISOArray")==0)) {
 878         // String.(compareTo/equals/indexOf) and Arrays.equals
 879         // and sun.nio.cs.iso8859_1$Encoder.EncodeISOArray
 880         // take 1 control and 1 memory edges.
 881     return 2;
 882   }
 883 
 884   // Check for handling of 'Memory' input/edge in the ideal world.
 885   // The AD file writer is shielded from knowledge of these edges.
 886   int base = 1;                 // Skip control
 887   base += _matrule->needs_ideal_memory_edge(globals);
 888 
 889   // Also skip the base-oop value for uses of derived oops.
 890   // The AD file writer is shielded from knowledge of these edges.
 891   base += needs_base_oop_edge(globals);
 892 
 893   return base;
 894 }
 895 
 896 // This function determines the order of the MachOper in _opnds[]
 897 // by writing the operand names into the _components list.
 898 //
 899 // Implementation does not modify state of internal structures
 900 void InstructForm::build_components() {
 901   // Add top-level operands to the components
 902   if (_matrule)  _matrule->append_components(_localNames, _components);
 903 
 904   // Add parameters that "do not appear in match rule".
 905   bool has_temp = false;
 906   const char *name;
 907   const char *kill_name = NULL;
 908   for (_parameters.reset(); (name = _parameters.iter()) != NULL;) {
 909     OpClassForm *opForm = _localNames[name]->is_opclass();
 910     assert(opForm != NULL, "sanity");
 911 
 912     Effect* e = NULL;
 913     {
 914       const Form* form = _effects[name];
 915       e = form ? form->is_effect() : NULL;
 916     }
 917 
 918     if (e != NULL) {
 919       has_temp |= e->is(Component::TEMP);
 920 
 921       // KILLs must be declared after any TEMPs because TEMPs are real
 922       // uses so their operand numbering must directly follow the real
 923       // inputs from the match rule.  Fixing the numbering seems
 924       // complex so simply enforce the restriction during parse.
 925       if (kill_name != NULL &&
 926           e->isa(Component::TEMP) && !e->isa(Component::DEF)) {
 927         OpClassForm* kill = _localNames[kill_name]->is_opclass();
 928         assert(kill != NULL, "sanity");
 929         globalAD->syntax_err(_linenum, "%s: %s %s must be at the end of the argument list\n",
 930                              _ident, kill->_ident, kill_name);
 931       } else if (e->isa(Component::KILL) && !e->isa(Component::USE)) {
 932         kill_name = name;
 933       }
 934     }
 935 
 936     const Component *component  = _components.search(name);
 937     if ( component  == NULL ) {
 938       if (e) {
 939         _components.insert(name, opForm->_ident, e->_use_def, false);
 940         component = _components.search(name);
 941         if (component->isa(Component::USE) && !component->isa(Component::TEMP) && _matrule) {
 942           const Form *form = globalAD->globalNames()[component->_type];
 943           assert( form, "component type must be a defined form");
 944           OperandForm *op   = form->is_operand();
 945           if (op->_interface && op->_interface->is_RegInterface()) {
 946             globalAD->syntax_err(_linenum, "%s: illegal USE of non-input: %s %s\n",
 947                                  _ident, opForm->_ident, name);
 948           }
 949         }
 950       } else {
 951         // This would be a nice warning but it triggers in a few places in a benign way
 952         // if (_matrule != NULL && !expands()) {
 953         //   globalAD->syntax_err(_linenum, "%s: %s %s not mentioned in effect or match rule\n",
 954         //                        _ident, opForm->_ident, name);
 955         // }
 956         _components.insert(name, opForm->_ident, Component::INVALID, false);
 957       }
 958     }
 959     else if (e) {
 960       // Component was found in the list
 961       // Check if there is a new effect that requires an extra component.
 962       // This happens when adding 'USE' to a component that is not yet one.
 963       if ((!component->isa( Component::USE) && ((e->_use_def & Component::USE) != 0))) {
 964         if (component->isa(Component::USE) && _matrule) {
 965           const Form *form = globalAD->globalNames()[component->_type];
 966           assert( form, "component type must be a defined form");
 967           OperandForm *op   = form->is_operand();
 968           if (op->_interface && op->_interface->is_RegInterface()) {
 969             globalAD->syntax_err(_linenum, "%s: illegal USE of non-input: %s %s\n",
 970                                  _ident, opForm->_ident, name);
 971           }
 972         }
 973         _components.insert(name, opForm->_ident, e->_use_def, false);
 974       } else {
 975         Component  *comp = (Component*)component;
 976         comp->promote_use_def_info(e->_use_def);
 977       }
 978       // Component positions are zero based.
 979       int  pos  = _components.operand_position(name);
 980       assert( ! (component->isa(Component::DEF) && (pos >= 1)),
 981               "Component::DEF can only occur in the first position");
 982     }
 983   }
 984 
 985   // Resolving the interactions between expand rules and TEMPs would
 986   // be complex so simply disallow it.
 987   if (_matrule == NULL && has_temp) {
 988     globalAD->syntax_err(_linenum, "%s: TEMPs without match rule isn't supported\n", _ident);
 989   }
 990 
 991   return;
 992 }
 993 
 994 // Return zero-based position in component list;  -1 if not in list.
 995 int   InstructForm::operand_position(const char *name, int usedef) {
 996   return unique_opnds_idx(_components.operand_position(name, usedef, this));
 997 }
 998 
 999 int   InstructForm::operand_position_format(const char *name) {
1000   return unique_opnds_idx(_components.operand_position_format(name, this));
1001 }
1002 
1003 // Return zero-based position in component list; -1 if not in list.
1004 int   InstructForm::label_position() {
1005   return unique_opnds_idx(_components.label_position());
1006 }
1007 
1008 int   InstructForm::method_position() {
1009   return unique_opnds_idx(_components.method_position());
1010 }
1011 
1012 // Return number of relocation entries needed for this instruction.
1013 uint  InstructForm::reloc(FormDict &globals) {
1014   uint reloc_entries  = 0;
1015   // Check for "Call" nodes
1016   if ( is_ideal_call() )      ++reloc_entries;
1017   if ( is_ideal_return() )    ++reloc_entries;
1018   if ( is_ideal_safepoint() ) ++reloc_entries;
1019 
1020 
1021   // Check if operands MAYBE oop pointers, by checking for ConP elements
1022   // Proceed through the leaves of the match-tree and check for ConPs
1023   if ( _matrule != NULL ) {
1024     uint         position = 0;
1025     const char  *result   = NULL;
1026     const char  *name     = NULL;
1027     const char  *opType   = NULL;
1028     while (_matrule->base_operand(position, globals, result, name, opType)) {
1029       if ( strcmp(opType,"ConP") == 0 ) {
1030 #ifdef SPARC
1031         reloc_entries += 2; // 1 for sethi + 1 for setlo
1032 #else
1033         ++reloc_entries;
1034 #endif
1035       }
1036       ++position;
1037     }
1038   }
1039 
1040   // Above is only a conservative estimate
1041   // because it did not check contents of operand classes.
1042   // !!!!! !!!!!
1043   // Add 1 to reloc info for each operand class in the component list.
1044   Component  *comp;
1045   _components.reset();
1046   while ( (comp = _components.iter()) != NULL ) {
1047     const Form        *form = globals[comp->_type];
1048     assert( form, "Did not find component's type in global names");
1049     const OpClassForm *opc  = form->is_opclass();
1050     const OperandForm *oper = form->is_operand();
1051     if ( opc && (oper == NULL) ) {
1052       ++reloc_entries;
1053     } else if ( oper ) {
1054       // floats and doubles loaded out of method's constant pool require reloc info
1055       Form::DataType type = oper->is_base_constant(globals);
1056       if ( (type == Form::idealF) || (type == Form::idealD) ) {
1057         ++reloc_entries;
1058       }
1059     }
1060   }
1061 
1062   // Float and Double constants may come from the CodeBuffer table
1063   // and require relocatable addresses for access
1064   // !!!!!
1065   // Check for any component being an immediate float or double.
1066   Form::DataType data_type = is_chain_of_constant(globals);
1067   if( data_type==idealD || data_type==idealF ) {
1068 #ifdef SPARC
1069     // sparc required more relocation entries for floating constants
1070     // (expires 9/98)
1071     reloc_entries += 6;
1072 #else
1073     reloc_entries++;
1074 #endif
1075   }
1076 
1077   return reloc_entries;
1078 }
1079 
1080 // Utility function defined in archDesc.cpp
1081 extern bool is_def(int usedef);
1082 
1083 // Return the result of reducing an instruction
1084 const char *InstructForm::reduce_result() {
1085   const char* result = "Universe";  // default
1086   _components.reset();
1087   Component *comp = _components.iter();
1088   if (comp != NULL && comp->isa(Component::DEF)) {
1089     result = comp->_type;
1090     // Override this if the rule is a store operation:
1091     if (_matrule && _matrule->_rChild &&
1092         is_store_to_memory(_matrule->_rChild->_opType))
1093       result = "Universe";
1094   }
1095   return result;
1096 }
1097 
1098 // Return the name of the operand on the right hand side of the binary match
1099 // Return NULL if there is no right hand side
1100 const char *InstructForm::reduce_right(FormDict &globals)  const {
1101   if( _matrule == NULL ) return NULL;
1102   return  _matrule->reduce_right(globals);
1103 }
1104 
1105 // Similar for left
1106 const char *InstructForm::reduce_left(FormDict &globals)   const {
1107   if( _matrule == NULL ) return NULL;
1108   return  _matrule->reduce_left(globals);
1109 }
1110 
1111 
1112 // Base class for this instruction, MachNode except for calls
1113 const char *InstructForm::mach_base_class(FormDict &globals)  const {
1114   if( is_ideal_call() == Form::JAVA_STATIC ) {
1115     return "MachCallStaticJavaNode";
1116   }
1117   else if( is_ideal_call() == Form::JAVA_DYNAMIC ) {
1118     return "MachCallDynamicJavaNode";
1119   }
1120   else if( is_ideal_call() == Form::JAVA_RUNTIME ) {
1121     return "MachCallRuntimeNode";
1122   }
1123   else if( is_ideal_call() == Form::JAVA_LEAF ) {
1124     return "MachCallLeafNode";
1125   }
1126   else if (is_ideal_return()) {
1127     return "MachReturnNode";
1128   }
1129   else if (is_ideal_halt()) {
1130     return "MachHaltNode";
1131   }
1132   else if (is_ideal_safepoint()) {
1133     return "MachSafePointNode";
1134   }
1135   else if (is_ideal_if()) {
1136     return "MachIfNode";
1137   }
1138   else if (is_ideal_goto()) {
1139     return "MachGotoNode";
1140   }
1141   else if (is_ideal_fastlock()) {
1142     return "MachFastLockNode";
1143   }
1144   else if (is_ideal_nop()) {
1145     return "MachNopNode";
1146   }
1147   else if (is_ideal_membar()) {
1148     return "MachMemBarNode";
1149   }
1150   else if (is_mach_constant()) {
1151     return "MachConstantNode";
1152   }
1153   else if (captures_bottom_type(globals)) {
1154     return "MachTypeNode";
1155   } else {
1156     return "MachNode";
1157   }
1158   assert( false, "ShouldNotReachHere()");
1159   return NULL;
1160 }
1161 
1162 // Compare the instruction predicates for textual equality
1163 bool equivalent_predicates( const InstructForm *instr1, const InstructForm *instr2 ) {
1164   const Predicate *pred1  = instr1->_predicate;
1165   const Predicate *pred2  = instr2->_predicate;
1166   if( pred1 == NULL && pred2 == NULL ) {
1167     // no predicates means they are identical
1168     return true;
1169   }
1170   if( pred1 != NULL && pred2 != NULL ) {
1171     // compare the predicates
1172     if (ADLParser::equivalent_expressions(pred1->_pred, pred2->_pred)) {
1173       return true;
1174     }
1175   }
1176 
1177   return false;
1178 }
1179 
1180 // Check if this instruction can cisc-spill to 'alternate'
1181 bool InstructForm::cisc_spills_to(ArchDesc &AD, InstructForm *instr) {
1182   assert( _matrule != NULL && instr->_matrule != NULL, "must have match rules");
1183   // Do not replace if a cisc-version has been found.
1184   if( cisc_spill_operand() != Not_cisc_spillable ) return false;
1185 
1186   int         cisc_spill_operand = Maybe_cisc_spillable;
1187   char       *result             = NULL;
1188   char       *result2            = NULL;
1189   const char *op_name            = NULL;
1190   const char *reg_type           = NULL;
1191   FormDict   &globals            = AD.globalNames();
1192   cisc_spill_operand = _matrule->matchrule_cisc_spill_match(globals, AD.get_registers(), instr->_matrule, op_name, reg_type);
1193   if( (cisc_spill_operand != Not_cisc_spillable) && (op_name != NULL) && equivalent_predicates(this, instr) ) {
1194     cisc_spill_operand = operand_position(op_name, Component::USE);
1195     int def_oper  = operand_position(op_name, Component::DEF);
1196     if( def_oper == NameList::Not_in_list && instr->num_opnds() == num_opnds()) {
1197       // Do not support cisc-spilling for destination operands and
1198       // make sure they have the same number of operands.
1199       _cisc_spill_alternate = instr;
1200       instr->set_cisc_alternate(true);
1201       if( AD._cisc_spill_debug ) {
1202         fprintf(stderr, "Instruction %s cisc-spills-to %s\n", _ident, instr->_ident);
1203         fprintf(stderr, "   using operand %s %s at index %d\n", reg_type, op_name, cisc_spill_operand);
1204       }
1205       // Record that a stack-version of the reg_mask is needed
1206       // !!!!!
1207       OperandForm *oper = (OperandForm*)(globals[reg_type]->is_operand());
1208       assert( oper != NULL, "cisc-spilling non operand");
1209       const char *reg_class_name = oper->constrained_reg_class();
1210       AD.set_stack_or_reg(reg_class_name);
1211       const char *reg_mask_name  = AD.reg_mask(*oper);
1212       set_cisc_reg_mask_name(reg_mask_name);
1213       const char *stack_or_reg_mask_name = AD.stack_or_reg_mask(*oper);
1214     } else {
1215       cisc_spill_operand = Not_cisc_spillable;
1216     }
1217   } else {
1218     cisc_spill_operand = Not_cisc_spillable;
1219   }
1220 
1221   set_cisc_spill_operand(cisc_spill_operand);
1222   return (cisc_spill_operand != Not_cisc_spillable);
1223 }
1224 
1225 // Check to see if this instruction can be replaced with the short branch
1226 // instruction `short-branch'
1227 bool InstructForm::check_branch_variant(ArchDesc &AD, InstructForm *short_branch) {
1228   if (_matrule != NULL &&
1229       this != short_branch &&   // Don't match myself
1230       !is_short_branch() &&     // Don't match another short branch variant
1231       reduce_result() != NULL &&
1232       strcmp(reduce_result(), short_branch->reduce_result()) == 0 &&
1233       _matrule->equivalent(AD.globalNames(), short_branch->_matrule) &&
1234       equivalent_predicates(this, short_branch)) {
1235     // The instructions are equivalent.
1236 
1237     // Now verify that both instructions have the same parameters and
1238     // the same effects. Both branch forms should have the same inputs
1239     // and resulting projections to correctly replace a long branch node
1240     // with corresponding short branch node during code generation.
1241 
1242     bool different = false;
1243     if (short_branch->_components.count() != _components.count()) {
1244        different = true;
1245     } else if (_components.count() > 0) {
1246       short_branch->_components.reset();
1247       _components.reset();
1248       Component *comp;
1249       while ((comp = _components.iter()) != NULL) {
1250         Component *short_comp = short_branch->_components.iter();
1251         if (short_comp == NULL ||
1252             short_comp->_type != comp->_type ||
1253             short_comp->_usedef != comp->_usedef) {
1254           different = true;
1255           break;
1256         }
1257       }
1258       if (short_branch->_components.iter() != NULL)
1259         different = true;
1260     }
1261     if (different) {
1262       globalAD->syntax_err(short_branch->_linenum, "Instruction %s and its short form %s have different parameters\n", _ident, short_branch->_ident);
1263     }
1264     if (AD._adl_debug > 1 || AD._short_branch_debug) {
1265       fprintf(stderr, "Instruction %s has short form %s\n", _ident, short_branch->_ident);
1266     }
1267     _short_branch_form = short_branch;
1268     return true;
1269   }
1270   return false;
1271 }
1272 
1273 
1274 // --------------------------- FILE *output_routines
1275 //
1276 // Generate the format call for the replacement variable
1277 void InstructForm::rep_var_format(FILE *fp, const char *rep_var) {
1278   // Handle special constant table variables.
1279   if (strcmp(rep_var, "constanttablebase") == 0) {
1280     fprintf(fp, "char reg[128];  ra->dump_register(in(mach_constant_base_node_input()), reg);\n");
1281     fprintf(fp, "    st->print(\"%%s\", reg);\n");
1282     return;
1283   }
1284   if (strcmp(rep_var, "constantoffset") == 0) {
1285     fprintf(fp, "st->print(\"#%%d\", constant_offset_unchecked());\n");
1286     return;
1287   }
1288   if (strcmp(rep_var, "constantaddress") == 0) {
1289     fprintf(fp, "st->print(\"constant table base + #%%d\", constant_offset_unchecked());\n");
1290     return;
1291   }
1292 
1293   // Find replacement variable's type
1294   const Form *form   = _localNames[rep_var];
1295   if (form == NULL) {
1296     globalAD->syntax_err(_linenum, "Unknown replacement variable %s in format statement of %s.",
1297                          rep_var, _ident);
1298     return;
1299   }
1300   OpClassForm *opc   = form->is_opclass();
1301   assert( opc, "replacement variable was not found in local names");
1302   // Lookup the index position of the replacement variable
1303   int idx  = operand_position_format(rep_var);
1304   if ( idx == -1 ) {
1305     globalAD->syntax_err(_linenum, "Could not find replacement variable %s in format statement of %s.\n",
1306                          rep_var, _ident);
1307     assert(strcmp(opc->_ident, "label") == 0, "Unimplemented");
1308     return;
1309   }
1310 
1311   if (is_noninput_operand(idx)) {
1312     // This component isn't in the input array.  Print out the static
1313     // name of the register.
1314     OperandForm* oper = form->is_operand();
1315     if (oper != NULL && oper->is_bound_register()) {
1316       const RegDef* first = oper->get_RegClass()->find_first_elem();
1317       fprintf(fp, "    st->print_raw(\"%s\");\n", first->_regname);
1318     } else {
1319       globalAD->syntax_err(_linenum, "In %s can't find format for %s %s", _ident, opc->_ident, rep_var);
1320     }
1321   } else {
1322     // Output the format call for this operand
1323     fprintf(fp,"opnd_array(%d)->",idx);
1324     if (idx == 0)
1325       fprintf(fp,"int_format(ra, this, st); // %s\n", rep_var);
1326     else
1327       fprintf(fp,"ext_format(ra, this,idx%d, st); // %s\n", idx, rep_var );
1328   }
1329 }
1330 
1331 // Seach through operands to determine parameters unique positions.
1332 void InstructForm::set_unique_opnds() {
1333   uint* uniq_idx = NULL;
1334   uint  nopnds = num_opnds();
1335   uint  num_uniq = nopnds;
1336   uint i;
1337   _uniq_idx_length = 0;
1338   if (nopnds > 0) {
1339     // Allocate index array.  Worst case we're mapping from each
1340     // component back to an index and any DEF always goes at 0 so the
1341     // length of the array has to be the number of components + 1.
1342     _uniq_idx_length = _components.count() + 1;
1343     uniq_idx = (uint*) malloc(sizeof(uint) * _uniq_idx_length);
1344     for (i = 0; i < _uniq_idx_length; i++) {
1345       uniq_idx[i] = i;
1346     }
1347   }
1348   // Do it only if there is a match rule and no expand rule.  With an
1349   // expand rule it is done by creating new mach node in Expand()
1350   // method.
1351   if (nopnds > 0 && _matrule != NULL && _exprule == NULL) {
1352     const char *name;
1353     uint count;
1354     bool has_dupl_use = false;
1355 
1356     _parameters.reset();
1357     while ((name = _parameters.iter()) != NULL) {
1358       count = 0;
1359       uint position = 0;
1360       uint uniq_position = 0;
1361       _components.reset();
1362       Component *comp = NULL;
1363       if (sets_result()) {
1364         comp = _components.iter();
1365         position++;
1366       }
1367       // The next code is copied from the method operand_position().
1368       for (; (comp = _components.iter()) != NULL; ++position) {
1369         // When the first component is not a DEF,
1370         // leave space for the result operand!
1371         if (position==0 && (!comp->isa(Component::DEF))) {
1372           ++position;
1373         }
1374         if (strcmp(name, comp->_name) == 0) {
1375           if (++count > 1) {
1376             assert(position < _uniq_idx_length, "out of bounds");
1377             uniq_idx[position] = uniq_position;
1378             has_dupl_use = true;
1379           } else {
1380             uniq_position = position;
1381           }
1382         }
1383         if (comp->isa(Component::DEF) && comp->isa(Component::USE)) {
1384           ++position;
1385           if (position != 1)
1386             --position;   // only use two slots for the 1st USE_DEF
1387         }
1388       }
1389     }
1390     if (has_dupl_use) {
1391       for (i = 1; i < nopnds; i++) {
1392         if (i != uniq_idx[i]) {
1393           break;
1394         }
1395       }
1396       uint j = i;
1397       for (; i < nopnds; i++) {
1398         if (i == uniq_idx[i]) {
1399           uniq_idx[i] = j++;
1400         }
1401       }
1402       num_uniq = j;
1403     }
1404   }
1405   _uniq_idx = uniq_idx;
1406   _num_uniq = num_uniq;
1407 }
1408 
1409 // Generate index values needed for determining the operand position
1410 void InstructForm::index_temps(FILE *fp, FormDict &globals, const char *prefix, const char *receiver) {
1411   uint  idx = 0;                  // position of operand in match rule
1412   int   cur_num_opnds = num_opnds();
1413 
1414   // Compute the index into vector of operand pointers:
1415   // idx0=0 is used to indicate that info comes from this same node, not from input edge.
1416   // idx1 starts at oper_input_base()
1417   if ( cur_num_opnds >= 1 ) {
1418     fprintf(fp,"  // Start at oper_input_base() and count operands\n");
1419     fprintf(fp,"  unsigned %sidx0 = %d;\n", prefix, oper_input_base(globals));
1420     fprintf(fp,"  unsigned %sidx1 = %d;", prefix, oper_input_base(globals));
1421     fprintf(fp," \t// %s\n", unique_opnd_ident(1));
1422 
1423     // Generate starting points for other unique operands if they exist
1424     for ( idx = 2; idx < num_unique_opnds(); ++idx ) {
1425       if( *receiver == 0 ) {
1426         fprintf(fp,"  unsigned %sidx%d = %sidx%d + opnd_array(%d)->num_edges();",
1427                 prefix, idx, prefix, idx-1, idx-1 );
1428       } else {
1429         fprintf(fp,"  unsigned %sidx%d = %sidx%d + %s_opnds[%d]->num_edges();",
1430                 prefix, idx, prefix, idx-1, receiver, idx-1 );
1431       }
1432       fprintf(fp," \t// %s\n", unique_opnd_ident(idx));
1433     }
1434   }
1435   if( *receiver != 0 ) {
1436     // This value is used by generate_peepreplace when copying a node.
1437     // Don't emit it in other cases since it can hide bugs with the
1438     // use invalid idx's.
1439     fprintf(fp,"  unsigned %sidx%d = %sreq(); \n", prefix, idx, receiver);
1440   }
1441 
1442 }
1443 
1444 // ---------------------------
1445 bool InstructForm::verify() {
1446   // !!!!! !!!!!
1447   // Check that a "label" operand occurs last in the operand list, if present
1448   return true;
1449 }
1450 
1451 void InstructForm::dump() {
1452   output(stderr);
1453 }
1454 
1455 void InstructForm::output(FILE *fp) {
1456   fprintf(fp,"\nInstruction: %s\n", (_ident?_ident:""));
1457   if (_matrule)   _matrule->output(fp);
1458   if (_insencode) _insencode->output(fp);
1459   if (_constant)  _constant->output(fp);
1460   if (_opcode)    _opcode->output(fp);
1461   if (_attribs)   _attribs->output(fp);
1462   if (_predicate) _predicate->output(fp);
1463   if (_effects.Size()) {
1464     fprintf(fp,"Effects\n");
1465     _effects.dump();
1466   }
1467   if (_exprule)   _exprule->output(fp);
1468   if (_rewrule)   _rewrule->output(fp);
1469   if (_format)    _format->output(fp);
1470   if (_peephole)  _peephole->output(fp);
1471 }
1472 
1473 void MachNodeForm::dump() {
1474   output(stderr);
1475 }
1476 
1477 void MachNodeForm::output(FILE *fp) {
1478   fprintf(fp,"\nMachNode: %s\n", (_ident?_ident:""));
1479 }
1480 
1481 //------------------------------build_predicate--------------------------------
1482 // Build instruction predicates.  If the user uses the same operand name
1483 // twice, we need to check that the operands are pointer-eequivalent in
1484 // the DFA during the labeling process.
1485 Predicate *InstructForm::build_predicate() {
1486   char buf[1024], *s=buf;
1487   Dict names(cmpstr,hashstr,Form::arena);       // Map Names to counts
1488 
1489   MatchNode *mnode =
1490     strcmp(_matrule->_opType, "Set") ? _matrule : _matrule->_rChild;
1491   mnode->count_instr_names(names);
1492 
1493   uint first = 1;
1494   // Start with the predicate supplied in the .ad file.
1495   if( _predicate ) {
1496     if( first ) first=0;
1497     strcpy(s,"("); s += strlen(s);
1498     strcpy(s,_predicate->_pred);
1499     s += strlen(s);
1500     strcpy(s,")"); s += strlen(s);
1501   }
1502   for( DictI i(&names); i.test(); ++i ) {
1503     uintptr_t cnt = (uintptr_t)i._value;
1504     if( cnt > 1 ) {             // Need a predicate at all?
1505       assert( cnt == 2, "Unimplemented" );
1506       // Handle many pairs
1507       if( first ) first=0;
1508       else {                    // All tests must pass, so use '&&'
1509         strcpy(s," && ");
1510         s += strlen(s);
1511       }
1512       // Add predicate to working buffer
1513       sprintf(s,"/*%s*/(",(char*)i._key);
1514       s += strlen(s);
1515       mnode->build_instr_pred(s,(char*)i._key,0);
1516       s += strlen(s);
1517       strcpy(s," == "); s += strlen(s);
1518       mnode->build_instr_pred(s,(char*)i._key,1);
1519       s += strlen(s);
1520       strcpy(s,")"); s += strlen(s);
1521     }
1522   }
1523   if( s == buf ) s = NULL;
1524   else {
1525     assert( strlen(buf) < sizeof(buf), "String buffer overflow" );
1526     s = strdup(buf);
1527   }
1528   return new Predicate(s);
1529 }
1530 
1531 //------------------------------EncodeForm-------------------------------------
1532 // Constructor
1533 EncodeForm::EncodeForm()
1534   : _encClass(cmpstr,hashstr, Form::arena) {
1535 }
1536 EncodeForm::~EncodeForm() {
1537 }
1538 
1539 // record a new register class
1540 EncClass *EncodeForm::add_EncClass(const char *className) {
1541   EncClass *encClass = new EncClass(className);
1542   _eclasses.addName(className);
1543   _encClass.Insert(className,encClass);
1544   return encClass;
1545 }
1546 
1547 // Lookup the function body for an encoding class
1548 EncClass  *EncodeForm::encClass(const char *className) {
1549   assert( className != NULL, "Must provide a defined encoding name");
1550 
1551   EncClass *encClass = (EncClass*)_encClass[className];
1552   return encClass;
1553 }
1554 
1555 // Lookup the function body for an encoding class
1556 const char *EncodeForm::encClassBody(const char *className) {
1557   if( className == NULL ) return NULL;
1558 
1559   EncClass *encClass = (EncClass*)_encClass[className];
1560   assert( encClass != NULL, "Encode Class is missing.");
1561   encClass->_code.reset();
1562   const char *code = (const char*)encClass->_code.iter();
1563   assert( code != NULL, "Found an empty encode class body.");
1564 
1565   return code;
1566 }
1567 
1568 // Lookup the function body for an encoding class
1569 const char *EncodeForm::encClassPrototype(const char *className) {
1570   assert( className != NULL, "Encode class name must be non NULL.");
1571 
1572   return className;
1573 }
1574 
1575 void EncodeForm::dump() {                  // Debug printer
1576   output(stderr);
1577 }
1578 
1579 void EncodeForm::output(FILE *fp) {          // Write info to output files
1580   const char *name;
1581   fprintf(fp,"\n");
1582   fprintf(fp,"-------------------- Dump EncodeForm --------------------\n");
1583   for (_eclasses.reset(); (name = _eclasses.iter()) != NULL;) {
1584     ((EncClass*)_encClass[name])->output(fp);
1585   }
1586   fprintf(fp,"-------------------- end  EncodeForm --------------------\n");
1587 }
1588 //------------------------------EncClass---------------------------------------
1589 EncClass::EncClass(const char *name)
1590   : _localNames(cmpstr,hashstr, Form::arena), _name(name) {
1591 }
1592 EncClass::~EncClass() {
1593 }
1594 
1595 // Add a parameter <type,name> pair
1596 void EncClass::add_parameter(const char *parameter_type, const char *parameter_name) {
1597   _parameter_type.addName( parameter_type );
1598   _parameter_name.addName( parameter_name );
1599 }
1600 
1601 // Verify operand types in parameter list
1602 bool EncClass::check_parameter_types(FormDict &globals) {
1603   // !!!!!
1604   return false;
1605 }
1606 
1607 // Add the decomposed "code" sections of an encoding's code-block
1608 void EncClass::add_code(const char *code) {
1609   _code.addName(code);
1610 }
1611 
1612 // Add the decomposed "replacement variables" of an encoding's code-block
1613 void EncClass::add_rep_var(char *replacement_var) {
1614   _code.addName(NameList::_signal);
1615   _rep_vars.addName(replacement_var);
1616 }
1617 
1618 // Lookup the function body for an encoding class
1619 int EncClass::rep_var_index(const char *rep_var) {
1620   uint        position = 0;
1621   const char *name     = NULL;
1622 
1623   _parameter_name.reset();
1624   while ( (name = _parameter_name.iter()) != NULL ) {
1625     if ( strcmp(rep_var,name) == 0 ) return position;
1626     ++position;
1627   }
1628 
1629   return -1;
1630 }
1631 
1632 // Check after parsing
1633 bool EncClass::verify() {
1634   // 1!!!!
1635   // Check that each replacement variable, '$name' in architecture description
1636   // is actually a local variable for this encode class, or a reserved name
1637   // "primary, secondary, tertiary"
1638   return true;
1639 }
1640 
1641 void EncClass::dump() {
1642   output(stderr);
1643 }
1644 
1645 // Write info to output files
1646 void EncClass::output(FILE *fp) {
1647   fprintf(fp,"EncClass: %s", (_name ? _name : ""));
1648 
1649   // Output the parameter list
1650   _parameter_type.reset();
1651   _parameter_name.reset();
1652   const char *type = _parameter_type.iter();
1653   const char *name = _parameter_name.iter();
1654   fprintf(fp, " ( ");
1655   for ( ; (type != NULL) && (name != NULL);
1656         (type = _parameter_type.iter()), (name = _parameter_name.iter()) ) {
1657     fprintf(fp, " %s %s,", type, name);
1658   }
1659   fprintf(fp, " ) ");
1660 
1661   // Output the code block
1662   _code.reset();
1663   _rep_vars.reset();
1664   const char *code;
1665   while ( (code = _code.iter()) != NULL ) {
1666     if ( _code.is_signal(code) ) {
1667       // A replacement variable
1668       const char *rep_var = _rep_vars.iter();
1669       fprintf(fp,"($%s)", rep_var);
1670     } else {
1671       // A section of code
1672       fprintf(fp,"%s", code);
1673     }
1674   }
1675 
1676 }
1677 
1678 //------------------------------Opcode-----------------------------------------
1679 Opcode::Opcode(char *primary, char *secondary, char *tertiary)
1680   : _primary(primary), _secondary(secondary), _tertiary(tertiary) {
1681 }
1682 
1683 Opcode::~Opcode() {
1684 }
1685 
1686 Opcode::opcode_type Opcode::as_opcode_type(const char *param) {
1687   if( strcmp(param,"primary") == 0 ) {
1688     return Opcode::PRIMARY;
1689   }
1690   else if( strcmp(param,"secondary") == 0 ) {
1691     return Opcode::SECONDARY;
1692   }
1693   else if( strcmp(param,"tertiary") == 0 ) {
1694     return Opcode::TERTIARY;
1695   }
1696   return Opcode::NOT_AN_OPCODE;
1697 }
1698 
1699 bool Opcode::print_opcode(FILE *fp, Opcode::opcode_type desired_opcode) {
1700   // Default values previously provided by MachNode::primary()...
1701   const char *description = NULL;
1702   const char *value       = NULL;
1703   // Check if user provided any opcode definitions
1704   if( this != NULL ) {
1705     // Update 'value' if user provided a definition in the instruction
1706     switch (desired_opcode) {
1707     case PRIMARY:
1708       description = "primary()";
1709       if( _primary   != NULL)  { value = _primary;     }
1710       break;
1711     case SECONDARY:
1712       description = "secondary()";
1713       if( _secondary != NULL ) { value = _secondary;   }
1714       break;
1715     case TERTIARY:
1716       description = "tertiary()";
1717       if( _tertiary  != NULL ) { value = _tertiary;    }
1718       break;
1719     default:
1720       assert( false, "ShouldNotReachHere();");
1721       break;
1722     }
1723   }
1724   if (value != NULL) {
1725     fprintf(fp, "(%s /*%s*/)", value, description);
1726   }
1727   return value != NULL;
1728 }
1729 
1730 void Opcode::dump() {
1731   output(stderr);
1732 }
1733 
1734 // Write info to output files
1735 void Opcode::output(FILE *fp) {
1736   if (_primary   != NULL) fprintf(fp,"Primary   opcode: %s\n", _primary);
1737   if (_secondary != NULL) fprintf(fp,"Secondary opcode: %s\n", _secondary);
1738   if (_tertiary  != NULL) fprintf(fp,"Tertiary  opcode: %s\n", _tertiary);
1739 }
1740 
1741 //------------------------------InsEncode--------------------------------------
1742 InsEncode::InsEncode() {
1743 }
1744 InsEncode::~InsEncode() {
1745 }
1746 
1747 // Add "encode class name" and its parameters
1748 NameAndList *InsEncode::add_encode(char *encoding) {
1749   assert( encoding != NULL, "Must provide name for encoding");
1750 
1751   // add_parameter(NameList::_signal);
1752   NameAndList *encode = new NameAndList(encoding);
1753   _encoding.addName((char*)encode);
1754 
1755   return encode;
1756 }
1757 
1758 // Access the list of encodings
1759 void InsEncode::reset() {
1760   _encoding.reset();
1761   // _parameter.reset();
1762 }
1763 const char* InsEncode::encode_class_iter() {
1764   NameAndList  *encode_class = (NameAndList*)_encoding.iter();
1765   return  ( encode_class != NULL ? encode_class->name() : NULL );
1766 }
1767 // Obtain parameter name from zero based index
1768 const char *InsEncode::rep_var_name(InstructForm &inst, uint param_no) {
1769   NameAndList *params = (NameAndList*)_encoding.current();
1770   assert( params != NULL, "Internal Error");
1771   const char *param = (*params)[param_no];
1772 
1773   // Remove '$' if parser placed it there.
1774   return ( param != NULL && *param == '$') ? (param+1) : param;
1775 }
1776 
1777 void InsEncode::dump() {
1778   output(stderr);
1779 }
1780 
1781 // Write info to output files
1782 void InsEncode::output(FILE *fp) {
1783   NameAndList *encoding  = NULL;
1784   const char  *parameter = NULL;
1785 
1786   fprintf(fp,"InsEncode: ");
1787   _encoding.reset();
1788 
1789   while ( (encoding = (NameAndList*)_encoding.iter()) != 0 ) {
1790     // Output the encoding being used
1791     fprintf(fp,"%s(", encoding->name() );
1792 
1793     // Output its parameter list, if any
1794     bool first_param = true;
1795     encoding->reset();
1796     while (  (parameter = encoding->iter()) != 0 ) {
1797       // Output the ',' between parameters
1798       if ( ! first_param )  fprintf(fp,", ");
1799       first_param = false;
1800       // Output the parameter
1801       fprintf(fp,"%s", parameter);
1802     } // done with parameters
1803     fprintf(fp,")  ");
1804   } // done with encodings
1805 
1806   fprintf(fp,"\n");
1807 }
1808 
1809 //------------------------------Effect-----------------------------------------
1810 static int effect_lookup(const char *name) {
1811   if(!strcmp(name, "USE")) return Component::USE;
1812   if(!strcmp(name, "DEF")) return Component::DEF;
1813   if(!strcmp(name, "USE_DEF")) return Component::USE_DEF;
1814   if(!strcmp(name, "KILL")) return Component::KILL;
1815   if(!strcmp(name, "USE_KILL")) return Component::USE_KILL;
1816   if(!strcmp(name, "TEMP")) return Component::TEMP;
1817   if(!strcmp(name, "INVALID")) return Component::INVALID;
1818   if(!strcmp(name, "CALL")) return Component::CALL;
1819   assert( false,"Invalid effect name specified\n");
1820   return Component::INVALID;
1821 }
1822 
1823 const char *Component::getUsedefName() {
1824   switch (_usedef) {
1825     case Component::INVALID:  return "INVALID";  break;
1826     case Component::USE:      return "USE";      break;
1827     case Component::USE_DEF:  return "USE_DEF";  break;
1828     case Component::USE_KILL: return "USE_KILL"; break;
1829     case Component::KILL:     return "KILL";     break;
1830     case Component::TEMP:     return "TEMP";     break;
1831     case Component::DEF:      return "DEF";      break;
1832     case Component::CALL:     return "CALL";     break;
1833     default: assert(false, "unknown effect");
1834   }
1835   return "Undefined Use/Def info";
1836 }
1837 
1838 Effect::Effect(const char *name) : _name(name), _use_def(effect_lookup(name)) {
1839   _ftype = Form::EFF;
1840 }
1841 
1842 Effect::~Effect() {
1843 }
1844 
1845 // Dynamic type check
1846 Effect *Effect::is_effect() const {
1847   return (Effect*)this;
1848 }
1849 
1850 
1851 // True if this component is equal to the parameter.
1852 bool Effect::is(int use_def_kill_enum) const {
1853   return (_use_def == use_def_kill_enum ? true : false);
1854 }
1855 // True if this component is used/def'd/kill'd as the parameter suggests.
1856 bool Effect::isa(int use_def_kill_enum) const {
1857   return (_use_def & use_def_kill_enum) == use_def_kill_enum;
1858 }
1859 
1860 void Effect::dump() {
1861   output(stderr);
1862 }
1863 
1864 void Effect::output(FILE *fp) {          // Write info to output files
1865   fprintf(fp,"Effect: %s\n", (_name?_name:""));
1866 }
1867 
1868 //------------------------------ExpandRule-------------------------------------
1869 ExpandRule::ExpandRule() : _expand_instrs(),
1870                            _newopconst(cmpstr, hashstr, Form::arena) {
1871   _ftype = Form::EXP;
1872 }
1873 
1874 ExpandRule::~ExpandRule() {                  // Destructor
1875 }
1876 
1877 void ExpandRule::add_instruction(NameAndList *instruction_name_and_operand_list) {
1878   _expand_instrs.addName((char*)instruction_name_and_operand_list);
1879 }
1880 
1881 void ExpandRule::reset_instructions() {
1882   _expand_instrs.reset();
1883 }
1884 
1885 NameAndList* ExpandRule::iter_instructions() {
1886   return (NameAndList*)_expand_instrs.iter();
1887 }
1888 
1889 
1890 void ExpandRule::dump() {
1891   output(stderr);
1892 }
1893 
1894 void ExpandRule::output(FILE *fp) {         // Write info to output files
1895   NameAndList *expand_instr = NULL;
1896   const char *opid = NULL;
1897 
1898   fprintf(fp,"\nExpand Rule:\n");
1899 
1900   // Iterate over the instructions 'node' expands into
1901   for(reset_instructions(); (expand_instr = iter_instructions()) != NULL; ) {
1902     fprintf(fp,"%s(", expand_instr->name());
1903 
1904     // iterate over the operand list
1905     for( expand_instr->reset(); (opid = expand_instr->iter()) != NULL; ) {
1906       fprintf(fp,"%s ", opid);
1907     }
1908     fprintf(fp,");\n");
1909   }
1910 }
1911 
1912 //------------------------------RewriteRule------------------------------------
1913 RewriteRule::RewriteRule(char* params, char* block)
1914   : _tempParams(params), _tempBlock(block) { };  // Constructor
1915 RewriteRule::~RewriteRule() {                 // Destructor
1916 }
1917 
1918 void RewriteRule::dump() {
1919   output(stderr);
1920 }
1921 
1922 void RewriteRule::output(FILE *fp) {         // Write info to output files
1923   fprintf(fp,"\nRewrite Rule:\n%s\n%s\n",
1924           (_tempParams?_tempParams:""),
1925           (_tempBlock?_tempBlock:""));
1926 }
1927 
1928 
1929 //==============================MachNodes======================================
1930 //------------------------------MachNodeForm-----------------------------------
1931 MachNodeForm::MachNodeForm(char *id)
1932   : _ident(id) {
1933 }
1934 
1935 MachNodeForm::~MachNodeForm() {
1936 }
1937 
1938 MachNodeForm *MachNodeForm::is_machnode() const {
1939   return (MachNodeForm*)this;
1940 }
1941 
1942 //==============================Operand Classes================================
1943 //------------------------------OpClassForm------------------------------------
1944 OpClassForm::OpClassForm(const char* id) : _ident(id) {
1945   _ftype = Form::OPCLASS;
1946 }
1947 
1948 OpClassForm::~OpClassForm() {
1949 }
1950 
1951 bool OpClassForm::ideal_only() const { return 0; }
1952 
1953 OpClassForm *OpClassForm::is_opclass() const {
1954   return (OpClassForm*)this;
1955 }
1956 
1957 Form::InterfaceType OpClassForm::interface_type(FormDict &globals) const {
1958   if( _oplst.count() == 0 ) return Form::no_interface;
1959 
1960   // Check that my operands have the same interface type
1961   Form::InterfaceType  interface;
1962   bool  first = true;
1963   NameList &op_list = (NameList &)_oplst;
1964   op_list.reset();
1965   const char *op_name;
1966   while( (op_name = op_list.iter()) != NULL ) {
1967     const Form  *form    = globals[op_name];
1968     OperandForm *operand = form->is_operand();
1969     assert( operand, "Entry in operand class that is not an operand");
1970     if( first ) {
1971       first     = false;
1972       interface = operand->interface_type(globals);
1973     } else {
1974       interface = (interface == operand->interface_type(globals) ? interface : Form::no_interface);
1975     }
1976   }
1977   return interface;
1978 }
1979 
1980 bool OpClassForm::stack_slots_only(FormDict &globals) const {
1981   if( _oplst.count() == 0 ) return false;  // how?
1982 
1983   NameList &op_list = (NameList &)_oplst;
1984   op_list.reset();
1985   const char *op_name;
1986   while( (op_name = op_list.iter()) != NULL ) {
1987     const Form  *form    = globals[op_name];
1988     OperandForm *operand = form->is_operand();
1989     assert( operand, "Entry in operand class that is not an operand");
1990     if( !operand->stack_slots_only(globals) )  return false;
1991   }
1992   return true;
1993 }
1994 
1995 
1996 void OpClassForm::dump() {
1997   output(stderr);
1998 }
1999 
2000 void OpClassForm::output(FILE *fp) {
2001   const char *name;
2002   fprintf(fp,"\nOperand Class: %s\n", (_ident?_ident:""));
2003   fprintf(fp,"\nCount = %d\n", _oplst.count());
2004   for(_oplst.reset(); (name = _oplst.iter()) != NULL;) {
2005     fprintf(fp,"%s, ",name);
2006   }
2007   fprintf(fp,"\n");
2008 }
2009 
2010 
2011 //==============================Operands=======================================
2012 //------------------------------OperandForm------------------------------------
2013 OperandForm::OperandForm(const char* id)
2014   : OpClassForm(id), _ideal_only(false),
2015     _localNames(cmpstr, hashstr, Form::arena) {
2016       _ftype = Form::OPER;
2017 
2018       _matrule   = NULL;
2019       _interface = NULL;
2020       _attribs   = NULL;
2021       _predicate = NULL;
2022       _constraint= NULL;
2023       _construct = NULL;
2024       _format    = NULL;
2025 }
2026 OperandForm::OperandForm(const char* id, bool ideal_only)
2027   : OpClassForm(id), _ideal_only(ideal_only),
2028     _localNames(cmpstr, hashstr, Form::arena) {
2029       _ftype = Form::OPER;
2030 
2031       _matrule   = NULL;
2032       _interface = NULL;
2033       _attribs   = NULL;
2034       _predicate = NULL;
2035       _constraint= NULL;
2036       _construct = NULL;
2037       _format    = NULL;
2038 }
2039 OperandForm::~OperandForm() {
2040 }
2041 
2042 
2043 OperandForm *OperandForm::is_operand() const {
2044   return (OperandForm*)this;
2045 }
2046 
2047 bool OperandForm::ideal_only() const {
2048   return _ideal_only;
2049 }
2050 
2051 Form::InterfaceType OperandForm::interface_type(FormDict &globals) const {
2052   if( _interface == NULL )  return Form::no_interface;
2053 
2054   return _interface->interface_type(globals);
2055 }
2056 
2057 
2058 bool OperandForm::stack_slots_only(FormDict &globals) const {
2059   if( _constraint == NULL )  return false;
2060   return _constraint->stack_slots_only();
2061 }
2062 
2063 
2064 // Access op_cost attribute or return NULL.
2065 const char* OperandForm::cost() {
2066   for (Attribute* cur = _attribs; cur != NULL; cur = (Attribute*)cur->_next) {
2067     if( strcmp(cur->_ident,AttributeForm::_op_cost) == 0 ) {
2068       return cur->_val;
2069     }
2070   }
2071   return NULL;
2072 }
2073 
2074 // Return the number of leaves below this complex operand
2075 uint OperandForm::num_leaves() const {
2076   if ( ! _matrule) return 0;
2077 
2078   int num_leaves = _matrule->_numleaves;
2079   return num_leaves;
2080 }
2081 
2082 // Return the number of constants contained within this complex operand
2083 uint OperandForm::num_consts(FormDict &globals) const {
2084   if ( ! _matrule) return 0;
2085 
2086   // This is a recursive invocation on all operands in the matchrule
2087   return _matrule->num_consts(globals);
2088 }
2089 
2090 // Return the number of constants in match rule with specified type
2091 uint OperandForm::num_consts(FormDict &globals, Form::DataType type) const {
2092   if ( ! _matrule) return 0;
2093 
2094   // This is a recursive invocation on all operands in the matchrule
2095   return _matrule->num_consts(globals, type);
2096 }
2097 
2098 // Return the number of pointer constants contained within this complex operand
2099 uint OperandForm::num_const_ptrs(FormDict &globals) const {
2100   if ( ! _matrule) return 0;
2101 
2102   // This is a recursive invocation on all operands in the matchrule
2103   return _matrule->num_const_ptrs(globals);
2104 }
2105 
2106 uint OperandForm::num_edges(FormDict &globals) const {
2107   uint edges  = 0;
2108   uint leaves = num_leaves();
2109   uint consts = num_consts(globals);
2110 
2111   // If we are matching a constant directly, there are no leaves.
2112   edges = ( leaves > consts ) ? leaves - consts : 0;
2113 
2114   // !!!!!
2115   // Special case operands that do not have a corresponding ideal node.
2116   if( (edges == 0) && (consts == 0) ) {
2117     if( constrained_reg_class() != NULL ) {
2118       edges = 1;
2119     } else {
2120       if( _matrule
2121           && (_matrule->_lChild == NULL) && (_matrule->_rChild == NULL) ) {
2122         const Form *form = globals[_matrule->_opType];
2123         OperandForm *oper = form ? form->is_operand() : NULL;
2124         if( oper ) {
2125           return oper->num_edges(globals);
2126         }
2127       }
2128     }
2129   }
2130 
2131   return edges;
2132 }
2133 
2134 
2135 // Check if this operand is usable for cisc-spilling
2136 bool  OperandForm::is_cisc_reg(FormDict &globals) const {
2137   const char *ideal = ideal_type(globals);
2138   bool is_cisc_reg = (ideal && (ideal_to_Reg_type(ideal) != none));
2139   return is_cisc_reg;
2140 }
2141 
2142 bool  OpClassForm::is_cisc_mem(FormDict &globals) const {
2143   Form::InterfaceType my_interface = interface_type(globals);
2144   return (my_interface == memory_interface);
2145 }
2146 
2147 
2148 // node matches ideal 'Bool'
2149 bool OperandForm::is_ideal_bool() const {
2150   if( _matrule == NULL ) return false;
2151 
2152   return _matrule->is_ideal_bool();
2153 }
2154 
2155 // Require user's name for an sRegX to be stackSlotX
2156 Form::DataType OperandForm::is_user_name_for_sReg() const {
2157   DataType data_type = none;
2158   if( _ident != NULL ) {
2159     if(      strcmp(_ident,"stackSlotI") == 0 ) data_type = Form::idealI;
2160     else if( strcmp(_ident,"stackSlotP") == 0 ) data_type = Form::idealP;
2161     else if( strcmp(_ident,"stackSlotD") == 0 ) data_type = Form::idealD;
2162     else if( strcmp(_ident,"stackSlotF") == 0 ) data_type = Form::idealF;
2163     else if( strcmp(_ident,"stackSlotL") == 0 ) data_type = Form::idealL;
2164   }
2165   assert((data_type == none) || (_matrule == NULL), "No match-rule for stackSlotX");
2166 
2167   return data_type;
2168 }
2169 
2170 
2171 // Return ideal type, if there is a single ideal type for this operand
2172 const char *OperandForm::ideal_type(FormDict &globals, RegisterForm *registers) const {
2173   const char *type = NULL;
2174   if (ideal_only()) type = _ident;
2175   else if( _matrule == NULL ) {
2176     // Check for condition code register
2177     const char *rc_name = constrained_reg_class();
2178     // !!!!!
2179     if (rc_name == NULL) return NULL;
2180     // !!!!! !!!!!
2181     // Check constraints on result's register class
2182     if( registers ) {
2183       RegClass *reg_class  = registers->getRegClass(rc_name);
2184       assert( reg_class != NULL, "Register class is not defined");
2185 
2186       // Check for ideal type of entries in register class, all are the same type
2187       reg_class->reset();
2188       RegDef *reg_def = reg_class->RegDef_iter();
2189       assert( reg_def != NULL, "No entries in register class");
2190       assert( reg_def->_idealtype != NULL, "Did not define ideal type for register");
2191       // Return substring that names the register's ideal type
2192       type = reg_def->_idealtype + 3;
2193       assert( *(reg_def->_idealtype + 0) == 'O', "Expect Op_ prefix");
2194       assert( *(reg_def->_idealtype + 1) == 'p', "Expect Op_ prefix");
2195       assert( *(reg_def->_idealtype + 2) == '_', "Expect Op_ prefix");
2196     }
2197   }
2198   else if( _matrule->_lChild == NULL && _matrule->_rChild == NULL ) {
2199     // This operand matches a single type, at the top level.
2200     // Check for ideal type
2201     type = _matrule->_opType;
2202     if( strcmp(type,"Bool") == 0 )
2203       return "Bool";
2204     // transitive lookup
2205     const Form *frm = globals[type];
2206     OperandForm *op = frm->is_operand();
2207     type = op->ideal_type(globals, registers);
2208   }
2209   return type;
2210 }
2211 
2212 
2213 // If there is a single ideal type for this interface field, return it.
2214 const char *OperandForm::interface_ideal_type(FormDict &globals,
2215                                               const char *field) const {
2216   const char  *ideal_type = NULL;
2217   const char  *value      = NULL;
2218 
2219   // Check if "field" is valid for this operand's interface
2220   if ( ! is_interface_field(field, value) )   return ideal_type;
2221 
2222   // !!!!! !!!!! !!!!!
2223   // If a valid field has a constant value, identify "ConI" or "ConP" or ...
2224 
2225   // Else, lookup type of field's replacement variable
2226 
2227   return ideal_type;
2228 }
2229 
2230 
2231 RegClass* OperandForm::get_RegClass() const {
2232   if (_interface && !_interface->is_RegInterface()) return NULL;
2233   return globalAD->get_registers()->getRegClass(constrained_reg_class());
2234 }
2235 
2236 
2237 bool OperandForm::is_bound_register() const {
2238   RegClass* reg_class = get_RegClass();
2239   if (reg_class == NULL) {
2240     return false;
2241   }
2242 
2243   const char* name = ideal_type(globalAD->globalNames());
2244   if (name == NULL) {
2245     return false;
2246   }
2247 
2248   uint size = 0;
2249   if (strcmp(name, "RegFlags") == 0) size = 1;
2250   if (strcmp(name, "RegI") == 0) size = 1;
2251   if (strcmp(name, "RegF") == 0) size = 1;
2252   if (strcmp(name, "RegD") == 0) size = 2;
2253   if (strcmp(name, "RegL") == 0) size = 2;
2254   if (strcmp(name, "RegN") == 0) size = 1;
2255   if (strcmp(name, "RegP") == 0) size = globalAD->get_preproc_def("_LP64") ? 2 : 1;
2256   if (size == 0) {
2257     return false;
2258   }
2259   return size == reg_class->size();
2260 }
2261 
2262 
2263 // Check if this is a valid field for this operand,
2264 // Return 'true' if valid, and set the value to the string the user provided.
2265 bool  OperandForm::is_interface_field(const char *field,
2266                                       const char * &value) const {
2267   return false;
2268 }
2269 
2270 
2271 // Return register class name if a constraint specifies the register class.
2272 const char *OperandForm::constrained_reg_class() const {
2273   const char *reg_class  = NULL;
2274   if ( _constraint ) {
2275     // !!!!!
2276     Constraint *constraint = _constraint;
2277     if ( strcmp(_constraint->_func,"ALLOC_IN_RC") == 0 ) {
2278       reg_class = _constraint->_arg;
2279     }
2280   }
2281 
2282   return reg_class;
2283 }
2284 
2285 
2286 // Return the register class associated with 'leaf'.
2287 const char *OperandForm::in_reg_class(uint leaf, FormDict &globals) {
2288   const char *reg_class = NULL; // "RegMask::Empty";
2289 
2290   if((_matrule == NULL) || (_matrule->is_chain_rule(globals))) {
2291     reg_class = constrained_reg_class();
2292     return reg_class;
2293   }
2294   const char *result   = NULL;
2295   const char *name     = NULL;
2296   const char *type     = NULL;
2297   // iterate through all base operands
2298   // until we reach the register that corresponds to "leaf"
2299   // This function is not looking for an ideal type.  It needs the first
2300   // level user type associated with the leaf.
2301   for(uint idx = 0;_matrule->base_operand(idx,globals,result,name,type);++idx) {
2302     const Form *form = (_localNames[name] ? _localNames[name] : globals[result]);
2303     OperandForm *oper = form ? form->is_operand() : NULL;
2304     if( oper ) {
2305       reg_class = oper->constrained_reg_class();
2306       if( reg_class ) {
2307         reg_class = reg_class;
2308       } else {
2309         // ShouldNotReachHere();
2310       }
2311     } else {
2312       // ShouldNotReachHere();
2313     }
2314 
2315     // Increment our target leaf position if current leaf is not a candidate.
2316     if( reg_class == NULL)    ++leaf;
2317     // Exit the loop with the value of reg_class when at the correct index
2318     if( idx == leaf )         break;
2319     // May iterate through all base operands if reg_class for 'leaf' is NULL
2320   }
2321   return reg_class;
2322 }
2323 
2324 
2325 // Recursive call to construct list of top-level operands.
2326 // Implementation does not modify state of internal structures
2327 void OperandForm::build_components() {
2328   if (_matrule)  _matrule->append_components(_localNames, _components);
2329 
2330   // Add parameters that "do not appear in match rule".
2331   const char *name;
2332   for (_parameters.reset(); (name = _parameters.iter()) != NULL;) {
2333     OpClassForm *opForm = _localNames[name]->is_opclass();
2334     assert(opForm != NULL, "sanity");
2335 
2336     if ( _components.operand_position(name) == -1 ) {
2337       _components.insert(name, opForm->_ident, Component::INVALID, false);
2338     }
2339   }
2340 
2341   return;
2342 }
2343 
2344 int OperandForm::operand_position(const char *name, int usedef) {
2345   return _components.operand_position(name, usedef, this);
2346 }
2347 
2348 
2349 // Return zero-based position in component list, only counting constants;
2350 // Return -1 if not in list.
2351 int OperandForm::constant_position(FormDict &globals, const Component *last) {
2352   // Iterate through components and count constants preceding 'constant'
2353   int position = 0;
2354   Component *comp;
2355   _components.reset();
2356   while( (comp = _components.iter()) != NULL  && (comp != last) ) {
2357     // Special case for operands that take a single user-defined operand
2358     // Skip the initial definition in the component list.
2359     if( strcmp(comp->_name,this->_ident) == 0 ) continue;
2360 
2361     const char *type = comp->_type;
2362     // Lookup operand form for replacement variable's type
2363     const Form *form = globals[type];
2364     assert( form != NULL, "Component's type not found");
2365     OperandForm *oper = form ? form->is_operand() : NULL;
2366     if( oper ) {
2367       if( oper->_matrule->is_base_constant(globals) != Form::none ) {
2368         ++position;
2369       }
2370     }
2371   }
2372 
2373   // Check for being passed a component that was not in the list
2374   if( comp != last )  position = -1;
2375 
2376   return position;
2377 }
2378 // Provide position of constant by "name"
2379 int OperandForm::constant_position(FormDict &globals, const char *name) {
2380   const Component *comp = _components.search(name);
2381   int idx = constant_position( globals, comp );
2382 
2383   return idx;
2384 }
2385 
2386 
2387 // Return zero-based position in component list, only counting constants;
2388 // Return -1 if not in list.
2389 int OperandForm::register_position(FormDict &globals, const char *reg_name) {
2390   // Iterate through components and count registers preceding 'last'
2391   uint  position = 0;
2392   Component *comp;
2393   _components.reset();
2394   while( (comp = _components.iter()) != NULL
2395          && (strcmp(comp->_name,reg_name) != 0) ) {
2396     // Special case for operands that take a single user-defined operand
2397     // Skip the initial definition in the component list.
2398     if( strcmp(comp->_name,this->_ident) == 0 ) continue;
2399 
2400     const char *type = comp->_type;
2401     // Lookup operand form for component's type
2402     const Form *form = globals[type];
2403     assert( form != NULL, "Component's type not found");
2404     OperandForm *oper = form ? form->is_operand() : NULL;
2405     if( oper ) {
2406       if( oper->_matrule->is_base_register(globals) ) {
2407         ++position;
2408       }
2409     }
2410   }
2411 
2412   return position;
2413 }
2414 
2415 
2416 const char *OperandForm::reduce_result()  const {
2417   return _ident;
2418 }
2419 // Return the name of the operand on the right hand side of the binary match
2420 // Return NULL if there is no right hand side
2421 const char *OperandForm::reduce_right(FormDict &globals)  const {
2422   return  ( _matrule ? _matrule->reduce_right(globals) : NULL );
2423 }
2424 
2425 // Similar for left
2426 const char *OperandForm::reduce_left(FormDict &globals)   const {
2427   return  ( _matrule ? _matrule->reduce_left(globals) : NULL );
2428 }
2429 
2430 
2431 // --------------------------- FILE *output_routines
2432 //
2433 // Output code for disp_is_oop, if true.
2434 void OperandForm::disp_is_oop(FILE *fp, FormDict &globals) {
2435   //  Check it is a memory interface with a non-user-constant disp field
2436   if ( this->_interface == NULL ) return;
2437   MemInterface *mem_interface = this->_interface->is_MemInterface();
2438   if ( mem_interface == NULL )    return;
2439   const char   *disp  = mem_interface->_disp;
2440   if ( *disp != '$' )             return;
2441 
2442   // Lookup replacement variable in operand's component list
2443   const char   *rep_var = disp + 1;
2444   const Component *comp = this->_components.search(rep_var);
2445   assert( comp != NULL, "Replacement variable not found in components");
2446   // Lookup operand form for replacement variable's type
2447   const char      *type = comp->_type;
2448   Form            *form = (Form*)globals[type];
2449   assert( form != NULL, "Replacement variable's type not found");
2450   OperandForm     *op   = form->is_operand();
2451   assert( op, "Memory Interface 'disp' can only emit an operand form");
2452   // Check if this is a ConP, which may require relocation
2453   if ( op->is_base_constant(globals) == Form::idealP ) {
2454     // Find the constant's index:  _c0, _c1, _c2, ... , _cN
2455     uint idx  = op->constant_position( globals, rep_var);
2456     fprintf(fp,"  virtual relocInfo::relocType disp_reloc() const {");
2457     fprintf(fp,  "  return _c%d->reloc();", idx);
2458     fprintf(fp, " }\n");
2459   }
2460 }
2461 
2462 // Generate code for internal and external format methods
2463 //
2464 // internal access to reg# node->_idx
2465 // access to subsumed constant _c0, _c1,
2466 void  OperandForm::int_format(FILE *fp, FormDict &globals, uint index) {
2467   Form::DataType dtype;
2468   if (_matrule && (_matrule->is_base_register(globals) ||
2469                    strcmp(ideal_type(globalAD->globalNames()), "RegFlags") == 0)) {
2470     // !!!!! !!!!!
2471     fprintf(fp,"  { char reg_str[128];\n");
2472     fprintf(fp,"    ra->dump_register(node,reg_str);\n");
2473     fprintf(fp,"    st->print(\"%cs\",reg_str);\n",'%');
2474     fprintf(fp,"  }\n");
2475   } else if (_matrule && (dtype = _matrule->is_base_constant(globals)) != Form::none) {
2476     format_constant( fp, index, dtype );
2477   } else if (ideal_to_sReg_type(_ident) != Form::none) {
2478     // Special format for Stack Slot Register
2479     fprintf(fp,"  { char reg_str[128];\n");
2480     fprintf(fp,"    ra->dump_register(node,reg_str);\n");
2481     fprintf(fp,"    st->print(\"%cs\",reg_str);\n",'%');
2482     fprintf(fp,"  }\n");
2483   } else {
2484     fprintf(fp,"  st->print(\"No format defined for %s\n\");\n", _ident);
2485     fflush(fp);
2486     fprintf(stderr,"No format defined for %s\n", _ident);
2487     dump();
2488     assert( false,"Internal error:\n  output_internal_operand() attempting to output other than a Register or Constant");
2489   }
2490 }
2491 
2492 // Similar to "int_format" but for cases where data is external to operand
2493 // external access to reg# node->in(idx)->_idx,
2494 void  OperandForm::ext_format(FILE *fp, FormDict &globals, uint index) {
2495   Form::DataType dtype;
2496   if (_matrule && (_matrule->is_base_register(globals) ||
2497                    strcmp(ideal_type(globalAD->globalNames()), "RegFlags") == 0)) {
2498     fprintf(fp,"  { char reg_str[128];\n");
2499     fprintf(fp,"    ra->dump_register(node->in(idx");
2500     if ( index != 0 ) fprintf(fp,              "+%d",index);
2501     fprintf(fp,                                      "),reg_str);\n");
2502     fprintf(fp,"    st->print(\"%cs\",reg_str);\n",'%');
2503     fprintf(fp,"  }\n");
2504   } else if (_matrule && (dtype = _matrule->is_base_constant(globals)) != Form::none) {
2505     format_constant( fp, index, dtype );
2506   } else if (ideal_to_sReg_type(_ident) != Form::none) {
2507     // Special format for Stack Slot Register
2508     fprintf(fp,"  { char reg_str[128];\n");
2509     fprintf(fp,"    ra->dump_register(node->in(idx");
2510     if ( index != 0 ) fprintf(fp,                  "+%d",index);
2511     fprintf(fp,                                       "),reg_str);\n");
2512     fprintf(fp,"    st->print(\"%cs\",reg_str);\n",'%');
2513     fprintf(fp,"  }\n");
2514   } else {
2515     fprintf(fp,"  st->print(\"No format defined for %s\n\");\n", _ident);
2516     assert( false,"Internal error:\n  output_external_operand() attempting to output other than a Register or Constant");
2517   }
2518 }
2519 
2520 void OperandForm::format_constant(FILE *fp, uint const_index, uint const_type) {
2521   switch(const_type) {
2522   case Form::idealI: fprintf(fp,"  st->print(\"#%%d\", _c%d);\n", const_index); break;
2523   case Form::idealP: fprintf(fp,"  if (_c%d) _c%d->dump_on(st);\n", const_index, const_index); break;
2524   case Form::idealNKlass:
2525   case Form::idealN: fprintf(fp,"  if (_c%d) _c%d->dump_on(st);\n", const_index, const_index); break;
2526   case Form::idealL: fprintf(fp,"  st->print(\"#\" INT64_FORMAT, (int64_t)_c%d);\n", const_index); break;
2527   case Form::idealF: fprintf(fp,"  st->print(\"#%%f\", _c%d);\n", const_index); break;
2528   case Form::idealD: fprintf(fp,"  st->print(\"#%%f\", _c%d);\n", const_index); break;
2529   default:
2530     assert( false, "ShouldNotReachHere()");
2531   }
2532 }
2533 
2534 // Return the operand form corresponding to the given index, else NULL.
2535 OperandForm *OperandForm::constant_operand(FormDict &globals,
2536                                            uint      index) {
2537   // !!!!!
2538   // Check behavior on complex operands
2539   uint n_consts = num_consts(globals);
2540   if( n_consts > 0 ) {
2541     uint i = 0;
2542     const char *type;
2543     Component  *comp;
2544     _components.reset();
2545     if ((comp = _components.iter()) == NULL) {
2546       assert(n_consts == 1, "Bad component list detected.\n");
2547       // Current operand is THE operand
2548       if ( index == 0 ) {
2549         return this;
2550       }
2551     } // end if NULL
2552     else {
2553       // Skip the first component, it can not be a DEF of a constant
2554       do {
2555         type = comp->base_type(globals);
2556         // Check that "type" is a 'ConI', 'ConP', ...
2557         if ( ideal_to_const_type(type) != Form::none ) {
2558           // When at correct component, get corresponding Operand
2559           if ( index == 0 ) {
2560             return globals[comp->_type]->is_operand();
2561           }
2562           // Decrement number of constants to go
2563           --index;
2564         }
2565       } while((comp = _components.iter()) != NULL);
2566     }
2567   }
2568 
2569   // Did not find a constant for this index.
2570   return NULL;
2571 }
2572 
2573 // If this operand has a single ideal type, return its type
2574 Form::DataType OperandForm::simple_type(FormDict &globals) const {
2575   const char *type_name = ideal_type(globals);
2576   Form::DataType type   = type_name ? ideal_to_const_type( type_name )
2577                                     : Form::none;
2578   return type;
2579 }
2580 
2581 Form::DataType OperandForm::is_base_constant(FormDict &globals) const {
2582   if ( _matrule == NULL )    return Form::none;
2583 
2584   return _matrule->is_base_constant(globals);
2585 }
2586 
2587 // "true" if this operand is a simple type that is swallowed
2588 bool  OperandForm::swallowed(FormDict &globals) const {
2589   Form::DataType type   = simple_type(globals);
2590   if( type != Form::none ) {
2591     return true;
2592   }
2593 
2594   return false;
2595 }
2596 
2597 // Output code to access the value of the index'th constant
2598 void OperandForm::access_constant(FILE *fp, FormDict &globals,
2599                                   uint const_index) {
2600   OperandForm *oper = constant_operand(globals, const_index);
2601   assert( oper, "Index exceeds number of constants in operand");
2602   Form::DataType dtype = oper->is_base_constant(globals);
2603 
2604   switch(dtype) {
2605   case idealI: fprintf(fp,"_c%d",           const_index); break;
2606   case idealP: fprintf(fp,"_c%d->get_con()",const_index); break;
2607   case idealL: fprintf(fp,"_c%d",           const_index); break;
2608   case idealF: fprintf(fp,"_c%d",           const_index); break;
2609   case idealD: fprintf(fp,"_c%d",           const_index); break;
2610   default:
2611     assert( false, "ShouldNotReachHere()");
2612   }
2613 }
2614 
2615 
2616 void OperandForm::dump() {
2617   output(stderr);
2618 }
2619 
2620 void OperandForm::output(FILE *fp) {
2621   fprintf(fp,"\nOperand: %s\n", (_ident?_ident:""));
2622   if (_matrule)    _matrule->dump();
2623   if (_interface)  _interface->dump();
2624   if (_attribs)    _attribs->dump();
2625   if (_predicate)  _predicate->dump();
2626   if (_constraint) _constraint->dump();
2627   if (_construct)  _construct->dump();
2628   if (_format)     _format->dump();
2629 }
2630 
2631 //------------------------------Constraint-------------------------------------
2632 Constraint::Constraint(const char *func, const char *arg)
2633   : _func(func), _arg(arg) {
2634 }
2635 Constraint::~Constraint() { /* not owner of char* */
2636 }
2637 
2638 bool Constraint::stack_slots_only() const {
2639   return strcmp(_func, "ALLOC_IN_RC") == 0
2640       && strcmp(_arg,  "stack_slots") == 0;
2641 }
2642 
2643 void Constraint::dump() {
2644   output(stderr);
2645 }
2646 
2647 void Constraint::output(FILE *fp) {           // Write info to output files
2648   assert((_func != NULL && _arg != NULL),"missing constraint function or arg");
2649   fprintf(fp,"Constraint: %s ( %s )\n", _func, _arg);
2650 }
2651 
2652 //------------------------------Predicate--------------------------------------
2653 Predicate::Predicate(char *pr)
2654   : _pred(pr) {
2655 }
2656 Predicate::~Predicate() {
2657 }
2658 
2659 void Predicate::dump() {
2660   output(stderr);
2661 }
2662 
2663 void Predicate::output(FILE *fp) {
2664   fprintf(fp,"Predicate");  // Write to output files
2665 }
2666 //------------------------------Interface--------------------------------------
2667 Interface::Interface(const char *name) : _name(name) {
2668 }
2669 Interface::~Interface() {
2670 }
2671 
2672 Form::InterfaceType Interface::interface_type(FormDict &globals) const {
2673   Interface *thsi = (Interface*)this;
2674   if ( thsi->is_RegInterface()   ) return Form::register_interface;
2675   if ( thsi->is_MemInterface()   ) return Form::memory_interface;
2676   if ( thsi->is_ConstInterface() ) return Form::constant_interface;
2677   if ( thsi->is_CondInterface()  ) return Form::conditional_interface;
2678 
2679   return Form::no_interface;
2680 }
2681 
2682 RegInterface   *Interface::is_RegInterface() {
2683   if ( strcmp(_name,"REG_INTER") != 0 )
2684     return NULL;
2685   return (RegInterface*)this;
2686 }
2687 MemInterface   *Interface::is_MemInterface() {
2688   if ( strcmp(_name,"MEMORY_INTER") != 0 )  return NULL;
2689   return (MemInterface*)this;
2690 }
2691 ConstInterface *Interface::is_ConstInterface() {
2692   if ( strcmp(_name,"CONST_INTER") != 0 )  return NULL;
2693   return (ConstInterface*)this;
2694 }
2695 CondInterface  *Interface::is_CondInterface() {
2696   if ( strcmp(_name,"COND_INTER") != 0 )  return NULL;
2697   return (CondInterface*)this;
2698 }
2699 
2700 
2701 void Interface::dump() {
2702   output(stderr);
2703 }
2704 
2705 // Write info to output files
2706 void Interface::output(FILE *fp) {
2707   fprintf(fp,"Interface: %s\n", (_name ? _name : "") );
2708 }
2709 
2710 //------------------------------RegInterface-----------------------------------
2711 RegInterface::RegInterface() : Interface("REG_INTER") {
2712 }
2713 RegInterface::~RegInterface() {
2714 }
2715 
2716 void RegInterface::dump() {
2717   output(stderr);
2718 }
2719 
2720 // Write info to output files
2721 void RegInterface::output(FILE *fp) {
2722   Interface::output(fp);
2723 }
2724 
2725 //------------------------------ConstInterface---------------------------------
2726 ConstInterface::ConstInterface() : Interface("CONST_INTER") {
2727 }
2728 ConstInterface::~ConstInterface() {
2729 }
2730 
2731 void ConstInterface::dump() {
2732   output(stderr);
2733 }
2734 
2735 // Write info to output files
2736 void ConstInterface::output(FILE *fp) {
2737   Interface::output(fp);
2738 }
2739 
2740 //------------------------------MemInterface-----------------------------------
2741 MemInterface::MemInterface(char *base, char *index, char *scale, char *disp)
2742   : Interface("MEMORY_INTER"), _base(base), _index(index), _scale(scale), _disp(disp) {
2743 }
2744 MemInterface::~MemInterface() {
2745   // not owner of any character arrays
2746 }
2747 
2748 void MemInterface::dump() {
2749   output(stderr);
2750 }
2751 
2752 // Write info to output files
2753 void MemInterface::output(FILE *fp) {
2754   Interface::output(fp);
2755   if ( _base  != NULL ) fprintf(fp,"  base  == %s\n", _base);
2756   if ( _index != NULL ) fprintf(fp,"  index == %s\n", _index);
2757   if ( _scale != NULL ) fprintf(fp,"  scale == %s\n", _scale);
2758   if ( _disp  != NULL ) fprintf(fp,"  disp  == %s\n", _disp);
2759   // fprintf(fp,"\n");
2760 }
2761 
2762 //------------------------------CondInterface----------------------------------
2763 CondInterface::CondInterface(const char* equal,         const char* equal_format,
2764                              const char* not_equal,     const char* not_equal_format,
2765                              const char* less,          const char* less_format,
2766                              const char* greater_equal, const char* greater_equal_format,
2767                              const char* less_equal,    const char* less_equal_format,
2768                              const char* greater,       const char* greater_format,
2769                              const char* overflow,      const char* overflow_format,
2770                              const char* no_overflow,   const char* no_overflow_format)
2771   : Interface("COND_INTER"),
2772     _equal(equal),                 _equal_format(equal_format),
2773     _not_equal(not_equal),         _not_equal_format(not_equal_format),
2774     _less(less),                   _less_format(less_format),
2775     _greater_equal(greater_equal), _greater_equal_format(greater_equal_format),
2776     _less_equal(less_equal),       _less_equal_format(less_equal_format),
2777     _greater(greater),             _greater_format(greater_format),
2778     _overflow(overflow),           _overflow_format(overflow_format),
2779     _no_overflow(no_overflow),     _no_overflow_format(no_overflow_format) {
2780 }
2781 CondInterface::~CondInterface() {
2782   // not owner of any character arrays
2783 }
2784 
2785 void CondInterface::dump() {
2786   output(stderr);
2787 }
2788 
2789 // Write info to output files
2790 void CondInterface::output(FILE *fp) {
2791   Interface::output(fp);
2792   if ( _equal  != NULL )     fprintf(fp," equal        == %s\n", _equal);
2793   if ( _not_equal  != NULL ) fprintf(fp," not_equal    == %s\n", _not_equal);
2794   if ( _less  != NULL )      fprintf(fp," less         == %s\n", _less);
2795   if ( _greater_equal  != NULL ) fprintf(fp," greater_equal    == %s\n", _greater_equal);
2796   if ( _less_equal  != NULL ) fprintf(fp," less_equal   == %s\n", _less_equal);
2797   if ( _greater  != NULL )    fprintf(fp," greater      == %s\n", _greater);
2798   if ( _overflow != NULL )    fprintf(fp," overflow     == %s\n", _overflow);
2799   if ( _no_overflow != NULL ) fprintf(fp," no_overflow  == %s\n", _no_overflow);
2800   // fprintf(fp,"\n");
2801 }
2802 
2803 //------------------------------ConstructRule----------------------------------
2804 ConstructRule::ConstructRule(char *cnstr)
2805   : _construct(cnstr) {
2806 }
2807 ConstructRule::~ConstructRule() {
2808 }
2809 
2810 void ConstructRule::dump() {
2811   output(stderr);
2812 }
2813 
2814 void ConstructRule::output(FILE *fp) {
2815   fprintf(fp,"\nConstruct Rule\n");  // Write to output files
2816 }
2817 
2818 
2819 //==============================Shared Forms===================================
2820 //------------------------------AttributeForm----------------------------------
2821 int         AttributeForm::_insId   = 0;           // start counter at 0
2822 int         AttributeForm::_opId    = 0;           // start counter at 0
2823 const char* AttributeForm::_ins_cost = "ins_cost"; // required name
2824 const char* AttributeForm::_op_cost  = "op_cost";  // required name
2825 
2826 AttributeForm::AttributeForm(char *attr, int type, char *attrdef)
2827   : Form(Form::ATTR), _attrname(attr), _atype(type), _attrdef(attrdef) {
2828     if (type==OP_ATTR) {
2829       id = ++_opId;
2830     }
2831     else if (type==INS_ATTR) {
2832       id = ++_insId;
2833     }
2834     else assert( false,"");
2835 }
2836 AttributeForm::~AttributeForm() {
2837 }
2838 
2839 // Dynamic type check
2840 AttributeForm *AttributeForm::is_attribute() const {
2841   return (AttributeForm*)this;
2842 }
2843 
2844 
2845 // inlined  // int  AttributeForm::type() { return id;}
2846 
2847 void AttributeForm::dump() {
2848   output(stderr);
2849 }
2850 
2851 void AttributeForm::output(FILE *fp) {
2852   if( _attrname && _attrdef ) {
2853     fprintf(fp,"\n// AttributeForm \nstatic const int %s = %s;\n",
2854             _attrname, _attrdef);
2855   }
2856   else {
2857     fprintf(fp,"\n// AttributeForm missing name %s or definition %s\n",
2858             (_attrname?_attrname:""), (_attrdef?_attrdef:"") );
2859   }
2860 }
2861 
2862 //------------------------------Component--------------------------------------
2863 Component::Component(const char *name, const char *type, int usedef)
2864   : _name(name), _type(type), _usedef(usedef) {
2865     _ftype = Form::COMP;
2866 }
2867 Component::~Component() {
2868 }
2869 
2870 // True if this component is equal to the parameter.
2871 bool Component::is(int use_def_kill_enum) const {
2872   return (_usedef == use_def_kill_enum ? true : false);
2873 }
2874 // True if this component is used/def'd/kill'd as the parameter suggests.
2875 bool Component::isa(int use_def_kill_enum) const {
2876   return (_usedef & use_def_kill_enum) == use_def_kill_enum;
2877 }
2878 
2879 // Extend this component with additional use/def/kill behavior
2880 int Component::promote_use_def_info(int new_use_def) {
2881   _usedef |= new_use_def;
2882 
2883   return _usedef;
2884 }
2885 
2886 // Check the base type of this component, if it has one
2887 const char *Component::base_type(FormDict &globals) {
2888   const Form *frm = globals[_type];
2889   if (frm == NULL) return NULL;
2890   OperandForm *op = frm->is_operand();
2891   if (op == NULL) return NULL;
2892   if (op->ideal_only()) return op->_ident;
2893   return (char *)op->ideal_type(globals);
2894 }
2895 
2896 void Component::dump() {
2897   output(stderr);
2898 }
2899 
2900 void Component::output(FILE *fp) {
2901   fprintf(fp,"Component:");  // Write to output files
2902   fprintf(fp, "  name = %s", _name);
2903   fprintf(fp, ", type = %s", _type);
2904   assert(_usedef != 0, "unknown effect");
2905   fprintf(fp, ", use/def = %s\n", getUsedefName());
2906 }
2907 
2908 
2909 //------------------------------ComponentList---------------------------------
2910 ComponentList::ComponentList() : NameList(), _matchcnt(0) {
2911 }
2912 ComponentList::~ComponentList() {
2913   // // This list may not own its elements if copied via assignment
2914   // Component *component;
2915   // for (reset(); (component = iter()) != NULL;) {
2916   //   delete component;
2917   // }
2918 }
2919 
2920 void   ComponentList::insert(Component *component, bool mflag) {
2921   NameList::addName((char *)component);
2922   if(mflag) _matchcnt++;
2923 }
2924 void   ComponentList::insert(const char *name, const char *opType, int usedef,
2925                              bool mflag) {
2926   Component * component = new Component(name, opType, usedef);
2927   insert(component, mflag);
2928 }
2929 Component *ComponentList::current() { return (Component*)NameList::current(); }
2930 Component *ComponentList::iter()    { return (Component*)NameList::iter(); }
2931 Component *ComponentList::match_iter() {
2932   if(_iter < _matchcnt) return (Component*)NameList::iter();
2933   return NULL;
2934 }
2935 Component *ComponentList::post_match_iter() {
2936   Component *comp = iter();
2937   // At end of list?
2938   if ( comp == NULL ) {
2939     return comp;
2940   }
2941   // In post-match components?
2942   if (_iter > match_count()-1) {
2943     return comp;
2944   }
2945 
2946   return post_match_iter();
2947 }
2948 
2949 void       ComponentList::reset()   { NameList::reset(); }
2950 int        ComponentList::count()   { return NameList::count(); }
2951 
2952 Component *ComponentList::operator[](int position) {
2953   // Shortcut complete iteration if there are not enough entries
2954   if (position >= count()) return NULL;
2955 
2956   int        index     = 0;
2957   Component *component = NULL;
2958   for (reset(); (component = iter()) != NULL;) {
2959     if (index == position) {
2960       return component;
2961     }
2962     ++index;
2963   }
2964 
2965   return NULL;
2966 }
2967 
2968 const Component *ComponentList::search(const char *name) {
2969   PreserveIter pi(this);
2970   reset();
2971   for( Component *comp = NULL; ((comp = iter()) != NULL); ) {
2972     if( strcmp(comp->_name,name) == 0 ) return comp;
2973   }
2974 
2975   return NULL;
2976 }
2977 
2978 // Return number of USEs + number of DEFs
2979 // When there are no components, or the first component is a USE,
2980 // then we add '1' to hold a space for the 'result' operand.
2981 int ComponentList::num_operands() {
2982   PreserveIter pi(this);
2983   uint       count = 1;           // result operand
2984   uint       position = 0;
2985 
2986   Component *component  = NULL;
2987   for( reset(); (component = iter()) != NULL; ++position ) {
2988     if( component->isa(Component::USE) ||
2989         ( position == 0 && (! component->isa(Component::DEF))) ) {
2990       ++count;
2991     }
2992   }
2993 
2994   return count;
2995 }
2996 
2997 // Return zero-based position of operand 'name' in list;  -1 if not in list.
2998 // if parameter 'usedef' is ::USE, it will match USE, USE_DEF, ...
2999 int ComponentList::operand_position(const char *name, int usedef, Form *fm) {
3000   PreserveIter pi(this);
3001   int position = 0;
3002   int num_opnds = num_operands();
3003   Component *component;
3004   Component* preceding_non_use = NULL;
3005   Component* first_def = NULL;
3006   for (reset(); (component = iter()) != NULL; ++position) {
3007     // When the first component is not a DEF,
3008     // leave space for the result operand!
3009     if ( position==0 && (! component->isa(Component::DEF)) ) {
3010       ++position;
3011       ++num_opnds;
3012     }
3013     if (strcmp(name, component->_name)==0 && (component->isa(usedef))) {
3014       // When the first entry in the component list is a DEF and a USE
3015       // Treat them as being separate, a DEF first, then a USE
3016       if( position==0
3017           && usedef==Component::USE && component->isa(Component::DEF) ) {
3018         assert(position+1 < num_opnds, "advertised index in bounds");
3019         return position+1;
3020       } else {
3021         if( preceding_non_use && strcmp(component->_name, preceding_non_use->_name) ) {
3022           fprintf(stderr, "the name '%s(%s)' should not precede the name '%s(%s)'",
3023                   preceding_non_use->_name, preceding_non_use->getUsedefName(),
3024                   name, component->getUsedefName());
3025           if (fm && fm->is_instruction()) fprintf(stderr,  "in form '%s'", fm->is_instruction()->_ident);
3026           if (fm && fm->is_operand()) fprintf(stderr,  "in form '%s'", fm->is_operand()->_ident);
3027           fprintf(stderr,  "\n");
3028         }
3029         if( position >= num_opnds ) {
3030           fprintf(stderr, "the name '%s' is too late in its name list", name);
3031           if (fm && fm->is_instruction()) fprintf(stderr,  "in form '%s'", fm->is_instruction()->_ident);
3032           if (fm && fm->is_operand()) fprintf(stderr,  "in form '%s'", fm->is_operand()->_ident);
3033           fprintf(stderr,  "\n");
3034         }
3035         assert(position < num_opnds, "advertised index in bounds");
3036         return position;
3037       }
3038     }
3039     if( component->isa(Component::DEF)
3040         && component->isa(Component::USE) ) {
3041       ++position;
3042       if( position != 1 )  --position;   // only use two slots for the 1st USE_DEF
3043     }
3044     if( component->isa(Component::DEF) && !first_def ) {
3045       first_def = component;
3046     }
3047     if( !component->isa(Component::USE) && component != first_def ) {
3048       preceding_non_use = component;
3049     } else if( preceding_non_use && !strcmp(component->_name, preceding_non_use->_name) ) {
3050       preceding_non_use = NULL;
3051     }
3052   }
3053   return Not_in_list;
3054 }
3055 
3056 // Find position for this name, regardless of use/def information
3057 int ComponentList::operand_position(const char *name) {
3058   PreserveIter pi(this);
3059   int position = 0;
3060   Component *component;
3061   for (reset(); (component = iter()) != NULL; ++position) {
3062     // When the first component is not a DEF,
3063     // leave space for the result operand!
3064     if ( position==0 && (! component->isa(Component::DEF)) ) {
3065       ++position;
3066     }
3067     if (strcmp(name, component->_name)==0) {
3068       return position;
3069     }
3070     if( component->isa(Component::DEF)
3071         && component->isa(Component::USE) ) {
3072       ++position;
3073       if( position != 1 )  --position;   // only use two slots for the 1st USE_DEF
3074     }
3075   }
3076   return Not_in_list;
3077 }
3078 
3079 int ComponentList::operand_position_format(const char *name, Form *fm) {
3080   PreserveIter pi(this);
3081   int  first_position = operand_position(name);
3082   int  use_position   = operand_position(name, Component::USE, fm);
3083 
3084   return ((first_position < use_position) ? use_position : first_position);
3085 }
3086 
3087 int ComponentList::label_position() {
3088   PreserveIter pi(this);
3089   int position = 0;
3090   reset();
3091   for( Component *comp; (comp = iter()) != NULL; ++position) {
3092     // When the first component is not a DEF,
3093     // leave space for the result operand!
3094     if ( position==0 && (! comp->isa(Component::DEF)) ) {
3095       ++position;
3096     }
3097     if (strcmp(comp->_type, "label")==0) {
3098       return position;
3099     }
3100     if( comp->isa(Component::DEF)
3101         && comp->isa(Component::USE) ) {
3102       ++position;
3103       if( position != 1 )  --position;   // only use two slots for the 1st USE_DEF
3104     }
3105   }
3106 
3107   return -1;
3108 }
3109 
3110 int ComponentList::method_position() {
3111   PreserveIter pi(this);
3112   int position = 0;
3113   reset();
3114   for( Component *comp; (comp = iter()) != NULL; ++position) {
3115     // When the first component is not a DEF,
3116     // leave space for the result operand!
3117     if ( position==0 && (! comp->isa(Component::DEF)) ) {
3118       ++position;
3119     }
3120     if (strcmp(comp->_type, "method")==0) {
3121       return position;
3122     }
3123     if( comp->isa(Component::DEF)
3124         && comp->isa(Component::USE) ) {
3125       ++position;
3126       if( position != 1 )  --position;   // only use two slots for the 1st USE_DEF
3127     }
3128   }
3129 
3130   return -1;
3131 }
3132 
3133 void ComponentList::dump() { output(stderr); }
3134 
3135 void ComponentList::output(FILE *fp) {
3136   PreserveIter pi(this);
3137   fprintf(fp, "\n");
3138   Component *component;
3139   for (reset(); (component = iter()) != NULL;) {
3140     component->output(fp);
3141   }
3142   fprintf(fp, "\n");
3143 }
3144 
3145 //------------------------------MatchNode--------------------------------------
3146 MatchNode::MatchNode(ArchDesc &ad, const char *result, const char *mexpr,
3147                      const char *opType, MatchNode *lChild, MatchNode *rChild)
3148   : _AD(ad), _result(result), _name(mexpr), _opType(opType),
3149     _lChild(lChild), _rChild(rChild), _internalop(0), _numleaves(0),
3150     _commutative_id(0) {
3151   _numleaves = (lChild ? lChild->_numleaves : 0)
3152                + (rChild ? rChild->_numleaves : 0);
3153 }
3154 
3155 MatchNode::MatchNode(ArchDesc &ad, MatchNode& mnode)
3156   : _AD(ad), _result(mnode._result), _name(mnode._name),
3157     _opType(mnode._opType), _lChild(mnode._lChild), _rChild(mnode._rChild),
3158     _internalop(0), _numleaves(mnode._numleaves),
3159     _commutative_id(mnode._commutative_id) {
3160 }
3161 
3162 MatchNode::MatchNode(ArchDesc &ad, MatchNode& mnode, int clone)
3163   : _AD(ad), _result(mnode._result), _name(mnode._name),
3164     _opType(mnode._opType),
3165     _internalop(0), _numleaves(mnode._numleaves),
3166     _commutative_id(mnode._commutative_id) {
3167   if (mnode._lChild) {
3168     _lChild = new MatchNode(ad, *mnode._lChild, clone);
3169   } else {
3170     _lChild = NULL;
3171   }
3172   if (mnode._rChild) {
3173     _rChild = new MatchNode(ad, *mnode._rChild, clone);
3174   } else {
3175     _rChild = NULL;
3176   }
3177 }
3178 
3179 MatchNode::~MatchNode() {
3180   // // This node may not own its children if copied via assignment
3181   // if( _lChild ) delete _lChild;
3182   // if( _rChild ) delete _rChild;
3183 }
3184 
3185 bool  MatchNode::find_type(const char *type, int &position) const {
3186   if ( (_lChild != NULL) && (_lChild->find_type(type, position)) ) return true;
3187   if ( (_rChild != NULL) && (_rChild->find_type(type, position)) ) return true;
3188 
3189   if (strcmp(type,_opType)==0)  {
3190     return true;
3191   } else {
3192     ++position;
3193   }
3194   return false;
3195 }
3196 
3197 // Recursive call collecting info on top-level operands, not transitive.
3198 // Implementation does not modify state of internal structures.
3199 void MatchNode::append_components(FormDict& locals, ComponentList& components,
3200                                   bool def_flag) const {
3201   int usedef = def_flag ? Component::DEF : Component::USE;
3202   FormDict &globals = _AD.globalNames();
3203 
3204   assert (_name != NULL, "MatchNode::build_components encountered empty node\n");
3205   // Base case
3206   if (_lChild==NULL && _rChild==NULL) {
3207     // If _opType is not an operation, do not build a component for it #####
3208     const Form *f = globals[_opType];
3209     if( f != NULL ) {
3210       // Add non-ideals that are operands, operand-classes,
3211       if( ! f->ideal_only()
3212           && (f->is_opclass() || f->is_operand()) ) {
3213         components.insert(_name, _opType, usedef, true);
3214       }
3215     }
3216     return;
3217   }
3218   // Promote results of "Set" to DEF
3219   bool tmpdef_flag = (!strcmp(_opType, "Set")) ? true : false;
3220   if (_lChild) _lChild->append_components(locals, components, tmpdef_flag);
3221   tmpdef_flag = false;   // only applies to component immediately following 'Set'
3222   if (_rChild) _rChild->append_components(locals, components, tmpdef_flag);
3223 }
3224 
3225 // Find the n'th base-operand in the match node,
3226 // recursively investigates match rules of user-defined operands.
3227 //
3228 // Implementation does not modify state of internal structures since they
3229 // can be shared.
3230 bool MatchNode::base_operand(uint &position, FormDict &globals,
3231                              const char * &result, const char * &name,
3232                              const char * &opType) const {
3233   assert (_name != NULL, "MatchNode::base_operand encountered empty node\n");
3234   // Base case
3235   if (_lChild==NULL && _rChild==NULL) {
3236     // Check for special case: "Universe", "label"
3237     if (strcmp(_opType,"Universe") == 0 || strcmp(_opType,"label")==0 ) {
3238       if (position == 0) {
3239         result = _result;
3240         name   = _name;
3241         opType = _opType;
3242         return 1;
3243       } else {
3244         -- position;
3245         return 0;
3246       }
3247     }
3248 
3249     const Form *form = globals[_opType];
3250     MatchNode *matchNode = NULL;
3251     // Check for user-defined type
3252     if (form) {
3253       // User operand or instruction?
3254       OperandForm  *opForm = form->is_operand();
3255       InstructForm *inForm = form->is_instruction();
3256       if ( opForm ) {
3257         matchNode = (MatchNode*)opForm->_matrule;
3258       } else if ( inForm ) {
3259         matchNode = (MatchNode*)inForm->_matrule;
3260       }
3261     }
3262     // if this is user-defined, recurse on match rule
3263     // User-defined operand and instruction forms have a match-rule.
3264     if (matchNode) {
3265       return (matchNode->base_operand(position,globals,result,name,opType));
3266     } else {
3267       // Either not a form, or a system-defined form (no match rule).
3268       if (position==0) {
3269         result = _result;
3270         name   = _name;
3271         opType = _opType;
3272         return 1;
3273       } else {
3274         --position;
3275         return 0;
3276       }
3277     }
3278 
3279   } else {
3280     // Examine the left child and right child as well
3281     if (_lChild) {
3282       if (_lChild->base_operand(position, globals, result, name, opType))
3283         return 1;
3284     }
3285 
3286     if (_rChild) {
3287       if (_rChild->base_operand(position, globals, result, name, opType))
3288         return 1;
3289     }
3290   }
3291 
3292   return 0;
3293 }
3294 
3295 // Recursive call on all operands' match rules in my match rule.
3296 uint  MatchNode::num_consts(FormDict &globals) const {
3297   uint        index      = 0;
3298   uint        num_consts = 0;
3299   const char *result;
3300   const char *name;
3301   const char *opType;
3302 
3303   for (uint position = index;
3304        base_operand(position,globals,result,name,opType); position = index) {
3305     ++index;
3306     if( ideal_to_const_type(opType) )        num_consts++;
3307   }
3308 
3309   return num_consts;
3310 }
3311 
3312 // Recursive call on all operands' match rules in my match rule.
3313 // Constants in match rule subtree with specified type
3314 uint  MatchNode::num_consts(FormDict &globals, Form::DataType type) const {
3315   uint        index      = 0;
3316   uint        num_consts = 0;
3317   const char *result;
3318   const char *name;
3319   const char *opType;
3320 
3321   for (uint position = index;
3322        base_operand(position,globals,result,name,opType); position = index) {
3323     ++index;
3324     if( ideal_to_const_type(opType) == type ) num_consts++;
3325   }
3326 
3327   return num_consts;
3328 }
3329 
3330 // Recursive call on all operands' match rules in my match rule.
3331 uint  MatchNode::num_const_ptrs(FormDict &globals) const {
3332   return  num_consts( globals, Form::idealP );
3333 }
3334 
3335 bool  MatchNode::sets_result() const {
3336   return   ( (strcmp(_name,"Set") == 0) ? true : false );
3337 }
3338 
3339 const char *MatchNode::reduce_right(FormDict &globals) const {
3340   // If there is no right reduction, return NULL.
3341   const char      *rightStr    = NULL;
3342 
3343   // If we are a "Set", start from the right child.
3344   const MatchNode *const mnode = sets_result() ?
3345     (const MatchNode *)this->_rChild :
3346     (const MatchNode *)this;
3347 
3348   // If our right child exists, it is the right reduction
3349   if ( mnode->_rChild ) {
3350     rightStr = mnode->_rChild->_internalop ? mnode->_rChild->_internalop
3351       : mnode->_rChild->_opType;
3352   }
3353   // Else, May be simple chain rule: (Set dst operand_form), rightStr=NULL;
3354   return rightStr;
3355 }
3356 
3357 const char *MatchNode::reduce_left(FormDict &globals) const {
3358   // If there is no left reduction, return NULL.
3359   const char  *leftStr  = NULL;
3360 
3361   // If we are a "Set", start from the right child.
3362   const MatchNode *const mnode = sets_result() ?
3363     (const MatchNode *)this->_rChild :
3364     (const MatchNode *)this;
3365 
3366   // If our left child exists, it is the left reduction
3367   if ( mnode->_lChild ) {
3368     leftStr = mnode->_lChild->_internalop ? mnode->_lChild->_internalop
3369       : mnode->_lChild->_opType;
3370   } else {
3371     // May be simple chain rule: (Set dst operand_form_source)
3372     if ( sets_result() ) {
3373       OperandForm *oper = globals[mnode->_opType]->is_operand();
3374       if( oper ) {
3375         leftStr = mnode->_opType;
3376       }
3377     }
3378   }
3379   return leftStr;
3380 }
3381 
3382 //------------------------------count_instr_names------------------------------
3383 // Count occurrences of operands names in the leaves of the instruction
3384 // match rule.
3385 void MatchNode::count_instr_names( Dict &names ) {
3386   if( !this ) return;
3387   if( _lChild ) _lChild->count_instr_names(names);
3388   if( _rChild ) _rChild->count_instr_names(names);
3389   if( !_lChild && !_rChild ) {
3390     uintptr_t cnt = (uintptr_t)names[_name];
3391     cnt++;                      // One more name found
3392     names.Insert(_name,(void*)cnt);
3393   }
3394 }
3395 
3396 //------------------------------build_instr_pred-------------------------------
3397 // Build a path to 'name' in buf.  Actually only build if cnt is zero, so we
3398 // can skip some leading instances of 'name'.
3399 int MatchNode::build_instr_pred( char *buf, const char *name, int cnt ) {
3400   if( _lChild ) {
3401     if( !cnt ) strcpy( buf, "_kids[0]->" );
3402     cnt = _lChild->build_instr_pred( buf+strlen(buf), name, cnt );
3403     if( cnt < 0 ) return cnt;   // Found it, all done
3404   }
3405   if( _rChild ) {
3406     if( !cnt ) strcpy( buf, "_kids[1]->" );
3407     cnt = _rChild->build_instr_pred( buf+strlen(buf), name, cnt );
3408     if( cnt < 0 ) return cnt;   // Found it, all done
3409   }
3410   if( !_lChild && !_rChild ) {  // Found a leaf
3411     // Wrong name?  Give up...
3412     if( strcmp(name,_name) ) return cnt;
3413     if( !cnt ) strcpy(buf,"_leaf");
3414     return cnt-1;
3415   }
3416   return cnt;
3417 }
3418 
3419 
3420 //------------------------------build_internalop-------------------------------
3421 // Build string representation of subtree
3422 void MatchNode::build_internalop( ) {
3423   char *iop, *subtree;
3424   const char *lstr, *rstr;
3425   // Build string representation of subtree
3426   // Operation lchildType rchildType
3427   int len = (int)strlen(_opType) + 4;
3428   lstr = (_lChild) ? ((_lChild->_internalop) ?
3429                        _lChild->_internalop : _lChild->_opType) : "";
3430   rstr = (_rChild) ? ((_rChild->_internalop) ?
3431                        _rChild->_internalop : _rChild->_opType) : "";
3432   len += (int)strlen(lstr) + (int)strlen(rstr);
3433   subtree = (char *)malloc(len);
3434   sprintf(subtree,"_%s_%s_%s", _opType, lstr, rstr);
3435   // Hash the subtree string in _internalOps; if a name exists, use it
3436   iop = (char *)_AD._internalOps[subtree];
3437   // Else create a unique name, and add it to the hash table
3438   if (iop == NULL) {
3439     iop = subtree;
3440     _AD._internalOps.Insert(subtree, iop);
3441     _AD._internalOpNames.addName(iop);
3442     _AD._internalMatch.Insert(iop, this);
3443   }
3444   // Add the internal operand name to the MatchNode
3445   _internalop = iop;
3446   _result = iop;
3447 }
3448 
3449 
3450 void MatchNode::dump() {
3451   output(stderr);
3452 }
3453 
3454 void MatchNode::output(FILE *fp) {
3455   if (_lChild==0 && _rChild==0) {
3456     fprintf(fp," %s",_name);    // operand
3457   }
3458   else {
3459     fprintf(fp," (%s ",_name);  // " (opcodeName "
3460     if(_lChild) _lChild->output(fp); //               left operand
3461     if(_rChild) _rChild->output(fp); //                    right operand
3462     fprintf(fp,")");                 //                                 ")"
3463   }
3464 }
3465 
3466 int MatchNode::needs_ideal_memory_edge(FormDict &globals) const {
3467   static const char *needs_ideal_memory_list[] = {
3468     "StoreI","StoreL","StoreP","StoreN","StoreNKlass","StoreD","StoreF" ,
3469     "StoreB","StoreC","Store" ,"StoreFP",
3470     "LoadI", "LoadL", "LoadP" ,"LoadN", "LoadD" ,"LoadF"  ,
3471     "LoadB" , "LoadUB", "LoadUS" ,"LoadS" ,"Load" ,
3472     "StoreVector", "LoadVector",
3473     "LoadRange", "LoadKlass", "LoadNKlass", "LoadL_unaligned", "LoadD_unaligned",
3474     "LoadPLocked",
3475     "StorePConditional", "StoreIConditional", "StoreLConditional",
3476     "CompareAndSwapI", "CompareAndSwapL", "CompareAndSwapP", "CompareAndSwapN",
3477     "StoreCM",
3478     "ClearArray",
3479     "GetAndAddI", "GetAndSetI", "GetAndSetP",
3480     "GetAndAddL", "GetAndSetL", "GetAndSetN",
3481     "ShenandoahReadBarrier",
3482   };
3483   int cnt = sizeof(needs_ideal_memory_list)/sizeof(char*);
3484   if( strcmp(_opType,"PrefetchRead")==0 ||
3485       strcmp(_opType,"PrefetchWrite")==0 ||
3486       strcmp(_opType,"PrefetchAllocation")==0 )
3487     return 1;
3488   if( _lChild ) {
3489     const char *opType = _lChild->_opType;
3490     for( int i=0; i<cnt; i++ )
3491       if( strcmp(opType,needs_ideal_memory_list[i]) == 0 )
3492         return 1;
3493     if( _lChild->needs_ideal_memory_edge(globals) )
3494       return 1;
3495   }
3496   if( _rChild ) {
3497     const char *opType = _rChild->_opType;
3498     for( int i=0; i<cnt; i++ )
3499       if( strcmp(opType,needs_ideal_memory_list[i]) == 0 )
3500         return 1;
3501     if( _rChild->needs_ideal_memory_edge(globals) )
3502       return 1;
3503   }
3504 
3505   return 0;
3506 }
3507 
3508 // TRUE if defines a derived oop, and so needs a base oop edge present
3509 // post-matching.
3510 int MatchNode::needs_base_oop_edge() const {
3511   if( !strcmp(_opType,"AddP") ) return 1;
3512   if( strcmp(_opType,"Set") ) return 0;
3513   return !strcmp(_rChild->_opType,"AddP");
3514 }
3515 
3516 int InstructForm::needs_base_oop_edge(FormDict &globals) const {
3517   if( is_simple_chain_rule(globals) ) {
3518     const char *src = _matrule->_rChild->_opType;
3519     OperandForm *src_op = globals[src]->is_operand();
3520     assert( src_op, "Not operand class of chain rule" );
3521     return src_op->_matrule ? src_op->_matrule->needs_base_oop_edge() : 0;
3522   }                             // Else check instruction
3523 
3524   return _matrule ? _matrule->needs_base_oop_edge() : 0;
3525 }
3526 
3527 
3528 //-------------------------cisc spilling methods-------------------------------
3529 // helper routines and methods for detecting cisc-spilling instructions
3530 //-------------------------cisc_spill_merge------------------------------------
3531 int MatchNode::cisc_spill_merge(int left_spillable, int right_spillable) {
3532   int cisc_spillable  = Maybe_cisc_spillable;
3533 
3534   // Combine results of left and right checks
3535   if( (left_spillable == Maybe_cisc_spillable) && (right_spillable == Maybe_cisc_spillable) ) {
3536     // neither side is spillable, nor prevents cisc spilling
3537     cisc_spillable = Maybe_cisc_spillable;
3538   }
3539   else if( (left_spillable == Maybe_cisc_spillable) && (right_spillable > Maybe_cisc_spillable) ) {
3540     // right side is spillable
3541     cisc_spillable = right_spillable;
3542   }
3543   else if( (right_spillable == Maybe_cisc_spillable) && (left_spillable > Maybe_cisc_spillable) ) {
3544     // left side is spillable
3545     cisc_spillable = left_spillable;
3546   }
3547   else if( (left_spillable == Not_cisc_spillable) || (right_spillable == Not_cisc_spillable) ) {
3548     // left or right prevents cisc spilling this instruction
3549     cisc_spillable = Not_cisc_spillable;
3550   }
3551   else {
3552     // Only allow one to spill
3553     cisc_spillable = Not_cisc_spillable;
3554   }
3555 
3556   return cisc_spillable;
3557 }
3558 
3559 //-------------------------root_ops_match--------------------------------------
3560 bool static root_ops_match(FormDict &globals, const char *op1, const char *op2) {
3561   // Base Case: check that the current operands/operations match
3562   assert( op1, "Must have op's name");
3563   assert( op2, "Must have op's name");
3564   const Form *form1 = globals[op1];
3565   const Form *form2 = globals[op2];
3566 
3567   return (form1 == form2);
3568 }
3569 
3570 //-------------------------cisc_spill_match_node-------------------------------
3571 // Recursively check two MatchRules for legal conversion via cisc-spilling
3572 int MatchNode::cisc_spill_match(FormDict& globals, RegisterForm* registers, MatchNode* mRule2, const char* &operand, const char* &reg_type) {
3573   int cisc_spillable  = Maybe_cisc_spillable;
3574   int left_spillable  = Maybe_cisc_spillable;
3575   int right_spillable = Maybe_cisc_spillable;
3576 
3577   // Check that each has same number of operands at this level
3578   if( (_lChild && !(mRule2->_lChild)) || (_rChild && !(mRule2->_rChild)) )
3579     return Not_cisc_spillable;
3580 
3581   // Base Case: check that the current operands/operations match
3582   // or are CISC spillable
3583   assert( _opType, "Must have _opType");
3584   assert( mRule2->_opType, "Must have _opType");
3585   const Form *form  = globals[_opType];
3586   const Form *form2 = globals[mRule2->_opType];
3587   if( form == form2 ) {
3588     cisc_spillable = Maybe_cisc_spillable;
3589   } else {
3590     const InstructForm *form2_inst = form2 ? form2->is_instruction() : NULL;
3591     const char *name_left  = mRule2->_lChild ? mRule2->_lChild->_opType : NULL;
3592     const char *name_right = mRule2->_rChild ? mRule2->_rChild->_opType : NULL;
3593     DataType data_type = Form::none;
3594     if (form->is_operand()) {
3595       // Make sure the loadX matches the type of the reg
3596       data_type = form->ideal_to_Reg_type(form->is_operand()->ideal_type(globals));
3597     }
3598     // Detect reg vs (loadX memory)
3599     if( form->is_cisc_reg(globals)
3600         && form2_inst
3601         && data_type != Form::none
3602         && (is_load_from_memory(mRule2->_opType) == data_type) // reg vs. (load memory)
3603         && (name_left != NULL)       // NOT (load)
3604         && (name_right == NULL) ) {  // NOT (load memory foo)
3605       const Form *form2_left = name_left ? globals[name_left] : NULL;
3606       if( form2_left && form2_left->is_cisc_mem(globals) ) {
3607         cisc_spillable = Is_cisc_spillable;
3608         operand        = _name;
3609         reg_type       = _result;
3610         return Is_cisc_spillable;
3611       } else {
3612         cisc_spillable = Not_cisc_spillable;
3613       }
3614     }
3615     // Detect reg vs memory
3616     else if( form->is_cisc_reg(globals) && form2->is_cisc_mem(globals) ) {
3617       cisc_spillable = Is_cisc_spillable;
3618       operand        = _name;
3619       reg_type       = _result;
3620       return Is_cisc_spillable;
3621     } else {
3622       cisc_spillable = Not_cisc_spillable;
3623     }
3624   }
3625 
3626   // If cisc is still possible, check rest of tree
3627   if( cisc_spillable == Maybe_cisc_spillable ) {
3628     // Check that each has same number of operands at this level
3629     if( (_lChild && !(mRule2->_lChild)) || (_rChild && !(mRule2->_rChild)) ) return Not_cisc_spillable;
3630 
3631     // Check left operands
3632     if( (_lChild == NULL) && (mRule2->_lChild == NULL) ) {
3633       left_spillable = Maybe_cisc_spillable;
3634     } else {
3635       left_spillable = _lChild->cisc_spill_match(globals, registers, mRule2->_lChild, operand, reg_type);
3636     }
3637 
3638     // Check right operands
3639     if( (_rChild == NULL) && (mRule2->_rChild == NULL) ) {
3640       right_spillable =  Maybe_cisc_spillable;
3641     } else {
3642       right_spillable = _rChild->cisc_spill_match(globals, registers, mRule2->_rChild, operand, reg_type);
3643     }
3644 
3645     // Combine results of left and right checks
3646     cisc_spillable = cisc_spill_merge(left_spillable, right_spillable);
3647   }
3648 
3649   return cisc_spillable;
3650 }
3651 
3652 //---------------------------cisc_spill_match_rule------------------------------
3653 // Recursively check two MatchRules for legal conversion via cisc-spilling
3654 // This method handles the root of Match tree,
3655 // general recursive checks done in MatchNode
3656 int  MatchRule::matchrule_cisc_spill_match(FormDict& globals, RegisterForm* registers,
3657                                            MatchRule* mRule2, const char* &operand,
3658                                            const char* &reg_type) {
3659   int cisc_spillable  = Maybe_cisc_spillable;
3660   int left_spillable  = Maybe_cisc_spillable;
3661   int right_spillable = Maybe_cisc_spillable;
3662 
3663   // Check that each sets a result
3664   if( !(sets_result() && mRule2->sets_result()) ) return Not_cisc_spillable;
3665   // Check that each has same number of operands at this level
3666   if( (_lChild && !(mRule2->_lChild)) || (_rChild && !(mRule2->_rChild)) ) return Not_cisc_spillable;
3667 
3668   // Check left operands: at root, must be target of 'Set'
3669   if( (_lChild == NULL) || (mRule2->_lChild == NULL) ) {
3670     left_spillable = Not_cisc_spillable;
3671   } else {
3672     // Do not support cisc-spilling instruction's target location
3673     if( root_ops_match(globals, _lChild->_opType, mRule2->_lChild->_opType) ) {
3674       left_spillable = Maybe_cisc_spillable;
3675     } else {
3676       left_spillable = Not_cisc_spillable;
3677     }
3678   }
3679 
3680   // Check right operands: recursive walk to identify reg->mem operand
3681   if( (_rChild == NULL) && (mRule2->_rChild == NULL) ) {
3682     right_spillable =  Maybe_cisc_spillable;
3683   } else {
3684     right_spillable = _rChild->cisc_spill_match(globals, registers, mRule2->_rChild, operand, reg_type);
3685   }
3686 
3687   // Combine results of left and right checks
3688   cisc_spillable = cisc_spill_merge(left_spillable, right_spillable);
3689 
3690   return cisc_spillable;
3691 }
3692 
3693 //----------------------------- equivalent ------------------------------------
3694 // Recursively check to see if two match rules are equivalent.
3695 // This rule handles the root.
3696 bool MatchRule::equivalent(FormDict &globals, MatchNode *mRule2) {
3697   // Check that each sets a result
3698   if (sets_result() != mRule2->sets_result()) {
3699     return false;
3700   }
3701 
3702   // Check that the current operands/operations match
3703   assert( _opType, "Must have _opType");
3704   assert( mRule2->_opType, "Must have _opType");
3705   const Form *form  = globals[_opType];
3706   const Form *form2 = globals[mRule2->_opType];
3707   if( form != form2 ) {
3708     return false;
3709   }
3710 
3711   if (_lChild ) {
3712     if( !_lChild->equivalent(globals, mRule2->_lChild) )
3713       return false;
3714   } else if (mRule2->_lChild) {
3715     return false; // I have NULL left child, mRule2 has non-NULL left child.
3716   }
3717 
3718   if (_rChild ) {
3719     if( !_rChild->equivalent(globals, mRule2->_rChild) )
3720       return false;
3721   } else if (mRule2->_rChild) {
3722     return false; // I have NULL right child, mRule2 has non-NULL right child.
3723   }
3724 
3725   // We've made it through the gauntlet.
3726   return true;
3727 }
3728 
3729 //----------------------------- equivalent ------------------------------------
3730 // Recursively check to see if two match rules are equivalent.
3731 // This rule handles the operands.
3732 bool MatchNode::equivalent(FormDict &globals, MatchNode *mNode2) {
3733   if( !mNode2 )
3734     return false;
3735 
3736   // Check that the current operands/operations match
3737   assert( _opType, "Must have _opType");
3738   assert( mNode2->_opType, "Must have _opType");
3739   const Form *form  = globals[_opType];
3740   const Form *form2 = globals[mNode2->_opType];
3741   if( form != form2 ) {
3742     return false;
3743   }
3744 
3745   // Check that their children also match
3746   if (_lChild ) {
3747     if( !_lChild->equivalent(globals, mNode2->_lChild) )
3748       return false;
3749   } else if (mNode2->_lChild) {
3750     return false; // I have NULL left child, mNode2 has non-NULL left child.
3751   }
3752 
3753   if (_rChild ) {
3754     if( !_rChild->equivalent(globals, mNode2->_rChild) )
3755       return false;
3756   } else if (mNode2->_rChild) {
3757     return false; // I have NULL right child, mNode2 has non-NULL right child.
3758   }
3759 
3760   // We've made it through the gauntlet.
3761   return true;
3762 }
3763 
3764 //-------------------------- has_commutative_op -------------------------------
3765 // Recursively check for commutative operations with subtree operands
3766 // which could be swapped.
3767 void MatchNode::count_commutative_op(int& count) {
3768   static const char *commut_op_list[] = {
3769     "AddI","AddL","AddF","AddD",
3770     "AndI","AndL",
3771     "MaxI","MinI",
3772     "MulI","MulL","MulF","MulD",
3773     "OrI" ,"OrL" ,
3774     "XorI","XorL"
3775   };
3776   int cnt = sizeof(commut_op_list)/sizeof(char*);
3777 
3778   if( _lChild && _rChild && (_lChild->_lChild || _rChild->_lChild) ) {
3779     // Don't swap if right operand is an immediate constant.
3780     bool is_const = false;
3781     if( _rChild->_lChild == NULL && _rChild->_rChild == NULL ) {
3782       FormDict &globals = _AD.globalNames();
3783       const Form *form = globals[_rChild->_opType];
3784       if ( form ) {
3785         OperandForm  *oper = form->is_operand();
3786         if( oper && oper->interface_type(globals) == Form::constant_interface )
3787           is_const = true;
3788       }
3789     }
3790     if( !is_const ) {
3791       for( int i=0; i<cnt; i++ ) {
3792         if( strcmp(_opType, commut_op_list[i]) == 0 ) {
3793           count++;
3794           _commutative_id = count; // id should be > 0
3795           break;
3796         }
3797       }
3798     }
3799   }
3800   if( _lChild )
3801     _lChild->count_commutative_op(count);
3802   if( _rChild )
3803     _rChild->count_commutative_op(count);
3804 }
3805 
3806 //-------------------------- swap_commutative_op ------------------------------
3807 // Recursively swap specified commutative operation with subtree operands.
3808 void MatchNode::swap_commutative_op(bool atroot, int id) {
3809   if( _commutative_id == id ) { // id should be > 0
3810     assert(_lChild && _rChild && (_lChild->_lChild || _rChild->_lChild ),
3811             "not swappable operation");
3812     MatchNode* tmp = _lChild;
3813     _lChild = _rChild;
3814     _rChild = tmp;
3815     // Don't exit here since we need to build internalop.
3816   }
3817 
3818   bool is_set = ( strcmp(_opType, "Set") == 0 );
3819   if( _lChild )
3820     _lChild->swap_commutative_op(is_set, id);
3821   if( _rChild )
3822     _rChild->swap_commutative_op(is_set, id);
3823 
3824   // If not the root, reduce this subtree to an internal operand
3825   if( !atroot && (_lChild || _rChild) ) {
3826     build_internalop();
3827   }
3828 }
3829 
3830 //-------------------------- swap_commutative_op ------------------------------
3831 // Recursively swap specified commutative operation with subtree operands.
3832 void MatchRule::matchrule_swap_commutative_op(const char* instr_ident, int count, int& match_rules_cnt) {
3833   assert(match_rules_cnt < 100," too many match rule clones");
3834   // Clone
3835   MatchRule* clone = new MatchRule(_AD, this);
3836   // Swap operands of commutative operation
3837   ((MatchNode*)clone)->swap_commutative_op(true, count);
3838   char* buf = (char*) malloc(strlen(instr_ident) + 4);
3839   sprintf(buf, "%s_%d", instr_ident, match_rules_cnt++);
3840   clone->_result = buf;
3841 
3842   clone->_next = this->_next;
3843   this-> _next = clone;
3844   if( (--count) > 0 ) {
3845     this-> matchrule_swap_commutative_op(instr_ident, count, match_rules_cnt);
3846     clone->matchrule_swap_commutative_op(instr_ident, count, match_rules_cnt);
3847   }
3848 }
3849 
3850 //------------------------------MatchRule--------------------------------------
3851 MatchRule::MatchRule(ArchDesc &ad)
3852   : MatchNode(ad), _depth(0), _construct(NULL), _numchilds(0) {
3853     _next = NULL;
3854 }
3855 
3856 MatchRule::MatchRule(ArchDesc &ad, MatchRule* mRule)
3857   : MatchNode(ad, *mRule, 0), _depth(mRule->_depth),
3858     _construct(mRule->_construct), _numchilds(mRule->_numchilds) {
3859     _next = NULL;
3860 }
3861 
3862 MatchRule::MatchRule(ArchDesc &ad, MatchNode* mroot, int depth, char *cnstr,
3863                      int numleaves)
3864   : MatchNode(ad,*mroot), _depth(depth), _construct(cnstr),
3865     _numchilds(0) {
3866       _next = NULL;
3867       mroot->_lChild = NULL;
3868       mroot->_rChild = NULL;
3869       delete mroot;
3870       _numleaves = numleaves;
3871       _numchilds = (_lChild ? 1 : 0) + (_rChild ? 1 : 0);
3872 }
3873 MatchRule::~MatchRule() {
3874 }
3875 
3876 // Recursive call collecting info on top-level operands, not transitive.
3877 // Implementation does not modify state of internal structures.
3878 void MatchRule::append_components(FormDict& locals, ComponentList& components, bool def_flag) const {
3879   assert (_name != NULL, "MatchNode::build_components encountered empty node\n");
3880 
3881   MatchNode::append_components(locals, components,
3882                                false /* not necessarily a def */);
3883 }
3884 
3885 // Recursive call on all operands' match rules in my match rule.
3886 // Implementation does not modify state of internal structures  since they
3887 // can be shared.
3888 // The MatchNode that is called first treats its
3889 bool MatchRule::base_operand(uint &position0, FormDict &globals,
3890                              const char *&result, const char * &name,
3891                              const char * &opType)const{
3892   uint position = position0;
3893 
3894   return (MatchNode::base_operand( position, globals, result, name, opType));
3895 }
3896 
3897 
3898 bool MatchRule::is_base_register(FormDict &globals) const {
3899   uint   position = 1;
3900   const char  *result   = NULL;
3901   const char  *name     = NULL;
3902   const char  *opType   = NULL;
3903   if (!base_operand(position, globals, result, name, opType)) {
3904     position = 0;
3905     if( base_operand(position, globals, result, name, opType) &&
3906         (strcmp(opType,"RegI")==0 ||
3907          strcmp(opType,"RegP")==0 ||
3908          strcmp(opType,"RegN")==0 ||
3909          strcmp(opType,"RegL")==0 ||
3910          strcmp(opType,"RegF")==0 ||
3911          strcmp(opType,"RegD")==0 ||
3912          strcmp(opType,"VecS")==0 ||
3913          strcmp(opType,"VecD")==0 ||
3914          strcmp(opType,"VecX")==0 ||
3915          strcmp(opType,"VecY")==0 ||
3916          strcmp(opType,"Reg" )==0) ) {
3917       return 1;
3918     }
3919   }
3920   return 0;
3921 }
3922 
3923 Form::DataType MatchRule::is_base_constant(FormDict &globals) const {
3924   uint         position = 1;
3925   const char  *result   = NULL;
3926   const char  *name     = NULL;
3927   const char  *opType   = NULL;
3928   if (!base_operand(position, globals, result, name, opType)) {
3929     position = 0;
3930     if (base_operand(position, globals, result, name, opType)) {
3931       return ideal_to_const_type(opType);
3932     }
3933   }
3934   return Form::none;
3935 }
3936 
3937 bool MatchRule::is_chain_rule(FormDict &globals) const {
3938 
3939   // Check for chain rule, and do not generate a match list for it
3940   if ((_lChild == NULL) && (_rChild == NULL) ) {
3941     const Form *form = globals[_opType];
3942     // If this is ideal, then it is a base match, not a chain rule.
3943     if ( form && form->is_operand() && (!form->ideal_only())) {
3944       return true;
3945     }
3946   }
3947   // Check for "Set" form of chain rule, and do not generate a match list
3948   if (_rChild) {
3949     const char *rch = _rChild->_opType;
3950     const Form *form = globals[rch];
3951     if ((!strcmp(_opType,"Set") &&
3952          ((form) && form->is_operand()))) {
3953       return true;
3954     }
3955   }
3956   return false;
3957 }
3958 
3959 int MatchRule::is_ideal_copy() const {
3960   if( _rChild ) {
3961     const char  *opType = _rChild->_opType;
3962 #if 1
3963     if( strcmp(opType,"CastIP")==0 )
3964       return 1;
3965 #else
3966     if( strcmp(opType,"CastII")==0 )
3967       return 1;
3968     // Do not treat *CastPP this way, because it
3969     // may transfer a raw pointer to an oop.
3970     // If the register allocator were to coalesce this
3971     // into a single LRG, the GC maps would be incorrect.
3972     //if( strcmp(opType,"CastPP")==0 )
3973     //  return 1;
3974     //if( strcmp(opType,"CheckCastPP")==0 )
3975     //  return 1;
3976     //
3977     // Do not treat CastX2P or CastP2X this way, because
3978     // raw pointers and int types are treated differently
3979     // when saving local & stack info for safepoints in
3980     // Output().
3981     //if( strcmp(opType,"CastX2P")==0 )
3982     //  return 1;
3983     //if( strcmp(opType,"CastP2X")==0 )
3984     //  return 1;
3985 #endif
3986   }
3987   if( is_chain_rule(_AD.globalNames()) &&
3988       _lChild && strncmp(_lChild->_opType,"stackSlot",9)==0 )
3989     return 1;
3990   return 0;
3991 }
3992 
3993 
3994 int MatchRule::is_expensive() const {
3995   if( _rChild ) {
3996     const char  *opType = _rChild->_opType;
3997     if( strcmp(opType,"AtanD")==0 ||
3998         strcmp(opType,"CosD")==0 ||
3999         strcmp(opType,"DivD")==0 ||
4000         strcmp(opType,"DivF")==0 ||
4001         strcmp(opType,"DivI")==0 ||
4002         strcmp(opType,"ExpD")==0 ||
4003         strcmp(opType,"LogD")==0 ||
4004         strcmp(opType,"Log10D")==0 ||
4005         strcmp(opType,"ModD")==0 ||
4006         strcmp(opType,"ModF")==0 ||
4007         strcmp(opType,"ModI")==0 ||
4008         strcmp(opType,"PowD")==0 ||
4009         strcmp(opType,"SinD")==0 ||
4010         strcmp(opType,"SqrtD")==0 ||
4011         strcmp(opType,"TanD")==0 ||
4012         strcmp(opType,"ConvD2F")==0 ||
4013         strcmp(opType,"ConvD2I")==0 ||
4014         strcmp(opType,"ConvD2L")==0 ||
4015         strcmp(opType,"ConvF2D")==0 ||
4016         strcmp(opType,"ConvF2I")==0 ||
4017         strcmp(opType,"ConvF2L")==0 ||
4018         strcmp(opType,"ConvI2D")==0 ||
4019         strcmp(opType,"ConvI2F")==0 ||
4020         strcmp(opType,"ConvI2L")==0 ||
4021         strcmp(opType,"ConvL2D")==0 ||
4022         strcmp(opType,"ConvL2F")==0 ||
4023         strcmp(opType,"ConvL2I")==0 ||
4024         strcmp(opType,"DecodeN")==0 ||
4025         strcmp(opType,"EncodeP")==0 ||
4026         strcmp(opType,"EncodePKlass")==0 ||
4027         strcmp(opType,"DecodeNKlass")==0 ||
4028         strcmp(opType,"RoundDouble")==0 ||
4029         strcmp(opType,"RoundFloat")==0 ||
4030         strcmp(opType,"ReverseBytesI")==0 ||
4031         strcmp(opType,"ReverseBytesL")==0 ||
4032         strcmp(opType,"ReverseBytesUS")==0 ||
4033         strcmp(opType,"ReverseBytesS")==0 ||
4034         strcmp(opType,"ReplicateB")==0 ||
4035         strcmp(opType,"ReplicateS")==0 ||
4036         strcmp(opType,"ReplicateI")==0 ||
4037         strcmp(opType,"ReplicateL")==0 ||
4038         strcmp(opType,"ReplicateF")==0 ||
4039         strcmp(opType,"ReplicateD")==0 ||
4040         0 /* 0 to line up columns nicely */ )
4041       return 1;
4042   }
4043   return 0;
4044 }
4045 
4046 bool MatchRule::is_ideal_if() const {
4047   if( !_opType ) return false;
4048   return
4049     !strcmp(_opType,"If"            ) ||
4050     !strcmp(_opType,"CountedLoopEnd");
4051 }
4052 
4053 bool MatchRule::is_ideal_fastlock() const {
4054   if ( _opType && (strcmp(_opType,"Set") == 0) && _rChild ) {
4055     return (strcmp(_rChild->_opType,"FastLock") == 0);
4056   }
4057   return false;
4058 }
4059 
4060 bool MatchRule::is_ideal_membar() const {
4061   if( !_opType ) return false;
4062   return
4063     !strcmp(_opType,"MemBarAcquire") ||
4064     !strcmp(_opType,"MemBarRelease") ||
4065     !strcmp(_opType,"MemBarAcquireLock") ||
4066     !strcmp(_opType,"MemBarReleaseLock") ||
4067     !strcmp(_opType,"LoadFence" ) ||
4068     !strcmp(_opType,"StoreFence") ||
4069     !strcmp(_opType,"MemBarVolatile") ||
4070     !strcmp(_opType,"MemBarCPUOrder") ||
4071     !strcmp(_opType,"MemBarStoreStore");
4072 }
4073 
4074 bool MatchRule::is_ideal_loadPC() const {
4075   if ( _opType && (strcmp(_opType,"Set") == 0) && _rChild ) {
4076     return (strcmp(_rChild->_opType,"LoadPC") == 0);
4077   }
4078   return false;
4079 }
4080 
4081 bool MatchRule::is_ideal_box() const {
4082   if ( _opType && (strcmp(_opType,"Set") == 0) && _rChild ) {
4083     return (strcmp(_rChild->_opType,"Box") == 0);
4084   }
4085   return false;
4086 }
4087 
4088 bool MatchRule::is_ideal_goto() const {
4089   bool   ideal_goto = false;
4090 
4091   if( _opType && (strcmp(_opType,"Goto") == 0) ) {
4092     ideal_goto = true;
4093   }
4094   return ideal_goto;
4095 }
4096 
4097 bool MatchRule::is_ideal_jump() const {
4098   if( _opType ) {
4099     if( !strcmp(_opType,"Jump") )
4100       return true;
4101   }
4102   return false;
4103 }
4104 
4105 bool MatchRule::is_ideal_bool() const {
4106   if( _opType ) {
4107     if( !strcmp(_opType,"Bool") )
4108       return true;
4109   }
4110   return false;
4111 }
4112 
4113 
4114 Form::DataType MatchRule::is_ideal_load() const {
4115   Form::DataType ideal_load = Form::none;
4116 
4117   if ( _opType && (strcmp(_opType,"Set") == 0) && _rChild ) {
4118     const char *opType = _rChild->_opType;
4119     ideal_load = is_load_from_memory(opType);
4120   }
4121 
4122   return ideal_load;
4123 }
4124 
4125 bool MatchRule::is_vector() const {
4126   static const char *vector_list[] = {
4127     "AddVB","AddVS","AddVI","AddVL","AddVF","AddVD",
4128     "SubVB","SubVS","SubVI","SubVL","SubVF","SubVD",
4129     "MulVS","MulVI","MulVF","MulVD",
4130     "DivVF","DivVD",
4131     "AndV" ,"XorV" ,"OrV",
4132     "LShiftCntV","RShiftCntV",
4133     "LShiftVB","LShiftVS","LShiftVI","LShiftVL",
4134     "RShiftVB","RShiftVS","RShiftVI","RShiftVL",
4135     "URShiftVB","URShiftVS","URShiftVI","URShiftVL",
4136     "ReplicateB","ReplicateS","ReplicateI","ReplicateL","ReplicateF","ReplicateD",
4137     "LoadVector","StoreVector",
4138     // Next are not supported currently.
4139     "PackB","PackS","PackI","PackL","PackF","PackD","Pack2L","Pack2D",
4140     "ExtractB","ExtractUB","ExtractC","ExtractS","ExtractI","ExtractL","ExtractF","ExtractD"
4141   };
4142   int cnt = sizeof(vector_list)/sizeof(char*);
4143   if (_rChild) {
4144     const char  *opType = _rChild->_opType;
4145     for (int i=0; i<cnt; i++)
4146       if (strcmp(opType,vector_list[i]) == 0)
4147         return true;
4148   }
4149   return false;
4150 }
4151 
4152 
4153 bool MatchRule::skip_antidep_check() const {
4154   // Some loads operate on what is effectively immutable memory so we
4155   // should skip the anti dep computations.  For some of these nodes
4156   // the rewritable field keeps the anti dep logic from triggering but
4157   // for certain kinds of LoadKlass it does not since they are
4158   // actually reading memory which could be rewritten by the runtime,
4159   // though never by generated code.  This disables it uniformly for
4160   // the nodes that behave like this: LoadKlass, LoadNKlass and
4161   // LoadRange.
4162   if ( _opType && (strcmp(_opType,"Set") == 0) && _rChild ) {
4163     const char *opType = _rChild->_opType;
4164     if (strcmp("LoadKlass", opType) == 0 ||
4165         strcmp("LoadNKlass", opType) == 0 ||
4166         strcmp("LoadRange", opType) == 0) {
4167       return true;
4168     }
4169   }
4170 
4171   return false;
4172 }
4173 
4174 
4175 Form::DataType MatchRule::is_ideal_store() const {
4176   Form::DataType ideal_store = Form::none;
4177 
4178   if ( _opType && (strcmp(_opType,"Set") == 0) && _rChild ) {
4179     const char *opType = _rChild->_opType;
4180     ideal_store = is_store_to_memory(opType);
4181   }
4182 
4183   return ideal_store;
4184 }
4185 
4186 
4187 void MatchRule::dump() {
4188   output(stderr);
4189 }
4190 
4191 // Write just one line.
4192 void MatchRule::output_short(FILE *fp) {
4193   fprintf(fp,"MatchRule: ( %s",_name);
4194   if (_lChild) _lChild->output(fp);
4195   if (_rChild) _rChild->output(fp);
4196   fprintf(fp," )");
4197 }
4198 
4199 void MatchRule::output(FILE *fp) {
4200   output_short(fp);
4201   fprintf(fp,"\n   nesting depth = %d\n", _depth);
4202   if (_result) fprintf(fp,"   Result Type = %s", _result);
4203   fprintf(fp,"\n");
4204 }
4205 
4206 //------------------------------Attribute--------------------------------------
4207 Attribute::Attribute(char *id, char* val, int type)
4208   : _ident(id), _val(val), _atype(type) {
4209 }
4210 Attribute::~Attribute() {
4211 }
4212 
4213 int Attribute::int_val(ArchDesc &ad) {
4214   // Make sure it is an integer constant:
4215   int result = 0;
4216   if (!_val || !ADLParser::is_int_token(_val, result)) {
4217     ad.syntax_err(0, "Attribute %s must have an integer value: %s",
4218                   _ident, _val ? _val : "");
4219   }
4220   return result;
4221 }
4222 
4223 void Attribute::dump() {
4224   output(stderr);
4225 } // Debug printer
4226 
4227 // Write to output files
4228 void Attribute::output(FILE *fp) {
4229   fprintf(fp,"Attribute: %s  %s\n", (_ident?_ident:""), (_val?_val:""));
4230 }
4231 
4232 //------------------------------FormatRule----------------------------------
4233 FormatRule::FormatRule(char *temp)
4234   : _temp(temp) {
4235 }
4236 FormatRule::~FormatRule() {
4237 }
4238 
4239 void FormatRule::dump() {
4240   output(stderr);
4241 }
4242 
4243 // Write to output files
4244 void FormatRule::output(FILE *fp) {
4245   fprintf(fp,"\nFormat Rule: \n%s", (_temp?_temp:""));
4246   fprintf(fp,"\n");
4247 }