Home | History | Annotate | Download | only in Scalar
      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 #define DEBUG_TYPE "constprop"
     22 #include "llvm/Transforms/Scalar.h"
     23 #include "llvm/Analysis/ConstantFolding.h"
     24 #include "llvm/Constant.h"
     25 #include "llvm/Instruction.h"
     26 #include "llvm/Pass.h"
     27 #include "llvm/Support/InstIterator.h"
     28 #include "llvm/ADT/Statistic.h"
     29 #include <set>
     30 using namespace llvm;
     31 
     32 STATISTIC(NumInstKilled, "Number of instructions killed");
     33 
     34 namespace {
     35   struct ConstantPropagation : public FunctionPass {
     36     static char ID; // Pass identification, replacement for typeid
     37     ConstantPropagation() : FunctionPass(ID) {
     38       initializeConstantPropagationPass(*PassRegistry::getPassRegistry());
     39     }
     40 
     41     bool runOnFunction(Function &F);
     42 
     43     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
     44       AU.setPreservesCFG();
     45     }
     46   };
     47 }
     48 
     49 char ConstantPropagation::ID = 0;
     50 INITIALIZE_PASS(ConstantPropagation, "constprop",
     51                 "Simple constant propagation", false, false)
     52 
     53 FunctionPass *llvm::createConstantPropagationPass() {
     54   return new ConstantPropagation();
     55 }
     56 
     57 
     58 bool ConstantPropagation::runOnFunction(Function &F) {
     59   // Initialize the worklist to all of the instructions ready to process...
     60   std::set<Instruction*> WorkList;
     61   for(inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) {
     62       WorkList.insert(&*i);
     63   }
     64   bool Changed = false;
     65 
     66   while (!WorkList.empty()) {
     67     Instruction *I = *WorkList.begin();
     68     WorkList.erase(WorkList.begin());    // Get an element from the worklist...
     69 
     70     if (!I->use_empty())                 // Don't muck with dead instructions...
     71       if (Constant *C = ConstantFoldInstruction(I)) {
     72         // Add all of the users of this instruction to the worklist, they might
     73         // be constant propagatable now...
     74         for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
     75              UI != UE; ++UI)
     76           WorkList.insert(cast<Instruction>(*UI));
     77 
     78         // Replace all of the uses of a variable with uses of the constant.
     79         I->replaceAllUsesWith(C);
     80 
     81         // Remove the dead instruction.
     82         WorkList.erase(I);
     83         I->eraseFromParent();
     84 
     85         // We made a change to the function...
     86         Changed = true;
     87         ++NumInstKilled;
     88       }
     89   }
     90   return Changed;
     91 }
     92