1 /*
   2  * Copyright (c) 1998, 2015, 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 == NULL ) 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,"PrefetchAllocation")==0 )
3493     return 1;
3494   if( _lChild ) {
3495     const char *opType = _lChild->_opType;
3496     for( int i=0; i<cnt; i++ )
3497       if( strcmp(opType,needs_ideal_memory_list[i]) == 0 )
3498         return 1;
3499     if( _lChild->needs_ideal_memory_edge(globals) )
3500       return 1;
3501   }
3502   if( _rChild ) {
3503     const char *opType = _rChild->_opType;
3504     for( int i=0; i<cnt; i++ )
3505       if( strcmp(opType,needs_ideal_memory_list[i]) == 0 )
3506         return 1;
3507     if( _rChild->needs_ideal_memory_edge(globals) )
3508       return 1;
3509   }
3510 
3511   return 0;
3512 }
3513 
3514 // TRUE if defines a derived oop, and so needs a base oop edge present
3515 // post-matching.
3516 int MatchNode::needs_base_oop_edge() const {
3517   if( !strcmp(_opType,"AddP") ) return 1;
3518   if( strcmp(_opType,"Set") ) return 0;
3519   return !strcmp(_rChild->_opType,"AddP");
3520 }
3521 
3522 int InstructForm::needs_base_oop_edge(FormDict &globals) const {
3523   if( is_simple_chain_rule(globals) ) {
3524     const char *src = _matrule->_rChild->_opType;
3525     OperandForm *src_op = globals[src]->is_operand();
3526     assert( src_op, "Not operand class of chain rule" );
3527     return src_op->_matrule ? src_op->_matrule->needs_base_oop_edge() : 0;
3528   }                             // Else check instruction
3529 
3530   return _matrule ? _matrule->needs_base_oop_edge() : 0;
3531 }
3532 
3533 
3534 //-------------------------cisc spilling methods-------------------------------
3535 // helper routines and methods for detecting cisc-spilling instructions
3536 //-------------------------cisc_spill_merge------------------------------------
3537 int MatchNode::cisc_spill_merge(int left_spillable, int right_spillable) {
3538   int cisc_spillable  = Maybe_cisc_spillable;
3539 
3540   // Combine results of left and right checks
3541   if( (left_spillable == Maybe_cisc_spillable) && (right_spillable == Maybe_cisc_spillable) ) {
3542     // neither side is spillable, nor prevents cisc spilling
3543     cisc_spillable = Maybe_cisc_spillable;
3544   }
3545   else if( (left_spillable == Maybe_cisc_spillable) && (right_spillable > Maybe_cisc_spillable) ) {
3546     // right side is spillable
3547     cisc_spillable = right_spillable;
3548   }
3549   else if( (right_spillable == Maybe_cisc_spillable) && (left_spillable > Maybe_cisc_spillable) ) {
3550     // left side is spillable
3551     cisc_spillable = left_spillable;
3552   }
3553   else if( (left_spillable == Not_cisc_spillable) || (right_spillable == Not_cisc_spillable) ) {
3554     // left or right prevents cisc spilling this instruction
3555     cisc_spillable = Not_cisc_spillable;
3556   }
3557   else {
3558     // Only allow one to spill
3559     cisc_spillable = Not_cisc_spillable;
3560   }
3561 
3562   return cisc_spillable;
3563 }
3564 
3565 //-------------------------root_ops_match--------------------------------------
3566 bool static root_ops_match(FormDict &globals, const char *op1, const char *op2) {
3567   // Base Case: check that the current operands/operations match
3568   assert( op1, "Must have op's name");
3569   assert( op2, "Must have op's name");
3570   const Form *form1 = globals[op1];
3571   const Form *form2 = globals[op2];
3572 
3573   return (form1 == form2);
3574 }
3575 
3576 //-------------------------cisc_spill_match_node-------------------------------
3577 // Recursively check two MatchRules for legal conversion via cisc-spilling
3578 int MatchNode::cisc_spill_match(FormDict& globals, RegisterForm* registers, MatchNode* mRule2, const char* &operand, const char* &reg_type) {
3579   int cisc_spillable  = Maybe_cisc_spillable;
3580   int left_spillable  = Maybe_cisc_spillable;
3581   int right_spillable = Maybe_cisc_spillable;
3582 
3583   // Check that each has same number of operands at this level
3584   if( (_lChild && !(mRule2->_lChild)) || (_rChild && !(mRule2->_rChild)) )
3585     return Not_cisc_spillable;
3586 
3587   // Base Case: check that the current operands/operations match
3588   // or are CISC spillable
3589   assert( _opType, "Must have _opType");
3590   assert( mRule2->_opType, "Must have _opType");
3591   const Form *form  = globals[_opType];
3592   const Form *form2 = globals[mRule2->_opType];
3593   if( form == form2 ) {
3594     cisc_spillable = Maybe_cisc_spillable;
3595   } else {
3596     const InstructForm *form2_inst = form2 ? form2->is_instruction() : NULL;
3597     const char *name_left  = mRule2->_lChild ? mRule2->_lChild->_opType : NULL;
3598     const char *name_right = mRule2->_rChild ? mRule2->_rChild->_opType : NULL;
3599     DataType data_type = Form::none;
3600     if (form->is_operand()) {
3601       // Make sure the loadX matches the type of the reg
3602       data_type = form->ideal_to_Reg_type(form->is_operand()->ideal_type(globals));
3603     }
3604     // Detect reg vs (loadX memory)
3605     if( form->is_cisc_reg(globals)
3606         && form2_inst
3607         && data_type != Form::none
3608         && (is_load_from_memory(mRule2->_opType) == data_type) // reg vs. (load memory)
3609         && (name_left != NULL)       // NOT (load)
3610         && (name_right == NULL) ) {  // NOT (load memory foo)
3611       const Form *form2_left = name_left ? globals[name_left] : NULL;
3612       if( form2_left && form2_left->is_cisc_mem(globals) ) {
3613         cisc_spillable = Is_cisc_spillable;
3614         operand        = _name;
3615         reg_type       = _result;
3616         return Is_cisc_spillable;
3617       } else {
3618         cisc_spillable = Not_cisc_spillable;
3619       }
3620     }
3621     // Detect reg vs memory
3622     else if( form->is_cisc_reg(globals) && form2->is_cisc_mem(globals) ) {
3623       cisc_spillable = Is_cisc_spillable;
3624       operand        = _name;
3625       reg_type       = _result;
3626       return Is_cisc_spillable;
3627     } else {
3628       cisc_spillable = Not_cisc_spillable;
3629     }
3630   }
3631 
3632   // If cisc is still possible, check rest of tree
3633   if( cisc_spillable == Maybe_cisc_spillable ) {
3634     // Check that each has same number of operands at this level
3635     if( (_lChild && !(mRule2->_lChild)) || (_rChild && !(mRule2->_rChild)) ) return Not_cisc_spillable;
3636 
3637     // Check left operands
3638     if( (_lChild == NULL) && (mRule2->_lChild == NULL) ) {
3639       left_spillable = Maybe_cisc_spillable;
3640     } else {
3641       left_spillable = _lChild->cisc_spill_match(globals, registers, mRule2->_lChild, operand, reg_type);
3642     }
3643 
3644     // Check right operands
3645     if( (_rChild == NULL) && (mRule2->_rChild == NULL) ) {
3646       right_spillable =  Maybe_cisc_spillable;
3647     } else {
3648       right_spillable = _rChild->cisc_spill_match(globals, registers, mRule2->_rChild, operand, reg_type);
3649     }
3650 
3651     // Combine results of left and right checks
3652     cisc_spillable = cisc_spill_merge(left_spillable, right_spillable);
3653   }
3654 
3655   return cisc_spillable;
3656 }
3657 
3658 //---------------------------cisc_spill_match_rule------------------------------
3659 // Recursively check two MatchRules for legal conversion via cisc-spilling
3660 // This method handles the root of Match tree,
3661 // general recursive checks done in MatchNode
3662 int  MatchRule::matchrule_cisc_spill_match(FormDict& globals, RegisterForm* registers,
3663                                            MatchRule* mRule2, const char* &operand,
3664                                            const char* &reg_type) {
3665   int cisc_spillable  = Maybe_cisc_spillable;
3666   int left_spillable  = Maybe_cisc_spillable;
3667   int right_spillable = Maybe_cisc_spillable;
3668 
3669   // Check that each sets a result
3670   if( !(sets_result() && mRule2->sets_result()) ) return Not_cisc_spillable;
3671   // Check that each has same number of operands at this level
3672   if( (_lChild && !(mRule2->_lChild)) || (_rChild && !(mRule2->_rChild)) ) return Not_cisc_spillable;
3673 
3674   // Check left operands: at root, must be target of 'Set'
3675   if( (_lChild == NULL) || (mRule2->_lChild == NULL) ) {
3676     left_spillable = Not_cisc_spillable;
3677   } else {
3678     // Do not support cisc-spilling instruction's target location
3679     if( root_ops_match(globals, _lChild->_opType, mRule2->_lChild->_opType) ) {
3680       left_spillable = Maybe_cisc_spillable;
3681     } else {
3682       left_spillable = Not_cisc_spillable;
3683     }
3684   }
3685 
3686   // Check right operands: recursive walk to identify reg->mem operand
3687   if( (_rChild == NULL) && (mRule2->_rChild == NULL) ) {
3688     right_spillable =  Maybe_cisc_spillable;
3689   } else {
3690     right_spillable = _rChild->cisc_spill_match(globals, registers, mRule2->_rChild, operand, reg_type);
3691   }
3692 
3693   // Combine results of left and right checks
3694   cisc_spillable = cisc_spill_merge(left_spillable, right_spillable);
3695 
3696   return cisc_spillable;
3697 }
3698 
3699 //----------------------------- equivalent ------------------------------------
3700 // Recursively check to see if two match rules are equivalent.
3701 // This rule handles the root.
3702 bool MatchRule::equivalent(FormDict &globals, MatchNode *mRule2) {
3703   // Check that each sets a result
3704   if (sets_result() != mRule2->sets_result()) {
3705     return false;
3706   }
3707 
3708   // Check that the current operands/operations match
3709   assert( _opType, "Must have _opType");
3710   assert( mRule2->_opType, "Must have _opType");
3711   const Form *form  = globals[_opType];
3712   const Form *form2 = globals[mRule2->_opType];
3713   if( form != form2 ) {
3714     return false;
3715   }
3716 
3717   if (_lChild ) {
3718     if( !_lChild->equivalent(globals, mRule2->_lChild) )
3719       return false;
3720   } else if (mRule2->_lChild) {
3721     return false; // I have NULL left child, mRule2 has non-NULL left child.
3722   }
3723 
3724   if (_rChild ) {
3725     if( !_rChild->equivalent(globals, mRule2->_rChild) )
3726       return false;
3727   } else if (mRule2->_rChild) {
3728     return false; // I have NULL right child, mRule2 has non-NULL right child.
3729   }
3730 
3731   // We've made it through the gauntlet.
3732   return true;
3733 }
3734 
3735 //----------------------------- equivalent ------------------------------------
3736 // Recursively check to see if two match rules are equivalent.
3737 // This rule handles the operands.
3738 bool MatchNode::equivalent(FormDict &globals, MatchNode *mNode2) {
3739   if( !mNode2 )
3740     return false;
3741 
3742   // Check that the current operands/operations match
3743   assert( _opType, "Must have _opType");
3744   assert( mNode2->_opType, "Must have _opType");
3745   const Form *form  = globals[_opType];
3746   const Form *form2 = globals[mNode2->_opType];
3747   if( form != form2 ) {
3748     return false;
3749   }
3750 
3751   // Check that their children also match
3752   if (_lChild ) {
3753     if( !_lChild->equivalent(globals, mNode2->_lChild) )
3754       return false;
3755   } else if (mNode2->_lChild) {
3756     return false; // I have NULL left child, mNode2 has non-NULL left child.
3757   }
3758 
3759   if (_rChild ) {
3760     if( !_rChild->equivalent(globals, mNode2->_rChild) )
3761       return false;
3762   } else if (mNode2->_rChild) {
3763     return false; // I have NULL right child, mNode2 has non-NULL right child.
3764   }
3765 
3766   // We've made it through the gauntlet.
3767   return true;
3768 }
3769 
3770 //-------------------------- has_commutative_op -------------------------------
3771 // Recursively check for commutative operations with subtree operands
3772 // which could be swapped.
3773 void MatchNode::count_commutative_op(int& count) {
3774   static const char *commut_op_list[] = {
3775     "AddI","AddL","AddF","AddD",
3776     "AndI","AndL",
3777     "MaxI","MinI",
3778     "MulI","MulL","MulF","MulD",
3779     "OrI" ,"OrL" ,
3780     "XorI","XorL"
3781   };
3782   int cnt = sizeof(commut_op_list)/sizeof(char*);
3783 
3784   if( _lChild && _rChild && (_lChild->_lChild || _rChild->_lChild) ) {
3785     // Don't swap if right operand is an immediate constant.
3786     bool is_const = false;
3787     if( _rChild->_lChild == NULL && _rChild->_rChild == NULL ) {
3788       FormDict &globals = _AD.globalNames();
3789       const Form *form = globals[_rChild->_opType];
3790       if ( form ) {
3791         OperandForm  *oper = form->is_operand();
3792         if( oper && oper->interface_type(globals) == Form::constant_interface )
3793           is_const = true;
3794       }
3795     }
3796     if( !is_const ) {
3797       for( int i=0; i<cnt; i++ ) {
3798         if( strcmp(_opType, commut_op_list[i]) == 0 ) {
3799           count++;
3800           _commutative_id = count; // id should be > 0
3801           break;
3802         }
3803       }
3804     }
3805   }
3806   if( _lChild )
3807     _lChild->count_commutative_op(count);
3808   if( _rChild )
3809     _rChild->count_commutative_op(count);
3810 }
3811 
3812 //-------------------------- swap_commutative_op ------------------------------
3813 // Recursively swap specified commutative operation with subtree operands.
3814 void MatchNode::swap_commutative_op(bool atroot, int id) {
3815   if( _commutative_id == id ) { // id should be > 0
3816     assert(_lChild && _rChild && (_lChild->_lChild || _rChild->_lChild ),
3817             "not swappable operation");
3818     MatchNode* tmp = _lChild;
3819     _lChild = _rChild;
3820     _rChild = tmp;
3821     // Don't exit here since we need to build internalop.
3822   }
3823 
3824   bool is_set = ( strcmp(_opType, "Set") == 0 );
3825   if( _lChild )
3826     _lChild->swap_commutative_op(is_set, id);
3827   if( _rChild )
3828     _rChild->swap_commutative_op(is_set, id);
3829 
3830   // If not the root, reduce this subtree to an internal operand
3831   if( !atroot && (_lChild || _rChild) ) {
3832     build_internalop();
3833   }
3834 }
3835 
3836 //-------------------------- swap_commutative_op ------------------------------
3837 // Recursively swap specified commutative operation with subtree operands.
3838 void MatchRule::matchrule_swap_commutative_op(const char* instr_ident, int count, int& match_rules_cnt) {
3839   assert(match_rules_cnt < 100," too many match rule clones");
3840   // Clone
3841   MatchRule* clone = new MatchRule(_AD, this);
3842   // Swap operands of commutative operation
3843   ((MatchNode*)clone)->swap_commutative_op(true, count);
3844   char* buf = (char*) malloc(strlen(instr_ident) + 4);
3845   sprintf(buf, "%s_%d", instr_ident, match_rules_cnt++);
3846   clone->_result = buf;
3847 
3848   clone->_next = this->_next;
3849   this-> _next = clone;
3850   if( (--count) > 0 ) {
3851     this-> matchrule_swap_commutative_op(instr_ident, count, match_rules_cnt);
3852     clone->matchrule_swap_commutative_op(instr_ident, count, match_rules_cnt);
3853   }
3854 }
3855 
3856 //------------------------------MatchRule--------------------------------------
3857 MatchRule::MatchRule(ArchDesc &ad)
3858   : MatchNode(ad), _depth(0), _construct(NULL), _numchilds(0) {
3859     _next = NULL;
3860 }
3861 
3862 MatchRule::MatchRule(ArchDesc &ad, MatchRule* mRule)
3863   : MatchNode(ad, *mRule, 0), _depth(mRule->_depth),
3864     _construct(mRule->_construct), _numchilds(mRule->_numchilds) {
3865     _next = NULL;
3866 }
3867 
3868 MatchRule::MatchRule(ArchDesc &ad, MatchNode* mroot, int depth, char *cnstr,
3869                      int numleaves)
3870   : MatchNode(ad,*mroot), _depth(depth), _construct(cnstr),
3871     _numchilds(0) {
3872       _next = NULL;
3873       mroot->_lChild = NULL;
3874       mroot->_rChild = NULL;
3875       delete mroot;
3876       _numleaves = numleaves;
3877       _numchilds = (_lChild ? 1 : 0) + (_rChild ? 1 : 0);
3878 }
3879 MatchRule::~MatchRule() {
3880 }
3881 
3882 // Recursive call collecting info on top-level operands, not transitive.
3883 // Implementation does not modify state of internal structures.
3884 void MatchRule::append_components(FormDict& locals, ComponentList& components, bool def_flag) const {
3885   assert (_name != NULL, "MatchNode::build_components encountered empty node\n");
3886 
3887   MatchNode::append_components(locals, components,
3888                                false /* not necessarily a def */);
3889 }
3890 
3891 // Recursive call on all operands' match rules in my match rule.
3892 // Implementation does not modify state of internal structures  since they
3893 // can be shared.
3894 // The MatchNode that is called first treats its
3895 bool MatchRule::base_operand(uint &position0, FormDict &globals,
3896                              const char *&result, const char * &name,
3897                              const char * &opType)const{
3898   uint position = position0;
3899 
3900   return (MatchNode::base_operand( position, globals, result, name, opType));
3901 }
3902 
3903 
3904 bool MatchRule::is_base_register(FormDict &globals) const {
3905   uint   position = 1;
3906   const char  *result   = NULL;
3907   const char  *name     = NULL;
3908   const char  *opType   = NULL;
3909   if (!base_operand(position, globals, result, name, opType)) {
3910     position = 0;
3911     if( base_operand(position, globals, result, name, opType) &&
3912         (strcmp(opType,"RegI")==0 ||
3913          strcmp(opType,"RegP")==0 ||
3914          strcmp(opType,"RegN")==0 ||
3915          strcmp(opType,"RegL")==0 ||
3916          strcmp(opType,"RegF")==0 ||
3917          strcmp(opType,"RegD")==0 ||
3918          strcmp(opType,"VecS")==0 ||
3919          strcmp(opType,"VecD")==0 ||
3920          strcmp(opType,"VecX")==0 ||
3921          strcmp(opType,"VecY")==0 ||
3922          strcmp(opType,"VecZ")==0 ||
3923          strcmp(opType,"Reg" )==0) ) {
3924       return 1;
3925     }
3926   }
3927   return 0;
3928 }
3929 
3930 Form::DataType MatchRule::is_base_constant(FormDict &globals) const {
3931   uint         position = 1;
3932   const char  *result   = NULL;
3933   const char  *name     = NULL;
3934   const char  *opType   = NULL;
3935   if (!base_operand(position, globals, result, name, opType)) {
3936     position = 0;
3937     if (base_operand(position, globals, result, name, opType)) {
3938       return ideal_to_const_type(opType);
3939     }
3940   }
3941   return Form::none;
3942 }
3943 
3944 bool MatchRule::is_chain_rule(FormDict &globals) const {
3945 
3946   // Check for chain rule, and do not generate a match list for it
3947   if ((_lChild == NULL) && (_rChild == NULL) ) {
3948     const Form *form = globals[_opType];
3949     // If this is ideal, then it is a base match, not a chain rule.
3950     if ( form && form->is_operand() && (!form->ideal_only())) {
3951       return true;
3952     }
3953   }
3954   // Check for "Set" form of chain rule, and do not generate a match list
3955   if (_rChild) {
3956     const char *rch = _rChild->_opType;
3957     const Form *form = globals[rch];
3958     if ((!strcmp(_opType,"Set") &&
3959          ((form) && form->is_operand()))) {
3960       return true;
3961     }
3962   }
3963   return false;
3964 }
3965 
3966 int MatchRule::is_ideal_copy() const {
3967   if( _rChild ) {
3968     const char  *opType = _rChild->_opType;
3969 #if 1
3970     if( strcmp(opType,"CastIP")==0 )
3971       return 1;
3972 #else
3973     if( strcmp(opType,"CastII")==0 )
3974       return 1;
3975     // Do not treat *CastPP this way, because it
3976     // may transfer a raw pointer to an oop.
3977     // If the register allocator were to coalesce this
3978     // into a single LRG, the GC maps would be incorrect.
3979     //if( strcmp(opType,"CastPP")==0 )
3980     //  return 1;
3981     //if( strcmp(opType,"CheckCastPP")==0 )
3982     //  return 1;
3983     //
3984     // Do not treat CastX2P or CastP2X this way, because
3985     // raw pointers and int types are treated differently
3986     // when saving local & stack info for safepoints in
3987     // Output().
3988     //if( strcmp(opType,"CastX2P")==0 )
3989     //  return 1;
3990     //if( strcmp(opType,"CastP2X")==0 )
3991     //  return 1;
3992 #endif
3993   }
3994   if( is_chain_rule(_AD.globalNames()) &&
3995       _lChild && strncmp(_lChild->_opType,"stackSlot",9)==0 )
3996     return 1;
3997   return 0;
3998 }
3999 
4000 
4001 int MatchRule::is_expensive() const {
4002   if( _rChild ) {
4003     const char  *opType = _rChild->_opType;
4004     if( strcmp(opType,"AtanD")==0 ||
4005         strcmp(opType,"CosD")==0 ||
4006         strcmp(opType,"DivD")==0 ||
4007         strcmp(opType,"DivF")==0 ||
4008         strcmp(opType,"DivI")==0 ||
4009         strcmp(opType,"LogD")==0 ||
4010         strcmp(opType,"Log10D")==0 ||
4011         strcmp(opType,"ModD")==0 ||
4012         strcmp(opType,"ModF")==0 ||
4013         strcmp(opType,"ModI")==0 ||
4014         strcmp(opType,"PowD")==0 ||
4015         strcmp(opType,"SinD")==0 ||
4016         strcmp(opType,"SqrtD")==0 ||
4017         strcmp(opType,"TanD")==0 ||
4018         strcmp(opType,"ConvD2F")==0 ||
4019         strcmp(opType,"ConvD2I")==0 ||
4020         strcmp(opType,"ConvD2L")==0 ||
4021         strcmp(opType,"ConvF2D")==0 ||
4022         strcmp(opType,"ConvF2I")==0 ||
4023         strcmp(opType,"ConvF2L")==0 ||
4024         strcmp(opType,"ConvI2D")==0 ||
4025         strcmp(opType,"ConvI2F")==0 ||
4026         strcmp(opType,"ConvI2L")==0 ||
4027         strcmp(opType,"ConvL2D")==0 ||
4028         strcmp(opType,"ConvL2F")==0 ||
4029         strcmp(opType,"ConvL2I")==0 ||
4030         strcmp(opType,"DecodeN")==0 ||
4031         strcmp(opType,"EncodeP")==0 ||
4032         strcmp(opType,"EncodePKlass")==0 ||
4033         strcmp(opType,"DecodeNKlass")==0 ||
4034         strcmp(opType,"RoundDouble")==0 ||
4035         strcmp(opType,"RoundFloat")==0 ||
4036         strcmp(opType,"ReverseBytesI")==0 ||
4037         strcmp(opType,"ReverseBytesL")==0 ||
4038         strcmp(opType,"ReverseBytesUS")==0 ||
4039         strcmp(opType,"ReverseBytesS")==0 ||
4040         strcmp(opType,"ReplicateB")==0 ||
4041         strcmp(opType,"ReplicateS")==0 ||
4042         strcmp(opType,"ReplicateI")==0 ||
4043         strcmp(opType,"ReplicateL")==0 ||
4044         strcmp(opType,"ReplicateF")==0 ||
4045         strcmp(opType,"ReplicateD")==0 ||
4046         strcmp(opType,"AddReductionVI")==0 ||
4047         strcmp(opType,"AddReductionVL")==0 ||
4048         strcmp(opType,"AddReductionVF")==0 ||
4049         strcmp(opType,"AddReductionVD")==0 ||
4050         strcmp(opType,"MulReductionVI")==0 ||
4051         strcmp(opType,"MulReductionVL")==0 ||
4052         strcmp(opType,"MulReductionVF")==0 ||
4053         strcmp(opType,"MulReductionVD")==0 ||
4054         0 /* 0 to line up columns nicely */ )
4055       return 1;
4056   }
4057   return 0;
4058 }
4059 
4060 bool MatchRule::is_ideal_if() const {
4061   if( !_opType ) return false;
4062   return
4063     !strcmp(_opType,"If"            ) ||
4064     !strcmp(_opType,"CountedLoopEnd");
4065 }
4066 
4067 bool MatchRule::is_ideal_fastlock() const {
4068   if ( _opType && (strcmp(_opType,"Set") == 0) && _rChild ) {
4069     return (strcmp(_rChild->_opType,"FastLock") == 0);
4070   }
4071   return false;
4072 }
4073 
4074 bool MatchRule::is_ideal_membar() const {
4075   if( !_opType ) return false;
4076   return
4077     !strcmp(_opType,"MemBarAcquire") ||
4078     !strcmp(_opType,"MemBarRelease") ||
4079     !strcmp(_opType,"MemBarAcquireLock") ||
4080     !strcmp(_opType,"MemBarReleaseLock") ||
4081     !strcmp(_opType,"LoadFence" ) ||
4082     !strcmp(_opType,"StoreFence") ||
4083     !strcmp(_opType,"MemBarVolatile") ||
4084     !strcmp(_opType,"MemBarCPUOrder") ||
4085     !strcmp(_opType,"MemBarStoreStore");
4086 }
4087 
4088 bool MatchRule::is_ideal_loadPC() const {
4089   if ( _opType && (strcmp(_opType,"Set") == 0) && _rChild ) {
4090     return (strcmp(_rChild->_opType,"LoadPC") == 0);
4091   }
4092   return false;
4093 }
4094 
4095 bool MatchRule::is_ideal_box() const {
4096   if ( _opType && (strcmp(_opType,"Set") == 0) && _rChild ) {
4097     return (strcmp(_rChild->_opType,"Box") == 0);
4098   }
4099   return false;
4100 }
4101 
4102 bool MatchRule::is_ideal_goto() const {
4103   bool   ideal_goto = false;
4104 
4105   if( _opType && (strcmp(_opType,"Goto") == 0) ) {
4106     ideal_goto = true;
4107   }
4108   return ideal_goto;
4109 }
4110 
4111 bool MatchRule::is_ideal_jump() const {
4112   if( _opType ) {
4113     if( !strcmp(_opType,"Jump") )
4114       return true;
4115   }
4116   return false;
4117 }
4118 
4119 bool MatchRule::is_ideal_bool() const {
4120   if( _opType ) {
4121     if( !strcmp(_opType,"Bool") )
4122       return true;
4123   }
4124   return false;
4125 }
4126 
4127 
4128 Form::DataType MatchRule::is_ideal_load() const {
4129   Form::DataType ideal_load = Form::none;
4130 
4131   if ( _opType && (strcmp(_opType,"Set") == 0) && _rChild ) {
4132     const char *opType = _rChild->_opType;
4133     ideal_load = is_load_from_memory(opType);
4134   }
4135 
4136   return ideal_load;
4137 }
4138 
4139 bool MatchRule::is_vector() const {
4140   static const char *vector_list[] = {
4141     "AddVB","AddVS","AddVI","AddVL","AddVF","AddVD",
4142     "SubVB","SubVS","SubVI","SubVL","SubVF","SubVD",
4143     "MulVS","MulVI","MulVL","MulVF","MulVD",
4144     "DivVF","DivVD",
4145     "AbsVF","AbsVD",
4146     "NegVF","NegVD",
4147     "SqrtVD",
4148     "AndV" ,"XorV" ,"OrV",
4149     "AddReductionVI", "AddReductionVL",
4150     "AddReductionVF", "AddReductionVD",
4151     "MulReductionVI", "MulReductionVL",
4152     "MulReductionVF", "MulReductionVD",
4153     "LShiftCntV","RShiftCntV",
4154     "LShiftVB","LShiftVS","LShiftVI","LShiftVL",
4155     "RShiftVB","RShiftVS","RShiftVI","RShiftVL",
4156     "URShiftVB","URShiftVS","URShiftVI","URShiftVL",
4157     "ReplicateB","ReplicateS","ReplicateI","ReplicateL","ReplicateF","ReplicateD",
4158     "LoadVector","StoreVector",
4159     // Next are not supported currently.
4160     "PackB","PackS","PackI","PackL","PackF","PackD","Pack2L","Pack2D",
4161     "ExtractB","ExtractUB","ExtractC","ExtractS","ExtractI","ExtractL","ExtractF","ExtractD"
4162   };
4163   int cnt = sizeof(vector_list)/sizeof(char*);
4164   if (_rChild) {
4165     const char  *opType = _rChild->_opType;
4166     for (int i=0; i<cnt; i++)
4167       if (strcmp(opType,vector_list[i]) == 0)
4168         return true;
4169   }
4170   return false;
4171 }
4172 
4173 
4174 bool MatchRule::skip_antidep_check() const {
4175   // Some loads operate on what is effectively immutable memory so we
4176   // should skip the anti dep computations.  For some of these nodes
4177   // the rewritable field keeps the anti dep logic from triggering but
4178   // for certain kinds of LoadKlass it does not since they are
4179   // actually reading memory which could be rewritten by the runtime,
4180   // though never by generated code.  This disables it uniformly for
4181   // the nodes that behave like this: LoadKlass, LoadNKlass and
4182   // LoadRange.
4183   if ( _opType && (strcmp(_opType,"Set") == 0) && _rChild ) {
4184     const char *opType = _rChild->_opType;
4185     if (strcmp("LoadKlass", opType) == 0 ||
4186         strcmp("LoadNKlass", opType) == 0 ||
4187         strcmp("LoadRange", opType) == 0) {
4188       return true;
4189     }
4190   }
4191 
4192   return false;
4193 }
4194 
4195 
4196 Form::DataType MatchRule::is_ideal_store() const {
4197   Form::DataType ideal_store = Form::none;
4198 
4199   if ( _opType && (strcmp(_opType,"Set") == 0) && _rChild ) {
4200     const char *opType = _rChild->_opType;
4201     ideal_store = is_store_to_memory(opType);
4202   }
4203 
4204   return ideal_store;
4205 }
4206 
4207 
4208 void MatchRule::dump() {
4209   output(stderr);
4210 }
4211 
4212 // Write just one line.
4213 void MatchRule::output_short(FILE *fp) {
4214   fprintf(fp,"MatchRule: ( %s",_name);
4215   if (_lChild) _lChild->output(fp);
4216   if (_rChild) _rChild->output(fp);
4217   fprintf(fp," )");
4218 }
4219 
4220 void MatchRule::output(FILE *fp) {
4221   output_short(fp);
4222   fprintf(fp,"\n   nesting depth = %d\n", _depth);
4223   if (_result) fprintf(fp,"   Result Type = %s", _result);
4224   fprintf(fp,"\n");
4225 }
4226 
4227 //------------------------------Attribute--------------------------------------
4228 Attribute::Attribute(char *id, char* val, int type)
4229   : _ident(id), _val(val), _atype(type) {
4230 }
4231 Attribute::~Attribute() {
4232 }
4233 
4234 int Attribute::int_val(ArchDesc &ad) {
4235   // Make sure it is an integer constant:
4236   int result = 0;
4237   if (!_val || !ADLParser::is_int_token(_val, result)) {
4238     ad.syntax_err(0, "Attribute %s must have an integer value: %s",
4239                   _ident, _val ? _val : "");
4240   }
4241   return result;
4242 }
4243 
4244 void Attribute::dump() {
4245   output(stderr);
4246 } // Debug printer
4247 
4248 // Write to output files
4249 void Attribute::output(FILE *fp) {
4250   fprintf(fp,"Attribute: %s  %s\n", (_ident?_ident:""), (_val?_val:""));
4251 }
4252 
4253 //------------------------------FormatRule----------------------------------
4254 FormatRule::FormatRule(char *temp)
4255   : _temp(temp) {
4256 }
4257 FormatRule::~FormatRule() {
4258 }
4259 
4260 void FormatRule::dump() {
4261   output(stderr);
4262 }
4263 
4264 // Write to output files
4265 void FormatRule::output(FILE *fp) {
4266   fprintf(fp,"\nFormat Rule: \n%s", (_temp?_temp:""));
4267   fprintf(fp,"\n");
4268 }