Index: lib/Transforms/Scalar/ADCE.cpp =================================================================== --- lib/Transforms/Scalar/ADCE.cpp +++ lib/Transforms/Scalar/ADCE.cpp @@ -36,32 +36,85 @@ STATISTIC(NumRemoved, "Number of instructions removed"); +// This is a tempoary option until we change the interface +// to this pass based on optimization level. +static cl::opt RemoveControlFlowFlag("adce-remove-control-flow", + cl::init(false), cl::Hidden); + namespace { +/// Information about Instructions +struct InstInfoType { + /// True if the associated instruction is live. + bool Live = false; + /// Quick access to information for block containing associated Instruction. + struct BlockInfoType *Block = nullptr; +}; + +/// Information about basic blocks relevant to dead code elimination. +struct BlockInfoType { + /// True when this block contains a live instructions. + bool Live = false; + /// True when this block ends in an unconditional branch. + bool UnconditionalBranch = false; + + /// Quick access to the LiveInfo for the terminator, + /// holds the value &InstInfo[Terminator] + InstInfoType *TerminatorLiveInfo = nullptr; + + bool terminatorIsLive() const { return TerminatorLiveInfo->Live; } + + /// Corresponding BasicBlock. + BasicBlock *BB = nullptr; + + /// Cache of BB->getTerminator() + TerminatorInst *Terminator = nullptr; +}; + class AggressiveDeadCodeElimination { Function &F; - /// Instructions known to be live. - SmallPtrSet Alive; + + /// Mapping of blocks to associated information, an 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; } + /// Instructions known to be live where we need to mark /// reaching definitions as live. SmallVector Worklist; /// Debug info scopes around a live instruction. SmallPtrSet AliveScopes; + /// Set of blocks with not known to have live terminators. + SmallPtrSet BlocksWithDeadTerminators; + + /// The set of blocks which we have determined are live in the + /// most recent iteration of propagating liveness. + SmallPtrSet NewLiveBlocks; + + /// Set up auxiliary data structures for Instructions and BasicBlocks and + /// initialize the Worklist to the set of must-be-live Instruscions. void initialize(); - /// True for operations which are always treated as live. + /// Return true for operations which are always treated as live. bool isAlwaysLive(Instruction &I); - /// True for instrumentation instructions for value profiling. + /// Return true for instrumentation instructions for value profiling. bool isInstrumentsConstant(Instruction &I); - /// Propagate liveness to reaching definitions. void markLiveInstructions(); /// Mark an instruction as live. - void markLive(Instruction &I); - + void markLive(Instruction *I); + + /// Record the Debug Scopes which surround live debug information. void collectLiveScopes(const DILocalScope &LS); void collectLiveScopes(const DILocation &DL); - + + /// Analyze dead branches to find those whose branches are the sources + /// of control dependences impacting a live block. Those branches are + /// marked live. + void markLiveBranchesFromControlDependences(); /// Remove instructions not marked live, return if any any instruction /// was removed. @@ -79,23 +132,94 @@ return removeDeadInstructions(); } +static bool isUnconditionalBranch(TerminatorInst *Term) { + auto BR = dyn_cast(Term); + return BR && BR->isUnconditional(); +} + void AggressiveDeadCodeElimination::initialize() { + + auto NumBlocks = F.size(); + + // We will have an entry in the map for each block so we grow the + // structure to twice that size to keep the load factor low in the hash table. + BlockInfo.reserve(NumBlocks); + size_t NumInsts = 0; + + // Iterate over blocks and initialize BlockInfoVec entries, count + // instructions to size the InstInfo hash table. + for (auto &BB : F) { + NumInsts += BB.size(); + auto &Info = BlockInfo[&BB]; + Info.BB = &BB; + Info.Terminator = BB.getTerminator(); + Info.UnconditionalBranch = isUnconditionalBranch(Info.Terminator); + } + + // Initialize instruction map and set pointers to block info. + InstInfo.reserve(NumInsts); + for (auto &BBInfo : BlockInfo) + for (Instruction &I : *BBInfo.second.BB) + InstInfo[&I].Block = &BBInfo.second; + + // Since BlockInfoVec holds pointers into InstInfo and vice-versa, we may not + // add any more elements to either after this point. + for (auto &BBInfo : BlockInfo) + BBInfo.second.TerminatorLiveInfo = &InstInfo[BBInfo.second.Terminator]; + // Collect the set of "root" instructions that are known live. for (Instruction &I : instructions(F)) if (isAlwaysLive(I)) - markLive(I); + markLive(&I); + + if (!RemoveControlFlowFlag) + return; + + // This is temporary: will update with post order traveral to + // find loop bottoms + SmallPtrSet Seen; + for (auto &BB : F) { + Seen.insert(&BB); + TerminatorInst *Term = BB.getTerminator(); + if (isLive(Term)) + continue; + + for (auto Succ : successors(&BB)) + if (Seen.count(Succ)) { + // back edge.... + markLive(Term); + break; + } + } + // end temporary handling of loops + + // Treat the entry block as always live + auto *BB = &F.getEntryBlock(); + auto &EntryInfo = BlockInfo[BB]; + EntryInfo.Live = true; + if (EntryInfo.UnconditionalBranch) + markLive(EntryInfo.Terminator); + + // Build initial collection of blocks with dead terminators + for (auto &BBInfo : BlockInfo) + if (!BBInfo.second.terminatorIsLive()) + BlocksWithDeadTerminators.insert(BBInfo.second.BB); } bool AggressiveDeadCodeElimination::isAlwaysLive(Instruction &I) { - // TODO -- use llvm::isInstructionTriviallyDead - if (isa(I) || I.isEHPad() || I.mayHaveSideEffects()) { + if (I.isEHPad() || I.mayHaveSideEffects()) { // Skip any value profile instrumentation calls if they are // instrumenting constants. - if (!isInstrumentsConstant(I)) - return true; + if (isInstrumentsConstant(I)) + return false; + return true; } - return false; + if (!isa(I)) + return false; + if (RemoveControlFlowFlag && (isa(I) || isa(I))) + return false; + return true; } // Check if this instruction is a runtime call for value profiling and @@ -112,29 +236,64 @@ void AggressiveDeadCodeElimination::markLiveInstructions() { - // Propagate liveness backwards to operands. Keep track of live debug info - // scopes. - while (!Worklist.empty()) { - Instruction *Curr = Worklist.pop_back_val(); + // Propagate liveness backwards to operands. + do { + // Worklist holds newly discovered live instructions + // where we need to mark the inputs as live. + while (!Worklist.empty()) { + Instruction *LiveInst = Worklist.pop_back_val(); + + // Collect the live debug info scopes attached to this instruction. + if (const DILocation *DL = LiveInst->getDebugLoc()) + collectLiveScopes(*DL); + + DEBUG(dbgs() << "work live: "; LiveInst->dump();); + for (Use &OI : LiveInst->operands()) + if (Instruction *Inst = dyn_cast(OI)) + markLive(Inst); + } + markLiveBranchesFromControlDependences(); + // TODO -- handle PhiNodes + } while (!Worklist.empty()); - // Collect the live debug info scopes attached to this instruction. - if (const DILocation *DL = Curr->getDebugLoc()) - collectLiveScopes(*DL); + // temporary until control dependences are implemented + assert(BlocksWithDeadTerminators.empty()); +} - for (Use &OI : Curr->operands()) { - if (Instruction *Inst = dyn_cast(OI)) - markLive(*Inst); - } - } +void AggressiveDeadCodeElimination::markLive(Instruction *I) { + + auto &Info = InstInfo[I]; + if (Info.Live) + return; + + DEBUG(dbgs() << "mark live: "; I->dump()); + Info.Live = true; + Worklist.push_back(I); + + // Mark the containing block live + auto &BBInfo = *Info.Block; + if (BBInfo.Terminator == I) + BlocksWithDeadTerminators.erase(BBInfo.BB); + if (BBInfo.Live) + return; + + DEBUG(dbgs() << "mark block live: " << BBInfo.BB->getName() << '\n'); + BBInfo.Live = true; + NewLiveBlocks.insert(BBInfo.BB); + + // Mark unconditional branches at the end of live + // blocks as live since there is no work to do for them later + if (BBInfo.UnconditionalBranch && I != BBInfo.Terminator) + markLive(BBInfo.Terminator); } void AggressiveDeadCodeElimination::collectLiveScopes(const DILocalScope &LS) { if (!AliveScopes.insert(&LS).second) return; - + if (isa(LS)) return; - + // Tail-recurse through the scope chain. collectLiveScopes(cast(*LS.getScope())); } @@ -144,19 +303,27 @@ // don't revisit them. if (!AliveScopes.insert(&DL).second) return; - + // Collect live scopes from the scope chain. collectLiveScopes(*DL.getScope()); - + // Tail-recurse through the inlined-at chain. if (const DILocation *IA = DL.getInlinedAt()) collectLiveScopes(*IA); } -void AggressiveDeadCodeElimination::markLive(Instruction &I) { - if (!Alive.insert(&I).second) - return; - Worklist.push_back(&I); +void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() { + + // This is a place holder, mark all read operations live + // The next patch will replace this with using iterated dominance + // frontier to compute branches that need to be live because they + // control live blocks with live operations + SmallVector DeadTerminators; + for (auto *BB : BlocksWithDeadTerminators) + DeadTerminators.push_back(BB->getTerminator()); + for (auto I : DeadTerminators) + markLive(I); + NewLiveBlocks.clear(); } bool AggressiveDeadCodeElimination::removeDeadInstructions() { @@ -167,9 +334,11 @@ // NOTE: We reuse the Worklist vector here for memory efficiency. for (Instruction &I : instructions(F)) { // Check if the instruction is alive. - if (Alive.count(&I)) + if (isLive(&I)) continue; + assert(!I.isTerminator() && "NYI: Removing Control Flow"); + if (auto *DII = dyn_cast(&I)) { // Check if the scope of this variable location is alive. if (AliveScopes.count(DII->getDebugLoc()->getScope())) @@ -182,7 +351,7 @@ // why isn't the scope of the location alive? if (Value *V = DII->getVariableLocation()) if (Instruction *II = dyn_cast(V)) - if (Alive.count(II)) + if (isLive(II)) dbgs() << "Dropping debug info for " << *DII << "\n"; }); }