diff options
author | Jakub Kuderski <kubakuderski@gmail.com> | 2017-08-17 01:41:49 +0000 |
---|---|---|
committer | Jakub Kuderski <kubakuderski@gmail.com> | 2017-08-17 01:41:49 +0000 |
commit | 85bef5a5c4c8a56a9b8ef9e815d88d03faee7876 (patch) | |
tree | 0f72c75901fd89eb2252c116991e7f8be805930f | |
parent | 994272f0314bf9f902fb9bcc22e58bb08472cea5 (diff) |
Reapply: [ADCE][Dominators] Teach ADCE to preserve dominators
Summary:
This patch teaches ADCE to preserve both DominatorTrees and PostDominatorTrees.
I didn't notice any performance impact when bootstrapping clang with this patch.
The patch was originally committed in r311039 and reverted in r311049.
This revision fixes the problem with not adding a dependency on the
DominatorTreeWrapperPass for the LegacyPassManager.
Reviewers: dberlin, chandlerc, sanjoy, davide, grosser, brzycki
Reviewed By: davide
Subscribers: grandinj, zhendongsu, llvm-commits, david2050
Differential Revision: https://reviews.llvm.org/D35869
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@311057 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | include/llvm/Support/GenericDomTreeConstruction.h | 7 | ||||
-rw-r--r-- | lib/Transforms/Scalar/ADCE.cpp | 53 | ||||
-rw-r--r-- | test/Transforms/ADCE/domtree-DoubleDeletion.ll | 39 | ||||
-rw-r--r-- | test/Transforms/ADCE/unreachable.ll | 18 |
4 files changed, 109 insertions, 8 deletions
diff --git a/include/llvm/Support/GenericDomTreeConstruction.h b/include/llvm/Support/GenericDomTreeConstruction.h index fa4a746d83b..5883ce9e1e5 100644 --- a/include/llvm/Support/GenericDomTreeConstruction.h +++ b/include/llvm/Support/GenericDomTreeConstruction.h @@ -914,7 +914,12 @@ struct SemiNCAInfo { if (!FromTN) return; const TreeNodePtr ToTN = DT.getNode(To); - assert(ToTN && "To already unreachable -- there is no edge to delete"); + if (!ToTN) { + DEBUG(dbgs() << "\tTo (" << BlockNamePrinter(To) + << ") already unreachable -- there is no edge to delete\n"); + return; + } + const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To); const TreeNodePtr NCD = DT.getNode(NCDBlock); diff --git a/lib/Transforms/Scalar/ADCE.cpp b/lib/Transforms/Scalar/ADCE.cpp index 9d45c3da38f..fb550a8e08a 100644 --- a/lib/Transforms/Scalar/ADCE.cpp +++ b/lib/Transforms/Scalar/ADCE.cpp @@ -27,6 +27,7 @@ #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" #include "llvm/IR/DebugInfoMetadata.h" +#include "llvm/IR/Dominators.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/Instructions.h" @@ -89,6 +90,10 @@ struct BlockInfoType { class AggressiveDeadCodeElimination { Function &F; + + // ADCE does not use DominatorTree per se, but it updates it to preserve the + // analysis. + DominatorTree &DT; PostDominatorTree &PDT; /// Mapping of blocks to associated information, an element in BlockInfoVec. @@ -157,9 +162,10 @@ class AggressiveDeadCodeElimination { void makeUnconditional(BasicBlock *BB, BasicBlock *Target); public: - AggressiveDeadCodeElimination(Function &F, PostDominatorTree &PDT) - : F(F), PDT(PDT) {} - bool performDeadCodeElimination(); + AggressiveDeadCodeElimination(Function &F, DominatorTree &DT, + PostDominatorTree &PDT) + : F(F), DT(DT), PDT(PDT) {} + bool performDeadCodeElimination(); }; } @@ -557,14 +563,31 @@ void AggressiveDeadCodeElimination::updateDeadRegions() { } assert((PreferredSucc && PreferredSucc->PostOrder > 0) && "Failed to find safe successor for dead branch"); + + // Collect removed successors to update the (Post)DominatorTrees. + SmallPtrSet<BasicBlock *, 4> RemovedSuccessors; bool First = true; for (auto *Succ : successors(BB)) { - if (!First || Succ != PreferredSucc->BB) + if (!First || Succ != PreferredSucc->BB) { Succ->removePredecessor(BB); - else + RemovedSuccessors.insert(Succ); + } else First = false; } makeUnconditional(BB, PreferredSucc->BB); + + // Inform the dominators about the deleted CFG edges. + for (auto *Succ : RemovedSuccessors) { + // It might have happened that the same successor appeared multiple times + // and the CFG edge wasn't really removed. + if (Succ != PreferredSucc->BB) { + DEBUG(dbgs() << "ADCE: Removing (Post)DomTree edge " << BB->getName() + << " -> " << Succ->getName() << "\n"); + DT.deleteEdge(BB, Succ); + PDT.deleteEdge(BB, Succ); + } + } + NumBranchesRemoved += 1; } } @@ -609,6 +632,9 @@ void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB, InstInfo[NewTerm].Live = true; if (const DILocation *DL = PredTerm->getDebugLoc()) NewTerm->setDebugLoc(DL); + + InstInfo.erase(PredTerm); + PredTerm->eraseFromParent(); } //===----------------------------------------------------------------------===// @@ -617,13 +643,16 @@ void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB, // //===----------------------------------------------------------------------===// PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) { + auto &DT = FAM.getResult<DominatorTreeAnalysis>(F); auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F); - if (!AggressiveDeadCodeElimination(F, PDT).performDeadCodeElimination()) + if (!AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination()) return PreservedAnalyses::all(); PreservedAnalyses PA; PA.preserveSet<CFGAnalyses>(); PA.preserve<GlobalsAA>(); + PA.preserve<DominatorTreeAnalysis>(); + PA.preserve<PostDominatorTreeAnalysis>(); return PA; } @@ -637,14 +666,23 @@ struct ADCELegacyPass : public FunctionPass { bool runOnFunction(Function &F) override { if (skipFunction(F)) return false; + + auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree(); - return AggressiveDeadCodeElimination(F, PDT).performDeadCodeElimination(); + return AggressiveDeadCodeElimination(F, DT, PDT) + .performDeadCodeElimination(); } void getAnalysisUsage(AnalysisUsage &AU) const override { + // We require DominatorTree here only to update and thus preserve it. + AU.addRequired<DominatorTreeWrapperPass>(); AU.addRequired<PostDominatorTreeWrapperPass>(); if (!RemoveControlFlowFlag) AU.setPreservesCFG(); + else { + AU.addPreserved<DominatorTreeWrapperPass>(); + AU.addPreserved<PostDominatorTreeWrapperPass>(); + } AU.addPreserved<GlobalsAAWrapperPass>(); } }; @@ -653,6 +691,7 @@ struct ADCELegacyPass : public FunctionPass { char ADCELegacyPass::ID = 0; INITIALIZE_PASS_BEGIN(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination", false, false) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass) INITIALIZE_PASS_END(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination", false, false) diff --git a/test/Transforms/ADCE/domtree-DoubleDeletion.ll b/test/Transforms/ADCE/domtree-DoubleDeletion.ll new file mode 100644 index 00000000000..018eb79b26f --- /dev/null +++ b/test/Transforms/ADCE/domtree-DoubleDeletion.ll @@ -0,0 +1,39 @@ +; RUN: opt < %s -gvn -simplifycfg -adce | llvm-dis +; RUN: opt < %s -gvn -simplifycfg -adce -verify-dom-info | llvm-dis + +; This test makes sure that the DominatorTree properly handles +; deletion of edges that go to forward-unreachable regions. +; In this case, %land.end is already forward unreachable when +; the DT gets informed about the deletion of %entry -> %land.end. + +@a = common global i32 0, align 4 + +define i32 @main() { +entry: + %retval = alloca i32, align 4 + store i32 0, i32* %retval, align 4 + %0 = load i32, i32* @a, align 4 + %cmp = icmp ne i32 %0, 1 + br i1 %cmp, label %land.rhs, label %land.end4 + +land.rhs: ; preds = %entry + %1 = load i32, i32* @a, align 4 + %tobool = icmp ne i32 %1, 0 + br i1 %tobool, label %land.rhs1, label %land.end + +land.rhs1: ; preds = %land.rhs + br label %land.end + +land.end: ; preds = %land.rhs1, %land.rhs + %2 = phi i1 [ false, %land.rhs ], [ true, %land.rhs1 ] + %land.ext = zext i1 %2 to i32 + %conv = trunc i32 %land.ext to i16 + %conv2 = sext i16 %conv to i32 + %tobool3 = icmp ne i32 %conv2, 0 + br label %land.end4 + +land.end4: ; preds = %land.end, %entry + %3 = phi i1 [ false, %entry ], [ %tobool3, %land.end ] + %land.ext5 = zext i1 %3 to i32 + ret i32 0 +} diff --git a/test/Transforms/ADCE/unreachable.ll b/test/Transforms/ADCE/unreachable.ll new file mode 100644 index 00000000000..aaacc184225 --- /dev/null +++ b/test/Transforms/ADCE/unreachable.ll @@ -0,0 +1,18 @@ +; RUN: opt < %s -adce -simplifycfg | llvm-dis +; RUN: opt < %s -passes=adce | llvm-dis + +define i32 @Test(i32 %A, i32 %B) { +BB1: + br label %BB4 + +BB2: ; No predecessors! + br label %BB3 + +BB3: ; preds = %BB4, %BB2 + %ret = phi i32 [ %X, %BB4 ], [ %B, %BB2 ] ; <i32> [#uses=1] + ret i32 %ret + +BB4: ; preds = %BB1 + %X = phi i32 [ %A, %BB1 ] ; <i32> [#uses=1] + br label %BB3 +} |