SimplifyCFG: Track the number of used icmps when turning a icmp chain into a switch...

Also prevent the switch-to-icmp transform from creating identity adds, noticed by Marius Wachtler.

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

diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp
index 93d814357608b0039079a40f84041d0785db6735..fb660dbfac100e899163128dc9138af2b1c61967 100644 (file)
--- a/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -305,7 +305,7 @@ static ConstantInt *GetConstantInt(Value *V, const TargetData *TD) {
 /// Values vector.
 static Value *
 GatherConstantCompares(Value *V, std::vector<ConstantInt*> &Vals, Value *&Extra,
 /// Values vector.
 static Value *
 GatherConstantCompares(Value *V, std::vector<ConstantInt*> &Vals, Value *&Extra,

-                       const TargetData *TD, bool isEQ) {
+                       const TargetData *TD, bool isEQ, unsigned &UsedICmps) {

   Instruction *I = dyn_cast<Instruction>(V);
   if (I == 0) return 0;
   
   Instruction *I = dyn_cast<Instruction>(V);
   if (I == 0) return 0;
   


@@ -313,6 +313,7 @@ GatherConstantCompares(Value *V, std::vector<ConstantInt*> &Vals, Value *&Extra,
   if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
     if (ConstantInt *C = GetConstantInt(I->getOperand(1), TD)) {
       if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) {
   if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
     if (ConstantInt *C = GetConstantInt(I->getOperand(1), TD)) {
       if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) {

+        UsedICmps++;

         Vals.push_back(C);
         return I->getOperand(0);
       }
         Vals.push_back(C);
         return I->getOperand(0);
       }


@@ -335,6 +336,7 @@ GatherConstantCompares(Value *V, std::vector<ConstantInt*> &Vals, Value *&Extra,
       
       for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp)
         Vals.push_back(ConstantInt::get(V->getContext(), Tmp));
       
       for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp)
         Vals.push_back(ConstantInt::get(V->getContext(), Tmp));

+      UsedICmps++;

       return I->getOperand(0);
     }
     return 0;
       return I->getOperand(0);
     }
     return 0;


@@ -345,14 +347,17 @@ GatherConstantCompares(Value *V, std::vector<ConstantInt*> &Vals, Value *&Extra,
     return 0;
   
   unsigned NumValsBeforeLHS = Vals.size();
     return 0;
   
   unsigned NumValsBeforeLHS = Vals.size();

+  unsigned UsedICmpsBeforeLHS = UsedICmps;

   if (Value *LHS = GatherConstantCompares(I->getOperand(0), Vals, Extra, TD,
   if (Value *LHS = GatherConstantCompares(I->getOperand(0), Vals, Extra, TD,

-                                          isEQ)) {
+                                          isEQ, UsedICmps)) {

     unsigned NumVals = Vals.size();
     unsigned NumVals = Vals.size();

+    unsigned UsedICmpsBeforeRHS = UsedICmps;

     if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD,
     if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD,

-                                            isEQ)) {
+                                            isEQ, UsedICmps)) {

       if (LHS == RHS)
         return LHS;
       Vals.resize(NumVals);
       if (LHS == RHS)
         return LHS;
       Vals.resize(NumVals);

+      UsedICmps = UsedICmpsBeforeRHS;

     }
 
     // The RHS of the or/and can't be folded in and we haven't used "Extra" yet,
     }
 
     // The RHS of the or/and can't be folded in and we haven't used "Extra" yet,


@@ -363,6 +368,7 @@ GatherConstantCompares(Value *V, std::vector<ConstantInt*> &Vals, Value *&Extra,
     }
     
     Vals.resize(NumValsBeforeLHS);
     }
     
     Vals.resize(NumValsBeforeLHS);

+    UsedICmps = UsedICmpsBeforeLHS;

     return 0;
   }
   
     return 0;
   }
   


@@ -372,7 +378,7 @@ GatherConstantCompares(Value *V, std::vector<ConstantInt*> &Vals, Value *&Extra,
     Value *OldExtra = Extra;
     Extra = I->getOperand(0);
     if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD,
     Value *OldExtra = Extra;
     Extra = I->getOperand(0);
     if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD,

-                                            isEQ))
+                                            isEQ, UsedICmps))

       return RHS;
     assert(Vals.size() == NumValsBeforeLHS);
     Extra = OldExtra;
       return RHS;
     assert(Vals.size() == NumValsBeforeLHS);
     Extra = OldExtra;


