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