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