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