X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocGreedy.cpp;h=a3a8760c54e4b7a0b48cd718e759b290d2ca0685;hb=d2ea3168ae9117324582210007a18ffc31fb6586;hp=923ec3e80030b590b04a36140c5fcdcd36801b80;hpb=3b2b5dfa9b4d868b1369c0b54f3cbaf31a9dca86;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp index 923ec3e8003..a3a8760c54e 100644 --- a/lib/CodeGen/RegAllocGreedy.cpp +++ b/lib/CodeGen/RegAllocGreedy.cpp @@ -12,7 +12,6 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "regalloc" #include "llvm/CodeGen/Passes.h" #include "AllocationOrder.h" #include "InterferenceCache.h" @@ -39,15 +38,19 @@ #include "llvm/CodeGen/VirtRegMap.h" #include "llvm/IR/LLVMContext.h" #include "llvm/PassAnalysisSupport.h" +#include "llvm/Support/BranchProbability.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/Timer.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetSubtargetInfo.h" #include using namespace llvm; +#define DEBUG_TYPE "regalloc" + STATISTIC(NumGlobalSplits, "Number of split global live ranges"); STATISTIC(NumLocalSplits, "Number of split local live ranges"); STATISTIC(NumEvicted, "Number of interferences evicted"); @@ -72,6 +75,17 @@ static cl::opt LastChanceRecoloringMaxInterference( " interference at a time"), cl::init(8)); +static cl::opt +ExhaustiveSearch("exhaustive-register-search", cl::NotHidden, + cl::desc("Exhaustive Search for registers bypassing the depth " + "and interference cutoffs of last chance recoloring")); + +static cl::opt EnableLocalReassignment( + "enable-local-reassign", cl::Hidden, + cl::desc("Local reassignment can yield better allocation decisions, but " + "may be compile time intensive"), + cl::init(false)); + // FIXME: Find a good default for this flag and remove the flag. static cl::opt CSRFirstTimeCost("regalloc-csr-first-time-cost", @@ -275,6 +289,13 @@ class RAGreedy : public MachineFunctionPass, /// NoCand which indicates the stack interval. SmallVector BundleCand; + /// Callee-save register cost, calculated once per machine function. + BlockFrequency CSRCost; + + /// Run or not the local reassignment heuristic. This information is + /// obtained from the TargetSubtargetInfo. + bool EnableLocalReassign; + public: RAGreedy(); @@ -343,6 +364,7 @@ private: unsigned tryAssignCSRFirstTime(LiveInterval &VirtReg, AllocationOrder &Order, unsigned PhysReg, unsigned &CostPerUseLimit, SmallVectorImpl &NewVRegs); + void initializeCSRCost(); unsigned tryBlockSplit(LiveInterval&, AllocationOrder&, SmallVectorImpl&); unsigned tryInstructionSplit(LiveInterval&, AllocationOrder&, @@ -464,7 +486,7 @@ void RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) { } void RAGreedy::releaseMemory() { - SpillerInstance.reset(0); + SpillerInstance.reset(); ExtraRegInfo.clear(); GlobalCand.clear(); } @@ -531,7 +553,7 @@ LiveInterval *RAGreedy::dequeue() { return dequeue(Queue); } LiveInterval *RAGreedy::dequeue(PQueue &CurQueue) { if (CurQueue.empty()) - return 0; + return nullptr; LiveInterval *LI = &LIS->getInterval(~CurQueue.top().second); CurQueue.pop(); return LI; @@ -720,7 +742,7 @@ bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg, // Evicting another local live range in this case could lead to suboptimal // coloring. if (!MaxCost.isMax() && IsLocal && LIS->intervalIsInOneMBB(*Intf) && - !canReassign(*Intf, PhysReg)) { + (!EnableLocalReassign || !canReassign(*Intf, PhysReg))) { return false; } } @@ -1927,7 +1949,7 @@ RAGreedy::mayRecolorAllInterferences(unsigned PhysReg, LiveInterval &VirtReg, // If there is LastChanceRecoloringMaxInterference or more interferences, // chances are one would not be recolorable. if (Q.collectInterferingVRegs(LastChanceRecoloringMaxInterference) >= - LastChanceRecoloringMaxInterference) { + LastChanceRecoloringMaxInterference && !ExhaustiveSearch) { DEBUG(dbgs() << "Early abort: too many interferences.\n"); CutOffInfo |= CO_Interf; return false; @@ -2000,7 +2022,7 @@ unsigned RAGreedy::tryLastChanceRecoloring(LiveInterval &VirtReg, // We may want to reconsider that if we end up with a too large search space // for target with hundreds of registers. // Indeed, in that case we may want to cut the search space earlier. - if (Depth >= LastChanceRecoloringMaxDepth) { + if (Depth >= LastChanceRecoloringMaxDepth && !ExhaustiveSearch) { DEBUG(dbgs() << "Abort because max depth has been reached.\n"); CutOffInfo |= CO_Depth; return ~0u; @@ -2134,14 +2156,17 @@ unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg, if (Reg == ~0U && (CutOffInfo != CO_None)) { uint8_t CutOffEncountered = CutOffInfo & (CO_Depth | CO_Interf); if (CutOffEncountered == CO_Depth) - Ctx.emitError( - "register allocation failed: maximum depth for recoloring reached"); + Ctx.emitError("register allocation failed: maximum depth for recoloring " + "reached. Use -fexhaustive-register-search to skip " + "cutoffs"); else if (CutOffEncountered == CO_Interf) Ctx.emitError("register allocation failed: maximum interference for " - "recoloring reached"); + "recoloring reached. Use -fexhaustive-register-search " + "to skip cutoffs"); else if (CutOffEncountered == (CO_Depth | CO_Interf)) Ctx.emitError("register allocation failed: maximum interference and " - "depth for recoloring reached"); + "depth for recoloring reached. Use " + "-fexhaustive-register-search to skip cutoffs"); } return Reg; } @@ -2157,10 +2182,6 @@ unsigned RAGreedy::tryAssignCSRFirstTime(LiveInterval &VirtReg, unsigned PhysReg, unsigned &CostPerUseLimit, SmallVectorImpl &NewVRegs) { - // We use the larger one out of the command-line option and the value report - // by TRI. - BlockFrequency CSRCost(std::max((unsigned)CSRFirstTimeCost, - TRI->getCSRFirstUseCost())); if (getStage(VirtReg) == RS_Spill && VirtReg.isSpillable()) { // We choose spill over using the CSR for the first time if the spill cost // is lower than CSRCost. @@ -2178,9 +2199,9 @@ unsigned RAGreedy::tryAssignCSRFirstTime(LiveInterval &VirtReg, // the cost of splitting is lower than CSRCost. SA->analyze(&VirtReg); unsigned NumCands = 0; - unsigned BestCand = - calculateRegionSplitCost(VirtReg, Order, CSRCost, NumCands, - true/*IgnoreCSR*/); + BlockFrequency BestCost = CSRCost; // Don't modify CSRCost. + unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost, + NumCands, true /*IgnoreCSR*/); if (BestCand == NoCand) // Use the CSR if we can't find a region split below CSRCost. return PhysReg; @@ -2192,6 +2213,31 @@ unsigned RAGreedy::tryAssignCSRFirstTime(LiveInterval &VirtReg, return PhysReg; } +void RAGreedy::initializeCSRCost() { + // We use the larger one out of the command-line option and the value report + // by TRI. + CSRCost = BlockFrequency( + std::max((unsigned)CSRFirstTimeCost, TRI->getCSRFirstUseCost())); + if (!CSRCost.getFrequency()) + return; + + // Raw cost is relative to Entry == 2^14; scale it appropriately. + uint64_t ActualEntry = MBFI->getEntryFreq(); + if (!ActualEntry) { + CSRCost = 0; + return; + } + uint64_t FixedEntry = 1 << 14; + if (ActualEntry < FixedEntry) + CSRCost *= BranchProbability(ActualEntry, FixedEntry); + else if (ActualEntry <= UINT32_MAX) + // Invert the fraction and divide. + CSRCost /= BranchProbability(FixedEntry, ActualEntry); + else + // Can't use BranchProbability in general, since it takes 32-bit numbers. + CSRCost = CSRCost.getFrequency() * (ActualEntry / FixedEntry); +} + unsigned RAGreedy::selectOrSplitImpl(LiveInterval &VirtReg, SmallVectorImpl &NewVRegs, SmallVirtRegSet &FixedRegisters, @@ -2209,8 +2255,7 @@ unsigned RAGreedy::selectOrSplitImpl(LiveInterval &VirtReg, // When NewVRegs is not empty, we may have made decisions such as evicting // a virtual register, go with the earlier decisions and use the physical // register. - if ((CSRFirstTimeCost || TRI->getCSRFirstUseCost()) && - CSRFirstUse && NewVRegs.empty()) { + if (CSRCost.getFrequency() && CSRFirstUse && NewVRegs.empty()) { unsigned CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg, CostPerUseLimit, NewVRegs); if (CSRReg || !NewVRegs.empty()) @@ -2274,9 +2319,14 @@ bool RAGreedy::runOnMachineFunction(MachineFunction &mf) { << "********** Function: " << mf.getName() << '\n'); MF = &mf; - TRI = MF->getTarget().getRegisterInfo(); - TII = MF->getTarget().getInstrInfo(); + const TargetMachine &TM = MF->getTarget(); + TRI = TM.getSubtargetImpl()->getRegisterInfo(); + TII = TM.getSubtargetImpl()->getInstrInfo(); RCI.runOnMachineFunction(mf); + + EnableLocalReassign = EnableLocalReassignment || + TM.getSubtargetImpl()->enableRALocalReassignment(TM.getOptLevel()); + if (VerifyEnabled) MF->verify(this, "Before greedy register allocator"); @@ -2292,6 +2342,8 @@ bool RAGreedy::runOnMachineFunction(MachineFunction &mf) { SpillPlacer = &getAnalysis(); DebugVars = &getAnalysis(); + initializeCSRCost(); + calculateSpillWeightsAndHints(*LIS, mf, *Loops, *MBFI); DEBUG(LIS->dump());