@@ -1926,17 +1932,24 @@ static bool SimplifyBranchOnICmpChain(BranchInst *BI, const TargetData *TD) {
   std::vector<ConstantInt*> Values;
   bool TrueWhenEqual = true;
   Value *ExtraCase = 0;
   std::vector<ConstantInt*> Values;
   bool TrueWhenEqual = true;
   Value *ExtraCase = 0;

+  unsigned UsedICmps = 0;

   
   if (Cond->getOpcode() == Instruction::Or) {
   
   if (Cond->getOpcode() == Instruction::Or) {

-    CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, true);
+    CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, true,
+                                     UsedICmps);

   } else if (Cond->getOpcode() == Instruction::And) {
   } else if (Cond->getOpcode() == Instruction::And) {

-    CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, false);
+    CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, false,
+                                     UsedICmps);

     TrueWhenEqual = false;
   }
   
   // If we didn't have a multiply compared value, fail.
   if (CompVal == 0) return false;
 
     TrueWhenEqual = false;
   }
   
   // If we didn't have a multiply compared value, fail.
   if (CompVal == 0) return false;
 

+  // Avoid turning single icmps into a switch.
+  if (UsedICmps <= 1)
+    return false;
+

   // There might be duplicate constants in the list, which the switch
   // instruction can't handle, remove them now.
   array_pod_sort(Values.begin(), Values.end(), ConstantIntSortPredicate);
   // There might be duplicate constants in the list, which the switch
   // instruction can't handle, remove them now.
   array_pod_sort(Values.begin(), Values.end(), ConstantIntSortPredicate);


@@ -2262,7 +2275,9 @@ static bool TurnSwitchRangeIntoICmp(SwitchInst *SI) {
   Constant *Offset = ConstantExpr::getNeg(Cases.back());
   Constant *NumCases = ConstantInt::get(Offset->getType(), SI->getNumCases()-1);
 
   Constant *Offset = ConstantExpr::getNeg(Cases.back());
   Constant *NumCases = ConstantInt::get(Offset->getType(), SI->getNumCases()-1);
 

-  Value *Sub = BinaryOperator::CreateAdd(SI->getCondition(), Offset, "off", SI);
+  Value *Sub = SI->getCondition();
+  if (!Offset->isNullValue())
+    Sub = BinaryOperator::CreateAdd(Sub, Offset, Sub->getName()+".off", SI);

   Value *Cmp = new ICmpInst(SI, ICmpInst::ICMP_ULT, Sub, NumCases, "switch");
   BranchInst::Create(SI->getSuccessor(1), SI->getDefaultDest(), Cmp, SI);
 
   Value *Cmp = new ICmpInst(SI, ICmpInst::ICMP_ULT, Sub, NumCases, "switch");
   BranchInst::Create(SI->getSuccessor(1), SI->getDefaultDest(), Cmp, SI);
 

diff --git a/test/Transforms/SimplifyCFG/switch-to-icmp.ll b/test/Transforms/SimplifyCFG/switch-to-icmp.ll
index 2499cdbcd69f1b0dc6acc4c3459ab4edc392a33e..414f8475bc2302353ff3cd7332250050e4837845 100644 (file)
--- a/test/Transforms/SimplifyCFG/switch-to-icmp.ll
+++ b/test/Transforms/SimplifyCFG/switch-to-icmp.ll
@@ -16,8 +16,8 @@ lor.end:
  ret i1 %0
 
 ; CHECK: @test1
  ret i1 %0
 
 ; CHECK: @test1

-; CHECK: %off = add i32 %x, -1
-; CHECK: %switch = icmp ult i32 %off, 3
+; CHECK: %x.off = add i32 %x, -1
+; CHECK: %switch = icmp ult i32 %x.off, 3

 }
 
 define zeroext i1 @test2(i32 %x) nounwind readnone ssp noredzone {
 }
 
 define zeroext i1 @test2(i32 %x) nounwind readnone ssp noredzone {


@@ -35,6 +35,5 @@ lor.end:
  ret i1 %0
 
 ; CHECK: @test2
  ret i1 %0
 
 ; CHECK: @test2

-; CHECK: %off = add i32 %x, 0
-; CHECK: %switch = icmp ult i32 %off, 2
+; CHECK: %switch = icmp ult i32 %x, 2

 }
 }

