enhance the compare/load/index optimization to work on *any* load

from a global with 32/64 elements or less (depending on whether
i64 is native on the target), generating a bitshift idiom to
determine the result.  For example, on test4 we produce:

define i1 @test4(i32 %X) {
  %1 = lshr i32 933, %X                           ; <i32> [#uses=1]
  %2 = and i32 %1, 1                              ; <i32> [#uses=1]
  %R = icmp ne i32 %2, 0                          ; <i1> [#uses=1]
  ret i1 %R
}

This triggers in a number of interesting cases, for example, here's an
fp case:
@A.3255 = internal constant [4 x double] [double 4.100000e+00, double -3.900000e+00, double -1.000000e+00, double 1.000000e+00], align 32 ; <[4 x double]*> [#uses=7]
...
	   %7 = fcmp olt double %3, 0.000000e+00

In this case we make the slen2_tab global dead, which is nice:
@slen2_tab = internal constant [16 x i32] [i32 0, i32 1, i32 2, i32 3, i32 0, i32 1, i32 2, i32 3, i32 1, i32 2, i32 3, i32 1, i32 2, i32 3, i32 2, i32 3], align 32 ; <[16 x i32]*> [#uses=1]
...
	   %204 = icmp eq i32 %46, 0

Perl has a bunch of these, also on the 'Perl_regkind' array:
@Perl_yygindex = internal constant [51 x i16] [i16 0, i16 0, i16 0, i16 0, i16 374, i16 351, i16 0, i16 -12, i16 0, i16 946, i16 413, i16 -83, i16 0, i16 0, i16 0, i16 -311, i16 -13, i16 4007, i16 2893, i16 0, i16 0, i16 0, i16 0, i16 0, i16 372, i16 -8, i16 0, i16 0, i16 246, i16 -131, i16 43, i16 86, i16 208, i16 -45, i16 -169, i16 987, i16 0, i16 0, i16 0, i16 0, i16 308, i16 0, i16 -271, i16 0, i16 0, i16 0, i16 0, i16 0, i16 0, i16 0, i16 0], align 32 ; <[51 x i16]*> [#uses=1]
...
  %1364 = icmp eq i16 %1361, 0

186.crafty really likes this on 64-bit machines, because it triggers on a bunch of globals like this:
@white_outpost = internal constant [64 x i8] c"\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\02\02\00\00\00\00\00\04\05\05\04\00\00\00\00\03\06\06\03\00\00\00\00\00\01\01\00\00\00\00\00\00\00\00\00\00\00", align 32 ; <[64 x i8]*> [#uses=2]

However the big winner is 403.gcc, which triggers hundreds of times, eliminating all the accesses to the 57-element arrays 'mode_class', mode_unit_size, mode_bitsize, regclass_map, etc.

go 64-bit machines :)

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

diff --git a/lib/Transforms/Scalar/InstructionCombining.cpp b/lib/Transforms/Scalar/InstructionCombining.cpp
index 05da044e38945ebbe22c268249d4232f32a707e7..85ef7b18ef9b18f89d846569b46f2ee572f94923 100644 (file)
--- a/lib/Transforms/Scalar/InstructionCombining.cpp
+++ b/lib/Transforms/Scalar/InstructionCombining.cpp
@@ -6053,6 +6053,12 @@ FoldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP, GlobalVariable *GV,
   // -2 -> overdef, >= 0 -> that index is false.
   int OnlyFalseElement = -1;
   
+  // MagicBitvector - This is a magic bitvector where we set a bit if the
+  // comparison is true for element 'i'.  If there are 64 elements or less in
+  // the array, this will fully represent all the comparison results.
+  uint64_t MagicBitvector = 0;
+  
+  
   // Scan the array and see if one of our patterns matches.
   Constant *CompareRHS = cast<Constant>(ICI.getOperand(1));
   for (unsigned i = 0, e = Init->getNumOperands(); i != e; ++i) {
@@ -6080,8 +6086,12 @@ FoldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP, GlobalVariable *GV,
       OnlyFalseElement = OnlyFalseElement == -1 ? i : -2;
     }
     
+    // If this element is in range, update our magic bitvector.
+    if (i < 64 && IsTrueForElt)
+      MagicBitvector |= 1 << i;
+    
     // If all of our states become overdefined, bail out early.
-    if (OnlyTrueElement == -2 && OnlyFalseElement == -2)
+    if (i >= 64 && OnlyTrueElement == -2 && OnlyFalseElement == -2)
       return 0;
   }
 
@@ -6108,17 +6118,24 @@ FoldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP, GlobalVariable *GV,
                                          OnlyFalseElement));
   }
   
-  assert(0 && "Should have bailed out early");
-  
-  // TODO: FCMP.
-  
-  // TODO: Range check.
+  // If a 32-bit or 64-bit magic bitvector captures the entire comparison state
+  // of this load, replace it with computation that does:
+  //   ((magic_cst >> i) & 1) != 0
+  if (Init->getNumOperands() <= 32 ||
+      (TD && Init->getNumOperands() <= 64 && TD->isLegalInteger(64))) {
+    const Type *Ty;
+    if (Init->getNumOperands() <= 32)
+      Ty = Type::getInt32Ty(Init->getContext());
+    else
+      Ty = Type::getInt64Ty(Init->getContext());
+    Value *V = Builder->CreateIntCast(GEP->getOperand(2), Ty, false);
+    V = Builder->CreateLShr(ConstantInt::get(Ty, MagicBitvector), V);
+    V = Builder->CreateAnd(ConstantInt::get(Ty, 1), V);
+    return new ICmpInst(ICmpInst::ICMP_NE, V, ConstantInt::get(Ty, 0));
+  }
   
-  // TODO: If the global array has 32 (or 64 if native!) or less entries, we
-  // can turn this into something like:
-  //  ((magicbitconstant >> i) & 1) != 0)
-  // where we populate magicbitconstant with 0101010 based on the comparison
-  // results.
+  // TODO: Range check, two compares.
+
   return 0;
 }
 

diff --git a/test/Transforms/InstCombine/load-cmp.ll b/test/Transforms/InstCombine/load-cmp.ll
index eac9ae495dc493c2c6e997b3f07c5fe4da5306d0..e44105791ae3d61dbea6082f94beb414176ee653 100644 (file)
--- a/test/Transforms/InstCombine/load-cmp.ll
+++ b/test/Transforms/InstCombine/load-cmp.ll
@@ -34,3 +34,14 @@ define i1 @test3(i32 %X) {
 ; CHECK-NEXT: ret i1 %R
 }
 
+define i1 @test4(i32 %X) {
+  %P = getelementptr [10 x i16]* @G16, i32 0, i32 %X
+  %Q = load i16* %P
+  %R = icmp sle i16 %Q, 73
+  ret i1 %R
+; CHECK: @test4
+; CHECK-NEXT: lshr i32 933, %X
+; CHECK-NEXT: and i32 {{.*}}, 1
+; CHECK-NEXT: %R = icmp ne i32 {{.*}}, 0
+; CHECK-NEXT: ret i1 %R
+}