1//===- ConstantProp.cpp - Code to perform Simple 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 constant propagation and merging: 10// 11// Specifically, this: 12// * Converts instructions like "add int 1, 2" into 3 13// 14// Notice that: 15// * This pass has a habit of making definitions be dead. It is a good idea 16// to run a DIE pass sometime after running this pass. 17// 18//===----------------------------------------------------------------------===// 19 20#include "llvm/ADT/SmallPtrSet.h" 21#include "llvm/ADT/SmallVector.h" 22#include "llvm/ADT/Statistic.h" 23#include "llvm/Analysis/ConstantFolding.h" 24#include "llvm/Analysis/TargetLibraryInfo.h" 25#include "llvm/IR/Constant.h" 26#include "llvm/IR/InstIterator.h" 27#include "llvm/IR/Instruction.h" 28#include "llvm/InitializePasses.h" 29#include "llvm/Pass.h" 30#include "llvm/Support/DebugCounter.h" 31#include "llvm/Transforms/Scalar.h" 32#include "llvm/Transforms/Utils/Local.h" 33using namespace llvm; 34 35#define DEBUG_TYPE "constprop" 36 37STATISTIC(NumInstKilled, "Number of instructions killed"); 38DEBUG_COUNTER(CPCounter, "constprop-transform", 39 "Controls which instructions are killed"); 40 41namespace { 42 struct ConstantPropagation : public FunctionPass { 43 static char ID; // Pass identification, replacement for typeid 44 ConstantPropagation() : FunctionPass(ID) { 45 initializeConstantPropagationPass(*PassRegistry::getPassRegistry()); 46 } 47 48 bool runOnFunction(Function &F) override; 49 50 void getAnalysisUsage(AnalysisUsage &AU) const override { 51 AU.setPreservesCFG(); 52 AU.addRequired<TargetLibraryInfoWrapperPass>(); 53 } 54 }; 55} 56 57char ConstantPropagation::ID = 0; 58INITIALIZE_PASS_BEGIN(ConstantPropagation, "constprop", 59 "Simple constant propagation", false, false) 60INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 61INITIALIZE_PASS_END(ConstantPropagation, "constprop", 62 "Simple constant propagation", false, false) 63 64FunctionPass *llvm::createConstantPropagationPass() { 65 return new ConstantPropagation(); 66} 67 68bool ConstantPropagation::runOnFunction(Function &F) { 69 if (skipFunction(F)) 70 return false; 71 72 // Initialize the worklist to all of the instructions ready to process... 73 SmallPtrSet<Instruction *, 16> WorkList; 74 // The SmallVector of WorkList ensures that we do iteration at stable order. 75 // We use two containers rather than one SetVector, since remove is 76 // linear-time, and we don't care enough to remove from Vec. 77 SmallVector<Instruction *, 16> WorkListVec; 78 for (Instruction &I : instructions(&F)) { 79 WorkList.insert(&I); 80 WorkListVec.push_back(&I); 81 } 82 83 bool Changed = false; 84 const DataLayout &DL = F.getParent()->getDataLayout(); 85 TargetLibraryInfo *TLI = 86 &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); 87 88 while (!WorkList.empty()) { 89 SmallVector<Instruction*, 16> NewWorkListVec; 90 for (auto *I : WorkListVec) { 91 WorkList.erase(I); // Remove element from the worklist... 92 93 if (!I->use_empty()) // Don't muck with dead instructions... 94 if (Constant *C = ConstantFoldInstruction(I, DL, TLI)) { 95 if (!DebugCounter::shouldExecute(CPCounter)) 96 continue; 97 98 // Add all of the users of this instruction to the worklist, they might 99 // be constant propagatable now... 100 for (User *U : I->users()) { 101 // If user not in the set, then add it to the vector. 102 if (WorkList.insert(cast<Instruction>(U)).second) 103 NewWorkListVec.push_back(cast<Instruction>(U)); 104 } 105 106 // Replace all of the uses of a variable with uses of the constant. 107 I->replaceAllUsesWith(C); 108 109 if (isInstructionTriviallyDead(I, TLI)) { 110 I->eraseFromParent(); 111 ++NumInstKilled; 112 } 113 114 // We made a change to the function... 115 Changed = true; 116 } 117 } 118 WorkListVec = std::move(NewWorkListVec); 119 } 120 return Changed; 121} 122