diff options
| -rw-r--r-- | lib/CodeGen/AggressiveAntiDepBreaker.cpp | 687 | ||||
| -rw-r--r-- | lib/CodeGen/AggressiveAntiDepBreaker.h | 136 | ||||
| -rw-r--r-- | lib/CodeGen/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | lib/CodeGen/PostRASchedulerList.cpp | 8 |
4 files changed, 829 insertions, 3 deletions
diff --git a/lib/CodeGen/AggressiveAntiDepBreaker.cpp b/lib/CodeGen/AggressiveAntiDepBreaker.cpp new file mode 100644 index 0000000000..0fb15eae0d --- /dev/null +++ b/lib/CodeGen/AggressiveAntiDepBreaker.cpp @@ -0,0 +1,687 @@ +//===----- AggressiveAntiDepBreaker.cpp - Anti-dep breaker -------- ---------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the AggressiveAntiDepBreaker class, which +// implements register anti-dependence breaking during post-RA +// scheduling. It attempts to break all anti-dependencies within a +// block. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "aggressive-antidep" +#include "AggressiveAntiDepBreaker.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineFrameInfo.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/Target/TargetInstrInfo.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" + +using namespace llvm; + +AggressiveAntiDepBreaker:: +AggressiveAntiDepBreaker(MachineFunction& MFi) : + AntiDepBreaker(), MF(MFi), + MRI(MF.getRegInfo()), + TRI(MF.getTarget().getRegisterInfo()), + AllocatableSet(TRI->getAllocatableSet(MF)), + GroupNodes(TargetRegisterInfo::FirstVirtualRegister, 0) +{ +} + +AggressiveAntiDepBreaker::~AggressiveAntiDepBreaker() { +} + +void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) { + // Initialize all registers to be in their own group. Initially we + // assign the register to the same-indexed GroupNode. + for (unsigned i = 0; i < TargetRegisterInfo::FirstVirtualRegister; ++i) + GroupNodeIndices[i] = i; + + // Initialize the indices to indicate that no registers are live. + std::fill(KillIndices, array_endof(KillIndices), ~0u); + std::fill(DefIndices, array_endof(DefIndices), BB->size()); + + bool IsReturnBlock = (!BB->empty() && BB->back().getDesc().isReturn()); + + // 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; + 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; + UnionGroups(AliasReg, 0); + KillIndices[AliasReg] = BB->size(); + DefIndices[AliasReg] = ~0u; + } + } + } else { + // In a non-return block, examine the live-in regs of all successors. + for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), + SE = BB->succ_end(); SI != SE; ++SI) + for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), + E = (*SI)->livein_end(); I != E; ++I) { + unsigned Reg = *I; + 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; + 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 + // callee-saved register that is not saved in the prolog. + const MachineFrameInfo *MFI = MF.getFrameInfo(); + BitVector Pristine = MFI->getPristineRegs(BB); + for (const unsigned *I = TRI->getCalleeSavedRegs(); *I; ++I) { + unsigned Reg = *I; + if (!IsReturnBlock && !Pristine.test(Reg)) continue; + 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; + UnionGroups(AliasReg, 0); + KillIndices[AliasReg] = BB->size(); + DefIndices[AliasReg] = ~0u; + } + } +} + +void AggressiveAntiDepBreaker::FinishBlock() { + RegRefs.clear(); +} + +void AggressiveAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count, + unsigned InsertPosIndex) { + assert(Count < InsertPosIndex && "Instruction index out of expected range!"); + + DEBUG(errs() << "Observe: "); + DEBUG(MI->dump()); + + for (unsigned Reg = 0; Reg != TargetRegisterInfo::FirstVirtualRegister; ++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 + // has been scheduled). If it is not live but was defined in the + // previous schedule region, then set its def index to the most + // conservative location (i.e. the beginning of the previous + // schedule region). + if (IsLive(Reg)) { + DEBUG(if (GetGroup(Reg) != 0) + errs() << " " << TRI->getName(Reg) << "=g" << + GetGroup(Reg) << "->g0(region live-out)"); + UnionGroups(Reg, 0); + } else if ((DefIndices[Reg] < InsertPosIndex) && (DefIndices[Reg] >= Count)) { + DefIndices[Reg] = Count; + } + } + + std::set<unsigned> PassthruRegs; + GetPassthruRegs(MI, PassthruRegs); + PrescanInstruction(MI, Count, PassthruRegs); + ScanInstruction(MI, Count); +} + +unsigned AggressiveAntiDepBreaker::GetGroup(unsigned Reg) +{ + unsigned Node = GroupNodeIndices[Reg]; + while (GroupNodes[Node] != Node) + Node = GroupNodes[Node]; + + return Node; +} + +void AggressiveAntiDepBreaker::GetGroupRegs(unsigned Group, std::vector<unsigned> &Regs) +{ + for (unsigned Reg = 0; Reg != TargetRegisterInfo::FirstVirtualRegister; ++Reg) { + if (GetGroup(Reg) == Group) + Regs.push_back(Reg); + } +} + +unsigned AggressiveAntiDepBreaker::UnionGroups(unsigned Reg1, unsigned Reg2) +{ + assert(GroupNodes[0] == 0 && "GroupNode 0 not parent!"); + assert(GroupNodeIndices[0] == 0 && "Reg 0 not in Group 0!"); + + // find group for each register + unsigned Group1 = GetGroup(Reg1); + unsigned Group2 = GetGroup(Reg2); + + // if either group is 0, then that must become the parent + unsigned Parent = (Group1 == 0) ? Group1 : Group2; + unsigned Other = (Parent == Group1) ? Group2 : Group1; + GroupNodes.at(Other) = Parent; + return Parent; +} + +unsigned AggressiveAntiDepBreaker::LeaveGroup(unsigned Reg) +{ + // Create a new GroupNode for Reg. Reg's existing GroupNode must + // stay as is because there could be other GroupNodes referring to + // it. + unsigned idx = GroupNodes.size(); + GroupNodes.push_back(idx); + GroupNodeIndices[Reg] = idx; + return idx; +} + +bool AggressiveAntiDepBreaker::IsLive(unsigned Reg) +{ + // KillIndex must be defined and DefIndex not defined for a register + // to be live. + return((KillIndices[Reg] != ~0u) && (DefIndices[Reg] == ~0u)); +} + +bool AggressiveAntiDepBreaker::IsImplicitDefUse(MachineInstr *MI, + MachineOperand& MO) +{ + if (!MO.isReg() || !MO.isImplicit()) + return false; + + unsigned Reg = MO.getReg(); + if (Reg == 0) + return false; + + MachineOperand *Op = NULL; + if (MO.isDef()) + Op = MI->findRegisterUseOperand(Reg, true); + else + Op = MI->findRegisterDefOperand(Reg); + + return((Op != NULL) && Op->isImplicit()); +} + +void AggressiveAntiDepBreaker::GetPassthruRegs(MachineInstr *MI, + std::set<unsigned>& PassthruRegs) { + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg()) continue; + if ((MO.isDef() && MI->isRegTiedToUseOperand(i)) || + IsImplicitDefUse(MI, MO)) { + const unsigned Reg = MO.getReg(); + PassthruRegs.insert(Reg); + for (const unsigned *Subreg = TRI->getSubRegisters(Reg); + *Subreg; ++Subreg) { + PassthruRegs.insert(*Subreg); + } + } + } +} + +/// AntiDepPathStep - Return SUnit that SU has an anti-dependence on. +static void AntiDepPathStep(SUnit *SU, std::vector<SDep*>& Edges) { + SmallSet<unsigned, 8> Dups; + for (SUnit::pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); + P != PE; ++P) { + if (P->getKind() == SDep::Anti) { + unsigned Reg = P->getReg(); + if (Dups.count(Reg) == 0) { + Edges.push_back(&*P); + Dups.insert(Reg); + } + } + } +} + +void AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr *MI, unsigned Count, + std::set<unsigned>& PassthruRegs) { + // Scan the register defs for this instruction and update + // live-ranges, groups and RegRefs. + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg() || !MO.isDef()) continue; + unsigned Reg = MO.getReg(); + if (Reg == 0) continue; + // Ignore passthru registers for liveness... + if (PassthruRegs.count(Reg) != 0) continue; + + // Update Def for Reg and subregs. + DefIndices[Reg] = Count; + for (const unsigned *Subreg = TRI->getSubRegisters(Reg); + *Subreg; ++Subreg) { + unsigned SubregReg = *Subreg; + DefIndices[SubregReg] = Count; + } + } + + DEBUG(errs() << "\tDef Groups:"); + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg() || !MO.isDef()) continue; + unsigned Reg = MO.getReg(); + if (Reg == 0) continue; + + DEBUG(errs() << " " << TRI->getName(Reg) << "=g" << GetGroup(Reg)); + + // If MI's defs have 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()) { + DEBUG(if (GetGroup(Reg) != 0) errs() << "->g0(alloc-req)"); + UnionGroups(Reg, 0); + } + + // Any aliased that are live at this point are completely or + // partially defined here, so group those subregisters with Reg. + for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { + unsigned AliasReg = *Alias; + if (IsLive(AliasReg)) { + UnionGroups(Reg, AliasReg); + DEBUG(errs() << "->g" << GetGroup(Reg) << "(via " << + TRI->getName(AliasReg) << ")"); + } + } + + // Note register reference... + const TargetRegisterClass *RC = NULL; + if (i < MI->getDesc().getNumOperands()) + RC = MI->getDesc().OpInfo[i].getRegClass(TRI); + RegisterReference RR = { &MO, RC }; + RegRefs.insert(std::make_pair(Reg, RR)); + } + + DEBUG(errs() << '\n'); +} + +void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr *MI, + unsigned Count) { + DEBUG(errs() << "\tUse Groups:"); + + // Scan the register uses for this instruction and update + // live-ranges, groups and RegRefs. + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg() || !MO.isUse()) continue; + unsigned Reg = MO.getReg(); + if (Reg == 0) continue; + + DEBUG(errs() << " " << TRI->getName(Reg) << "=g" << GetGroup(Reg)); + + // It wasn't previously live but now it is, this is a kill. Forget + // the previous live-range information and start a new live-range + // for the register. + if (!IsLive(Reg)) { + KillIndices[Reg] = Count; + DefIndices[Reg] = ~0u; + RegRefs.erase(Reg); + LeaveGroup(Reg); + DEBUG(errs() << "->g" << GetGroup(Reg) << "(last-use)"); + } + // Repeat, for subregisters. + for (const unsigned *Subreg = TRI->getSubRegisters(Reg); + *Subreg; ++Subreg) { + unsigned SubregReg = *Subreg; + if (!IsLive(SubregReg)) { + KillIndices[SubregReg] = Count; + DefIndices[SubregReg] = ~0u; + RegRefs.erase(SubregReg); + LeaveGroup(SubregReg); + DEBUG(errs() << " " << TRI->getName(SubregReg) << "->g" << + GetGroup(SubregReg) << "(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()) { + DEBUG(if (GetGroup(Reg) != 0) errs() << "->g0(alloc-req)"); + UnionGroups(Reg, 0); + } + + // Note register reference... + const TargetRegisterClass *RC = NULL; + if (i < MI->getDesc().getNumOperands()) + RC = MI->getDesc().OpInfo[i].getRegClass(TRI); + RegisterReference RR = { &MO, RC }; + RegRefs.insert(std::make_pair(Reg, RR)); + } + + DEBUG(errs() << '\n'); + + // Form a group of all defs and uses of a KILL instruction to ensure + // that all registers are renamed as a group. + if (MI->getOpcode() == TargetInstrInfo::KILL) { + DEBUG(errs() << "\tKill Group:"); + + unsigned FirstReg = 0; + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg()) continue; + unsigned Reg = MO.getReg(); + if (Reg == 0) continue; + + if (FirstReg != 0) { + DEBUG(errs() << "=" << TRI->getName(Reg)); + UnionGroups(FirstReg, Reg); + } else { + DEBUG(errs() << " " << TRI->getName(Reg)); + FirstReg = Reg; + } + } + + DEBUG(errs() << "->g" << GetGroup(FirstReg) << '\n'); + } +} + +BitVector AggressiveAntiDepBreaker::GetRenameRegisters(unsigned Reg) { + BitVector BV(TRI->getNumRegs(), false); + bool first = true; + + // Check all references that need rewriting for Reg. For each, use + // the corresponding register class to narrow the set of registers + // that are appropriate for renaming. + std::pair<std::multimap<unsigned, RegisterReference>::iterator, + std::multimap<unsigned, RegisterReference>::iterator> + Range = RegRefs.equal_range(Reg); + for (std::multimap<unsigned, RegisterReference>::iterator + Q = Range.first, QE = Range.second; Q != QE; ++Q) { + const TargetRegisterClass *RC = Q->second.RC; + if (RC == NULL) continue; + + BitVector RCBV = TRI->getAllocatableSet(MF, RC); + if (first) { + BV |= RCBV; + first = false; + } else { + BV &= RCBV; + } + + DEBUG(errs() << " " << RC->getName()); + } + + return BV; +} + +bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters( + unsigned AntiDepGroupIndex, + std::map<unsigned, unsigned> &RenameMap) { + // Collect all registers in the same group as AntiDepReg. These all + // need to be renamed together if we are to break the + // anti-dependence. + std::vector<unsigned> Regs; + GetGroupRegs(AntiDepGroupIndex, Regs); + assert(Regs.size() > 0 && "Empty register group!"); + if (Regs.size() == 0) + return false; + + // Find the "superest" register in the group. At the same time, + // collect the BitVector of registers that can be used to rename + // each register. + DEBUG(errs() << "\tRename Candidates for Group g" << AntiDepGroupIndex << ":\n"); + std::map<unsigned, BitVector> RenameRegisterMap; + unsigned SuperReg = 0; + for (unsigned i = 0, e = Regs.size(); i != e; ++i) { + unsigned Reg = Regs[i]; + if ((SuperReg == 0) || TRI->isSuperRegister(SuperReg, Reg)) + SuperReg = Reg; + + // If Reg has any references, then collect possible rename regs + if (RegRefs.count(Reg) > 0) { + DEBUG(errs() << "\t\t" << TRI->getName(Reg) << ":"); + + BitVector BV = GetRenameRegisters(Reg); + RenameRegisterMap.insert(std::pair<unsigned, BitVector>(Reg, BV)); + + DEBUG(errs() << " ::"); + DEBUG(for (int r = BV.find_first(); r != -1; r = BV.find_next(r)) + errs() << " " << TRI->getName(r)); + DEBUG(errs() << "\n"); + } + } + + // All group registers should be a subreg of SuperReg. + for (unsigned i = 0, e = Regs.size(); i != e; ++i) { + unsigned Reg = Regs[i]; + if (Reg == SuperReg) continue; + bool IsSub = TRI->isSubRegister(SuperReg, Reg); + assert(IsSub && "Expecting group subregister"); + if (!IsSub) + return false; + } + + // FIXME: for now just handle single register in group case... + if (Regs.size() > 1) + return false; + + // Check each possible rename register for SuperReg. If that register + // is available, and the corresponding registers are available for + // the other group subregisters, then we can use those registers to + // rename. + DEBUG(errs() << "\tFind Register:"); + BitVector SuperBV = RenameRegisterMap[SuperReg]; + for (int r = SuperBV.find_first(); r != -1; r = SuperBV.find_next(r)) { + const unsigned Reg = (unsigned)r; + // Don't replace a register with itself. + if (Reg == SuperReg) continue; + + DEBUG(errs() << " " << TRI->getName(Reg)); + + // If Reg is dead and Reg's most recent def is not before + // SuperRegs's kill, it's safe to replace SuperReg with + // Reg. We must also check all subregisters of Reg. + if (IsLive(Reg) || (KillIndices[SuperReg] > DefIndices[Reg])) { + DEBUG(errs() << "(live)"); + continue; + } else { + bool found = false; + for (const unsigned *Subreg = TRI->getSubRegisters(Reg); + *Subreg; ++Subreg) { + unsigned SubregReg = *Subreg; + if (IsLive(SubregReg) || (KillIndices[SuperReg] > DefIndices[SubregReg])) { + DEBUG(errs() << "(subreg " << TRI->getName(SubregReg) << " live)"); + found = true; + break; + } + } + if (found) + continue; + } + + if (Reg != 0) { + DEBUG(errs() << '\n'); + RenameMap.insert(std::pair<unsigned, unsigned>(SuperReg, Reg)); + return true; + } + } + + DEBUG(errs() << '\n'); + + // No registers are free and available! + return false; +} + +/// BreakAntiDependencies - Identifiy anti-dependencies within the +/// ScheduleDAG and break them by renaming registers. +/// +unsigned AggressiveAntiDepBreaker::BreakAntiDependencies(std::vector<SUnit>& SUnits, + MachineBasicBlock::iterator& Begin, + MachineBasicBlock::iterator& End, + unsigned InsertPosIndex) { + // The code below assumes that there is at least one instruction, + // so just duck out immediately if the block is empty. + if (SUnits.empty()) return false; + + // ...need a map from MI to SUnit. + std::map<MachineInstr *, SUnit *> MISUnitMap; + + DEBUG(errs() << "Breaking all anti-dependencies\n"); + for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { + SUnit *SU = &SUnits[i]; + MISUnitMap.insert(std::pair<MachineInstr *, SUnit *>(SU->getInstr(), SU)); + } + +#ifndef NDEBUG + { + DEBUG(errs() << "Available regs:"); + for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) { + if (!IsLive(Reg)) + DEBUG(errs() << " " << TRI->getName(Reg)); + } + DEBUG(errs() << '\n'); + } +#endif + + // Attempt to break anti-dependence edges. Walk the instructions + // from the bottom up, tracking information about liveness as we go + // to help determine which registers are available. + unsigned Broken = 0; + unsigned Count = InsertPosIndex - 1; + for (MachineBasicBlock::iterator I = End, E = Begin; + I != E; --Count) { + MachineInstr *MI = --I; + + DEBUG(errs() << "Anti: "); + DEBUG(MI->dump()); + + std::set<unsigned> PassthruRegs; + GetPassthruRegs(MI, PassthruRegs); + + // Process the defs in MI... + PrescanInstruction(MI, Count, PassthruRegs); + + std::vector<SDep*> Edges; + SUnit *PathSU = MISUnitMap[MI]; + if (PathSU) + AntiDepPathStep(PathSU, Edges); + + // Ignore KILL instructions (they form a group in ScanInstruction + // but don't cause any anti-dependence breaking themselves) + if (MI->getOpcode() != TargetInstrInfo::KILL) { + // Attempt to break each anti-dependency... + for (unsigned i = 0, e = Edges.size(); i != e; ++i) { + SDep *Edge = Edges[i]; + SUnit *NextSU = Edge->getSUnit(); + + if (Edge->getKind() != SDep::Anti) continue; + + unsigned AntiDepReg = Edge->getReg(); + DEBUG(errs() << "\tAntidep reg: " << TRI->getName(AntiDepReg)); + assert(AntiDepReg != 0 && "Anti-dependence on reg0?"); + + if (!AllocatableSet.test(AntiDepReg)) { + // Don't break anti-dependencies on non-allocatable registers. + DEBUG(errs() << " (non-allocatable)\n"); + continue; + } else if (PassthruRegs.count(AntiDepReg) != 0) { + // If the anti-dep register liveness "passes-thru", then + // don't try to change it. It will be changed along with + // the use if required to break an earlier antidep. + DEBUG(errs() << " (passthru)\n"); + continue; + } else { + // No anti-dep breaking for implicit deps + MachineOperand *AntiDepOp = MI->findRegisterDefOperand(AntiDepReg); + assert(AntiDepOp != NULL && "Can't find index for defined register operand"); + if ((AntiDepOp == NULL) || AntiDepOp->isImplicit()) { + DEBUG(errs() << " (implicit)\n"); + continue; + } + + // If the SUnit has other dependencies on the SUnit that + // it anti-depends on, don't bother breaking the + // anti-dependency since those edges would prevent such + // units from being scheduled past each other + // regardless. + for (SUnit::pred_iterator P = PathSU->Preds.begin(), + PE = PathSU->Preds.end(); P != PE; ++P) { + if ((P->getSUnit() == NextSU) && (P->getKind() != SDep::Anti)) { + DEBUG(errs() << " (real dependency)\n"); + AntiDepReg = 0; + break; + } + } + + if (AntiDepReg == 0) continue; + } + + assert(AntiDepReg != 0); + if (AntiDepReg == 0) continue; + + // Determine AntiDepReg's register group. + const unsigned GroupIndex = GetGroup(AntiDepReg); + if (GroupIndex == 0) { + DEBUG(errs() << " (zero group)\n"); + continue; + } + + DEBUG(errs() << '\n'); + + // Look for a suitable register to use to break the anti-dependence. + std::map<unsigned, unsigned> RenameMap; + if (FindSuitableFreeRegisters(GroupIndex, RenameMap)) { + DEBUG(errs() << "\tBreaking anti-dependence edge on " + << TRI->getName(AntiDepReg) << ":"); + + // Handle each group register... + for (std::map<unsigned, unsigned>::iterator + S = RenameMap.begin(), E = RenameMap.end(); S != E; ++S) { + unsigned CurrReg = S->first; + unsigned NewReg = S->second; + + DEBUG(errs() << " " << TRI->getName(CurrReg) << "->" << + TRI->getName(NewReg) << "(" << + RegRefs.count(CurrReg) << " refs)"); + + // Update the references to the old register CurrReg to + // refer to the new register NewReg. + std::pair<std::multimap<unsigned, RegisterReference>::iterator, + std::multimap<unsigned, RegisterReference>::iterator> + Range = RegRefs.equal_range(CurrReg); + for (std::multimap<unsigned, RegisterReference>::iterator + Q = Range.first, QE = Range.second; Q != QE; ++Q) { + Q->second.Operand->setReg(NewReg); + } + + // We just went back in time and modified history; the + // liveness information for CurrReg is now inconsistent. Set + // the state as if it were dead. + UnionGroups(NewReg, 0); + RegRefs.erase(NewReg); + DefIndices[NewReg] = DefIndices[CurrReg]; + KillIndices[NewReg] = KillIndices[CurrReg]; + + UnionGroups(CurrReg, 0); + RegRefs.erase(CurrReg); + DefIndices[CurrReg] = KillIndices[CurrReg]; + KillIndices[CurrReg] = ~0u; + assert(((KillIndices[CurrReg] == ~0u) != + (DefIndices[CurrReg] == ~0u)) && + "Kill and Def maps aren't consistent for AntiDepReg!"); + } + + ++Broken; + DEBUG(errs() << '\n'); + } + } + } + + ScanInstruction(MI, Count); + } + + return Broken; +} diff --git a/lib/CodeGen/AggressiveAntiDepBreaker.h b/lib/CodeGen/AggressiveAntiDepBreaker.h new file mode 100644 index 0000000000..e6b7268e77 --- /dev/null +++ b/lib/CodeGen/AggressiveAntiDepBreaker.h @@ -0,0 +1,136 @@ +//=- llvm/CodeGen/AggressiveAntiDepBreaker.h - Anti-Dep Support -*- C++ -*-=// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the AggressiveAntiDepBreaker class, which +// implements register anti-dependence breaking during post-RA +// scheduling. It attempts to break all anti-dependencies within a +// block. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H +#define LLVM_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H + +#include "llvm/CodeGen/AntiDepBreaker.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineFrameInfo.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/ScheduleDAG.h" +#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/SmallSet.h" + +namespace llvm { + class AggressiveAntiDepBreaker : public AntiDepBreaker { + MachineFunction& MF; + MachineRegisterInfo &MRI; + const TargetRegisterInfo *TRI; + + /// RegisterReference - Information about a register reference + /// within a liverange + typedef struct { + /// Operand - The registers operand + MachineOperand *Operand; + /// RC - The register class + const TargetRegisterClass *RC; + } RegisterReference; + + /// AllocatableSet - The set of allocatable registers. + /// We'll be ignoring anti-dependencies on non-allocatable registers, + /// because they may not be safe to break. + const BitVector AllocatableSet; + + /// GroupNodes - Implements a disjoint-union data structure to + /// form register groups. A node is represented by an index into + /// the vector. A node can "point to" itself to indicate that it + /// is the parent of a group, or point to another node to indicate + /// that it is a member of the same group as that node. + std::vector<unsigned> GroupNodes; + + /// GroupNodeIndices - For each register, the index of the GroupNode + /// currently representing the group that the register belongs to. + /// Register 0 is always represented by the 0 group, a group + /// composed of registers that are not eligible for anti-aliasing. + unsigned GroupNodeIndices[TargetRegisterInfo::FirstVirtualRegister]; + + /// RegRegs - Map registers to all their references within a live range. + std::multimap<unsigned, RegisterReference> RegRefs; + + /// KillIndices - The index of the most recent kill (proceding bottom-up), + /// or ~0u if the register is not live. + unsigned KillIndices[TargetRegisterInfo::FirstVirtualRegister]; + + /// DefIndices - The index of the most recent complete def (proceding bottom + /// up), or ~0u if the register is live. + unsigned DefIndices[TargetRegisterInfo::FirstVirtualRegister]; + + public: + AggressiveAntiDepBreaker(MachineFunction& MFi); + ~AggressiveAntiDepBreaker(); + + /// Start - Initialize anti-dep breaking for a new basic block. + void StartBlock(MachineBasicBlock *BB); + + /// BreakAntiDependencies - Identifiy anti-dependencies along the critical path + /// of the ScheduleDAG and break them by renaming registers. + /// + unsigned BreakAntiDependencies(std::vector<SUnit>& SUnits, + MachineBasicBlock::iterator& Begin, + MachineBasicBlock::iterator& End, + unsigned InsertPosIndex); + + /// Observe - Update liveness information to account for the current + /// instruction, which will not be scheduled. + /// + void Observe(MachineInstr *MI, unsigned Count, unsigned InsertPosIndex); + + /// Finish - Finish anti-dep breaking for a basic block. + void FinishBlock(); + + private: + // GetGroup - Get the group for a register. The returned value is + // the index of the GroupNode representing the group. + unsigned GetGroup(unsigned Reg); + + // GetGroupRegs - Return a vector of the registers belonging to a + // group. + void GetGroupRegs(unsigned Group, std::vector<unsigned> &Regs); + + // UnionGroups - Union Reg1's and Reg2's groups to form a new + // group. Return the index of the GroupNode representing the + // group. + unsigned UnionGroups(unsigned Reg1, unsigned Reg2); + + // LeaveGroup - Remove a register from its current group and place + // it alone in its own group. Return the index of the GroupNode + // representing the registers new group. + unsigned LeaveGroup(unsigned Reg); + + /// IsLive - Return true if Reg is live + bool IsLive(unsigned Reg); + + /// IsImplicitDefUse - Return true if MO represents a register + /// that is both implicitly used and defined in MI + bool IsImplicitDefUse(MachineInstr *MI, MachineOperand& MO); + + /// GetPassthruRegs - If MI implicitly def/uses a register, then + /// return that register and all subregisters. + void GetPassthruRegs(MachineInstr *MI, std::set<unsigned>& PassthruRegs); + + void PrescanInstruction(MachineInstr *MI, unsigned Count, + std::set<unsigned>& PassthruRegs); + void ScanInstruction(MachineInstr *MI, unsigned Count); + BitVector GetRenameRegisters(unsigned Reg); + bool FindSuitableFreeRegisters(unsigned AntiDepGroupIndex, + std::map<unsigned, unsigned> &RenameMap); + }; +} + +#endif diff --git a/lib/CodeGen/CMakeLists.txt b/lib/CodeGen/CMakeLists.txt index 14b215ec07..416f4ba014 100644 --- a/lib/CodeGen/CMakeLists.txt +++ b/lib/CodeGen/CMakeLists.txt @@ -1,4 +1,5 @@ add_llvm_library(LLVMCodeGen + AggressiveAntiDepBreaker.cpp BranchFolding.cpp CodePlacementOpt.cpp CriticalAntiDepBreaker.cpp diff --git a/lib/CodeGen/PostRASchedulerList.cpp b/lib/CodeGen/PostRASchedulerList.cpp index ea66f02a4b..4ee97e79b5 100644 --- a/lib/CodeGen/PostRASchedulerList.cpp +++ b/lib/CodeGen/PostRASchedulerList.cpp @@ -19,6 +19,7 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "post-RA-sched" +#include "AggressiveAntiDepBreaker.h" #include "CriticalAntiDepBreaker.h" #include "ExactHazardRecognizer.h" #include "SimpleHazardRecognizer.h" @@ -236,9 +237,10 @@ bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { (ScheduleHazardRecognizer *)new ExactHazardRecognizer(InstrItins) : (ScheduleHazardRecognizer *)new SimpleHazardRecognizer(); AntiDepBreaker *ADB = - (AntiDepMode == TargetSubtarget::ANTIDEP_ALL) ? NULL /* FIXME */ : - (AntiDepMode == TargetSubtarget::ANTIDEP_CRITICAL) ? - new CriticalAntiDepBreaker(Fn) : NULL; + ((AntiDepMode == TargetSubtarget::ANTIDEP_ALL) ? + (AntiDepBreaker *)new AggressiveAntiDepBreaker(Fn) : + ((AntiDepMode == TargetSubtarget::ANTIDEP_CRITICAL) ? + (AntiDepBreaker *)new CriticalAntiDepBreaker(Fn) : NULL)); SchedulePostRATDList Scheduler(Fn, MLI, MDT, HR, ADB, AA); |