#include "llvm/CodeGen/Passes.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SparseBitVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/MachinePostDominators.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
class MachineSinking : public MachineFunctionPass {
const TargetInstrInfo *TII;
const TargetRegisterInfo *TRI;
- MachineRegisterInfo *MRI; // Machine register information
- MachineDominatorTree *DT; // Machine dominator tree
+ MachineRegisterInfo *MRI; // Machine register information
+ MachineDominatorTree *DT; // Machine dominator tree
+ MachinePostDominatorTree *PDT; // Machine post dominator tree
MachineLoopInfo *LI;
const MachineBlockFrequencyInfo *MBFI;
AliasAnalysis *AA;
// will be split.
SetVector<std::pair<MachineBasicBlock*,MachineBasicBlock*> > ToSplit;
+ SparseBitVector<> RegsToClearKillFlags;
+
+ typedef std::map<MachineBasicBlock *, SmallVector<MachineBasicBlock *, 4>>
+ AllSuccsCache;
+
public:
static char ID; // Pass identification
MachineSinking() : MachineFunctionPass(ID) {
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
MachineFunctionPass::getAnalysisUsage(AU);
- AU.addRequired<AliasAnalysis>();
+ AU.addRequired<AAResultsWrapperPass>();
AU.addRequired<MachineDominatorTree>();
+ AU.addRequired<MachinePostDominatorTree>();
AU.addRequired<MachineLoopInfo>();
AU.addPreserved<MachineDominatorTree>();
+ AU.addPreserved<MachinePostDominatorTree>();
AU.addPreserved<MachineLoopInfo>();
if (UseBlockFreqInfo)
AU.addRequired<MachineBlockFrequencyInfo>();
/// for the lifetime of an iteration.
///
/// \return True if the edge is marked as toSplit, false otherwise.
- /// False can be retruned if, for instance, this is not profitable.
+ /// False can be returned if, for instance, this is not profitable.
bool PostponeSplitCriticalEdge(MachineInstr *MI,
MachineBasicBlock *From,
MachineBasicBlock *To,
bool BreakPHIEdge);
- bool SinkInstruction(MachineInstr *MI, bool &SawStore);
+ bool SinkInstruction(MachineInstr *MI, bool &SawStore,
+ AllSuccsCache &AllSuccessors);
bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB,
MachineBasicBlock *DefMBB,
bool &BreakPHIEdge, bool &LocalUse) const;
MachineBasicBlock *FindSuccToSinkTo(MachineInstr *MI, MachineBasicBlock *MBB,
- bool &BreakPHIEdge);
+ bool &BreakPHIEdge, AllSuccsCache &AllSuccessors);
bool isProfitableToSinkTo(unsigned Reg, MachineInstr *MI,
MachineBasicBlock *MBB,
- MachineBasicBlock *SuccToSinkTo);
+ MachineBasicBlock *SuccToSinkTo,
+ AllSuccsCache &AllSuccessors);
bool PerformTrivialForwardCoalescing(MachineInstr *MI,
MachineBasicBlock *MBB);
+
+ SmallVector<MachineBasicBlock *, 4> &
+ GetAllSortedSuccessors(MachineInstr *MI, MachineBasicBlock *MBB,
+ AllSuccsCache &AllSuccessors) const;
};
} // end anonymous namespace
"Machine code sinking", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
-INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
+INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_END(MachineSinking, "machine-sink",
"Machine code sinking", false, false)
TRI = MF.getSubtarget().getRegisterInfo();
MRI = &MF.getRegInfo();
DT = &getAnalysis<MachineDominatorTree>();
+ PDT = &getAnalysis<MachinePostDominatorTree>();
LI = &getAnalysis<MachineLoopInfo>();
MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
- AA = &getAnalysis<AliasAnalysis>();
+ AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
bool EverMadeChange = false;
// Process all basic blocks.
CEBCandidates.clear();
ToSplit.clear();
- for (MachineFunction::iterator I = MF.begin(), E = MF.end();
- I != E; ++I)
- MadeChange |= ProcessBlock(*I);
+ for (auto &MBB: MF)
+ MadeChange |= ProcessBlock(MBB);
// If we have anything we marked as toSplit, split it now.
for (auto &Pair : ToSplit) {
if (!MadeChange) break;
EverMadeChange = true;
}
+
+ // Now clear any kill flags for recorded registers.
+ for (auto I : RegsToClearKillFlags)
+ MRI->clearKillFlags(I);
+ RegsToClearKillFlags.clear();
+
return EverMadeChange;
}
bool MadeChange = false;
+ // Cache all successors, sorted by frequency info and loop depth.
+ AllSuccsCache AllSuccessors;
+
// Walk the basic block bottom-up. Remember if we saw a store.
MachineBasicBlock::iterator I = MBB.end();
--I;
continue;
}
- if (SinkInstruction(MI, SawStore))
+ if (SinkInstruction(MI, SawStore, AllSuccessors))
++NumSunk, MadeChange = true;
// If we just processed the first instruction in the block, we're done.
// If the pass has already considered breaking this edge (during this pass
// through the function), then let's go ahead and break it. This means
// sinking multiple "cheap" instructions into the same block.
- if (!CEBCandidates.insert(std::make_pair(From, To)))
+ if (!CEBCandidates.insert(std::make_pair(From, To)).second)
return true;
if (!MI->isCopy() && !TII->isAsCheapAsAMove(MI))
}
}
-/// isPostDominatedBy - Return true if A is post dominated by B.
-static bool isPostDominatedBy(MachineBasicBlock *A, MachineBasicBlock *B) {
-
- // FIXME - Use real post dominator.
- if (A->succ_size() != 2)
- return false;
- MachineBasicBlock::succ_iterator I = A->succ_begin();
- if (B == *I)
- ++I;
- MachineBasicBlock *OtherSuccBlock = *I;
- if (OtherSuccBlock->succ_size() != 1 ||
- *(OtherSuccBlock->succ_begin()) != B)
- return false;
-
- return true;
-}
-
/// isProfitableToSinkTo - Return true if it is profitable to sink MI.
bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr *MI,
MachineBasicBlock *MBB,
- MachineBasicBlock *SuccToSinkTo) {
+ MachineBasicBlock *SuccToSinkTo,
+ AllSuccsCache &AllSuccessors) {
assert (MI && "Invalid MachineInstr!");
assert (SuccToSinkTo && "Invalid SinkTo Candidate BB");
return false;
// It is profitable if SuccToSinkTo does not post dominate current block.
- if (!isPostDominatedBy(MBB, SuccToSinkTo))
- return true;
+ 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))
+ return true;
// Check if only use in post dominated block is PHI instruction.
bool NonPHIUse = false;
// If SuccToSinkTo post dominates then also it may be profitable if MI
// can further profitably sinked into another block in next round.
bool BreakPHIEdge = false;
- // FIXME - If finding successor is compile time expensive then catch results.
- if (MachineBasicBlock *MBB2 = FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge))
- return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2);
+ // FIXME - If finding successor is compile time expensive then cache results.
+ if (MachineBasicBlock *MBB2 =
+ FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge, AllSuccessors))
+ return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2, AllSuccessors);
// If SuccToSinkTo is final destination and it is a post dominator of current
// block then it is not profitable to sink MI into SuccToSinkTo block.
return false;
}
+/// Get the sorted sequence of successors for this MachineBasicBlock, possibly
+/// computing it if it was not already cached.
+SmallVector<MachineBasicBlock *, 4> &
+MachineSinking::GetAllSortedSuccessors(MachineInstr *MI, MachineBasicBlock *MBB,
+ AllSuccsCache &AllSuccessors) const {
+
+ // Do we have the sorted successors in cache ?
+ auto Succs = AllSuccessors.find(MBB);
+ if (Succs != AllSuccessors.end())
+ return Succs->second;
+
+ SmallVector<MachineBasicBlock *, 4> AllSuccs(MBB->succ_begin(),
+ MBB->succ_end());
+
+ // Handle cases where sinking can happen but where the sink point isn't a
+ // successor. For example:
+ //
+ // x = computation
+ // if () {} else {}
+ // use x
+ //
+ const std::vector<MachineDomTreeNode *> &Children =
+ DT->getNode(MBB)->getChildren();
+ for (const auto &DTChild : Children)
+ // DomTree children of MBB that have MBB as immediate dominator are added.
+ if (DTChild->getIDom()->getBlock() == MI->getParent() &&
+ // Skip MBBs already added to the AllSuccs vector above.
+ !MBB->isSuccessor(DTChild->getBlock()))
+ AllSuccs.push_back(DTChild->getBlock());
+
+ // Sort Successors according to their loop depth or block frequency info.
+ std::stable_sort(
+ AllSuccs.begin(), AllSuccs.end(),
+ [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);
+ });
+
+ auto it = AllSuccessors.insert(std::make_pair(MBB, AllSuccs));
+
+ return it.first->second;
+}
+
/// FindSuccToSinkTo - Find a successor to sink this instruction to.
MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI,
MachineBasicBlock *MBB,
- bool &BreakPHIEdge) {
+ bool &BreakPHIEdge,
+ AllSuccsCache &AllSuccessors) {
assert (MI && "Invalid MachineInstr!");
assert (MBB && "Invalid MachineBasicBlock!");
if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg)))
return nullptr;
- // FIXME: This picks a successor to sink into based on having one
- // successor that dominates all the uses. However, there are cases where
- // sinking can happen but where the sink point isn't a successor. For
- // example:
- //
- // x = computation
- // if () {} else {}
- // use x
- //
- // the instruction could be sunk over the whole diamond for the
- // if/then/else (or loop, etc), allowing it to be sunk into other blocks
- // after that.
-
// Virtual register defs can only be sunk if all their uses are in blocks
// dominated by one of the successors.
if (SuccToSinkTo) {
// 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.
- SmallVector<MachineBasicBlock*, 4> Succs(MBB->succ_begin(),
- MBB->succ_end());
- // Sort Successors according to their loop depth or block frequency info.
- std::stable_sort(
- Succs.begin(), Succs.end(),
- [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);
- });
- for (SmallVectorImpl<MachineBasicBlock *>::iterator SI = Succs.begin(),
- E = Succs.end(); SI != E; ++SI) {
- MachineBasicBlock *SuccBlock = *SI;
+ for (MachineBasicBlock *SuccBlock :
+ GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {
bool LocalUse = false;
if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB,
BreakPHIEdge, LocalUse)) {
// If we couldn't find a block to sink to, ignore this instruction.
if (!SuccToSinkTo)
return nullptr;
- if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo))
+ if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors))
return nullptr;
}
}
// It's not safe to sink instructions to EH landing pad. Control flow into
// landing pad is implicitly defined.
- if (SuccToSinkTo && SuccToSinkTo->isLandingPad())
+ if (SuccToSinkTo && SuccToSinkTo->isEHPad())
return nullptr;
return SuccToSinkTo;
/// 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) {
+bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore,
+ AllSuccsCache &AllSuccessors) {
// Don't sink insert_subreg, subreg_to_reg, reg_sequence. These are meant to
// be close to the source to make it easier to coalesce.
if (AvoidsSinking(MI, MRI))
return false;
// Check if it's safe to move the instruction.
- if (!MI->isSafeToMove(TII, AA, SawStore))
+ if (!MI->isSafeToMove(AA, SawStore))
+ return false;
+
+ // Convergent operations may not be made control-dependent on additional
+ // values.
+ if (MI->isConvergent())
return false;
// FIXME: This should include support for sinking instructions within the
bool BreakPHIEdge = false;
MachineBasicBlock *ParentBlock = MI->getParent();
- MachineBasicBlock *SuccToSinkTo = FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge);
+ MachineBasicBlock *SuccToSinkTo =
+ FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors);
// If there are no outputs, it must have side-effects.
if (!SuccToSinkTo)
// other code paths.
bool TryBreak = false;
bool store = true;
- if (!MI->isSafeToMove(TII, AA, store)) {
+ if (!MI->isSafeToMove(AA, store)) {
DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n");
TryBreak = true;
}
// Conservatively, clear any kill flags, since it's possible that they are no
// longer correct.
- MI->clearKillInfo();
+ // Note that we have to clear the kill flags for any register this instruction
+ // uses as we may sink over another instruction which currently kills the
+ // used registers.
+ for (MachineOperand &MO : MI->operands()) {
+ if (MO.isReg() && MO.isUse())
+ RegsToClearKillFlags.set(MO.getReg()); // Remember to clear kill flags.
+ }
return true;
}
projects / oota-llvm.git / blobdiff