Index: include/llvm/Analysis/IteratedDominanceFrontier.h =================================================================== --- include/llvm/Analysis/IteratedDominanceFrontier.h +++ include/llvm/Analysis/IteratedDominanceFrontier.h @@ -78,8 +78,10 @@ /// This uses the linear-time phi algorithm based on DJ-graphs mentioned in /// the file-level comment. It performs DF->IDF pruning using the live-in /// set, to avoid computing the IDF for blocks where an inserted PHI node - /// would be dead. - void calculate(SmallVectorImpl &IDFBlocks); + /// would be dead. When ReverseGraph is set, DT is assumed to be a + /// post-dominator tree and the reverse graph is used + void calculate(SmallVectorImpl &IDFBlocks, + bool ReverseGraph = false); private: DominatorTreeBase &DT; Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -63,6 +63,7 @@ void initializeTarget(PassRegistry&); void initializeAAEvalLegacyPassPass(PassRegistry&); +void initializeACDCELegacyPassPass(PassRegistry&); void initializeAddDiscriminatorsPass(PassRegistry&); void initializeADCELegacyPassPass(PassRegistry&); void initializeBDCEPass(PassRegistry&); Index: include/llvm/LinkAllPasses.h =================================================================== --- include/llvm/LinkAllPasses.h +++ include/llvm/LinkAllPasses.h @@ -60,6 +60,7 @@ return; (void) llvm::createAAEvalPass(); + (void) llvm::createAggressiveControlDCEPass(); (void) llvm::createAggressiveDCEPass(); (void) llvm::createBitTrackingDCEPass(); (void) llvm::createArgumentPromotionPass(); Index: include/llvm/Transforms/Scalar.h =================================================================== --- include/llvm/Transforms/Scalar.h +++ include/llvm/Transforms/Scalar.h @@ -84,6 +84,15 @@ //===----------------------------------------------------------------------===// // +// AggressiveControlDCE - This pass uses the SSA based Aggressive DCE algorithm. This +// algorithm assumes instructions are dead until proven otherwise, which makes +// it more successful at removing non-obviously dead instructions. This +// variant does not treat branches as automatically live +// +FunctionPass *createAggressiveControlDCEPass(); + +//===----------------------------------------------------------------------===// +// // BitTrackingDCE - This pass uses a bit-tracking DCE algorithm in order to // remove computations of dead bits. // Index: include/llvm/Transforms/Scalar/ACDCE.h =================================================================== --- /dev/null +++ include/llvm/Transforms/Scalar/ACDCE.h @@ -0,0 +1,40 @@ +//===- ACDCE.h - Aggressive dead code elimination +//--------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides the interface for the Aggressive Control Dead Code Elimination +// pass. This pass optimistically assumes that all instructions are dead until +// proven otherwise, allowing it to eliminate dead computations that other DCE +// passes do not catch, particularly involving loop computations. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_ACDCE_H +#define LLVM_TRANSFORMS_SCALAR_ACDCE_H + +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// A DCE pass that assumes instructions including branches are dead until +/// proven otherwise. +/// +/// This pass eliminates dead code by optimistically assuming that all +/// instructions are dead until proven otherwise. This allows it to eliminate +/// dead computations that other DCE passes do not catch, particularly involving +/// loop computations. This pass augments the predecessor "Aggressive DCE" by +/// not treating all branch operations as automatically live and by altering the +/// control flow graph remove dead branching. +struct ACDCEPass : PassInfoMixin { + PreservedAnalyses run(Function &F, AnalysisManager &AM); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_ACDCE_H Index: lib/Analysis/IteratedDominanceFrontier.cpp =================================================================== --- lib/Analysis/IteratedDominanceFrontier.cpp +++ lib/Analysis/IteratedDominanceFrontier.cpp @@ -18,7 +18,8 @@ using namespace llvm; -void IDFCalculator::calculate(SmallVectorImpl &PHIBlocks) { +void IDFCalculator::calculate(SmallVectorImpl &PHIBlocks, + bool ReverseGraph) { // If we haven't computed dominator tree levels, do so now. if (DomLevels.empty()) { for (auto DFI = df_begin(DT.getRootNode()), DFE = df_end(DT.getRootNode()); @@ -61,8 +62,19 @@ while (!Worklist.empty()) { DomTreeNode *Node = Worklist.pop_back_val(); BasicBlock *BB = Node->getBlock(); + SmallVector Successors; + if (!ReverseGraph) { + for (auto Succ : successors(BB)) { + Successors.push_back(Succ); + } + } + else { + for (auto Pred : predecessors(BB)) { + Successors.push_back(Pred); + } + } - for (auto Succ : successors(BB)) { + for (auto Succ : Successors) { DomTreeNode *SuccNode = DT.getNode(Succ); // Quickly skip all CFG edges that are also dominator tree edges instead Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -49,6 +49,7 @@ #include "llvm/Transforms/IPO/InferFunctionAttrs.h" #include "llvm/Transforms/IPO/StripDeadPrototypes.h" #include "llvm/Transforms/InstCombine/InstCombine.h" +#include "llvm/Transforms/Scalar/ACDCE.h" #include "llvm/Transforms/Scalar/ADCE.h" #include "llvm/Transforms/Scalar/EarlyCSE.h" #include "llvm/Transforms/Scalar/LowerExpectIntrinsic.h" Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ lib/Passes/PassRegistry.def @@ -92,6 +92,7 @@ #ifndef FUNCTION_PASS #define FUNCTION_PASS(NAME, CREATE_PASS) #endif +FUNCTION_PASS("acdce", ACDCEPass()) FUNCTION_PASS("aa-eval", AAEvaluator()) FUNCTION_PASS("adce", ADCEPass()) FUNCTION_PASS("early-cse", EarlyCSEPass()) Index: lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- lib/Transforms/IPO/PassManagerBuilder.cpp +++ lib/Transforms/IPO/PassManagerBuilder.cpp @@ -318,7 +318,12 @@ if (LoadCombine) MPM.add(createLoadCombinePass()); - MPM.add(createAggressiveDCEPass()); // Delete dead instructions + if (OptLevel > 2) { + MPM.add(createAggressiveControlDCEPass()); // Delete dead instructions + } + else { + MPM.add(createAggressiveDCEPass()); // Delete dead instructions + } MPM.add(createCFGSimplificationPass()); // Merge & remove BBs // Clean up after everything. addInstructionCombiningPass(MPM); Index: lib/Transforms/Scalar/ACDCE.cpp =================================================================== --- /dev/null +++ lib/Transforms/Scalar/ACDCE.cpp @@ -0,0 +1,1022 @@ +//===- ACDCE.cpp - Code to perform dead code elimination +//-------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the Aggressive Dead Code Elimination pass. This pass +// optimistically assumes that all instructions are dead until proven otherwise, +// allowing it to eliminate dead computations that other DCE passes do not +// catch, particularly involving loop computations. +// +// https://groups.google.com/forum/#!topic/llvm-dev/j2vlIECKkdE -- dead loops +// discussion +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Scalar/ACDCE.h" + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/CFGPrinter.h" +#include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/IteratedDominanceFrontier.h" +#include "llvm/Analysis/PostDominators.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/Pass.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/FileSystem.h" +#include "llvm/Transforms/Scalar.h" + +using namespace llvm; + +#define DEBUG_TYPE "acdce" +#define DEBUG_MSG(x) DEBUG(dbgs() << x << '\n';) + +static cl::opt RemoveLoops("acdce-remove-loops", cl::init(false), + cl::Hidden); + +STATISTIC(NumRemoved, "Number of non-branch instructions removed"); +STATISTIC(NumBranchesRemoved, "Number of branch instructions removed"); + +namespace { + +// helper functions ... +static bool isUnconditional(TerminatorInst *term) { + auto br = dyn_cast(term); + return br && br->isUnconditional(); +} + +// simplified erase pattern +template void erase(V *vec, Pred p) { + vec->erase(std::remove_if(vec->begin(), vec->end(), p), vec->end()); +} +// a composite transform and copy-if which test for non-null +template +OutputIterator copy_non_null(InputIterator first1, InputIterator last1, + OutputIterator result, UnaryOperator op) { + while (first1 != last1) { + auto value = op(*first1); + if (value) { + *result = value; + ++result; + } + ++first1; + } + return result; +} +} + +namespace llvm { + +// Specialize po_iterator_storage to identify loop bottoms +// which we define simply as back edges in a depth first +// traversal of the CFG starting at the entry. +class PO_WithLoops; + +template <> class po_iterator_storage { + PO_WithLoops &Storage; + +public: + po_iterator_storage(PO_WithLoops &Storage) : Storage(Storage) {} + // These functions are defined below. + bool insertEdge(BasicBlock *From, BasicBlock *To); + void finishPostorder(BasicBlock *BB); +}; + +class PO_WithLoops { + typedef SmallPtrSet LoopBottomsType; + typedef po_iterator POTIterator; + + Function &F; + // Visited[BB] is true while the basic block *BB is on + // the stack of being visited nodes and false after + // all children have been visited + DenseMap Visited; + LoopBottomsType LoopBottoms; + +public: + PO_WithLoops(Function &F) : F(F) { Visited.grow(2 * F.size()); } + POTIterator begin() { return po_ext_begin(&F.getEntryBlock(), *this); } + POTIterator end() { return po_ext_end(&F.getEntryBlock(), *this); } + bool insertEdge(BasicBlock *From, BasicBlock *To) { + auto P = Visited.insert(std::make_pair(To, true)); + if (P.second) { + return true; + } + if (P.first->second) { + // back edge to an ancestor in DFS + LoopBottoms.insert(From); + } + return false; + } + + void finishPostorder(BasicBlock *BB) { Visited[BB] = false; } + bool reachable(BasicBlock *BB) const { + return (Visited.find(BB) != Visited.end()); + } + const LoopBottomsType &getLoopBottoms() { return LoopBottoms; } +}; + +bool po_iterator_storage::insertEdge(BasicBlock *From, + BasicBlock *To) { + return Storage.insertEdge(From, To); +} +void po_iterator_storage::finishPostorder(BasicBlock *BB) { + Storage.finishPostorder(BB); +} +} + +namespace { + +struct BlockInfoType; +/// A Dead Region is a set of dead basic blocks with a common +/// post-dominating live block +struct DeadRegionInfo { + /// true when all blocks have unconditional branches + bool Trivial = true; // dead blocks are just unconditional branches + /// the set of dead blocks in this region + SmallVector DeadBlocks; + /// sources of edges from live nodes into dead ones of this region + SmallPtrSet LivePreds; +}; + +/// Information about basic blocks relevant to dead code elimination +struct BlockInfoType { + /// true when this block contains a live instructions + bool Live = false; + /// this block ends in an unconditional branch + bool UnconditionalBranch = false; + /// quick access to the Live flag for the terminator + bool *TerminatorLive = nullptr; // == & InstInfo[Terminator].Live + + bool terminatorIsLive() const { return *TerminatorLive; } + + /// corresponding BasicBlock + BasicBlock *BB = nullptr; + + /// points to this BB when this block is live, otherwise the most immediate + /// live post-dominator of BB + BasicBlock *LivePostDom = nullptr; + + TerminatorInst *Terminator = nullptr; ///< cache of BB->getTerminator() + + /// block found to not reach a function return point + bool isUnreachable() const { return Terminator == nullptr; } + + /// the collection of dead blocks which have this block as + /// the most-immediate live post-dominator + DeadRegionInfo DeadRegion; + + /// used to control exploration of dead connected components + unsigned RegionVisited = 0; +}; + +/// Information about Instruction's +struct InstInfoType { + + bool Live = false; ///< true if this unstruction is live + + /// quick access to information for block containing associated Instruction + BlockInfoType *Block = nullptr; +}; + +/// This class implements analysis to determine instructions including branching +/// which does not effect the output. Such operations are removed as are +/// unreachable operations for some scenarions. Dead loops are optionally +/// removed +/// or retained. +class AggressiveCDCE { + Function &F; + + /// reverse partial order of blocks with a collection of sources of backward + /// edges referred to as loop bottoms + PO_WithLoops PO; + PostDominatorTree &PDT; + bool GraphWasModified = false; + + /// function-level statistics + unsigned FuncNumBranchesRemoved = 0; + unsigned FuncNumInstRemoved = 0; + + /// one per basic block in the function + std::vector BlockInfoVec; + + /// mapping of blocks to associated information, element in BlockInfoVec + DenseMap BlockInfo; + bool isLive(BasicBlock *BB) { return BlockInfo[BB]->Live; } + + /// mapping of instructions to associated information + DenseMap InstInfo; + bool isLive(Instruction *I) { return InstInfo[I].Live; } + + /// initialize maps and BlockInfoVec + void initialize(); + + /// live instructions to be processed or dead instructions to be deleted + SmallVector Worklist; + + /// Propagate "live-ness" to definitions which reach "live" instructions + void markLive(); + /// Mark I and its containing block as live. + void markLive(Instruction *I); + + /// true for any instructions which is always treated as live + bool alwaysLive(Instruction &I) const; + + /// vector of blocks with not known to be live terminators, + SmallPtrSet BlocksWithDeadTerminators; + + /// The set of blocks which we have determined are live in the + /// most recent pass + SmallPtrSet NewLiveBlocks; + + /// Analyze basic blocks to find to loop bottoms to keep live and + /// remove unreachable blocks + void analyzeBlocks(); + + /// blocks found to be unreachable when searching for back edges + SmallVector UnreachableBlocks; + void removeUnreachable(BasicBlock *); + + /// Analyze dead branches to find those whose branches are the sources + /// of control dependences impacting a live block. Those branches are + /// marked live. + void checkControlDependences(); + + /// look for phi nodes with complex value which force + /// source blocks of reaching values to be treated as live. + void checkPhiNodes(); + + typedef SmallPtrSet RegionSetType; + + /// Traverse the connected component associated with BBInfo where + /// nodes whose RegionVisited field is greater than FirstVisit are considered + /// already 'visited' and we stop at tops of live blocks. + /// Set RegionVisited for blocks newly visited to CurrentVisit. + /// Record live blocks that are successors of DeadBlocks on this + /// componente in LivePdoms + void visitRegion(BlockInfoType *, unsigned FirstVisit, unsigned CurrentVisit, + RegionSetType *LivePdoms); + + /// Incremented for each new traversal of connected components + unsigned LastCurrentVisit = 0; + + /// Verify that all edges from "dead" predecessors into PN + /// have the same associated value. To refine the precision, the + /// dead blocks are partitioned into connnected components and + /// all definitions associated with predecessor blocks in the same + /// connected component must be the same + void checkPhiNode(PHINode *PN, unsigned FirstVisit); + + /// find groups of dead blocks with common live post-dominator + /// and rewrite the control flow graph + void processDeadRegions(); + + /// Rewrite non-trivial dead regions by redirection incoming live + /// control flow to the post-dominator and updating phi-nnodes in the + /// post-dominator + void updateDeadRegion(BasicBlock *BB, DeadRegionInfo *Info); + + /// adjust BB so it has an unconditional branch to Target + /// mark that branch live. + void makeUnconditional(BasicBlock *BB, BasicBlock *Target); + + /// the collection of unconditional branch instructions created + /// by makeUnconditional + SmallVector NewBranches; + + /// for trivial regions, we just mark all the branches as live to be + /// cleaned up by other phases + void cleanTrivialRegion(const DeadRegionInfo &Info); + + void removeDeadCode(); + +#ifndef NDEBUG + /// the set of live blocks with dead predecessors + SmallPtrSet BlocksForPhiValidation; + + /// verify one value for each predecessor after dead blocks are removed + void validatePhiNodes(BasicBlock *); +#endif + +public: + AggressiveCDCE(Function &F, PostDominatorTree &PDT) + : F(F), PO(F), PDT(PDT) {} + bool doAggressiveCDCE(); +}; +} + +bool AggressiveCDCE::doAggressiveCDCE() { + + initialize(); + markLive(); + processDeadRegions(); + removeDeadCode(); + + return GraphWasModified; +} + +//===----------------------------------------------------------------------===// +// +// +// Initialize of data structures and identification of +// loops and unreachable code +// +//===----------------------------------------------------------------------===// +void AggressiveCDCE::initialize() { + + DEBUG(PDT.print(dbgs())); + + auto NumBlocks = F.size(); + BlockInfoVec.resize(NumBlocks); + BlockInfo.grow(2 * NumBlocks); + auto InfoP = BlockInfoVec.begin(); + size_t NumInsts = 0; + for (auto &BB : F) { + NumInsts += BB.size(); + auto &Info = *InfoP; + BlockInfo[&BB] = &Info; + DEBUG_MSG("initializing block " << BB.getName()); + Info.BB = &BB; + Info.Terminator = BB.getTerminator(); + Info.UnconditionalBranch = isUnconditional(Info.Terminator); + ++InfoP; + } + if (!RemoveLoops) { + // remove unreachable code, identify loop bottoms + // to be forced live below. + analyzeBlocks(); + } + InstInfo.grow(2 * NumInsts); + for (auto &BBInfo : BlockInfoVec) { + if (BBInfo.isUnreachable()) { // removed unreachable node + continue; + } + for (Instruction &I : *BBInfo.BB) { + auto &IInfo = InstInfo[&I]; + IInfo.Block = &BBInfo; + if (alwaysLive(I)) { + markLive(&I); + } + } + } + + // For blocks which do not reach a function return, mark + // them live. Also branches where some reach the return + // and some done as live. + for (auto &BBInfo : BlockInfoVec) { + if (!BBInfo.isUnreachable() && !PDT.getNode(BBInfo.BB)) { + markLive(BBInfo.Terminator); + for (auto Pred : predecessors(BBInfo.BB)) { + DEBUG_MSG("no pdom pred live: " << Pred->getName()); + markLive(Pred->getTerminator()); + } + } + } + + // mark all loop bottom terminators as live so loops are not + // deleted (in case they are infinite) + for (auto BB : PO.getLoopBottoms()) { + DEBUG_MSG("loop bottom " << BB->getName()); + markLive(BB->getTerminator()); + } + + for (auto &BBInfo : BlockInfoVec) { + BBInfo.TerminatorLive = &InstInfo[BBInfo.Terminator].Live; + if (! *BBInfo.TerminatorLive) { + BlocksWithDeadTerminators.insert(BBInfo.BB); + } + } + + // Treat the entry block as always live + auto BB = &F.getEntryBlock(); + auto &EntryInfo = *BlockInfo[BB]; + EntryInfo.Live = true; + EntryInfo.LivePostDom = BB; + if (EntryInfo.UnconditionalBranch) { + *EntryInfo.TerminatorLive = true; + BlocksWithDeadTerminators.erase(BB); + } +} + +// Find and remove unreachable code and compute the bottoms of loops +// which will be forced live so loops are retained. +void AggressiveCDCE::analyzeBlocks() { + + // This loop drives a Post Order traversal of the + // control flow graph which will determine the set + // of blocks reachable from the entry and also mark + // those which are the sources of back edges (loop bottoms) + for (auto BB : PO) { + (void) BB; + } + + for (auto &BB : F) { + if (PO.reachable(&BB)) { + continue; + } + DEBUG_MSG("unreachable " << BB.getName()); + removeUnreachable(&BB); + UnreachableBlocks.push_back(&BB); + } + if (Worklist.empty()) { + return; + } + GraphWasModified = true; + for (auto I : Worklist) { + I->eraseFromParent(); + } + Worklist.clear(); +} + +// since we go to the trouble of finding unreachable blocks +// might as well remove them. +void AggressiveCDCE::removeUnreachable(BasicBlock *BB) { + auto &Info = *BlockInfo[BB]; + Info.Live = true; + Info.Terminator = nullptr; + + while (PHINode *PN = dyn_cast(BB->begin())) { + PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); + BB->getInstList().pop_front(); + } + for (auto Succ : successors(BB)) { + Succ->removePredecessor(BB); + } + BB->dropAllReferences(); + for (Instruction &I : *BB) { + Worklist.push_back(&I); + } +} + +//===----------------------------------------------------------------------===// +// +// Core algorithm to propagate liveness +// +//===----------------------------------------------------------------------===// +void AggressiveCDCE::markLive() { + + DEBUG_MSG("propagate live\n"); + + // Propagate liveness backwards to operands. + do { + while (!Worklist.empty()) { + Instruction *Curr = Worklist.pop_back_val(); + DEBUG(dbgs() << "work live: "; Curr->dump();); + for (Use &OI : Curr->operands()) { + if (Instruction *Inst = dyn_cast(OI)) { + markLive(Inst); + } + } + } + checkControlDependences(); + if (Worklist.empty()) { + checkPhiNodes(); + } + } while (!Worklist.empty()); + + // Find blocks with dead terminators which are simply + // unconditional branches and mark them live to avoid + // trivial edits + SmallVector NowLiveBlocks; + for (auto BB : BlocksWithDeadTerminators) { + auto Info = BlockInfo[BB]; + if (!Info->Live && Info->UnconditionalBranch && + &Info->BB->front() == Info->Terminator) { + if (auto Pred = Info->BB->getSinglePredecessor()) { + if (isLive(Pred->getTerminator())) { + // this mostly avoids unnecessary work removing trival dead regions + DEBUG_MSG("unconditional from live pred " << Info->BB->getName()); + Info->Live = true; + *Info->TerminatorLive = true; + Info->LivePostDom = BB; + NowLiveBlocks.push_back(BB); + } + } + } + } + for (auto BB : NowLiveBlocks) { + BlocksWithDeadTerminators.erase(BB); + } +} + +bool AggressiveCDCE::alwaysLive(Instruction &I) const { + if (isa(I) || I.isEHPad() || I.mayHaveSideEffects()) { + return true; + } + if (!isa(I)) { + return false; + } + if (isa(I) || isa(I)) { + return false; + } + return true; +} + +void AggressiveCDCE::markLive(Instruction *I) { + auto &Info = InstInfo[I]; + if (Info.Live) { + return; + } + DEBUG(dbgs() << "mark live: "; I->dump()); + Info.Live = true; + Worklist.push_back(I); + auto &BBInfo = *Info.Block; + if (BBInfo.Live) { + return; + } + DEBUG_MSG("mark block live: " << BBInfo.BB->getName()); + BBInfo.Live = true; + NewLiveBlocks.insert(BBInfo.BB); + + // See comments below... + BBInfo.LivePostDom = BBInfo.BB; + if (!BBInfo.UnconditionalBranch) { + return; + } + BlocksWithDeadTerminators.erase(BBInfo.BB); + + if (!BBInfo.TerminatorLive) { // not set in first initialization pass + InstInfo[BBInfo.Terminator].Live = true; + } else { + *BBInfo.TerminatorLive = true; + } +} + +// Use the IDFCalculator to find control dependences +// strting at newly discovered live blocks but stopping +// at blocks with live terminators. +void AggressiveCDCE::checkControlDependences() { + + if (BlocksWithDeadTerminators.empty()) { + return ; + } + + DEBUG({ + dbgs() << "new live blocks:\n"; + for (auto BB : NewLiveBlocks) { + dbgs() << "\t" << BB->getName() << '\n'; + } + dbgs() << "dead terminator blocks:\n"; + for (auto BB : BlocksWithDeadTerminators) { + dbgs() << "\t" << BB->getName() << '\n'; + } + }); + + SmallVector IDFBlocks; + IDFCalculator IDFs(PDT); + IDFs.setDefiningBlocks(NewLiveBlocks); + IDFs.setLiveInBlocks(BlocksWithDeadTerminators); + IDFs.calculate(IDFBlocks, /*reverse graph*/true); + NewLiveBlocks.clear(); + + /* dead terminators which control live blocks become live */ + for (auto BB : IDFBlocks) { + DEBUG_MSG("live control in: " << BB->getName()); + markLive(BB->getTerminator()); + BlocksWithDeadTerminators.erase(BB); + } +} + +// there are scenarios in which a phi node is really short-hand +// for a copy operations on the edge and the semantics of the program +// rely on this. We look for situations where there are distinct values from +// blocks with dead terminators (which we assume +// are all replaced with +// a single edge) and if we find this case we mark some of those terminators +// as live. +void AggressiveCDCE::checkPhiNodes() { + RegionSetType LivePdoms; + auto FirstVisit = LastCurrentVisit; + for (auto DB : BlocksWithDeadTerminators) { + auto DBInfo = BlockInfo[DB]; + if (DBInfo->RegionVisited > FirstVisit || DBInfo->terminatorIsLive()) { + continue; + } + ++LastCurrentVisit; + visitRegion(DBInfo, FirstVisit, LastCurrentVisit, &LivePdoms); + } + for (auto Succ : LivePdoms) { + DEBUG_MSG("checking Phi Nodes " << Succ->getName()); + for (auto it = Succ->begin(); PHINode *PN = dyn_cast(it); ++it) { + if (isLive(PN)) { + checkPhiNode(PN, FirstVisit); + } + } + } +} + +// Traverse the connected component associated with BBInfo where +// nodes whose RegionVisited field is > FirstVisit are considered 'visited' +// and we stop at tops of live blocks. +void AggressiveCDCE::visitRegion(BlockInfoType *BBInfo, unsigned FirstVisit, + unsigned CurrentVisit, + RegionSetType *LivePdoms) { + BBInfo->RegionVisited = CurrentVisit; + DEBUG_MSG("region visited " << CurrentVisit << " " << BBInfo->BB->getName()); + if (!BBInfo->Live) { + for (auto Pred : predecessors(BBInfo->BB)) { + auto PredInfo = BlockInfo[Pred]; + if (PredInfo->RegionVisited <= FirstVisit) { + visitRegion(PredInfo, FirstVisit, CurrentVisit, LivePdoms); + } + } + } + for (auto Succ : successors(BBInfo->BB)) { + auto SuccInfo = BlockInfo[Succ]; + if (SuccInfo->Live) { + LivePdoms->insert(SuccInfo->BB); + continue; + } + if (SuccInfo->RegionVisited <= FirstVisit) { + visitRegion(SuccInfo, FirstVisit, CurrentVisit, LivePdoms); + } + } +} + +// This code verifies that all edges from "dead" predecessors +// have the same associated value. This might not be true +// after certain optimizations of eliminated intermediate PHI +// nodes +void AggressiveCDCE::checkPhiNode(PHINode *PN, unsigned FirstVisit) { + DenseMap DeadValues; + + auto NumIdx = PN->getNumIncomingValues(); + // A block P may be a direct predecessor of a block Q and have a live + // terminator. It may also have a path from dead blocks leading to When that + // path is removed, there will only be one edge from P to Q and so we can + // only have one value in that case. + for (unsigned Idx = 0; Idx < NumIdx; ++Idx) { + auto PredBB = PN->getIncomingBlock(Idx); + auto &Info = *BlockInfo[PredBB]; + if (Info.RegionVisited > FirstVisit && Info.Live && + Info.terminatorIsLive()) { + DeadValues[Info.RegionVisited] = PN->getIncomingValue(Idx); + DEBUG_MSG("live for region " << Info.RegionVisited << " from " + << PredBB->getName()); + } + } + for (unsigned Idx = 0; Idx < NumIdx; ++Idx) { + auto PredBB = PN->getIncomingBlock(Idx); + auto PredInfo = BlockInfo[PredBB]; + if (PredInfo->terminatorIsLive()) { + continue; + } + DEBUG_MSG("check pred " << PredInfo->RegionVisited << " " + << PredBB->getName()); + auto Value = PN->getIncomingValue(Idx); + auto &DeadValue = DeadValues[PredInfo->RegionVisited]; + if (DeadValue) { + if (Value != DeadValue) { + DEBUG(dbgs() << "hard phi, region = " << PredInfo->RegionVisited + << " pred " << PredBB->getName() << '\n'; + PN->dump()); + markLive(PredInfo->Terminator); + } + } else { + DeadValue = Value; + } + } +} + +//===----------------------------------------------------------------------===// +// +// Routines to update the CFG and SSA information before removing dead code +// +//===----------------------------------------------------------------------===// +// A dead region is the set of dead blocks with a common live post-dominator +// A trivial region is a region which consists of blocks with unconditional +// branches. We don't bother removing such blocks and defer to other phases +void AggressiveCDCE::processDeadRegions() { + + + // Set LivePostDom fields for blocks which dead terminators + SmallVector *, 16> deadPdoms; + for (auto & Info : BlockInfoVec) { + if( Info.isUnreachable()) { + continue; + } + if(Info.LivePostDom == nullptr) { + assert(!Info.Live); + auto Node = PDT.getNode(Info.BB)->getIDom(); + while(!isLive(Node->getBlock())) { + deadPdoms.push_back(Node); + Node = Node->getIDom(); + } + Info.LivePostDom = Node->getBlock(); + for (auto DeadNode : deadPdoms) { + BlockInfo[DeadNode->getBlock()]->LivePostDom = Info.LivePostDom; + } + deadPdoms.clear(); + } + if (Info.LivePostDom != Info.BB) { + DEBUG_MSG("live pdom " << Info.BB->getName() << " " + << Info.LivePostDom->getName()); + } + } + SmallPtrSet DeadRegions; + + // Examine dead blocks and collect them at their + // live post-dominator to be processed as a region. + for (auto DB : BlocksWithDeadTerminators) { + auto Info = BlockInfo[DB]; + assert(! *Info->TerminatorLive); + if (Info->Live) { + // Look for live blocks with dead branches which + // will need to be converted to unconditional branches + for (auto Succ : successors(Info->BB)) { + auto &SuccInfo = *BlockInfo[Succ]; + if (!SuccInfo.Live) { + continue; + } + DEBUG_MSG("dead br in pred " << Info->BB->getName() << " reaches " + << Succ->getName()); + SuccInfo.DeadRegion.LivePreds.insert(Info); + SuccInfo.DeadRegion.Trivial = false; + DeadRegions.insert(&SuccInfo); + } + continue; + } + auto LivePdom = Info->LivePostDom; + DEBUG_MSG("Dead block: " << Info->BB->getName() << " pdom " + << LivePdom->getName()); + auto &LivePdomInfo = *BlockInfo[LivePdom]; + DeadRegions.insert(&LivePdomInfo); + auto &DeadRegion = LivePdomInfo.DeadRegion; + for (auto PredBB : predecessors(Info->BB)) { + auto &PredInfo = *BlockInfo[PredBB]; + if (PredInfo.Live) { + DeadRegion.LivePreds.insert(&PredInfo); + if (!PredInfo.terminatorIsLive()) { + DeadRegion.Trivial = false; + } + } + } + if (!Info->UnconditionalBranch) { + DeadRegion.Trivial = false; + } else if (DeadRegion.Trivial) { + DeadRegion.DeadBlocks.push_back(Info); + } + } + + for (auto Info : DeadRegions) { + if (!Info->DeadRegion.Trivial) { + updateDeadRegion(Info->BB, &Info->DeadRegion); + } else { + cleanTrivialRegion(Info->DeadRegion); + } + } +} + +void AggressiveCDCE::updateDeadRegion(BasicBlock *BB, DeadRegionInfo *Info) { + + DEBUG({ + dbgs() << "live edges (unique predecessors) into " << BB->getName() << "\n"; + for (auto PredInfo : Info->LivePreds) { + dbgs() << "\t" << PredInfo->BB->getName() << '\n'; + } + }); + + // update each phi based on the new incoming edges + for (auto it = BB->begin(); PHINode *PN = dyn_cast(it); ++it) { + if (!isLive(PN)) { + continue; + } + DEBUG(dbgs() << "old phi: "; PN->dump()); + // Note that we have verified in checkPhiNodes that all are + // the same from dead predecessors. + DenseMap DeadValues; + + for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) { + auto PredBB = PN->getIncomingBlock(i); + auto PredInfo = BlockInfo[PredBB]; + if (PredInfo->terminatorIsLive()) { + continue; + } + DEBUG_MSG(" removing " << PredInfo->RegionVisited << " " + << PredBB->getName()); + auto &DeadValue = DeadValues[PredInfo->RegionVisited]; + assert(!DeadValue || DeadValue == PN->getIncomingValue(i)); + DeadValue = PN->getIncomingValue(i); + PN->removeIncomingValue(i, /*DeletePHIIfEmpty*/ false); + } + for (auto PredInfo : Info->LivePreds) { + auto DeadValue = DeadValues[PredInfo->RegionVisited]; + assert(DeadValue && "Failed to find value for dead predecessor"); + PN->addIncoming(DeadValue, PredInfo->BB); + } + DEBUG(dbgs() << "new phi: "; PN->dump()); + } + + // update edges + for (auto PredInfo : Info->LivePreds) { + if (!PredInfo->terminatorIsLive()) { + makeUnconditional(PredInfo->BB, BB); + } else { + auto PredTerm = PredInfo->Terminator; + auto NumSucc = PredTerm->getNumSuccessors(); + for (unsigned Idx = 0; Idx != NumSucc; ++Idx) { + auto Succ = PredTerm->getSuccessor(Idx); + auto SuccInfo = BlockInfo[Succ]; + if (SuccInfo->LivePostDom == BB) { + PredTerm->setSuccessor(Idx, BB); + } + } + } + } +#ifndef NDEBUG + BlocksForPhiValidation.insert(BB); +#endif +} +void AggressiveCDCE::makeUnconditional(BasicBlock *BB, BasicBlock *Target) { + auto PredTerm = BB->getTerminator(); + if (isUnconditional(PredTerm)) { + InstInfo[PredTerm].Live = true; + return; + } + DEBUG_MSG("making unconditional " << BB->getName()); + IRBuilder<> Builder(PredTerm); + auto NewTerm = Builder.CreateBr(Target); + // don't update InstInfo to protect pointers into it... + NewBranches.push_back(NewTerm); +} + +// mark trivial blocks live and their unconditional-branch terminators as well. +void AggressiveCDCE::cleanTrivialRegion(const DeadRegionInfo &DRInfo) { + for (auto DBInfo : DRInfo.DeadBlocks) { + DEBUG_MSG("Trivial: " << DBInfo->BB->getName()); + DBInfo->Live = true; + *DBInfo->TerminatorLive = true; + } +} + +// the actual work of removing dead instructions and blocks +void AggressiveCDCE::removeDeadCode() { + + assert(Worklist.empty() && + "Expected empty work list when removing dead code"); + // 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 + // value of the function, and may therefore be deleted safely. + // NOTE: We reuse the Worklist vector here for memory efficiency. + unsigned LocalNumBranchesRemoved = std::count_if( + BlocksWithDeadTerminators.begin(), BlocksWithDeadTerminators.end(), + [this](BasicBlock *DB) { return !isLive(DB->getTerminator()); }); + + // this update invalidates BlockInfoType::TerminatorLive fields + for (Instruction *I : NewBranches) { + InstInfo[I].Live = true; + } + for (Instruction &I : instructions(F)) { + if (!isLive(&I)) { + DEBUG(dbgs() << "dead: "; I.dump()); + Worklist.push_back(&I); + I.dropAllReferences(); + } + } + for (auto UB : UnreachableBlocks) { + DEBUG_MSG("removing unreachble " << UB->getName()); + UB->eraseFromParent(); + } + if (Worklist.empty()) { + return; + } + GraphWasModified = true; + for (Instruction *I : Worklist) { + I->eraseFromParent(); + } + for (auto BB : BlocksWithDeadTerminators) { + auto DB = BlockInfo[BB]; + if (!DB->Live) { + DEBUG_MSG("deleting block " << DB->BB->getName()); + DB->BB->eraseFromParent(); + } + } + auto LocalNumRemoved = Worklist.size(); + DEBUG_MSG("Num removed " << LocalNumRemoved << "\n" + << "Num branches removed " + << LocalNumBranchesRemoved); + FuncNumInstRemoved += LocalNumRemoved; + FuncNumBranchesRemoved += LocalNumBranchesRemoved; + NumBranchesRemoved += FuncNumBranchesRemoved; + NumRemoved += FuncNumInstRemoved; +} + +//===----------------------------------------------------------------------===// +// +// Debugging and validation code +// +//===----------------------------------------------------------------------===// + +#ifndef NDEBUG +void AggressiveCDCE::validatePhiNodes(BasicBlock *BB) { + + if (BB->empty()) + return; + PHINode *APN = dyn_cast(&BB->front()); + if (!APN) + return; + + SmallVector, 16> Preds; + for (auto Pred : predecessors(BB)) { + Preds.emplace_back(Pred, nullptr); + } + auto error = [this, BB](PHINode *PN, BasicBlock *Pred, const char *Message) { + errs() << "Error in function: " << F.getName() << "\n\t" << Message << '\n'; + errs() << "\tblock " << BB->getName() << '\n'; + errs() << "\tpred " << Pred->getName() << "\n\t"; + PN->print(errs()); + errs() << '\n'; + }; + + for (auto it = BB->begin(); PHINode *PN = dyn_cast(it); ++it) { + if (!isLive(PN)) { + continue; + } + auto NumIdx = PN->getNumIncomingValues(); + for (unsigned Idx = 0; Idx < NumIdx; ++Idx) { + auto Value = PN->getIncomingValue(Idx); + auto Pred = PN->getIncomingBlock(Idx); + bool Found = false; + for (auto &P : Preds) { + if (P.first == Pred) { + if (!P.second) { + P.second = Value; + Found = true; + break; + } + if (P.second != Value) { + error(PN, Pred, "multiple distinct values"); + } + } + } + if (!Found) { + error(PN, Pred, "no predecessor for value"); + } + } + for (auto &P : Preds) { + if (!P.second) { + error(PN, P.first, "no value for predecessor"); + } + P.second = nullptr; // reset for next PHI + } + } +} +#endif + +//===----------------------------------------------------------------------===// +// +// Pass Manager integration code +// +//===----------------------------------------------------------------------===// +PreservedAnalyses ACDCEPass::run(Function &F, AnalysisManager &AM) { + auto &PDT = AM.getResult(F); + if (AggressiveCDCE(F, PDT).doAggressiveCDCE()) + return PreservedAnalyses::none(); + return PreservedAnalyses::all(); +} + +namespace { +struct ACDCELegacyPass : public FunctionPass { + static char ID; // Pass identification, replacement for typeid + ACDCELegacyPass() : FunctionPass(ID) { + initializeACDCELegacyPassPass(*PassRegistry::getPassRegistry()); + } + + bool runOnFunction(Function &F) override { + if (skipOptnoneFunction(F)) + return false; + auto &PDT = getAnalysis().getPostDomTree(); + return AggressiveCDCE(F, PDT).doAggressiveCDCE(); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + AU.addPreserved(); + } +}; +} + +char ACDCELegacyPass::ID = 0; +INITIALIZE_PASS_BEGIN(ACDCELegacyPass, "acdce", + "Aggressive Control Dead Code Elimination", false, false) +INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass) +INITIALIZE_PASS_END(ACDCELegacyPass, "acdce", + "Aggressive Control Dead Code Elimination", false, false) + +FunctionPass *llvm::createAggressiveControlDCEPass() { + return new ACDCELegacyPass(); +} Index: lib/Transforms/Scalar/CMakeLists.txt =================================================================== --- lib/Transforms/Scalar/CMakeLists.txt +++ lib/Transforms/Scalar/CMakeLists.txt @@ -1,4 +1,5 @@ add_llvm_library(LLVMScalarOpts + ACDCE.cpp ADCE.cpp AlignmentFromAssumptions.cpp BDCE.cpp Index: lib/Transforms/Scalar/Scalar.cpp =================================================================== --- lib/Transforms/Scalar/Scalar.cpp +++ lib/Transforms/Scalar/Scalar.cpp @@ -31,6 +31,7 @@ /// initializeScalarOptsPasses - Initialize all passes linked into the /// ScalarOpts library. void llvm::initializeScalarOpts(PassRegistry &Registry) { + initializeACDCELegacyPassPass(Registry); initializeADCELegacyPassPass(Registry); initializeBDCEPass(Registry); initializeAlignmentFromAssumptionsPass(Registry); @@ -96,6 +97,10 @@ initializeScalarOpts(*unwrap(R)); } +void LLVMAddAggressiveControlDCEPass(LLVMPassManagerRef PM) { + unwrap(PM)->add(createAggressiveControlDCEPass()); +} + void LLVMAddAggressiveDCEPass(LLVMPassManagerRef PM) { unwrap(PM)->add(createAggressiveDCEPass()); } Index: test/Transforms/ADCE/2002-01-31-UseStuckAround.ll =================================================================== --- test/Transforms/ADCE/2002-01-31-UseStuckAround.ll +++ test/Transforms/ADCE/2002-01-31-UseStuckAround.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -adce +; RUN: opt < %s -acdce define i32 @"main"(i32 %argc) { br label %2 Index: test/Transforms/ADCE/2002-05-22-PHITest.ll =================================================================== --- test/Transforms/ADCE/2002-05-22-PHITest.ll +++ test/Transforms/ADCE/2002-05-22-PHITest.ll @@ -1,6 +1,7 @@ ; It is illegal to remove BB1 because it will mess up the PHI node! ; ; RUN: opt < %s -adce -S | grep BB1 +; RUN: opt < %s -acdce -S | grep BB1 define i32 @test(i1 %C, i32 %A, i32 %B) { ;