From ae4bcd7566752af5a15a40026c39a92da3eadec4 Mon Sep 17 00:00:00 2001 From: Ruchira Sasanka Date: Sat, 10 Nov 2001 21:20:43 +0000 Subject: [PATCH] Corrected reodering code for instructions inserted before calls git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@1252 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Target/SparcV9/SparcV9Internals.h | 29 ++- lib/Target/SparcV9/SparcV9RegInfo.cpp | 306 +++++++++++++++----------- 2 files changed, 210 insertions(+), 125 deletions(-) diff --git a/lib/Target/SparcV9/SparcV9Internals.h b/lib/Target/SparcV9/SparcV9Internals.h index ad04eb3ee73..27debf716d9 100644 --- a/lib/Target/SparcV9/SparcV9Internals.h +++ b/lib/Target/SparcV9/SparcV9Internals.h @@ -271,6 +271,22 @@ class UltraSparcRegInfo : public MachineRegInfo } + int getRegType(int reg) const { + if( reg < 32 ) + return IntRegType; + else if ( reg < (32 + 32) ) + return FPSingleRegType; + else if ( reg < (64 + 32) ) + return FPDoubleRegType; + else if( reg < (64+32+4) ) + return FloatCCRegType; + else if( reg < (64+32+4+2) ) + return IntCCRegType; + else + assert(0 && "Invalid register number in getRegType"); + } + + // ***TODO: See this method is necessary @@ -284,8 +300,19 @@ class UltraSparcRegInfo : public MachineRegInfo MachineInstr * cpCCR2IntMI(const unsigned IntReg) const; MachineInstr * cpInt2CCRMI(const unsigned IntReg) const; + + + void moveInst2OrdVec(vector &OrdVec, MachineInstr *UnordInst, + PhyRegAlloc &PRA ) const; + void OrderAddedInstrns( vector &UnordVec, - vector &OrdVec) const; + vector &OrdVec, + PhyRegAlloc &PRA) const; + + + + + public: diff --git a/lib/Target/SparcV9/SparcV9RegInfo.cpp b/lib/Target/SparcV9/SparcV9RegInfo.cpp index 7cdd80bd918..5ac0a556bfb 100644 --- a/lib/Target/SparcV9/SparcV9RegInfo.cpp +++ b/lib/Target/SparcV9/SparcV9RegInfo.cpp @@ -741,16 +741,16 @@ void UltraSparcRegInfo::colorCallArgs(const MachineInstr *const CallMI, if( ! AddedInstrnsBefore.empty() ) { - if( DEBUG_RA) { + if( DEBUG_RA ) { cerr << "\nCalling reorder with instrns: \n"; for(unsigned i=0; i < AddedInstrnsBefore.size(); i++) cerr << *(AddedInstrnsBefore[i]); } vector TmpVec; - OrderAddedInstrns(AddedInstrnsBefore, TmpVec); + OrderAddedInstrns(AddedInstrnsBefore, TmpVec, PRA); - if( DEBUG_RA) { + if( DEBUG_RA ) { cerr << "\nAfter reordering instrns: \n"; for(unsigned i=0; i < TmpVec.size(); i++) cerr << *(TmpVec[i]); @@ -1007,7 +1007,7 @@ MachineInstr * UltraSparcRegInfo::cpMem2RegMI(const unsigned SrcPtrReg, MI->SetMachineOperand(0, SrcPtrReg, false); MI->SetMachineOperand(1, MachineOperand:: MO_SignExtendedImmed, (int64_t) Offset, false); - MI->SetMachineOperand(2, DestReg, false); + MI->SetMachineOperand(2, DestReg, true); break; case FPSingleRegType: @@ -1015,7 +1015,7 @@ MachineInstr * UltraSparcRegInfo::cpMem2RegMI(const unsigned SrcPtrReg, MI->SetMachineOperand(0, SrcPtrReg, false); MI->SetMachineOperand(1, MachineOperand:: MO_SignExtendedImmed, (int64_t) Offset, false); - MI->SetMachineOperand(2, DestReg, false); + MI->SetMachineOperand(2, DestReg, true); break; @@ -1024,14 +1024,14 @@ MachineInstr * UltraSparcRegInfo::cpMem2RegMI(const unsigned SrcPtrReg, MI->SetMachineOperand(0, SrcPtrReg, false); MI->SetMachineOperand(1, MachineOperand:: MO_SignExtendedImmed, (int64_t) Offset, false); - MI->SetMachineOperand(2, DestReg, false); + MI->SetMachineOperand(2, DestReg, true); break; case IntCCRegType: assert( 0 && "Cannot directly load into %ccr from memory"); default: - assert(0 && "Unknow RegType in cpMem2RegMI"); + assert(0 && "Unknown RegType in cpMem2RegMI"); } return MI; @@ -1090,8 +1090,9 @@ void UltraSparcRegInfo::insertCallerSavingCode(const MachineInstr *MInst, LiveRange *RetValLR = PRA.LRI.getLiveRangeForValue( RetVal ); assert( RetValLR && "No LR for RetValue of call"); - PushedRegSet.insert( - getUnifiedRegNum((RetValLR->getRegClass())->getID(), + if( RetValLR->hasColor()) + PushedRegSet.insert( + getUnifiedRegNum((RetValLR->getRegClass())->getID(), RetValLR->getColor() ) ); } @@ -1312,17 +1313,24 @@ void UltraSparcRegInfo::printReg(const LiveRange *const LR) { // 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 suhc instruction MUST have -// their USES BEFORE THE DEFS. +// 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. + +// All the uses are before THE def to a register + + //--------------------------------------------------------------------------- void UltraSparcRegInfo::OrderAddedInstrns( vector &UnordVec, - vector &OrdVec) const{ + vector &OrdVec, + PhyRegAlloc &PRA) const{ /* Problem: We can have instructions inserted by RegAlloc like @@ -1330,176 +1338,226 @@ void UltraSparcRegInfo::OrderAddedInstrns( vector &UnordVec, 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: - - Round 1: - For each instruction 'Inst' in UnordVec, starting from UnordVec.begin, - let Def be the destination reg of instr. - For each use 'Use' of the following instruction - If Def==Use continue - If no use is found, push back 'Inst' to OrdVec - - If no inst is left in UnordVec by the end of Round1, return - - Round 2: - For each inst 'Inst' left in UnordVec - For each use 'Use' in Inst - If threre is NO Def for this Use in an inst in OrdVec - push back Inst - Else - push_front a stack save instr mem location "Loc" - push_back a restore inst to load to Use from Loc - discard Inst (assert that one operand is %g0) + 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 = true; + bool CouldMoveAll; + bool DebugPrint = false; - vector::iterator DefIt = UnordVec.begin(); + do { - for( ; DefIt != UnordVec.end(); ++DefIt ) { + CouldMoveAll = true; - // for each instruction in the UnordVec do ... + vector::iterator DefIt = UnordVec.begin(); - MachineInstr *DefInst = *DefIt; + for( ; DefIt != UnordVec.end(); ++DefIt ) { - // cerr << "\nDefInst = " << *DefInst; + // for each instruction in the UnordVec do ... - for(unsigned OpNumD=0; OpNumD < DefInst->getNumOperands(); ++OpNumD) { + MachineInstr *DefInst = *DefIt; - MachineOperand& DefOp = DefInst->getOperand(OpNumD); + 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; - + vector::iterator UseIt = DefIt; UseIt++; - + for( ; UseIt != UnordVec.end(); ++UseIt ) { - // for each inst (UseInst) that is below the DefInst do ... - MachineInstr *UseInst = *UseIt; + if( UseInst == NULL) continue; + + // for each inst (UseInst) that is below the DefInst do ... + - for(unsigned OpNumU=0; OpNumU < UseInst->getNumOperands(); ++OpNumU){ - - MachineOperand& UseOp = UseInst->getOperand(OpNumU); - - 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 - - DefEqUse = true; - CouldMoveAll = false; - - cerr << "\nReordered Ins (Moved up): " << *UseInst; - break; + 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; - } // if two registers are equal + 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 - } // if use is a register + // cerr << "Moved to Ord: " << *DefInst; - } // for all uses + moveInst2OrdVec(OrdVec, DefInst, PRA); - }// for all use instructions + //OrdVec.push_back(DefInst); - if( ! DefEqUse ) { - // cerr << "\nMoved Inst = " << *DefInst; - OrdVec.push_back(DefInst); + // mark the pos of DefInst with NULL to indicate that it is + // empty *DefIt = NULL; } - else - break; // exit the loop since we can't move DefInst - + } // if Def is a machine register + + } // for all instructions in the UnordVec + - } // for all Defs in DefInst (there should be only 1) - - } // for all instructions in the UnordVec + } while( !CouldMoveAll); - if( CouldMoveAll ) { - assert( (UnordVec.size() == OrdVec.size()) && - "Different Vec Sizes after reordering"); - return; + if(DebugPrint) { + cerr << "\nAdded instructions were reordered to:\n"; + for(unsigned int i=0; i < OrdVec.size(); i++) + cerr << *(OrdVec[i]); } +} - // We are here because there were two instructions like: - // 1. add %ox %g0 %oy - // 2. add %oy %g0 %oz, where z!=x or z==x - // and hence we could not move 1 to the OrdVec - // cerr << "\nCaution: Added instructions will be RE-ORDERED !@!@!"; - vector< MachineInstr *>::iterator UnordIt = UnordVec.begin(); - for( ; UnordIt != UnordVec.end(); ++UnordIt ) { - MachineInstr *UnordInst = *UnordIt; - if( UnordInst == NULL ) continue; - for(unsigned OpNumU=0; OpNumU < UnordInst->getNumOperands(); ++OpNumU) { - MachineOperand& UseOp = UnordInst->getOperand(OpNumU); - if( ! UseOp.opIsDef() && - UseOp.getOperandType() == MachineOperand::MO_MachineRegister) { +void UltraSparcRegInfo::moveInst2OrdVec(vector &OrdVec, + MachineInstr *UnordInst, + PhyRegAlloc &PRA ) const { - if( UseOp.getMachineRegNum() == getZeroRegNum() ) - continue; + MachineOperand& UseOp = UnordInst->getOperand(0); - // for all uses of UnordInst - bool DefEqUse = false; + if( ! UseOp.opIsDef() && + UseOp.getOperandType() == MachineOperand::MO_MachineRegister) { - vector::iterator OrdIt = OrdVec.begin(); - - for( ; OrdIt != OrdVec.end(); ++OrdIt ) { - - MachineInstr *OrdInst = *OrdIt ; + // for the use of UnordInst, see whether there is a defining instr + // before in the OrdVec + bool DefEqUse = false; - for(unsigned OpNumO=0; OpNumO < OrdInst->getNumOperands(); ++OpNumO){ + vector::iterator OrdIt = OrdVec.begin(); + + for( ; OrdIt != OrdVec.end(); ++OrdIt ) { - MachineOperand& DefOp = OrdInst->getOperand(OpNumO); + MachineInstr *OrdInst = *OrdIt ; - if( DefOp.opIsDef() && - DefOp.getOperandType() == MachineOperand::MO_MachineRegister) { + MachineOperand& DefOp = + OrdInst->getOperand(OrdInst->getNumOperands()-1); - if( DefOp.getMachineRegNum() == UseOp.getMachineRegNum() ) { + if( DefOp.opIsDef() && + DefOp.getOperandType() == MachineOperand::MO_MachineRegister) { - DefEqUse = true; - assert(0 && "Insert save/restre code for reordering"); + //cerr << "\nDefining Ord Inst: " << *OrdInst; + + if( DefOp.getMachineRegNum() == UseOp.getMachineRegNum() ) { + + // we are here because there is a preceding def in the OrdVec + // for the use in this intr we are going to insert. This + // happened because the original code was like: + // 1. add %ox %g0 %oy + // 2. add %oy %g0 %ox + // In Round1, we added 2 to OrdVec but 1 remained in UnordVec + // Now we are processing %ox of 1. + // We have to + + const int UReg = DefOp.getMachineRegNum(); + const int RegType = getRegType(UReg); + MachineInstr *AdIBef, *AdIAft; + + // TODO: Change 8 below + const int StackOff = PRA.mcInfo.pushTempValue(target, 8); + + // Save the UReg (%ox) on stack before it's destroyed + AdIBef=cpReg2MemMI(UReg, getStackPointer(), StackOff, RegType); + OrdIt = OrdVec.insert( OrdIt, AdIBef); + OrdIt++; // points to current instr we processed + + // Load directly into DReg (%oy) + MachineOperand& DOp= + (UnordInst->getOperand(UnordInst->getNumOperands()-1)); + assert(DOp.opIsDef() && "Last operand is not the def"); + const int DReg = DOp.getMachineRegNum(); + + AdIAft=cpMem2RegMI(getStackPointer(), StackOff, DReg, RegType); + OrdVec.push_back(AdIAft); + + cerr << "\nFixed CIRCULAR references by reordering"; - } // if two registers are equal + if( DEBUG_RA ) { + cerr << "\nBefore CIRCULAR Reordering:\n"; + cerr << *UnordInst; + cerr << *OrdInst; + + cerr << "\nAfter CIRCULAR Reordering - All Inst so far:\n"; + for(unsigned i=0; i < OrdVec.size(); i++) + cerr << *(OrdVec[i]); + } + + // Do not copy the UseInst to OrdVec + DefEqUse = true; + break; + + }// if two registers are equal - } // if Def is a register + } // if Def is a register - } // for all defs + } // for each instr in OrdVec - } // for each instr in OrdVec + if( !DefEqUse ) { - if( !DefEqUse ) { - OrdVec.push_back( UnordInst ); - cerr << "\nReordered instr (Moved Down): " << *UnordInst; - } + // We didn't find a def in the OrdVec, so just append this inst + OrdVec.push_back( UnordInst ); + //cerr << "Reordered Inst (Moved Dn): " << *UnordInst; + } - } // if the operand in UnordInst is a use + }// if the operand in UnordInst is a use - } // for each use in the UnordInst +} + + + + - } // for each UnordInst in UnordVec -} -- 2.34.1