namespace llvm {
-class AliasAnalysis;
class MemoryDependenceAnalysis;
class DominatorTree;
class LoopInfo;
/// any single-entry PHI nodes in it, fold them away. This handles the case
/// when all entries to the PHI nodes in a block are guaranteed equal, such as
/// when the block has exactly one predecessor.
-void FoldSingleEntryPHINodes(BasicBlock *BB, AliasAnalysis *AA = nullptr,
+void FoldSingleEntryPHINodes(BasicBlock *BB,
MemoryDependenceAnalysis *MemDep = nullptr);
/// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it
/// if possible. The return value indicates success or failure.
bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT = nullptr,
LoopInfo *LI = nullptr,
- AliasAnalysis *AA = nullptr,
MemoryDependenceAnalysis *MemDep = nullptr);
// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI)
/// This provides a builder interface for overriding the default options used
/// during critical edge splitting.
struct CriticalEdgeSplittingOptions {
- AliasAnalysis *AA;
DominatorTree *DT;
LoopInfo *LI;
bool MergeIdenticalEdges;
bool DontDeleteUselessPHIs;
bool PreserveLCSSA;
- CriticalEdgeSplittingOptions()
- : AA(nullptr), DT(nullptr), LI(nullptr), MergeIdenticalEdges(false),
- DontDeleteUselessPHIs(false), PreserveLCSSA(false) {}
-
- /// \brief Basic case of setting up all the analysis.
- CriticalEdgeSplittingOptions(AliasAnalysis *AA, DominatorTree *DT = nullptr,
+ CriticalEdgeSplittingOptions(DominatorTree *DT = nullptr,
LoopInfo *LI = nullptr)
- : AA(AA), DT(DT), LI(LI), MergeIdenticalEdges(false),
- DontDeleteUselessPHIs(false), PreserveLCSSA(false) {}
-
- /// \brief A common pattern is to preserve the dominator tree and loop
- /// info but not care about AA.
- CriticalEdgeSplittingOptions(DominatorTree *DT, LoopInfo *LI)
- : AA(nullptr), DT(DT), LI(LI), MergeIdenticalEdges(false),
+ : DT(DT), LI(LI), MergeIdenticalEdges(false),
DontDeleteUselessPHIs(false), PreserveLCSSA(false) {}
CriticalEdgeSplittingOptions &setMergeIdenticalEdges() {
/// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more
/// details on this case.
///
-/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
-/// DominanceFrontier, LoopInfo, and LCCSA but no other analyses.
-/// In particular, it does not preserve LoopSimplify (because it's
-/// complicated to handle the case where one of the edges being split
-/// is an exit of a loop with other exits).
+/// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but
+/// no other analyses. In particular, it does not preserve LoopSimplify
+/// (because it's complicated to handle the case where one of the edges being
+/// split is an exit of a loop with other exits).
///
BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
const char *Suffix,
- AliasAnalysis *AA = nullptr,
DominatorTree *DT = nullptr,
LoopInfo *LI = nullptr,
bool PreserveLCSSA = false);
/// OrigBB is clone into both of the new basic blocks. The new blocks are given
/// the suffixes 'Suffix1' and 'Suffix2', and are returned in the NewBBs vector.
///
-/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
-/// DominanceFrontier, LoopInfo, and LCCSA but no other analyses. In particular,
-/// it does not preserve LoopSimplify (because it's complicated to handle the
-/// case where one of the edges being split is an exit of a loop with other
-/// exits).
+/// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but
+/// no other analyses. In particular, it does not preserve LoopSimplify
+/// (because it's complicated to handle the case where one of the edges being
+/// split is an exit of a loop with other exits).
///
void SplitLandingPadPredecessors(BasicBlock *OrigBB,
ArrayRef<BasicBlock *> Preds,
const char *Suffix, const char *Suffix2,
SmallVectorImpl<BasicBlock *> &NewBBs,
- AliasAnalysis *AA = nullptr,
DominatorTree *DT = nullptr,
LoopInfo *LI = nullptr,
bool PreserveLCSSA = false);
/// will optionally update \c AliasAnalysis and \c ScalarEvolution analyses if
/// passed into it.
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP,
- AliasAnalysis *AA = nullptr, ScalarEvolution *SE = nullptr,
- AssumptionCache *AC = nullptr);
+ ScalarEvolution *SE = nullptr, AssumptionCache *AC = nullptr);
/// \brief Put loop into LCSSA form.
///
///
/// This is required for correctness, so it must be done at -O0.
///
-static void SplitCriticalSideEffectEdges(Function &Fn, AliasAnalysis *AA) {
+static void SplitCriticalSideEffectEdges(Function &Fn) {
// Loop for blocks with phi nodes.
for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
PHINode *PN = dyn_cast<PHINode>(BB->begin());
// Okay, we have to split this edge.
SplitCriticalEdge(
Pred->getTerminator(), GetSuccessorNumber(Pred, BB),
- CriticalEdgeSplittingOptions(AA).setMergeIdenticalEdges());
+ CriticalEdgeSplittingOptions().setMergeIdenticalEdges());
goto ReprocessBlock;
}
}
DEBUG(dbgs() << "\n\n\n=== " << Fn.getName() << "\n");
- SplitCriticalSideEffectEdges(const_cast<Function&>(Fn), AA);
+ SplitCriticalSideEffectEdges(const_cast<Function &>(Fn));
CurDAG->init(*MF);
FuncInfo->set(Fn, *MF, CurDAG);
if (std::find(Latches.begin(), Latches.end(), *PI) == Latches.end())
Preds.push_back(*PI);
}
- BB = llvm::SplitBlockPredecessors(BB, Preds, "endcf.split", nullptr, DT,
- LI, false);
+ BB = llvm::SplitBlockPredecessors(BB, Preds, "endcf.split", DT, LI, false);
}
CallInst::Create(EndCf, popSaved(), "", BB->getFirstInsertionPt());
for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) {
BasicBlock *BB = FI++;
- bool removedBlock = MergeBlockIntoPredecessor(
- BB, DT, /* LoopInfo */ nullptr, VN.getAliasAnalysis(), MD);
+ bool removedBlock =
+ MergeBlockIntoPredecessor(BB, DT, /* LoopInfo */ nullptr, MD);
if (removedBlock) ++NumGVNBlocks;
Changed |= removedBlock;
/// Split the critical edge connecting the given two blocks, and return
/// the block inserted to the critical edge.
BasicBlock *GVN::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) {
- BasicBlock *BB = SplitCriticalEdge(
- Pred, Succ, CriticalEdgeSplittingOptions(getAliasAnalysis(), DT));
+ BasicBlock *BB =
+ SplitCriticalEdge(Pred, Succ, CriticalEdgeSplittingOptions(DT));
if (MD)
MD->invalidateCachedPredecessors();
return BB;
do {
std::pair<TerminatorInst*, unsigned> Edge = toSplit.pop_back_val();
SplitCriticalEdge(Edge.first, Edge.second,
- CriticalEdgeSplittingOptions(getAliasAnalysis(), DT));
+ CriticalEdgeSplittingOptions(DT));
} while (!toSplit.empty());
if (MD) MD->invalidateCachedPredecessors();
return true;
.setDontDeleteUselessPHIs());
} else {
SmallVector<BasicBlock*, 2> NewBBs;
- SplitLandingPadPredecessors(Parent, BB, "", "", NewBBs,
- /*AliasAnalysis*/ nullptr, &DT, &LI);
+ SplitLandingPadPredecessors(Parent, BB, "", "", NewBBs, &DT, &LI);
NewBB = NewBBs[0];
}
// If NewBB==NULL, then SplitCriticalEdge refused to split because all
// Although SplitBlockPredecessors doesn't preserve loop-simplify in
// general, if we call it on all predecessors of all exits then it does.
- SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa",
- /*AliasAnalysis*/ nullptr, DT, LI,
+ SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", DT, LI,
/*PreserveLCSSA*/ true);
}
}
DominatorTree &DT) {
BasicBlock *Ret = BB;
if (!BB->getUniquePredecessor()) {
- Ret = SplitBlockPredecessors(BB, InvokeParent, "", nullptr, &DT);
+ Ret = SplitBlockPredecessors(BB, InvokeParent, "", &DT);
}
// Now that 'ret' has unique predecessor we can safely remove all phi nodes
/// any single-entry PHI nodes in it, fold them away. This handles the case
/// when all entries to the PHI nodes in a block are guaranteed equal, such as
/// when the block has exactly one predecessor.
-void llvm::FoldSingleEntryPHINodes(BasicBlock *BB, AliasAnalysis *AA,
+void llvm::FoldSingleEntryPHINodes(BasicBlock *BB,
MemoryDependenceAnalysis *MemDep) {
if (!isa<PHINode>(BB->begin())) return;
/// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor,
/// if possible. The return value indicates success or failure.
bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT,
- LoopInfo *LI, AliasAnalysis *AA,
+ LoopInfo *LI,
MemoryDependenceAnalysis *MemDep) {
// Don't merge away blocks who have their address taken.
if (BB->hasAddressTaken()) return false;
// Begin by getting rid of unneeded PHIs.
if (isa<PHINode>(BB->front()))
- FoldSingleEntryPHINodes(BB, AA, MemDep);
+ FoldSingleEntryPHINodes(BB, MemDep);
// Delete the unconditional branch from the predecessor...
PredBB->getInstList().pop_back();
/// from NewBB. This also updates AliasAnalysis, if available.
static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB,
ArrayRef<BasicBlock *> Preds, BranchInst *BI,
- AliasAnalysis *AA, bool HasLoopExit) {
+ bool HasLoopExit) {
// Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB.
SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end());
for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) {
///
BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
ArrayRef<BasicBlock *> Preds,
- const char *Suffix, AliasAnalysis *AA,
- DominatorTree *DT, LoopInfo *LI,
- bool PreserveLCSSA) {
+ const char *Suffix, DominatorTree *DT,
+ LoopInfo *LI, bool PreserveLCSSA) {
// For the landingpads we need to act a bit differently.
// Delegate this work to the SplitLandingPadPredecessors.
if (BB->isLandingPad()) {
SmallVector<BasicBlock*, 2> NewBBs;
std::string NewName = std::string(Suffix) + ".split-lp";
- SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(),
- NewBBs, AA, DT, LI, PreserveLCSSA);
+ SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs, DT,
+ LI, PreserveLCSSA);
return NewBBs[0];
}
HasLoopExit);
// Update the PHI nodes in BB with the values coming from NewBB.
- UpdatePHINodes(BB, NewBB, Preds, BI, AA, HasLoopExit);
+ UpdatePHINodes(BB, NewBB, Preds, BI, HasLoopExit);
return NewBB;
}
ArrayRef<BasicBlock *> Preds,
const char *Suffix1, const char *Suffix2,
SmallVectorImpl<BasicBlock *> &NewBBs,
- AliasAnalysis *AA, DominatorTree *DT,
- LoopInfo *LI, bool PreserveLCSSA) {
+ DominatorTree *DT, LoopInfo *LI,
+ bool PreserveLCSSA) {
assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!");
// Create a new basic block for OrigBB's predecessors listed in Preds. Insert
HasLoopExit);
// Update the PHI nodes in OrigBB with the values coming from NewBB1.
- UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, AA, HasLoopExit);
+ UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, HasLoopExit);
// Move the remaining edges from OrigBB to point to NewBB2.
SmallVector<BasicBlock*, 8> NewBB2Preds;
PreserveLCSSA, HasLoopExit);
// Update the PHI nodes in OrigBB with the values coming from NewBB2.
- UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, AA, HasLoopExit);
+ UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, HasLoopExit);
}
LandingPadInst *LPad = OrigBB->getLandingPadInst();
}
// If we have nothing to update, just return.
- auto *AA = Options.AA;
auto *DT = Options.DT;
auto *LI = Options.LI;
if (!DT && !LI)
assert(!DestBB->isLandingPad() &&
"We don't split edges to landing pads!");
BasicBlock *NewExitBB = SplitBlockPredecessors(
- DestBB, LoopPreds, "split", AA, DT, LI, Options.PreserveLCSSA);
+ DestBB, LoopPreds, "split", DT, LI, Options.PreserveLCSSA);
if (Options.PreserveLCSSA)
createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB);
}
BasicBlock *Header = L->getHeader();
// Get analyses that we try to update.
- auto *AA = PP->getAnalysisIfAvailable<AliasAnalysis>();
auto *DTWP = PP->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
auto *LIWP = PP->getAnalysisIfAvailable<LoopInfoWrapperPass>();
// Split out the loop pre-header.
BasicBlock *PreheaderBB;
- PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader",
- AA, DT, LI, PreserveLCSSA);
+ PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader", DT,
+ LI, PreserveLCSSA);
DEBUG(dbgs() << "LoopSimplify: Creating pre-header "
<< PreheaderBB->getName() << "\n");
/// This method is used to split exit blocks that have predecessors outside of
/// the loop.
static BasicBlock *rewriteLoopExitBlock(Loop *L, BasicBlock *Exit,
- AliasAnalysis *AA, DominatorTree *DT,
- LoopInfo *LI, Pass *PP) {
+ DominatorTree *DT, LoopInfo *LI,
+ Pass *PP) {
SmallVector<BasicBlock*, 8> LoopBlocks;
for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) {
BasicBlock *P = *I;
bool PreserveLCSSA = PP->mustPreserveAnalysisID(LCSSAID);
- NewExitBB = SplitBlockPredecessors(Exit, LoopBlocks, ".loopexit", AA, DT,
- LI, PreserveLCSSA);
+ NewExitBB = SplitBlockPredecessors(Exit, LoopBlocks, ".loopexit", DT, LI,
+ PreserveLCSSA);
DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "
<< NewExitBB->getName() << "\n");
/// \brief The first part of loop-nestification is to find a PHI node that tells
/// us how to partition the loops.
-static PHINode *findPHIToPartitionLoops(Loop *L, AliasAnalysis *AA,
- DominatorTree *DT,
+static PHINode *findPHIToPartitionLoops(Loop *L, DominatorTree *DT,
AssumptionCache *AC) {
const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) {
/// created.
///
static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,
- AliasAnalysis *AA, DominatorTree *DT,
- LoopInfo *LI, ScalarEvolution *SE, Pass *PP,
+ DominatorTree *DT, LoopInfo *LI,
+ ScalarEvolution *SE, Pass *PP,
AssumptionCache *AC) {
// Don't try to separate loops without a preheader.
if (!Preheader)
assert(!L->getHeader()->isLandingPad() &&
"Can't insert backedge to landing pad");
- PHINode *PN = findPHIToPartitionLoops(L, AA, DT, AC);
+ PHINode *PN = findPHIToPartitionLoops(L, DT, AC);
if (!PN) return nullptr; // No known way to partition.
// Pull out all predecessors that have varying values in the loop. This
BasicBlock *Header = L->getHeader();
BasicBlock *NewBB = SplitBlockPredecessors(Header, OuterLoopPreds, ".outer",
- AA, DT, LI, PreserveLCSSA);
+ DT, LI, PreserveLCSSA);
// Make sure that NewBB is put someplace intelligent, which doesn't mess up
// code layout too horribly.
/// and have that block branch to the loop header. This ensures that loops
/// have exactly one backedge.
static BasicBlock *insertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader,
- AliasAnalysis *AA,
DominatorTree *DT, LoopInfo *LI) {
assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!");
/// specific analyses. Rather than a pass it would be much cleaner and more
/// explicit if they accepted the analysis directly and then updated it.
static bool simplifyOneLoop(Loop *L, SmallVectorImpl<Loop *> &Worklist,
- AliasAnalysis *AA, DominatorTree *DT, LoopInfo *LI,
+ DominatorTree *DT, LoopInfo *LI,
ScalarEvolution *SE, Pass *PP,
AssumptionCache *AC) {
bool Changed = false;
// Must be exactly this loop: no subloops, parent loops, or non-loop preds
// allowed.
if (!L->contains(*PI)) {
- if (rewriteLoopExitBlock(L, ExitBlock, AA, DT, LI, PP)) {
+ if (rewriteLoopExitBlock(L, ExitBlock, DT, LI, PP)) {
++NumInserted;
Changed = true;
}
// this for loops with a giant number of backedges, just factor them into a
// common backedge instead.
if (L->getNumBackEdges() < 8) {
- if (Loop *OuterL =
- separateNestedLoop(L, Preheader, AA, DT, LI, SE, PP, AC)) {
+ if (Loop *OuterL = separateNestedLoop(L, Preheader, DT, LI, SE, PP, AC)) {
++NumNested;
// Enqueue the outer loop as it should be processed next in our
// depth-first nest walk.
// If we either couldn't, or didn't want to, identify nesting of the loops,
// insert a new block that all backedges target, then make it jump to the
// loop header.
- LoopLatch = insertUniqueBackedgeBlock(L, Preheader, AA, DT, LI);
+ LoopLatch = insertUniqueBackedgeBlock(L, Preheader, DT, LI);
if (LoopLatch) {
++NumInserted;
Changed = true;
}
bool llvm::simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP,
- AliasAnalysis *AA, ScalarEvolution *SE,
- AssumptionCache *AC) {
+ ScalarEvolution *SE, AssumptionCache *AC) {
bool Changed = false;
// Worklist maintains our depth-first queue of loops in this nest to process.
}
while (!Worklist.empty())
- Changed |= simplifyOneLoop(Worklist.pop_back_val(), Worklist, AA, DT, LI,
- SE, PP, AC);
+ Changed |=
+ simplifyOneLoop(Worklist.pop_back_val(), Worklist, DT, LI, SE, PP, AC);
return Changed;
}
initializeLoopSimplifyPass(*PassRegistry::getPassRegistry());
}
- // AA - If we have an alias analysis object to update, this is it, otherwise
- // this is null.
- AliasAnalysis *AA;
DominatorTree *DT;
LoopInfo *LI;
ScalarEvolution *SE;
///
bool LoopSimplify::runOnFunction(Function &F) {
bool Changed = false;
- AA = getAnalysisIfAvailable<AliasAnalysis>();
LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
SE = getAnalysisIfAvailable<ScalarEvolution>();
// Simplify each loop nest in the function.
for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
- Changed |= simplifyLoop(*I, DT, LI, this, AA, SE, AC);
+ Changed |= simplifyLoop(*I, DT, LI, this, SE, AC);
return Changed;
}
if (!OuterL && !CompletelyUnroll)
OuterL = L;
if (OuterL) {
- simplifyLoop(OuterL, DT, LI, PP, /*AliasAnalysis*/ nullptr, SE, AC);
+ simplifyLoop(OuterL, DT, LI, PP, SE, AC);
// LCSSA must be performed on the outermost affected loop. The unrolled
// loop's last loop latch is guaranteed to be in the outermost loop after
static void ConnectProlog(Loop *L, Value *BECount, unsigned Count,
BasicBlock *LastPrologBB, BasicBlock *PrologEnd,
BasicBlock *OrigPH, BasicBlock *NewPH,
- ValueToValueMapTy &VMap, AliasAnalysis *AA,
- DominatorTree *DT, LoopInfo *LI, Pass *P) {
+ ValueToValueMapTy &VMap, DominatorTree *DT,
+ LoopInfo *LI, Pass *P) {
BasicBlock *Latch = L->getLoopLatch();
assert(Latch && "Loop must have a latch");
assert(Exit && "Loop must have a single exit block only");
// Split the exit to maintain loop canonicalization guarantees
SmallVector<BasicBlock*, 4> Preds(pred_begin(Exit), pred_end(Exit));
- SplitBlockPredecessors(Exit, Preds, ".unr-lcssa", AA, DT, LI,
+ SplitBlockPredecessors(Exit, Preds, ".unr-lcssa", DT, LI,
P->mustPreserveAnalysisID(LCSSAID));
// Add the branch to the exit block (around the unrolled loop)
B.CreateCondBr(BrLoopExit, Exit, NewPH);
// Connect the prolog code to the original loop and update the
// PHI functions.
BasicBlock *LastLoopBB = cast<BasicBlock>(VMap[Latch]);
- ConnectProlog(L, BECount, Count, LastLoopBB, PEnd, PH, NewPH, VMap,
- /*AliasAnalysis*/ nullptr, DT, LI, LPM->getAsPass());
+ ConnectProlog(L, BECount, Count, LastLoopBB, PEnd, PH, NewPH, VMap, DT, LI,
+ LPM->getAsPass());
NumRuntimeUnrolled++;
return true;
}
projects / oota-llvm.git / commitdiff