1 //===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===// 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 sparse conditional constant propagation and merging: 10 // 11 // Specifically, this: 12 // * Assumes values are constant unless proven otherwise 13 // * Assumes BasicBlocks are dead unless proven otherwise 14 // * Proves values to be constant, and replaces them with constants 15 // * Proves conditional branches to be unconditional 16 // 17 //===----------------------------------------------------------------------===// 18 19 #include "llvm/Transforms/Scalar/SCCP.h" 20 #include "llvm/ADT/SmallPtrSet.h" 21 #include "llvm/ADT/SmallVector.h" 22 #include "llvm/ADT/Statistic.h" 23 #include "llvm/Analysis/DomTreeUpdater.h" 24 #include "llvm/Analysis/GlobalsModRef.h" 25 #include "llvm/Analysis/TargetLibraryInfo.h" 26 #include "llvm/Analysis/ValueLatticeUtils.h" 27 #include "llvm/Analysis/ValueTracking.h" 28 #include "llvm/IR/BasicBlock.h" 29 #include "llvm/IR/DerivedTypes.h" 30 #include "llvm/IR/Function.h" 31 #include "llvm/IR/InstrTypes.h" 32 #include "llvm/IR/Instruction.h" 33 #include "llvm/IR/Instructions.h" 34 #include "llvm/IR/PassManager.h" 35 #include "llvm/IR/Type.h" 36 #include "llvm/IR/Value.h" 37 #include "llvm/Pass.h" 38 #include "llvm/Support/Debug.h" 39 #include "llvm/Support/raw_ostream.h" 40 #include "llvm/Transforms/Scalar.h" 41 #include "llvm/Transforms/Utils/Local.h" 42 #include "llvm/Transforms/Utils/SCCPSolver.h" 43 44 using namespace llvm; 45 46 #define DEBUG_TYPE "sccp" 47 48 STATISTIC(NumInstRemoved, "Number of instructions removed"); 49 STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable"); 50 STATISTIC(NumInstReplaced, 51 "Number of instructions replaced with (simpler) instruction"); 52 53 // runSCCP() - Run the Sparse Conditional Constant Propagation algorithm, 54 // and return true if the function was modified. 55 static bool runSCCP(Function &F, const DataLayout &DL, 56 const TargetLibraryInfo *TLI, DomTreeUpdater &DTU) { 57 LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n"); 58 SCCPSolver Solver( 59 DL, [TLI](Function &F) -> const TargetLibraryInfo & { return *TLI; }, 60 F.getContext()); 61 62 // While we don't do any actual inter-procedural analysis, still track 63 // return values so we can infer attributes. 64 if (canTrackReturnsInterprocedurally(&F)) 65 Solver.addTrackedFunction(&F); 66 67 // Mark the first block of the function as being executable. 68 Solver.markBlockExecutable(&F.front()); 69 70 // Initialize arguments based on attributes. 71 for (Argument &AI : F.args()) 72 Solver.trackValueOfArgument(&AI); 73 74 // Solve for constants. 75 bool ResolvedUndefs = true; 76 while (ResolvedUndefs) { 77 Solver.solve(); 78 LLVM_DEBUG(dbgs() << "RESOLVING UNDEFs\n"); 79 ResolvedUndefs = Solver.resolvedUndefsIn(F); 80 } 81 82 bool MadeChanges = false; 83 84 // If we decided that there are basic blocks that are dead in this function, 85 // delete their contents now. Note that we cannot actually delete the blocks, 86 // as we cannot modify the CFG of the function. 87 88 SmallPtrSet<Value *, 32> InsertedValues; 89 SmallVector<BasicBlock *, 8> BlocksToErase; 90 for (BasicBlock &BB : F) { 91 if (!Solver.isBlockExecutable(&BB)) { 92 LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB); 93 ++NumDeadBlocks; 94 BlocksToErase.push_back(&BB); 95 MadeChanges = true; 96 continue; 97 } 98 99 MadeChanges |= Solver.simplifyInstsInBlock(BB, InsertedValues, 100 NumInstRemoved, NumInstReplaced); 101 } 102 103 // Remove unreachable blocks and non-feasible edges. 104 for (BasicBlock *DeadBB : BlocksToErase) 105 NumInstRemoved += changeToUnreachable(&*DeadBB->getFirstNonPHIIt(), 106 /*PreserveLCSSA=*/false, &DTU); 107 108 BasicBlock *NewUnreachableBB = nullptr; 109 for (BasicBlock &BB : F) 110 MadeChanges |= Solver.removeNonFeasibleEdges(&BB, DTU, NewUnreachableBB); 111 112 for (BasicBlock *DeadBB : BlocksToErase) 113 if (!DeadBB->hasAddressTaken()) 114 DTU.deleteBB(DeadBB); 115 116 Solver.inferReturnAttributes(); 117 118 return MadeChanges; 119 } 120 121 PreservedAnalyses SCCPPass::run(Function &F, FunctionAnalysisManager &AM) { 122 const DataLayout &DL = F.getDataLayout(); 123 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); 124 auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F); 125 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); 126 if (!runSCCP(F, DL, &TLI, DTU)) 127 return PreservedAnalyses::all(); 128 129 auto PA = PreservedAnalyses(); 130 PA.preserve<DominatorTreeAnalysis>(); 131 return PA; 132 } 133