+}
+
+//---------------------------------------------------------------------------
+// This method examines instructions inserted by RegAlloc code before a
+// machine instruction to detect invalid orders that destroy values before
+// they are used. If it detects such conditions, it reorders the instructions.
+//
+// The unordered instructions come in the UnordVec. These instructions are
+// instructions inserted by RegAlloc. All such instruction MUST have
+// their USES BEFORE THE DEFS after reordering.
+//
+// The UnordVec & OrdVec must be DISTINCT. The OrdVec must be empty when
+// this method is called.
+//
+// This method uses two vectors for efficiency in accessing
+//
+// Since instructions are inserted in RegAlloc, this assumes that the
+// first operand is the source reg and the last operand is the dest reg.
+// It also does not consider operands that are both use and def.
+//
+// All the uses are before THE def to a register
+//---------------------------------------------------------------------------
+
+void UltraSparcRegInfo::OrderAddedInstrns(std::vector<MachineInstr*> &UnordVec,
+ std::vector<MachineInstr*> &OrdVec,
+ PhyRegAlloc &PRA) const{
+
+ /*
+ Problem: We can have instructions inserted by RegAlloc like
+ 1. add %ox %g0 %oy
+ 2. add %oy %g0 %oz, where z!=x or z==x
+
+ This is wrong since %oy used by 2 is overwritten by 1
+
+ Solution:
+ We re-order the instructions so that the uses are before the defs
+
+ Algorithm:
+
+ do
+ for each instruction 'DefInst' in the UnOrdVec
+ for each instruction 'UseInst' that follows the DefInst
+ if the reg defined by DefInst is used by UseInst
+ mark DefInst as not movable in this iteration
+ If DefInst is not marked as not-movable, move DefInst to OrdVec
+ while all instructions in DefInst are moved to OrdVec
+
+ For moving, we call the move2OrdVec(). It checks whether there is a def
+ in it for the uses in the instruction to be added to OrdVec. If there
+ are no preceding defs, it just appends the instruction. If there is a
+ preceding def, it puts two instructions to save the reg on stack before
+ the load and puts a restore at use.
+
+ */
+
+ bool CouldMoveAll;
+ bool DebugPrint = false;
+
+ do {
+ CouldMoveAll = true;
+ std::vector<MachineInstr *>::iterator DefIt = UnordVec.begin();
+
+ for( ; DefIt != UnordVec.end(); ++DefIt ) {
+
+ // for each instruction in the UnordVec do ...
+
+ MachineInstr *DefInst = *DefIt;
+
+ if( DefInst == NULL) continue;
+
+ //cerr << "\nInst in UnordVec = " << *DefInst;
+
+ // last operand is the def (unless for a store which has no def reg)
+ MachineOperand& DefOp = DefInst->getOperand(DefInst->getNumOperands()-1);
+
+ if( DefOp.opIsDef() &&
+ DefOp.getOperandType() == MachineOperand::MO_MachineRegister) {
+
+ // If the operand in DefInst is a def ...
+
+ bool DefEqUse = false;
+
+ std::vector<MachineInstr *>::iterator UseIt = DefIt;
+ UseIt++;
+
+ for( ; UseIt != UnordVec.end(); ++UseIt ) {
+
+ MachineInstr *UseInst = *UseIt;
+ if( UseInst == NULL) continue;
+
+ // for each inst (UseInst) that is below the DefInst do ...
+ MachineOperand& UseOp = UseInst->getOperand(0);
+
+ if( ! UseOp.opIsDef() &&
+ UseOp.getOperandType() == MachineOperand::MO_MachineRegister) {
+
+ // if use is a register ...
+
+ if( DefOp.getMachineRegNum() == UseOp.getMachineRegNum() ) {
+
+ // if Def and this use are the same, it means that this use
+ // is destroyed by a def before it is used
+
+ // cerr << "\nCouldn't move " << *DefInst;
+
+ DefEqUse = true;
+ CouldMoveAll = false;
+ DebugPrint = true;
+ break;
+ } // if two registers are equal
+
+ } // if use is a register
+
+ }// for all use instructions
+
+ if( ! DefEqUse ) {
+
+ // after examining all the instructions that follow the DefInst
+ // if there are no dependencies, we can move it to the OrdVec
+
+ // cerr << "Moved to Ord: " << *DefInst;
+
+ moveInst2OrdVec(OrdVec, DefInst, PRA);
+
+ //OrdVec.push_back(DefInst);
+
+ // mark the pos of DefInst with NULL to indicate that it is
+ // empty
+ *DefIt = NULL;
+ }
+
+ } // if Def is a machine register
+
+ } // for all instructions in the UnordVec
+
+
+ } while(!CouldMoveAll);
+
+ if (DebugPrint && DEBUG_RA) {
+ cerr << "\nAdded instructions were reordered to:\n";
+ for(unsigned int i=0; i < OrdVec.size(); i++)
+ cerr << *(OrdVec[i]);