lib/Transforms/Scalar/CondPropagate.cpp

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