Fold code like:

  if (C)
    V1 |= V2;

into:
  Vx = V1 | V2;
  V1 = select C, V1, Vx

when the expression can be evaluated unconditionally and is *cheap* to
execute.  This limited form of if conversion is quite handy in lots of cases.
For example, it turns this testcase into straight-line code:

int in0 ; int in1 ; int in2 ; int in3 ;
int in4 ; int in5 ; int in6 ; int in7 ;
int in8 ; int in9 ; int in10; int in11;
int in12; int in13; int in14; int in15;
long output;

void mux(void) {
  output =
      (in0   ?  0x00000001 : 0) | (in1   ?  0x00000002 : 0) |
      (in2   ?  0x00000004 : 0) | (in3   ?  0x00000008 : 0) |
      (in4   ?  0x00000010 : 0) | (in5   ?  0x00000020 : 0) |
      (in6   ?  0x00000040 : 0) | (in7   ?  0x00000080 : 0) |
      (in8   ?  0x00000100 : 0) | (in9   ?  0x00000200 : 0) |
      (in10  ?  0x00000400 : 0) | (in11  ?  0x00000800 : 0) |
      (in12  ?  0x00001000 : 0) | (in13  ?  0x00002000 : 0) |
      (in14  ?  0x00004000 : 0) | (in15  ?  0x00008000 : 0) ;
}


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12798 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 72 insertions, 18 deletions

diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp
index 9c3610830e..4bb480d840 100644
--- a/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -182,23 +182,59 @@ static Value *GetIfCondition(BasicBlock *BB,
 // if the specified value dominates the block.  We don't handle the true
 // generality of domination here, just a special case which works well enough
 // for us.
-static bool DominatesMergePoint(Value *V, BasicBlock *BB) {
-  if (Instruction *I = dyn_cast<Instruction>(V)) {
-    BasicBlock *PBB = I->getParent();
-    // If this instruction is defined in a block that contains an unconditional
-    // branch to BB, then it must be in the 'conditional' part of the "if
-    // statement".
-    if (isa<BranchInst>(PBB->getTerminator()) && 
-        cast<BranchInst>(PBB->getTerminator())->isUnconditional() && 
-        cast<BranchInst>(PBB->getTerminator())->getSuccessor(0) == BB)
-      return false;
-
-    // We also don't want to allow wierd loops that might have the "if
-    // condition" in the bottom of this block.
-    if (PBB == BB) return false;
-  }
+static bool DominatesMergePoint(Value *V, BasicBlock *BB, bool AllowAggressive){
+  Instruction *I = dyn_cast<Instruction>(V);
+  if (!I) return true;    // Non-instructions all dominate instructions.
+  BasicBlock *PBB = I->getParent();
+
+  // We don't want to allow wierd loops that might have the "if condition" in
+  // the bottom of this block.
+  if (PBB == BB) return false;
+
+  // If this instruction is defined in a block that contains an unconditional
+  // branch to BB, then it must be in the 'conditional' part of the "if
+  // statement".
+  if (BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator()))
+    if (BI->isUnconditional() && BI->getSuccessor(0) == BB) {
+      if (!AllowAggressive) return false;
+      // Okay, it looks like the instruction IS in the "condition".  Check to
+      // see if its a cheap instruction to unconditionally compute, and if it
+      // only uses stuff defined outside of the condition.  If so, hoist it out.
+      switch (I->getOpcode()) {
+      default: return false;  // Cannot hoist this out safely.
+      case Instruction::Load:
+        // We can hoist loads that are non-volatile and obviously cannot trap.
+        if (cast<LoadInst>(I)->isVolatile())
+          return false;
+        if (!isa<AllocaInst>(I->getOperand(0)) &&
+            !isa<Constant>(I->getOperand(0)) &&
+            !isa<GlobalValue>(I->getOperand(0)))
+          return false;
+
+        // Finally, we have to check to make sure there are no instructions
+        // before the load in its basic block, as we are going to hoist the loop
+        // out to its predecessor.
+        if (PBB->begin() != BasicBlock::iterator(I))
+          return false;
+        break;
+      case Instruction::Add:
+      case Instruction::Sub:
+      case Instruction::And:
+      case Instruction::Or:
+      case Instruction::Xor:
+      case Instruction::Shl:
+      case Instruction::Shr:
+        break;   // These are all cheap and non-trapping instructions.
+      }
+      
+      // Okay, we can only really hoist these out if their operands are not
+      // defined in the conditional region.
+      for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
+        if (!DominatesMergePoint(I->getOperand(i), BB, false))
+          return false;
+      // Okay, it's safe to do this!
+    }
 
-  // Non-instructions all dominate instructions.
   return true;
 }
 
@@ -904,13 +940,31 @@ bool llvm::SimplifyCFG(BasicBlock *BB) {
           // incoming values are defined in the conditional parts of the branch,
           // so check for this.
           //
-          if (DominatesMergePoint(PN->getIncomingValue(0), BB) &&
-              DominatesMergePoint(PN->getIncomingValue(1), BB)) {
+          if (DominatesMergePoint(PN->getIncomingValue(0), BB, true) &&
+              DominatesMergePoint(PN->getIncomingValue(1), BB, true)) {
             Value *TrueVal =
               PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse);
             Value *FalseVal =
               PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue);
 
+            // If one of the incoming values is defined in the conditional
+            // region, move it into it's predecessor block, which we know is
+            // safe.
+            if (!DominatesMergePoint(TrueVal, BB, false)) {
+              Instruction *TrueI = cast<Instruction>(TrueVal);
+              BasicBlock *OldBB = TrueI->getParent();
+              OldBB->getInstList().remove(TrueI);
+              BasicBlock *NewBB = *pred_begin(OldBB);
+              NewBB->getInstList().insert(NewBB->getTerminator(), TrueI);
+            }
+            if (!DominatesMergePoint(FalseVal, BB, false)) {
+              Instruction *FalseI = cast<Instruction>(FalseVal);
+              BasicBlock *OldBB = FalseI->getParent();
+              OldBB->getInstList().remove(FalseI);
+              BasicBlock *NewBB = *pred_begin(OldBB);
+              NewBB->getInstList().insert(NewBB->getTerminator(), FalseI);
+            }
+
             // Change the PHI node into a select instruction.
             BasicBlock::iterator InsertPos = PN;
             while (isa<PHINode>(InsertPos)) ++InsertPos;