- Use O(1) check of basic block size limit.

[oota-llvm.git] / lib / Transforms / Utils / SimplifyCFG.cpp

diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp
index c72806b9e2f079f2cf6b68e105629bc73c921e42..c215b91259cf75236c4e9149b671c097dab93193 100644 (file)
--- a/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -23,12 +23,15 @@
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/Statistic.h"
 #include <algorithm>
 #include <functional>
 #include <set>
 #include <map>
 using namespace llvm;
 
+STATISTIC(NumSpeculations, "Number of speculative executed instructions");
+
 /// SafeToMergeTerminators - Return true if it is safe to merge these two
 /// terminator instructions together.
 ///
@@ -962,7 +965,16 @@ HoistTerminator:
 static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) {
   // Only speculatively execution a single instruction (not counting the
   // terminator) for now.
-  if (BB1->size() != 2)
+  BasicBlock::iterator BBI = BB1->begin();
+  ++BBI; // must have at least a terminator
+  if (BBI == BB1->end()) return false; // only one inst
+  ++BBI;
+  if (BBI != BB1->end()) return false; // more than 2 insts.
+
+  // Be conservative for now. FP select instruction can often be expensive.
+  Value *BrCond = BI->getCondition();
+  if (isa<Instruction>(BrCond) &&
+      cast<Instruction>(BrCond)->getOpcode() == Instruction::FCmp)
     return false;
 
   // If BB1 is actually on the false edge of the conditional branch, remember
@@ -997,8 +1009,9 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) {
   case Instruction::Shl:
   case Instruction::LShr:
   case Instruction::AShr:
-    if (I->getOperand(0)->getType()->isFPOrFPVector())
-      return false;  // FP arithmetic might trap.
+    if (!I->getOperand(0)->getType()->isInteger())
+      // FP arithmetic might trap. Not worth doing for vector ops.
+      return false;
     break;   // These are all cheap and non-trapping instructions.
   }
 
@@ -1024,13 +1037,22 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) {
   if (!FalseV)  // Can this happen?
     return false;
 
+  // Do not hoist the instruction if any of its operands are defined but not
+  // used in this BB. The transformation will prevent the operand from
+  // being sunk into the use block.
+  for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) {
+    Instruction *OpI = dyn_cast<Instruction>(*i);
+    if (OpI && OpI->getParent() == BIParent &&
+        !OpI->isUsedInBasicBlock(BIParent))
+      return false;
+  }
+
   // If we get here, we can hoist the instruction. Try to place it before the
-  // icmp / fcmp instruction preceeding the conditional branch.
+  // icmp instruction preceeding the conditional branch.
   BasicBlock::iterator InsertPos = BI;
   if (InsertPos != BIParent->begin())
     --InsertPos;
-  if (InsertPos->getOpcode() == Instruction::ICmp ||
-      InsertPos->getOpcode() == Instruction::FCmp)
+  if (InsertPos == BrCond && !isa<PHINode>(BrCond))
     BIParent->getInstList().splice(InsertPos, BB1->getInstList(), I);
   else
     BIParent->getInstList().splice(BI, BB1->getInstList(), I);
@@ -1039,10 +1061,10 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) {
   // false value is the previously determined FalseV.
   SelectInst *SI;
   if (Invert)
-    SI = SelectInst::Create(BI->getCondition(), FalseV, I,
+    SI = SelectInst::Create(BrCond, FalseV, I,
                             FalseV->getName() + "." + I->getName(), BI);
   else
-    SI = SelectInst::Create(BI->getCondition(), I, FalseV,
+    SI = SelectInst::Create(BrCond, I, FalseV,
                             I->getName() + "." + FalseV->getName(), BI);
 
   // Make the PHI node use the select for all incoming values for "then" and
@@ -1055,6 +1077,7 @@ static bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) {
         PN->setIncomingValue(j, SI);
   }
 
+  ++NumSpeculations;
   return true;
 }