From 4259fe3281558d129a5442d1eba03b390ed50bc8 Mon Sep 17 00:00:00 2001
From: Devang Patel <dpatel@apple.com>
Date: Fri, 24 Aug 2007 06:17:19 +0000
Subject: It is not safe to execute split condition's true branch first all the
 time. If split condition predicate is GT or GE then execute false branch
 first.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@41358 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Scalar/LoopIndexSplit.cpp | 40 ++++++++++++++++++++++++++++----
 1 file changed, 35 insertions(+), 5 deletions(-)

(limited to 'lib/Transforms/Scalar/LoopIndexSplit.cpp')

diff --git a/lib/Transforms/Scalar/LoopIndexSplit.cpp b/lib/Transforms/Scalar/LoopIndexSplit.cpp
index 93d6309..23ffc3a 100644
--- a/lib/Transforms/Scalar/LoopIndexSplit.cpp
+++ b/lib/Transforms/Scalar/LoopIndexSplit.cpp
@@ -57,7 +57,8 @@ namespace {
 
     class SplitInfo {
     public:
-      SplitInfo() : SplitValue(NULL), SplitCondition(NULL) {}
+      SplitInfo() : SplitValue(NULL), SplitCondition(NULL), 
+                    UseTrueBranchFirst(true) {}
 
       // Induction variable's range is split at this value.
       Value *SplitValue;
@@ -65,10 +66,14 @@ namespace {
       // This compare instruction compares IndVar against SplitValue.
       ICmpInst *SplitCondition;
 
+      // True if after loop index split, first loop will execute split condition's
+      // true branch.
+      bool UseTrueBranchFirst;
       // Clear split info.
       void clear() {
         SplitValue = NULL;
         SplitCondition = NULL;
+        UseTrueBranchFirst = true;
       }
 
     };
@@ -199,6 +204,9 @@ bool LoopIndexSplit::runOnLoop(Loop *IncomingLoop, LPPassManager &LPM_Ref) {
       ++SI;
   }
 
+  if (SplitData.empty())
+    return false;
+
   // Split most profitiable condition.
   // FIXME : Implement cost analysis.
   unsigned MostProfitableSDIndex = 0;
@@ -341,6 +349,14 @@ void LoopIndexSplit::findSplitCondition() {
     if (CI->getPredicate() == ICmpInst::ICMP_NE)
       return;
 
+    // If split condition predicate is GT or GE then first execute
+    // false branch of split condition.
+    if (CI->getPredicate() != ICmpInst::ICMP_ULT
+        && CI->getPredicate() != ICmpInst::ICMP_SLT
+        && CI->getPredicate() != ICmpInst::ICMP_ULE
+        && CI->getPredicate() != ICmpInst::ICMP_SLE)
+      SD.UseTrueBranchFirst = false;
+
     // If one operand is loop invariant and second operand is SCEVAddRecExpr
     // based on induction variable then CI is a candidate split condition.
     Value *V0 = CI->getOperand(0);
@@ -878,16 +894,30 @@ bool LoopIndexSplit::splitLoop(SplitInfo &SD) {
   //[*] Eliminate split condition's inactive branch from ALoop.
   BasicBlock *A_SplitCondBlock = SD.SplitCondition->getParent();
   BranchInst *A_BR = cast<BranchInst>(A_SplitCondBlock->getTerminator());
-  BasicBlock *A_InactiveBranch = A_BR->getSuccessor(1);
-  BasicBlock *A_ActiveBranch = A_BR->getSuccessor(0);
+  BasicBlock *A_InactiveBranch = NULL;
+  BasicBlock *A_ActiveBranch = NULL;
+  if (SD.UseTrueBranchFirst) {
+    A_ActiveBranch = A_BR->getSuccessor(0);
+    A_InactiveBranch = A_BR->getSuccessor(1);
+  } else {
+    A_ActiveBranch = A_BR->getSuccessor(1);
+    A_InactiveBranch = A_BR->getSuccessor(0);
+  }
   A_BR->setUnconditionalDest(A_BR->getSuccessor(0));
   removeBlocks(A_InactiveBranch, L, A_ActiveBranch);
 
   //[*] Eliminate split condition's inactive branch in from BLoop.
   BasicBlock *B_SplitCondBlock = cast<BasicBlock>(ValueMap[A_SplitCondBlock]);
   BranchInst *B_BR = cast<BranchInst>(B_SplitCondBlock->getTerminator());
-  BasicBlock *B_InactiveBranch = B_BR->getSuccessor(0);
-  BasicBlock *B_ActiveBranch = B_BR->getSuccessor(1);
+  BasicBlock *B_InactiveBranch = NULL;
+  BasicBlock *B_ActiveBranch = NULL;
+  if (SD.UseTrueBranchFirst) {
+    B_ActiveBranch = B_BR->getSuccessor(1);
+    B_InactiveBranch = B_BR->getSuccessor(0);
+  } else {
+    B_ActiveBranch = B_BR->getSuccessor(0);
+    B_InactiveBranch = B_BR->getSuccessor(1);
+  }
   B_BR->setUnconditionalDest(B_BR->getSuccessor(1));
   removeBlocks(B_InactiveBranch, BLoop, B_ActiveBranch);
 
-- 
cgit v1.1