Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -64,6 +64,7 @@ void initializeAAEvalLegacyPassPass(PassRegistry&); void initializeAddDiscriminatorsPass(PassRegistry&); +void initializeACDCELegacyPassPass(PassRegistry&); void initializeADCELegacyPassPass(PassRegistry&); void initializeBDCEPass(PassRegistry&); void initializeAliasSetPrinterPass(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); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_ACDCE_H 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 @@ -314,7 +314,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,1059 @@ +//===- 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/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 Disabled("acdce-off", cl::init(false), cl::Hidden); +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(); +} +#ifndef NDEBUG +StringRef getName(BasicBlock *BB) { return BB ? BB->getName() : "null block"; } +#endif +// 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() + + /// 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; + + 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 branches not known to be live, when we retain loops these + /// are in post-order otherwise we simply use the reverse order of the + /// blocks to approximate post-order + SmallVector DeadBranchesInPostOrder; + + /// true if DeadBranchesInPostOrder needs to be initialized + bool initializeDeadBranches = true; + + /// 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 *); + + /// When we don't retain all loops, initialize the vector of + /// dead branches or remove branches found to be live from the vector + void setDeadBranchesInPostOrder(); + + /// 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 *); + + void debugDumpDead(); ///< dump dead operations +#endif + +public: + AggressiveCDCE(Function &F) : F(F), PO(F) { } + 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() { + + 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) { + analyzeBlocks(); + } + InstInfo.grow(2 * NumInsts); + for (auto &BBInfo : BlockInfoVec) { + if (!BBInfo.Terminator) { + continue; + } + for (Instruction &I : *BBInfo.BB) { + auto &IInfo = InstInfo[&I]; + IInfo.Block = &BBInfo; + if (alwaysLive(I)) { + markLive(&I); + } + } + } + // 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; + } + // 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; + } +} + +void AggressiveCDCE::analyzeBlocks() { + + initializeDeadBranches = false; + DeadBranchesInPostOrder.reserve(F.size()); + + // Perform a post-order traversal and build + // a vector of the dead terminators (which are currently + // all branch instructions) + std::transform(PO.begin(), PO.end(), + std::back_inserter(DeadBranchesInPostOrder), + [this](BasicBlock *BB) { return BlockInfo[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()); + + DEBUG(debugDumpDead()); +} + +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; + + // See comments below... + BBInfo.LivePostDom = BBInfo.BB; + if (!BBInfo.UnconditionalBranch) { + return; + } + if (!BBInfo.TerminatorLive) { // not set in first initialization pass + InstInfo[BBInfo.Terminator].Live = true; + } else { + *BBInfo.TerminatorLive = true; + } +} + +// We handle control dependences as a simple stand-alone +// data flow problem to avoid computing +// the post-dominator relation and the cost of +// computing control dependences directly. +// +// Define LivePdom(BB) = BB, if BB has a live instruction +// Otherwise LivePdom is initialized to TOP +// Then define +// IN(BB) = merge({ LivePdom[S] | S is a successor of BB }) +// where Merge(TOP,S) = S, Merge(S,S) = S, Merge(S,T) = BOTTOM otherwise +// +// Where IN(BB) == BOTTOM, we mark the branch at the end of BB as live and +// set LivePdom(BB) = BB +// otherwse LivePDOM(BB) = IN(BB) +// (below IN(BB) is hold transiently in CommonSuccPostDom) +// +// We traverse the graph in approximate reverse execution order +// and iterate when changes are observed. If we find new live +// nodes however we return from this function and propagate +// that information before making another pass here. +// Once a branch is live, LivePdom for that block will not change and so we +// limit +// iteration to just blocks which have dead branches. We filter this list +// to remove live branches each time this function is called so that this +// analysis is limited to the may-be-dead subset of the graph. +// Note that we also eagerly force LivePdom(BB) to BB for blocks which have +// live instructions and an unconditional branch just to eliminate an +// edge condition (see markLive(Instruction*)) +// +void AggressiveCDCE::checkControlDependences() { + // basic blocks in reverse order + setDeadBranchesInPostOrder(); + if (!Worklist.empty()) { + return; // marked loop bottoms live + } + bool Changed; + SmallVector NeverEndingBlocks; + do { + Changed = false; + NeverEndingBlocks.clear(); + // basic blocks in reverse order + for (auto DBInfo : DeadBranchesInPostOrder) { + auto BB = DBInfo->BB; + + DEBUG_MSG("check control flow at " << (DBInfo->Live ? "live " : "dead ") + << BB->getName()); + bool BranchIsLive = false; + BasicBlock *CommonSuccPostDom = nullptr; + for (auto Succ : successors(BB)) { + auto SuccPostDom = BlockInfo[Succ]->LivePostDom; + DEBUG_MSG(" SuccPostDom for " << Succ->getName() << " is " + << getName(SuccPostDom)); + if (!SuccPostDom) { // nullptr == TOP + continue; + } + if (!CommonSuccPostDom) { + CommonSuccPostDom = SuccPostDom; + continue; + } + if (CommonSuccPostDom != SuccPostDom) { + BranchIsLive = true; + break; + } + } + // found new live branch + if (BranchIsLive) { + DEBUG_MSG("control dependence live: " << BB->getName()); + markLive(DBInfo->Terminator); + DBInfo->LivePostDom = DBInfo->BB; + Changed = true; + continue; + } + DEBUG_MSG("Common Live Pdom = " << getName(CommonSuccPostDom)); + if (DBInfo->Live) { + CommonSuccPostDom = BB; + } else if (!CommonSuccPostDom) { + // might also be a loop bottom before we have seen + // the loop top which is why we recompute this set every + // iteration + NeverEndingBlocks.push_back(DBInfo->Terminator); + continue; + } + if (DBInfo->LivePostDom != BB && + DBInfo->LivePostDom != CommonSuccPostDom) { + Changed = true; + DBInfo->LivePostDom = CommonSuccPostDom; + } + DEBUG_MSG("live post dom " << getName(DBInfo->LivePostDom)); + } + // propagate new live information sparsely + // before iterating over blocks again + if (!Worklist.empty()) { + return; + } + } while (Changed); + + // handle blocks which don't reach a live block by simply treating + // them as live. Note that if we force "loop bottoms" to be livethen this + // code should not be reached since it corresponds to loops that do + // not exit. + for (auto Term : NeverEndingBlocks) { + DEBUG_MSG("never ending: " << Term->getParent()->getName()); + markLive(Term); + } +} + +// set of update the vector of dead branches +void AggressiveCDCE::setDeadBranchesInPostOrder() { + if (initializeDeadBranches) { + initializeDeadBranches = false; + DeadBranchesInPostOrder.reserve(F.size()); + copy_non_null(BlockInfoVec.rbegin(), BlockInfoVec.rend(), + std::back_inserter(DeadBranchesInPostOrder), + [](BlockInfoType &Info) { + return Info.terminatorIsLive() ? nullptr : &Info; + }); + return; + } + // remove branches which have known to be live + // and reset the LivePostDom for the dead ones + erase(&DeadBranchesInPostOrder, [this](BlockInfoType *Info) { + if (Info->terminatorIsLive()) { + return true; + } + // block with only unconditional branch? + if (!Info->Live && Info->UnconditionalBranch && + &Info->BB->front() == Info->Terminator) { + if (auto Pred = Info->BB->getSinglePredecessor()) { + if (isLive(Pred->getTerminator())) { + // this mostly avoids unnecssary work removing trival dead regions + DEBUG_MSG("unconditional from live pred " << Info->BB->getName()); + Info->Live = true; + *Info->TerminatorLive = true; + return true; + } + } + } + Info->LivePostDom = nullptr; + return false; + }); +} + +// 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 DBInfo : DeadBranchesInPostOrder) { + 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); + } + } + } +} + +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); + } + } +} + +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() { + + erase(&DeadBranchesInPostOrder, + [](const BlockInfoType *DB) { return DB->terminatorIsLive(); }); + SmallPtrSet DeadRegions; + + // Examine dead blocks and collect them at their + // live post-dominator to be processed as a region. + for (auto Info : DeadBranchesInPostOrder) { + 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( + DeadBranchesInPostOrder.begin(), DeadBranchesInPostOrder.end(), + [](const BlockInfoType *DB) { return !DB->terminatorIsLive(); }); + + // 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 DB : DeadBranchesInPostOrder) { + 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::debugDumpDead() { + dbgs() << "Dead operations:\n"; + BasicBlock *BB = nullptr; + for (Instruction &I : instructions(F)) { + if (!isLive(&I)) { + if (BB != I.getParent()) { + BB = I.getParent(); + dbgs() << (isLive(BB) ? "\nlive " : "\ndead ") << "block " + << BB->getName() << '\n'; + } + I.dump(); + } + } +} + +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) { + if (!Disabled) { + if (AggressiveCDCE(F).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 (Disabled || skipOptnoneFunction(F)) + return false; + return AggressiveCDCE(F).doAggressiveCDCE(); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addPreserved(); + } +}; +} + +char ACDCELegacyPass::ID = 0; +INITIALIZE_PASS(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/Feature/optnone-opt.ll =================================================================== --- test/Feature/optnone-opt.ll +++ test/Feature/optnone-opt.ll @@ -1,7 +1,7 @@ ; RUN: opt -S -debug %s 2>&1 | FileCheck %s --check-prefix=OPT-O0 -; RUN: opt -O1 -S -debug %s 2>&1 | FileCheck %s --check-prefix=OPT-O1 -; RUN: opt -O2 -S -debug %s 2>&1 | FileCheck %s --check-prefix=OPT-O1 --check-prefix=OPT-O2O3 -; RUN: opt -O3 -S -debug %s 2>&1 | FileCheck %s --check-prefix=OPT-O1 --check-prefix=OPT-O2O3 +; RUN: opt -O1 -S -debug %s 2>&1 | FileCheck %s --check-prefix=OPT-O1 --check-prefix=OPT-O1O2 +; RUN: opt -O2 -S -debug %s 2>&1 | FileCheck %s --check-prefix=OPT-O1 --check-prefix=OPT-O1O2 --check-prefix=OPT-O2O3 +; RUN: opt -O3 -S -debug %s 2>&1 | FileCheck %s --check-prefix=OPT-O1 --check-prefix=OPT-O2O3 --check-prefix=OPT-O3 ; RUN: opt -bb-vectorize -dce -die -loweratomic -S -debug %s 2>&1 | FileCheck %s --check-prefix=OPT-MORE ; RUN: opt -indvars -licm -loop-deletion -loop-extract -loop-idiom -loop-instsimplify -loop-reduce -loop-reroll -loop-rotate -loop-unroll -loop-unswitch -S -debug %s 2>&1 | FileCheck %s --check-prefix=OPT-LOOP @@ -37,7 +37,6 @@ ; OPT-O0-NOT: Skipping pass ; IR passes run at -O1 and higher. -; OPT-O1-DAG: Skipping pass 'Aggressive Dead Code Elimination' ; OPT-O1-DAG: Skipping pass 'Combine redundant instructions' ; OPT-O1-DAG: Skipping pass 'Dead Store Elimination' ; OPT-O1-DAG: Skipping pass 'Early CSE' @@ -50,10 +49,16 @@ ; OPT-O1-DAG: Skipping pass 'Tail Call Elimination' ; OPT-O1-DAG: Skipping pass 'Value Propagation' +; Additional IR passes run at -01 and -O2 and higher. +; OPT-O1O2-DAG: Skipping pass 'Aggressive Dead Code Elimination' + ; Additional IR passes run at -O2 and higher. ; OPT-O2O3-DAG: Skipping pass 'Global Value Numbering' ; OPT-O2O3-DAG: Skipping pass 'SLP Vectorizer' +; Additional IR passes run at -O3 and higher. +; OPT-O3-DAG: Skipping pass 'Aggressive Control Dead Code Elimination' + ; Additional IR passes that opt doesn't turn on by default. ; OPT-MORE-DAG: Skipping pass 'Basic-Block Vectorization' ; OPT-MORE-DAG: Skipping pass 'Dead Code Elimination' 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) { ;