//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/Passes.h"
+#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallSet.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"
#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"
using namespace llvm;
#define DEBUG_TYPE "machine-sink"
cl::desc("Split critical edges during machine sinking"),
cl::init(true), cl::Hidden);
+static cl::opt<bool>
+UseBlockFreqInfo("machine-sink-bfi",
+ cl::desc("Use block frequency info to find successors to sink"),
+ cl::init(true), cl::Hidden);
+
+
STATISTIC(NumSunk, "Number of machine instructions sunk");
STATISTIC(NumSplit, "Number of critical edges split");
STATISTIC(NumCoalesces, "Number of copies coalesced");
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;
// Remember which edges have been considered for breaking.
SmallSet<std::pair<MachineBasicBlock*,MachineBasicBlock*>, 8>
CEBCandidates;
+ // Remember which edges we are about to split.
+ // This is different from CEBCandidates since those edges
+ // will be split.
+ SetVector<std::pair<MachineBasicBlock*,MachineBasicBlock*> > ToSplit;
public:
static char ID; // Pass identification
MachineFunctionPass::getAnalysisUsage(AU);
AU.addRequired<AliasAnalysis>();
AU.addRequired<MachineDominatorTree>();
+ AU.addRequired<MachinePostDominatorTree>();
AU.addRequired<MachineLoopInfo>();
AU.addPreserved<MachineDominatorTree>();
+ AU.addPreserved<MachinePostDominatorTree>();
AU.addPreserved<MachineLoopInfo>();
+ if (UseBlockFreqInfo)
+ AU.addRequired<MachineBlockFrequencyInfo>();
}
void releaseMemory() override {
bool isWorthBreakingCriticalEdge(MachineInstr *MI,
MachineBasicBlock *From,
MachineBasicBlock *To);
- MachineBasicBlock *SplitCriticalEdge(MachineInstr *MI,
- MachineBasicBlock *From,
- MachineBasicBlock *To,
- bool BreakPHIEdge);
+ /// \brief Postpone the splitting of the given critical
+ /// edge (\p From, \p To).
+ ///
+ /// We do not split the edges on the fly. Indeed, this invalidates
+ /// the dominance information and thus triggers a lot of updates
+ /// of that information underneath.
+ /// Instead, we postpone all the splits after each iteration of
+ /// the main loop. That way, the information is at least valid
+ /// for the lifetime of an iteration.
+ ///
+ /// \return True if the edge is marked as toSplit, false otherwise.
+ /// 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 AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB,
MachineBasicBlock *DefMBB,
DEBUG(dbgs() << "*** to: " << *MI);
MRI->replaceRegWith(DstReg, SrcReg);
MI->eraseFromParent();
+
+ // Conservatively, clear any kill flags, since it's possible that they are no
+ // longer correct.
+ MRI->clearKillFlags(SrcReg);
+
++NumCoalesces;
return true;
}
DEBUG(dbgs() << "******** Machine Sinking ********\n");
- const TargetMachine &TM = MF.getTarget();
- TII = TM.getInstrInfo();
- TRI = TM.getRegisterInfo();
+ TII = MF.getSubtarget().getInstrInfo();
+ TRI = MF.getSubtarget().getRegisterInfo();
MRI = &MF.getRegInfo();
DT = &getAnalysis<MachineDominatorTree>();
+ PDT = &getAnalysis<MachinePostDominatorTree>();
LI = &getAnalysis<MachineLoopInfo>();
+ MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
AA = &getAnalysis<AliasAnalysis>();
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);
+ // If we have anything we marked as toSplit, split it now.
+ for (auto &Pair : ToSplit) {
+ auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, this);
+ if (NewSucc != nullptr) {
+ DEBUG(dbgs() << " *** Splitting critical edge:"
+ " BB#" << Pair.first->getNumber()
+ << " -- BB#" << NewSucc->getNumber()
+ << " -- BB#" << Pair.second->getNumber() << '\n');
+ MadeChange = true;
+ ++NumSplit;
+ } else
+ DEBUG(dbgs() << " *** Not legal to break critical edge\n");
+ }
// If this iteration over the code changed anything, keep iterating.
if (!MadeChange) break;
EverMadeChange = true;
// 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() && !MI->isAsCheapAsAMove())
+ if (!MI->isCopy() && !TII->isAsCheapAsAMove(MI))
return true;
// MI is cheap, we probably don't want to break the critical edge for it.
return false;
}
-MachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineInstr *MI,
- MachineBasicBlock *FromBB,
- MachineBasicBlock *ToBB,
- bool BreakPHIEdge) {
+bool MachineSinking::PostponeSplitCriticalEdge(MachineInstr *MI,
+ MachineBasicBlock *FromBB,
+ MachineBasicBlock *ToBB,
+ bool BreakPHIEdge) {
if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB))
- return nullptr;
+ return false;
// Avoid breaking back edge. From == To means backedge for single BB loop.
if (!SplitEdges || FromBB == ToBB)
- return nullptr;
+ return false;
// Check for backedges of more "complex" loops.
if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) &&
LI->isLoopHeader(ToBB))
- return nullptr;
+ return false;
// It's not always legal to break critical edges and sink the computation
// to the edge.
if (*PI == FromBB)
continue;
if (!DT->dominates(ToBB, *PI))
- return nullptr;
+ return false;
}
}
- return FromBB->SplitCriticalEdge(ToBB, this);
+ ToSplit.insert(std::make_pair(FromBB, ToBB));
+
+ return true;
}
static bool AvoidsSinking(MachineInstr *MI, MachineRegisterInfo *MRI) {
}
}
-/// 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,
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.
+ // FIXME - If finding successor is compile time expensive then cache results.
if (MachineBasicBlock *MBB2 = FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge))
return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2);
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) {
}
// Otherwise, we should look at all the successors and decide which one
- // we should sink to.
- // We give successors with smaller loop depth higher priority.
- SmallVector<MachineBasicBlock*, 4> Succs(MBB->succ_begin(), MBB->succ_end());
- // Sort Successors according to their loop depth.
+ // 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());
+
+ // 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 Succs vector above.
+ !MBB->isSuccessor(DTChild->getBlock()))
+ Succs.push_back(DTChild->getBlock());
+
+ // Sort Successors according to their loop depth or block frequency info.
std::stable_sort(
Succs.begin(), Succs.end(),
- [this](const MachineBasicBlock *LHS, const MachineBasicBlock *RHS) {
- return LI->getLoopDepth(LHS) < LI->getLoopDepth(RHS);
+ [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) {
if (!TryBreak)
DEBUG(dbgs() << "Sinking along critical edge.\n");
else {
- MachineBasicBlock *NewSucc =
- SplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);
- if (!NewSucc) {
+ // Mark this edge as to be split.
+ // If the edge can actually be split, the next iteration of the main loop
+ // will sink MI in the newly created block.
+ bool Status =
+ PostponeSplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);
+ if (!Status)
DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
- "break critical edge\n");
- return false;
- } else {
- DEBUG(dbgs() << " *** Splitting critical edge:"
- " BB#" << ParentBlock->getNumber()
- << " -- BB#" << NewSucc->getNumber()
- << " -- BB#" << SuccToSinkTo->getNumber() << '\n');
- SuccToSinkTo = NewSucc;
- ++NumSplit;
- BreakPHIEdge = false;
- }
+ "break critical edge\n");
+ // The instruction will not be sunk this time.
+ return false;
}
}
// BreakPHIEdge is true if all the uses are in the successor MBB being
// sunken into and they are all PHI nodes. In this case, machine-sink must
// break the critical edge first.
- MachineBasicBlock *NewSucc = SplitCriticalEdge(MI, ParentBlock,
- SuccToSinkTo, BreakPHIEdge);
- if (!NewSucc) {
+ bool Status = PostponeSplitCriticalEdge(MI, ParentBlock,
+ SuccToSinkTo, BreakPHIEdge);
+ if (!Status)
DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to "
"break critical edge\n");
- return false;
- }
-
- DEBUG(dbgs() << " *** Splitting critical edge:"
- " BB#" << ParentBlock->getNumber()
- << " -- BB#" << NewSucc->getNumber()
- << " -- BB#" << SuccToSinkTo->getNumber() << '\n');
- SuccToSinkTo = NewSucc;
- ++NumSplit;
+ // The instruction will not be sunk this time.
+ return false;
}
// Determine where to insert into. Skip phi nodes.
projects / oota-llvm.git / blobdiff