diff --git a/test/Transforms/SimplifyCFG/switch_create.ll b/test/Transforms/SimplifyCFG/switch_create.ll
index 7c153e868222d805d22dc9637f31796dd22ae73c..546cc75f2973b00db9852e6cd0a563d5e16b0a69 100644 (file)
--- a/test/Transforms/SimplifyCFG/switch_create.ll
+++ b/test/Transforms/SimplifyCFG/switch_create.ll
@@ -141,8 +141,8 @@ UnifiedReturnBlock:             ; preds = %shortcirc_done.4, %shortcirc_next.4
         ret i1 %UnifiedRetVal
         
 ; CHECK: @test6
         ret i1 %UnifiedRetVal
         
 ; CHECK: @test6

-; CHECK: %off = add i32 %tmp.2.i, -14
-; CHECK: %switch = icmp ult i32 %off, 6
+; CHECK: %tmp.2.i.off = add i32 %tmp.2.i, -14
+; CHECK: %switch = icmp ult i32 %tmp.2.i.off, 6

 }
 
 define void @test7(i8 zeroext %c, i32 %x) nounwind ssp noredzone {
 }
 
 define void @test7(i8 zeroext %c, i32 %x) nounwind ssp noredzone {


@@ -441,8 +441,8 @@ if.end:
 define zeroext i1 @test16(i32 %x) nounwind {
 entry:
 ; CHECK: @test16
 define zeroext i1 @test16(i32 %x) nounwind {
 entry:
 ; CHECK: @test16

-; CHECK: %off = add i32 %x, -1
-; CHECK: %switch = icmp ult i32 %off, 3
+; CHECK: %x.off = add i32 %x, -1
+; CHECK: %switch = icmp ult i32 %x.off, 3

   %cmp.i = icmp eq i32 %x, 1
   br i1 %cmp.i, label %lor.end, label %lor.lhs.false
 
   %cmp.i = icmp eq i32 %x, 1
   br i1 %cmp.i, label %lor.end, label %lor.lhs.false
 


@@ -458,3 +458,24 @@ lor.end:
   %0 = phi i1 [ true, %lor.lhs.false ], [ true, %entry ], [ %cmp.i1, %lor.rhs ]
   ret i1 %0
 }
   %0 = phi i1 [ true, %lor.lhs.false ], [ true, %entry ], [ %cmp.i1, %lor.rhs ]
   ret i1 %0
 }

+
+; Check that we don't turn an icmp into a switch where it's not useful.
+define void @test17(i32 %x, i32 %y) {
+  %cmp = icmp ult i32 %x, 3
+  %switch = icmp ult i32 %y, 2
+  %or.cond775 = or i1 %cmp, %switch
+  br i1 %or.cond775, label %lor.lhs.false8, label %return
+
+lor.lhs.false8:
+  tail call void @foo1()
+  ret void
+
+return:
+  ret void
+
+; CHECK: @test17
+; CHECK-NOT: switch.early.test
+; CHECK-NOT: switch i32
+; CHECK: ret void
+}
+

diff --git a/test/Transforms/SimplifyCFG/switch_formation.dbg.ll b/test/Transforms/SimplifyCFG/switch_formation.dbg.ll
index 09bef648ab09008264f01cc6301a26729ebaa6a6..2723ec608e1d7931fa0b5d5849b8a833621fdc11 100644 (file)
--- a/test/Transforms/SimplifyCFG/switch_formation.dbg.ll
+++ b/test/Transforms/SimplifyCFG/switch_formation.dbg.ll
@@ -14,8 +14,8 @@ declare void @llvm.dbg.stoppoint(i32, i32, { }*) nounwind
 
 define i1 @t({ i32, i32 }* %I) {
 ; CHECK: @t
 
 define i1 @t({ i32, i32 }* %I) {
 ; CHECK: @t

-; CHECK: %off = add i32 %tmp.2.i, -14
-; CHECK: %switch = icmp ult i32 %off, 6
+; CHECK: %tmp.2.i.off = add i32 %tmp.2.i, -14
+; CHECK: %switch = icmp ult i32 %tmp.2.i.off, 6

 entry:
         %tmp.1.i = getelementptr { i32, i32 }* %I, i64 0, i32 1         ; <i32*> [#uses=1]
         %tmp.2.i = load i32* %tmp.1.i           ; <i32> [#uses=6]
 entry:
         %tmp.1.i = getelementptr { i32, i32 }* %I, i64 0, i32 1         ; <i32*> [#uses=1]
         %tmp.2.i = load i32* %tmp.1.i           ; <i32> [#uses=6]