X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FAggressiveAntiDepBreaker.cpp;h=b520d8fcedc0e0493d578960072a63d8135dc457;hb=98d9648de7d571b2e6d139b65961a70d1833b0d7;hp=4008a6a63cf802e6dbec37645dfef1b1add2b037;hpb=66db3a0f10e96ae190c8a46a1a8d5242928d068c;p=oota-llvm.git diff --git a/lib/CodeGen/AggressiveAntiDepBreaker.cpp b/lib/CodeGen/AggressiveAntiDepBreaker.cpp index 4008a6a63cf..b520d8fcedc 100644 --- a/lib/CodeGen/AggressiveAntiDepBreaker.cpp +++ b/lib/CodeGen/AggressiveAntiDepBreaker.cpp @@ -21,6 +21,7 @@ #include "llvm/CodeGen/MachineInstr.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" @@ -40,8 +41,11 @@ DebugMod("agg-antidep-debugmod", AggressiveAntiDepState::AggressiveAntiDepState(const unsigned TargetRegs, MachineBasicBlock *BB) : - NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0) { - + NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0), + GroupNodeIndices(TargetRegs, 0), + KillIndices(TargetRegs, 0), + DefIndices(TargetRegs, 0) +{ const unsigned BBSize = BB->size(); for (unsigned i = 0; i < NumTargetRegs; ++i) { // Initialize all registers to be in their own group. Initially we @@ -53,8 +57,7 @@ AggressiveAntiDepState::AggressiveAntiDepState(const unsigned TargetRegs, } } -unsigned AggressiveAntiDepState::GetGroup(unsigned Reg) -{ +unsigned AggressiveAntiDepState::GetGroup(unsigned Reg) { unsigned Node = GroupNodeIndices[Reg]; while (GroupNodes[Node] != Node) Node = GroupNodes[Node]; @@ -114,6 +117,7 @@ AggressiveAntiDepBreaker(MachineFunction& MFi, TargetSubtarget::RegClassVector& CriticalPathRCs) : AntiDepBreaker(), MF(MFi), MRI(MF.getRegInfo()), + TII(MF.getTarget().getInstrInfo()), TRI(MF.getTarget().getRegisterInfo()), AllocatableSet(TRI->getAllocatableSet(MF)), State(NULL) { @@ -143,45 +147,37 @@ void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) { State = new AggressiveAntiDepState(TRI->getNumRegs(), BB); bool IsReturnBlock = (!BB->empty() && BB->back().getDesc().isReturn()); - unsigned *KillIndices = State->GetKillIndices(); - unsigned *DefIndices = State->GetDefIndices(); + std::vector &KillIndices = State->GetKillIndices(); + std::vector &DefIndices = State->GetDefIndices(); // Determine the live-out physregs for this block. if (IsReturnBlock) { // In a return block, examine the function live-out regs. for (MachineRegisterInfo::liveout_iterator I = MRI.liveout_begin(), E = MRI.liveout_end(); I != E; ++I) { - unsigned Reg = *I; - State->UnionGroups(Reg, 0); - KillIndices[Reg] = BB->size(); - DefIndices[Reg] = ~0u; - // Repeat, for all aliases. - for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { - unsigned AliasReg = *Alias; - State->UnionGroups(AliasReg, 0); - KillIndices[AliasReg] = BB->size(); - DefIndices[AliasReg] = ~0u; + for (const unsigned *Alias = TRI->getOverlaps(*I); + unsigned Reg = *Alias; ++Alias) { + State->UnionGroups(Reg, 0); + KillIndices[Reg] = BB->size(); + DefIndices[Reg] = ~0u; } } - } else { - // In a non-return block, examine the live-in regs of all successors. - for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), + } + + // In a non-return block, examine the live-in regs of all successors. + // Note a return block can have successors if the return instruction is + // predicated. + for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), SE = BB->succ_end(); SI != SE; ++SI) - for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), + for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), E = (*SI)->livein_end(); I != E; ++I) { - unsigned Reg = *I; + for (const unsigned *Alias = TRI->getOverlaps(*I); + unsigned Reg = *Alias; ++Alias) { State->UnionGroups(Reg, 0); KillIndices[Reg] = BB->size(); DefIndices[Reg] = ~0u; - // Repeat, for all aliases. - for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { - unsigned AliasReg = *Alias; - State->UnionGroups(AliasReg, 0); - KillIndices[AliasReg] = BB->size(); - DefIndices[AliasReg] = ~0u; - } } - } + } // Mark live-out callee-saved registers. In a return block this is // all callee-saved registers. In non-return this is any @@ -191,12 +187,8 @@ void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) { for (const unsigned *I = TRI->getCalleeSavedRegs(); *I; ++I) { unsigned Reg = *I; if (!IsReturnBlock && !Pristine.test(Reg)) continue; - State->UnionGroups(Reg, 0); - KillIndices[Reg] = BB->size(); - DefIndices[Reg] = ~0u; - // Repeat, for all aliases. - for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { - unsigned AliasReg = *Alias; + for (const unsigned *Alias = TRI->getOverlaps(Reg); + unsigned AliasReg = *Alias; ++Alias) { State->UnionGroups(AliasReg, 0); KillIndices[AliasReg] = BB->size(); DefIndices[AliasReg] = ~0u; @@ -222,7 +214,7 @@ void AggressiveAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count, DEBUG(MI->dump()); DEBUG(dbgs() << "\tRegs:"); - unsigned *DefIndices = State->GetDefIndices(); + std::vector &DefIndices = State->GetDefIndices(); for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg) { // If Reg is current live, then mark that it can't be renamed as // we don't know the extent of its live-range anymore (now that it @@ -324,8 +316,8 @@ void AggressiveAntiDepBreaker::HandleLastUse(unsigned Reg, unsigned KillIdx, const char *tag, const char *header, const char *footer) { - unsigned *KillIndices = State->GetKillIndices(); - unsigned *DefIndices = State->GetDefIndices(); + std::vector &KillIndices = State->GetKillIndices(); + std::vector &DefIndices = State->GetDefIndices(); std::multimap& RegRefs = State->GetRegRefs(); @@ -360,7 +352,7 @@ void AggressiveAntiDepBreaker::HandleLastUse(unsigned Reg, unsigned KillIdx, void AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr *MI, unsigned Count, std::set& PassthruRegs) { - unsigned *DefIndices = State->GetDefIndices(); + std::vector &DefIndices = State->GetDefIndices(); std::multimap& RegRefs = State->GetRegRefs(); @@ -390,7 +382,8 @@ void AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr *MI, // If MI's defs have a special allocation requirement, don't allow // any def registers to be changed. Also assume all registers // defined in a call must not be changed (ABI). - if (MI->getDesc().isCall() || MI->getDesc().hasExtraDefRegAllocReq()) { + if (MI->getDesc().isCall() || MI->getDesc().hasExtraDefRegAllocReq() || + TII->isPredicated(MI)) { DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)"); State->UnionGroups(Reg, 0); } @@ -428,12 +421,9 @@ void AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr *MI, continue; // Update def for Reg and aliases. - DefIndices[Reg] = Count; - for (const unsigned *Alias = TRI->getAliasSet(Reg); - *Alias; ++Alias) { - unsigned AliasReg = *Alias; + for (const unsigned *Alias = TRI->getOverlaps(Reg); + unsigned AliasReg = *Alias; ++Alias) DefIndices[AliasReg] = Count; - } } } @@ -443,6 +433,26 @@ void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr *MI, std::multimap& RegRefs = State->GetRegRefs(); + // If MI's uses have special allocation requirement, don't allow + // any use registers to be changed. Also assume all registers + // used in a call must not be changed (ABI). + // FIXME: The issue with predicated instruction is more complex. We are being + // conservatively here because the kill markers cannot be trusted after + // if-conversion: + // %R6 = LDR %SP, %reg0, 92, pred:14, pred:%reg0; mem:LD4[FixedStack14] + // ... + // STR %R0, %R6, %reg0, 0, pred:0, pred:%CPSR; mem:ST4[%395] + // %R6 = LDR %SP, %reg0, 100, pred:0, pred:%CPSR; mem:LD4[FixedStack12] + // STR %R0, %R6, %reg0, 0, pred:14, pred:%reg0; mem:ST4[%396](align=8) + // + // The first R6 kill is not really a kill since it's killed by a predicated + // instruction which may not be executed. The second R6 def may or may not + // re-define R6 so it's not safe to change it since the last R6 use cannot be + // changed. + bool Special = MI->getDesc().isCall() || + MI->getDesc().hasExtraSrcRegAllocReq() || + TII->isPredicated(MI); + // Scan the register uses for this instruction and update // live-ranges, groups and RegRefs. for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { @@ -459,10 +469,7 @@ void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr *MI, // for the register. HandleLastUse(Reg, Count, "(last-use)"); - // If MI's uses have special allocation requirement, don't allow - // any use registers to be changed. Also assume all registers - // used in a call must not be changed (ABI). - if (MI->getDesc().isCall() || MI->getDesc().hasExtraSrcRegAllocReq()) { + if (Special) { DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)"); State->UnionGroups(Reg, 0); } @@ -538,8 +545,8 @@ bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters( unsigned AntiDepGroupIndex, RenameOrderType& RenameOrder, std::map &RenameMap) { - unsigned *KillIndices = State->GetKillIndices(); - unsigned *DefIndices = State->GetDefIndices(); + std::vector &KillIndices = State->GetKillIndices(); + std::vector &DefIndices = State->GetDefIndices(); std::multimap& RegRefs = State->GetRegRefs(); @@ -604,8 +611,12 @@ bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters( // order. If that register is available, and the corresponding // registers are available for the other group subregisters, then we // can use those registers to rename. + + // FIXME: Using getMinimalPhysRegClass is very conservative. We should + // check every use of the register and find the largest register class + // that can be used in all of them. const TargetRegisterClass *SuperRC = - TRI->getPhysicalRegisterRegClass(SuperReg, MVT::Other); + TRI->getMinimalPhysRegClass(SuperReg, MVT::Other); const TargetRegisterClass::iterator RB = SuperRC->allocation_order_begin(MF); const TargetRegisterClass::iterator RE = SuperRC->allocation_order_end(MF); @@ -626,6 +637,8 @@ bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters( if (R == RB) R = RE; --R; const unsigned NewSuperReg = *R; + // Don't consider non-allocatable registers + if (!AllocatableSet.test(NewSuperReg)) continue; // Don't replace a register with itself. if (NewSuperReg == SuperReg) continue; @@ -707,8 +720,8 @@ unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned InsertPosIndex) { - unsigned *KillIndices = State->GetKillIndices(); - unsigned *DefIndices = State->GetDefIndices(); + std::vector &KillIndices = State->GetKillIndices(); + std::vector &DefIndices = State->GetDefIndices(); std::multimap& RegRefs = State->GetRegRefs(); @@ -905,6 +918,19 @@ unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( AggressiveAntiDepState::RegisterReference>::iterator Q = Range.first, QE = Range.second; Q != QE; ++Q) { Q->second.Operand->setReg(NewReg); + // If the SU for the instruction being updated has debug + // information related to the anti-dependency register, make + // sure to update that as well. + const SUnit *SU = MISUnitMap[Q->second.Operand->getParent()]; + if (!SU) continue; + for (unsigned i = 0, e = SU->DbgInstrList.size() ; i < e ; ++i) { + MachineInstr *DI = SU->DbgInstrList[i]; + assert (DI->getNumOperands()==3 && DI->getOperand(0).isReg() && + DI->getOperand(0).getReg() + && "Non register dbg_value attached to SUnit!"); + if (DI->getOperand(0).getReg() == AntiDepReg) + DI->getOperand(0).setReg(NewReg); + } } // We just went back in time and modified history; the