diff options
18 files changed, 328 insertions, 61 deletions
diff --git a/llvm/lib/Transforms/Scalar/ADCE.cpp b/llvm/lib/Transforms/Scalar/ADCE.cpp index 976b2fdcd9b..adc903cab31 100644 --- a/llvm/lib/Transforms/Scalar/ADCE.cpp +++ b/llvm/lib/Transforms/Scalar/ADCE.cpp @@ -17,6 +17,7 @@ #include "llvm/Transforms/Scalar/ADCE.h" #include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" @@ -26,6 +27,7 @@ #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" #include "llvm/IR/DebugInfoMetadata.h" +#include "llvm/IR/IRBuilder.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" @@ -37,11 +39,17 @@ using namespace llvm; #define DEBUG_TYPE "adce" STATISTIC(NumRemoved, "Number of instructions removed"); +STATISTIC(NumBranchesRemoved, "Number of branch instructions removed"); // This is a tempoary option until we change the interface // to this pass based on optimization level. static cl::opt<bool> RemoveControlFlowFlag("adce-remove-control-flow", - cl::init(false), cl::Hidden); + cl::init(true), cl::Hidden); + +// This option enables removing of may-be-infinite loops which have no other +// effect. +static cl::opt<bool> RemoveLoops("adce-remove-loops", cl::init(false), + cl::Hidden); namespace { /// Information about Instructions @@ -72,8 +80,11 @@ struct BlockInfoType { /// Corresponding BasicBlock. BasicBlock *BB = nullptr; - /// Cache of BB->getTerminator() + /// Cache of BB->getTerminator(). TerminatorInst *Terminator = nullptr; + + /// Post-order numbering of reverse control flow graph. + unsigned PostOrder; }; class AggressiveDeadCodeElimination { @@ -97,8 +108,9 @@ class AggressiveDeadCodeElimination { /// Set of blocks with not known to have live terminators. SmallPtrSet<BasicBlock *, 16> BlocksWithDeadTerminators; - /// The set of blocks which we have determined are live in the - /// most recent iteration of propagating liveness. + /// The set of blocks which we have determined whose control + /// dependence sources must be live and which have not had + /// those dependences analyized. SmallPtrSet<BasicBlock *, 16> NewLiveBlocks; /// Set up auxiliary data structures for Instructions and BasicBlocks and @@ -113,7 +125,10 @@ class AggressiveDeadCodeElimination { void markLiveInstructions(); /// Mark an instruction as live. void markLive(Instruction *I); - + /// Mark a block as live. + void markLive(BlockInfoType &BB); + void markLive(BasicBlock *BB) { markLive(BlockInfo[BB]); } + /// Mark terminators of control predecessors of a PHI node live. void markPhiLive(PHINode *PN); @@ -130,6 +145,17 @@ class AggressiveDeadCodeElimination { /// was removed. bool removeDeadInstructions(); + /// Identify connected sections of the control flow grap which have + /// dead terminators and rewrite the control flow graph to remove them. + void updateDeadRegions(); + + /// Set the BlockInfo::PostOrder field based on a post-order + /// numbering of the reverse control flow graph. + void computeReversePostOrder(); + + /// Make the terminator of this block an unconditional branch to \p Target. + void makeUnconditional(BasicBlock *BB, BasicBlock *Target); + public: AggressiveDeadCodeElimination(Function &F, PostDominatorTree &PDT) : F(F), PDT(PDT) {} @@ -144,7 +170,7 @@ bool AggressiveDeadCodeElimination::performDeadCodeElimination() { } static bool isUnconditionalBranch(TerminatorInst *Term) { - auto BR = dyn_cast<BranchInst>(Term); + auto *BR = dyn_cast<BranchInst>(Term); return BR && BR->isUnconditional(); } @@ -186,23 +212,65 @@ void AggressiveDeadCodeElimination::initialize() { if (!RemoveControlFlowFlag) return; - // This is temporary: will update with post order traveral to - // find loop bottoms - SmallPtrSet<BasicBlock *, 16> Seen; - for (auto &BB : F) { - Seen.insert(&BB); - TerminatorInst *Term = BB.getTerminator(); - if (isLive(Term)) - continue; + if (!RemoveLoops) { + // This stores state for the depth-first iterator. In addition + // to recording which nodes have been visited we also record whether + // a node is currently on the "stack" of active ancestors of the current + // node. + typedef DenseMap<BasicBlock *, bool> StatusMap ; + class DFState : public StatusMap { + public: + std::pair<StatusMap::iterator, bool> insert(BasicBlock *BB) { + return StatusMap::insert(std::make_pair(BB, true)); + } + + // Invoked after we have visited all children of a node. + void completed(BasicBlock *BB) { (*this)[BB] = false; } - for (auto Succ : successors(&BB)) - if (Seen.count(Succ)) { - // back edge.... - markLive(Term); + // Return true if \p BB is currently on the active stack + // of ancestors. + bool onStack(BasicBlock *BB) { + auto Iter = find(BB); + return Iter != end() && Iter->second; + } + } State; + + State.reserve(F.size()); + // Iterate over blocks in depth-first pre-order and + // treat all edges to a block already seen as loop back edges + // and mark the branch live it if there is a back edge. + for (auto *BB: depth_first_ext(&F.getEntryBlock(), State)) { + TerminatorInst *Term = BB->getTerminator(); + if (isLive(Term)) + continue; + + for (auto *Succ : successors(BB)) + if (State.onStack(Succ)) { + // back edge.... + markLive(Term); + break; + } + } + } + + // Mark blocks live if there is no path from the block to the + // return of the function or a successor for which this is true. + // This protects IDFCalculator which cannot handle such blocks. + for (auto &BBInfoPair : BlockInfo) { + auto &BBInfo = BBInfoPair.second; + if (BBInfo.terminatorIsLive()) + continue; + auto *BB = BBInfo.BB; + if (!PDT.getNode(BB)) { + markLive(BBInfo.Terminator); + continue; + } + for (auto *Succ : successors(BB)) + if (!PDT.getNode(Succ)) { + markLive(BBInfo.Terminator); break; } } - // End temporary handling of loops. // Mark blocks live if there is no path from the block to the // return of the function or a successor for which this is true. @@ -218,7 +286,7 @@ void AggressiveDeadCodeElimination::initialize() { markLive(BBInfo.Terminator); continue; } - for (auto Succ : successors(BB)) + for (auto *Succ : successors(BB)) if (!PDT.getNode(Succ)) { DEBUG(dbgs() << "Successor not post-dominated by return: " << BB->getName() << '\n';); @@ -278,32 +346,19 @@ void AggressiveDeadCodeElimination::markLiveInstructions() { Instruction *LiveInst = Worklist.pop_back_val(); DEBUG(dbgs() << "work live: "; LiveInst->dump();); - // Collect the live debug info scopes attached to this instruction. - if (const DILocation *DL = LiveInst->getDebugLoc()) - collectLiveScopes(*DL); - for (Use &OI : LiveInst->operands()) if (Instruction *Inst = dyn_cast<Instruction>(OI)) markLive(Inst); - + if (auto *PN = dyn_cast<PHINode>(LiveInst)) markPhiLive(PN); } + + // After data flow liveness has been identified, examine which branch + // decisions are required to determine live instructions are executed. markLiveBranchesFromControlDependences(); - if (Worklist.empty()) { - // Temporary until we can actually delete branches. - SmallVector<TerminatorInst *, 16> DeadTerminators; - for (auto *BB : BlocksWithDeadTerminators) - DeadTerminators.push_back(BB->getTerminator()); - for (auto *I : DeadTerminators) - markLive(I); - assert(BlocksWithDeadTerminators.empty()); - // End temporary. - } } while (!Worklist.empty()); - - assert(BlocksWithDeadTerminators.empty()); } void AggressiveDeadCodeElimination::markLive(Instruction *I) { @@ -316,13 +371,26 @@ void AggressiveDeadCodeElimination::markLive(Instruction *I) { Info.Live = true; Worklist.push_back(I); + // Collect the live debug info scopes attached to this instruction. + if (const DILocation *DL = I->getDebugLoc()) + collectLiveScopes(*DL); + // Mark the containing block live auto &BBInfo = *Info.Block; - if (BBInfo.Terminator == I) + if (BBInfo.Terminator == I) { BlocksWithDeadTerminators.erase(BBInfo.BB); + // For live terminators, mark destination blocks + // live to preserve this control flow edges. + if (!BBInfo.UnconditionalBranch) + for (auto *BB : successors(I->getParent())) + markLive(BB); + } + markLive(BBInfo); +} + +void AggressiveDeadCodeElimination::markLive(BlockInfoType &BBInfo) { if (BBInfo.Live) return; - DEBUG(dbgs() << "mark block live: " << BBInfo.BB->getName() << '\n'); BBInfo.Live = true; if (!BBInfo.CFLive) { @@ -332,7 +400,7 @@ void AggressiveDeadCodeElimination::markLive(Instruction *I) { // Mark unconditional branches at the end of live // blocks as live since there is no work to do for them later - if (BBInfo.UnconditionalBranch && I != BBInfo.Terminator) + if (BBInfo.UnconditionalBranch) markLive(BBInfo.Terminator); } @@ -408,7 +476,7 @@ void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() { NewLiveBlocks.clear(); // Dead terminators which control live blocks are now marked live. - for (auto BB : IDFBlocks) { + for (auto *BB : IDFBlocks) { DEBUG(dbgs() << "live control in: " << BB->getName() << '\n'); markLive(BB->getTerminator()); } @@ -421,8 +489,33 @@ void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() { //===----------------------------------------------------------------------===// bool AggressiveDeadCodeElimination::removeDeadInstructions() { + // Updates control and dataflow around dead blocks + updateDeadRegions(); + + DEBUG({ + for (Instruction &I : instructions(F)) { + // Check if the instruction is alive. + if (isLive(&I)) + continue; + + if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I)) { + // Check if the scope of this variable location is alive. + if (AliveScopes.count(DII->getDebugLoc()->getScope())) + continue; + + // If intrinsic is pointing at a live SSA value, there may be an + // earlier optimization bug: if we know the location of the variable, + // why isn't the scope of the location alive? + if (Value *V = DII->getVariableLocation()) + if (Instruction *II = dyn_cast<Instruction>(V)) + if (isLive(II)) + dbgs() << "Dropping debug info for " << *DII << "\n"; + } + } + }); + // The inverse of the live set is the dead set. These are those instructions - // which have no side effects and do not influence the control flow or return + // that have no side effects and do not influence the control flow or return // value of the function, and may therefore be deleted safely. // NOTE: We reuse the Worklist vector here for memory efficiency. for (Instruction &I : instructions(F)) { @@ -430,23 +523,12 @@ bool AggressiveDeadCodeElimination::removeDeadInstructions() { if (isLive(&I)) continue; - assert(!I.isTerminator() && "NYI: Removing Control Flow"); - if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I)) { // Check if the scope of this variable location is alive. if (AliveScopes.count(DII->getDebugLoc()->getScope())) continue; // Fallthrough and drop the intrinsic. - DEBUG({ - // If intrinsic is pointing at a live SSA value, there may be an - // earlier optimization bug: if we know the location of the variable, - // why isn't the scope of the location alive? - if (Value *V = DII->getVariableLocation()) - if (Instruction *II = dyn_cast<Instruction>(V)) - if (isLive(II)) - dbgs() << "Dropping debug info for " << *DII << "\n"; - }); } // Prepare to delete. @@ -462,6 +544,96 @@ bool AggressiveDeadCodeElimination::removeDeadInstructions() { return !Worklist.empty(); } +// A dead region is the set of dead blocks with a common live post-dominator. +void AggressiveDeadCodeElimination::updateDeadRegions() { + + DEBUG({ + dbgs() << "final dead terminator blocks: " << '\n'; + for (auto *BB : BlocksWithDeadTerminators) + dbgs() << '\t' << BB->getName() + << (BlockInfo[BB].Live ? " LIVE\n" : "\n"); + }); + + // Don't compute the post ordering unless we needed it. + bool HavePostOrder = false; + + for (auto *BB : BlocksWithDeadTerminators) { + auto &Info = BlockInfo[BB]; + if (Info.UnconditionalBranch) { + InstInfo[Info.Terminator].Live = true; + continue; + } + + if (!HavePostOrder) { + computeReversePostOrder(); + HavePostOrder = true; + } + + // Add an unconditional branch to the successor closest to the + // end of the function which insures a path to the exit for each + // live edge. + BlockInfoType *PreferredSucc = nullptr; + for (auto *Succ : successors(BB)) { + auto *Info = &BlockInfo[Succ]; + if (!PreferredSucc || PreferredSucc->PostOrder < Info->PostOrder) + PreferredSucc = Info; + } + assert((PreferredSucc && PreferredSucc->PostOrder > 0) && + "Failed to find safe successor for dead branc"); + bool First = true; + for (auto *Succ : successors(BB)) { + if (!First || Succ != PreferredSucc->BB) + Succ->removePredecessor(BB); + else + First = false; + } + makeUnconditional(BB, PreferredSucc->BB); + NumBranchesRemoved += 1; + } +} + +// reverse top-sort order +void AggressiveDeadCodeElimination::computeReversePostOrder() { + + // This provides a post-order numbering of the reverse conrtol flow graph + // Note that it is incomplete in the presence of infinite loops but we don't + // need numbers blocks which don't reach the end of the functions since + // all branches in those blocks are forced live. + + // For each block without successors, extend the DFS from the bloack + // backward through the graph + SmallPtrSet<BasicBlock*, 16> Visited; + unsigned PostOrder = 0; + for (auto &BB : F) { + if (succ_begin(&BB) != succ_end(&BB)) + continue; + for (BasicBlock *Block : inverse_post_order_ext(&BB,Visited)) + BlockInfo[Block].PostOrder = PostOrder++; + } +} + +void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB, + BasicBlock *Target) { + TerminatorInst *PredTerm = BB->getTerminator(); + // Collect the live debug info scopes attached to this instruction. + if (const DILocation *DL = PredTerm->getDebugLoc()) + collectLiveScopes(*DL); + + // Just mark live an existing unconditional branch + if (isUnconditionalBranch(PredTerm)) { + PredTerm->setSuccessor(0, Target); + InstInfo[PredTerm].Live = true; + return; + } + DEBUG(dbgs() << "making unconditional " << BB->getName() << '\n'); + NumBranchesRemoved += 1; + IRBuilder<> Builder(PredTerm); + auto *NewTerm = Builder.CreateBr(Target); + InstInfo[NewTerm].Live = true; + if (const DILocation *DL = PredTerm->getDebugLoc()) + NewTerm->setDebugLoc(DL); +} + //===----------------------------------------------------------------------===// // // Pass Manager integration code @@ -494,7 +666,8 @@ struct ADCELegacyPass : public FunctionPass { void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired<PostDominatorTreeWrapperPass>(); - AU.setPreservesCFG(); // TODO -- will remove when we start removing branches + if (!RemoveControlFlowFlag) + AU.setPreservesCFG(); AU.addPreserved<GlobalsAAWrapperPass>(); } }; diff --git a/llvm/test/Transforms/ADCE/2002-05-23-ZeroArgPHITest.ll b/llvm/test/Transforms/ADCE/2002-05-23-ZeroArgPHITest.ll index 8d1beec8ed3..a9da9c70380 100644 --- a/llvm/test/Transforms/ADCE/2002-05-23-ZeroArgPHITest.ll +++ b/llvm/test/Transforms/ADCE/2002-05-23-ZeroArgPHITest.ll @@ -4,7 +4,8 @@ ; removed even though there were uses still around. Now the uses are filled ; in with a dummy value before the PHI is deleted. ; -; RUN: opt < %s -adce +; RUN: opt < %s -S -adce | grep bb1 +; RUN: opt < %s -S -adce -adce-remove-loops | FileCheck %s %node_t = type { double*, %node_t*, %node_t**, double**, double*, i32, i32 } @@ -17,6 +18,7 @@ bb0: bb1: ; preds = %bb0 %reg107 = load %node_t*, %node_t** %nodelist.upgrd.1 ; <%node_t*> [#uses=2] %cond211 = icmp eq %node_t* %reg107, null ; <i1> [#uses=1] +; CHECK: br label %bb3 br i1 %cond211, label %bb3, label %bb2 bb2: ; preds = %bb2, %bb1 @@ -24,6 +26,7 @@ bb2: ; preds = %bb2, %bb1 %reg212 = getelementptr %node_t, %node_t* %reg109, i64 0, i32 1 ; <%node_t**> [#uses=1] %reg110 = load %node_t*, %node_t** %reg212 ; <%node_t*> [#uses=2] %cond213 = icmp ne %node_t* %reg110, null ; <i1> [#uses=1] +; CHECK: br label %bb3 br i1 %cond213, label %bb2, label %bb3 bb3: ; preds = %bb2, %bb1 diff --git a/llvm/test/Transforms/ADCE/2002-05-28-Crash-distilled.ll b/llvm/test/Transforms/ADCE/2002-05-28-Crash-distilled.ll index 337be9f4fa4..2fefd0a5f98 100644 --- a/llvm/test/Transforms/ADCE/2002-05-28-Crash-distilled.ll +++ b/llvm/test/Transforms/ADCE/2002-05-28-Crash-distilled.ll @@ -1,6 +1,7 @@ ; This testcase is a distilled form of: 2002-05-28-Crash.ll ; RUN: opt < %s -adce +; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s define float @test(i32 %i) { %F = sitofp i32 %i to float ; <float> [#uses=1] @@ -9,6 +10,7 @@ define float @test(i32 %i) { Loop: ; preds = %Loop, %0 %B = icmp ne i32 %I, 0 ; <i1> [#uses=1] +; CHECK: br label %Out br i1 %B, label %Out, label %Loop Out: ; preds = %Loop diff --git a/llvm/test/Transforms/ADCE/2002-05-28-Crash.ll b/llvm/test/Transforms/ADCE/2002-05-28-Crash.ll index d88580afad0..3090792a55a 100644 --- a/llvm/test/Transforms/ADCE/2002-05-28-Crash.ll +++ b/llvm/test/Transforms/ADCE/2002-05-28-Crash.ll @@ -12,6 +12,7 @@ ;} ; ; RUN: opt < %s -adce +; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s define i32 @rx_bitset_empty(i32 %size, i32* %set) { bb1: @@ -28,6 +29,7 @@ bb1: %reg124 = getelementptr i32, i32* %set, i64 %reg114-idxcast-offset.upgrd.1 ; <i32*> [#uses=1] %reg125 = load i32, i32* %reg124 ; <i32> [#uses=1] %cond232 = icmp ne i32 %reg125, 0 ; <i1> [#uses=1] +; CHECK: br label %bb3 br i1 %cond232, label %bb3, label %bb2 bb2: ; preds = %bb2, %bb1 diff --git a/llvm/test/Transforms/ADCE/2002-07-17-AssertionFailure.ll b/llvm/test/Transforms/ADCE/2002-07-17-AssertionFailure.ll index ff8bdb3fd3b..a83d856e9d7 100644 --- a/llvm/test/Transforms/ADCE/2002-07-17-AssertionFailure.ll +++ b/llvm/test/Transforms/ADCE/2002-07-17-AssertionFailure.ll @@ -3,11 +3,12 @@ ; block in this function, it would work fine, but that would be the part we ; have to fix now, wouldn't it.... ; -; RUN: opt < %s -adce +; RUN: opt < %s -adce -S | FileCheck %s define void @foo(i8* %reg5481) { %cast611 = bitcast i8* %reg5481 to i8** ; <i8**> [#uses=1] %reg162 = load i8*, i8** %cast611 ; <i8*> [#uses=1] +; CHECK-NOT: ptrtoint ptrtoint i8* %reg162 to i32 ; <i32>:1 [#uses=0] ret void } diff --git a/llvm/test/Transforms/ADCE/2002-07-17-PHIAssertion.ll b/llvm/test/Transforms/ADCE/2002-07-17-PHIAssertion.ll index 1bf79e8ec6c..bb8ef26c61c 100644 --- a/llvm/test/Transforms/ADCE/2002-07-17-PHIAssertion.ll +++ b/llvm/test/Transforms/ADCE/2002-07-17-PHIAssertion.ll @@ -1,6 +1,6 @@ ; This testcase was extracted from the gzip SPEC benchmark ; -; RUN: opt < %s -adce +; RUN: opt < %s -adce | FileCheck %s @bk = external global i32 ; <i32*> [#uses=2] @hufts = external global i32 ; <i32*> [#uses=1] @@ -16,6 +16,8 @@ bb2: ; preds = %bb6, %bb0 bb3: ; preds = %bb2 br label %UnifiedExitNode +; CHECK-NOT: bb4: +; CHECK-NOT: bb5: bb4: ; preds = %bb2 %reg117 = load i32, i32* @hufts ; <i32> [#uses=2] %cond241 = icmp ule i32 %reg117, %reg128 ; <i1> [#uses=1] diff --git a/llvm/test/Transforms/ADCE/2002-07-29-Segfault.ll b/llvm/test/Transforms/ADCE/2002-07-29-Segfault.ll index 1c8e6e8adf0..6745555a406 100644 --- a/llvm/test/Transforms/ADCE/2002-07-29-Segfault.ll +++ b/llvm/test/Transforms/ADCE/2002-07-29-Segfault.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -adce -disable-output +; RUN: opt < %s -adce -disable-output -adce-remove-loops define void @test() { br label %BB3 diff --git a/llvm/test/Transforms/ADCE/2003-01-22-PredecessorProblem.ll b/llvm/test/Transforms/ADCE/2003-01-22-PredecessorProblem.ll index 17003be9fb1..ac395de6d41 100644 --- a/llvm/test/Transforms/ADCE/2003-01-22-PredecessorProblem.ll +++ b/llvm/test/Transforms/ADCE/2003-01-22-PredecessorProblem.ll @@ -1,5 +1,6 @@ ; Testcase reduced from 197.parser by bugpoint ; RUN: opt < %s -adce +; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s define void @conjunction_prune() { ; <label>:0 @@ -7,16 +8,20 @@ define void @conjunction_prune() { bb19: ; preds = %bb23, %bb22, %0 %reg205 = phi i8* [ null, %bb22 ], [ null, %bb23 ], [ null, %0 ] ; <i8*> [#uses=1] +; CHECK: br label %bb22 br i1 false, label %bb21, label %bb22 bb21: ; preds = %bb19 %cast455 = bitcast i8* %reg205 to i8** ; <i8**> [#uses=0] +; CHECK: br label %bb22 br label %bb22 bb22: ; preds = %bb21, %bb19 +; CHECK: br label %bb23 br i1 false, label %bb19, label %bb23 bb23: ; preds = %bb22 +; CHECK: br label %bb28 br i1 false, label %bb19, label %bb28 bb28: ; preds = %bb23 diff --git a/llvm/test/Transforms/ADCE/2003-04-25-PHIPostDominateProblem.ll b/llvm/test/Transforms/ADCE/2003-04-25-PHIPostDominateProblem.ll index d30df19fc7c..37adba599cd 100644 --- a/llvm/test/Transforms/ADCE/2003-04-25-PHIPostDominateProblem.ll +++ b/llvm/test/Transforms/ADCE/2003-04-25-PHIPostDominateProblem.ll @@ -2,7 +2,8 @@ ; entries for it's postdominator. But I think this can only happen when the ; PHI node is dead, so we just avoid patching up dead PHI nodes. -; RUN: opt < %s -adce +; RUN: opt < %s -adce -S | FileCheck %s +; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s target datalayout = "e-p:32:32" @@ -15,6 +16,7 @@ loopentry: ; preds = %endif, %entry br i1 false, label %no_exit, label %return no_exit: ; preds = %loopentry +; CHECK: br label %then br i1 false, label %then, label %else then: ; preds = %no_exit diff --git a/llvm/test/Transforms/ADCE/2003-06-11-InvalidCFG.ll b/llvm/test/Transforms/ADCE/2003-06-11-InvalidCFG.ll index 7c7e238f9d9..8ff98b7e7b3 100644 --- a/llvm/test/Transforms/ADCE/2003-06-11-InvalidCFG.ll +++ b/llvm/test/Transforms/ADCE/2003-06-11-InvalidCFG.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -adce -disable-output +; RUN: opt < %s -adce -adce-remove-loops -disable-output @G = external global i32* ; <i32**> [#uses=1] diff --git a/llvm/test/Transforms/ADCE/2003-06-24-BadSuccessor.ll b/llvm/test/Transforms/ADCE/2003-06-24-BadSuccessor.ll index 707e14aad0d..48513654f8d 100644 --- a/llvm/test/Transforms/ADCE/2003-06-24-BadSuccessor.ll +++ b/llvm/test/Transforms/ADCE/2003-06-24-BadSuccessor.ll @@ -1,4 +1,6 @@ ; RUN: opt < %s -adce -disable-output +; RUN: opt < %s -adce -adce-remove-loops=true -disable-output + target datalayout = "e-p:32:32" %struct..CppObjTypeDesc = type { i32, i16, i16 } %struct..TypeToken = type { i32, i16, i16 } @@ -30,6 +32,7 @@ loopentry.1: ; preds = %then.53, %endif.14 br i1 false, label %no_exit.1, label %loopentry.0 no_exit.1: ; preds = %loopentry.1 +; CHECK: switch switch i32 0, label %label.17 [ i32 2, label %label.11 i32 19, label %label.10 diff --git a/llvm/test/Transforms/ADCE/2003-06-24-BasicFunctionality.ll b/llvm/test/Transforms/ADCE/2003-06-24-BasicFunctionality.ll index f0de4316436..ac2a30d40b9 100644 --- a/llvm/test/Transforms/ADCE/2003-06-24-BasicFunctionality.ll +++ b/llvm/test/Transforms/ADCE/2003-06-24-BasicFunctionality.ll @@ -1,4 +1,5 @@ -; RUN: opt < %s -adce -simplifycfg -S | not grep then: +; RUN: opt < %s -adce -S | FileCheck %s +; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s define void @dead_test8(i32* %data.1, i32 %idx.1) { entry: @@ -17,7 +18,9 @@ no_exit: ; preds = %endif, %no_exit.preheader %i.0 = phi i32 [ %inc.1, %endif ], [ 0, %no_exit.preheader ] ; <i32> [#uses=1] %tmp.12 = load i32, i32* %tmp.11 ; <i32> [#uses=1] %tmp.14 = sub i32 0, %tmp.12 ; <i32> [#uses=1] +; CHECK-NOT: %tmp.161 %tmp.161 = icmp ne i32 %k.1, %tmp.14 ; <i1> [#uses=1] +; CHECK: br label %then br i1 %tmp.161, label %then, label %else then: ; preds = %no_exit diff --git a/llvm/test/Transforms/ADCE/2003-09-15-InfLoopCrash.ll b/llvm/test/Transforms/ADCE/2003-09-15-InfLoopCrash.ll index 499ac515e44..458045a086f 100644 --- a/llvm/test/Transforms/ADCE/2003-09-15-InfLoopCrash.ll +++ b/llvm/test/Transforms/ADCE/2003-09-15-InfLoopCrash.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -adce -disable-output +; RUN: opt < %s -adce -adce-remove-loops -disable-output define i32 @main() { br label %loop diff --git a/llvm/test/Transforms/ADCE/2003-11-16-MissingPostDominanceInfo.ll b/llvm/test/Transforms/ADCE/2003-11-16-MissingPostDominanceInfo.ll index 5ba1a2eadfc..f60469a6163 100644 --- a/llvm/test/Transforms/ADCE/2003-11-16-MissingPostDominanceInfo.ll +++ b/llvm/test/Transforms/ADCE/2003-11-16-MissingPostDominanceInfo.ll @@ -1,4 +1,6 @@ ; RUN: opt < %s -adce -simplifycfg -S | grep call +; RUN: opt < %s -adce -adce-remove-loops -simplifycfg -S | grep call + declare void @exit(i32) define i32 @main(i32 %argc) { diff --git a/llvm/test/Transforms/ADCE/2004-05-04-UnreachableBlock.ll b/llvm/test/Transforms/ADCE/2004-05-04-UnreachableBlock.ll index 7ee0f468af0..123b6832f0f 100644 --- a/llvm/test/Transforms/ADCE/2004-05-04-UnreachableBlock.ll +++ b/llvm/test/Transforms/ADCE/2004-05-04-UnreachableBlock.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -adce -disable-output +; RUN: opt < %s -adce -adce-remove-loops -disable-output define void @test() { entry: diff --git a/llvm/test/Transforms/ADCE/2016-09-06.ll b/llvm/test/Transforms/ADCE/2016-09-06.ll new file mode 100644 index 00000000000..82c333bb45e --- /dev/null +++ b/llvm/test/Transforms/ADCE/2016-09-06.ll @@ -0,0 +1,55 @@ +; RUN: opt < %s -sroa -adce -adce-remove-loops -S | FileCheck %s +; ModuleID = 'test1.bc' +source_filename = "test1.c" +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +; Function Attrs: nounwind uwtable +define i32 @foo(i32, i32, i32) #0 { + %4 = alloca i32, align 4 + %5 = alloca i32, align 4 + %6 = alloca i32, align 4 + %7 = alloca i32, align 4 + %8 = alloca i32, align 4 + store i32 %0, i32* %4, align 4 + store i32 %1, i32* %5, align 4 + store i32 %2, i32* %6, align 4 + store i32 0, i32* %7, align 4 + %9 = load i32, i32* %5, align 4 + %I10 = icmp ne i32 %9, 0 + br i1 %I10, label %B11, label %B21 + +B11: + store i32 0, i32* %8, align 4 + br label %B12 + +B12: + %I13 = load i32, i32* %8, align 4 + %I14 = load i32, i32* %6, align 4 + %I15 = icmp slt i32 %I13, %I14 +; CHECK: br label %B20 + br i1 %I15, label %B16, label %B20 + +B16: + br label %B17 + +B17: + %I18 = load i32, i32* %8, align 4 + %I19 = add nsw i32 %I18, 1 + store i32 %I19, i32* %8, align 4 + br label %B12 + +B20: + store i32 1, i32* %7, align 4 + br label %B21 + +B21: + %I22 = load i32, i32* %7, align 4 + ret i32 %I22 +} + +attributes #0 = { nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } + +!llvm.ident = !{!0} + +!0 = !{!"clang version 4.0.0 (http://llvm.org/git/clang.git 5864a13abf4490e76ae2eb0896198e1305927df2)"} diff --git a/llvm/test/Transforms/ADCE/basictest1.ll b/llvm/test/Transforms/ADCE/basictest1.ll index 4d0d386384b..76bb5cabf66 100644 --- a/llvm/test/Transforms/ADCE/basictest1.ll +++ b/llvm/test/Transforms/ADCE/basictest1.ll @@ -1,4 +1,6 @@ -; RUN: opt < %s -adce -simplifycfg | llvm-dis +; RUN: opt < %s -adce -S | FileCheck %s +; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s + %FILE = type { i32, i8*, i8*, i8, i8, i32, i32, i32 } %spec_fd_t = type { i32, i32, i32, i8* } @__iob = external global [20 x %FILE] ; <[20 x %FILE]*> [#uses=1] @@ -24,6 +26,7 @@ declare void @perror(i8*) define i32 @spec_getc(i32 %fd) { %reg109 = load i32, i32* @dbglvl ; <i32> [#uses=1] %cond266 = icmp sle i32 %reg109, 4 ; <i1> [#uses=1] +; CHECKL br label %bb3 br i1 %cond266, label %bb3, label %bb2 bb2: ; preds = %0 @@ -55,6 +58,7 @@ bb5: ; preds = %bb3 bb6: ; preds = %bb5 %reg134 = load i32, i32* @dbglvl ; <i32> [#uses=1] %cond271 = icmp sle i32 %reg134, 4 ; <i1> [#uses=1] +; CHECK: br label %bb8 br i1 %cond271, label %bb8, label %bb7 bb7: ; preds = %bb6 @@ -77,6 +81,7 @@ bb9: ; preds = %bb5 store i32 %reg157, i32* %idx5 %reg163 = load i32, i32* @dbglvl ; <i32> [#uses=1] %cond272 = icmp sle i32 %reg163, 4 ; <i1> [#uses=1] +; CHECK: br label %bb11 br i1 %cond272, label %bb11, label %bb10 bb10: ; preds = %bb9 diff --git a/llvm/test/Transforms/ADCE/basictest2.ll b/llvm/test/Transforms/ADCE/basictest2.ll index 26b2e85cccb..50336e18705 100644 --- a/llvm/test/Transforms/ADCE/basictest2.ll +++ b/llvm/test/Transforms/ADCE/basictest2.ll @@ -1,4 +1,6 @@ -; RUN: opt < %s -adce -simplifycfg | llvm-dis +; RUN: opt < %s -adce -disable-output +; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s + %FILE = type { i32, i8*, i8*, i8, i8, i32, i32, i32 } %spec_fd_t = type { i32, i32, i32, i8* } @__iob = external global [20 x %FILE] ; <[20 x %FILE]*> [#uses=1] @@ -24,6 +26,7 @@ declare void @perror(i8*) define i32 @spec_getc(i32 %fd) { %reg109 = load i32, i32* @dbglvl ; <i32> [#uses=1] %cond266 = icmp sle i32 %reg109, 4 ; <i1> [#uses=1] +; CHECK: br label %bb3 br i1 %cond266, label %bb3, label %bb2 bb2: ; preds = %0 @@ -55,6 +58,7 @@ bb5: ; preds = %bb3 bb6: ; preds = %bb5 %reg134 = load i32, i32* @dbglvl ; <i32> [#uses=1] %cond271 = icmp sle i32 %reg134, 4 ; <i1> [#uses=1] +; CHECK: br label %bb8 br i1 %cond271, label %bb8, label %bb7 bb7: ; preds = %bb6 @@ -77,6 +81,7 @@ bb9: ; preds = %bb5 store i32 %reg157, i32* %idx5 %reg163 = load i32, i32* @dbglvl ; <i32> [#uses=1] %cond272 = icmp sle i32 %reg163, 4 ; <i1> [#uses=1] +; CHECK: br label %bb11 br i1 %cond272, label %bb11, label %bb10 bb10: ; preds = %bb9 |
