lib/Transforms/Scalar/ConstantProp.cpp

   1 //===- ConstantProp.cpp - Code to perform Simple Constant Propogation -----===//
   2 //
   3 // This file implements constant propogation and merging:
   4 //
   5 // Specifically, this:
   6 //   * Converts instructions like "add int 1, 2" into 3
   7 //
   8 // Notice that:
   9 //   * This pass has a habit of making definitions be dead.  It is a good idea
  10 //     to to run a DIE pass sometime after running this pass.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Transforms/Scalar/ConstantProp.h"
  15 #include "llvm/ConstantHandling.h"
  16 #include "llvm/Function.h"
  17 #include "llvm/BasicBlock.h"
  18 #include "llvm/iTerminators.h"
  19 #include "llvm/Pass.h"
  20 #include "llvm/Support/InstIterator.h"
  21 #include <set>
  22
  23 // FIXME: ConstantFoldInstruction & ConstantFoldTerminator should be moved out
  24 // to the Transformations library.
  25
  26 // ConstantFoldInstruction - If an instruction references constants, try to fold
  27 // them together...
  28 //
  29 bool doConstantPropogation(BasicBlock *BB, BasicBlock::iterator &II) {
  30   Instruction *Inst = *II;
  31   if (Constant *C = ConstantFoldInstruction(Inst)) {
  32     // Replaces all of the uses of a variable with uses of the constant.
  33     Inst->replaceAllUsesWith(C);
  34
  35     // Remove the instruction from the basic block...
  36     delete BB->getInstList().remove(II);
  37     return true;
  38   }
  39
  40   return false;
  41 }
  42
  43 // ConstantFoldTerminator - If a terminator instruction is predicated on a
  44 // constant value, convert it into an unconditional branch to the constant
  45 // destination.
  46 //
  47 bool ConstantFoldTerminator(BasicBlock *BB, BasicBlock::iterator &II,
  48                             TerminatorInst *T) {
  49   // Branch - See if we are conditional jumping on constant
  50   if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
  51     if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
  52     BasicBlock *Dest1 = cast<BasicBlock>(BI->getOperand(0));
  53     BasicBlock *Dest2 = cast<BasicBlock>(BI->getOperand(1));
  54
  55     if (ConstantBool *Cond = dyn_cast<ConstantBool>(BI->getCondition())) {
  56       // Are we branching on constant?
  57       // YES.  Change to unconditional branch...
  58       BasicBlock *Destination = Cond->getValue() ? Dest1 : Dest2;
  59       BasicBlock *OldDest     = Cond->getValue() ? Dest2 : Dest1;
  60
  61       //cerr << "Function: " << T->getParent()->getParent()
  62       //     << "\nRemoving branch from " << T->getParent()
  63       //     << "\n\nTo: " << OldDest << endl;
  64
  65       // Let the basic block know that we are letting go of it.  Based on this,
  66       // it will adjust it's PHI nodes.
  67       assert(BI->getParent() && "Terminator not inserted in block!");
  68       OldDest->removePredecessor(BI->getParent());
  69
  70       // Set the unconditional destination, and change the insn to be an
  71       // unconditional branch.
  72       BI->setUnconditionalDest(Destination);
  73       II = BB->end()-1;  // Update instruction iterator!
  74       return true;
  75     }
  76 #if 0
  77     // FIXME: TODO: This doesn't work if the destination has PHI nodes with
  78     // different incoming values on each branch!
  79     //
  80     else if (Dest2 == Dest1) {       // Conditional branch to same location?
  81       // This branch matches something like this:
  82       //     br bool %cond, label %Dest, label %Dest
  83       // and changes it into:  br label %Dest
  84
  85       // Let the basic block know that we are letting go of one copy of it.
  86       assert(BI->getParent() && "Terminator not inserted in block!");
  87       Dest1->removePredecessor(BI->getParent());
  88
  89       // Change a conditional branch to unconditional.
  90       BI->setUnconditionalDest(Dest1);
  91       return true;
  92     }
  93 #endif
  94   }
  95   return false;
  96 }
  97
  98
  99
 100 namespace {
 101   struct ConstantPropogation : public FunctionPass {
 102     const char *getPassName() const { return "Simple Constant Propogation"; }
 103
 104     inline bool runOnFunction(Function *F);
 105
 106     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 107       AU.preservesCFG();
 108     }
 109   };
 110 }
 111
 112 Pass *createConstantPropogationPass() {
 113   return new ConstantPropogation();
 114 }
 115
 116
 117 bool ConstantPropogation::runOnFunction(Function *F) {
 118   // Initialize the worklist to all of the instructions ready to process...
 119   std::set<Instruction*> WorkList(inst_begin(F), inst_end(F));
 120   bool Changed = false;
 121
 122   while (!WorkList.empty()) {
 123     Instruction *I = *WorkList.begin();
 124     WorkList.erase(WorkList.begin());    // Get an element from the worklist...
 125
 126     if (!I->use_empty())                 // Don't muck with dead instructions...
 127       if (Constant *C = ConstantFoldInstruction(I)) {
 128         // Add all of the users of this instruction to the worklist, they might
 129         // be constant propogatable now...
 130         for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
 131              UI != UE; ++UI)
 132           WorkList.insert(cast<Instruction>(*UI));
 133
 134         // Replace all of the uses of a variable with uses of the constant.
 135         I->replaceAllUsesWith(C);
 136
 137         // We made a change to the function...
 138         Changed = true;
 139       }
 140   }
 141   return Changed;
 142 }