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"
24 #include "llvm/Analysis/ConstantFolding.h"
25 #include "llvm/Analysis/TargetLibraryInfo.h"
26 #include "llvm/IR/Constant.h"
27 #include "llvm/IR/InstIterator.h"
28 #include "llvm/IR/Instruction.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"
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) {
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 
57 char ConstantPropagation::ID = 0;
58 INITIALIZE_PASS_BEGIN(ConstantPropagation, "constprop",
59                 "Simple constant propagation", false, false)
60 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
61 INITIALIZE_PASS_END(ConstantPropagation, "constprop",
62                 "Simple constant propagation", false, false)
63 
64 FunctionPass *llvm::createConstantPropagationPass() {
65   return new ConstantPropagation();
66 }
67 
68 bool 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();
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