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