//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "regalloc"
#include "llvm/CodeGen/Passes.h"
#include "AllocationOrder.h"
#include "InterferenceCache.h"
#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"
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");
" interference at a time"),
cl::init(8));
+static cl::opt<bool>
+ExhaustiveSearch("exhaustive-register-search", cl::NotHidden,
+ cl::desc("Exhaustive Search for registers bypassing the depth "
+ "and interference cutoffs of last chance recoloring"));
+
// FIXME: Find a good default for this flag and remove the flag.
static cl::opt<unsigned>
CSRFirstTimeCost("regalloc-csr-first-time-cost",
/// NoCand which indicates the stack interval.
SmallVector<unsigned, 32> BundleCand;
+ /// Callee-save register cost, calculated once per machine function.
+ BlockFrequency CSRCost;
+
public:
RAGreedy();
unsigned tryAssignCSRFirstTime(LiveInterval &VirtReg, AllocationOrder &Order,
unsigned PhysReg, unsigned &CostPerUseLimit,
SmallVectorImpl<unsigned> &NewVRegs);
+ void initializeCSRCost();
unsigned tryBlockSplit(LiveInterval&, AllocationOrder&,
SmallVectorImpl<unsigned>&);
unsigned tryInstructionSplit(LiveInterval&, AllocationOrder&,
}
void RAGreedy::releaseMemory() {
- SpillerInstance.reset(0);
+ SpillerInstance.reset(nullptr);
ExtraRegInfo.clear();
GlobalCand.clear();
}
LiveInterval *RAGreedy::dequeue(PQueue &CurQueue) {
if (CurQueue.empty())
- return 0;
+ return nullptr;
LiveInterval *LI = &LIS->getInterval(~CurQueue.top().second);
CurQueue.pop();
return LI;
// 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;
// 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;
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;
}
unsigned PhysReg,
unsigned &CostPerUseLimit,
SmallVectorImpl<unsigned> &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.
// 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;
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<unsigned> &NewVRegs,
SmallVirtRegSet &FixedRegisters,
// 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())
SpillPlacer = &getAnalysis<SpillPlacement>();
DebugVars = &getAnalysis<LiveDebugVariables>();
+ initializeCSRCost();
+
calculateSpillWeightsAndHints(*LIS, mf, *Loops, *MBFI);
DEBUG(LIS->dump());