LLVM  9.0.0svn
ConstantProp.cpp
Go to the documentation of this file.
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"
25 #include "llvm/IR/Constant.h"
26 #include "llvm/IR/InstIterator.h"
27 #include "llvm/IR/Instruction.h"
28 #include "llvm/Pass.h"
30 #include "llvm/Transforms/Scalar.h"
32 using namespace llvm;
33 
34 #define DEBUG_TYPE "constprop"
35 
36 STATISTIC(NumInstKilled, "Number of instructions killed");
37 DEBUG_COUNTER(CPCounter, "constprop-transform",
38  "Controls which instructions are killed");
39 
40 namespace {
41  struct ConstantPropagation : public FunctionPass {
42  static char ID; // Pass identification, replacement for typeid
43  ConstantPropagation() : FunctionPass(ID) {
45  }
46 
47  bool runOnFunction(Function &F) override;
48 
49  void getAnalysisUsage(AnalysisUsage &AU) const override {
50  AU.setPreservesCFG();
52  }
53  };
54 }
55 
57 INITIALIZE_PASS_BEGIN(ConstantPropagation, "constprop",
58  "Simple constant propagation", false, false)
60 INITIALIZE_PASS_END(ConstantPropagation, "constprop",
61  "Simple constant propagation", false, false)
62 
64  return new ConstantPropagation();
65 }
66 
68  if (skipFunction(F))
69  return false;
70 
71  // Initialize the worklist to all of the instructions ready to process...
73  // The SmallVector of WorkList ensures that we do iteration at stable order.
74  // We use two containers rather than one SetVector, since remove is
75  // linear-time, and we don't care enough to remove from Vec.
77  for (Instruction &I : instructions(&F)) {
78  WorkList.insert(&I);
79  WorkListVec.push_back(&I);
80  }
81 
82  bool Changed = false;
83  const DataLayout &DL = F.getParent()->getDataLayout();
84  TargetLibraryInfo *TLI =
85  &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
86 
87  while (!WorkList.empty()) {
88  SmallVector<Instruction*, 16> NewWorkListVec;
89  for (auto *I : WorkListVec) {
90  WorkList.erase(I); // Remove element from the worklist...
91 
92  if (!I->use_empty()) // Don't muck with dead instructions...
93  if (Constant *C = ConstantFoldInstruction(I, DL, TLI)) {
94  if (!DebugCounter::shouldExecute(CPCounter))
95  continue;
96 
97  // Add all of the users of this instruction to the worklist, they might
98  // be constant propagatable now...
99  for (User *U : I->users()) {
100  // If user not in the set, then add it to the vector.
101  if (WorkList.insert(cast<Instruction>(U)).second)
102  NewWorkListVec.push_back(cast<Instruction>(U));
103  }
104 
105  // Replace all of the uses of a variable with uses of the constant.
106  I->replaceAllUsesWith(C);
107 
108  if (isInstructionTriviallyDead(I, TLI)) {
109  I->eraseFromParent();
110  ++NumInstKilled;
111  }
112 
113  // We made a change to the function...
114  Changed = true;
115  }
116  }
117  WorkListVec = std::move(NewWorkListVec);
118  }
119  return Changed;
120 }
uint64_t CallInst * C
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
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:23
void push_back(const T &Elt)
Definition: SmallVector.h:211
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:50
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
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:41
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
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:370
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:284
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:73
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:417
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false...
Definition: SmallPtrSet.h:377
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:301
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:575
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:353
inst_range instructions(Function *F)
Definition: InstIterator.h:133