X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FExecutionDepsFix.cpp;h=dd508b3e5e328a7cbdad6e759c3345db8218f78b;hb=e903f64b10dc61461b135425460efb63346f0fed;hp=26db8027aa91da6af33fd43df0df271f50cceead;hpb=4ba844388c586ee40871a52dc9d6eab883fde1b7;p=oota-llvm.git diff --git a/lib/CodeGen/ExecutionDepsFix.cpp b/lib/CodeGen/ExecutionDepsFix.cpp index 26db8027aa9..dd508b3e5e3 100644 --- a/lib/CodeGen/ExecutionDepsFix.cpp +++ b/lib/CodeGen/ExecutionDepsFix.cpp @@ -20,9 +20,9 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "execution-fix" #include "llvm/CodeGen/Passes.h" #include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/iterator_range.h" #include "llvm/CodeGen/LivePhysRegs.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineRegisterInfo.h" @@ -30,9 +30,12 @@ #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetSubtargetInfo.h" + using namespace llvm; +#define DEBUG_TYPE "execution-fix" + /// A DomainValue is a bit like LiveIntervals' ValNo, but it also keeps track /// of execution domains. /// @@ -72,6 +75,9 @@ struct DomainValue { // Is domain available? bool hasDomain(unsigned domain) const { + assert(domain < + static_cast(std::numeric_limits::digits) && + "undefined behavior"); return AvailableDomains & (1u << domain); } @@ -104,10 +110,10 @@ struct DomainValue { Instrs.clear(); } }; -} +} // namespace namespace { -/// LiveReg - Information about a live register. +/// Information about a live register. struct LiveReg { /// Value currently in this register, or NULL when no value is being tracked. /// This counts as a DomainValue reference. @@ -119,7 +125,7 @@ struct LiveReg { /// will be a negative number. int Def; }; -} // anonynous namespace +} // anonymous namespace namespace { class ExeDepsFix : public MachineFunctionPass { @@ -131,7 +137,7 @@ class ExeDepsFix : public MachineFunctionPass { MachineFunction *MF; const TargetInstrInfo *TII; const TargetRegisterInfo *TRI; - std::vector AliasMap; + std::vector> AliasMap; const unsigned NumRegs; LiveReg *LiveRegs; typedef DenseMap LiveOutMap; @@ -167,8 +173,8 @@ public: } private: - // Register mapping. - int regIndex(unsigned Reg); + iterator_range::const_iterator> + regIndices(unsigned Reg) const; // DomainValue allocation. DomainValue *alloc(int domain = -1); @@ -195,15 +201,17 @@ private: bool shouldBreakDependence(MachineInstr*, unsigned OpIdx, unsigned Pref); void processUndefReads(MachineBasicBlock*); }; -} +} // namespace char ExeDepsFix::ID = 0; -/// Translate TRI register number to an index into our smaller tables of -/// interesting registers. Return -1 for boring registers. -int ExeDepsFix::regIndex(unsigned Reg) { +/// Translate TRI register number to a list of indices into our smaller tables +/// of interesting registers. +iterator_range::const_iterator> +ExeDepsFix::regIndices(unsigned Reg) const { assert(Reg < AliasMap.size() && "Invalid register"); - return AliasMap[Reg]; + const auto &Entry = AliasMap[Reg]; + return make_range(Entry.begin(), Entry.end()); } DomainValue *ExeDepsFix::alloc(int domain) { @@ -217,7 +225,7 @@ DomainValue *ExeDepsFix::alloc(int domain) { return dv; } -/// release - Release a reference to DV. When the last reference is released, +/// Release a reference to DV. When the last reference is released, /// collapse if needed. void ExeDepsFix::release(DomainValue *DV) { while (DV) { @@ -237,8 +245,8 @@ void ExeDepsFix::release(DomainValue *DV) { } } -/// resolve - Follow the chain of dead DomainValues until a live DomainValue is -/// reached. Update the referenced pointer when necessary. +/// Follow the chain of dead DomainValues until a live DomainValue is reached. +/// Update the referenced pointer when necessary. DomainValue *ExeDepsFix::resolve(DomainValue *&DVRef) { DomainValue *DV = DVRef; if (!DV || !DV->Next) @@ -317,8 +325,7 @@ void ExeDepsFix::collapse(DomainValue *dv, unsigned domain) { setLiveReg(rx, alloc(domain)); } -/// Merge - All instructions and registers in B are moved to A, and B is -/// released. +/// All instructions and registers in B are moved to A, and B is released. bool ExeDepsFix::merge(DomainValue *A, DomainValue *B) { assert(!A->isCollapsed() && "Cannot merge into collapsed"); assert(!B->isCollapsed() && "Cannot merge from collapsed"); @@ -336,13 +343,15 @@ bool ExeDepsFix::merge(DomainValue *A, DomainValue *B) { // All uses of B are referred to A. B->Next = retain(A); - for (unsigned rx = 0; rx != NumRegs; ++rx) + for (unsigned rx = 0; rx != NumRegs; ++rx) { + assert(LiveRegs && "no space allocated for live registers"); if (LiveRegs[rx].Value == B) setLiveReg(rx, A); + } return true; } -// enterBasicBlock - Set up LiveRegs by merging predecessor live-out values. +/// Set up LiveRegs by merging predecessor live-out values. void ExeDepsFix::enterBasicBlock(MachineBasicBlock *MBB) { // Detect back-edges from predecessors we haven't processed yet. SeenUnknownBackEdge = false; @@ -368,13 +377,12 @@ void ExeDepsFix::enterBasicBlock(MachineBasicBlock *MBB) { if (MBB->pred_empty()) { for (MachineBasicBlock::livein_iterator i = MBB->livein_begin(), e = MBB->livein_end(); i != e; ++i) { - int rx = regIndex(*i); - if (rx < 0) - continue; - // Treat function live-ins as if they were defined just before the first - // instruction. Usually, function arguments are set up immediately - // before the call. - LiveRegs[rx].Def = -1; + for (int rx : regIndices(*i)) { + // Treat function live-ins as if they were defined just before the first + // instruction. Usually, function arguments are set up immediately + // before the call. + LiveRegs[rx].Def = -1; + } } DEBUG(dbgs() << "BB#" << MBB->getNumber() << ": entry\n"); return; @@ -404,7 +412,7 @@ void ExeDepsFix::enterBasicBlock(MachineBasicBlock *MBB) { // We have a live DomainValue from more than one predecessor. if (LiveRegs[rx].Value->isCollapsed()) { - // We are already collapsed, but predecessor is not. Force him. + // We are already collapsed, but predecessor is not. Force it. unsigned Domain = LiveRegs[rx].Value->getFirstDomain(); if (!pdv->isCollapsed() && pdv->hasDomain(Domain)) collapse(pdv, Domain); @@ -465,26 +473,26 @@ void ExeDepsFix::visitInstr(MachineInstr *MI) { /// or undef use. bool ExeDepsFix::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx, unsigned Pref) { - int rx = regIndex(MI->getOperand(OpIdx).getReg()); - if (rx < 0) - return false; - - unsigned Clearance = CurInstr - LiveRegs[rx].Def; - DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref); + unsigned reg = MI->getOperand(OpIdx).getReg(); + for (int rx : regIndices(reg)) { + unsigned Clearance = CurInstr - LiveRegs[rx].Def; + DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref); - if (Pref > Clearance) { - DEBUG(dbgs() << ": Break dependency.\n"); - return true; - } - // The current clearance seems OK, but we may be ignoring a def from a - // back-edge. - if (!SeenUnknownBackEdge || Pref <= unsigned(CurInstr)) { - DEBUG(dbgs() << ": OK .\n"); + if (Pref > Clearance) { + DEBUG(dbgs() << ": Break dependency.\n"); + continue; + } + // The current clearance seems OK, but we may be ignoring a def from a + // back-edge. + if (!SeenUnknownBackEdge || Pref <= unsigned(CurInstr)) { + DEBUG(dbgs() << ": OK .\n"); + return false; + } + // A def from an unprocessed back-edge may make us break this dependency. + DEBUG(dbgs() << ": Wait for back-edge to resolve.\n"); return false; } - // A def from an unprocessed back-edge may make us break this dependency. - DEBUG(dbgs() << ": Wait for back-edge to resolve.\n"); - return false; + return true; } // Update def-ages for registers defined by MI. @@ -512,26 +520,24 @@ void ExeDepsFix::processDefs(MachineInstr *MI, bool Kill) { break; if (MO.isUse()) continue; - int rx = regIndex(MO.getReg()); - if (rx < 0) - continue; - - // This instruction explicitly defines rx. - DEBUG(dbgs() << TRI->getName(RC->getRegister(rx)) << ":\t" << CurInstr - << '\t' << *MI); - - // Check clearance before partial register updates. - // Call breakDependence before setting LiveRegs[rx].Def. - unsigned Pref = TII->getPartialRegUpdateClearance(MI, i, TRI); - if (Pref && shouldBreakDependence(MI, i, Pref)) - TII->breakPartialRegDependency(MI, i, TRI); - - // How many instructions since rx was last written? - LiveRegs[rx].Def = CurInstr; - - // Kill off domains redefined by generic instructions. - if (Kill) - kill(rx); + for (int rx : regIndices(MO.getReg())) { + // This instruction explicitly defines rx. + DEBUG(dbgs() << TRI->getName(RC->getRegister(rx)) << ":\t" << CurInstr + << '\t' << *MI); + + // Check clearance before partial register updates. + // Call breakDependence before setting LiveRegs[rx].Def. + unsigned Pref = TII->getPartialRegUpdateClearance(MI, i, TRI); + if (Pref && shouldBreakDependence(MI, i, Pref)) + TII->breakPartialRegDependency(MI, i, TRI); + + // How many instructions since rx was last written? + LiveRegs[rx].Def = CurInstr; + + // Kill off domains redefined by generic instructions. + if (Kill) + kill(rx); + } } ++CurInstr; } @@ -580,19 +586,19 @@ void ExeDepsFix::visitHardInstr(MachineInstr *mi, unsigned domain) { e = mi->getDesc().getNumOperands(); i != e; ++i) { MachineOperand &mo = mi->getOperand(i); if (!mo.isReg()) continue; - int rx = regIndex(mo.getReg()); - if (rx < 0) continue; - force(rx, domain); + for (int rx : regIndices(mo.getReg())) { + force(rx, domain); + } } // Kill all defs and force them. for (unsigned i = 0, e = mi->getDesc().getNumDefs(); i != e; ++i) { MachineOperand &mo = mi->getOperand(i); if (!mo.isReg()) continue; - int rx = regIndex(mo.getReg()); - if (rx < 0) continue; - kill(rx); - force(rx, domain); + for (int rx : regIndices(mo.getReg())) { + kill(rx); + force(rx, domain); + } } } @@ -609,9 +615,10 @@ void ExeDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) { e = mi->getDesc().getNumOperands(); i != e; ++i) { MachineOperand &mo = mi->getOperand(i); if (!mo.isReg()) continue; - int rx = regIndex(mo.getReg()); - if (rx < 0) continue; - if (DomainValue *dv = LiveRegs[rx].Value) { + for (int rx : regIndices(mo.getReg())) { + DomainValue *dv = LiveRegs[rx].Value; + if (dv == nullptr) + continue; // Bitmask of domains that dv and available have in common. unsigned common = dv->getCommonDomains(available); // Is it possible to use this collapsed register for free? @@ -643,6 +650,7 @@ void ExeDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) { SmallVector Regs; for (SmallVectorImpl::iterator i=used.begin(), e=used.end(); i!=e; ++i) { int rx = *i; + assert(LiveRegs && "no space allocated for live registers"); const LiveReg &LR = LiveRegs[rx]; // This useless DomainValue could have been missed above. if (!LR.Value->getCommonDomains(available)) { @@ -682,9 +690,11 @@ void ExeDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) { continue; // If latest didn't merge, it is useless now. Kill all registers using it. - for (SmallVectorImpl::iterator i=used.begin(), e=used.end(); i!=e; ++i) - if (LiveRegs[*i].Value == Latest) - kill(*i); + for (int i : used) { + assert(LiveRegs && "no space allocated for live registers"); + if (LiveRegs[i].Value == Latest) + kill(i); + } } // dv is the DomainValue we are going to use for this instruction. @@ -701,24 +711,24 @@ void ExeDepsFix::visitSoftInstr(MachineInstr *mi, unsigned mask) { ii != ee; ++ii) { MachineOperand &mo = *ii; if (!mo.isReg()) continue; - int rx = regIndex(mo.getReg()); - if (rx < 0) continue; - if (!LiveRegs[rx].Value || (mo.isDef() && LiveRegs[rx].Value != dv)) { - kill(rx); - setLiveReg(rx, dv); + for (int rx : regIndices(mo.getReg())) { + if (!LiveRegs[rx].Value || (mo.isDef() && LiveRegs[rx].Value != dv)) { + kill(rx); + setLiveReg(rx, dv); + } } } } bool ExeDepsFix::runOnMachineFunction(MachineFunction &mf) { MF = &mf; - TII = MF->getTarget().getInstrInfo(); - TRI = MF->getTarget().getRegisterInfo(); + TII = MF->getSubtarget().getInstrInfo(); + TRI = MF->getSubtarget().getRegisterInfo(); LiveRegs = nullptr; assert(NumRegs == RC->getNumRegs() && "Bad regclass"); DEBUG(dbgs() << "********** FIX EXECUTION DEPENDENCIES: " - << RC->getName() << " **********\n"); + << TRI->getRegClassName(RC) << " **********\n"); // If no relevant registers are used in the function, we can skip it // completely. @@ -733,13 +743,13 @@ bool ExeDepsFix::runOnMachineFunction(MachineFunction &mf) { // Initialize the AliasMap on the first use. if (AliasMap.empty()) { - // Given a PhysReg, AliasMap[PhysReg] is either the relevant index into RC, - // or -1. - AliasMap.resize(TRI->getNumRegs(), -1); + // Given a PhysReg, AliasMap[PhysReg] returns a list of indices into RC and + // therefore the LiveRegs array. + AliasMap.resize(TRI->getNumRegs()); for (unsigned i = 0, e = RC->getNumRegs(); i != e; ++i) for (MCRegAliasIterator AI(RC->getRegister(i), TRI, true); AI.isValid(); ++AI) - AliasMap[*AI] = i; + AliasMap[*AI].push_back(i); } MachineBasicBlock *Entry = MF->begin();