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/Instructions.h"
  18 #include "llvm/IntrinsicInst.h"
  19 #include "llvm/Pass.h"
  20 #include "llvm/Type.h"
  21 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  22 #include "llvm/Transforms/Utils/Local.h"
  23 #include "llvm/ADT/Statistic.h"
  24 #include "llvm/ADT/SmallVector.h"
  25 #include "llvm/Support/Compiler.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 VISIBILITY_HIDDEN CondProp : public FunctionPass {
  33     static char ID; // Pass identification, replacement for typeid
  34     CondProp() : FunctionPass(&ID) {}
  35
  36     virtual bool runOnFunction(Function &F);
  37
  38     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  39       AU.addRequiredID(BreakCriticalEdgesID);
  40       //AU.addRequired<DominanceFrontier>();
  41     }
  42
  43   private:
  44     bool MadeChange;
  45     SmallVector<BasicBlock *, 4> DeadBlocks;
  46     void SimplifyBlock(BasicBlock *BB);
  47     void SimplifyPredecessors(BranchInst *BI);
  48     void SimplifyPredecessors(SwitchInst *SI);
  49     void RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB);
  50     bool RevectorBlockTo(BasicBlock *FromBB, Value *Cond, BranchInst *BI);
  51   };
  52 }
  53
  54 char CondProp::ID = 0;
  55 static RegisterPass<CondProp> X("condprop", "Conditional Propagation");
  56
  57 FunctionPass *llvm::createCondPropagationPass() {
  58   return new CondProp();
  59 }
  60
  61 bool CondProp::runOnFunction(Function &F) {
  62   bool EverMadeChange = false;
  63   DeadBlocks.clear();
  64
  65   // While we are simplifying blocks, keep iterating.
  66   do {
  67     MadeChange = false;
  68     for (Function::iterator BB = F.begin(), E = F.end(); BB != E;)
  69       SimplifyBlock(BB++);
  70     EverMadeChange = EverMadeChange || MadeChange;
  71   } while (MadeChange);
  72
  73   if (EverMadeChange) {
  74     while (!DeadBlocks.empty()) {
  75       BasicBlock *BB = DeadBlocks.back(); DeadBlocks.pop_back();
  76       DeleteDeadBlock(BB);
  77     }
  78   }
  79   return EverMadeChange;
  80 }
  81
  82 void CondProp::SimplifyBlock(BasicBlock *BB) {
  83   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) {
  84     // If this is a conditional branch based on a phi node that is defined in
  85     // this block, see if we can simplify predecessors of this block.
  86     if (BI->isConditional() && isa<PHINode>(BI->getCondition()) &&
  87         cast<PHINode>(BI->getCondition())->getParent() == BB)
  88       SimplifyPredecessors(BI);
  89
  90   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) {
  91     if (isa<PHINode>(SI->getCondition()) &&
  92         cast<PHINode>(SI->getCondition())->getParent() == BB)
  93       SimplifyPredecessors(SI);
  94   }
  95
  96   // If possible, simplify the terminator of this block.
  97   if (ConstantFoldTerminator(BB))
  98     MadeChange = true;
  99
 100   // If this block ends with an unconditional branch and the only successor has
 101   // only this block as a predecessor, merge the two blocks together.
 102   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()))
 103     if (BI->isUnconditional() && BI->getSuccessor(0)->getSinglePredecessor() &&
 104         BB != BI->getSuccessor(0)) {
 105       BasicBlock *Succ = BI->getSuccessor(0);
 106
 107       // If Succ has any PHI nodes, they are all single-entry PHI's.  Eliminate
 108       // them.
 109       FoldSingleEntryPHINodes(Succ);
 110
 111       // Remove BI.
 112       BI->eraseFromParent();
 113
 114       // Move over all of the instructions.
 115       BB->getInstList().splice(BB->end(), Succ->getInstList());
 116
 117       // Any phi nodes that had entries for Succ now have entries from BB.
 118       Succ->replaceAllUsesWith(BB);
 119
 120       // Succ is now dead, but we cannot delete it without potentially
 121       // invalidating iterators elsewhere.  Just insert an unreachable
 122       // instruction in it and delete this block later on.
 123       new UnreachableInst(BB->getContext(), Succ);
 124       DeadBlocks.push_back(Succ);
 125       MadeChange = true;
 126     }
 127 }
 128
 129 // SimplifyPredecessors(branches) - We know that BI is a conditional branch
 130 // based on a PHI node defined in this block.  If the phi node contains constant
 131 // operands, then the blocks corresponding to those operands can be modified to
 132 // jump directly to the destination instead of going through this block.
 133 void CondProp::SimplifyPredecessors(BranchInst *BI) {
 134   // TODO: We currently only handle the most trival case, where the PHI node has
 135   // one use (the branch), and is the only instruction besides the branch and dbg
 136   // intrinsics in the block.
 137   PHINode *PN = cast<PHINode>(BI->getCondition());
 138
 139   if (PN->getNumIncomingValues() == 1) {
 140     // Eliminate single-entry PHI nodes.
 141     FoldSingleEntryPHINodes(PN->getParent());
 142     return;
 143   }
 144
 145
 146   if (!PN->hasOneUse()) return;
 147
 148   BasicBlock *BB = BI->getParent();
 149   if (&*BB->begin() != PN)
 150     return;
 151   BasicBlock::iterator BBI = BB->begin();
 152   BasicBlock::iterator BBE = BB->end();
 153   while (BBI != BBE && isa<DbgInfoIntrinsic>(++BBI)) /* empty */;
 154   if (&*BBI != BI)
 155     return;
 156
 157   // Ok, we have this really simple case, walk the PHI operands, looking for
 158   // constants.  Walk from the end to remove operands from the end when
 159   // possible, and to avoid invalidating "i".
 160   for (unsigned i = PN->getNumIncomingValues(); i != 0; --i) {
 161     Value *InVal = PN->getIncomingValue(i-1);
 162     if (!RevectorBlockTo(PN->getIncomingBlock(i-1), InVal, BI))
 163       continue;
 164
 165     ++NumBrThread;
 166
 167     // If there were two predecessors before this simplification, or if the
 168     // PHI node contained all the same value except for the one we just
 169     // substituted, the PHI node may be deleted.  Don't iterate through it the
 170     // last time.
 171     if (BI->getCondition() != PN) return;
 172   }
 173 }
 174
 175 // SimplifyPredecessors(switch) - We know that SI is switch based on a PHI node
 176 // defined in this block.  If the phi node contains constant operands, then the
 177 // blocks corresponding to those operands can be modified to jump directly to
 178 // the destination instead of going through this block.
 179 void CondProp::SimplifyPredecessors(SwitchInst *SI) {
 180   // TODO: We currently only handle the most trival case, where the PHI node has
 181   // one use (the branch), and is the only instruction besides the branch and
 182   // dbg intrinsics in the block.
 183   PHINode *PN = cast<PHINode>(SI->getCondition());
 184   if (!PN->hasOneUse()) return;
 185
 186   BasicBlock *BB = SI->getParent();
 187   if (&*BB->begin() != PN)
 188     return;
 189   BasicBlock::iterator BBI = BB->begin();
 190   BasicBlock::iterator BBE = BB->end();
 191   while (BBI != BBE && isa<DbgInfoIntrinsic>(++BBI)) /* empty */;
 192   if (&*BBI != SI)
 193     return;
 194
 195   bool RemovedPreds = false;
 196
 197   // Ok, we have this really simple case, walk the PHI operands, looking for
 198   // constants.  Walk from the end to remove operands from the end when
 199   // possible, and to avoid invalidating "i".
 200   for (unsigned i = PN->getNumIncomingValues(); i != 0; --i)
 201     if (ConstantInt *CI = dyn_cast<ConstantInt>(PN->getIncomingValue(i-1))) {
 202       // If we have a constant, forward the edge from its current to its
 203       // ultimate destination.
 204       unsigned DestCase = SI->findCaseValue(CI);
 205       RevectorBlockTo(PN->getIncomingBlock(i-1),
 206                       SI->getSuccessor(DestCase));
 207       ++NumSwThread;
 208       RemovedPreds = true;
 209
 210       // If there were two predecessors before this simplification, or if the
 211       // PHI node contained all the same value except for the one we just
 212       // substituted, the PHI node may be deleted.  Don't iterate through it the
 213       // last time.
 214       if (SI->getCondition() != PN) return;
 215     }
 216 }
 217
 218
 219 // RevectorBlockTo - Revector the unconditional branch at the end of FromBB to
 220 // the ToBB block, which is one of the successors of its current successor.
 221 void CondProp::RevectorBlockTo(BasicBlock *FromBB, BasicBlock *ToBB) {
 222   BranchInst *FromBr = cast<BranchInst>(FromBB->getTerminator());
 223   assert(FromBr->isUnconditional() && "FromBB should end with uncond br!");
 224
 225   // Get the old block we are threading through.
 226   BasicBlock *OldSucc = FromBr->getSuccessor(0);
 227
 228   // OldSucc had multiple successors. If ToBB has multiple predecessors, then
 229   // the edge between them would be critical, which we already took care of.
 230   // If ToBB has single operand PHI node then take care of it here.
 231   FoldSingleEntryPHINodes(ToBB);
 232
 233   // Update PHI nodes in OldSucc to know that FromBB no longer branches to it.
 234   OldSucc->removePredecessor(FromBB);
 235
 236   // Change FromBr to branch to the new destination.
 237   FromBr->setSuccessor(0, ToBB);
 238
 239   MadeChange = true;
 240 }
 241
 242 bool CondProp::RevectorBlockTo(BasicBlock *FromBB, Value *Cond, BranchInst *BI){
 243   BranchInst *FromBr = cast<BranchInst>(FromBB->getTerminator());
 244   if (!FromBr->isUnconditional())
 245     return false;
 246
 247   // Get the old block we are threading through.
 248   BasicBlock *OldSucc = FromBr->getSuccessor(0);
 249
 250   // If the condition is a constant, simply revector the unconditional branch at
 251   // the end of FromBB to one of the successors of its current successor.
 252   if (ConstantInt *CB = dyn_cast<ConstantInt>(Cond)) {
 253     BasicBlock *ToBB = BI->getSuccessor(CB->isZero());
 254
 255     // OldSucc had multiple successors. If ToBB has multiple predecessors, then
 256     // the edge between them would be critical, which we already took care of.
 257     // If ToBB has single operand PHI node then take care of it here.
 258     FoldSingleEntryPHINodes(ToBB);
 259
 260     // Update PHI nodes in OldSucc to know that FromBB no longer branches to it.
 261     OldSucc->removePredecessor(FromBB);
 262
 263     // Change FromBr to branch to the new destination.
 264     FromBr->setSuccessor(0, ToBB);
 265   } else {
 266     BasicBlock *Succ0 = BI->getSuccessor(0);
 267     // Do not perform transform if the new destination has PHI nodes. The
 268     // transform will add new preds to the PHI's.
 269     if (isa<PHINode>(Succ0->begin()))
 270       return false;
 271
 272     BasicBlock *Succ1 = BI->getSuccessor(1);
 273     if (isa<PHINode>(Succ1->begin()))
 274       return false;
 275
 276     // Insert the new conditional branch.
 277     BranchInst::Create(Succ0, Succ1, Cond, FromBr);
 278
 279     FoldSingleEntryPHINodes(Succ0);
 280     FoldSingleEntryPHINodes(Succ1);
 281
 282     // Update PHI nodes in OldSucc to know that FromBB no longer branches to it.
 283     OldSucc->removePredecessor(FromBB);
 284
 285     // Delete the old branch.
 286     FromBr->eraseFromParent();
 287   }
 288
 289   MadeChange = true;
 290   return true;
 291 }