| File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Transforms/Scalar/ADCE.cpp |
| Warning: | line 609, column 29 Access to field 'BB' results in a dereference of a null pointer (loaded from variable 'PreferredSucc') |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | //===- ADCE.cpp - Code to perform dead code elimination -------------------===// | |||
| 2 | // | |||
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |||
| 4 | // See https://llvm.org/LICENSE.txt for license information. | |||
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |||
| 6 | // | |||
| 7 | //===----------------------------------------------------------------------===// | |||
| 8 | // | |||
| 9 | // This file implements the Aggressive Dead Code Elimination pass. This pass | |||
| 10 | // optimistically assumes that all instructions are dead until proven otherwise, | |||
| 11 | // allowing it to eliminate dead computations that other DCE passes do not | |||
| 12 | // catch, particularly involving loop computations. | |||
| 13 | // | |||
| 14 | //===----------------------------------------------------------------------===// | |||
| 15 | ||||
| 16 | #include "llvm/Transforms/Scalar/ADCE.h" | |||
| 17 | #include "llvm/ADT/DenseMap.h" | |||
| 18 | #include "llvm/ADT/DepthFirstIterator.h" | |||
| 19 | #include "llvm/ADT/GraphTraits.h" | |||
| 20 | #include "llvm/ADT/MapVector.h" | |||
| 21 | #include "llvm/ADT/PostOrderIterator.h" | |||
| 22 | #include "llvm/ADT/SetVector.h" | |||
| 23 | #include "llvm/ADT/SmallPtrSet.h" | |||
| 24 | #include "llvm/ADT/SmallVector.h" | |||
| 25 | #include "llvm/ADT/Statistic.h" | |||
| 26 | #include "llvm/Analysis/DomTreeUpdater.h" | |||
| 27 | #include "llvm/Analysis/GlobalsModRef.h" | |||
| 28 | #include "llvm/Analysis/IteratedDominanceFrontier.h" | |||
| 29 | #include "llvm/Analysis/PostDominators.h" | |||
| 30 | #include "llvm/IR/BasicBlock.h" | |||
| 31 | #include "llvm/IR/CFG.h" | |||
| 32 | #include "llvm/IR/DebugInfoMetadata.h" | |||
| 33 | #include "llvm/IR/DebugLoc.h" | |||
| 34 | #include "llvm/IR/Dominators.h" | |||
| 35 | #include "llvm/IR/Function.h" | |||
| 36 | #include "llvm/IR/IRBuilder.h" | |||
| 37 | #include "llvm/IR/InstIterator.h" | |||
| 38 | #include "llvm/IR/InstrTypes.h" | |||
| 39 | #include "llvm/IR/Instruction.h" | |||
| 40 | #include "llvm/IR/Instructions.h" | |||
| 41 | #include "llvm/IR/IntrinsicInst.h" | |||
| 42 | #include "llvm/IR/PassManager.h" | |||
| 43 | #include "llvm/IR/Use.h" | |||
| 44 | #include "llvm/IR/Value.h" | |||
| 45 | #include "llvm/InitializePasses.h" | |||
| 46 | #include "llvm/Pass.h" | |||
| 47 | #include "llvm/ProfileData/InstrProf.h" | |||
| 48 | #include "llvm/Support/Casting.h" | |||
| 49 | #include "llvm/Support/CommandLine.h" | |||
| 50 | #include "llvm/Support/Debug.h" | |||
| 51 | #include "llvm/Support/raw_ostream.h" | |||
| 52 | #include "llvm/Transforms/Scalar.h" | |||
| 53 | #include "llvm/Transforms/Utils/Local.h" | |||
| 54 | #include <cassert> | |||
| 55 | #include <cstddef> | |||
| 56 | #include <utility> | |||
| 57 | ||||
| 58 | using namespace llvm; | |||
| 59 | ||||
| 60 | #define DEBUG_TYPE"adce" "adce" | |||
| 61 | ||||
| 62 | STATISTIC(NumRemoved, "Number of instructions removed")static llvm::Statistic NumRemoved = {"adce", "NumRemoved", "Number of instructions removed" }; | |||
| 63 | STATISTIC(NumBranchesRemoved, "Number of branch instructions removed")static llvm::Statistic NumBranchesRemoved = {"adce", "NumBranchesRemoved" , "Number of branch instructions removed"}; | |||
| 64 | ||||
| 65 | // This is a temporary option until we change the interface to this pass based | |||
| 66 | // on optimization level. | |||
| 67 | static cl::opt<bool> RemoveControlFlowFlag("adce-remove-control-flow", | |||
| 68 | cl::init(true), cl::Hidden); | |||
| 69 | ||||
| 70 | // This option enables removing of may-be-infinite loops which have no other | |||
| 71 | // effect. | |||
| 72 | static cl::opt<bool> RemoveLoops("adce-remove-loops", cl::init(false), | |||
| 73 | cl::Hidden); | |||
| 74 | ||||
| 75 | namespace { | |||
| 76 | ||||
| 77 | /// Information about Instructions | |||
| 78 | struct InstInfoType { | |||
| 79 | /// True if the associated instruction is live. | |||
| 80 | bool Live = false; | |||
| 81 | ||||
| 82 | /// Quick access to information for block containing associated Instruction. | |||
| 83 | struct BlockInfoType *Block = nullptr; | |||
| 84 | }; | |||
| 85 | ||||
| 86 | /// Information about basic blocks relevant to dead code elimination. | |||
| 87 | struct BlockInfoType { | |||
| 88 | /// True when this block contains a live instructions. | |||
| 89 | bool Live = false; | |||
| 90 | ||||
| 91 | /// True when this block ends in an unconditional branch. | |||
| 92 | bool UnconditionalBranch = false; | |||
| 93 | ||||
| 94 | /// True when this block is known to have live PHI nodes. | |||
| 95 | bool HasLivePhiNodes = false; | |||
| 96 | ||||
| 97 | /// Control dependence sources need to be live for this block. | |||
| 98 | bool CFLive = false; | |||
| 99 | ||||
| 100 | /// Quick access to the LiveInfo for the terminator, | |||
| 101 | /// holds the value &InstInfo[Terminator] | |||
| 102 | InstInfoType *TerminatorLiveInfo = nullptr; | |||
| 103 | ||||
| 104 | /// Corresponding BasicBlock. | |||
| 105 | BasicBlock *BB = nullptr; | |||
| 106 | ||||
| 107 | /// Cache of BB->getTerminator(). | |||
| 108 | Instruction *Terminator = nullptr; | |||
| 109 | ||||
| 110 | /// Post-order numbering of reverse control flow graph. | |||
| 111 | unsigned PostOrder; | |||
| 112 | ||||
| 113 | bool terminatorIsLive() const { return TerminatorLiveInfo->Live; } | |||
| 114 | }; | |||
| 115 | ||||
| 116 | class AggressiveDeadCodeElimination { | |||
| 117 | Function &F; | |||
| 118 | ||||
| 119 | // ADCE does not use DominatorTree per se, but it updates it to preserve the | |||
| 120 | // analysis. | |||
| 121 | DominatorTree *DT; | |||
| 122 | PostDominatorTree &PDT; | |||
| 123 | ||||
| 124 | /// Mapping of blocks to associated information, an element in BlockInfoVec. | |||
| 125 | /// Use MapVector to get deterministic iteration order. | |||
| 126 | MapVector<BasicBlock *, BlockInfoType> BlockInfo; | |||
| 127 | bool isLive(BasicBlock *BB) { return BlockInfo[BB].Live; } | |||
| 128 | ||||
| 129 | /// Mapping of instructions to associated information. | |||
| 130 | DenseMap<Instruction *, InstInfoType> InstInfo; | |||
| 131 | bool isLive(Instruction *I) { return InstInfo[I].Live; } | |||
| 132 | ||||
| 133 | /// Instructions known to be live where we need to mark | |||
| 134 | /// reaching definitions as live. | |||
| 135 | SmallVector<Instruction *, 128> Worklist; | |||
| 136 | ||||
| 137 | /// Debug info scopes around a live instruction. | |||
| 138 | SmallPtrSet<const Metadata *, 32> AliveScopes; | |||
| 139 | ||||
| 140 | /// Set of blocks with not known to have live terminators. | |||
| 141 | SmallSetVector<BasicBlock *, 16> BlocksWithDeadTerminators; | |||
| 142 | ||||
| 143 | /// The set of blocks which we have determined whose control | |||
| 144 | /// dependence sources must be live and which have not had | |||
| 145 | /// those dependences analyzed. | |||
| 146 | SmallPtrSet<BasicBlock *, 16> NewLiveBlocks; | |||
| 147 | ||||
| 148 | /// Set up auxiliary data structures for Instructions and BasicBlocks and | |||
| 149 | /// initialize the Worklist to the set of must-be-live Instruscions. | |||
| 150 | void initialize(); | |||
| 151 | ||||
| 152 | /// Return true for operations which are always treated as live. | |||
| 153 | bool isAlwaysLive(Instruction &I); | |||
| 154 | ||||
| 155 | /// Return true for instrumentation instructions for value profiling. | |||
| 156 | bool isInstrumentsConstant(Instruction &I); | |||
| 157 | ||||
| 158 | /// Propagate liveness to reaching definitions. | |||
| 159 | void markLiveInstructions(); | |||
| 160 | ||||
| 161 | /// Mark an instruction as live. | |||
| 162 | void markLive(Instruction *I); | |||
| 163 | ||||
| 164 | /// Mark a block as live. | |||
| 165 | void markLive(BlockInfoType &BB); | |||
| 166 | void markLive(BasicBlock *BB) { markLive(BlockInfo[BB]); } | |||
| 167 | ||||
| 168 | /// Mark terminators of control predecessors of a PHI node live. | |||
| 169 | void markPhiLive(PHINode *PN); | |||
| 170 | ||||
| 171 | /// Record the Debug Scopes which surround live debug information. | |||
| 172 | void collectLiveScopes(const DILocalScope &LS); | |||
| 173 | void collectLiveScopes(const DILocation &DL); | |||
| 174 | ||||
| 175 | /// Analyze dead branches to find those whose branches are the sources | |||
| 176 | /// of control dependences impacting a live block. Those branches are | |||
| 177 | /// marked live. | |||
| 178 | void markLiveBranchesFromControlDependences(); | |||
| 179 | ||||
| 180 | /// Remove instructions not marked live, return if any instruction was | |||
| 181 | /// removed. | |||
| 182 | bool removeDeadInstructions(); | |||
| 183 | ||||
| 184 | /// Identify connected sections of the control flow graph which have | |||
| 185 | /// dead terminators and rewrite the control flow graph to remove them. | |||
| 186 | bool updateDeadRegions(); | |||
| 187 | ||||
| 188 | /// Set the BlockInfo::PostOrder field based on a post-order | |||
| 189 | /// numbering of the reverse control flow graph. | |||
| 190 | void computeReversePostOrder(); | |||
| 191 | ||||
| 192 | /// Make the terminator of this block an unconditional branch to \p Target. | |||
| 193 | void makeUnconditional(BasicBlock *BB, BasicBlock *Target); | |||
| 194 | ||||
| 195 | public: | |||
| 196 | AggressiveDeadCodeElimination(Function &F, DominatorTree *DT, | |||
| 197 | PostDominatorTree &PDT) | |||
| 198 | : F(F), DT(DT), PDT(PDT) {} | |||
| 199 | ||||
| 200 | bool performDeadCodeElimination(); | |||
| 201 | }; | |||
| 202 | ||||
| 203 | } // end anonymous namespace | |||
| 204 | ||||
| 205 | bool AggressiveDeadCodeElimination::performDeadCodeElimination() { | |||
| 206 | initialize(); | |||
| 207 | markLiveInstructions(); | |||
| 208 | return removeDeadInstructions(); | |||
| 209 | } | |||
| 210 | ||||
| 211 | static bool isUnconditionalBranch(Instruction *Term) { | |||
| 212 | auto *BR = dyn_cast<BranchInst>(Term); | |||
| 213 | return BR && BR->isUnconditional(); | |||
| 214 | } | |||
| 215 | ||||
| 216 | void AggressiveDeadCodeElimination::initialize() { | |||
| 217 | auto NumBlocks = F.size(); | |||
| 218 | ||||
| 219 | // We will have an entry in the map for each block so we grow the | |||
| 220 | // structure to twice that size to keep the load factor low in the hash table. | |||
| 221 | BlockInfo.reserve(NumBlocks); | |||
| 222 | size_t NumInsts = 0; | |||
| 223 | ||||
| 224 | // Iterate over blocks and initialize BlockInfoVec entries, count | |||
| 225 | // instructions to size the InstInfo hash table. | |||
| 226 | for (auto &BB : F) { | |||
| 227 | NumInsts += BB.size(); | |||
| 228 | auto &Info = BlockInfo[&BB]; | |||
| 229 | Info.BB = &BB; | |||
| 230 | Info.Terminator = BB.getTerminator(); | |||
| 231 | Info.UnconditionalBranch = isUnconditionalBranch(Info.Terminator); | |||
| 232 | } | |||
| 233 | ||||
| 234 | // Initialize instruction map and set pointers to block info. | |||
| 235 | InstInfo.reserve(NumInsts); | |||
| 236 | for (auto &BBInfo : BlockInfo) | |||
| 237 | for (Instruction &I : *BBInfo.second.BB) | |||
| 238 | InstInfo[&I].Block = &BBInfo.second; | |||
| 239 | ||||
| 240 | // Since BlockInfoVec holds pointers into InstInfo and vice-versa, we may not | |||
| 241 | // add any more elements to either after this point. | |||
| 242 | for (auto &BBInfo : BlockInfo) | |||
| 243 | BBInfo.second.TerminatorLiveInfo = &InstInfo[BBInfo.second.Terminator]; | |||
| 244 | ||||
| 245 | // Collect the set of "root" instructions that are known live. | |||
| 246 | for (Instruction &I : instructions(F)) | |||
| 247 | if (isAlwaysLive(I)) | |||
| 248 | markLive(&I); | |||
| 249 | ||||
| 250 | if (!RemoveControlFlowFlag) | |||
| 251 | return; | |||
| 252 | ||||
| 253 | if (!RemoveLoops) { | |||
| 254 | // This stores state for the depth-first iterator. In addition | |||
| 255 | // to recording which nodes have been visited we also record whether | |||
| 256 | // a node is currently on the "stack" of active ancestors of the current | |||
| 257 | // node. | |||
| 258 | using StatusMap = DenseMap<BasicBlock *, bool>; | |||
| 259 | ||||
| 260 | class DFState : public StatusMap { | |||
| 261 | public: | |||
| 262 | std::pair<StatusMap::iterator, bool> insert(BasicBlock *BB) { | |||
| 263 | return StatusMap::insert(std::make_pair(BB, true)); | |||
| 264 | } | |||
| 265 | ||||
| 266 | // Invoked after we have visited all children of a node. | |||
| 267 | void completed(BasicBlock *BB) { (*this)[BB] = false; } | |||
| 268 | ||||
| 269 | // Return true if \p BB is currently on the active stack | |||
| 270 | // of ancestors. | |||
| 271 | bool onStack(BasicBlock *BB) { | |||
| 272 | auto Iter = find(BB); | |||
| 273 | return Iter != end() && Iter->second; | |||
| 274 | } | |||
| 275 | } State; | |||
| 276 | ||||
| 277 | State.reserve(F.size()); | |||
| 278 | // Iterate over blocks in depth-first pre-order and | |||
| 279 | // treat all edges to a block already seen as loop back edges | |||
| 280 | // and mark the branch live it if there is a back edge. | |||
| 281 | for (auto *BB: depth_first_ext(&F.getEntryBlock(), State)) { | |||
| 282 | Instruction *Term = BB->getTerminator(); | |||
| 283 | if (isLive(Term)) | |||
| 284 | continue; | |||
| 285 | ||||
| 286 | for (auto *Succ : successors(BB)) | |||
| 287 | if (State.onStack(Succ)) { | |||
| 288 | // back edge.... | |||
| 289 | markLive(Term); | |||
| 290 | break; | |||
| 291 | } | |||
| 292 | } | |||
| 293 | } | |||
| 294 | ||||
| 295 | // Mark blocks live if there is no path from the block to a | |||
| 296 | // return of the function. | |||
| 297 | // We do this by seeing which of the postdomtree root children exit the | |||
| 298 | // program, and for all others, mark the subtree live. | |||
| 299 | for (auto &PDTChild : children<DomTreeNode *>(PDT.getRootNode())) { | |||
| 300 | auto *BB = PDTChild->getBlock(); | |||
| 301 | auto &Info = BlockInfo[BB]; | |||
| 302 | // Real function return | |||
| 303 | if (isa<ReturnInst>(Info.Terminator)) { | |||
| 304 | LLVM_DEBUG(dbgs() << "post-dom root child is a return: " << BB->getName()do { } while (false) | |||
| 305 | << '\n';)do { } while (false); | |||
| 306 | continue; | |||
| 307 | } | |||
| 308 | ||||
| 309 | // This child is something else, like an infinite loop. | |||
| 310 | for (auto DFNode : depth_first(PDTChild)) | |||
| 311 | markLive(BlockInfo[DFNode->getBlock()].Terminator); | |||
| 312 | } | |||
| 313 | ||||
| 314 | // Treat the entry block as always live | |||
| 315 | auto *BB = &F.getEntryBlock(); | |||
| 316 | auto &EntryInfo = BlockInfo[BB]; | |||
| 317 | EntryInfo.Live = true; | |||
| 318 | if (EntryInfo.UnconditionalBranch) | |||
| 319 | markLive(EntryInfo.Terminator); | |||
| 320 | ||||
| 321 | // Build initial collection of blocks with dead terminators | |||
| 322 | for (auto &BBInfo : BlockInfo) | |||
| 323 | if (!BBInfo.second.terminatorIsLive()) | |||
| 324 | BlocksWithDeadTerminators.insert(BBInfo.second.BB); | |||
| 325 | } | |||
| 326 | ||||
| 327 | bool AggressiveDeadCodeElimination::isAlwaysLive(Instruction &I) { | |||
| 328 | // TODO -- use llvm::isInstructionTriviallyDead | |||
| 329 | if (I.isEHPad() || I.mayHaveSideEffects()) { | |||
| 330 | // Skip any value profile instrumentation calls if they are | |||
| 331 | // instrumenting constants. | |||
| 332 | if (isInstrumentsConstant(I)) | |||
| 333 | return false; | |||
| 334 | return true; | |||
| 335 | } | |||
| 336 | if (!I.isTerminator()) | |||
| 337 | return false; | |||
| 338 | if (RemoveControlFlowFlag && (isa<BranchInst>(I) || isa<SwitchInst>(I))) | |||
| 339 | return false; | |||
| 340 | return true; | |||
| 341 | } | |||
| 342 | ||||
| 343 | // Check if this instruction is a runtime call for value profiling and | |||
| 344 | // if it's instrumenting a constant. | |||
| 345 | bool AggressiveDeadCodeElimination::isInstrumentsConstant(Instruction &I) { | |||
| 346 | // TODO -- move this test into llvm::isInstructionTriviallyDead | |||
| 347 | if (CallInst *CI = dyn_cast<CallInst>(&I)) | |||
| 348 | if (Function *Callee = CI->getCalledFunction()) | |||
| 349 | if (Callee->getName().equals(getInstrProfValueProfFuncName())) | |||
| 350 | if (isa<Constant>(CI->getArgOperand(0))) | |||
| 351 | return true; | |||
| 352 | return false; | |||
| 353 | } | |||
| 354 | ||||
| 355 | void AggressiveDeadCodeElimination::markLiveInstructions() { | |||
| 356 | // Propagate liveness backwards to operands. | |||
| 357 | do { | |||
| 358 | // Worklist holds newly discovered live instructions | |||
| 359 | // where we need to mark the inputs as live. | |||
| 360 | while (!Worklist.empty()) { | |||
| 361 | Instruction *LiveInst = Worklist.pop_back_val(); | |||
| 362 | LLVM_DEBUG(dbgs() << "work live: "; LiveInst->dump();)do { } while (false); | |||
| 363 | ||||
| 364 | for (Use &OI : LiveInst->operands()) | |||
| 365 | if (Instruction *Inst = dyn_cast<Instruction>(OI)) | |||
| 366 | markLive(Inst); | |||
| 367 | ||||
| 368 | if (auto *PN = dyn_cast<PHINode>(LiveInst)) | |||
| 369 | markPhiLive(PN); | |||
| 370 | } | |||
| 371 | ||||
| 372 | // After data flow liveness has been identified, examine which branch | |||
| 373 | // decisions are required to determine live instructions are executed. | |||
| 374 | markLiveBranchesFromControlDependences(); | |||
| 375 | ||||
| 376 | } while (!Worklist.empty()); | |||
| 377 | } | |||
| 378 | ||||
| 379 | void AggressiveDeadCodeElimination::markLive(Instruction *I) { | |||
| 380 | auto &Info = InstInfo[I]; | |||
| 381 | if (Info.Live) | |||
| 382 | return; | |||
| 383 | ||||
| 384 | LLVM_DEBUG(dbgs() << "mark live: "; I->dump())do { } while (false); | |||
| 385 | Info.Live = true; | |||
| 386 | Worklist.push_back(I); | |||
| 387 | ||||
| 388 | // Collect the live debug info scopes attached to this instruction. | |||
| 389 | if (const DILocation *DL = I->getDebugLoc()) | |||
| 390 | collectLiveScopes(*DL); | |||
| 391 | ||||
| 392 | // Mark the containing block live | |||
| 393 | auto &BBInfo = *Info.Block; | |||
| 394 | if (BBInfo.Terminator == I) { | |||
| 395 | BlocksWithDeadTerminators.remove(BBInfo.BB); | |||
| 396 | // For live terminators, mark destination blocks | |||
| 397 | // live to preserve this control flow edges. | |||
| 398 | if (!BBInfo.UnconditionalBranch) | |||
| 399 | for (auto *BB : successors(I->getParent())) | |||
| 400 | markLive(BB); | |||
| 401 | } | |||
| 402 | markLive(BBInfo); | |||
| 403 | } | |||
| 404 | ||||
| 405 | void AggressiveDeadCodeElimination::markLive(BlockInfoType &BBInfo) { | |||
| 406 | if (BBInfo.Live) | |||
| 407 | return; | |||
| 408 | LLVM_DEBUG(dbgs() << "mark block live: " << BBInfo.BB->getName() << '\n')do { } while (false); | |||
| 409 | BBInfo.Live = true; | |||
| 410 | if (!BBInfo.CFLive) { | |||
| 411 | BBInfo.CFLive = true; | |||
| 412 | NewLiveBlocks.insert(BBInfo.BB); | |||
| 413 | } | |||
| 414 | ||||
| 415 | // Mark unconditional branches at the end of live | |||
| 416 | // blocks as live since there is no work to do for them later | |||
| 417 | if (BBInfo.UnconditionalBranch) | |||
| 418 | markLive(BBInfo.Terminator); | |||
| 419 | } | |||
| 420 | ||||
| 421 | void AggressiveDeadCodeElimination::collectLiveScopes(const DILocalScope &LS) { | |||
| 422 | if (!AliveScopes.insert(&LS).second) | |||
| 423 | return; | |||
| 424 | ||||
| 425 | if (isa<DISubprogram>(LS)) | |||
| 426 | return; | |||
| 427 | ||||
| 428 | // Tail-recurse through the scope chain. | |||
| 429 | collectLiveScopes(cast<DILocalScope>(*LS.getScope())); | |||
| 430 | } | |||
| 431 | ||||
| 432 | void AggressiveDeadCodeElimination::collectLiveScopes(const DILocation &DL) { | |||
| 433 | // Even though DILocations are not scopes, shove them into AliveScopes so we | |||
| 434 | // don't revisit them. | |||
| 435 | if (!AliveScopes.insert(&DL).second) | |||
| 436 | return; | |||
| 437 | ||||
| 438 | // Collect live scopes from the scope chain. | |||
| 439 | collectLiveScopes(*DL.getScope()); | |||
| 440 | ||||
| 441 | // Tail-recurse through the inlined-at chain. | |||
| 442 | if (const DILocation *IA = DL.getInlinedAt()) | |||
| 443 | collectLiveScopes(*IA); | |||
| 444 | } | |||
| 445 | ||||
| 446 | void AggressiveDeadCodeElimination::markPhiLive(PHINode *PN) { | |||
| 447 | auto &Info = BlockInfo[PN->getParent()]; | |||
| 448 | // Only need to check this once per block. | |||
| 449 | if (Info.HasLivePhiNodes) | |||
| 450 | return; | |||
| 451 | Info.HasLivePhiNodes = true; | |||
| 452 | ||||
| 453 | // If a predecessor block is not live, mark it as control-flow live | |||
| 454 | // which will trigger marking live branches upon which | |||
| 455 | // that block is control dependent. | |||
| 456 | for (auto *PredBB : predecessors(Info.BB)) { | |||
| 457 | auto &Info = BlockInfo[PredBB]; | |||
| 458 | if (!Info.CFLive) { | |||
| 459 | Info.CFLive = true; | |||
| 460 | NewLiveBlocks.insert(PredBB); | |||
| 461 | } | |||
| 462 | } | |||
| 463 | } | |||
| 464 | ||||
| 465 | void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() { | |||
| 466 | if (BlocksWithDeadTerminators.empty()) | |||
| 467 | return; | |||
| 468 | ||||
| 469 | LLVM_DEBUG({do { } while (false) | |||
| 470 | dbgs() << "new live blocks:\n";do { } while (false) | |||
| 471 | for (auto *BB : NewLiveBlocks)do { } while (false) | |||
| 472 | dbgs() << "\t" << BB->getName() << '\n';do { } while (false) | |||
| 473 | dbgs() << "dead terminator blocks:\n";do { } while (false) | |||
| 474 | for (auto *BB : BlocksWithDeadTerminators)do { } while (false) | |||
| 475 | dbgs() << "\t" << BB->getName() << '\n';do { } while (false) | |||
| 476 | })do { } while (false); | |||
| 477 | ||||
| 478 | // The dominance frontier of a live block X in the reverse | |||
| 479 | // control graph is the set of blocks upon which X is control | |||
| 480 | // dependent. The following sequence computes the set of blocks | |||
| 481 | // which currently have dead terminators that are control | |||
| 482 | // dependence sources of a block which is in NewLiveBlocks. | |||
| 483 | ||||
| 484 | const SmallPtrSet<BasicBlock *, 16> BWDT{ | |||
| 485 | BlocksWithDeadTerminators.begin(), | |||
| 486 | BlocksWithDeadTerminators.end() | |||
| 487 | }; | |||
| 488 | SmallVector<BasicBlock *, 32> IDFBlocks; | |||
| 489 | ReverseIDFCalculator IDFs(PDT); | |||
| 490 | IDFs.setDefiningBlocks(NewLiveBlocks); | |||
| 491 | IDFs.setLiveInBlocks(BWDT); | |||
| 492 | IDFs.calculate(IDFBlocks); | |||
| 493 | NewLiveBlocks.clear(); | |||
| 494 | ||||
| 495 | // Dead terminators which control live blocks are now marked live. | |||
| 496 | for (auto *BB : IDFBlocks) { | |||
| 497 | LLVM_DEBUG(dbgs() << "live control in: " << BB->getName() << '\n')do { } while (false); | |||
| 498 | markLive(BB->getTerminator()); | |||
| 499 | } | |||
| 500 | } | |||
| 501 | ||||
| 502 | //===----------------------------------------------------------------------===// | |||
| 503 | // | |||
| 504 | // Routines to update the CFG and SSA information before removing dead code. | |||
| 505 | // | |||
| 506 | //===----------------------------------------------------------------------===// | |||
| 507 | bool AggressiveDeadCodeElimination::removeDeadInstructions() { | |||
| 508 | // Updates control and dataflow around dead blocks | |||
| 509 | bool RegionsUpdated = updateDeadRegions(); | |||
| 510 | ||||
| 511 | LLVM_DEBUG({do { } while (false) | |||
| 512 | for (Instruction &I : instructions(F)) {do { } while (false) | |||
| 513 | // Check if the instruction is alive.do { } while (false) | |||
| 514 | if (isLive(&I))do { } while (false) | |||
| 515 | continue;do { } while (false) | |||
| 516 | ||||
| 517 | if (auto *DII = dyn_cast<DbgVariableIntrinsic>(&I)) {do { } while (false) | |||
| 518 | // Check if the scope of this variable location is alive.do { } while (false) | |||
| 519 | if (AliveScopes.count(DII->getDebugLoc()->getScope()))do { } while (false) | |||
| 520 | continue;do { } while (false) | |||
| 521 | ||||
| 522 | // If intrinsic is pointing at a live SSA value, there may be ando { } while (false) | |||
| 523 | // earlier optimization bug: if we know the location of the variable,do { } while (false) | |||
| 524 | // why isn't the scope of the location alive?do { } while (false) | |||
| 525 | for (Value *V : DII->location_ops()) {do { } while (false) | |||
| 526 | if (Instruction *II = dyn_cast<Instruction>(V)) {do { } while (false) | |||
| 527 | if (isLive(II)) {do { } while (false) | |||
| 528 | dbgs() << "Dropping debug info for " << *DII << "\n";do { } while (false) | |||
| 529 | break;do { } while (false) | |||
| 530 | }do { } while (false) | |||
| 531 | }do { } while (false) | |||
| 532 | }do { } while (false) | |||
| 533 | }do { } while (false) | |||
| 534 | }do { } while (false) | |||
| 535 | })do { } while (false); | |||
| 536 | ||||
| 537 | // The inverse of the live set is the dead set. These are those instructions | |||
| 538 | // that have no side effects and do not influence the control flow or return | |||
| 539 | // value of the function, and may therefore be deleted safely. | |||
| 540 | // NOTE: We reuse the Worklist vector here for memory efficiency. | |||
| 541 | for (Instruction &I : instructions(F)) { | |||
| 542 | // Check if the instruction is alive. | |||
| 543 | if (isLive(&I)) | |||
| 544 | continue; | |||
| 545 | ||||
| 546 | if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I)) { | |||
| 547 | // Check if the scope of this variable location is alive. | |||
| 548 | if (AliveScopes.count(DII->getDebugLoc()->getScope())) | |||
| 549 | continue; | |||
| 550 | ||||
| 551 | // Fallthrough and drop the intrinsic. | |||
| 552 | } | |||
| 553 | ||||
| 554 | // Prepare to delete. | |||
| 555 | Worklist.push_back(&I); | |||
| 556 | salvageDebugInfo(I); | |||
| 557 | I.dropAllReferences(); | |||
| 558 | } | |||
| 559 | ||||
| 560 | for (Instruction *&I : Worklist) { | |||
| 561 | ++NumRemoved; | |||
| 562 | I->eraseFromParent(); | |||
| 563 | } | |||
| 564 | ||||
| 565 | return !Worklist.empty() || RegionsUpdated; | |||
| 566 | } | |||
| 567 | ||||
| 568 | // A dead region is the set of dead blocks with a common live post-dominator. | |||
| 569 | bool AggressiveDeadCodeElimination::updateDeadRegions() { | |||
| 570 | LLVM_DEBUG({do { } while (false) | |||
| 571 | dbgs() << "final dead terminator blocks: " << '\n';do { } while (false) | |||
| 572 | for (auto *BB : BlocksWithDeadTerminators)do { } while (false) | |||
| 573 | dbgs() << '\t' << BB->getName()do { } while (false) | |||
| 574 | << (BlockInfo[BB].Live ? " LIVE\n" : "\n");do { } while (false) | |||
| 575 | })do { } while (false); | |||
| 576 | ||||
| 577 | // Don't compute the post ordering unless we needed it. | |||
| 578 | bool HavePostOrder = false; | |||
| 579 | bool Changed = false; | |||
| 580 | ||||
| 581 | for (auto *BB : BlocksWithDeadTerminators) { | |||
| 582 | auto &Info = BlockInfo[BB]; | |||
| 583 | if (Info.UnconditionalBranch) { | |||
| 584 | InstInfo[Info.Terminator].Live = true; | |||
| 585 | continue; | |||
| 586 | } | |||
| 587 | ||||
| 588 | if (!HavePostOrder
| |||
| 589 | computeReversePostOrder(); | |||
| 590 | HavePostOrder = true; | |||
| 591 | } | |||
| 592 | ||||
| 593 | // Add an unconditional branch to the successor closest to the | |||
| 594 | // end of the function which insures a path to the exit for each | |||
| 595 | // live edge. | |||
| 596 | BlockInfoType *PreferredSucc = nullptr; | |||
| 597 | for (auto *Succ : successors(BB)) { | |||
| 598 | auto *Info = &BlockInfo[Succ]; | |||
| 599 | if (!PreferredSucc || PreferredSucc->PostOrder < Info->PostOrder) | |||
| 600 | PreferredSucc = Info; | |||
| 601 | } | |||
| 602 | assert((PreferredSucc && PreferredSucc->PostOrder > 0) &&((void)0) | |||
| 603 | "Failed to find safe successor for dead branch")((void)0); | |||
| 604 | ||||
| 605 | // Collect removed successors to update the (Post)DominatorTrees. | |||
| 606 | SmallPtrSet<BasicBlock *, 4> RemovedSuccessors; | |||
| 607 | bool First = true; | |||
| 608 | for (auto *Succ : successors(BB)) { | |||
| 609 | if (!First
| |||
| ||||
| 610 | Succ->removePredecessor(BB); | |||
| 611 | RemovedSuccessors.insert(Succ); | |||
| 612 | } else | |||
| 613 | First = false; | |||
| 614 | } | |||
| 615 | makeUnconditional(BB, PreferredSucc->BB); | |||
| 616 | ||||
| 617 | // Inform the dominators about the deleted CFG edges. | |||
| 618 | SmallVector<DominatorTree::UpdateType, 4> DeletedEdges; | |||
| 619 | for (auto *Succ : RemovedSuccessors) { | |||
| 620 | // It might have happened that the same successor appeared multiple times | |||
| 621 | // and the CFG edge wasn't really removed. | |||
| 622 | if (Succ != PreferredSucc->BB) { | |||
| 623 | LLVM_DEBUG(dbgs() << "ADCE: (Post)DomTree edge enqueued for deletion"do { } while (false) | |||
| 624 | << BB->getName() << " -> " << Succ->getName()do { } while (false) | |||
| 625 | << "\n")do { } while (false); | |||
| 626 | DeletedEdges.push_back({DominatorTree::Delete, BB, Succ}); | |||
| 627 | } | |||
| 628 | } | |||
| 629 | ||||
| 630 | DomTreeUpdater(DT, &PDT, DomTreeUpdater::UpdateStrategy::Eager) | |||
| 631 | .applyUpdates(DeletedEdges); | |||
| 632 | ||||
| 633 | NumBranchesRemoved += 1; | |||
| 634 | Changed = true; | |||
| 635 | } | |||
| 636 | ||||
| 637 | return Changed; | |||
| 638 | } | |||
| 639 | ||||
| 640 | // reverse top-sort order | |||
| 641 | void AggressiveDeadCodeElimination::computeReversePostOrder() { | |||
| 642 | // This provides a post-order numbering of the reverse control flow graph | |||
| 643 | // Note that it is incomplete in the presence of infinite loops but we don't | |||
| 644 | // need numbers blocks which don't reach the end of the functions since | |||
| 645 | // all branches in those blocks are forced live. | |||
| 646 | ||||
| 647 | // For each block without successors, extend the DFS from the block | |||
| 648 | // backward through the graph | |||
| 649 | SmallPtrSet<BasicBlock*, 16> Visited; | |||
| 650 | unsigned PostOrder = 0; | |||
| 651 | for (auto &BB : F) { | |||
| 652 | if (!succ_empty(&BB)) | |||
| 653 | continue; | |||
| 654 | for (BasicBlock *Block : inverse_post_order_ext(&BB,Visited)) | |||
| 655 | BlockInfo[Block].PostOrder = PostOrder++; | |||
| 656 | } | |||
| 657 | } | |||
| 658 | ||||
| 659 | void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB, | |||
| 660 | BasicBlock *Target) { | |||
| 661 | Instruction *PredTerm = BB->getTerminator(); | |||
| 662 | // Collect the live debug info scopes attached to this instruction. | |||
| 663 | if (const DILocation *DL = PredTerm->getDebugLoc()) | |||
| 664 | collectLiveScopes(*DL); | |||
| 665 | ||||
| 666 | // Just mark live an existing unconditional branch | |||
| 667 | if (isUnconditionalBranch(PredTerm)) { | |||
| 668 | PredTerm->setSuccessor(0, Target); | |||
| 669 | InstInfo[PredTerm].Live = true; | |||
| 670 | return; | |||
| 671 | } | |||
| 672 | LLVM_DEBUG(dbgs() << "making unconditional " << BB->getName() << '\n')do { } while (false); | |||
| 673 | NumBranchesRemoved += 1; | |||
| 674 | IRBuilder<> Builder(PredTerm); | |||
| 675 | auto *NewTerm = Builder.CreateBr(Target); | |||
| 676 | InstInfo[NewTerm].Live = true; | |||
| 677 | if (const DILocation *DL = PredTerm->getDebugLoc()) | |||
| 678 | NewTerm->setDebugLoc(DL); | |||
| 679 | ||||
| 680 | InstInfo.erase(PredTerm); | |||
| 681 | PredTerm->eraseFromParent(); | |||
| 682 | } | |||
| 683 | ||||
| 684 | //===----------------------------------------------------------------------===// | |||
| 685 | // | |||
| 686 | // Pass Manager integration code | |||
| 687 | // | |||
| 688 | //===----------------------------------------------------------------------===// | |||
| 689 | PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) { | |||
| 690 | // ADCE does not need DominatorTree, but require DominatorTree here | |||
| 691 | // to update analysis if it is already available. | |||
| 692 | auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F); | |||
| 693 | auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F); | |||
| 694 | if (!AggressiveDeadCodeElimination(F, DT, PDT).performDeadCodeElimination()) | |||
| 695 | return PreservedAnalyses::all(); | |||
| 696 | ||||
| 697 | PreservedAnalyses PA; | |||
| 698 | // TODO: We could track if we have actually done CFG changes. | |||
| 699 | if (!RemoveControlFlowFlag) | |||
| 700 | PA.preserveSet<CFGAnalyses>(); | |||
| 701 | else { | |||
| 702 | PA.preserve<DominatorTreeAnalysis>(); | |||
| 703 | PA.preserve<PostDominatorTreeAnalysis>(); | |||
| 704 | } | |||
| 705 | return PA; | |||
| 706 | } | |||
| 707 | ||||
| 708 | namespace { | |||
| 709 | ||||
| 710 | struct ADCELegacyPass : public FunctionPass { | |||
| 711 | static char ID; // Pass identification, replacement for typeid | |||
| 712 | ||||
| 713 | ADCELegacyPass() : FunctionPass(ID) { | |||
| 714 | initializeADCELegacyPassPass(*PassRegistry::getPassRegistry()); | |||
| 715 | } | |||
| 716 | ||||
| 717 | bool runOnFunction(Function &F) override { | |||
| 718 | if (skipFunction(F)) | |||
| ||||
| 719 | return false; | |||
| 720 | ||||
| 721 | // ADCE does not need DominatorTree, but require DominatorTree here | |||
| 722 | // to update analysis if it is already available. | |||
| 723 | auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); | |||
| 724 | auto *DT = DTWP
| |||
| 725 | auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree(); | |||
| 726 | return AggressiveDeadCodeElimination(F, DT, PDT) | |||
| 727 | .performDeadCodeElimination(); | |||
| 728 | } | |||
| 729 | ||||
| 730 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
| 731 | AU.addRequired<PostDominatorTreeWrapperPass>(); | |||
| 732 | if (!RemoveControlFlowFlag) | |||
| 733 | AU.setPreservesCFG(); | |||
| 734 | else { | |||
| 735 | AU.addPreserved<DominatorTreeWrapperPass>(); | |||
| 736 | AU.addPreserved<PostDominatorTreeWrapperPass>(); | |||
| 737 | } | |||
| 738 | AU.addPreserved<GlobalsAAWrapperPass>(); | |||
| 739 | } | |||
| 740 | }; | |||
| 741 | ||||
| 742 | } // end anonymous namespace | |||
| 743 | ||||
| 744 | char ADCELegacyPass::ID = 0; | |||
| 745 | ||||
| 746 | INITIALIZE_PASS_BEGIN(ADCELegacyPass, "adce",static void *initializeADCELegacyPassPassOnce(PassRegistry & Registry) { | |||
| 747 | "Aggressive Dead Code Elimination", false, false)static void *initializeADCELegacyPassPassOnce(PassRegistry & Registry) { | |||
| 748 | INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)initializePostDominatorTreeWrapperPassPass(Registry); | |||
| 749 | INITIALIZE_PASS_END(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination",PassInfo *PI = new PassInfo( "Aggressive Dead Code Elimination" , "adce", &ADCELegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor <ADCELegacyPass>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeADCELegacyPassPassFlag ; void llvm::initializeADCELegacyPassPass(PassRegistry &Registry ) { llvm::call_once(InitializeADCELegacyPassPassFlag, initializeADCELegacyPassPassOnce , std::ref(Registry)); } | |||
| 750 | false, false)PassInfo *PI = new PassInfo( "Aggressive Dead Code Elimination" , "adce", &ADCELegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor <ADCELegacyPass>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeADCELegacyPassPassFlag ; void llvm::initializeADCELegacyPassPass(PassRegistry &Registry ) { llvm::call_once(InitializeADCELegacyPassPassFlag, initializeADCELegacyPassPassOnce , std::ref(Registry)); } | |||
| 751 | ||||
| 752 | FunctionPass *llvm::createAggressiveDCEPass() { return new ADCELegacyPass(); } |