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