Add transformation to update loop interation space. Now,

for (i=A; i<N; i++) {
  if (i < X && i > Y)
    do_something();
}

is transformed into

U=min(N,X); L=max(A,Y);
for (i=L;i<U;i++)
  do_somethihg();                            



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

2 files changed, 205 insertions, 7 deletions

diff --git a/lib/Transforms/Scalar/LoopIndexSplit.cpp b/lib/Transforms/Scalar/LoopIndexSplit.cpp
index afb7339..ae38bae 100644
--- a/lib/Transforms/Scalar/LoopIndexSplit.cpp
+++ b/lib/Transforms/Scalar/LoopIndexSplit.cpp
@@ -728,6 +728,27 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) {
   else
     NV = V1;
 
+  if (ExitCondition->getPredicate() == ICmpInst::ICMP_SGT
+      || ExitCondition->getPredicate() == ICmpInst::ICMP_UGT
+      || ExitCondition->getPredicate() == ICmpInst::ICMP_SGE
+      || ExitCondition->getPredicate() == ICmpInst::ICMP_UGE)  {
+    ExitCondition->swapOperands();
+    if (ExitValueNum)
+      ExitValueNum = 0;
+    else
+      ExitValueNum = 1;
+  }
+
+  Value *NUB = NULL;
+  Value *NLB = NULL;
+  Value *UB = ExitCondition->getOperand(ExitValueNum);
+  const Type *Ty = NV->getType();
+  bool Sign = ExitCondition->isSignedPredicate();
+  BasicBlock *Preheader = L->getLoopPreheader();
+  Instruction *PHTerminator = Preheader->getTerminator();
+
+  assert (NV && "Unexpected value");
+
   switch (CI->getPredicate()) {
   case ICmpInst::ICMP_ULE:
   case ICmpInst::ICMP_SLE:
@@ -740,9 +761,15 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) {
     // for (i = LB; i < NUB ; ++i)
     //   LOOP_BODY
     //
-
-
-
+    if (ExitCondition->getPredicate() == ICmpInst::ICMP_SLT
+        || ExitCondition->getPredicate() == ICmpInst::ICMP_ULT) {
+      Value *A = BinaryOperator::createAdd(NV, ConstantInt::get(Ty, 1, Sign),
+                                           "lsplit.add", PHTerminator);
+      Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+                              A, UB,"lsplit,c", PHTerminator);
+      NUB = new SelectInst (C, A, UB, "lsplit.nub", PHTerminator);
+    }
+    
     // for (i = LB; i <= UB; ++i)
     //   if (i <= NV && ...)
     //      LOOP_BODY
@@ -752,6 +779,12 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) {
     // for (i = LB; i <= NUB ; ++i)
     //   LOOP_BODY
     //
+    else if (ExitCondition->getPredicate() == ICmpInst::ICMP_SLE
+             || ExitCondition->getPredicate() == ICmpInst::ICMP_ULE) {
+      Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+                              NV, UB, "lsplit.c", PHTerminator);
+      NUB = new SelectInst (C, NV, UB, "lsplit.nub", PHTerminator);
+    }
     break;
   case ICmpInst::ICMP_ULT:
   case ICmpInst::ICMP_SLT:
@@ -764,8 +797,12 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) {
     // for (i = LB; i < NUB ; ++i)
     //   LOOP_BODY
     //
-
-
+    if (ExitCondition->getPredicate() == ICmpInst::ICMP_SLT
+        || ExitCondition->getPredicate() == ICmpInst::ICMP_ULT) {
+      Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+                              NV, UB, "lsplit.c", PHTerminator);
+      NUB = new SelectInst (C, NV, UB, "lsplit.nub", PHTerminator);
+    }
 
     // for (i = LB; i <= UB; ++i)
     //   if (i < NV && ...)
@@ -776,6 +813,14 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) {
     // for (i = LB; i <= NUB ; ++i)
     //   LOOP_BODY
     //
+    else if (ExitCondition->getPredicate() == ICmpInst::ICMP_SLE
+             || ExitCondition->getPredicate() == ICmpInst::ICMP_ULE) {
+      Value *S = BinaryOperator::createSub(NV, ConstantInt::get(Ty, 1, Sign),
+                                           "lsplit.add", PHTerminator);
+      Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+                              S, UB, "lsplit.c", PHTerminator);
+      NUB = new SelectInst (C, S, UB, "lsplit.nub", PHTerminator);
+    }
     break;
   case ICmpInst::ICMP_UGE:
   case ICmpInst::ICMP_SGE:
@@ -788,6 +833,11 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) {
     // for (i = NLB; i (< or <=) UB ; ++i)
     //   LOOP_BODY
     //
+    {
+      Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+                              NV, StartValue, "lsplit.c", PHTerminator);
+      NLB = new SelectInst (C, StartValue, NV, "lsplit.nlb", PHTerminator);
+    }
     break;
   case ICmpInst::ICMP_UGT:
   case ICmpInst::ICMP_SGT:
