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