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