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