lib/Transforms/Scalar/SCCP.cpp

   1 //===- SCCP.cpp - Sparse Conditional Constant Propogation -----------------===//
   2 //
   3 // This file implements sparse conditional constant propogation and merging:
   4 //
   5 // Specifically, this:
   6 //   * Assumes values are constant unless proven otherwise
   7 //   * Assumes BasicBlocks are dead unless proven otherwise
   8 //   * Proves values to be constant, and replaces them with constants
   9 //   * Proves conditional branches constant, and unconditionalizes them
  10 //   * Folds multiple identical constants in the constant pool together
  11 //
  12 // Notice that:
  13 //   * This pass has a habit of making definitions be dead.  It is a good idea
  14 //     to to run a DCE pass sometime after running this pass.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "llvm/Transforms/Scalar.h"
  19 #include "llvm/ConstantHandling.h"
  20 #include "llvm/Function.h"
  21 #include "llvm/BasicBlock.h"
  22 #include "llvm/iPHINode.h"
  23 #include "llvm/iMemory.h"
  24 #include "llvm/iTerminators.h"
  25 #include "llvm/iOther.h"
  26 #include "llvm/Pass.h"
  27 #include "llvm/Support/InstVisitor.h"
  28 #include "Support/STLExtras.h"
  29 #include "Support/StatisticReporter.h"
  30 #include <algorithm>
  31 #include <set>
  32 #include <iostream>
  33 using std::cerr;
  34
  35 static Statistic<> NumInstRemoved("sccp\t\t- Number of instructions removed");
  36
  37 // InstVal class - This class represents the different lattice values that an
  38 // instruction may occupy.  It is a simple class with value semantics.
  39 //
  40 namespace {
  41 class InstVal {
  42   enum {
  43     undefined,           // This instruction has no known value
  44     constant,            // This instruction has a constant value
  45     // Range,            // This instruction is known to fall within a range
  46     overdefined          // This instruction has an unknown value
  47   } LatticeValue;        // The current lattice position
  48   Constant *ConstantVal; // If Constant value, the current value
  49 public:
  50   inline InstVal() : LatticeValue(undefined), ConstantVal(0) {}
  51
  52   // markOverdefined - Return true if this is a new status to be in...
  53   inline bool markOverdefined() {
  54     if (LatticeValue != overdefined) {
  55       LatticeValue = overdefined;
  56       return true;
  57     }
  58     return false;
  59   }
  60
  61   // markConstant - Return true if this is a new status for us...
  62   inline bool markConstant(Constant *V) {
  63     if (LatticeValue != constant) {
  64       LatticeValue = constant;
  65       ConstantVal = V;
  66       return true;
  67     } else {
  68       assert(ConstantVal == V && "Marking constant with different value");
  69     }
  70     return false;
  71   }
  72
  73   inline bool isUndefined()   const { return LatticeValue == undefined; }
  74   inline bool isConstant()    const { return LatticeValue == constant; }
  75   inline bool isOverdefined() const { return LatticeValue == overdefined; }
  76
  77   inline Constant *getConstant() const { return ConstantVal; }
  78 };
  79
  80 } // end anonymous namespace
  81
  82
  83 //===----------------------------------------------------------------------===//
  84 // SCCP Class
  85 //
  86 // This class does all of the work of Sparse Conditional Constant Propogation.
  87 //
  88 namespace {
  89 class SCCP : public FunctionPass, public InstVisitor<SCCP> {
  90   std::set<BasicBlock*>     BBExecutable;// The basic blocks that are executable
  91   std::map<Value*, InstVal> ValueState;  // The state each value is in...
  92
  93   std::vector<Instruction*> InstWorkList;// The instruction work list
  94   std::vector<BasicBlock*>  BBWorkList;  // The BasicBlock work list
  95 public:
  96
  97   const char *getPassName() const {
  98     return "Sparse Conditional Constant Propogation";
  99   }
 100
 101   // runOnFunction - Run the Sparse Conditional Constant Propogation algorithm,
 102   // and return true if the function was modified.
 103   //
 104   bool runOnFunction(Function *F);
 105
 106   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 107     AU.preservesCFG();
 108   }
 109
 110
 111   //===--------------------------------------------------------------------===//
 112   // The implementation of this class
 113   //
 114 private:
 115   friend class InstVisitor<SCCP>;        // Allow callbacks from visitor
 116
 117   // markValueOverdefined - Make a value be marked as "constant".  If the value
 118   // is not already a constant, add it to the instruction work list so that
 119   // the users of the instruction are updated later.
 120   //
 121   inline bool markConstant(Instruction *I, Constant *V) {
 122     DEBUG(cerr << "markConstant: " << V << " = " << I);
 123
 124     if (ValueState[I].markConstant(V)) {
 125       InstWorkList.push_back(I);
 126       return true;
 127     }
 128     return false;
 129   }
 130
 131   // markValueOverdefined - Make a value be marked as "overdefined". If the
 132   // value is not already overdefined, add it to the instruction work list so
 133   // that the users of the instruction are updated later.
 134   //
 135   inline bool markOverdefined(Value *V) {
 136     if (ValueState[V].markOverdefined()) {
 137       if (Instruction *I = dyn_cast<Instruction>(V)) {
 138         DEBUG(cerr << "markOverdefined: " << V);
 139         InstWorkList.push_back(I);  // Only instructions go on the work list
 140       }
 141       return true;
 142     }
 143     return false;
 144   }
 145
 146   // getValueState - Return the InstVal object that corresponds to the value.
 147   // This function is neccesary because not all values should start out in the
 148   // underdefined state... Argument's should be overdefined, and
 149   // constants should be marked as constants.  If a value is not known to be an
 150   // Instruction object, then use this accessor to get its value from the map.
 151   //
 152   inline InstVal &getValueState(Value *V) {
 153     std::map<Value*, InstVal>::iterator I = ValueState.find(V);
 154     if (I != ValueState.end()) return I->second;  // Common case, in the map
 155
 156     if (Constant *CPV = dyn_cast<Constant>(V)) {  // Constants are constant
 157       ValueState[CPV].markConstant(CPV);
 158     } else if (isa<Argument>(V)) {                // Arguments are overdefined
 159       ValueState[V].markOverdefined();
 160     }
 161     // All others are underdefined by default...
 162     return ValueState[V];
 163   }
 164
 165   // markExecutable - Mark a basic block as executable, adding it to the BB
 166   // work list if it is not already executable...
 167   //
 168   void markExecutable(BasicBlock *BB) {
 169     if (BBExecutable.count(BB)) return;
 170     DEBUG(cerr << "Marking BB Executable: " << BB);
 171     BBExecutable.insert(BB);   // Basic block is executable!
 172     BBWorkList.push_back(BB);  // Add the block to the work list!
 173   }
 174
 175
 176   // visit implementations - Something changed in this instruction... Either an
 177   // operand made a transition, or the instruction is newly executable.  Change
 178   // the value type of I to reflect these changes if appropriate.
 179   //
 180   void visitPHINode(PHINode *I);
 181
 182   // Terminators
 183   void visitReturnInst(ReturnInst *I) { /*does not have an effect*/ }
 184   void visitTerminatorInst(TerminatorInst *TI);
 185
 186   void visitUnaryOperator(Instruction *I);
 187   void visitCastInst(CastInst *I) { visitUnaryOperator(I); }
 188   void visitBinaryOperator(Instruction *I);
 189   void visitShiftInst(ShiftInst *I) { visitBinaryOperator(I); }
 190
 191   // Instructions that cannot be folded away...
 192   void visitStoreInst     (Instruction *I) { /*returns void*/ }
 193   void visitMemAccessInst (Instruction *I) { markOverdefined(I); }
 194   void visitCallInst      (Instruction *I) { markOverdefined(I); }
 195   void visitInvokeInst    (Instruction *I) { markOverdefined(I); }
 196   void visitAllocationInst(Instruction *I) { markOverdefined(I); }
 197   void visitFreeInst      (Instruction *I) { /*returns void*/ }
 198
 199   void visitInstruction(Instruction *I) {
 200     // If a new instruction is added to LLVM that we don't handle...
 201     cerr << "SCCP: Don't know how to handle: " << I;
 202     markOverdefined(I);   // Just in case
 203   }
 204
 205   // getFeasibleSuccessors - Return a vector of booleans to indicate which
 206   // successors are reachable from a given terminator instruction.
 207   //
 208   void getFeasibleSuccessors(TerminatorInst *I, std::vector<bool> &Succs);
 209
 210   // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
 211   // block to the 'To' basic block is currently feasible...
 212   //
 213   bool isEdgeFeasible(BasicBlock *From, BasicBlock *To);
 214
 215   // OperandChangedState - This method is invoked on all of the users of an
 216   // instruction that was just changed state somehow....  Based on this
 217   // information, we need to update the specified user of this instruction.
 218   //
 219   void OperandChangedState(User *U) {
 220     // Only instructions use other variable values!
 221     Instruction *I = cast<Instruction>(U);
 222     if (!BBExecutable.count(I->getParent())) return;// Inst not executable yet!
 223     visit(I);
 224   }
 225 };
 226 } // end anonymous namespace
 227
 228
 229 // createSCCPPass - This is the public interface to this file...
 230 //
 231 Pass *createSCCPPass() {
 232   return new SCCP();
 233 }
 234
 235
 236
 237 //===----------------------------------------------------------------------===//
 238 // SCCP Class Implementation
 239
 240
 241 // runOnFunction() - Run the Sparse Conditional Constant Propogation algorithm,
 242 // and return true if the function was modified.
 243 //
 244 bool SCCP::runOnFunction(Function *F) {
 245   // Mark the first block of the function as being executable...
 246   markExecutable(F->front());
 247
 248   // Process the work lists until their are empty!
 249   while (!BBWorkList.empty() || !InstWorkList.empty()) {
 250     // Process the instruction work list...
 251     while (!InstWorkList.empty()) {
 252       Instruction *I = InstWorkList.back();
 253       InstWorkList.pop_back();
 254
 255       DEBUG(cerr << "\nPopped off I-WL: " << I);
 256
 257
 258       // "I" got into the work list because it either made the transition from
 259       // bottom to constant, or to Overdefined.
 260       //
 261       // Update all of the users of this instruction's value...
 262       //
 263       for_each(I->use_begin(), I->use_end(),
 264                bind_obj(this, &SCCP::OperandChangedState));
 265     }
 266
 267     // Process the basic block work list...
 268     while (!BBWorkList.empty()) {
 269       BasicBlock *BB = BBWorkList.back();
 270       BBWorkList.pop_back();
 271
 272       DEBUG(cerr << "\nPopped off BBWL: " << BB);
 273
 274       // If this block only has a single successor, mark it as executable as
 275       // well... if not, terminate the do loop.
 276       //
 277       if (BB->getTerminator()->getNumSuccessors() == 1)
 278         markExecutable(BB->getTerminator()->getSuccessor(0));
 279
 280       // Notify all instructions in this basic block that they are newly
 281       // executable.
 282       visit(BB);
 283     }
 284   }
 285
 286   if (DebugFlag) {
 287     for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
 288       if (!BBExecutable.count(*I))
 289         cerr << "BasicBlock Dead:" << *I;
 290   }
 291
 292   // Iterate over all of the instructions in a function, replacing them with
 293   // constants if we have found them to be of constant values.
 294   //
 295   bool MadeChanges = false;
 296   for (Function::iterator FI = F->begin(), FE = F->end(); FI != FE; ++FI) {
 297     BasicBlock *BB = *FI;
 298     for (BasicBlock::iterator BI = BB->begin(); BI != BB->end();) {
 299       Instruction *Inst = *BI;
 300       InstVal &IV = ValueState[Inst];
 301       if (IV.isConstant()) {
 302         Constant *Const = IV.getConstant();
 303         DEBUG(cerr << "Constant: " << Const << " = " << Inst);
 304
 305         // Replaces all of the uses of a variable with uses of the constant.
 306         Inst->replaceAllUsesWith(Const);
 307
 308         // Remove the operator from the list of definitions... and delete it.
 309         delete BB->getInstList().remove(BI);
 310
 311         // Hey, we just changed something!
 312         MadeChanges = true;
 313         ++NumInstRemoved;
 314       } else {
 315         ++BI;
 316       }
 317     }
 318   }
 319
 320   // Reset state so that the next invocation will have empty data structures
 321   BBExecutable.clear();
 322   ValueState.clear();
 323
 324   return MadeChanges;
 325 }
 326
 327
 328 // getFeasibleSuccessors - Return a vector of booleans to indicate which
 329 // successors are reachable from a given terminator instruction.
 330 //
 331 void SCCP::getFeasibleSuccessors(TerminatorInst *TI, std::vector<bool> &Succs) {
 332   assert(Succs.size() == TI->getNumSuccessors() && "Succs vector wrong size!");
 333   if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
 334     if (BI->isUnconditional()) {
 335       Succs[0] = true;
 336     } else {
 337       InstVal &BCValue = getValueState(BI->getCondition());
 338       if (BCValue.isOverdefined()) {
 339         // Overdefined condition variables mean the branch could go either way.
 340         Succs[0] = Succs[1] = true;
 341       } else if (BCValue.isConstant()) {
 342         // Constant condition variables mean the branch can only go a single way
 343         Succs[BCValue.getConstant() == ConstantBool::False] = true;
 344       }
 345     }
 346   } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) {
 347     // Invoke instructions successors are always executable.
 348     Succs[0] = Succs[1] = true;
 349   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
 350     InstVal &SCValue = getValueState(SI->getCondition());
 351     if (SCValue.isOverdefined()) {  // Overdefined condition?
 352       // All destinations are executable!
 353       Succs.assign(TI->getNumSuccessors(), true);
 354     } else if (SCValue.isConstant()) {
 355       Constant *CPV = SCValue.getConstant();
 356       // Make sure to skip the "default value" which isn't a value
 357       for (unsigned i = 1, E = SI->getNumSuccessors(); i != E; ++i) {
 358         if (SI->getSuccessorValue(i) == CPV) {// Found the right branch...
 359           Succs[i] = true;
 360           return;
 361         }
 362       }
 363
 364       // Constant value not equal to any of the branches... must execute
 365       // default branch then...
 366       Succs[0] = true;
 367     }
 368   } else {
 369     cerr << "SCCP: Don't know how to handle: " << TI;
 370     Succs.assign(TI->getNumSuccessors(), true);
 371   }
 372 }
 373
 374
 375 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
 376 // block to the 'To' basic block is currently feasible...
 377 //
 378 bool SCCP::isEdgeFeasible(BasicBlock *From, BasicBlock *To) {
 379   assert(BBExecutable.count(To) && "Dest should always be alive!");
 380
 381   // Make sure the source basic block is executable!!
 382   if (!BBExecutable.count(From)) return false;
 383
 384   // Check to make sure this edge itself is actually feasible now...
 385   TerminatorInst *FT = From->getTerminator();
 386   std::vector<bool> SuccFeasible(FT->getNumSuccessors());
 387   getFeasibleSuccessors(FT, SuccFeasible);
 388
 389   // Check all edges from From to To.  If any are feasible, return true.
 390   for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
 391     if (FT->getSuccessor(i) == To && SuccFeasible[i])
 392       return true;
 393
 394   // Otherwise, none of the edges are actually feasible at this time...
 395   return false;
 396 }
 397
 398 // visit Implementations - Something changed in this instruction... Either an
 399 // operand made a transition, or the instruction is newly executable.  Change
 400 // the value type of I to reflect these changes if appropriate.  This method
 401 // makes sure to do the following actions:
 402 //
 403 // 1. If a phi node merges two constants in, and has conflicting value coming
 404 //    from different branches, or if the PHI node merges in an overdefined
 405 //    value, then the PHI node becomes overdefined.
 406 // 2. If a phi node merges only constants in, and they all agree on value, the
 407 //    PHI node becomes a constant value equal to that.
 408 // 3. If V <- x (op) y && isConstant(x) && isConstant(y) V = Constant
 409 // 4. If V <- x (op) y && (isOverdefined(x) || isOverdefined(y)) V = Overdefined
 410 // 5. If V <- MEM or V <- CALL or V <- (unknown) then V = Overdefined
 411 // 6. If a conditional branch has a value that is constant, make the selected
 412 //    destination executable
 413 // 7. If a conditional branch has a value that is overdefined, make all
 414 //    successors executable.
 415 //
 416
 417 void SCCP::visitPHINode(PHINode *PN) {
 418   unsigned NumValues = PN->getNumIncomingValues(), i;
 419   InstVal *OperandIV = 0;
 420
 421   // Look at all of the executable operands of the PHI node.  If any of them
 422   // are overdefined, the PHI becomes overdefined as well.  If they are all
 423   // constant, and they agree with each other, the PHI becomes the identical
 424   // constant.  If they are constant and don't agree, the PHI is overdefined.
 425   // If there are no executable operands, the PHI remains undefined.
 426   //
 427   for (i = 0; i < NumValues; ++i) {
 428     if (isEdgeFeasible(PN->getIncomingBlock(i), PN->getParent())) {
 429       InstVal &IV = getValueState(PN->getIncomingValue(i));
 430       if (IV.isUndefined()) continue;  // Doesn't influence PHI node.
 431       if (IV.isOverdefined()) {   // PHI node becomes overdefined!
 432         markOverdefined(PN);
 433         return;
 434       }
 435
 436       if (OperandIV == 0) {   // Grab the first value...
 437         OperandIV = &IV;
 438       } else {                // Another value is being merged in!
 439         // There is already a reachable operand.  If we conflict with it,
 440         // then the PHI node becomes overdefined.  If we agree with it, we
 441         // can continue on.
 442
 443         // Check to see if there are two different constants merging...
 444         if (IV.getConstant() != OperandIV->getConstant()) {
 445           // Yes there is.  This means the PHI node is not constant.
 446           // You must be overdefined poor PHI.
 447           //
 448           markOverdefined(PN);         // The PHI node now becomes overdefined
 449           return;    // I'm done analyzing you
 450         }
 451       }
 452     }
 453   }
 454
 455   // If we exited the loop, this means that the PHI node only has constant
 456   // arguments that agree with each other(and OperandIV is a pointer to one
 457   // of their InstVal's) or OperandIV is null because there are no defined
 458   // incoming arguments.  If this is the case, the PHI remains undefined.
 459   //
 460   if (OperandIV) {
 461     assert(OperandIV->isConstant() && "Should only be here for constants!");
 462     markConstant(PN, OperandIV->getConstant());  // Aquire operand value
 463   }
 464 }
 465
 466 void SCCP::visitTerminatorInst(TerminatorInst *TI) {
 467   std::vector<bool> SuccFeasible(TI->getNumSuccessors());
 468   getFeasibleSuccessors(TI, SuccFeasible);
 469
 470   // Mark all feasible successors executable...
 471   for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
 472     if (SuccFeasible[i]) {
 473       BasicBlock *Succ = TI->getSuccessor(i);
 474       markExecutable(Succ);
 475
 476       // Visit all of the PHI nodes that merge values from this block...
 477       // Because this edge may be new executable, and PHI nodes that used to be
 478       // constant now may not be.
 479       //
 480       for (BasicBlock::iterator I = Succ->begin();
 481            PHINode *PN = dyn_cast<PHINode>(*I); ++I)
 482         visitPHINode(PN);
 483     }
 484 }
 485
 486 void SCCP::visitUnaryOperator(Instruction *I) {
 487   Value *V = I->getOperand(0);
 488   InstVal &VState = getValueState(V);
 489   if (VState.isOverdefined()) {        // Inherit overdefinedness of operand
 490     markOverdefined(I);
 491   } else if (VState.isConstant()) {    // Propogate constant value
 492     Constant *Result = isa<CastInst>(I)
 493       ? ConstantFoldCastInstruction(VState.getConstant(), I->getType())
 494       : ConstantFoldUnaryInstruction(I->getOpcode(), VState.getConstant());
 495
 496     if (Result) {
 497       // This instruction constant folds!
 498       markConstant(I, Result);
 499     } else {
 500       markOverdefined(I);   // Don't know how to fold this instruction.  :(
 501     }
 502   }
 503 }
 504
 505 // Handle BinaryOperators and Shift Instructions...
 506 void SCCP::visitBinaryOperator(Instruction *I) {
 507   InstVal &V1State = getValueState(I->getOperand(0));
 508   InstVal &V2State = getValueState(I->getOperand(1));
 509   if (V1State.isOverdefined() || V2State.isOverdefined()) {
 510     markOverdefined(I);
 511   } else if (V1State.isConstant() && V2State.isConstant()) {
 512     Constant *Result = 0;
 513     if (isa<BinaryOperator>(I))
 514       Result = ConstantFoldBinaryInstruction(I->getOpcode(),
 515                                              V1State.getConstant(),
 516                                              V2State.getConstant());
 517     else if (isa<ShiftInst>(I))
 518       Result = ConstantFoldShiftInstruction(I->getOpcode(),
 519                                             V1State.getConstant(),
 520                                             V2State.getConstant());
 521     if (Result)
 522       markConstant(I, Result);      // This instruction constant folds!
 523     else
 524       markOverdefined(I);   // Don't know how to fold this instruction.  :(
 525   }
 526 }