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