summaryrefslogtreecommitdiff
path: root/lib/Transforms/Utils
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Utils')
-rw-r--r--lib/Transforms/Utils/CloneFunction.cpp35
-rw-r--r--lib/Transforms/Utils/InlineFunction.cpp13
-rw-r--r--lib/Transforms/Utils/LCSSA.cpp22
-rw-r--r--lib/Transforms/Utils/LoopSimplify.cpp62
4 files changed, 112 insertions, 20 deletions
diff --git a/lib/Transforms/Utils/CloneFunction.cpp b/lib/Transforms/Utils/CloneFunction.cpp
index c5ca56360fc8..4f1052d81433 100644
--- a/lib/Transforms/Utils/CloneFunction.cpp
+++ b/lib/Transforms/Utils/CloneFunction.cpp
@@ -14,6 +14,7 @@
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
@@ -552,9 +553,39 @@ void llvm::CloneAndPruneIntoFromInst(Function *NewFunc, const Function *OldFunc,
// two PHINodes, the iteration over the old PHIs remains valid, and the
// mapping will just map us to the new node (which may not even be a PHI
// node).
+ const DataLayout &DL = NewFunc->getParent()->getDataLayout();
+ SmallSetVector<const Value *, 8> Worklist;
for (unsigned Idx = 0, Size = PHIToResolve.size(); Idx != Size; ++Idx)
- if (PHINode *PN = dyn_cast<PHINode>(VMap[PHIToResolve[Idx]]))
- recursivelySimplifyInstruction(PN);
+ if (isa<PHINode>(VMap[PHIToResolve[Idx]]))
+ Worklist.insert(PHIToResolve[Idx]);
+
+ // Note that we must test the size on each iteration, the worklist can grow.
+ for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
+ const Value *OrigV = Worklist[Idx];
+ auto *I = dyn_cast_or_null<Instruction>(VMap.lookup(OrigV));
+ if (!I)
+ continue;
+
+ // See if this instruction simplifies.
+ Value *SimpleV = SimplifyInstruction(I, DL);
+ if (!SimpleV)
+ continue;
+
+ // Stash away all the uses of the old instruction so we can check them for
+ // recursive simplifications after a RAUW. This is cheaper than checking all
+ // uses of To on the recursive step in most cases.
+ for (const User *U : OrigV->users())
+ Worklist.insert(cast<Instruction>(U));
+
+ // Replace the instruction with its simplified value.
+ I->replaceAllUsesWith(SimpleV);
+
+ // If the original instruction had no side effects, remove it.
+ if (isInstructionTriviallyDead(I))
+ I->eraseFromParent();
+ else
+ VMap[OrigV] = I;
+ }
// Now that the inlined function body has been fully constructed, go through
// and zap unconditional fall-through branches. This happens all the time when
diff --git a/lib/Transforms/Utils/InlineFunction.cpp b/lib/Transforms/Utils/InlineFunction.cpp
index 1fbb19d2b8ad..e82c07fd7b59 100644
--- a/lib/Transforms/Utils/InlineFunction.cpp
+++ b/lib/Transforms/Utils/InlineFunction.cpp
@@ -1294,6 +1294,13 @@ updateInlinedAtInfo(const DebugLoc &DL, DILocation *InlinedAtNode,
return DebugLoc::get(DL.getLine(), DL.getCol(), DL.getScope(), Last);
}
+/// Return the result of AI->isStaticAlloca() if AI were moved to the entry
+/// block. Allocas used in inalloca calls and allocas of dynamic array size
+/// cannot be static.
+static bool allocaWouldBeStaticInEntry(const AllocaInst *AI ) {
+ return isa<Constant>(AI->getArraySize()) && !AI->isUsedWithInAlloca();
+}
+
/// Update inlined instructions' line numbers to
/// to encode location where these instructions are inlined.
static void fixupLineNumbers(Function *Fn, Function::iterator FI,
@@ -1328,7 +1335,7 @@ static void fixupLineNumbers(Function *Fn, Function::iterator FI,
// Don't update static allocas, as they may get moved later.
if (auto *AI = dyn_cast<AllocaInst>(BI))
- if (isa<Constant>(AI->getArraySize()))
+ if (allocaWouldBeStaticInEntry(AI))
continue;
BI->setDebugLoc(TheCallDL);
@@ -1626,7 +1633,7 @@ bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI,
continue;
}
- if (!isa<Constant>(AI->getArraySize()))
+ if (!allocaWouldBeStaticInEntry(AI))
continue;
// Keep track of the static allocas that we inline into the caller.
@@ -1635,7 +1642,7 @@ bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI,
// Scan for the block of allocas that we can move over, and move them
// all at once.
while (isa<AllocaInst>(I) &&
- isa<Constant>(cast<AllocaInst>(I)->getArraySize())) {
+ allocaWouldBeStaticInEntry(cast<AllocaInst>(I))) {
IFI.StaticAllocas.push_back(cast<AllocaInst>(I));
++I;
}
diff --git a/lib/Transforms/Utils/LCSSA.cpp b/lib/Transforms/Utils/LCSSA.cpp
index 9658966779b9..0d5a25b8ebc5 100644
--- a/lib/Transforms/Utils/LCSSA.cpp
+++ b/lib/Transforms/Utils/LCSSA.cpp
@@ -64,6 +64,7 @@ bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
DominatorTree &DT, LoopInfo &LI) {
SmallVector<Use *, 16> UsesToRewrite;
SmallVector<BasicBlock *, 8> ExitBlocks;
+ SmallSetVector<PHINode *, 16> PHIsToRemove;
PredIteratorCache PredCache;
bool Changed = false;
@@ -115,7 +116,8 @@ bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
SmallVector<PHINode *, 16> AddedPHIs;
SmallVector<PHINode *, 8> PostProcessPHIs;
- SSAUpdater SSAUpdate;
+ SmallVector<PHINode *, 4> InsertedPHIs;
+ SSAUpdater SSAUpdate(&InsertedPHIs);
SSAUpdate.Initialize(I->getType(), I->getName());
// Insert the LCSSA phi's into all of the exit blocks dominated by the
@@ -184,6 +186,14 @@ bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
// Otherwise, do full PHI insertion.
SSAUpdate.RewriteUse(*UseToRewrite);
+
+ // SSAUpdater might have inserted phi-nodes inside other loops. We'll need
+ // to post-process them to keep LCSSA form.
+ for (PHINode *InsertedPN : InsertedPHIs) {
+ if (auto *OtherLoop = LI.getLoopFor(InsertedPN->getParent()))
+ if (!L->contains(OtherLoop))
+ PostProcessPHIs.push_back(InsertedPN);
+ }
}
// Post process PHI instructions that were inserted into another disjoint
@@ -196,13 +206,19 @@ bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
Worklist.push_back(PostProcessPN);
}
- // Remove PHI nodes that did not have any uses rewritten.
+ // Keep track of PHI nodes that we want to remove because they did not have
+ // any uses rewritten.
for (PHINode *PN : AddedPHIs)
if (PN->use_empty())
- PN->eraseFromParent();
+ PHIsToRemove.insert(PN);
Changed = true;
}
+ // Remove PHI nodes that did not have any uses rewritten.
+ for (PHINode *PN : PHIsToRemove) {
+ assert (PN->use_empty() && "Trying to remove a phi with uses.");
+ PN->eraseFromParent();
+ }
return Changed;
}
diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp
index b3a928bf7753..2846e8f235b7 100644
--- a/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/lib/Transforms/Utils/LoopSimplify.cpp
@@ -327,6 +327,8 @@ static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,
else
NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I));
+ SmallVector<BasicBlock *, 8> OuterLoopBlocks;
+ OuterLoopBlocks.push_back(NewBB);
// Now that we know which blocks are in L and which need to be moved to
// OuterLoop, move any blocks that need it.
for (unsigned i = 0; i != L->getBlocks().size(); ++i) {
@@ -334,12 +336,53 @@ static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,
if (!BlocksInL.count(BB)) {
// Move this block to the parent, updating the exit blocks sets
L->removeBlockFromLoop(BB);
- if ((*LI)[BB] == L)
+ if ((*LI)[BB] == L) {
LI->changeLoopFor(BB, NewOuter);
+ OuterLoopBlocks.push_back(BB);
+ }
--i;
}
}
+ // Split edges to exit blocks from the inner loop, if they emerged in the
+ // process of separating the outer one.
+ SmallVector<BasicBlock *, 8> ExitBlocks;
+ L->getExitBlocks(ExitBlocks);
+ SmallSetVector<BasicBlock *, 8> ExitBlockSet(ExitBlocks.begin(),
+ ExitBlocks.end());
+ for (BasicBlock *ExitBlock : ExitBlockSet) {
+ if (any_of(predecessors(ExitBlock),
+ [L](BasicBlock *BB) { return !L->contains(BB); })) {
+ rewriteLoopExitBlock(L, ExitBlock, DT, LI, PreserveLCSSA);
+ }
+ }
+
+ if (PreserveLCSSA) {
+ // Fix LCSSA form for L. Some values, which previously were only used inside
+ // L, can now be used in NewOuter loop. We need to insert phi-nodes for them
+ // in corresponding exit blocks.
+
+ // Go through all instructions in OuterLoopBlocks and check if they are
+ // using operands from the inner loop. In this case we'll need to fix LCSSA
+ // for these instructions.
+ SmallSetVector<Instruction *, 8> WorklistSet;
+ for (BasicBlock *OuterBB: OuterLoopBlocks) {
+ for (Instruction &I : *OuterBB) {
+ for (Value *Op : I.operands()) {
+ Instruction *OpI = dyn_cast<Instruction>(Op);
+ if (!OpI || !L->contains(OpI))
+ continue;
+ WorklistSet.insert(OpI);
+ }
+ }
+ }
+ SmallVector<Instruction *, 8> Worklist(WorklistSet.begin(),
+ WorklistSet.end());
+ formLCSSAForInstructions(Worklist, *DT, *LI);
+ assert(NewOuter->isRecursivelyLCSSAForm(*DT) &&
+ "LCSSA is broken after separating nested loops!");
+ }
+
return NewOuter;
}
@@ -541,17 +584,12 @@ ReprocessLoop:
SmallSetVector<BasicBlock *, 8> ExitBlockSet(ExitBlocks.begin(),
ExitBlocks.end());
for (BasicBlock *ExitBlock : ExitBlockSet) {
- for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock);
- PI != PE; ++PI)
- // Must be exactly this loop: no subloops, parent loops, or non-loop preds
- // allowed.
- if (!L->contains(*PI)) {
- if (rewriteLoopExitBlock(L, ExitBlock, DT, LI, PreserveLCSSA)) {
- ++NumInserted;
- Changed = true;
- }
- break;
- }
+ if (any_of(predecessors(ExitBlock),
+ [L](BasicBlock *BB) { return !L->contains(BB); })) {
+ rewriteLoopExitBlock(L, ExitBlock, DT, LI, PreserveLCSSA);
+ ++NumInserted;
+ Changed = true;
+ }
}
// If the header has more than two predecessors at this point (from the
generated by cgit v1.3 (git 2.53.0) at 2026-05-13 20:17:28 +0000