aboutsummaryrefslogtreecommitdiff
path: root/contrib/llvm-project/llvm/lib/CodeGen/MachineSink.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm-project/llvm/lib/CodeGen/MachineSink.cpp')
-rw-r--r--contrib/llvm-project/llvm/lib/CodeGen/MachineSink.cpp298
1 files changed, 175 insertions, 123 deletions
diff --git a/contrib/llvm-project/llvm/lib/CodeGen/MachineSink.cpp b/contrib/llvm-project/llvm/lib/CodeGen/MachineSink.cpp
index bc03776bde19..006ba9273dfb 100644
--- a/contrib/llvm-project/llvm/lib/CodeGen/MachineSink.cpp
+++ b/contrib/llvm-project/llvm/lib/CodeGen/MachineSink.cpp
@@ -16,19 +16,20 @@
//===----------------------------------------------------------------------===//
#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/SparseBitVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
+#include "llvm/CodeGen/MachineCycleAnalysis.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
@@ -95,18 +96,18 @@ static cl::opt<unsigned> SinkLoadBlocksThreshold(
cl::init(20), cl::Hidden);
static cl::opt<bool>
-SinkInstsIntoLoop("sink-insts-to-avoid-spills",
- cl::desc("Sink instructions into loops to avoid "
- "register spills"),
- cl::init(false), cl::Hidden);
-
-static cl::opt<unsigned> SinkIntoLoopLimit(
- "machine-sink-loop-limit",
- cl::desc("The maximum number of instructions considered for loop sinking."),
+ SinkInstsIntoCycle("sink-insts-to-avoid-spills",
+ cl::desc("Sink instructions into cycles to avoid "
+ "register spills"),
+ cl::init(false), cl::Hidden);
+
+static cl::opt<unsigned> SinkIntoCycleLimit(
+ "machine-sink-cycle-limit",
+ cl::desc("The maximum number of instructions considered for cycle sinking."),
cl::init(50), cl::Hidden);
STATISTIC(NumSunk, "Number of machine instructions sunk");
-STATISTIC(NumLoopSunk, "Number of machine instructions sunk into a loop");
+STATISTIC(NumCycleSunk, "Number of machine instructions sunk into a cycle");
STATISTIC(NumSplit, "Number of critical edges split");
STATISTIC(NumCoalesces, "Number of copies coalesced");
STATISTIC(NumPostRACopySink, "Number of copies sunk after RA");
@@ -119,7 +120,7 @@ namespace {
MachineRegisterInfo *MRI; // Machine register information
MachineDominatorTree *DT; // Machine dominator tree
MachinePostDominatorTree *PDT; // Machine post dominator tree
- MachineLoopInfo *LI;
+ MachineCycleInfo *CI;
MachineBlockFrequencyInfo *MBFI;
const MachineBranchProbabilityInfo *MBPI;
AliasAnalysis *AA;
@@ -180,8 +181,9 @@ namespace {
AU.addRequired<AAResultsWrapperPass>();
AU.addRequired<MachineDominatorTree>();
AU.addRequired<MachinePostDominatorTree>();
- AU.addRequired<MachineLoopInfo>();
+ AU.addRequired<MachineCycleInfoWrapperPass>();
AU.addRequired<MachineBranchProbabilityInfo>();
+ AU.addPreserved<MachineCycleInfoWrapperPass>();
AU.addPreserved<MachineLoopInfo>();
if (UseBlockFreqInfo)
AU.addRequired<MachineBlockFrequencyInfo>();
@@ -232,9 +234,9 @@ namespace {
MachineBasicBlock *FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
bool &BreakPHIEdge, AllSuccsCache &AllSuccessors);
- void FindLoopSinkCandidates(MachineLoop *L, MachineBasicBlock *BB,
- SmallVectorImpl<MachineInstr *> &Candidates);
- bool SinkIntoLoop(MachineLoop *L, MachineInstr &I);
+ void FindCycleSinkCandidates(MachineCycle *Cycle, MachineBasicBlock *BB,
+ SmallVectorImpl<MachineInstr *> &Candidates);
+ bool SinkIntoCycle(MachineCycle *Cycle, MachineInstr &I);
bool isProfitableToSinkTo(Register Reg, MachineInstr &MI,
MachineBasicBlock *MBB,
@@ -261,7 +263,7 @@ INITIALIZE_PASS_BEGIN(MachineSinking, DEBUG_TYPE,
"Machine code sinking", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
-INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
+INITIALIZE_PASS_DEPENDENCY(MachineCycleInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_END(MachineSinking, DEBUG_TYPE,
"Machine code sinking", false, false)
@@ -378,26 +380,27 @@ static bool mayLoadFromGOTOrConstantPool(MachineInstr &MI) {
return false;
}
-void MachineSinking::FindLoopSinkCandidates(MachineLoop *L, MachineBasicBlock *BB,
+void MachineSinking::FindCycleSinkCandidates(
+ MachineCycle *Cycle, MachineBasicBlock *BB,
SmallVectorImpl<MachineInstr *> &Candidates) {
for (auto &MI : *BB) {
- LLVM_DEBUG(dbgs() << "LoopSink: Analysing candidate: " << MI);
+ LLVM_DEBUG(dbgs() << "CycleSink: Analysing candidate: " << MI);
if (!TII->shouldSink(MI)) {
- LLVM_DEBUG(dbgs() << "LoopSink: Instruction not a candidate for this "
+ LLVM_DEBUG(dbgs() << "CycleSink: Instruction not a candidate for this "
"target\n");
continue;
}
- if (!L->isLoopInvariant(MI)) {
- LLVM_DEBUG(dbgs() << "LoopSink: Instruction is not loop invariant\n");
+ if (!isCycleInvariant(Cycle, MI)) {
+ LLVM_DEBUG(dbgs() << "CycleSink: Instruction is not cycle invariant\n");
continue;
}
bool DontMoveAcrossStore = true;
if (!MI.isSafeToMove(AA, DontMoveAcrossStore)) {
- LLVM_DEBUG(dbgs() << "LoopSink: Instruction not safe to move.\n");
+ LLVM_DEBUG(dbgs() << "CycleSink: Instruction not safe to move.\n");
continue;
}
if (MI.mayLoad() && !mayLoadFromGOTOrConstantPool(MI)) {
- LLVM_DEBUG(dbgs() << "LoopSink: Dont sink GOT or constant pool loads\n");
+ LLVM_DEBUG(dbgs() << "CycleSink: Dont sink GOT or constant pool loads\n");
continue;
}
if (MI.isConvergent())
@@ -409,7 +412,7 @@ void MachineSinking::FindLoopSinkCandidates(MachineLoop *L, MachineBasicBlock *B
if (!MRI->hasOneDef(MO.getReg()))
continue;
- LLVM_DEBUG(dbgs() << "LoopSink: Instruction added as candidate.\n");
+ LLVM_DEBUG(dbgs() << "CycleSink: Instruction added as candidate.\n");
Candidates.push_back(&MI);
}
}
@@ -425,22 +428,12 @@ bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
MRI = &MF.getRegInfo();
DT = &getAnalysis<MachineDominatorTree>();
PDT = &getAnalysis<MachinePostDominatorTree>();
- LI = &getAnalysis<MachineLoopInfo>();
+ CI = &getAnalysis<MachineCycleInfoWrapperPass>().getCycleInfo();
MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
RegClassInfo.runOnMachineFunction(MF);
- // MachineSink currently uses MachineLoopInfo, which only recognizes natural
- // loops. As such, we could sink instructions into irreducible cycles, which
- // would be non-profitable.
- // WARNING: The current implementation of hasStoreBetween() is incorrect for
- // sinking into irreducible cycles (PR53990), this bailout is currently
- // necessary for correctness, not just profitability.
- ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin());
- if (containsIrreducibleCFG<MachineBasicBlock *>(RPOT, *LI))
- return false;
-
bool EverMadeChange = false;
while (true) {
@@ -473,32 +466,33 @@ bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
EverMadeChange = true;
}
- if (SinkInstsIntoLoop) {
- SmallVector<MachineLoop *, 8> Loops(LI->begin(), LI->end());
- for (auto *L : Loops) {
- MachineBasicBlock *Preheader = LI->findLoopPreheader(L);
+ if (SinkInstsIntoCycle) {
+ SmallVector<MachineCycle *, 8> Cycles(CI->toplevel_begin(),
+ CI->toplevel_end());
+ for (auto *Cycle : Cycles) {
+ MachineBasicBlock *Preheader = Cycle->getCyclePreheader();
if (!Preheader) {
- LLVM_DEBUG(dbgs() << "LoopSink: Can't find preheader\n");
+ LLVM_DEBUG(dbgs() << "CycleSink: Can't find preheader\n");
continue;
}
SmallVector<MachineInstr *, 8> Candidates;
- FindLoopSinkCandidates(L, Preheader, Candidates);
+ FindCycleSinkCandidates(Cycle, Preheader, Candidates);
// Walk the candidates in reverse order so that we start with the use
// of a def-use chain, if there is any.
// TODO: Sort the candidates using a cost-model.
unsigned i = 0;
for (MachineInstr *I : llvm::reverse(Candidates)) {
- if (i++ == SinkIntoLoopLimit) {
- LLVM_DEBUG(dbgs() << "LoopSink: Limit reached of instructions to "
+ if (i++ == SinkIntoCycleLimit) {
+ LLVM_DEBUG(dbgs() << "CycleSink: Limit reached of instructions to "
"be analysed.");
break;
}
- if (!SinkIntoLoop(L, *I))
+ if (!SinkIntoCycle(Cycle, *I))
break;
EverMadeChange = true;
- ++NumLoopSunk;
+ ++NumCycleSunk;
}
}
}
@@ -520,12 +514,12 @@ bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
// Don't bother sinking code out of unreachable blocks. In addition to being
// unprofitable, it can also lead to infinite looping, because in an
- // unreachable loop there may be nowhere to stop.
+ // unreachable cycle there may be nowhere to stop.
if (!DT->isReachableFromEntry(&MBB)) return false;
bool MadeChange = false;
- // Cache all successors, sorted by frequency info and loop depth.
+ // Cache all successors, sorted by frequency info and cycle depth.
AllSuccsCache AllSuccessors;
// Walk the basic block bottom-up. Remember if we saw a store.
@@ -644,13 +638,16 @@ bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr &MI,
if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB))
return false;
- // Avoid breaking back edge. From == To means backedge for single BB loop.
+ // Avoid breaking back edge. From == To means backedge for single BB cycle.
if (!SplitEdges || FromBB == ToBB)
return false;
- // Check for backedges of more "complex" loops.
- if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) &&
- LI->isLoopHeader(ToBB))
+ MachineCycle *FromCycle = CI->getCycle(FromBB);
+ MachineCycle *ToCycle = CI->getCycle(ToBB);
+
+ // Check for backedges of more "complex" cycles.
+ if (FromCycle == ToCycle && FromCycle &&
+ (!FromCycle->isReducible() || FromCycle->getHeader() == ToBB))
return false;
// It's not always legal to break critical edges and sink the computation
@@ -753,9 +750,9 @@ bool MachineSinking::isProfitableToSinkTo(Register Reg, MachineInstr &MI,
if (!PDT->dominates(SuccToSinkTo, MBB))
return true;
- // It is profitable to sink an instruction from a deeper loop to a shallower
- // loop, even if the latter post-dominates the former (PR21115).
- if (LI->getLoopDepth(MBB) > LI->getLoopDepth(SuccToSinkTo))
+ // It is profitable to sink an instruction from a deeper cycle to a shallower
+ // cycle, even if the latter post-dominates the former (PR21115).
+ if (CI->getCycleDepth(MBB) > CI->getCycleDepth(SuccToSinkTo))
return true;
// Check if only use in post dominated block is PHI instruction.
@@ -776,11 +773,11 @@ bool MachineSinking::isProfitableToSinkTo(Register Reg, MachineInstr &MI,
FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors);
- MachineLoop *ML = LI->getLoopFor(MBB);
+ MachineCycle *MCycle = CI->getCycle(MBB);
- // If the instruction is not inside a loop, it is not profitable to sink MI to
+ // If the instruction is not inside a cycle, it is not profitable to sink MI to
// a post dominate block SuccToSinkTo.
- if (!ML)
+ if (!MCycle)
return false;
auto isRegisterPressureSetExceedLimit = [&](const TargetRegisterClass *RC) {
@@ -798,7 +795,7 @@ bool MachineSinking::isProfitableToSinkTo(Register Reg, MachineInstr &MI,
return false;
};
- // If this instruction is inside a loop and sinking this instruction can make
+ // If this instruction is inside a Cycle and sinking this instruction can make
// more registers live range shorten, it is still prifitable.
for (const MachineOperand &MO : MI.operands()) {
// Ignore non-register operands.
@@ -826,14 +823,17 @@ bool MachineSinking::isProfitableToSinkTo(Register Reg, MachineInstr &MI,
return false;
} else {
MachineInstr *DefMI = MRI->getVRegDef(Reg);
- // DefMI is defined outside of loop. There should be no live range
- // impact for this operand. Defination outside of loop means:
- // 1: defination is outside of loop.
- // 2: defination is in this loop, but it is a PHI in the loop header.
- if (LI->getLoopFor(DefMI->getParent()) != ML ||
- (DefMI->isPHI() && LI->isLoopHeader(DefMI->getParent())))
+ if (!DefMI)
+ continue;
+ MachineCycle *Cycle = CI->getCycle(DefMI->getParent());
+ // DefMI is defined outside of cycle. There should be no live range
+ // impact for this operand. Defination outside of cycle means:
+ // 1: defination is outside of cycle.
+ // 2: defination is in this cycle, but it is a PHI in the cycle header.
+ if (Cycle != MCycle || (DefMI->isPHI() && Cycle && Cycle->isReducible() &&
+ Cycle->getHeader() == DefMI->getParent()))
continue;
- // The DefMI is defined inside the loop.
+ // The DefMI is defined inside the cycle.
// If sinking this operand makes some register pressure set exceed limit,
// it is not profitable.
if (isRegisterPressureSetExceedLimit(MRI->getRegClass(Reg))) {
@@ -843,8 +843,8 @@ bool MachineSinking::isProfitableToSinkTo(Register Reg, MachineInstr &MI,
}
}
- // If MI is in loop and all its operands are alive across the whole loop or if
- // no operand sinking make register pressure set exceed limit, it is
+ // If MI is in cycle and all its operands are alive across the whole cycle or
+ // if no operand sinking make register pressure set exceed limit, it is
// profitable to sink MI.
return true;
}
@@ -876,14 +876,14 @@ MachineSinking::GetAllSortedSuccessors(MachineInstr &MI, MachineBasicBlock *MBB,
AllSuccs.push_back(DTChild->getBlock());
}
- // Sort Successors according to their loop depth or block frequency info.
+ // Sort Successors according to their cycle depth or block frequency info.
llvm::stable_sort(
AllSuccs, [this](const MachineBasicBlock *L, const MachineBasicBlock *R) {
uint64_t LHSFreq = MBFI ? MBFI->getBlockFreq(L).getFrequency() : 0;
uint64_t RHSFreq = MBFI ? MBFI->getBlockFreq(R).getFrequency() : 0;
bool HasBlockFreq = LHSFreq != 0 && RHSFreq != 0;
return HasBlockFreq ? LHSFreq < RHSFreq
- : LI->getLoopDepth(L) < LI->getLoopDepth(R);
+ : CI->getCycleDepth(L) < CI->getCycleDepth(R);
});
auto it = AllSuccessors.insert(std::make_pair(MBB, AllSuccs));
@@ -898,7 +898,7 @@ MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
AllSuccsCache &AllSuccessors) {
assert (MBB && "Invalid MachineBasicBlock!");
- // Loop over all the operands of the specified instruction. If there is
+ // loop over all the operands of the specified instruction. If there is
// anything we can't handle, bail out.
// SuccToSinkTo - This is the successor to sink this instruction to, once we
@@ -945,7 +945,7 @@ MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
// Otherwise, we should look at all the successors and decide which one
// we should sink to. If we have reliable block frequency information
// (frequency != 0) available, give successors with smaller frequencies
- // higher priority, otherwise prioritize smaller loop depths.
+ // higher priority, otherwise prioritize smaller cycle depths.
for (MachineBasicBlock *SuccBlock :
GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {
bool LocalUse = false;
@@ -968,7 +968,7 @@ MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,
}
// It is not possible to sink an instruction into its own block. This can
- // happen with loops.
+ // happen with cycles.
if (MBB == SuccToSinkTo)
return nullptr;
@@ -1093,8 +1093,7 @@ using MIRegs = std::pair<MachineInstr *, SmallVector<unsigned, 2>>;
/// Sink an instruction and its associated debug instructions.
static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo,
MachineBasicBlock::iterator InsertPos,
- SmallVectorImpl<MIRegs> &DbgValuesToSink) {
-
+ ArrayRef<MIRegs> DbgValuesToSink) {
// If we cannot find a location to use (merge with), then we erase the debug
// location to prevent debug-info driven tools from potentially reporting
// wrong location information.
@@ -1113,7 +1112,7 @@ static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo,
// DBG_VALUE location as 'undef', indicating that any earlier variable
// location should be terminated as we've optimised away the value at this
// point.
- for (auto DbgValueToSink : DbgValuesToSink) {
+ for (const auto &DbgValueToSink : DbgValuesToSink) {
MachineInstr *DbgMI = DbgValueToSink.first;
MachineInstr *NewDbgMI = DbgMI->getMF()->CloneMachineInstr(DbgMI);
SuccToSinkTo.insert(InsertPos, NewDbgMI);
@@ -1178,7 +1177,7 @@ bool MachineSinking::hasStoreBetween(MachineBasicBlock *From,
// If this BB is too big or the block number in straight line between From
// and To is too big, stop searching to save compiling time.
- if (BB->size() > SinkLoadInstsPerBlockThreshold ||
+ if (BB->sizeWithoutDebugLargerThan(SinkLoadInstsPerBlockThreshold) ||
HandledDomBlocks.size() > SinkLoadBlocksThreshold) {
for (auto *DomBB : HandledDomBlocks) {
if (DomBB != BB && DT->dominates(DomBB, BB))
@@ -1223,69 +1222,78 @@ bool MachineSinking::hasStoreBetween(MachineBasicBlock *From,
return HasAliasedStore;
}
-/// Sink instructions into loops if profitable. This especially tries to prevent
-/// register spills caused by register pressure if there is little to no
-/// overhead moving instructions into loops.
-bool MachineSinking::SinkIntoLoop(MachineLoop *L, MachineInstr &I) {
- LLVM_DEBUG(dbgs() << "LoopSink: Finding sink block for: " << I);
- MachineBasicBlock *Preheader = L->getLoopPreheader();
- assert(Preheader && "Loop sink needs a preheader block");
+/// Sink instructions into cycles if profitable. This especially tries to
+/// prevent register spills caused by register pressure if there is little to no
+/// overhead moving instructions into cycles.
+bool MachineSinking::SinkIntoCycle(MachineCycle *Cycle, MachineInstr &I) {
+ LLVM_DEBUG(dbgs() << "CycleSink: Finding sink block for: " << I);
+ MachineBasicBlock *Preheader = Cycle->getCyclePreheader();
+ assert(Preheader && "Cycle sink needs a preheader block");
MachineBasicBlock *SinkBlock = nullptr;
bool CanSink = true;
const MachineOperand &MO = I.getOperand(0);
for (MachineInstr &MI : MRI->use_instructions(MO.getReg())) {
- LLVM_DEBUG(dbgs() << "LoopSink: Analysing use: " << MI);
- if (!L->contains(&MI)) {
- LLVM_DEBUG(dbgs() << "LoopSink: Use not in loop, can't sink.\n");
+ LLVM_DEBUG(dbgs() << "CycleSink: Analysing use: " << MI);
+ if (!Cycle->contains(MI.getParent())) {
+ LLVM_DEBUG(dbgs() << "CycleSink: Use not in cycle, can't sink.\n");
CanSink = false;
break;
}
// FIXME: Come up with a proper cost model that estimates whether sinking
- // the instruction (and thus possibly executing it on every loop
+ // the instruction (and thus possibly executing it on every cycle
// iteration) is more expensive than a register.
// For now assumes that copies are cheap and thus almost always worth it.
if (!MI.isCopy()) {
- LLVM_DEBUG(dbgs() << "LoopSink: Use is not a copy\n");
+ LLVM_DEBUG(dbgs() << "CycleSink: Use is not a copy\n");
CanSink = false;
break;
}
if (!SinkBlock) {
SinkBlock = MI.getParent();
- LLVM_DEBUG(dbgs() << "LoopSink: Setting sink block to: "
+ LLVM_DEBUG(dbgs() << "CycleSink: Setting sink block to: "
<< printMBBReference(*SinkBlock) << "\n");
continue;
}
SinkBlock = DT->findNearestCommonDominator(SinkBlock, MI.getParent());
if (!SinkBlock) {
- LLVM_DEBUG(dbgs() << "LoopSink: Can't find nearest dominator\n");
+ LLVM_DEBUG(dbgs() << "CycleSink: Can't find nearest dominator\n");
CanSink = false;
break;
}
- LLVM_DEBUG(dbgs() << "LoopSink: Setting nearest common dom block: " <<
+ LLVM_DEBUG(dbgs() << "CycleSink: Setting nearest common dom block: " <<
printMBBReference(*SinkBlock) << "\n");
}
if (!CanSink) {
- LLVM_DEBUG(dbgs() << "LoopSink: Can't sink instruction.\n");
+ LLVM_DEBUG(dbgs() << "CycleSink: Can't sink instruction.\n");
return false;
}
if (!SinkBlock) {
- LLVM_DEBUG(dbgs() << "LoopSink: Not sinking, can't find sink block.\n");
+ LLVM_DEBUG(dbgs() << "CycleSink: Not sinking, can't find sink block.\n");
return false;
}
if (SinkBlock == Preheader) {
- LLVM_DEBUG(dbgs() << "LoopSink: Not sinking, sink block is the preheader\n");
+ LLVM_DEBUG(
+ dbgs() << "CycleSink: Not sinking, sink block is the preheader\n");
return false;
}
- if (SinkBlock->size() > SinkLoadInstsPerBlockThreshold) {
- LLVM_DEBUG(dbgs() << "LoopSink: Not Sinking, block too large to analyse.\n");
+ if (SinkBlock->sizeWithoutDebugLargerThan(SinkLoadInstsPerBlockThreshold)) {
+ LLVM_DEBUG(
+ dbgs() << "CycleSink: Not Sinking, block too large to analyse.\n");
return false;
}
- LLVM_DEBUG(dbgs() << "LoopSink: Sinking instruction!\n");
- SinkBlock->splice(SinkBlock->getFirstNonPHI(), Preheader, I);
+ LLVM_DEBUG(dbgs() << "CycleSink: Sinking instruction!\n");
+ SinkBlock->splice(SinkBlock->SkipPHIsAndLabels(SinkBlock->begin()), Preheader,
+ I);
+
+ // Conservatively clear any kill flags on uses of sunk instruction
+ for (MachineOperand &MO : I.operands()) {
+ if (MO.isReg() && MO.readsReg())
+ RegsToClearKillFlags.insert(MO.getReg());
+ }
// The instruction is moved from its basic block, so do not retain the
// debug information.
@@ -1294,6 +1302,45 @@ bool MachineSinking::SinkIntoLoop(MachineLoop *L, MachineInstr &I) {
return true;
}
+/// Return true if a target defined block prologue instruction interferes
+/// with a sink candidate.
+static bool blockPrologueInterferes(MachineBasicBlock *BB,
+ MachineBasicBlock::iterator End,
+ MachineInstr &MI,
+ const TargetRegisterInfo *TRI,
+ const TargetInstrInfo *TII,
+ const MachineRegisterInfo *MRI) {
+ if (BB->begin() == End)
+ return false; // no prologue
+ for (MachineBasicBlock::iterator PI = BB->getFirstNonPHI(); PI != End; ++PI) {
+ // Only check target defined prologue instructions
+ if (!TII->isBasicBlockPrologue(*PI))
+ continue;
+ for (auto &MO : MI.operands()) {
+ if (!MO.isReg())
+ continue;
+ Register Reg = MO.getReg();
+ if (!Reg)
+ continue;
+ if (MO.isUse()) {
+ if (Register::isPhysicalRegister(Reg) &&
+ (TII->isIgnorableUse(MO) || (MRI && MRI->isConstantPhysReg(Reg))))
+ continue;
+ if (PI->modifiesRegister(Reg, TRI))
+ return true;
+ } else {
+ if (PI->readsRegister(Reg, TRI))
+ return true;
+ // Check for interference with non-dead defs
+ auto *DefOp = PI->findRegisterDefOperand(Reg, false, true, TRI);
+ if (DefOp && !DefOp->isDead())
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
/// SinkInstruction - Determine whether it is safe to sink the specified machine
/// instruction out of its current block into a successor.
bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
@@ -1368,9 +1415,11 @@ bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
TryBreak = true;
}
- // Don't sink instructions into a loop.
- if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) {
- LLVM_DEBUG(dbgs() << " *** NOTE: Loop header found\n");
+ // Don't sink instructions into a cycle.
+ if (!TryBreak && CI->getCycle(SuccToSinkTo) &&
+ (!CI->getCycle(SuccToSinkTo)->isReducible() ||
+ CI->getCycle(SuccToSinkTo)->getHeader() == SuccToSinkTo)) {
+ LLVM_DEBUG(dbgs() << " *** NOTE: cycle header found\n");
TryBreak = true;
}
@@ -1405,9 +1454,12 @@ bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
}
// Determine where to insert into. Skip phi nodes.
- MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin();
- while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI())
- ++InsertPos;
+ MachineBasicBlock::iterator InsertPos =
+ SuccToSinkTo->SkipPHIsAndLabels(SuccToSinkTo->begin());
+ if (blockPrologueInterferes(SuccToSinkTo, InsertPos, MI, TRI, TII, MRI)) {
+ LLVM_DEBUG(dbgs() << " *** Not sinking: prologue interference\n");
+ return false;
+ }
// Collect debug users of any vreg that this inst defines.
SmallVector<MIRegs, 4> DbgUsersToSink;
@@ -1696,14 +1748,6 @@ static bool hasRegisterDependency(MachineInstr *MI,
return HasRegDependency;
}
-static SmallSet<MCRegister, 4> getRegUnits(MCRegister Reg,
- const TargetRegisterInfo *TRI) {
- SmallSet<MCRegister, 4> RegUnits;
- for (auto RI = MCRegUnitIterator(Reg, TRI); RI.isValid(); ++RI)
- RegUnits.insert(*RI);
- return RegUnits;
-}
-
bool PostRAMachineSinking::tryToSinkCopy(MachineBasicBlock &CurBB,
MachineFunction &MF,
const TargetRegisterInfo *TRI,
@@ -1749,14 +1793,15 @@ bool PostRAMachineSinking::tryToSinkCopy(MachineBasicBlock &CurBB,
}
// Record debug use of each reg unit.
- SmallSet<MCRegister, 4> RegUnits = getRegUnits(MO.getReg(), TRI);
- for (MCRegister Reg : RegUnits)
- MIUnits[Reg].push_back(MO.getReg());
+ for (auto RI = MCRegUnitIterator(MO.getReg(), TRI); RI.isValid();
+ ++RI)
+ MIUnits[*RI].push_back(MO.getReg());
}
}
if (IsValid) {
- for (auto RegOps : MIUnits)
- SeenDbgInstrs[RegOps.first].push_back({&MI, RegOps.second});
+ for (auto &RegOps : MIUnits)
+ SeenDbgInstrs[RegOps.first].emplace_back(&MI,
+ std::move(RegOps.second));
}
continue;
}
@@ -1803,22 +1848,29 @@ bool PostRAMachineSinking::tryToSinkCopy(MachineBasicBlock &CurBB,
if (!MO.isReg() || !MO.isDef())
continue;
- SmallSet<MCRegister, 4> Units = getRegUnits(MO.getReg(), TRI);
- for (MCRegister Reg : Units) {
- for (auto MIRegs : SeenDbgInstrs.lookup(Reg)) {
+ for (auto RI = MCRegUnitIterator(MO.getReg(), TRI); RI.isValid(); ++RI) {
+ for (const auto &MIRegs : SeenDbgInstrs.lookup(*RI)) {
auto &Regs = DbgValsToSinkMap[MIRegs.first];
for (unsigned Reg : MIRegs.second)
Regs.push_back(Reg);
}
}
}
- SmallVector<MIRegs, 4> DbgValsToSink(DbgValsToSinkMap.begin(),
- DbgValsToSinkMap.end());
+ auto DbgValsToSink = DbgValsToSinkMap.takeVector();
+
+ LLVM_DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccBB);
+
+ MachineBasicBlock::iterator InsertPos =
+ SuccBB->SkipPHIsAndLabels(SuccBB->begin());
+ if (blockPrologueInterferes(SuccBB, InsertPos, MI, TRI, TII, nullptr)) {
+ LLVM_DEBUG(
+ dbgs() << " *** Not sinking: prologue interference\n");
+ continue;
+ }
// Clear the kill flag if SrcReg is killed between MI and the end of the
// block.
clearKillFlags(&MI, CurBB, UsedOpsInCopy, UsedRegUnits, TRI);
- MachineBasicBlock::iterator InsertPos = SuccBB->getFirstNonPHI();
performSink(MI, *SuccBB, InsertPos, DbgValsToSink);
updateLiveIn(&MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy);
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-04 07:41:34 +0000