From a90e77061d52076d9edf09b2f1ae42db04ff14d4 Mon Sep 17 00:00:00 2001 From: Ruchira Sasanka Date: Mon, 15 Oct 2001 16:26:38 +0000 Subject: [PATCH] updated suggesting/coloring of call & return args & implicit operands. Changed added instr to a deque (from a vector) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@831 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/RegAlloc/LiveRangeInfo.cpp | 95 ++++++-------- lib/CodeGen/RegAlloc/PhyRegAlloc.cpp | 122 +++++++++++++++--- lib/Target/SparcV9/RegAlloc/LiveRangeInfo.cpp | 95 ++++++-------- lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp | 122 +++++++++++++++--- 4 files changed, 294 insertions(+), 140 deletions(-) diff --git a/lib/CodeGen/RegAlloc/LiveRangeInfo.cpp b/lib/CodeGen/RegAlloc/LiveRangeInfo.cpp index 242b30cc57b..c137e676b1b 100644 --- a/lib/CodeGen/RegAlloc/LiveRangeInfo.cpp +++ b/lib/CodeGen/RegAlloc/LiveRangeInfo.cpp @@ -108,30 +108,27 @@ void LiveRangeInfo::constructLiveRanges() const MachineInstr * MInst = *MInstIterator; - // Now if the machine instruction has special operands that must be - // set with a "suggested color", do it here. - // This will be true for call/return instructions + // Now if the machine instruction is a call/return instruction, + // add it to CallRetInstrList for processing its implicit operands - - if( MRI.handleSpecialMInstr(MInst, *this, RegClassList) ) - continue; - - + if( (TM.getInstrInfo()).isReturn( MInst->getOpCode()) || + (TM.getInstrInfo()).isCall( MInst->getOpCode()) ) + CallRetInstrList.push_back( MInst ); + + // iterate over MI operands to find defs for( MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done(); ++OpI) { - - // delete later from here ************ - MachineOperand::MachineOperandType OpTyp = - OpI.getMachineOperand().getOperandType(); - - if (DEBUG_RA && OpTyp == MachineOperand::MO_CCRegister) { - cout << "\n**CC reg found. Is Def=" << OpI.isDef() << " Val:"; - printValue( OpI.getMachineOperand().getVRegValue() ); - cout << endl; + if( DEBUG_RA) { + MachineOperand::MachineOperandType OpTyp = + OpI.getMachineOperand().getOperandType(); + + if ( OpTyp == MachineOperand::MO_CCRegister) { + cout << "\n**CC reg found. Is Def=" << OpI.isDef() << " Val:"; + printValue( OpI.getMachineOperand().getVRegValue() ); + cout << endl; + } } - // ************* to here - // create a new LR iff this operand is a def if( OpI.isDef() ) { @@ -193,60 +190,56 @@ void LiveRangeInfo::constructLiveRanges() } } - - - } // if isDef() } // for all opereands in machine instructions } // for all machine instructions in the BB - } // for all BBs in method - // go thru LLVM instructions in the basic block and suggest colors - // for their args. Also record all CALL - // instructions and Return instructions in the CallRetInstrList - // This is done because since there are no reverse pointers in machine - // instructions to find the llvm instruction, when we encounter a call - // or a return whose args must be specailly colored (e.g., %o's for args) - // We have to makes sure that all LRs of call/ret args are added before - // doing this. But return value of call will not have a LR. - BBI = Meth->begin(); // random iterator for BBs + // Now we have to suggest clors for call and return arg live ranges. + // Also, if there are implicit defs (e.g., retun value of a call inst) + // they must be added to the live range list - for( ; BBI != Meth->end(); ++BBI) { // go thru BBs in random order + suggestRegs4CallRets(); - BasicBlock::const_iterator InstIt = (*BBI)->begin(); + if( DEBUG_RA) + cout << "Initial Live Ranges constructed!" << endl; - for( ; InstIt != (*BBI)->end() ; ++InstIt) { +} - const Instruction *const CallRetI = *InstIt; - unsigned OpCode = (CallRetI)->getOpcode(); - - if( (OpCode == Instruction::Call) ) { - CallRetInstrList.push_back(CallRetI ); - MRI.suggestRegs4CallArgs( (CallInst *) CallRetI, *this, RegClassList ); - } - else if (OpCode == Instruction::Ret ) { - CallRetInstrList.push_back( CallRetI ); - MRI.suggestReg4RetValue( (ReturnInst *) CallRetI, *this); - } +// Suggest colors for call and return args. +// Also create new LRs for implicit defs - } // for each llvm instr in BB +void LiveRangeInfo::suggestRegs4CallRets() +{ - } // for all BBs in method + CallRetInstrListType::const_iterator It = CallRetInstrList.begin(); - if( DEBUG_RA) - cout << "Initial Live Ranges constructed!" << endl; + for( ; It != CallRetInstrList.end(); ++It ) { + + const MachineInstr *MInst = *It; + MachineOpCode OpCode = MInst->getOpCode(); + + if( (TM.getInstrInfo()).isReturn(OpCode) ) + MRI.suggestReg4RetValue( MInst, *this); + + else if( (TM.getInstrInfo()).isCall( OpCode ) ) + MRI.suggestRegs4CallArgs( MInst, *this, RegClassList ); + + else + assert( 0 && "Non call/ret instr in CallRetInstrList" ); + } } + void LiveRangeInfo::coalesceLRs() { @@ -318,8 +311,6 @@ void LiveRangeInfo::coalesceLRs() if( RCOfDef == RCOfUse ) { // if the reg classes are the same - // if( LROfUse->getTypeID() == LROfDef->getTypeID() ) { - if( ! RCOfDef->getInterference(LROfDef, LROfUse) ) { unsigned CombinedDegree = diff --git a/lib/CodeGen/RegAlloc/PhyRegAlloc.cpp b/lib/CodeGen/RegAlloc/PhyRegAlloc.cpp index 832e4824e56..e0b55db5090 100644 --- a/lib/CodeGen/RegAlloc/PhyRegAlloc.cpp +++ b/lib/CodeGen/RegAlloc/PhyRegAlloc.cpp @@ -248,6 +248,100 @@ void PhyRegAlloc::addInterferencesForArgs() } +#if 0 +//---------------------------------------------------------------------------- + +//---------------------------------------------------------------------------- + + +void PhyRegAlloc::insertCallerSavingCode(const MachineInstr *MInst, + const BasicBlock *BB ) +{ + assert( (TM.getInstrInfo()).isCall( MInst->getOpCode() ) ); + + int StackOff = 10; // ****TODO : Change + set PushedRegSet(); + + // Now find the LR of the return value of the call + // The last *implicit operand* is the return value of a call + // Insert it to to he PushedRegSet since we must not save that register + // and restore it after the call. + // We do this because, we look at the LV set *after* the instruction + // to determine, which LRs must be saved across calls. The return value + // of the call is live in this set - but we must not save/restore it. + + unsigned NumOfImpRefs = MInst->getNumImplicitRefs(); + if( NumOfImpRefs > 0 ) { + + if( MInst->implicitRefIsDefined(NumOfImpRefs-1) ) { + + const Value *RetVal = CallMI->getImplicitRef(NumOfImpRefs-1); + LiveRange *RetValLR = LRI.getLiveRangeForValue( RetVal ); + assert( RetValLR && "No LR for RetValue of call"); + + PushedRegSet.insert( + MRI.getUnifiedRegNum((RetValLR->getRegClass())->getID(), + RetValLR->getColor() ) ); + } + + } + + + LiveVarSet *LVSetAft = LVI->getLiveVarSetAfterMInst(MInst, BB); + + LiveVarSet::const_iterator LIt = LVSetAft->begin(); + + // for each live var in live variable set after machine inst + for( ; LIt != LVSetAft->end(); ++LIt) { + + // get the live range corresponding to live var + LiveRange *const LR = LRI.getLiveRangeForValue(*LIt ); + + // LROfVar can be null if it is a const since a const + // doesn't have a dominating def - see Assumptions above + if( LR ) { + + if( LR->hasColor() ) { + + unsigned RCID = (LR->getRegClass())->getID(); + unsigned Color = LR->getColor(); + + if ( MRI.isRegVolatile(RCID, Color) ) { + + // if the value is in both LV sets (i.e., live before and after + // the call machine instruction) + + unsigned Reg = MRI.getUnifiedRegNum(RCID, Color); + + if( PuhsedRegSet.find(Reg) == PhusedRegSet.end() ) { + + // if we haven't already pushed that register + + MachineInstr *AdI = + MRI.saveRegOnStackMI(Reg, MRI.getFPReg(), StackOff ); + + ((AddedInstrMap[MInst])->InstrnsBefore).push_front(AdI); + ((AddedInstrMap[MInst])->InstrnsAfter).push_back(AdI); + + + PushedRegSet.insert( Reg ); + StackOff += 4; // ****TODO: Correct ?????? + cout << "Inserted caller saving instr"); + + } // if not already pushed + + } // if LR has a volatile color + + } // if LR has color + + } // if there is a LR for Var + + } // for each value in the LV set after instruction + +} + +#endif + //---------------------------------------------------------------------------- // This method is called after register allocation is complete to set the // allocated reisters in the machine code. This code will add register numbers @@ -275,12 +369,12 @@ void PhyRegAlloc::updateMachineCode() // ***TODO: Add InstrnsAfter as well if( AddedInstrMap[ MInst ] ) { - vector &IBef = + deque &IBef = (AddedInstrMap[MInst])->InstrnsBefore; if( ! IBef.empty() ) { - vector::iterator AdIt; + deque::iterator AdIt; for( AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt ) { @@ -331,7 +425,8 @@ void PhyRegAlloc::updateMachineCode() cout << TargetInstrDescriptors[MInst->getOpCode()].opCodeString; } - Op.setRegForValue( 1000 ); // mark register as invalid + if( Op.getAllocatedRegNum() == -1) + Op.setRegForValue( 1000 ); // mark register as invalid #if 0 if( ((Val->getType())->isLabelType()) || @@ -475,16 +570,9 @@ void PhyRegAlloc::colorCallRetArgs() for( ; It != CallRetInstList.end(); ++It ) { - const Instruction *const CallRetI = *It; - unsigned OpCode = (CallRetI)->getOpcode(); + const MachineInstr *const CRMI = *It; + unsigned OpCode = CRMI->getOpCode(); - const MachineInstr *CRMI = *((CallRetI->getMachineInstrVec()).begin()); - - - assert( (TM.getInstrInfo().isReturn(CRMI->getOpCode()) || - TM.getInstrInfo().isCall(CRMI->getOpCode()) ) - && "First Machine Instruction is not a Call/Retrunr" ); - // get the added instructions for this Call/Ret instruciton AddedInstrns *AI = AddedInstrMap[ CRMI ]; if ( !AI ) { @@ -492,14 +580,12 @@ void PhyRegAlloc::colorCallRetArgs() AddedInstrMap[ CRMI ] = AI; } - if( (OpCode == Instruction::Call) ) - MRI.colorCallArgs( (CallInst *) CallRetI, LRI, AI ); + if( (TM.getInstrInfo()).isCall( OpCode ) ) + MRI.colorCallArgs( CRMI, LRI, AI ); - - else if (OpCode == Instruction::Ret ) - MRI.colorRetValue( (ReturnInst *) CallRetI, LRI, AI ); + else if ( (TM.getInstrInfo()).isReturn(OpCode) ) + MRI.colorRetValue( CRMI, LRI, AI ); - else assert( 0 && "Non Call/Ret instrn in CallRetInstrList\n" ); } diff --git a/lib/Target/SparcV9/RegAlloc/LiveRangeInfo.cpp b/lib/Target/SparcV9/RegAlloc/LiveRangeInfo.cpp index 242b30cc57b..c137e676b1b 100644 --- a/lib/Target/SparcV9/RegAlloc/LiveRangeInfo.cpp +++ b/lib/Target/SparcV9/RegAlloc/LiveRangeInfo.cpp @@ -108,30 +108,27 @@ void LiveRangeInfo::constructLiveRanges() const MachineInstr * MInst = *MInstIterator; - // Now if the machine instruction has special operands that must be - // set with a "suggested color", do it here. - // This will be true for call/return instructions + // Now if the machine instruction is a call/return instruction, + // add it to CallRetInstrList for processing its implicit operands - - if( MRI.handleSpecialMInstr(MInst, *this, RegClassList) ) - continue; - - + if( (TM.getInstrInfo()).isReturn( MInst->getOpCode()) || + (TM.getInstrInfo()).isCall( MInst->getOpCode()) ) + CallRetInstrList.push_back( MInst ); + + // iterate over MI operands to find defs for( MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done(); ++OpI) { - - // delete later from here ************ - MachineOperand::MachineOperandType OpTyp = - OpI.getMachineOperand().getOperandType(); - - if (DEBUG_RA && OpTyp == MachineOperand::MO_CCRegister) { - cout << "\n**CC reg found. Is Def=" << OpI.isDef() << " Val:"; - printValue( OpI.getMachineOperand().getVRegValue() ); - cout << endl; + if( DEBUG_RA) { + MachineOperand::MachineOperandType OpTyp = + OpI.getMachineOperand().getOperandType(); + + if ( OpTyp == MachineOperand::MO_CCRegister) { + cout << "\n**CC reg found. Is Def=" << OpI.isDef() << " Val:"; + printValue( OpI.getMachineOperand().getVRegValue() ); + cout << endl; + } } - // ************* to here - // create a new LR iff this operand is a def if( OpI.isDef() ) { @@ -193,60 +190,56 @@ void LiveRangeInfo::constructLiveRanges() } } - - - } // if isDef() } // for all opereands in machine instructions } // for all machine instructions in the BB - } // for all BBs in method - // go thru LLVM instructions in the basic block and suggest colors - // for their args. Also record all CALL - // instructions and Return instructions in the CallRetInstrList - // This is done because since there are no reverse pointers in machine - // instructions to find the llvm instruction, when we encounter a call - // or a return whose args must be specailly colored (e.g., %o's for args) - // We have to makes sure that all LRs of call/ret args are added before - // doing this. But return value of call will not have a LR. - BBI = Meth->begin(); // random iterator for BBs + // Now we have to suggest clors for call and return arg live ranges. + // Also, if there are implicit defs (e.g., retun value of a call inst) + // they must be added to the live range list - for( ; BBI != Meth->end(); ++BBI) { // go thru BBs in random order + suggestRegs4CallRets(); - BasicBlock::const_iterator InstIt = (*BBI)->begin(); + if( DEBUG_RA) + cout << "Initial Live Ranges constructed!" << endl; - for( ; InstIt != (*BBI)->end() ; ++InstIt) { +} - const Instruction *const CallRetI = *InstIt; - unsigned OpCode = (CallRetI)->getOpcode(); - - if( (OpCode == Instruction::Call) ) { - CallRetInstrList.push_back(CallRetI ); - MRI.suggestRegs4CallArgs( (CallInst *) CallRetI, *this, RegClassList ); - } - else if (OpCode == Instruction::Ret ) { - CallRetInstrList.push_back( CallRetI ); - MRI.suggestReg4RetValue( (ReturnInst *) CallRetI, *this); - } +// Suggest colors for call and return args. +// Also create new LRs for implicit defs - } // for each llvm instr in BB +void LiveRangeInfo::suggestRegs4CallRets() +{ - } // for all BBs in method + CallRetInstrListType::const_iterator It = CallRetInstrList.begin(); - if( DEBUG_RA) - cout << "Initial Live Ranges constructed!" << endl; + for( ; It != CallRetInstrList.end(); ++It ) { + + const MachineInstr *MInst = *It; + MachineOpCode OpCode = MInst->getOpCode(); + + if( (TM.getInstrInfo()).isReturn(OpCode) ) + MRI.suggestReg4RetValue( MInst, *this); + + else if( (TM.getInstrInfo()).isCall( OpCode ) ) + MRI.suggestRegs4CallArgs( MInst, *this, RegClassList ); + + else + assert( 0 && "Non call/ret instr in CallRetInstrList" ); + } } + void LiveRangeInfo::coalesceLRs() { @@ -318,8 +311,6 @@ void LiveRangeInfo::coalesceLRs() if( RCOfDef == RCOfUse ) { // if the reg classes are the same - // if( LROfUse->getTypeID() == LROfDef->getTypeID() ) { - if( ! RCOfDef->getInterference(LROfDef, LROfUse) ) { unsigned CombinedDegree = diff --git a/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp b/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp index 832e4824e56..e0b55db5090 100644 --- a/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp +++ b/lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp @@ -248,6 +248,100 @@ void PhyRegAlloc::addInterferencesForArgs() } +#if 0 +//---------------------------------------------------------------------------- + +//---------------------------------------------------------------------------- + + +void PhyRegAlloc::insertCallerSavingCode(const MachineInstr *MInst, + const BasicBlock *BB ) +{ + assert( (TM.getInstrInfo()).isCall( MInst->getOpCode() ) ); + + int StackOff = 10; // ****TODO : Change + set PushedRegSet(); + + // Now find the LR of the return value of the call + // The last *implicit operand* is the return value of a call + // Insert it to to he PushedRegSet since we must not save that register + // and restore it after the call. + // We do this because, we look at the LV set *after* the instruction + // to determine, which LRs must be saved across calls. The return value + // of the call is live in this set - but we must not save/restore it. + + unsigned NumOfImpRefs = MInst->getNumImplicitRefs(); + if( NumOfImpRefs > 0 ) { + + if( MInst->implicitRefIsDefined(NumOfImpRefs-1) ) { + + const Value *RetVal = CallMI->getImplicitRef(NumOfImpRefs-1); + LiveRange *RetValLR = LRI.getLiveRangeForValue( RetVal ); + assert( RetValLR && "No LR for RetValue of call"); + + PushedRegSet.insert( + MRI.getUnifiedRegNum((RetValLR->getRegClass())->getID(), + RetValLR->getColor() ) ); + } + + } + + + LiveVarSet *LVSetAft = LVI->getLiveVarSetAfterMInst(MInst, BB); + + LiveVarSet::const_iterator LIt = LVSetAft->begin(); + + // for each live var in live variable set after machine inst + for( ; LIt != LVSetAft->end(); ++LIt) { + + // get the live range corresponding to live var + LiveRange *const LR = LRI.getLiveRangeForValue(*LIt ); + + // LROfVar can be null if it is a const since a const + // doesn't have a dominating def - see Assumptions above + if( LR ) { + + if( LR->hasColor() ) { + + unsigned RCID = (LR->getRegClass())->getID(); + unsigned Color = LR->getColor(); + + if ( MRI.isRegVolatile(RCID, Color) ) { + + // if the value is in both LV sets (i.e., live before and after + // the call machine instruction) + + unsigned Reg = MRI.getUnifiedRegNum(RCID, Color); + + if( PuhsedRegSet.find(Reg) == PhusedRegSet.end() ) { + + // if we haven't already pushed that register + + MachineInstr *AdI = + MRI.saveRegOnStackMI(Reg, MRI.getFPReg(), StackOff ); + + ((AddedInstrMap[MInst])->InstrnsBefore).push_front(AdI); + ((AddedInstrMap[MInst])->InstrnsAfter).push_back(AdI); + + + PushedRegSet.insert( Reg ); + StackOff += 4; // ****TODO: Correct ?????? + cout << "Inserted caller saving instr"); + + } // if not already pushed + + } // if LR has a volatile color + + } // if LR has color + + } // if there is a LR for Var + + } // for each value in the LV set after instruction + +} + +#endif + //---------------------------------------------------------------------------- // This method is called after register allocation is complete to set the // allocated reisters in the machine code. This code will add register numbers @@ -275,12 +369,12 @@ void PhyRegAlloc::updateMachineCode() // ***TODO: Add InstrnsAfter as well if( AddedInstrMap[ MInst ] ) { - vector &IBef = + deque &IBef = (AddedInstrMap[MInst])->InstrnsBefore; if( ! IBef.empty() ) { - vector::iterator AdIt; + deque::iterator AdIt; for( AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt ) { @@ -331,7 +425,8 @@ void PhyRegAlloc::updateMachineCode() cout << TargetInstrDescriptors[MInst->getOpCode()].opCodeString; } - Op.setRegForValue( 1000 ); // mark register as invalid + if( Op.getAllocatedRegNum() == -1) + Op.setRegForValue( 1000 ); // mark register as invalid #if 0 if( ((Val->getType())->isLabelType()) || @@ -475,16 +570,9 @@ void PhyRegAlloc::colorCallRetArgs() for( ; It != CallRetInstList.end(); ++It ) { - const Instruction *const CallRetI = *It; - unsigned OpCode = (CallRetI)->getOpcode(); + const MachineInstr *const CRMI = *It; + unsigned OpCode = CRMI->getOpCode(); - const MachineInstr *CRMI = *((CallRetI->getMachineInstrVec()).begin()); - - - assert( (TM.getInstrInfo().isReturn(CRMI->getOpCode()) || - TM.getInstrInfo().isCall(CRMI->getOpCode()) ) - && "First Machine Instruction is not a Call/Retrunr" ); - // get the added instructions for this Call/Ret instruciton AddedInstrns *AI = AddedInstrMap[ CRMI ]; if ( !AI ) { @@ -492,14 +580,12 @@ void PhyRegAlloc::colorCallRetArgs() AddedInstrMap[ CRMI ] = AI; } - if( (OpCode == Instruction::Call) ) - MRI.colorCallArgs( (CallInst *) CallRetI, LRI, AI ); + if( (TM.getInstrInfo()).isCall( OpCode ) ) + MRI.colorCallArgs( CRMI, LRI, AI ); - - else if (OpCode == Instruction::Ret ) - MRI.colorRetValue( (ReturnInst *) CallRetI, LRI, AI ); + else if ( (TM.getInstrInfo()).isReturn(OpCode) ) + MRI.colorRetValue( CRMI, LRI, AI ); - else assert( 0 && "Non Call/Ret instrn in CallRetInstrList\n" ); } -- 2.34.1