Mercurial > jdk8-mips64-public > hotspot / file revision

 /*

  * Copyright (c) 1998, 2014, Oracle and/or its affiliates. All rights reserved.

  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

  *

  * This code is free software; you can redistribute it and/or modify it

  * under the terms of the GNU General Public License version 2 only, as

  * published by the Free Software Foundation.

  *

  * This code is distributed in the hope that it will be useful, but WITHOUT

  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

  * version 2 for more details (a copy is included in the LICENSE file that

  * accompanied this code).

  *

  * You should have received a copy of the GNU General Public License version

  * 2 along with this work; if not, write to the Free Software Foundation,

  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

  *

  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

  * or visit www.oracle.com if you need additional information or have any

  * questions.

  *

  */

 // FORMS.CPP - Definitions for ADL Parser Forms Classes

 #include "adlc.hpp"

 //==============================Instructions===================================

 //------------------------------InstructForm-----------------------------------

 InstructForm::InstructForm(const char *id, bool ideal_only)

   : _ident(id), _ideal_only(ideal_only),

     _localNames(cmpstr, hashstr, Form::arena),

     _effects(cmpstr, hashstr, Form::arena),

     _is_mach_constant(false),

     _needs_constant_base(false),

     _has_call(false)

 {

       _ftype = Form::INS;

       _matrule              = NULL;

       _insencode            = NULL;

       _constant             = NULL;

       _is_postalloc_expand  = false;

       _opcode               = NULL;

       _size                 = NULL;

       _attribs              = NULL;

       _predicate            = NULL;

       _exprule              = NULL;

       _rewrule              = NULL;

       _format               = NULL;

       _peephole             = NULL;

       _ins_pipe             = NULL;

       _uniq_idx             = NULL;

       _num_uniq             = 0;

       _cisc_spill_operand   = Not_cisc_spillable;// Which operand may cisc-spill

       _cisc_spill_alternate = NULL;            // possible cisc replacement

       _cisc_reg_mask_name   = NULL;

       _is_cisc_alternate    = false;

       _is_short_branch      = false;

       _short_branch_form    = NULL;

       _alignment            = 1;

 }

 InstructForm::InstructForm(const char *id, InstructForm *instr, MatchRule *rule)

   : _ident(id), _ideal_only(false),

     _localNames(instr->_localNames),

     _effects(instr->_effects),

     _is_mach_constant(false),

     _needs_constant_base(false),

     _has_call(false)

 {

       _ftype = Form::INS;

       _matrule               = rule;

       _insencode             = instr->_insencode;

       _constant              = instr->_constant;

       _is_postalloc_expand   = instr->_is_postalloc_expand;

       _opcode                = instr->_opcode;

       _size                  = instr->_size;

       _attribs               = instr->_attribs;

       _predicate             = instr->_predicate;

       _exprule               = instr->_exprule;

       _rewrule               = instr->_rewrule;

       _format                = instr->_format;

       _peephole              = instr->_peephole;

       _ins_pipe              = instr->_ins_pipe;

       _uniq_idx              = instr->_uniq_idx;

       _num_uniq              = instr->_num_uniq;

       _cisc_spill_operand    = Not_cisc_spillable; // Which operand may cisc-spill

       _cisc_spill_alternate  = NULL;               // possible cisc replacement

       _cisc_reg_mask_name    = NULL;

       _is_cisc_alternate     = false;

       _is_short_branch       = false;

       _short_branch_form     = NULL;

       _alignment             = 1;

      // Copy parameters

      const char *name;

      instr->_parameters.reset();

      for (; (name = instr->_parameters.iter()) != NULL;)

        _parameters.addName(name);

 }

 InstructForm::~InstructForm() {

 }

 InstructForm *InstructForm::is_instruction() const {

   return (InstructForm*)this;

 }

 bool InstructForm::ideal_only() const {

   return _ideal_only;

 }

 bool InstructForm::sets_result() const {

   return (_matrule != NULL && _matrule->sets_result());

 }

 bool InstructForm::needs_projections() {

   _components.reset();

   for( Component *comp; (comp = _components.iter()) != NULL; ) {

     if (comp->isa(Component::KILL)) {

       return true;

     }

   }

   return false;

 }

 bool InstructForm::has_temps() {

   if (_matrule) {

     // Examine each component to see if it is a TEMP

     _components.reset();

     // Skip the first component, if already handled as (SET dst (...))

     Component *comp = NULL;

     if (sets_result())  comp = _components.iter();

     while ((comp = _components.iter()) != NULL) {

       if (comp->isa(Component::TEMP)) {

         return true;

       }

     }

   }

   return false;

 }

 uint InstructForm::num_defs_or_kills() {

   uint   defs_or_kills = 0;

   _components.reset();

   for( Component *comp; (comp = _components.iter()) != NULL; ) {

     if( comp->isa(Component::DEF) || comp->isa(Component::KILL) ) {

       ++defs_or_kills;

     }

   }

   return  defs_or_kills;

 }

 // This instruction has an expand rule?

 bool InstructForm::expands() const {

   return ( _exprule != NULL );

 }

 // This instruction has a late expand rule?

 bool InstructForm::postalloc_expands() const {

   return _is_postalloc_expand;

 }

 // This instruction has a peephole rule?

 Peephole *InstructForm::peepholes() const {

   return _peephole;

 }

 // This instruction has a peephole rule?

 void InstructForm::append_peephole(Peephole *peephole) {

   if( _peephole == NULL ) {

     _peephole = peephole;

   } else {

     _peephole->append_peephole(peephole);

   }

 }

 // ideal opcode enumeration

 const char *InstructForm::ideal_Opcode( FormDict &globalNames )  const {

   if( !_matrule ) return "Node"; // Something weird

   // Chain rules do not really have ideal Opcodes; use their source

   // operand ideal Opcode instead.

   if( is_simple_chain_rule(globalNames) ) {

     const char *src = _matrule->_rChild->_opType;

     OperandForm *src_op = globalNames[src]->is_operand();

     assert( src_op, "Not operand class of chain rule" );

     if( !src_op->_matrule ) return "Node";

     return src_op->_matrule->_opType;

   }

   // Operand chain rules do not really have ideal Opcodes

   if( _matrule->is_chain_rule(globalNames) )

     return "Node";

   return strcmp(_matrule->_opType,"Set")

     ? _matrule->_opType

     : _matrule->_rChild->_opType;

 }

 // Recursive check on all operands' match rules in my match rule

 bool InstructForm::is_pinned(FormDict &globals) {

   if ( ! _matrule)  return false;

   int  index   = 0;

   if (_matrule->find_type("Goto",          index)) return true;

   if (_matrule->find_type("If",            index)) return true;

   if (_matrule->find_type("CountedLoopEnd",index)) return true;

   if (_matrule->find_type("Return",        index)) return true;

   if (_matrule->find_type("Rethrow",       index)) return true;

   if (_matrule->find_type("TailCall",      index)) return true;

   if (_matrule->find_type("TailJump",      index)) return true;

   if (_matrule->find_type("Halt",          index)) return true;

   if (_matrule->find_type("Jump",          index)) return true;

   return is_parm(globals);

 }

 // Recursive check on all operands' match rules in my match rule

 bool InstructForm::is_projection(FormDict &globals) {

   if ( ! _matrule)  return false;

   int  index   = 0;

   if (_matrule->find_type("Goto",    index)) return true;

   if (_matrule->find_type("Return",  index)) return true;

   if (_matrule->find_type("Rethrow", index)) return true;

   if (_matrule->find_type("TailCall",index)) return true;

   if (_matrule->find_type("TailJump",index)) return true;

   if (_matrule->find_type("Halt",    index)) return true;

   return false;

 }

 // Recursive check on all operands' match rules in my match rule

 bool InstructForm::is_parm(FormDict &globals) {

   if ( ! _matrule)  return false;

   int  index   = 0;

   if (_matrule->find_type("Parm",index)) return true;

   return false;

 }

 bool InstructForm::is_ideal_negD() const {

   return (_matrule && _matrule->_rChild && strcmp(_matrule->_rChild->_opType, "NegD") == 0);

 }

 // Return 'true' if this instruction matches an ideal 'Copy*' node

 int InstructForm::is_ideal_copy() const {

   return _matrule ? _matrule->is_ideal_copy() : 0;

 }

 // Return 'true' if this instruction is too complex to rematerialize.

 int InstructForm::is_expensive() const {

   // We can prove it is cheap if it has an empty encoding.

   // This helps with platform-specific nops like ThreadLocal and RoundFloat.

   if (is_empty_encoding())

     return 0;

   if (is_tls_instruction())

     return 1;

   if (_matrule == NULL)  return 0;

   return _matrule->is_expensive();

 }

 // Has an empty encoding if _size is a constant zero or there

 // are no ins_encode tokens.

 int InstructForm::is_empty_encoding() const {

   if (_insencode != NULL) {

     _insencode->reset();

     if (_insencode->encode_class_iter() == NULL) {

       return 1;

     }

   }

   if (_size != NULL && strcmp(_size, "0") == 0) {

     return 1;

   }

   return 0;

 }

 int InstructForm::is_tls_instruction() const {

   if (_ident != NULL &&

       ( ! strcmp( _ident,"tlsLoadP") ||

         ! strncmp(_ident,"tlsLoadP_",9)) ) {

     return 1;

   }

   if (_matrule != NULL && _insencode != NULL) {

     const char* opType = _matrule->_opType;

     if (strcmp(opType, "Set")==0)

       opType = _matrule->_rChild->_opType;

     if (strcmp(opType,"ThreadLocal")==0) {

       fprintf(stderr, "Warning: ThreadLocal instruction %s should be named 'tlsLoadP_*'\n",

               (_ident == NULL ? "NULL" : _ident));

       return 1;

     }

   }

   return 0;

 }

 // Return 'true' if this instruction matches an ideal 'If' node

 bool InstructForm::is_ideal_if() const {

   if( _matrule == NULL ) return false;

   return _matrule->is_ideal_if();

 }

 // Return 'true' if this instruction matches an ideal 'FastLock' node

 bool InstructForm::is_ideal_fastlock() const {

   if( _matrule == NULL ) return false;

   return _matrule->is_ideal_fastlock();

 }

 // Return 'true' if this instruction matches an ideal 'MemBarXXX' node

 bool InstructForm::is_ideal_membar() const {

   if( _matrule == NULL ) return false;

   return _matrule->is_ideal_membar();

 }

 // Return 'true' if this instruction matches an ideal 'LoadPC' node

 bool InstructForm::is_ideal_loadPC() const {

   if( _matrule == NULL ) return false;

   return _matrule->is_ideal_loadPC();

 }

 // Return 'true' if this instruction matches an ideal 'Box' node

 bool InstructForm::is_ideal_box() const {

   if( _matrule == NULL ) return false;

   return _matrule->is_ideal_box();

 }

 // Return 'true' if this instruction matches an ideal 'Goto' node

 bool InstructForm::is_ideal_goto() const {

   if( _matrule == NULL ) return false;

   return _matrule->is_ideal_goto();

 }

 // Return 'true' if this instruction matches an ideal 'Jump' node

 bool InstructForm::is_ideal_jump() const {

   if( _matrule == NULL ) return false;

   return _matrule->is_ideal_jump();

 }

 // Return 'true' if instruction matches ideal 'If' | 'Goto' | 'CountedLoopEnd'

 bool InstructForm::is_ideal_branch() const {

   if( _matrule == NULL ) return false;

   return _matrule->is_ideal_if() || _matrule->is_ideal_goto();

 }

 // Return 'true' if this instruction matches an ideal 'Return' node

 bool InstructForm::is_ideal_return() const {

   if( _matrule == NULL ) return false;

   // Check MatchRule to see if the first entry is the ideal "Return" node

   int  index   = 0;

   if (_matrule->find_type("Return",index)) return true;

   if (_matrule->find_type("Rethrow",index)) return true;

   if (_matrule->find_type("TailCall",index)) return true;

   if (_matrule->find_type("TailJump",index)) return true;

   return false;

 }

 // Return 'true' if this instruction matches an ideal 'Halt' node

 bool InstructForm::is_ideal_halt() const {

   int  index   = 0;

   return _matrule && _matrule->find_type("Halt",index);

 }

 // Return 'true' if this instruction matches an ideal 'SafePoint' node

 bool InstructForm::is_ideal_safepoint() const {

   int  index   = 0;

   return _matrule && _matrule->find_type("SafePoint",index);

 }

 // Return 'true' if this instruction matches an ideal 'Nop' node

 bool InstructForm::is_ideal_nop() const {

   return _ident && _ident[0] == 'N' && _ident[1] == 'o' && _ident[2] == 'p' && _ident[3] == '_';

 }

 bool InstructForm::is_ideal_control() const {

   if ( ! _matrule)  return false;

   return is_ideal_return() || is_ideal_branch() || _matrule->is_ideal_jump() || is_ideal_halt();

 }

 // Return 'true' if this instruction matches an ideal 'Call' node

 Form::CallType InstructForm::is_ideal_call() const {

   if( _matrule == NULL ) return Form::invalid_type;

   // Check MatchRule to see if the first entry is the ideal "Call" node

   int  idx   = 0;

   if(_matrule->find_type("CallStaticJava",idx))   return Form::JAVA_STATIC;

   idx = 0;

   if(_matrule->find_type("Lock",idx))             return Form::JAVA_STATIC;

   idx = 0;

   if(_matrule->find_type("Unlock",idx))           return Form::JAVA_STATIC;

   idx = 0;

   if(_matrule->find_type("CallDynamicJava",idx))  return Form::JAVA_DYNAMIC;

   idx = 0;

   if(_matrule->find_type("CallRuntime",idx))      return Form::JAVA_RUNTIME;

   idx = 0;

   if(_matrule->find_type("CallLeaf",idx))         return Form::JAVA_LEAF;

   idx = 0;

   if(_matrule->find_type("CallLeafNoFP",idx))     return Form::JAVA_LEAF;

   idx = 0;

   return Form::invalid_type;

 }

 // Return 'true' if this instruction matches an ideal 'Load?' node

 Form::DataType InstructForm::is_ideal_load() const {

   if( _matrule == NULL ) return Form::none;

   return  _matrule->is_ideal_load();

 }

 // Return 'true' if this instruction matches an ideal 'LoadKlass' node

 bool InstructForm::skip_antidep_check() const {

   if( _matrule == NULL ) return false;

   return  _matrule->skip_antidep_check();

 }

 // Return 'true' if this instruction matches an ideal 'Load?' node

 Form::DataType InstructForm::is_ideal_store() const {

   if( _matrule == NULL ) return Form::none;

   return  _matrule->is_ideal_store();

 }

 // Return 'true' if this instruction matches an ideal vector node

 bool InstructForm::is_vector() const {

   if( _matrule == NULL ) return false;

   return _matrule->is_vector();

 }

 // Return the input register that must match the output register

 // If this is not required, return 0

 uint InstructForm::two_address(FormDict &globals) {

   uint  matching_input = 0;

   if(_components.count() == 0) return 0;

   _components.reset();

   Component *comp = _components.iter();

   // Check if there is a DEF

   if( comp->isa(Component::DEF) ) {

     // Check that this is a register

     const char  *def_type = comp->_type;

     const Form  *form     = globals[def_type];

     OperandForm *op       = form->is_operand();

     if( op ) {

       if( op->constrained_reg_class() != NULL &&

           op->interface_type(globals) == Form::register_interface ) {

         // Remember the local name for equality test later

         const char *def_name = comp->_name;

         // Check if a component has the same name and is a USE

         do {

           if( comp->isa(Component::USE) && strcmp(comp->_name,def_name)==0 ) {

             return operand_position_format(def_name);

           }

         } while( (comp = _components.iter()) != NULL);

       }

     }

   }

   return 0;

 }

 // when chaining a constant to an instruction, returns 'true' and sets opType

 Form::DataType InstructForm::is_chain_of_constant(FormDict &globals) {

   const char *dummy  = NULL;

   const char *dummy2 = NULL;

   return is_chain_of_constant(globals, dummy, dummy2);

 }

 Form::DataType InstructForm::is_chain_of_constant(FormDict &globals,

                 const char * &opTypeParam) {

   const char *result = NULL;

   return is_chain_of_constant(globals, opTypeParam, result);

 }

 Form::DataType InstructForm::is_chain_of_constant(FormDict &globals,

                 const char * &opTypeParam, const char * &resultParam) {

   Form::DataType  data_type = Form::none;

   if ( ! _matrule)  return data_type;

   // !!!!!

   // The source of the chain rule is 'position = 1'

   uint         position = 1;

   const char  *result   = NULL;

   const char  *name     = NULL;

   const char  *opType   = NULL;

   // Here base_operand is looking for an ideal type to be returned (opType).

   if ( _matrule->is_chain_rule(globals)

        && _matrule->base_operand(position, globals, result, name, opType) ) {

     data_type = ideal_to_const_type(opType);

     // if it isn't an ideal constant type, just return

     if ( data_type == Form::none ) return data_type;

     // Ideal constant types also adjust the opType parameter.

     resultParam = result;

     opTypeParam = opType;

     return data_type;

   }

   return data_type;

 }

 // Check if a simple chain rule

 bool InstructForm::is_simple_chain_rule(FormDict &globals) const {

   if( _matrule && _matrule->sets_result()

       && _matrule->_rChild->_lChild == NULL

       && globals[_matrule->_rChild->_opType]

       && globals[_matrule->_rChild->_opType]->is_opclass() ) {

     return true;

   }

   return false;

 }

 // check for structural rematerialization

 bool InstructForm::rematerialize(FormDict &globals, RegisterForm *registers ) {

   bool   rematerialize = false;

   Form::DataType data_type = is_chain_of_constant(globals);

   if( data_type != Form::none )

     rematerialize = true;

   // Constants

   if( _components.count() == 1 && _components[0]->is(Component::USE_DEF) )

     rematerialize = true;

   // Pseudo-constants (values easily available to the runtime)

   if (is_empty_encoding() && is_tls_instruction())

     rematerialize = true;

   // 1-input, 1-output, such as copies or increments.

   if( _components.count() == 2 &&

       _components[0]->is(Component::DEF) &&

       _components[1]->isa(Component::USE) )

     rematerialize = true;

   // Check for an ideal 'Load?' and eliminate rematerialize option

   if ( is_ideal_load() != Form::none || // Ideal load?  Do not rematerialize

        is_ideal_copy() != Form::none || // Ideal copy?  Do not rematerialize

        is_expensive()  != Form::none) { // Expensive?   Do not rematerialize

     rematerialize = false;

   }

   // Always rematerialize the flags.  They are more expensive to save &

   // restore than to recompute (and possibly spill the compare's inputs).

   if( _components.count() >= 1 ) {

     Component *c = _components[0];

     const Form *form = globals[c->_type];

     OperandForm *opform = form->is_operand();

     if( opform ) {

       // Avoid the special stack_slots register classes

       const char *rc_name = opform->constrained_reg_class();

       if( rc_name ) {

         if( strcmp(rc_name,"stack_slots") ) {

           // Check for ideal_type of RegFlags

           const char *type = opform->ideal_type( globals, registers );

           if( (type != NULL) && !strcmp(type, "RegFlags") )

             rematerialize = true;

         } else

           rematerialize = false; // Do not rematerialize things target stk

       }

     }

   }

   return rematerialize;

 }

 // loads from memory, so must check for anti-dependence

 bool InstructForm::needs_anti_dependence_check(FormDict &globals) const {

   if ( skip_antidep_check() ) return false;

   // Machine independent loads must be checked for anti-dependences

   if( is_ideal_load() != Form::none )  return true;

   // !!!!! !!!!! !!!!!

   // TEMPORARY

   // if( is_simple_chain_rule(globals) )  return false;

   // String.(compareTo/equals/indexOf) and Arrays.equals use many memorys edges,

   // but writes none

   if( _matrule && _matrule->_rChild &&

       ( strcmp(_matrule->_rChild->_opType,"StrComp"    )==0 ||

         strcmp(_matrule->_rChild->_opType,"StrEquals"  )==0 ||

         strcmp(_matrule->_rChild->_opType,"StrIndexOf" )==0 ||

         strcmp(_matrule->_rChild->_opType,"AryEq"      )==0 ))

     return true;

   // Check if instruction has a USE of a memory operand class, but no defs

   bool USE_of_memory  = false;

   bool DEF_of_memory  = false;

   Component     *comp = NULL;

   ComponentList &components = (ComponentList &)_components;

   components.reset();

   while( (comp = components.iter()) != NULL ) {

     const Form  *form = globals[comp->_type];

     if( !form ) continue;

     OpClassForm *op   = form->is_opclass();

     if( !op ) continue;

     if( form->interface_type(globals) == Form::memory_interface ) {

       if( comp->isa(Component::USE) ) USE_of_memory = true;

       if( comp->isa(Component::DEF) ) {

         OperandForm *oper = form->is_operand();

         if( oper && oper->is_user_name_for_sReg() ) {

           // Stack slots are unaliased memory handled by allocator

           oper = oper;  // debug stopping point !!!!!

         } else {

           DEF_of_memory = true;

         }

       }

     }

   }

   return (USE_of_memory && !DEF_of_memory);

 }

 bool InstructForm::is_wide_memory_kill(FormDict &globals) const {

   if( _matrule == NULL ) return false;

   if( !_matrule->_opType ) return false;

   if( strcmp(_matrule->_opType,"MemBarRelease") == 0 ) return true;

   if( strcmp(_matrule->_opType,"MemBarAcquire") == 0 ) return true;

   if( strcmp(_matrule->_opType,"MemBarReleaseLock") == 0 ) return true;

   if( strcmp(_matrule->_opType,"MemBarAcquireLock") == 0 ) return true;

   if( strcmp(_matrule->_opType,"MemBarStoreStore") == 0 ) return true;

   if( strcmp(_matrule->_opType,"StoreFence") == 0 ) return true;

   if( strcmp(_matrule->_opType,"LoadFence") == 0 ) return true;

   return false;

 }

 int InstructForm::memory_operand(FormDict &globals) const {

   // Machine independent loads must be checked for anti-dependences

   // Check if instruction has a USE of a memory operand class, or a def.

   int USE_of_memory  = 0;

   int DEF_of_memory  = 0;

   const char*    last_memory_DEF = NULL; // to test DEF/USE pairing in asserts

   const char*    last_memory_USE = NULL;

   Component     *unique          = NULL;

   Component     *comp            = NULL;

   ComponentList &components      = (ComponentList &)_components;

   components.reset();

   while( (comp = components.iter()) != NULL ) {

     const Form  *form = globals[comp->_type];

     if( !form ) continue;

     OpClassForm *op   = form->is_opclass();

     if( !op ) continue;

     if( op->stack_slots_only(globals) )  continue;

     if( form->interface_type(globals) == Form::memory_interface ) {

       if( comp->isa(Component::DEF) ) {

         last_memory_DEF = comp->_name;

         DEF_of_memory++;

         unique = comp;

       } else if( comp->isa(Component::USE) ) {

         if( last_memory_DEF != NULL ) {

           assert(0 == strcmp(last_memory_DEF, comp->_name), "every memory DEF is followed by a USE of the same name");

           last_memory_DEF = NULL;

         }

         // Handles same memory being used multiple times in the case of BMI1 instructions.

         if (last_memory_USE != NULL) {

           if (strcmp(comp->_name, last_memory_USE) != 0) {

             USE_of_memory++;

           }

         } else {

           USE_of_memory++;

         }

         last_memory_USE = comp->_name;

         if (DEF_of_memory == 0)  // defs take precedence

           unique = comp;

       } else {

         assert(last_memory_DEF == NULL, "unpaired memory DEF");

       }

     }

   }

   assert(last_memory_DEF == NULL, "unpaired memory DEF");

   assert(USE_of_memory >= DEF_of_memory, "unpaired memory DEF");

   USE_of_memory -= DEF_of_memory;   // treat paired DEF/USE as one occurrence

   if( (USE_of_memory + DEF_of_memory) > 0 ) {

     if( is_simple_chain_rule(globals) ) {

       //fprintf(stderr, "Warning: chain rule is not really a memory user.\n");

       //((InstructForm*)this)->dump();

       // Preceding code prints nothing on sparc and these insns on intel:

       // leaP8 leaP32 leaPIdxOff leaPIdxScale leaPIdxScaleOff leaP8 leaP32

       // leaPIdxOff leaPIdxScale leaPIdxScaleOff

       return NO_MEMORY_OPERAND;

     }

     if( DEF_of_memory == 1 ) {

       assert(unique != NULL, "");

       if( USE_of_memory == 0 ) {

         // unique def, no uses

       } else {

         // // unique def, some uses

         // // must return bottom unless all uses match def

         // unique = NULL;

       }

     } else if( DEF_of_memory > 0 ) {

       // multiple defs, don't care about uses

       unique = NULL;

     } else if( USE_of_memory == 1) {

       // unique use, no defs

       assert(unique != NULL, "");

     } else if( USE_of_memory > 0 ) {

       // multiple uses, no defs

       unique = NULL;

     } else {

       assert(false, "bad case analysis");

     }

     // process the unique DEF or USE, if there is one

     if( unique == NULL ) {

       return MANY_MEMORY_OPERANDS;

     } else {

       int pos = components.operand_position(unique->_name);

       if( unique->isa(Component::DEF) ) {

         pos += 1;                // get corresponding USE from DEF

       }

       assert(pos >= 1, "I was just looking at it!");

       return pos;

     }

   }

   // missed the memory op??

   if( true ) {  // %%% should not be necessary

     if( is_ideal_store() != Form::none ) {

       fprintf(stderr, "Warning: cannot find memory opnd in instr.\n");

       ((InstructForm*)this)->dump();

       // pretend it has multiple defs and uses

       return MANY_MEMORY_OPERANDS;

     }

     if( is_ideal_load()  != Form::none ) {

       fprintf(stderr, "Warning: cannot find memory opnd in instr.\n");

       ((InstructForm*)this)->dump();

       // pretend it has multiple uses and no defs

       return MANY_MEMORY_OPERANDS;

     }

   }

   return NO_MEMORY_OPERAND;

 }

 // This instruction captures the machine-independent bottom_type

 // Expected use is for pointer vs oop determination for LoadP

 bool InstructForm::captures_bottom_type(FormDict &globals) const {

   if( _matrule && _matrule->_rChild &&

        (!strcmp(_matrule->_rChild->_opType,"CastPP")       ||  // new result type

         !strcmp(_matrule->_rChild->_opType,"CastX2P")      ||  // new result type

         !strcmp(_matrule->_rChild->_opType,"DecodeN")      ||

         !strcmp(_matrule->_rChild->_opType,"EncodeP")      ||

         !strcmp(_matrule->_rChild->_opType,"DecodeNKlass") ||

         !strcmp(_matrule->_rChild->_opType,"EncodePKlass") ||

         !strcmp(_matrule->_rChild->_opType,"LoadN")        ||

         !strcmp(_matrule->_rChild->_opType,"LoadNKlass")   ||

         !strcmp(_matrule->_rChild->_opType,"CreateEx")     ||  // type of exception

         !strcmp(_matrule->_rChild->_opType,"CheckCastPP")  ||

         !strcmp(_matrule->_rChild->_opType,"GetAndSetP")   ||

         !strcmp(_matrule->_rChild->_opType,"GetAndSetN")) )  return true;

   else if ( is_ideal_load() == Form::idealP )                return true;

   else if ( is_ideal_store() != Form::none  )                return true;

   if (needs_base_oop_edge(globals)) return true;

   if (is_vector()) return true;

   if (is_mach_constant()) return true;

   return  false;

 }

 // Access instr_cost attribute or return NULL.

 const char* InstructForm::cost() {

   for (Attribute* cur = _attribs; cur != NULL; cur = (Attribute*)cur->_next) {

     if( strcmp(cur->_ident,AttributeForm::_ins_cost) == 0 ) {

       return cur->_val;

     }

   }

   return NULL;

 }

 // Return count of top-level operands.

 uint InstructForm::num_opnds() {

   int  num_opnds = _components.num_operands();

   // Need special handling for matching some ideal nodes

   // i.e. Matching a return node

   /*

   if( _matrule ) {

     if( strcmp(_matrule->_opType,"Return"   )==0 ||

         strcmp(_matrule->_opType,"Halt"     )==0 )

       return 3;

   }

     */

   return num_opnds;

 }

 const char* InstructForm::opnd_ident(int idx) {

   return _components.at(idx)->_name;

 }

 const char* InstructForm::unique_opnd_ident(uint idx) {

   uint i;

   for (i = 1; i < num_opnds(); ++i) {

     if (unique_opnds_idx(i) == idx) {

       break;

     }

   }

   return (_components.at(i) != NULL) ? _components.at(i)->_name : "";

 }

 // Return count of unmatched operands.

 uint InstructForm::num_post_match_opnds() {

   uint  num_post_match_opnds = _components.count();

   uint  num_match_opnds = _components.match_count();

   num_post_match_opnds = num_post_match_opnds - num_match_opnds;

   return num_post_match_opnds;

 }

 // Return the number of leaves below this complex operand

 uint InstructForm::num_consts(FormDict &globals) const {

   if ( ! _matrule) return 0;

   // This is a recursive invocation on all operands in the matchrule

   return _matrule->num_consts(globals);

 }

 // Constants in match rule with specified type

 uint InstructForm::num_consts(FormDict &globals, Form::DataType type) const {

   if ( ! _matrule) return 0;

   // This is a recursive invocation on all operands in the matchrule

   return _matrule->num_consts(globals, type);

 }

 // Return the register class associated with 'leaf'.

 const char *InstructForm::out_reg_class(FormDict &globals) {

   assert( false, "InstructForm::out_reg_class(FormDict &globals); Not Implemented");

   return NULL;

 }

 // Lookup the starting position of inputs we are interested in wrt. ideal nodes

 uint InstructForm::oper_input_base(FormDict &globals) {

   if( !_matrule ) return 1;     // Skip control for most nodes

   // Need special handling for matching some ideal nodes

   // i.e. Matching a return node

   if( strcmp(_matrule->_opType,"Return"    )==0 ||

       strcmp(_matrule->_opType,"Rethrow"   )==0 ||

       strcmp(_matrule->_opType,"TailCall"  )==0 ||

       strcmp(_matrule->_opType,"TailJump"  )==0 ||

       strcmp(_matrule->_opType,"SafePoint" )==0 ||

       strcmp(_matrule->_opType,"Halt"      )==0 )

     return AdlcVMDeps::Parms;   // Skip the machine-state edges

   if( _matrule->_rChild &&

       ( strcmp(_matrule->_rChild->_opType,"AryEq"     )==0 ||

         strcmp(_matrule->_rChild->_opType,"StrComp"   )==0 ||

         strcmp(_matrule->_rChild->_opType,"StrEquals" )==0 ||

         strcmp(_matrule->_rChild->_opType,"StrIndexOf")==0 ||

         strcmp(_matrule->_rChild->_opType,"EncodeISOArray")==0)) {

         // String.(compareTo/equals/indexOf) and Arrays.equals

         // and sun.nio.cs.iso8859_1$Encoder.EncodeISOArray

         // take 1 control and 1 memory edges.

     return 2;

   }

   // Check for handling of 'Memory' input/edge in the ideal world.

   // The AD file writer is shielded from knowledge of these edges.

   int base = 1;                 // Skip control

   base += _matrule->needs_ideal_memory_edge(globals);

   // Also skip the base-oop value for uses of derived oops.

   // The AD file writer is shielded from knowledge of these edges.

   base += needs_base_oop_edge(globals);

   return base;

 }

 // This function determines the order of the MachOper in _opnds[]

 // by writing the operand names into the _components list.

 //

 // Implementation does not modify state of internal structures

 void InstructForm::build_components() {

   // Add top-level operands to the components

   if (_matrule)  _matrule->append_components(_localNames, _components);

   // Add parameters that "do not appear in match rule".

   bool has_temp = false;

   const char *name;

   const char *kill_name = NULL;

   for (_parameters.reset(); (name = _parameters.iter()) != NULL;) {

     OperandForm *opForm = (OperandForm*)_localNames[name];

     Effect* e = NULL;

     {

       const Form* form = _effects[name];

       e = form ? form->is_effect() : NULL;

     }

     if (e != NULL) {

       has_temp |= e->is(Component::TEMP);

       // KILLs must be declared after any TEMPs because TEMPs are real

       // uses so their operand numbering must directly follow the real

       // inputs from the match rule.  Fixing the numbering seems

       // complex so simply enforce the restriction during parse.

       if (kill_name != NULL &&

           e->isa(Component::TEMP) && !e->isa(Component::DEF)) {

         OperandForm* kill = (OperandForm*)_localNames[kill_name];

         globalAD->syntax_err(_linenum, "%s: %s %s must be at the end of the argument list\n",

                              _ident, kill->_ident, kill_name);

       } else if (e->isa(Component::KILL) && !e->isa(Component::USE)) {

         kill_name = name;

       }

     }

     const Component *component  = _components.search(name);

     if ( component  == NULL ) {

       if (e) {

         _components.insert(name, opForm->_ident, e->_use_def, false);

         component = _components.search(name);

         if (component->isa(Component::USE) && !component->isa(Component::TEMP) && _matrule) {

           const Form *form = globalAD->globalNames()[component->_type];

           assert( form, "component type must be a defined form");

           OperandForm *op   = form->is_operand();

           if (op->_interface && op->_interface->is_RegInterface()) {

             globalAD->syntax_err(_linenum, "%s: illegal USE of non-input: %s %s\n",

                                  _ident, opForm->_ident, name);

           }

         }

       } else {

         // This would be a nice warning but it triggers in a few places in a benign way

         // if (_matrule != NULL && !expands()) {

         //   globalAD->syntax_err(_linenum, "%s: %s %s not mentioned in effect or match rule\n",

         //                        _ident, opForm->_ident, name);

         // }

         _components.insert(name, opForm->_ident, Component::INVALID, false);

       }

     }

     else if (e) {

       // Component was found in the list

       // Check if there is a new effect that requires an extra component.

       // This happens when adding 'USE' to a component that is not yet one.

       if ((!component->isa( Component::USE) && ((e->_use_def & Component::USE) != 0))) {

         if (component->isa(Component::USE) && _matrule) {

           const Form *form = globalAD->globalNames()[component->_type];

           assert( form, "component type must be a defined form");

           OperandForm *op   = form->is_operand();

           if (op->_interface && op->_interface->is_RegInterface()) {

             globalAD->syntax_err(_linenum, "%s: illegal USE of non-input: %s %s\n",

                                  _ident, opForm->_ident, name);

           }

         }

         _components.insert(name, opForm->_ident, e->_use_def, false);

       } else {

         Component  *comp = (Component*)component;

         comp->promote_use_def_info(e->_use_def);

       }

       // Component positions are zero based.

       int  pos  = _components.operand_position(name);

       assert( ! (component->isa(Component::DEF) && (pos >= 1)),

               "Component::DEF can only occur in the first position");

     }

   }

   // Resolving the interactions between expand rules and TEMPs would

   // be complex so simply disallow it.

   if (_matrule == NULL && has_temp) {

     globalAD->syntax_err(_linenum, "%s: TEMPs without match rule isn't supported\n", _ident);

   }

   return;

 }

 // Return zero-based position in component list;  -1 if not in list.

 int   InstructForm::operand_position(const char *name, int usedef) {

   return unique_opnds_idx(_components.operand_position(name, usedef, this));

 }

 int   InstructForm::operand_position_format(const char *name) {

   return unique_opnds_idx(_components.operand_position_format(name, this));

 }

 // Return zero-based position in component list; -1 if not in list.

 int   InstructForm::label_position() {

   return unique_opnds_idx(_components.label_position());

 }

 int   InstructForm::method_position() {

   return unique_opnds_idx(_components.method_position());

 }

 // Return number of relocation entries needed for this instruction.

 uint  InstructForm::reloc(FormDict &globals) {

   uint reloc_entries  = 0;

   // Check for "Call" nodes

   if ( is_ideal_call() )      ++reloc_entries;

   if ( is_ideal_return() )    ++reloc_entries;

   if ( is_ideal_safepoint() ) ++reloc_entries;

   // Check if operands MAYBE oop pointers, by checking for ConP elements

   // Proceed through the leaves of the match-tree and check for ConPs

   if ( _matrule != NULL ) {

     uint         position = 0;

     const char  *result   = NULL;

     const char  *name     = NULL;

     const char  *opType   = NULL;

     while (_matrule->base_operand(position, globals, result, name, opType)) {

       if ( strcmp(opType,"ConP") == 0 ) {

 #ifdef SPARC

         reloc_entries += 2; // 1 for sethi + 1 for setlo

 #else

         ++reloc_entries;

 #endif

       }

       ++position;

     }

   }

   // Above is only a conservative estimate

   // because it did not check contents of operand classes.

   // !!!!! !!!!!

   // Add 1 to reloc info for each operand class in the component list.

   Component  *comp;

   _components.reset();

   while ( (comp = _components.iter()) != NULL ) {

     const Form        *form = globals[comp->_type];

     assert( form, "Did not find component's type in global names");

     const OpClassForm *opc  = form->is_opclass();

     const OperandForm *oper = form->is_operand();

     if ( opc && (oper == NULL) ) {

       ++reloc_entries;

     } else if ( oper ) {

       // floats and doubles loaded out of method's constant pool require reloc info

       Form::DataType type = oper->is_base_constant(globals);

       if ( (type == Form::idealF) || (type == Form::idealD) ) {

         ++reloc_entries;

       }

     }

   }

   // Float and Double constants may come from the CodeBuffer table

   // and require relocatable addresses for access

   // !!!!!

   // Check for any component being an immediate float or double.

   Form::DataType data_type = is_chain_of_constant(globals);

   if( data_type==idealD || data_type==idealF ) {

 #ifdef SPARC

     // sparc required more relocation entries for floating constants

     // (expires 9/98)

     reloc_entries += 6;

 #else

     reloc_entries++;

 #endif

   }

   return reloc_entries;

 }

 // Utility function defined in archDesc.cpp

 extern bool is_def(int usedef);

 // Return the result of reducing an instruction

 const char *InstructForm::reduce_result() {

   const char* result = "Universe";  // default

   _components.reset();

   Component *comp = _components.iter();

   if (comp != NULL && comp->isa(Component::DEF)) {

     result = comp->_type;

     // Override this if the rule is a store operation:

     if (_matrule && _matrule->_rChild &&

         is_store_to_memory(_matrule->_rChild->_opType))

       result = "Universe";

   }

   return result;

 }

 // Return the name of the operand on the right hand side of the binary match

 // Return NULL if there is no right hand side

 const char *InstructForm::reduce_right(FormDict &globals)  const {

   if( _matrule == NULL ) return NULL;

   return  _matrule->reduce_right(globals);

 }

 // Similar for left

 const char *InstructForm::reduce_left(FormDict &globals)   const {

   if( _matrule == NULL ) return NULL;

   return  _matrule->reduce_left(globals);

 }

 // Base class for this instruction, MachNode except for calls

 const char *InstructForm::mach_base_class(FormDict &globals)  const {

   if( is_ideal_call() == Form::JAVA_STATIC ) {

     return "MachCallStaticJavaNode";

   }

   else if( is_ideal_call() == Form::JAVA_DYNAMIC ) {

     return "MachCallDynamicJavaNode";

   }

   else if( is_ideal_call() == Form::JAVA_RUNTIME ) {

     return "MachCallRuntimeNode";

   }

   else if( is_ideal_call() == Form::JAVA_LEAF ) {

     return "MachCallLeafNode";

   }

   else if (is_ideal_return()) {

     return "MachReturnNode";

   }

   else if (is_ideal_halt()) {

     return "MachHaltNode";

   }

   else if (is_ideal_safepoint()) {

     return "MachSafePointNode";

   }

   else if (is_ideal_if()) {

     return "MachIfNode";

   }

   else if (is_ideal_goto()) {

     return "MachGotoNode";

   }

   else if (is_ideal_fastlock()) {

     return "MachFastLockNode";

   }

   else if (is_ideal_nop()) {

     return "MachNopNode";

   }

   else if (is_mach_constant()) {

     return "MachConstantNode";

   }

   else if (captures_bottom_type(globals)) {

     return "MachTypeNode";

   } else {

     return "MachNode";

   }

   assert( false, "ShouldNotReachHere()");

   return NULL;

 }

 // Compare the instruction predicates for textual equality

 bool equivalent_predicates( const InstructForm *instr1, const InstructForm *instr2 ) {

   const Predicate *pred1  = instr1->_predicate;

   const Predicate *pred2  = instr2->_predicate;

   if( pred1 == NULL && pred2 == NULL ) {

     // no predicates means they are identical

     return true;

   }

   if( pred1 != NULL && pred2 != NULL ) {

     // compare the predicates

     if (ADLParser::equivalent_expressions(pred1->_pred, pred2->_pred)) {

       return true;

     }

   }

   return false;

 }

 // Check if this instruction can cisc-spill to 'alternate'

 bool InstructForm::cisc_spills_to(ArchDesc &AD, InstructForm *instr) {

   assert( _matrule != NULL && instr->_matrule != NULL, "must have match rules");

   // Do not replace if a cisc-version has been found.

   if( cisc_spill_operand() != Not_cisc_spillable ) return false;

   int         cisc_spill_operand = Maybe_cisc_spillable;

   char       *result             = NULL;

   char       *result2            = NULL;

   const char *op_name            = NULL;

   const char *reg_type           = NULL;

   FormDict   &globals            = AD.globalNames();

   cisc_spill_operand = _matrule->matchrule_cisc_spill_match(globals, AD.get_registers(), instr->_matrule, op_name, reg_type);

   if( (cisc_spill_operand != Not_cisc_spillable) && (op_name != NULL) && equivalent_predicates(this, instr) ) {

     cisc_spill_operand = operand_position(op_name, Component::USE);

     int def_oper  = operand_position(op_name, Component::DEF);

     if( def_oper == NameList::Not_in_list && instr->num_opnds() == num_opnds()) {

       // Do not support cisc-spilling for destination operands and

       // make sure they have the same number of operands.

       _cisc_spill_alternate = instr;

       instr->set_cisc_alternate(true);

       if( AD._cisc_spill_debug ) {

         fprintf(stderr, "Instruction %s cisc-spills-to %s\n", _ident, instr->_ident);

         fprintf(stderr, "   using operand %s %s at index %d\n", reg_type, op_name, cisc_spill_operand);

       }

       // Record that a stack-version of the reg_mask is needed

       // !!!!!

       OperandForm *oper = (OperandForm*)(globals[reg_type]->is_operand());

       assert( oper != NULL, "cisc-spilling non operand");

       const char *reg_class_name = oper->constrained_reg_class();

       AD.set_stack_or_reg(reg_class_name);

       const char *reg_mask_name  = AD.reg_mask(*oper);

       set_cisc_reg_mask_name(reg_mask_name);

       const char *stack_or_reg_mask_name = AD.stack_or_reg_mask(*oper);

     } else {

       cisc_spill_operand = Not_cisc_spillable;

     }

   } else {

     cisc_spill_operand = Not_cisc_spillable;

   }

   set_cisc_spill_operand(cisc_spill_operand);

   return (cisc_spill_operand != Not_cisc_spillable);

 }

 // Check to see if this instruction can be replaced with the short branch

 // instruction `short-branch'

 bool InstructForm::check_branch_variant(ArchDesc &AD, InstructForm *short_branch) {

   if (_matrule != NULL &&

       this != short_branch &&   // Don't match myself

       !is_short_branch() &&     // Don't match another short branch variant

       reduce_result() != NULL &&

       strcmp(reduce_result(), short_branch->reduce_result()) == 0 &&

       _matrule->equivalent(AD.globalNames(), short_branch->_matrule)) {

     // The instructions are equivalent.

     // Now verify that both instructions have the same parameters and

     // the same effects. Both branch forms should have the same inputs

     // and resulting projections to correctly replace a long branch node

     // with corresponding short branch node during code generation.

     bool different = false;

     if (short_branch->_components.count() != _components.count()) {

        different = true;

     } else if (_components.count() > 0) {

       short_branch->_components.reset();

       _components.reset();

       Component *comp;

       while ((comp = _components.iter()) != NULL) {

         Component *short_comp = short_branch->_components.iter();

         if (short_comp == NULL ||

             short_comp->_type != comp->_type ||

             short_comp->_usedef != comp->_usedef) {

           different = true;

           break;

         }

       }

       if (short_branch->_components.iter() != NULL)

         different = true;

     }

     if (different) {

       globalAD->syntax_err(short_branch->_linenum, "Instruction %s and its short form %s have different parameters\n", _ident, short_branch->_ident);

     }

     if (AD._adl_debug > 1 || AD._short_branch_debug) {

       fprintf(stderr, "Instruction %s has short form %s\n", _ident, short_branch->_ident);

     }

     _short_branch_form = short_branch;

     return true;

   }

   return false;

 }

 // --------------------------- FILE *output_routines

 //

 // Generate the format call for the replacement variable

 void InstructForm::rep_var_format(FILE *fp, const char *rep_var) {

   // Handle special constant table variables.

   if (strcmp(rep_var, "constanttablebase") == 0) {

     fprintf(fp, "char reg[128];  ra->dump_register(in(mach_constant_base_node_input()), reg);\n");

     fprintf(fp, "    st->print(\"%%s\", reg);\n");

     return;

   }

   if (strcmp(rep_var, "constantoffset") == 0) {

     fprintf(fp, "st->print(\"#%%d\", constant_offset_unchecked());\n");

     return;

   }

   if (strcmp(rep_var, "constantaddress") == 0) {

     fprintf(fp, "st->print(\"constant table base + #%%d\", constant_offset_unchecked());\n");

     return;

   }

   // Find replacement variable's type

   const Form *form   = _localNames[rep_var];

   if (form == NULL) {

     globalAD->syntax_err(_linenum, "Unknown replacement variable %s in format statement of %s.",

                          rep_var, _ident);

     return;

   }

   OpClassForm *opc   = form->is_opclass();

   assert( opc, "replacement variable was not found in local names");

   // Lookup the index position of the replacement variable

   int idx  = operand_position_format(rep_var);

   if ( idx == -1 ) {

     globalAD->syntax_err(_linenum, "Could not find replacement variable %s in format statement of %s.\n",

                          rep_var, _ident);

     assert(strcmp(opc->_ident, "label") == 0, "Unimplemented");

     return;

   }

   if (is_noninput_operand(idx)) {

     // This component isn't in the input array.  Print out the static

     // name of the register.

     OperandForm* oper = form->is_operand();

     if (oper != NULL && oper->is_bound_register()) {

       const RegDef* first = oper->get_RegClass()->find_first_elem();

       fprintf(fp, "    st->print_raw(\"%s\");\n", first->_regname);

     } else {

       globalAD->syntax_err(_linenum, "In %s can't find format for %s %s", _ident, opc->_ident, rep_var);

     }

   } else {

     // Output the format call for this operand

     fprintf(fp,"opnd_array(%d)->",idx);

     if (idx == 0)

       fprintf(fp,"int_format(ra, this, st); // %s\n", rep_var);

     else

       fprintf(fp,"ext_format(ra, this,idx%d, st); // %s\n", idx, rep_var );

   }

 }

 // Seach through operands to determine parameters unique positions.

 void InstructForm::set_unique_opnds() {

   uint* uniq_idx = NULL;

   uint  nopnds = num_opnds();

   uint  num_uniq = nopnds;

   uint i;

   _uniq_idx_length = 0;

   if (nopnds > 0) {

     // Allocate index array.  Worst case we're mapping from each

     // component back to an index and any DEF always goes at 0 so the

     // length of the array has to be the number of components + 1.

     _uniq_idx_length = _components.count() + 1;

     uniq_idx = (uint*) malloc(sizeof(uint) * _uniq_idx_length);

     for (i = 0; i < _uniq_idx_length; i++) {

       uniq_idx[i] = i;

     }

   }

   // Do it only if there is a match rule and no expand rule.  With an

   // expand rule it is done by creating new mach node in Expand()

   // method.

   if (nopnds > 0 && _matrule != NULL && _exprule == NULL) {

     const char *name;

     uint count;

     bool has_dupl_use = false;

     _parameters.reset();

     while ((name = _parameters.iter()) != NULL) {

       count = 0;

       uint position = 0;

       uint uniq_position = 0;

       _components.reset();

       Component *comp = NULL;

       if (sets_result()) {

         comp = _components.iter();

         position++;

       }

       // The next code is copied from the method operand_position().

       for (; (comp = _components.iter()) != NULL; ++position) {

         // When the first component is not a DEF,

         // leave space for the result operand!

         if (position==0 && (!comp->isa(Component::DEF))) {

           ++position;

         }

         if (strcmp(name, comp->_name) == 0) {

           if (++count > 1) {

             assert(position < _uniq_idx_length, "out of bounds");

             uniq_idx[position] = uniq_position;

             has_dupl_use = true;

           } else {

             uniq_position = position;

           }

         }

         if (comp->isa(Component::DEF) && comp->isa(Component::USE)) {

           ++position;

           if (position != 1)

             --position;   // only use two slots for the 1st USE_DEF

         }

       }

     }

     if (has_dupl_use) {

       for (i = 1; i < nopnds; i++) {

         if (i != uniq_idx[i]) {

           break;

         }

       }

       uint j = i;

       for (; i < nopnds; i++) {

         if (i == uniq_idx[i]) {

           uniq_idx[i] = j++;

         }

       }

       num_uniq = j;

     }

   }

   _uniq_idx = uniq_idx;

   _num_uniq = num_uniq;

 }

 // Generate index values needed for determining the operand position

 void InstructForm::index_temps(FILE *fp, FormDict &globals, const char *prefix, const char *receiver) {

   uint  idx = 0;                  // position of operand in match rule

   int   cur_num_opnds = num_opnds();

   // Compute the index into vector of operand pointers:

   // idx0=0 is used to indicate that info comes from this same node, not from input edge.

   // idx1 starts at oper_input_base()

   if ( cur_num_opnds >= 1 ) {

     fprintf(fp,"  // Start at oper_input_base() and count operands\n");

     fprintf(fp,"  unsigned %sidx0 = %d;\n", prefix, oper_input_base(globals));

     fprintf(fp,"  unsigned %sidx1 = %d;", prefix, oper_input_base(globals));

     fprintf(fp," \t// %s\n", unique_opnd_ident(1));

     // Generate starting points for other unique operands if they exist

     for ( idx = 2; idx < num_unique_opnds(); ++idx ) {

       if( *receiver == 0 ) {

         fprintf(fp,"  unsigned %sidx%d = %sidx%d + opnd_array(%d)->num_edges();",

                 prefix, idx, prefix, idx-1, idx-1 );

       } else {

         fprintf(fp,"  unsigned %sidx%d = %sidx%d + %s_opnds[%d]->num_edges();",

                 prefix, idx, prefix, idx-1, receiver, idx-1 );

       }

       fprintf(fp," \t// %s\n", unique_opnd_ident(idx));

     }

   }

   if( *receiver != 0 ) {

     // This value is used by generate_peepreplace when copying a node.

     // Don't emit it in other cases since it can hide bugs with the

     // use invalid idx's.

     fprintf(fp,"  unsigned %sidx%d = %sreq(); \n", prefix, idx, receiver);

   }

 }

 // ---------------------------

 bool InstructForm::verify() {

   // !!!!! !!!!!

   // Check that a "label" operand occurs last in the operand list, if present

   return true;

 }

 void InstructForm::dump() {

   output(stderr);

 }

 void InstructForm::output(FILE *fp) {

   fprintf(fp,"\nInstruction: %s\n", (_ident?_ident:""));

   if (_matrule)   _matrule->output(fp);

   if (_insencode) _insencode->output(fp);

   if (_constant)  _constant->output(fp);

   if (_opcode)    _opcode->output(fp);

   if (_attribs)   _attribs->output(fp);

   if (_predicate) _predicate->output(fp);

   if (_effects.Size()) {

     fprintf(fp,"Effects\n");

     _effects.dump();

   }

   if (_exprule)   _exprule->output(fp);

   if (_rewrule)   _rewrule->output(fp);

   if (_format)    _format->output(fp);

   if (_peephole)  _peephole->output(fp);

 }

 void MachNodeForm::dump() {

   output(stderr);

 }

 void MachNodeForm::output(FILE *fp) {

   fprintf(fp,"\nMachNode: %s\n", (_ident?_ident:""));

 }

 //------------------------------build_predicate--------------------------------

 // Build instruction predicates.  If the user uses the same operand name

 // twice, we need to check that the operands are pointer-eequivalent in

 // the DFA during the labeling process.

 Predicate *InstructForm::build_predicate() {

   char buf[1024], *s=buf;

   Dict names(cmpstr,hashstr,Form::arena);       // Map Names to counts

   MatchNode *mnode =

     strcmp(_matrule->_opType, "Set") ? _matrule : _matrule->_rChild;

   mnode->count_instr_names(names);

   uint first = 1;

   // Start with the predicate supplied in the .ad file.

   if( _predicate ) {

     if( first ) first=0;

     strcpy(s,"("); s += strlen(s);

     strcpy(s,_predicate->_pred);

     s += strlen(s);

     strcpy(s,")"); s += strlen(s);

   }

   for( DictI i(&names); i.test(); ++i ) {

     uintptr_t cnt = (uintptr_t)i._value;

     if( cnt > 1 ) {             // Need a predicate at all?

       assert( cnt == 2, "Unimplemented" );

       // Handle many pairs

       if( first ) first=0;

       else {                    // All tests must pass, so use '&&'

         strcpy(s," && ");

         s += strlen(s);

       }

       // Add predicate to working buffer

       sprintf(s,"/*%s*/(",(char*)i._key);

       s += strlen(s);

       mnode->build_instr_pred(s,(char*)i._key,0);

       s += strlen(s);

       strcpy(s," == "); s += strlen(s);

       mnode->build_instr_pred(s,(char*)i._key,1);

       s += strlen(s);

       strcpy(s,")"); s += strlen(s);

     }

   }

   if( s == buf ) s = NULL;

   else {

     assert( strlen(buf) < sizeof(buf), "String buffer overflow" );

     s = strdup(buf);

   }

   return new Predicate(s);

 }

 //------------------------------EncodeForm-------------------------------------

 // Constructor

 EncodeForm::EncodeForm()

   : _encClass(cmpstr,hashstr, Form::arena) {

 }

 EncodeForm::~EncodeForm() {

 }

 // record a new register class

 EncClass *EncodeForm::add_EncClass(const char *className) {

   EncClass *encClass = new EncClass(className);

   _eclasses.addName(className);

   _encClass.Insert(className,encClass);

   return encClass;

 }

 // Lookup the function body for an encoding class

 EncClass  *EncodeForm::encClass(const char *className) {

   assert( className != NULL, "Must provide a defined encoding name");

   EncClass *encClass = (EncClass*)_encClass[className];

   return encClass;

 }

 // Lookup the function body for an encoding class

 const char *EncodeForm::encClassBody(const char *className) {

   if( className == NULL ) return NULL;

   EncClass *encClass = (EncClass*)_encClass[className];

   assert( encClass != NULL, "Encode Class is missing.");

   encClass->_code.reset();

   const char *code = (const char*)encClass->_code.iter();

   assert( code != NULL, "Found an empty encode class body.");

   return code;

 }

 // Lookup the function body for an encoding class

 const char *EncodeForm::encClassPrototype(const char *className) {

   assert( className != NULL, "Encode class name must be non NULL.");

   return className;

 }

 void EncodeForm::dump() {                  // Debug printer

   output(stderr);

 }

 void EncodeForm::output(FILE *fp) {          // Write info to output files

   const char *name;

   fprintf(fp,"\n");

   fprintf(fp,"-------------------- Dump EncodeForm --------------------\n");

   for (_eclasses.reset(); (name = _eclasses.iter()) != NULL;) {

     ((EncClass*)_encClass[name])->output(fp);

   }

   fprintf(fp,"-------------------- end  EncodeForm --------------------\n");

 }

 //------------------------------EncClass---------------------------------------

 EncClass::EncClass(const char *name)

   : _localNames(cmpstr,hashstr, Form::arena), _name(name) {

 }

 EncClass::~EncClass() {

 }

 // Add a parameter <type,name> pair

 void EncClass::add_parameter(const char *parameter_type, const char *parameter_name) {

   _parameter_type.addName( parameter_type );

   _parameter_name.addName( parameter_name );

 }

 // Verify operand types in parameter list

 bool EncClass::check_parameter_types(FormDict &globals) {

   // !!!!!

   return false;

 }

 // Add the decomposed "code" sections of an encoding's code-block

 void EncClass::add_code(const char *code) {

   _code.addName(code);

 }

 // Add the decomposed "replacement variables" of an encoding's code-block

 void EncClass::add_rep_var(char *replacement_var) {

   _code.addName(NameList::_signal);

   _rep_vars.addName(replacement_var);

 }

 // Lookup the function body for an encoding class

 int EncClass::rep_var_index(const char *rep_var) {

   uint        position = 0;

   const char *name     = NULL;

   _parameter_name.reset();

   while ( (name = _parameter_name.iter()) != NULL ) {

     if ( strcmp(rep_var,name) == 0 ) return position;

     ++position;

   }

   return -1;

 }

 // Check after parsing

 bool EncClass::verify() {

   // 1!!!!

   // Check that each replacement variable, '$name' in architecture description

   // is actually a local variable for this encode class, or a reserved name

   // "primary, secondary, tertiary"

   return true;

 }

 void EncClass::dump() {

   output(stderr);

 }

 // Write info to output files

 void EncClass::output(FILE *fp) {

   fprintf(fp,"EncClass: %s", (_name ? _name : ""));

   // Output the parameter list

   _parameter_type.reset();

   _parameter_name.reset();

   const char *type = _parameter_type.iter();

   const char *name = _parameter_name.iter();

   fprintf(fp, " ( ");

   for ( ; (type != NULL) && (name != NULL);

         (type = _parameter_type.iter()), (name = _parameter_name.iter()) ) {

     fprintf(fp, " %s %s,", type, name);

   }

   fprintf(fp, " ) ");

   // Output the code block

   _code.reset();

   _rep_vars.reset();

   const char *code;

   while ( (code = _code.iter()) != NULL ) {

     if ( _code.is_signal(code) ) {

       // A replacement variable

       const char *rep_var = _rep_vars.iter();

       fprintf(fp,"($%s)", rep_var);

     } else {

       // A section of code

       fprintf(fp,"%s", code);

     }

   }

 }

 //------------------------------Opcode-----------------------------------------

 Opcode::Opcode(char *primary, char *secondary, char *tertiary)

   : _primary(primary), _secondary(secondary), _tertiary(tertiary) {

 }

 Opcode::~Opcode() {

 }

 Opcode::opcode_type Opcode::as_opcode_type(const char *param) {

   if( strcmp(param,"primary") == 0 ) {

     return Opcode::PRIMARY;

   }

   else if( strcmp(param,"secondary") == 0 ) {

     return Opcode::SECONDARY;

   }

   else if( strcmp(param,"tertiary") == 0 ) {

     return Opcode::TERTIARY;

   }

   return Opcode::NOT_AN_OPCODE;

 }

 bool Opcode::print_opcode(FILE *fp, Opcode::opcode_type desired_opcode) {

   // Default values previously provided by MachNode::primary()...

   const char *description = NULL;

   const char *value       = NULL;

   // Check if user provided any opcode definitions

   if( this != NULL ) {

     // Update 'value' if user provided a definition in the instruction

     switch (desired_opcode) {

     case PRIMARY:

       description = "primary()";

       if( _primary   != NULL)  { value = _primary;     }

       break;

     case SECONDARY:

       description = "secondary()";

       if( _secondary != NULL ) { value = _secondary;   }

       break;

     case TERTIARY:

       description = "tertiary()";

       if( _tertiary  != NULL ) { value = _tertiary;    }

       break;

     default:

       assert( false, "ShouldNotReachHere();");

       break;

     }

   }

   if (value != NULL) {

     fprintf(fp, "(%s /*%s*/)", value, description);

   }

   return value != NULL;

 }

 void Opcode::dump() {

   output(stderr);

 }

 // Write info to output files

 void Opcode::output(FILE *fp) {

   if (_primary   != NULL) fprintf(fp,"Primary   opcode: %s\n", _primary);

   if (_secondary != NULL) fprintf(fp,"Secondary opcode: %s\n", _secondary);

   if (_tertiary  != NULL) fprintf(fp,"Tertiary  opcode: %s\n", _tertiary);

 }

 //------------------------------InsEncode--------------------------------------

 InsEncode::InsEncode() {

 }

 InsEncode::~InsEncode() {

 }

 // Add "encode class name" and its parameters

 NameAndList *InsEncode::add_encode(char *encoding) {

   assert( encoding != NULL, "Must provide name for encoding");

   // add_parameter(NameList::_signal);

   NameAndList *encode = new NameAndList(encoding);

   _encoding.addName((char*)encode);

   return encode;

 }

 // Access the list of encodings

 void InsEncode::reset() {

   _encoding.reset();

   // _parameter.reset();

 }

 const char* InsEncode::encode_class_iter() {

   NameAndList  *encode_class = (NameAndList*)_encoding.iter();

   return  ( encode_class != NULL ? encode_class->name() : NULL );

 }

 // Obtain parameter name from zero based index

 const char *InsEncode::rep_var_name(InstructForm &inst, uint param_no) {

   NameAndList *params = (NameAndList*)_encoding.current();

   assert( params != NULL, "Internal Error");

   const char *param = (*params)[param_no];

   // Remove '$' if parser placed it there.

   return ( param != NULL && *param == '$') ? (param+1) : param;

 }

 void InsEncode::dump() {

   output(stderr);

 }

 // Write info to output files

 void InsEncode::output(FILE *fp) {

   NameAndList *encoding  = NULL;

   const char  *parameter = NULL;

   fprintf(fp,"InsEncode: ");

   _encoding.reset();

   while ( (encoding = (NameAndList*)_encoding.iter()) != 0 ) {

     // Output the encoding being used

     fprintf(fp,"%s(", encoding->name() );

     // Output its parameter list, if any

     bool first_param = true;

     encoding->reset();

     while (  (parameter = encoding->iter()) != 0 ) {

       // Output the ',' between parameters

       if ( ! first_param )  fprintf(fp,", ");

       first_param = false;

       // Output the parameter

       fprintf(fp,"%s", parameter);

     } // done with parameters

     fprintf(fp,")  ");

   } // done with encodings

   fprintf(fp,"\n");

 }

 //------------------------------Effect-----------------------------------------

 static int effect_lookup(const char *name) {

   if(!strcmp(name, "USE")) return Component::USE;

   if(!strcmp(name, "DEF")) return Component::DEF;

   if(!strcmp(name, "USE_DEF")) return Component::USE_DEF;

   if(!strcmp(name, "KILL")) return Component::KILL;

   if(!strcmp(name, "USE_KILL")) return Component::USE_KILL;

   if(!strcmp(name, "TEMP")) return Component::TEMP;

   if(!strcmp(name, "INVALID")) return Component::INVALID;

   if(!strcmp(name, "CALL")) return Component::CALL;

   assert( false,"Invalid effect name specified\n");

   return Component::INVALID;

 }

 const char *Component::getUsedefName() {

   switch (_usedef) {

     case Component::INVALID:  return "INVALID";  break;

     case Component::USE:      return "USE";      break;

     case Component::USE_DEF:  return "USE_DEF";  break;

     case Component::USE_KILL: return "USE_KILL"; break;

     case Component::KILL:     return "KILL";     break;

     case Component::TEMP:     return "TEMP";     break;

     case Component::DEF:      return "DEF";      break;

     case Component::CALL:     return "CALL";     break;

     default: assert(false, "unknown effect");

   }

   return "Undefined Use/Def info";

 }

 Effect::Effect(const char *name) : _name(name), _use_def(effect_lookup(name)) {

   _ftype = Form::EFF;

 }

 Effect::~Effect() {

 }

 // Dynamic type check

 Effect *Effect::is_effect() const {

   return (Effect*)this;

 }

 // True if this component is equal to the parameter.

 bool Effect::is(int use_def_kill_enum) const {

   return (_use_def == use_def_kill_enum ? true : false);

 }

 // True if this component is used/def'd/kill'd as the parameter suggests.

 bool Effect::isa(int use_def_kill_enum) const {

   return (_use_def & use_def_kill_enum) == use_def_kill_enum;

 }

 void Effect::dump() {

   output(stderr);

 }

 void Effect::output(FILE *fp) {          // Write info to output files

   fprintf(fp,"Effect: %s\n", (_name?_name:""));

 }

 //------------------------------ExpandRule-------------------------------------

 ExpandRule::ExpandRule() : _expand_instrs(),

                            _newopconst(cmpstr, hashstr, Form::arena) {

   _ftype = Form::EXP;

 }

 ExpandRule::~ExpandRule() {                  // Destructor

 }

 void ExpandRule::add_instruction(NameAndList *instruction_name_and_operand_list) {

   _expand_instrs.addName((char*)instruction_name_and_operand_list);

 }

 void ExpandRule::reset_instructions() {

   _expand_instrs.reset();

 }

 NameAndList* ExpandRule::iter_instructions() {

   return (NameAndList*)_expand_instrs.iter();

 }

 void ExpandRule::dump() {

   output(stderr);

 }

 void ExpandRule::output(FILE *fp) {         // Write info to output files

   NameAndList *expand_instr = NULL;

   const char *opid = NULL;

   fprintf(fp,"\nExpand Rule:\n");

   // Iterate over the instructions 'node' expands into

   for(reset_instructions(); (expand_instr = iter_instructions()) != NULL; ) {

     fprintf(fp,"%s(", expand_instr->name());

     // iterate over the operand list

     for( expand_instr->reset(); (opid = expand_instr->iter()) != NULL; ) {

       fprintf(fp,"%s ", opid);

     }

     fprintf(fp,");\n");

   }

 }

 //------------------------------RewriteRule------------------------------------

 RewriteRule::RewriteRule(char* params, char* block)

   : _tempParams(params), _tempBlock(block) { };  // Constructor

 RewriteRule::~RewriteRule() {                 // Destructor

 }

 void RewriteRule::dump() {

   output(stderr);

 }

 void RewriteRule::output(FILE *fp) {         // Write info to output files

   fprintf(fp,"\nRewrite Rule:\n%s\n%s\n",

           (_tempParams?_tempParams:""),

           (_tempBlock?_tempBlock:""));

 }

 //==============================MachNodes======================================

 //------------------------------MachNodeForm-----------------------------------

 MachNodeForm::MachNodeForm(char *id)

   : _ident(id) {

 }

 MachNodeForm::~MachNodeForm() {

 }

 MachNodeForm *MachNodeForm::is_machnode() const {

   return (MachNodeForm*)this;

 }

 //==============================Operand Classes================================

 //------------------------------OpClassForm------------------------------------

 OpClassForm::OpClassForm(const char* id) : _ident(id) {

   _ftype = Form::OPCLASS;

 }

 OpClassForm::~OpClassForm() {

 }

 bool OpClassForm::ideal_only() const { return 0; }

 OpClassForm *OpClassForm::is_opclass() const {

   return (OpClassForm*)this;

 }

 Form::InterfaceType OpClassForm::interface_type(FormDict &globals) const {

   if( _oplst.count() == 0 ) return Form::no_interface;

   // Check that my operands have the same interface type

   Form::InterfaceType  interface;

   bool  first = true;

   NameList &op_list = (NameList &)_oplst;

   op_list.reset();

   const char *op_name;

   while( (op_name = op_list.iter()) != NULL ) {

     const Form  *form    = globals[op_name];

     OperandForm *operand = form->is_operand();

     assert( operand, "Entry in operand class that is not an operand");

     if( first ) {

       first     = false;

       interface = operand->interface_type(globals);

     } else {

       interface = (interface == operand->interface_type(globals) ? interface : Form::no_interface);

     }

   }

   return interface;

 }

 bool OpClassForm::stack_slots_only(FormDict &globals) const {

   if( _oplst.count() == 0 ) return false;  // how?

   NameList &op_list = (NameList &)_oplst;

   op_list.reset();

   const char *op_name;

   while( (op_name = op_list.iter()) != NULL ) {

     const Form  *form    = globals[op_name];

     OperandForm *operand = form->is_operand();

     assert( operand, "Entry in operand class that is not an operand");

     if( !operand->stack_slots_only(globals) )  return false;

   }

   return true;

 }

 void OpClassForm::dump() {

   output(stderr);

 }

 void OpClassForm::output(FILE *fp) {

   const char *name;

   fprintf(fp,"\nOperand Class: %s\n", (_ident?_ident:""));

   fprintf(fp,"\nCount = %d\n", _oplst.count());

   for(_oplst.reset(); (name = _oplst.iter()) != NULL;) {

     fprintf(fp,"%s, ",name);

   }

   fprintf(fp,"\n");

 }

 //==============================Operands=======================================

 //------------------------------OperandForm------------------------------------

 OperandForm::OperandForm(const char* id)

   : OpClassForm(id), _ideal_only(false),

     _localNames(cmpstr, hashstr, Form::arena) {

       _ftype = Form::OPER;

       _matrule   = NULL;

       _interface = NULL;

       _attribs   = NULL;

       _predicate = NULL;

       _constraint= NULL;

       _construct = NULL;

       _format    = NULL;

 }

 OperandForm::OperandForm(const char* id, bool ideal_only)

   : OpClassForm(id), _ideal_only(ideal_only),

     _localNames(cmpstr, hashstr, Form::arena) {

       _ftype = Form::OPER;

       _matrule   = NULL;

       _interface = NULL;

       _attribs   = NULL;

       _predicate = NULL;

       _constraint= NULL;

       _construct = NULL;

       _format    = NULL;

 }

 OperandForm::~OperandForm() {

 }

 OperandForm *OperandForm::is_operand() const {

   return (OperandForm*)this;

 }

 bool OperandForm::ideal_only() const {

   return _ideal_only;

 }

 Form::InterfaceType OperandForm::interface_type(FormDict &globals) const {

   if( _interface == NULL )  return Form::no_interface;

   return _interface->interface_type(globals);

 }

 bool OperandForm::stack_slots_only(FormDict &globals) const {

   if( _constraint == NULL )  return false;

   return _constraint->stack_slots_only();

 }

 // Access op_cost attribute or return NULL.

 const char* OperandForm::cost() {

   for (Attribute* cur = _attribs; cur != NULL; cur = (Attribute*)cur->_next) {

     if( strcmp(cur->_ident,AttributeForm::_op_cost) == 0 ) {

       return cur->_val;

     }

   }

   return NULL;

 }

 // Return the number of leaves below this complex operand

 uint OperandForm::num_leaves() const {

   if ( ! _matrule) return 0;

   int num_leaves = _matrule->_numleaves;

   return num_leaves;

 }

 // Return the number of constants contained within this complex operand

 uint OperandForm::num_consts(FormDict &globals) const {

   if ( ! _matrule) return 0;

   // This is a recursive invocation on all operands in the matchrule

   return _matrule->num_consts(globals);

 }

 // Return the number of constants in match rule with specified type

 uint OperandForm::num_consts(FormDict &globals, Form::DataType type) const {

   if ( ! _matrule) return 0;

   // This is a recursive invocation on all operands in the matchrule

   return _matrule->num_consts(globals, type);

 }

 // Return the number of pointer constants contained within this complex operand

 uint OperandForm::num_const_ptrs(FormDict &globals) const {

   if ( ! _matrule) return 0;

   // This is a recursive invocation on all operands in the matchrule

   return _matrule->num_const_ptrs(globals);

 }

 uint OperandForm::num_edges(FormDict &globals) const {

   uint edges  = 0;

   uint leaves = num_leaves();

   uint consts = num_consts(globals);

   // If we are matching a constant directly, there are no leaves.

   edges = ( leaves > consts ) ? leaves - consts : 0;

   // !!!!!

   // Special case operands that do not have a corresponding ideal node.

   if( (edges == 0) && (consts == 0) ) {

     if( constrained_reg_class() != NULL ) {

       edges = 1;

     } else {

       if( _matrule

           && (_matrule->_lChild == NULL) && (_matrule->_rChild == NULL) ) {

         const Form *form = globals[_matrule->_opType];

         OperandForm *oper = form ? form->is_operand() : NULL;

         if( oper ) {

           return oper->num_edges(globals);

         }

       }

     }

   }

   return edges;

 }

 // Check if this operand is usable for cisc-spilling

 bool  OperandForm::is_cisc_reg(FormDict &globals) const {

   const char *ideal = ideal_type(globals);

   bool is_cisc_reg = (ideal && (ideal_to_Reg_type(ideal) != none));

   return is_cisc_reg;

 }

 bool  OpClassForm::is_cisc_mem(FormDict &globals) const {

   Form::InterfaceType my_interface = interface_type(globals);

   return (my_interface == memory_interface);

 }

 // node matches ideal 'Bool'

 bool OperandForm::is_ideal_bool() const {

   if( _matrule == NULL ) return false;

   return _matrule->is_ideal_bool();

 }

 // Require user's name for an sRegX to be stackSlotX

 Form::DataType OperandForm::is_user_name_for_sReg() const {

   DataType data_type = none;

   if( _ident != NULL ) {

     if(      strcmp(_ident,"stackSlotI") == 0 ) data_type = Form::idealI;

     else if( strcmp(_ident,"stackSlotP") == 0 ) data_type = Form::idealP;

     else if( strcmp(_ident,"stackSlotD") == 0 ) data_type = Form::idealD;

     else if( strcmp(_ident,"stackSlotF") == 0 ) data_type = Form::idealF;

     else if( strcmp(_ident,"stackSlotL") == 0 ) data_type = Form::idealL;

   }

   assert((data_type == none) || (_matrule == NULL), "No match-rule for stackSlotX");

   return data_type;

 }

 // Return ideal type, if there is a single ideal type for this operand

 const char *OperandForm::ideal_type(FormDict &globals, RegisterForm *registers) const {

   const char *type = NULL;

   if (ideal_only()) type = _ident;

   else if( _matrule == NULL ) {

     // Check for condition code register

     const char *rc_name = constrained_reg_class();

     // !!!!!

     if (rc_name == NULL) return NULL;

     // !!!!! !!!!!

     // Check constraints on result's register class

     if( registers ) {

       RegClass *reg_class  = registers->getRegClass(rc_name);

       assert( reg_class != NULL, "Register class is not defined");

       // Check for ideal type of entries in register class, all are the same type

       reg_class->reset();

       RegDef *reg_def = reg_class->RegDef_iter();

       assert( reg_def != NULL, "No entries in register class");

       assert( reg_def->_idealtype != NULL, "Did not define ideal type for register");

       // Return substring that names the register's ideal type

       type = reg_def->_idealtype + 3;

       assert( *(reg_def->_idealtype + 0) == 'O', "Expect Op_ prefix");

       assert( *(reg_def->_idealtype + 1) == 'p', "Expect Op_ prefix");

       assert( *(reg_def->_idealtype + 2) == '_', "Expect Op_ prefix");

     }

   }

   else if( _matrule->_lChild == NULL && _matrule->_rChild == NULL ) {

     // This operand matches a single type, at the top level.

     // Check for ideal type

     type = _matrule->_opType;

     if( strcmp(type,"Bool") == 0 )

       return "Bool";

     // transitive lookup

     const Form *frm = globals[type];

     OperandForm *op = frm->is_operand();

     type = op->ideal_type(globals, registers);

   }

   return type;

 }

 // If there is a single ideal type for this interface field, return it.

 const char *OperandForm::interface_ideal_type(FormDict &globals,

                                               const char *field) const {

   const char  *ideal_type = NULL;

   const char  *value      = NULL;

   // Check if "field" is valid for this operand's interface

   if ( ! is_interface_field(field, value) )   return ideal_type;

   // !!!!! !!!!! !!!!!

   // If a valid field has a constant value, identify "ConI" or "ConP" or ...

   // Else, lookup type of field's replacement variable

   return ideal_type;

 }

 RegClass* OperandForm::get_RegClass() const {

   if (_interface && !_interface->is_RegInterface()) return NULL;

   return globalAD->get_registers()->getRegClass(constrained_reg_class());

 }

 bool OperandForm::is_bound_register() const {

   RegClass* reg_class = get_RegClass();

   if (reg_class == NULL) {

     return false;

   }

   const char* name = ideal_type(globalAD->globalNames());

   if (name == NULL) {

     return false;

   }

   uint size = 0;

   if (strcmp(name, "RegFlags") == 0) size = 1;

   if (strcmp(name, "RegI") == 0) size = 1;

   if (strcmp(name, "RegF") == 0) size = 1;

   if (strcmp(name, "RegD") == 0) size = 2;

   if (strcmp(name, "RegL") == 0) size = 2;

   if (strcmp(name, "RegN") == 0) size = 1;

   if (strcmp(name, "RegP") == 0) size = globalAD->get_preproc_def("_LP64") ? 2 : 1;

   if (size == 0) {

     return false;

   }

   return size == reg_class->size();

 }

 // Check if this is a valid field for this operand,

 // Return 'true' if valid, and set the value to the string the user provided.

 bool  OperandForm::is_interface_field(const char *field,

                                       const char * &value) const {

   return false;

 }

 // Return register class name if a constraint specifies the register class.

 const char *OperandForm::constrained_reg_class() const {

   const char *reg_class  = NULL;

   if ( _constraint ) {

     // !!!!!

     Constraint *constraint = _constraint;

     if ( strcmp(_constraint->_func,"ALLOC_IN_RC") == 0 ) {

       reg_class = _constraint->_arg;

     }

   }

   return reg_class;

 }

 // Return the register class associated with 'leaf'.

 const char *OperandForm::in_reg_class(uint leaf, FormDict &globals) {

   const char *reg_class = NULL; // "RegMask::Empty";

   if((_matrule == NULL) || (_matrule->is_chain_rule(globals))) {

     reg_class = constrained_reg_class();

     return reg_class;

   }

   const char *result   = NULL;

   const char *name     = NULL;

   const char *type     = NULL;

   // iterate through all base operands

   // until we reach the register that corresponds to "leaf"

   // This function is not looking for an ideal type.  It needs the first

   // level user type associated with the leaf.

   for(uint idx = 0;_matrule->base_operand(idx,globals,result,name,type);++idx) {

     const Form *form = (_localNames[name] ? _localNames[name] : globals[result]);

     OperandForm *oper = form ? form->is_operand() : NULL;

     if( oper ) {

       reg_class = oper->constrained_reg_class();

       if( reg_class ) {

         reg_class = reg_class;

       } else {

         // ShouldNotReachHere();

       }

     } else {

       // ShouldNotReachHere();

     }

     // Increment our target leaf position if current leaf is not a candidate.

     if( reg_class == NULL)    ++leaf;

     // Exit the loop with the value of reg_class when at the correct index

     if( idx == leaf )         break;

     // May iterate through all base operands if reg_class for 'leaf' is NULL

   }

   return reg_class;

 }

 // Recursive call to construct list of top-level operands.

 // Implementation does not modify state of internal structures

 void OperandForm::build_components() {

   if (_matrule)  _matrule->append_components(_localNames, _components);

   // Add parameters that "do not appear in match rule".

   const char *name;

   for (_parameters.reset(); (name = _parameters.iter()) != NULL;) {

     OperandForm *opForm = (OperandForm*)_localNames[name];

     if ( _components.operand_position(name) == -1 ) {

       _components.insert(name, opForm->_ident, Component::INVALID, false);

     }

   }

   return;

 }

 int OperandForm::operand_position(const char *name, int usedef) {

   return _components.operand_position(name, usedef, this);

 }

 // Return zero-based position in component list, only counting constants;

 // Return -1 if not in list.

 int OperandForm::constant_position(FormDict &globals, const Component *last) {

   // Iterate through components and count constants preceding 'constant'

   int position = 0;

   Component *comp;

   _components.reset();

   while( (comp = _components.iter()) != NULL  && (comp != last) ) {

     // Special case for operands that take a single user-defined operand

     // Skip the initial definition in the component list.

     if( strcmp(comp->_name,this->_ident) == 0 ) continue;

     const char *type = comp->_type;

     // Lookup operand form for replacement variable's type

     const Form *form = globals[type];

     assert( form != NULL, "Component's type not found");

     OperandForm *oper = form ? form->is_operand() : NULL;

     if( oper ) {

       if( oper->_matrule->is_base_constant(globals) != Form::none ) {

         ++position;

       }

     }

   }

   // Check for being passed a component that was not in the list

   if( comp != last )  position = -1;

   return position;

 }

 // Provide position of constant by "name"

 int OperandForm::constant_position(FormDict &globals, const char *name) {

   const Component *comp = _components.search(name);

   int idx = constant_position( globals, comp );

   return idx;

 }

 // Return zero-based position in component list, only counting constants;

 // Return -1 if not in list.

 int OperandForm::register_position(FormDict &globals, const char *reg_name) {

   // Iterate through components and count registers preceding 'last'

   uint  position = 0;

   Component *comp;

   _components.reset();

   while( (comp = _components.iter()) != NULL

          && (strcmp(comp->_name,reg_name) != 0) ) {

     // Special case for operands that take a single user-defined operand

     // Skip the initial definition in the component list.

     if( strcmp(comp->_name,this->_ident) == 0 ) continue;

     const char *type = comp->_type;

     // Lookup operand form for component's type

     const Form *form = globals[type];

     assert( form != NULL, "Component's type not found");

     OperandForm *oper = form ? form->is_operand() : NULL;

     if( oper ) {

       if( oper->_matrule->is_base_register(globals) ) {

         ++position;

       }

     }

   }

   return position;

 }

 const char *OperandForm::reduce_result()  const {

   return _ident;

 }

 // Return the name of the operand on the right hand side of the binary match

 // Return NULL if there is no right hand side

 const char *OperandForm::reduce_right(FormDict &globals)  const {

   return  ( _matrule ? _matrule->reduce_right(globals) : NULL );

 }

 // Similar for left

 const char *OperandForm::reduce_left(FormDict &globals)   const {

   return  ( _matrule ? _matrule->reduce_left(globals) : NULL );

 }

 // --------------------------- FILE *output_routines

 //

 // Output code for disp_is_oop, if true.

 void OperandForm::disp_is_oop(FILE *fp, FormDict &globals) {

   //  Check it is a memory interface with a non-user-constant disp field

   if ( this->_interface == NULL ) return;

   MemInterface *mem_interface = this->_interface->is_MemInterface();

   if ( mem_interface == NULL )    return;

   const char   *disp  = mem_interface->_disp;

   if ( *disp != '$' )             return;

   // Lookup replacement variable in operand's component list

   const char   *rep_var = disp + 1;

   const Component *comp = this->_components.search(rep_var);

   assert( comp != NULL, "Replacement variable not found in components");

   // Lookup operand form for replacement variable's type

   const char      *type = comp->_type;

   Form            *form = (Form*)globals[type];

   assert( form != NULL, "Replacement variable's type not found");

   OperandForm     *op   = form->is_operand();

   assert( op, "Memory Interface 'disp' can only emit an operand form");

   // Check if this is a ConP, which may require relocation

   if ( op->is_base_constant(globals) == Form::idealP ) {

     // Find the constant's index:  _c0, _c1, _c2, ... , _cN

     uint idx  = op->constant_position( globals, rep_var);

     fprintf(fp,"  virtual relocInfo::relocType disp_reloc() const {");

     fprintf(fp,  "  return _c%d->reloc();", idx);

     fprintf(fp, " }\n");

   }

 }

 // Generate code for internal and external format methods

 //

 // internal access to reg# node->_idx

 // access to subsumed constant _c0, _c1,

 void  OperandForm::int_format(FILE *fp, FormDict &globals, uint index) {

   Form::DataType dtype;

   if (_matrule && (_matrule->is_base_register(globals) ||

                    strcmp(ideal_type(globalAD->globalNames()), "RegFlags") == 0)) {

     // !!!!! !!!!!

     fprintf(fp,"  { char reg_str[128];\n");

     fprintf(fp,"    ra->dump_register(node,reg_str);\n");

     fprintf(fp,"    st->print(\"%cs\",reg_str);\n",'%');

     fprintf(fp,"  }\n");

   } else if (_matrule && (dtype = _matrule->is_base_constant(globals)) != Form::none) {

     format_constant( fp, index, dtype );

   } else if (ideal_to_sReg_type(_ident) != Form::none) {

     // Special format for Stack Slot Register

     fprintf(fp,"  { char reg_str[128];\n");

     fprintf(fp,"    ra->dump_register(node,reg_str);\n");

     fprintf(fp,"    st->print(\"%cs\",reg_str);\n",'%');

     fprintf(fp,"  }\n");

   } else {

     fprintf(fp,"  st->print(\"No format defined for %s\n\");\n", _ident);

     fflush(fp);

     fprintf(stderr,"No format defined for %s\n", _ident);

     dump();

     assert( false,"Internal error:\n  output_internal_operand() attempting to output other than a Register or Constant");

   }

 }

 // Similar to "int_format" but for cases where data is external to operand

 // external access to reg# node->in(idx)->_idx,

 void  OperandForm::ext_format(FILE *fp, FormDict &globals, uint index) {

   Form::DataType dtype;

   if (_matrule && (_matrule->is_base_register(globals) ||

                    strcmp(ideal_type(globalAD->globalNames()), "RegFlags") == 0)) {

     fprintf(fp,"  { char reg_str[128];\n");

     fprintf(fp,"    ra->dump_register(node->in(idx");

     if ( index != 0 ) fprintf(fp,              "+%d",index);

     fprintf(fp,                                      "),reg_str);\n");

     fprintf(fp,"    st->print(\"%cs\",reg_str);\n",'%');

     fprintf(fp,"  }\n");

   } else if (_matrule && (dtype = _matrule->is_base_constant(globals)) != Form::none) {

     format_constant( fp, index, dtype );

   } else if (ideal_to_sReg_type(_ident) != Form::none) {

     // Special format for Stack Slot Register

     fprintf(fp,"  { char reg_str[128];\n");

     fprintf(fp,"    ra->dump_register(node->in(idx");

     if ( index != 0 ) fprintf(fp,                  "+%d",index);

     fprintf(fp,                                       "),reg_str);\n");

     fprintf(fp,"    st->print(\"%cs\",reg_str);\n",'%');

     fprintf(fp,"  }\n");

   } else {

     fprintf(fp,"  st->print(\"No format defined for %s\n\");\n", _ident);

     assert( false,"Internal error:\n  output_external_operand() attempting to output other than a Register or Constant");

   }

 }

 void OperandForm::format_constant(FILE *fp, uint const_index, uint const_type) {

   switch(const_type) {

   case Form::idealI: fprintf(fp,"  st->print(\"#%%d\", _c%d);\n", const_index); break;

   case Form::idealP: fprintf(fp,"  if (_c%d) _c%d->dump_on(st);\n", const_index, const_index); break;

   case Form::idealNKlass:

   case Form::idealN: fprintf(fp,"  if (_c%d) _c%d->dump_on(st);\n", const_index, const_index); break;

   case Form::idealL: fprintf(fp,"  st->print(\"#\" INT64_FORMAT, (int64_t)_c%d);\n", const_index); break;

   case Form::idealF: fprintf(fp,"  st->print(\"#%%f\", _c%d);\n", const_index); break;

   case Form::idealD: fprintf(fp,"  st->print(\"#%%f\", _c%d);\n", const_index); break;

   default:

     assert( false, "ShouldNotReachHere()");

   }

 }

 // Return the operand form corresponding to the given index, else NULL.

 OperandForm *OperandForm::constant_operand(FormDict &globals,

                                            uint      index) {

   // !!!!!

   // Check behavior on complex operands

   uint n_consts = num_consts(globals);

   if( n_consts > 0 ) {

     uint i = 0;

     const char *type;

     Component  *comp;

     _components.reset();

     if ((comp = _components.iter()) == NULL) {

       assert(n_consts == 1, "Bad component list detected.\n");

       // Current operand is THE operand

       if ( index == 0 ) {

         return this;

       }

     } // end if NULL

     else {

       // Skip the first component, it can not be a DEF of a constant

       do {

         type = comp->base_type(globals);

         // Check that "type" is a 'ConI', 'ConP', ...

         if ( ideal_to_const_type(type) != Form::none ) {

           // When at correct component, get corresponding Operand

           if ( index == 0 ) {

             return globals[comp->_type]->is_operand();

           }

           // Decrement number of constants to go

           --index;

         }

       } while((comp = _components.iter()) != NULL);

     }

   }

   // Did not find a constant for this index.

   return NULL;

 }

 // If this operand has a single ideal type, return its type

 Form::DataType OperandForm::simple_type(FormDict &globals) const {

   const char *type_name = ideal_type(globals);

   Form::DataType type   = type_name ? ideal_to_const_type( type_name )

                                     : Form::none;

   return type;

 }

 Form::DataType OperandForm::is_base_constant(FormDict &globals) const {

   if ( _matrule == NULL )    return Form::none;

   return _matrule->is_base_constant(globals);

 }

 // "true" if this operand is a simple type that is swallowed

 bool  OperandForm::swallowed(FormDict &globals) const {

   Form::DataType type   = simple_type(globals);

   if( type != Form::none ) {

     return true;

   }

   return false;

 }

 // Output code to access the value of the index'th constant

 void OperandForm::access_constant(FILE *fp, FormDict &globals,

                                   uint const_index) {

   OperandForm *oper = constant_operand(globals, const_index);

   assert( oper, "Index exceeds number of constants in operand");

   Form::DataType dtype = oper->is_base_constant(globals);

   switch(dtype) {

   case idealI: fprintf(fp,"_c%d",           const_index); break;

   case idealP: fprintf(fp,"_c%d->get_con()",const_index); break;

   case idealL: fprintf(fp,"_c%d",           const_index); break;

   case idealF: fprintf(fp,"_c%d",           const_index); break;

   case idealD: fprintf(fp,"_c%d",           const_index); break;

   default:

     assert( false, "ShouldNotReachHere()");

   }

 }

 void OperandForm::dump() {

   output(stderr);

 }

 void OperandForm::output(FILE *fp) {

   fprintf(fp,"\nOperand: %s\n", (_ident?_ident:""));

   if (_matrule)    _matrule->dump();

   if (_interface)  _interface->dump();

   if (_attribs)    _attribs->dump();

   if (_predicate)  _predicate->dump();

   if (_constraint) _constraint->dump();

   if (_construct)  _construct->dump();

   if (_format)     _format->dump();

 }

 //------------------------------Constraint-------------------------------------

 Constraint::Constraint(const char *func, const char *arg)

   : _func(func), _arg(arg) {

 }

 Constraint::~Constraint() { /* not owner of char* */

 }