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/STLExtras.h" 21#include "llvm/ADT/SmallPtrSet.h" 22#include "llvm/ADT/SmallVector.h" 23#include "llvm/ADT/Statistic.h" 24#include "llvm/Analysis/DomTreeUpdater.h" 25#include "llvm/Analysis/GlobalsModRef.h" 26#include "llvm/Analysis/TargetLibraryInfo.h" 27#include "llvm/Analysis/ValueTracking.h" 28#include "llvm/IR/BasicBlock.h" 29#include "llvm/IR/Constant.h" 30#include "llvm/IR/DerivedTypes.h" 31#include "llvm/IR/Function.h" 32#include "llvm/IR/GlobalVariable.h" 33#include "llvm/IR/InstrTypes.h" 34#include "llvm/IR/Instruction.h" 35#include "llvm/IR/Instructions.h" 36#include "llvm/IR/Module.h" 37#include "llvm/IR/PassManager.h" 38#include "llvm/IR/Type.h" 39#include "llvm/IR/User.h" 40#include "llvm/IR/Value.h" 41#include "llvm/Pass.h" 42#include "llvm/Support/Casting.h" 43#include "llvm/Support/Debug.h" 44#include "llvm/Support/ErrorHandling.h" 45#include "llvm/Support/raw_ostream.h" 46#include "llvm/Transforms/Scalar.h" 47#include "llvm/Transforms/Utils/Local.h" 48#include "llvm/Transforms/Utils/SCCPSolver.h" 49#include <utility> 50 51using namespace llvm; 52 53#define DEBUG_TYPE "sccp" 54 55STATISTIC(NumInstRemoved, "Number of instructions removed"); 56STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable"); 57STATISTIC(NumInstReplaced, 58 "Number of instructions replaced with (simpler) instruction"); 59 60// runSCCP() - Run the Sparse Conditional Constant Propagation algorithm, 61// and return true if the function was modified. 62static bool runSCCP(Function &F, const DataLayout &DL, 63 const TargetLibraryInfo *TLI, DomTreeUpdater &DTU) { 64 LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n"); 65 SCCPSolver Solver( 66 DL, [TLI](Function &F) -> const TargetLibraryInfo & { return *TLI; }, 67 F.getContext()); 68 69 // Mark the first block of the function as being executable. 70 Solver.markBlockExecutable(&F.front()); 71 72 // Mark all arguments to the function as being overdefined. 73 for (Argument &AI : F.args()) 74 Solver.markOverdefined(&AI); 75 76 // Solve for constants. 77 bool ResolvedUndefs = true; 78 while (ResolvedUndefs) { 79 Solver.solve(); 80 LLVM_DEBUG(dbgs() << "RESOLVING UNDEFs\n"); 81 ResolvedUndefs = Solver.resolvedUndefsIn(F); 82 } 83 84 bool MadeChanges = false; 85 86 // If we decided that there are basic blocks that are dead in this function, 87 // delete their contents now. Note that we cannot actually delete the blocks, 88 // as we cannot modify the CFG of the function. 89 90 SmallPtrSet<Value *, 32> InsertedValues; 91 SmallVector<BasicBlock *, 8> BlocksToErase; 92 for (BasicBlock &BB : F) { 93 if (!Solver.isBlockExecutable(&BB)) { 94 LLVM_DEBUG(dbgs() << " BasicBlock Dead:" << BB); 95 ++NumDeadBlocks; 96 BlocksToErase.push_back(&BB); 97 MadeChanges = true; 98 continue; 99 } 100 101 MadeChanges |= Solver.simplifyInstsInBlock(BB, InsertedValues, 102 NumInstRemoved, NumInstReplaced); 103 } 104 105 // Remove unreachable blocks and non-feasible edges. 106 for (BasicBlock *DeadBB : BlocksToErase) 107 NumInstRemoved += changeToUnreachable(DeadBB->getFirstNonPHI(), 108 /*PreserveLCSSA=*/false, &DTU); 109 110 BasicBlock *NewUnreachableBB = nullptr; 111 for (BasicBlock &BB : F) 112 MadeChanges |= Solver.removeNonFeasibleEdges(&BB, DTU, NewUnreachableBB); 113 114 for (BasicBlock *DeadBB : BlocksToErase) 115 if (!DeadBB->hasAddressTaken()) 116 DTU.deleteBB(DeadBB); 117 118 return MadeChanges; 119} 120 121PreservedAnalyses SCCPPass::run(Function &F, FunctionAnalysisManager &AM) { 122 const DataLayout &DL = F.getParent()->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