lib/Transforms/Scalar/JumpThreading.cpp

   1 //===- JumpThreading.cpp - Thread control through conditional blocks ------===//
   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 file implements the Jump Threading pass.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "jump-threading"
  15 #include "llvm/Transforms/Scalar.h"
  16 #include "llvm/IntrinsicInst.h"
  17 #include "llvm/Pass.h"
  18 #include "llvm/ADT/Statistic.h"
  19 #include "llvm/Support/CommandLine.h"
  20 #include "llvm/Support/Compiler.h"
  21 #include "llvm/Support/Debug.h"
  22 using namespace llvm;
  23
  24 //STATISTIC(NumThreads, "Number of jumps threaded");
  25
  26 static cl::opt<unsigned>
  27 Threshold("jump-threading-threshold",
  28           cl::desc("Max block size to duplicate for jump threading"),
  29           cl::init(6), cl::Hidden);
  30
  31 namespace {
  32   /// This pass performs 'jump threading', which looks at blocks that have
  33   /// multiple predecessors and multiple successors.  If one or more of the
  34   /// predecessors of the block can be proven to always jump to one of the
  35   /// successors, we forward the edge from the predecessor to the successor by
  36   /// duplicating the contents of this block.
  37   ///
  38   /// An example of when this can occur is code like this:
  39   ///
  40   ///   if () { ...
  41   ///     X = 4;
  42   ///   }
  43   ///   if (X < 3) {
  44   ///
  45   /// In this case, the unconditional branch at the end of the first if can be
  46   /// revectored to the false side of the second if.
  47   ///
  48   class VISIBILITY_HIDDEN JumpThreading : public FunctionPass {
  49   public:
  50     static char ID; // Pass identification
  51     JumpThreading() : FunctionPass((intptr_t)&ID) {}
  52
  53     bool runOnFunction(Function &F);
  54     bool ThreadBlock(BasicBlock &BB);
  55   };
  56   char JumpThreading::ID = 0;
  57   RegisterPass<JumpThreading> X("jump-threading", "Jump Threading");
  58 }
  59
  60 // Public interface to the Jump Threading pass
  61 FunctionPass *llvm::createJumpThreadingPass() { return new JumpThreading(); }
  62
  63 /// runOnFunction - Top level algorithm.
  64 ///
  65 bool JumpThreading::runOnFunction(Function &F) {
  66   DOUT << "Jump threading on function '" << F.getNameStart() << "'\n";
  67   bool Changed = false;
  68   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
  69     Changed |= ThreadBlock(*I);
  70   return Changed;
  71 }
  72
  73 /// getJumpThreadDuplicationCost - Return the cost of duplicating this block to
  74 /// thread across it.
  75 static unsigned getJumpThreadDuplicationCost(const BasicBlock &BB) {
  76   BasicBlock::const_iterator I = BB.begin();
  77   /// Ignore PHI nodes, these will be flattened when duplication happens.
  78   while (isa<PHINode>(*I)) ++I;
  79
  80   // Sum up the cost of each instruction until we get to the terminator.  Don't
  81   // include the terminator because the copy won't include it.
  82   unsigned Size = 0;
  83   for (; !isa<TerminatorInst>(I); ++I) {
  84     // Debugger intrinsics don't incur code size.
  85     if (isa<DbgInfoIntrinsic>(I)) continue;
  86
  87     // If this is a pointer->pointer bitcast, it is free.
  88     if (isa<BitCastInst>(I) && isa<PointerType>(I->getType()))
  89       continue;
  90
  91     // All other instructions count for at least one unit.
  92     ++Size;
  93
  94     // Calls are more expensive.  If they are non-intrinsic calls, we model them
  95     // as having cost of 4.  If they are a non-vector intrinsic, we model them
  96     // as having cost of 2 total, and if they are a vector intrinsic, we model
  97     // them as having cost 1.
  98     if (const CallInst *CI = dyn_cast<CallInst>(I)) {
  99       if (!isa<IntrinsicInst>(CI))
 100         Size += 3;
 101       else if (isa<VectorType>(CI->getType()))
 102         Size += 1;
 103     }
 104   }
 105
 106   // Threading through a switch statement is particularly profitable.  If this
 107   // block ends in a switch, decrease its cost to make it more likely to happen.
 108   if (isa<SwitchInst>(I))
 109     Size = Size > 6 ? Size-6 : 0;
 110
 111   return Size;
 112 }
 113
 114
 115 /// ThreadBlock - If there are any predecessors whose control can be threaded
 116 /// through to a successor, transform them now.
 117 bool JumpThreading::ThreadBlock(BasicBlock &BB) {
 118   // If there is only one predecessor or successor, then there is nothing to do.
 119   if (BB.getTerminator()->getNumSuccessors() == 1 || BB.getSinglePredecessor())
 120     return false;
 121
 122   // See if this block ends with a branch of switch.  If so, see if the
 123   // condition is a phi node.  If so, and if an entry of the phi node is a
 124   // constant, we can thread the block.
 125   Value *Condition;
 126   if (BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator()))
 127     Condition = BI->getCondition();
 128   else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB.getTerminator()))
 129     Condition = SI->getCondition();
 130   else
 131     return false; // Must be an invoke.
 132
 133   // See if this is a phi node in the current block.
 134   PHINode *PN = dyn_cast<PHINode>(Condition);
 135   if (!PN || PN->getParent() != &BB) return false;
 136
 137   // See if the cost of duplicating this block is low enough.
 138   unsigned JumpThreadCost = getJumpThreadDuplicationCost(BB);
 139   if (JumpThreadCost > Threshold) {
 140     DOUT << "  Not threading BB '" << BB.getNameStart()
 141          << "': Cost is too high: " << JumpThreadCost << "\n";
 142     return false;
 143   }
 144
 145   DOUT << "  Threading BB '" << BB.getNameStart() << "'.  Cost is : "
 146        << JumpThreadCost << "\n";
 147
 148   return false;
 149 }