From 5288e9123b1632b0eb21745beb1e6399d0998622 Mon Sep 17 00:00:00 2001 From: Jakub Kuderski Date: Tue, 22 Aug 2017 16:30:21 +0000 Subject: [PATCH] [ADCE][Dominators] Reapply: Teach ADCE to preserve dominators Summary: This patch teaches ADCE to preserve both DominatorTrees and PostDominatorTrees. This is reapplies the original patch r311057 that was reverted in r311381. The previous version wasn't using the batch update api for updating dominators, which in vary rare cases caused assertion failures. This also fixes PR34258. 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@311467 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/ADCE.cpp | 56 +++++++++++++++++++--- .../ADCE/2017-08-21-DomTree-deletions.ll | 24 ++++++++++ test/Transforms/ADCE/domtree-DoubleDeletion.ll | 39 +++++++++++++++ test/Transforms/ADCE/unreachable.ll | 18 +++++++ 4 files changed, 130 insertions(+), 7 deletions(-) create mode 100644 test/Transforms/ADCE/2017-08-21-DomTree-deletions.ll create mode 100644 test/Transforms/ADCE/domtree-DoubleDeletion.ll create mode 100644 test/Transforms/ADCE/unreachable.ll diff --git a/lib/Transforms/Scalar/ADCE.cpp b/lib/Transforms/Scalar/ADCE.cpp index 9d45c3da38f..c47e904692d 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,34 @@ 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 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. + SmallVector DeletedEdges; + 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: (Post)DomTree edge enqueued for deletion" + << BB->getName() << " -> " << Succ->getName() << "\n"); + DeletedEdges.push_back({DominatorTree::Delete, BB, Succ}); + } + } + + DT.applyUpdates(DeletedEdges); + PDT.applyUpdates(DeletedEdges); + NumBranchesRemoved += 1; } } @@ -609,6 +635,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 +646,16 @@ void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB, // //===----------------------------------------------------------------------===// PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) { + auto &DT = FAM.getResult(F); auto &PDT = FAM.getResult(F); - if (!AggressiveDeadCodeElimination(F, PDT).performDeadCodeElimination()) + if (!AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination()) return PreservedAnalyses::all(); PreservedAnalyses PA; PA.preserveSet(); PA.preserve(); + PA.preserve(); + PA.preserve(); return PA; } @@ -637,14 +669,23 @@ struct ADCELegacyPass : public FunctionPass { bool runOnFunction(Function &F) override { if (skipFunction(F)) return false; + + auto &DT = getAnalysis().getDomTree(); auto &PDT = getAnalysis().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(); AU.addRequired(); if (!RemoveControlFlowFlag) AU.setPreservesCFG(); + else { + AU.addPreserved(); + AU.addPreserved(); + } AU.addPreserved(); } }; @@ -653,6 +694,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/2017-08-21-DomTree-deletions.ll b/test/Transforms/ADCE/2017-08-21-DomTree-deletions.ll new file mode 100644 index 00000000000..e532f29e9f4 --- /dev/null +++ b/test/Transforms/ADCE/2017-08-21-DomTree-deletions.ll @@ -0,0 +1,24 @@ +; RUN: opt < %s -adce | llvm-dis +; RUN: opt < %s -adce -verify-dom-info | llvm-dis + +define void @foo() { +entry: + br label %switch +switch: ; preds = %entry + switch i32 undef, label %default [ + i32 2, label %two + i32 5, label %five + i32 4, label %four + ] +four: ; preds = %switch + br label %exit +five: ; preds = %switch + br label %exit +two: ; preds = %switch + br label %exit +default: ; preds = %switch + br label %exit +exit: ; preds = %default, %two, %five, %four + ret void +} + 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 ] ; [#uses=1] + ret i32 %ret + +BB4: ; preds = %BB1 + %X = phi i32 [ %A, %BB1 ] ; [#uses=1] + br label %BB3 +} -- 2.11.0