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