@@ -800,10 +850,26 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) {
     // for (i = NLB; i (< or <=) UB ; ++i)
     //   LOOP_BODY
     //
+    {
+      Value *A = BinaryOperator::createAdd(NV, ConstantInt::get(Ty, 1, Sign),
+                                           "lsplit.add", PHTerminator);
+      Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+                              A, StartValue, "lsplit.c", PHTerminator);
+      NLB = new SelectInst (C, StartValue, A, "lsplit.nlb", PHTerminator);
+    }
     break;
   default:
     assert ( 0 && "Unexpected split condition predicate");
   }
+
+  if (NLB) {
+    unsigned i = IndVar->getBasicBlockIndex(Preheader);
+    IndVar->setIncomingValue(i, NLB);
+  }
+
+  if (NUB) {
+    ExitCondition->setOperand(ExitValueNum, NUB);
+  }
 }
 /// updateLoopIterationSpace - Current loop body is covered by an AND
 /// instruction whose operands compares induction variables with loop
@@ -811,6 +877,9 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) {
 /// updating appropriate start and end values for induction variable.
 bool LoopIndexSplit::updateLoopIterationSpace(SplitInfo &SD) {
   BasicBlock *Header = L->getHeader();
+  BasicBlock *ExitingBlock = ExitCondition->getParent();
+  BasicBlock *SplitCondBlock = SD.SplitCondition->getParent();
+
   ICmpInst *Op0 = cast<ICmpInst>(SD.SplitCondition->getOperand(0));
   ICmpInst *Op1 = cast<ICmpInst>(SD.SplitCondition->getOperand(1));
 
@@ -865,11 +934,83 @@ bool LoopIndexSplit::updateLoopIterationSpace(SplitInfo &SD) {
   // loop may not be eliminated.
   if (!safeExitingBlock(SD, ExitCondition->getParent())) 
     return false;
-
+  
+  // Verify that loop exiting block has only two predecessor, where one predecessor
+  // is split condition block. The other predecessor will become exiting block's
+  // dominator after CFG is updated. TODO : Handle CFG's where exiting block has
+  // more then two predecessors. This requires extra work in updating dominator
+  // information.
+  BasicBlock *ExitingBBPred = NULL;
+  for (pred_iterator PI = pred_begin(ExitingBlock), PE = pred_end(ExitingBlock);
+       PI != PE; ++PI) {
+    BasicBlock *BB = *PI;
+    if (SplitCondBlock == BB) 
+      continue;
+    if (ExitingBBPred)
+      return false;
+    else
+      ExitingBBPred = BB;
+  }
+  
+  // Update loop bounds to absorb Op0 check.
   updateLoopBounds(Op0);
+  // Update loop bounds to absorb Op1 check.
   updateLoopBounds(Op1);
+
   // Update CFG
-  return false;
+
+  // Unconditionally connect split block to its remaining successor. 
+  BranchInst *SplitTerminator = 
+    cast<BranchInst>(SplitCondBlock->getTerminator());
+  BasicBlock *Succ0 = SplitTerminator->getSuccessor(0);
+  BasicBlock *Succ1 = SplitTerminator->getSuccessor(1);
+  if (Succ0 == ExitCondition->getParent())
+    SplitTerminator->setUnconditionalDest(Succ1);
+  else
+    SplitTerminator->setUnconditionalDest(Succ0);
+
+  // Remove split condition.
+  SD.SplitCondition->eraseFromParent();
+  if (Op0->use_begin() == Op0->use_end())
+    Op0->eraseFromParent();
+  if (Op1->use_begin() == Op1->use_end())
+    Op1->eraseFromParent();
+      
+  BranchInst *ExitInsn =
+    dyn_cast<BranchInst>(ExitingBlock->getTerminator());
+  assert (ExitInsn && "Unable to find suitable loop exit branch");
+  BasicBlock *ExitBlock = ExitInsn->getSuccessor(1);
+  if (L->contains(ExitBlock))
+    ExitBlock = ExitInsn->getSuccessor(0);
+
+  // Update domiantor info. Now, ExitingBlock has only one predecessor, 
+  // ExitingBBPred, and it is ExitingBlock's immediate domiantor.
+  DT->changeImmediateDominator(ExitingBlock, ExitingBBPred);
+  
+  // If ExitingBlock is a member of loop BB's DF list then replace it with
+  // loop header and exit block.
+  for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
+       I != E; ++I) {
+    BasicBlock *BB = *I;
+    if (BB == Header || BB == ExitingBlock)
+      continue;
+    DominanceFrontier::iterator BBDF = DF->find(BB);
+    DominanceFrontier::DomSetType::iterator DomSetI = BBDF->second.begin();
+    DominanceFrontier::DomSetType::iterator DomSetE = BBDF->second.end();
+    while (DomSetI != DomSetE) {
+      DominanceFrontier::DomSetType::iterator CurrentItr = DomSetI;
+      ++DomSetI;
+      BasicBlock *DFBB = *CurrentItr;
+      if (DFBB == ExitingBlock) {
+        BBDF->second.erase(DFBB);
+        BBDF->second.insert(Header);
+        if (Header != ExitingBlock)
+          BBDF->second.insert(ExitBlock);
+      }
+    }
+  }
+
+  return return;
 }
 
 
diff --git a/test/Transforms/LoopIndexSplit/2007-09-24-UpdateIterationSpace.ll b/test/Transforms/LoopIndexSplit/2007-09-24-UpdateIterationSpace.ll
new file mode 100644
index 0000000..b648cec
--- /dev/null
+++ b/test/Transforms/LoopIndexSplit/2007-09-24-UpdateIterationSpace.ll
@@ -0,0 +1,57 @@
+
+; Update loop iteraton space to eliminate condition inside loop.
+; RUN: llvm-as < %s | opt -loop-index-split | llvm-dis | not grep bothcond
+define void @test(float* %x, i32 %ndat, float** %y, float %xcen, i32 %xmin, i32 %xmax, float %sigmal, float %contribution) {
+entry:
+	%tmp519 = icmp sgt i32 %xmin, %xmax		; <i1> [#uses=1]
+	br i1 %tmp519, label %return, label %bb.preheader
+
+bb.preheader:		; preds = %entry
+	%tmp3031 = fpext float %contribution to double		; <double> [#uses=1]
+	%tmp32 = mul double %tmp3031, 5.000000e-01		; <double> [#uses=1]
+	%tmp3839 = fpext float %sigmal to double		; <double> [#uses=1]
+	br label %bb
+
+bb:		; preds = %bb.preheader, %cond_next45
+	%i.01.0 = phi i32 [ %tmp47, %cond_next45 ], [ %xmin, %bb.preheader ]		; <i32> [#uses=6]
+	%tmp2 = icmp sgt i32 %i.01.0, -1		; <i1> [#uses=1]
+	%tmp6 = icmp slt i32 %i.01.0, %ndat		; <i1> [#uses=1]
+	%bothcond = and i1 %tmp2, %tmp6		; <i1> [#uses=1]
+	br i1 %bothcond, label %cond_true9, label %cond_next45
+
+cond_true9:		; preds = %bb
+	%tmp12 = getelementptr float* %x, i32 %i.01.0		; <float*> [#uses=1]
+	%tmp13 = load float* %tmp12, align 4		; <float> [#uses=1]
+	%tmp15 = sub float %xcen, %tmp13		; <float> [#uses=1]
+	%tmp16 = tail call float @fabsf( float %tmp15 )		; <float> [#uses=1]
+	%tmp18 = fdiv float %tmp16, %sigmal		; <float> [#uses=1]
+	%tmp21 = load float** %y, align 4		; <float*> [#uses=2]
+	%tmp27 = getelementptr float* %tmp21, i32 %i.01.0		; <float*> [#uses=1]
+	%tmp28 = load float* %tmp27, align 4		; <float> [#uses=1]
+	%tmp2829 = fpext float %tmp28 to double		; <double> [#uses=1]
+	%tmp34 = sub float -0.000000e+00, %tmp18		; <float> [#uses=1]
+	%tmp3435 = fpext float %tmp34 to double		; <double> [#uses=1]
+	%tmp36 = tail call double @exp( double %tmp3435 )		; <double> [#uses=1]
+	%tmp37 = mul double %tmp32, %tmp36		; <double> [#uses=1]
+	%tmp40 = fdiv double %tmp37, %tmp3839		; <double> [#uses=1]
+	%tmp41 = add double %tmp2829, %tmp40		; <double> [#uses=1]
+	%tmp4142 = fptrunc double %tmp41 to float		; <float> [#uses=1]
+	%tmp44 = getelementptr float* %tmp21, i32 %i.01.0		; <float*> [#uses=1]
+	store float %tmp4142, float* %tmp44, align 4
+	br label %cond_next45
+
+cond_next45:		; preds = %bb, %cond_true9
+	%tmp47 = add i32 %i.01.0, 1		; <i32> [#uses=2]
+	%tmp51 = icmp sgt i32 %tmp47, %xmax		; <i1> [#uses=1]
+	br i1 %tmp51, label %return.loopexit, label %bb
+
+return.loopexit:		; preds = %cond_next45
+	br label %return
+
+return:		; preds = %return.loopexit, %entry
+	ret void
+}
+
+declare float @fabsf(float)
+
+declare double @exp(double)