LLVM  8.0.0svn
ConstantProp.cpp
Go to the documentation of this file.
1 //===- ConstantProp.cpp - Code to perform Simple Constant Propagation -----===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements constant propagation and merging:
11 //
12 // Specifically, this:
13 // * Converts instructions like "add int 1, 2" into 3
14 //
15 // Notice that:
16 // * This pass has a habit of making definitions be dead. It is a good idea
17 // to run a DIE pass sometime after running this pass.
18 //
19 //===----------------------------------------------------------------------===//
20 
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/Statistic.h"
26 #include "llvm/IR/Constant.h"
27 #include "llvm/IR/InstIterator.h"
28 #include "llvm/IR/Instruction.h"
29 #include "llvm/Pass.h"
31 #include "llvm/Transforms/Scalar.h"
33 using namespace llvm;
34 
35 #define DEBUG_TYPE "constprop"
36 
37 STATISTIC(NumInstKilled, "Number of instructions killed");
38 DEBUG_COUNTER(CPCounter, "constprop-transform",
39  "Controls which instructions are killed");
40 
41 namespace {
42  struct ConstantPropagation : public FunctionPass {
43  static char ID; // Pass identification, replacement for typeid
44  ConstantPropagation() : FunctionPass(ID) {
46  }
47 
48  bool runOnFunction(Function &F) override;
49 
50  void getAnalysisUsage(AnalysisUsage &AU) const override {
51  AU.setPreservesCFG();
53  }
54  };
55 }
56 
58 INITIALIZE_PASS_BEGIN(ConstantPropagation, "constprop",
59  "Simple constant propagation", false, false)
61 INITIALIZE_PASS_END(ConstantPropagation, "constprop",
62  "Simple constant propagation", false, false)
63 
65  return new ConstantPropagation();
66 }
67 
69  if (skipFunction(F))
70  return false;
71 
72  // Initialize the worklist to all of the instructions ready to process...
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.
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();
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 }
uint64_t CallInst * C
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents lattice values for constants.
Definition: AllocatorList.h:24
DEBUG_COUNTER(CPCounter, "constprop-transform", "Controls which instructions are killed")
STATISTIC(NumFunctions, "Total number of functions")
F(f)
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:365
FunctionPass * createConstantPropagationPass()
This file provides an implementation of debug counters.
void initializeConstantPropagationPass(PassRegistry &)
static bool runOnFunction(Function &F, bool PostInlining)
This is an important base class in LLVM.
Definition: Constant.h:42
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:92
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
Constant * ConstantFoldInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstruction - Try to constant fold the specified instruction.
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false...
Definition: SmallPtrSet.h:378
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Provides information about what library functions are available for the current target.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:286
INITIALIZE_PASS_BEGIN(ConstantPropagation, "constprop", "Simple constant propagation", false, false) INITIALIZE_PASS_END(ConstantPropagation
Simple constant propagation
#define I(x, y, z)
Definition: MD5.cpp:58
constprop
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:566
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:348
inst_range instructions(Function *F)
Definition: InstIterator.h:134