lib/Transforms/Scalar/CondPropagate.cpp

   1 //===-- CondPropagate.cpp - Propagate Conditional Expressions -------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass propagates information about conditional expressions through the
  11 // program, allowing it to eliminate conditional branches in some cases.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "condprop"
  16 #include "llvm/Transforms/Scalar.h"
  17 #include "llvm/Transforms/Utils/Local.h"
  18 #include "llvm/Constants.h"
  19 #include "llvm/Function.h"
  20 #include "llvm/Instructions.h"
  21 #include "llvm/Pass.h"
  22 #include "llvm/Type.h"
  23 #include "llvm/ADT/STLExtras.h"
  24 #include "llvm/ADT/Statistic.h"
  25 #include "llvm/Support/Streams.h"
  26 using namespace llvm;
  27
  28 STATISTIC(NumBrThread, "Number of CFG edges threaded through branches");
  29 STATISTIC(NumSwThread, "Number of CFG edges threaded through switches");
  30
  31 namespace {
  32   struct CondProp : public FunctionPass {
  33     virtual bool runOnFunction(Function &F);
  34
  35     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  36       AU.addRequiredID(BreakCriticalEdgesID);
  37       //AU.addRequired<DominanceFrontier>();
  38     }
  39
  40   private:
  41     bool MadeChange;
  42     void SimplifyBlock(BasicBlock *BB);
  43     void SimplifyPredecessors(BranchInst *BI);
  44     void SimplifyPredecessors(SwitchInst *SI);
  45     void RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB);
  46   };
  47   RegisterPass<CondProp> X("condprop", "Conditional Propagation");
  48 }
  49
  50 FunctionPass *llvm::createCondPropagationPass() {
  51   return new CondProp();
  52 }
  53
  54 bool CondProp::runOnFunction(Function &F) {
  55   bool EverMadeChange = false;
  56
  57   // While we are simplifying blocks, keep iterating.
  58   do {
  59     MadeChange = false;
  60     for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
  61       SimplifyBlock(BB);
  62     EverMadeChange = MadeChange;
  63   } while (MadeChange);
  64   return EverMadeChange;
  65 }
  66
  67 void CondProp::SimplifyBlock(BasicBlock *BB) {
  68   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
  69     // If this is a conditional branch based on a phi node that is defined in
  70     // this block, see if we can simplify predecessors of this block.
  71     if (BI->isConditional() && isa<PHINode>(BI->getCondition()) &&
  72         cast<PHINode>(BI->getCondition())->getParent() == BB)
  73       SimplifyPredecessors(BI);
  74
  75   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
  76     if (isa<PHINode>(SI->getCondition()) &&
  77         cast<PHINode>(SI->getCondition())->getParent() == BB)
  78       SimplifyPredecessors(SI);
  79   }
  80
  81   // If possible, simplify the terminator of this block.
  82   if (ConstantFoldTerminator(BB))
  83     MadeChange = true;
  84
  85   // If this block ends with an unconditional branch and the only successor has
  86   // only this block as a predecessor, merge the two blocks together.
  87   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()))
  88     if (BI->isUnconditional() && BI->getSuccessor(0)->getSinglePredecessor() &&
  89         BB != BI->getSuccessor(0)) {
  90       BasicBlock *Succ = BI->getSuccessor(0);
  91
  92       // If Succ has any PHI nodes, they are all single-entry PHI's.
  93       while (PHINode *PN = dyn_cast<PHINode>(Succ->begin())) {
  94         assert(PN->getNumIncomingValues() == 1 &&
  95                "PHI doesn't match parent block");
  96         PN->replaceAllUsesWith(PN->getIncomingValue(0));
  97         PN->eraseFromParent();
  98       }
  99
 100       // Remove BI.
 101       BI->eraseFromParent();
 102
 103       // Move over all of the instructions.
 104       BB->getInstList().splice(BB->end(), Succ->getInstList());
 105
 106       // Any phi nodes that had entries for Succ now have entries from BB.
 107       Succ->replaceAllUsesWith(BB);
 108
 109       // Succ is now dead, but we cannot delete it without potentially
 110       // invalidating iterators elsewhere.  Just insert an unreachable
 111       // instruction in it.
 112       new UnreachableInst(Succ);
 113       MadeChange = true;
 114     }
 115 }
 116
 117 // SimplifyPredecessors(branches) - We know that BI is a conditional branch
 118 // based on a PHI node defined in this block.  If the phi node contains constant
 119 // operands, then the blocks corresponding to those operands can be modified to
 120 // jump directly to the destination instead of going through this block.
 121 void CondProp::SimplifyPredecessors(BranchInst *BI) {
 122   // TODO: We currently only handle the most trival case, where the PHI node has
 123   // one use (the branch), and is the only instruction besides the branch in the
 124   // block.
 125   PHINode *PN = cast<PHINode>(BI->getCondition());
 126   if (!PN->hasOneUse()) return;
 127
 128   BasicBlock *BB = BI->getParent();
 129   if (&*BB->begin() != PN || &*next(BB->begin()) != BI)
 130     return;
 131
 132   // Ok, we have this really simple case, walk the PHI operands, looking for
 133   // constants.  Walk from the end to remove operands from the end when
 134   // possible, and to avoid invalidating "i".
 135   for (unsigned i = PN->getNumIncomingValues(); i != 0; --i)
 136     if (ConstantInt *CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i-1))) {
 137       if (CB->getType() != Type::Int1Ty) continue;
 138       // If we have a constant, forward the edge from its current to its
 139       // ultimate destination.
 140       bool PHIGone = PN->getNumIncomingValues() == 2;
 141       RevectorBlockTo(PN->getIncomingBlock(i-1),
 142                       BI->getSuccessor(CB->getZExtValue() == 0));
 143       ++NumBrThread;
 144
 145       // If there were two predecessors before this simplification, the PHI node
 146       // will be deleted.  Don't iterate through it the last time.
 147       if (PHIGone) return;
 148     }
 149 }
 150
 151 // SimplifyPredecessors(switch) - We know that SI is switch based on a PHI node
 152 // defined in this block.  If the phi node contains constant operands, then the
 153 // blocks corresponding to those operands can be modified to jump directly to
 154 // the destination instead of going through this block.
 155 void CondProp::SimplifyPredecessors(SwitchInst *SI) {
 156   // TODO: We currently only handle the most trival case, where the PHI node has
 157   // one use (the branch), and is the only instruction besides the branch in the
 158   // block.
 159   PHINode *PN = cast<PHINode>(SI->getCondition());
 160   if (!PN->hasOneUse()) return;
 161
 162   BasicBlock *BB = SI->getParent();
 163   if (&*BB->begin() != PN || &*next(BB->begin()) != SI)
 164     return;
 165
 166   bool RemovedPreds = false;
 167
 168   // Ok, we have this really simple case, walk the PHI operands, looking for
 169   // constants.  Walk from the end to remove operands from the end when
 170   // possible, and to avoid invalidating "i".
 171   for (unsigned i = PN->getNumIncomingValues(); i != 0; --i)
 172     if (ConstantInt *CI = dyn_cast<ConstantInt>(PN->getIncomingValue(i-1))) {
 173       // If we have a constant, forward the edge from its current to its
 174       // ultimate destination.
 175       bool PHIGone = PN->getNumIncomingValues() == 2;
 176       unsigned DestCase = SI->findCaseValue(CI);
 177       RevectorBlockTo(PN->getIncomingBlock(i-1),
 178                       SI->getSuccessor(DestCase));
 179       ++NumSwThread;
 180       RemovedPreds = true;
 181
 182       // If there were two predecessors before this simplification, the PHI node
 183       // will be deleted.  Don't iterate through it the last time.
 184       if (PHIGone) return;
 185     }
 186 }
 187
 188
 189 // RevectorBlockTo - Revector the unconditional branch at the end of FromBB to
 190 // the ToBB block, which is one of the successors of its current successor.
 191 void CondProp::RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB) {
 192   BranchInst *FromBr = cast<BranchInst>(FromBB->getTerminator());
 193   assert(FromBr->isUnconditional() && "FromBB should end with uncond br!");
 194
 195   // Get the old block we are threading through.
 196   BasicBlock *OldSucc = FromBr->getSuccessor(0);
 197
 198   // OldSucc had multiple successors. If ToBB has multiple predecessors, then
 199   // the edge between them would be critical, which we already took care of.
 200   // If ToBB has single operand PHI node then take care of it here.
 201   while (PHINode *PN = dyn_cast<PHINode>(ToBB->begin())) {
 202     assert(PN->getNumIncomingValues() == 1 && "Critical Edge Found!");
 203     PN->replaceAllUsesWith(PN->getIncomingValue(0));
 204     PN->eraseFromParent();
 205   }
 206
 207   // Update PHI nodes in OldSucc to know that FromBB no longer branches to it.
 208   OldSucc->removePredecessor(FromBB);
 209
 210   // Change FromBr to branch to the new destination.
 211   FromBr->setSuccessor(0, ToBB);
 212
 213   MadeChange = true;
 214 }