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

4012         strcmp(opType,"DivD")==0 ||
4013         strcmp(opType,"DivF")==0 ||
4014         strcmp(opType,"DivI")==0 ||
4015         strcmp(opType,"Log10D")==0 ||
4016         strcmp(opType,"ModD")==0 ||
4017         strcmp(opType,"ModF")==0 ||
4018         strcmp(opType,"ModI")==0 ||
4019         strcmp(opType,"PowD")==0 ||

4020         strcmp(opType,"SqrtD")==0 ||
4021         strcmp(opType,"TanD")==0 ||
4022         strcmp(opType,"ConvD2F")==0 ||
4023         strcmp(opType,"ConvD2I")==0 ||
4024         strcmp(opType,"ConvD2L")==0 ||
4025         strcmp(opType,"ConvF2D")==0 ||
4026         strcmp(opType,"ConvF2I")==0 ||
4027         strcmp(opType,"ConvF2L")==0 ||
4028         strcmp(opType,"ConvI2D")==0 ||
4029         strcmp(opType,"ConvI2F")==0 ||
4030         strcmp(opType,"ConvI2L")==0 ||
4031         strcmp(opType,"ConvL2D")==0 ||
4032         strcmp(opType,"ConvL2F")==0 ||
4033         strcmp(opType,"ConvL2I")==0 ||
4034         strcmp(opType,"DecodeN")==0 ||
4035         strcmp(opType,"EncodeP")==0 ||
4036         strcmp(opType,"EncodePKlass")==0 ||
4037         strcmp(opType,"DecodeNKlass")==0 ||
4038         strcmp(opType,"RoundDouble")==0 ||
4039         strcmp(opType,"RoundFloat")==0 ||
4040         strcmp(opType,"ReverseBytesI")==0 ||
4041         strcmp(opType,"ReverseBytesL")==0 ||
4042         strcmp(opType,"ReverseBytesUS")==0 ||
4043         strcmp(opType,"ReverseBytesS")==0 ||
4044         strcmp(opType,"ReplicateB")==0 ||
4045         strcmp(opType,"ReplicateS")==0 ||
4046         strcmp(opType,"ReplicateI")==0 ||
4047         strcmp(opType,"ReplicateL")==0 ||
4048         strcmp(opType,"ReplicateF")==0 ||
4049         strcmp(opType,"ReplicateD")==0 ||
4050         strcmp(opType,"AddReductionVI")==0 ||
4051         strcmp(opType,"AddReductionVL")==0 ||
4052         strcmp(opType,"AddReductionVF")==0 ||
4053         strcmp(opType,"AddReductionVD")==0 ||
4054         strcmp(opType,"MulReductionVI")==0 ||
4055         strcmp(opType,"MulReductionVL")==0 ||
4056         strcmp(opType,"MulReductionVF")==0 ||
4057         strcmp(opType,"MulReductionVD")==0 ||
4058         0 /* 0 to line up columns nicely */ )
4059       return 1;
4060   }
4061   return 0;
4062 }
4063 
4064 bool MatchRule::is_ideal_if() const {
4065   if( !_opType ) return false;
4066   return
4067     !strcmp(_opType,"If"            ) ||
4068     !strcmp(_opType,"CountedLoopEnd");
4069 }
4070 
4071 bool MatchRule::is_ideal_fastlock() const {
4072   if ( _opType && (strcmp(_opType,"Set") == 0) && _rChild ) {
4073     return (strcmp(_rChild->_opType,"FastLock") == 0);
4074   }
4075   return false;
4076 }
4077 
4078 bool MatchRule::is_ideal_membar() const {
4079   if( !_opType ) return false;
4080   return
4081     !strcmp(_opType,"MemBarAcquire") ||
4082     !strcmp(_opType,"MemBarRelease") ||
4083     !strcmp(_opType,"MemBarAcquireLock") ||
4084     !strcmp(_opType,"MemBarReleaseLock") ||
4085     !strcmp(_opType,"LoadFence" ) ||
4086     !strcmp(_opType,"StoreFence") ||
4087     !strcmp(_opType,"MemBarVolatile") ||
4088     !strcmp(_opType,"MemBarCPUOrder") ||
4089     !strcmp(_opType,"MemBarStoreStore");
4090 }
4091 
4092 bool MatchRule::is_ideal_loadPC() const {
4093   if ( _opType && (strcmp(_opType,"Set") == 0) && _rChild ) {
4094     return (strcmp(_rChild->_opType,"LoadPC") == 0);
4095   }
4096   return false;
4097 }
4098 
4099 bool MatchRule::is_ideal_box() const {
4100   if ( _opType && (strcmp(_opType,"Set") == 0) && _rChild ) {
4101     return (strcmp(_rChild->_opType,"Box") == 0);
4102   }
4103   return false;
4104 }
4105 
4106 bool MatchRule::is_ideal_goto() const {
4107   bool   ideal_goto = false;
4108 
4109   if( _opType && (strcmp(_opType,"Goto") == 0) ) {
4110     ideal_goto = true;
4111   }
4112   return ideal_goto;
4113 }
4114 
4115 bool MatchRule::is_ideal_jump() const {
4116   if( _opType ) {
4117     if( !strcmp(_opType,"Jump") )
4118       return true;
4119   }
4120   return false;
4121 }
4122 
4123 bool MatchRule::is_ideal_bool() const {
4124   if( _opType ) {
4125     if( !strcmp(_opType,"Bool") )
4126       return true;
4127   }
4128   return false;
4129 }
4130 
4131 
4132 Form::DataType MatchRule::is_ideal_load() const {
4133   Form::DataType ideal_load = Form::none;
4134 
4135   if ( _opType && (strcmp(_opType,"Set") == 0) && _rChild ) {
4136     const char *opType = _rChild->_opType;
4137     ideal_load = is_load_from_memory(opType);
4138   }
4139 
4140   return ideal_load;
4141 }
4142 
4143 bool MatchRule::is_vector() const {
4144   static const char *vector_list[] = {
4145     "AddVB","AddVS","AddVI","AddVL","AddVF","AddVD",
4146     "SubVB","SubVS","SubVI","SubVL","SubVF","SubVD",
4147     "MulVS","MulVI","MulVL","MulVF","MulVD",
4148     "CMoveVD",
4149     "DivVF","DivVD",
4150     "AbsVF","AbsVD",
4151     "NegVF","NegVD",
4152     "SqrtVD",
4153     "AndV" ,"XorV" ,"OrV",
4154     "AddReductionVI", "AddReductionVL",
4155     "AddReductionVF", "AddReductionVD",
4156     "MulReductionVI", "MulReductionVL",
4157     "MulReductionVF", "MulReductionVD",
4158     "LShiftCntV","RShiftCntV",
4159     "LShiftVB","LShiftVS","LShiftVI","LShiftVL",
4160     "RShiftVB","RShiftVS","RShiftVI","RShiftVL",
4161     "URShiftVB","URShiftVS","URShiftVI","URShiftVL",
4162     "ReplicateB","ReplicateS","ReplicateI","ReplicateL","ReplicateF","ReplicateD",
4163     "LoadVector","StoreVector",
4164     // Next are not supported currently.
4165     "PackB","PackS","PackI","PackL","PackF","PackD","Pack2L","Pack2D",
4166     "ExtractB","ExtractUB","ExtractC","ExtractS","ExtractI","ExtractL","ExtractF","ExtractD"
4167   };
4168   int cnt = sizeof(vector_list)/sizeof(char*);
4169   if (_rChild) {
4170     const char  *opType = _rChild->_opType;
4171     for (int i=0; i<cnt; i++)
4172       if (strcmp(opType,vector_list[i]) == 0)
4173         return true;
4174   }
4175   return false;
4176 }
4177 
4178 
4179 bool MatchRule::skip_antidep_check() const {
4180   // Some loads operate on what is effectively immutable memory so we
4181   // should skip the anti dep computations.  For some of these nodes
4182   // the rewritable field keeps the anti dep logic from triggering but
4183   // for certain kinds of LoadKlass it does not since they are
4184   // actually reading memory which could be rewritten by the runtime,
4185   // though never by generated code.  This disables it uniformly for
4186   // the nodes that behave like this: LoadKlass, LoadNKlass and
4187   // LoadRange.
4188   if ( _opType && (strcmp(_opType,"Set") == 0) && _rChild ) {
4189     const char *opType = _rChild->_opType;
4190     if (strcmp("LoadKlass", opType) == 0 ||
4191         strcmp("LoadNKlass", opType) == 0 ||
4192         strcmp("LoadRange", opType) == 0) {
4193       return true;
4194     }
4195   }
4196 
4197   return false;
4198 }
4199 
4200 
4201 Form::DataType MatchRule::is_ideal_store() const {
4202   Form::DataType ideal_store = Form::none;
4203 
4204   if ( _opType && (strcmp(_opType,"Set") == 0) && _rChild ) {
4205     const char *opType = _rChild->_opType;
4206     ideal_store = is_store_to_memory(opType);
4207   }
4208 
4209   return ideal_store;
4210 }
4211 
4212 
4213 void MatchRule::dump() {
4214   output(stderr);
4215 }
4216 
4217 // Write just one line.
4218 void MatchRule::output_short(FILE *fp) {
4219   fprintf(fp,"MatchRule: ( %s",_name);
4220   if (_lChild) _lChild->output(fp);
4221   if (_rChild) _rChild->output(fp);
4222   fprintf(fp," )");
4223 }
4224 
4225 void MatchRule::output(FILE *fp) {
4226   output_short(fp);
4227   fprintf(fp,"\n   nesting depth = %d\n", _depth);
4228   if (_result) fprintf(fp,"   Result Type = %s", _result);
4229   fprintf(fp,"\n");
4230 }
4231 
4232 //------------------------------Attribute--------------------------------------
4233 Attribute::Attribute(char *id, char* val, int type)
4234   : _ident(id), _val(val), _atype(type) {
4235 }
4236 Attribute::~Attribute() {
4237 }
4238 
4239 int Attribute::int_val(ArchDesc &ad) {
4240   // Make sure it is an integer constant:
4241   int result = 0;
4242   if (!_val || !ADLParser::is_int_token(_val, result)) {
4243     ad.syntax_err(0, "Attribute %s must have an integer value: %s",
4244                   _ident, _val ? _val : "");
4245   }
4246   return result;
4247 }
4248 
4249 void Attribute::dump() {
4250   output(stderr);
4251 } // Debug printer
4252 
4253 // Write to output files
4254 void Attribute::output(FILE *fp) {
4255   fprintf(fp,"Attribute: %s  %s\n", (_ident?_ident:""), (_val?_val:""));
4256 }
4257 
4258 //------------------------------FormatRule----------------------------------
4259 FormatRule::FormatRule(char *temp)
4260   : _temp(temp) {
4261 }
4262 FormatRule::~FormatRule() {
4263 }
4264 
4265 void FormatRule::dump() {
4266   output(stderr);
4267 }
4268 
4269 // Write to output files
4270 void FormatRule::output(FILE *fp) {
4271   fprintf(fp,"\nFormat Rule: \n%s", (_temp?_temp:""));
4272   fprintf(fp,"\n");
4273 }
--- EOF ---