summaryrefslogtreecommitdiff
path: root/lib/CodeGen/RegAllocGreedy.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/CodeGen/RegAllocGreedy.cpp')
-rw-r--r--lib/CodeGen/RegAllocGreedy.cpp96
1 files changed, 59 insertions, 37 deletions
diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp
index 47d726f6da7a..50d241bff23d 100644
--- a/lib/CodeGen/RegAllocGreedy.cpp
+++ b/lib/CodeGen/RegAllocGreedy.cpp
@@ -1,4 +1,4 @@
-//===-- RegAllocGreedy.cpp - greedy register allocator --------------------===//
+//===- RegAllocGreedy.cpp - greedy register allocator ---------------------===//
//
// The LLVM Compiler Infrastructure
//
@@ -19,36 +19,63 @@
#include "SpillPlacement.h"
#include "Spiller.h"
#include "SplitKit.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/IndexedMap.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/OptimizationDiagnosticInfo.h"
#include "llvm/CodeGen/CalcSpillWeights.h"
#include "llvm/CodeGen/EdgeBundles.h"
+#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/LiveIntervalUnion.h"
#include "llvm/CodeGen/LiveRangeEdit.h"
#include "llvm/CodeGen/LiveRegMatrix.h"
#include "llvm/CodeGen/LiveStackAnalysis.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
+#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
+#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/CodeGen/VirtRegMap.h"
+#include "llvm/IR/Function.h"
#include "llvm/IR/LLVMContext.h"
-#include "llvm/PassAnalysisSupport.h"
+#include "llvm/MC/MCRegisterInfo.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/BlockFrequency.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
-#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/MathExtras.h"
#include "llvm/Support/Timer.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
+#include <algorithm>
+#include <cassert>
+#include <cstdint>
+#include <memory>
#include <queue>
+#include <tuple>
+#include <utility>
using namespace llvm;
@@ -106,13 +133,14 @@ static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
createGreedyRegisterAllocator);
namespace {
+
class RAGreedy : public MachineFunctionPass,
public RegAllocBase,
private LiveRangeEdit::Delegate {
// Convenient shortcuts.
- typedef std::priority_queue<std::pair<unsigned, unsigned> > PQueue;
- typedef SmallPtrSet<LiveInterval *, 4> SmallLISet;
- typedef SmallSet<unsigned, 16> SmallVirtRegSet;
+ using PQueue = std::priority_queue<std::pair<unsigned, unsigned>>;
+ using SmallLISet = SmallPtrSet<LiveInterval *, 4>;
+ using SmallVirtRegSet = SmallSet<unsigned, 16>;
// context
MachineFunction *MF;
@@ -201,12 +229,12 @@ class RAGreedy : public MachineFunctionPass,
// RegInfo - Keep additional information about each live range.
struct RegInfo {
- LiveRangeStage Stage;
+ LiveRangeStage Stage = RS_New;
// Cascade - Eviction loop prevention. See canEvictInterference().
- unsigned Cascade;
+ unsigned Cascade = 0;
- RegInfo() : Stage(RS_New), Cascade(0) {}
+ RegInfo() = default;
};
IndexedMap<RegInfo, VirtReg2IndexFunctor> ExtraRegInfo;
@@ -232,10 +260,10 @@ class RAGreedy : public MachineFunctionPass,
/// Cost of evicting interference.
struct EvictionCost {
- unsigned BrokenHints; ///< Total number of broken hints.
- float MaxWeight; ///< Maximum spill weight evicted.
+ unsigned BrokenHints = 0; ///< Total number of broken hints.
+ float MaxWeight = 0; ///< Maximum spill weight evicted.
- EvictionCost(): BrokenHints(0), MaxWeight(0) {}
+ EvictionCost() = default;
bool isMax() const { return BrokenHints == ~0u; }
@@ -413,10 +441,12 @@ private:
/// Its currently assigned register.
/// In case of a physical register Reg == PhysReg.
unsigned PhysReg;
+
HintInfo(BlockFrequency Freq, unsigned Reg, unsigned PhysReg)
: Freq(Freq), Reg(Reg), PhysReg(PhysReg) {}
};
- typedef SmallVector<HintInfo, 4> HintsInfo;
+ using HintsInfo = SmallVector<HintInfo, 4>;
+
BlockFrequency getBrokenHintFreq(const HintsInfo &, unsigned);
void collectHintInfo(unsigned, HintsInfo &);
@@ -436,6 +466,7 @@ private:
}
}
};
+
} // end anonymous namespace
char RAGreedy::ID = 0;
@@ -475,7 +506,6 @@ const char *const RAGreedy::StageName[] = {
// This helps stabilize decisions based on float comparisons.
const float Hysteresis = (2007 / 2048.0f); // 0.97998046875
-
FunctionPass* llvm::createGreedyRegisterAllocator() {
return new RAGreedy();
}
@@ -511,7 +541,6 @@ void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
MachineFunctionPass::getAnalysisUsage(AU);
}
-
//===----------------------------------------------------------------------===//
// LiveRangeEdit delegate methods
//===----------------------------------------------------------------------===//
@@ -634,7 +663,6 @@ LiveInterval *RAGreedy::dequeue(PQueue &CurQueue) {
return LI;
}
-
//===----------------------------------------------------------------------===//
// Direct Assignment
//===----------------------------------------------------------------------===//
@@ -682,7 +710,6 @@ unsigned RAGreedy::tryAssign(LiveInterval &VirtReg,
return CheapReg ? CheapReg : PhysReg;
}
-
//===----------------------------------------------------------------------===//
// Interference eviction
//===----------------------------------------------------------------------===//
@@ -954,7 +981,6 @@ unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
return BestPhys;
}
-
//===----------------------------------------------------------------------===//
// Region Splitting
//===----------------------------------------------------------------------===//
@@ -1025,7 +1051,6 @@ bool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf,
return SpillPlacer->scanActiveBundles();
}
-
/// addThroughConstraints - Add constraints and links to SpillPlacer from the
/// live-through blocks in Blocks.
void RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf,
@@ -1083,7 +1108,7 @@ void RAGreedy::growRegion(GlobalSplitCandidate &Cand) {
unsigned Visited = 0;
#endif
- for (;;) {
+ while (true) {
ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive();
// Find new through blocks in the periphery of PrefRegBundles.
for (int i = 0, e = NewBundles.size(); i != e; ++i) {
@@ -1197,8 +1222,8 @@ BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand) {
for (unsigned i = 0; i != UseBlocks.size(); ++i) {
const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
- bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, 0)];
- bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)];
+ bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, false)];
+ bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, true)];
unsigned Ins = 0;
if (BI.LiveIn)
@@ -1211,8 +1236,8 @@ BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand) {
for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) {
unsigned Number = Cand.ActiveBlocks[i];
- bool RegIn = LiveBundles[Bundles->getBundle(Number, 0)];
- bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)];
+ bool RegIn = LiveBundles[Bundles->getBundle(Number, false)];
+ bool RegOut = LiveBundles[Bundles->getBundle(Number, true)];
if (!RegIn && !RegOut)
continue;
if (RegIn && RegOut) {
@@ -1264,7 +1289,7 @@ void RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit,
unsigned IntvIn = 0, IntvOut = 0;
SlotIndex IntfIn, IntfOut;
if (BI.LiveIn) {
- unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)];
+ unsigned CandIn = BundleCand[Bundles->getBundle(Number, false)];
if (CandIn != NoCand) {
GlobalSplitCandidate &Cand = GlobalCand[CandIn];
IntvIn = Cand.IntvIdx;
@@ -1273,7 +1298,7 @@ void RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit,
}
}
if (BI.LiveOut) {
- unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)];
+ unsigned CandOut = BundleCand[Bundles->getBundle(Number, true)];
if (CandOut != NoCand) {
GlobalSplitCandidate &Cand = GlobalCand[CandOut];
IntvOut = Cand.IntvIdx;
@@ -1313,7 +1338,7 @@ void RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit,
unsigned IntvIn = 0, IntvOut = 0;
SlotIndex IntfIn, IntfOut;
- unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)];
+ unsigned CandIn = BundleCand[Bundles->getBundle(Number, false)];
if (CandIn != NoCand) {
GlobalSplitCandidate &Cand = GlobalCand[CandIn];
IntvIn = Cand.IntvIdx;
@@ -1321,7 +1346,7 @@ void RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit,
IntfIn = Cand.Intf.first();
}
- unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)];
+ unsigned CandOut = BundleCand[Bundles->getBundle(Number, true)];
if (CandOut != NoCand) {
GlobalSplitCandidate &Cand = GlobalCand[CandOut];
IntvOut = Cand.IntvIdx;
@@ -1533,7 +1558,6 @@ unsigned RAGreedy::doRegionSplit(LiveInterval &VirtReg, unsigned BestCand,
return 0;
}
-
//===----------------------------------------------------------------------===//
// Per-Block Splitting
//===----------------------------------------------------------------------===//
@@ -1580,7 +1604,6 @@ unsigned RAGreedy::tryBlockSplit(LiveInterval &VirtReg, AllocationOrder &Order,
return 0;
}
-
//===----------------------------------------------------------------------===//
// Per-Instruction Splitting
//===----------------------------------------------------------------------===//
@@ -1664,12 +1687,10 @@ RAGreedy::tryInstructionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
return 0;
}
-
//===----------------------------------------------------------------------===//
// Local Splitting
//===----------------------------------------------------------------------===//
-
/// calcGapWeights - Compute the maximum spill weight that needs to be evicted
/// in order to use PhysReg between two entries in SA->UseSlots.
///
@@ -1740,7 +1761,7 @@ void RAGreedy::calcGapWeights(unsigned PhysReg,
break;
for (; Gap != NumGaps; ++Gap) {
- GapWeight[Gap] = llvm::huge_valf;
+ GapWeight[Gap] = huge_valf;
if (Uses[Gap+1].getBaseIndex() >= I->end)
break;
}
@@ -1846,7 +1867,7 @@ unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
// Remove any gaps with regmask clobbers.
if (Matrix->checkRegMaskInterference(VirtReg, PhysReg))
for (unsigned i = 0, e = RegMaskGaps.size(); i != e; ++i)
- GapWeight[RegMaskGaps[i]] = llvm::huge_valf;
+ GapWeight[RegMaskGaps[i]] = huge_valf;
// Try to find the best sequence of gaps to close.
// The new spill weight must be larger than any gap interference.
@@ -1858,7 +1879,7 @@ unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
// It is the spill weight that needs to be evicted.
float MaxGap = GapWeight[0];
- for (;;) {
+ while (true) {
// Live before/after split?
const bool LiveBefore = SplitBefore != 0 || BI.LiveIn;
const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut;
@@ -1881,7 +1902,7 @@ unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
// Legally, without causing looping?
bool Legal = !ProgressRequired || NewGaps < NumGaps;
- if (Legal && MaxGap < llvm::huge_valf) {
+ if (Legal && MaxGap < huge_valf) {
// Estimate the new spill weight. Each instruction reads or writes the
// register. Conservatively assume there are no read-modify-write
// instructions.
@@ -2680,6 +2701,7 @@ void RAGreedy::reportNumberOfSplillsReloads(MachineLoop *L, unsigned &Reloads,
if (Reloads || FoldedReloads || Spills || FoldedSpills) {
using namespace ore;
+
MachineOptimizationRemarkMissed R(DEBUG_TYPE, "LoopSpillReload",
L->getStartLoc(), L->getHeader());
if (Spills)
generated by cgit v1.2.3 (git 2.25.1) at 2025-11-04 06:23:52 +0000