[ValueTracking] Teach computeKnownBits and ComputeNumSignBits to look through ExtractElement.

[bjope]

Summary

The computeKnownBits and ComputeNumSignBits functions in ValueTracking can now do a simple look-through of ExtractElement.

[spatel]

The idea looks good to me, but we should increase the depth for the recursive call. The reason that depth is not incremented for the ExtractValue case is that computeKnownBitsAddSub / computeKnownBitsMul are helper functions (they are not recursing on themselves), so the depth is incremented internally when calling computeKnownBits.

test/Analysis/ValueTracking/signbits-extract-elt.ll

2

Use -instsimplify instead.

8–10

The test case is overly complicated because something in -instcombine is able to reduce a simplified version of the test. If you change the test to use -instsimplify, then this test will prove that your ValueTracking change is firing:

define i1 @computeKnownBits_look_through_extractelt(<2 x i8> %vecin) {
  %vec = zext <2 x i8> %vecin to <2 x i32>
  %elt1 = extractelement <2 x i32> %vec, i32 1
  %bool = icmp slt i32 %elt1, 0
  ret i1 %bool
}

24–39

We have to dig deeper to find an instsimplify fold that works based on ComputeNumSignBits, but I think this will do it:

define i32 @computeNumSignBits_look_through_extractelt(<2 x i1> %vec) {
  %vec4 = sext <2 x i1> %vec to <2 x i32>
  %elt0 = extractelement <2 x i32> %vec4, i32 0
  %ashr = ashr i32 %elt0, 5  <--- this will disappear after this patch is applied
  ret i32 %ashr
}

[bjope]

In D24955#554091, @spatel wrote:

The idea looks good to me, but we should increase the depth for the recursive call. The reason that depth is not incremented for the ExtractValue case is that computeKnownBitsAddSub / computeKnownBitsMul are helper functions (they are not recursing on themselves), so the depth is incremented internally when calling computeKnownBits.

Ok, well, if Depth is about level of recursion then I agree. If it is about "search depth", then I got the feeling that it was about how many "operational" instructions that could be analysed. In the case of ExtractValue it increases Depth by one, when analysing both the ExtractValue and the add/sub/mul operation. So from an LLVM IR perspective it traverses two instructions on the same Depth, and ExtractValue does not count towards Depth.

Anyhow, I'll make sure we increase the Depth when looking through ExtractElement.

BTW, highly appreciate your comments about the testcases. It will be much easier to use -instsimplify for these tests.

[bjope]

Updated accoring to recommendations from Sanjay.

[spatel]

In D24955#555008, @bjope wrote:

Ok, well, if Depth is about level of recursion then I agree. If it is about "search depth", then I got the feeling that it was about how many "operational" instructions that could be analysed.

Ah, I didn't think of it that way. You can ask on the dev list if you'd like a more authoritative answer. It's fuzzy to me since it's based on a magic '6' presented with no code comments. :)

LGTM - see inline for a couple of nits.

test/Analysis/ValueTracking/signbits-extract-elt.ll

5

typo: now -> know

18–21

A tip (mostly for future reference): you can auto-generate the CHECK lines using the script in utils/update_test_checks.py. The only difference in this case should be that the script will create FileCheck variables for you. That will provide flexibility in case the intermediate variable names change for some unrelated reason.

[bjope]

Corrected type in test case and auto-generated FileCheck assertions.

We should probably wait for relaxed checks in a clang test case (see https://reviews.llvm.org/D24397 ) before commit.
But I hope someone will help me commit this when that test case has been corrected.

[spatel]

In D24955#555330, @bjope wrote:

Corrected type in test case and auto-generated FileCheck assertions.

We should probably wait for relaxed checks in a clang test case (see https://reviews.llvm.org/D24397 ) before commit.

No - a clang regression test should not be dependent on the optimizer; usually, it should only be checking IR with -O0 or -Xclang -disable-llvm-optzns.

[bjope]

Committed revision 283434

lib/Analysis/ValueTracking.cpp

if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
         break;
       }
       case Intrinsic::x86_sse42_crc32_64_64:
         KnownZero |= APInt::getHighBitsSet(64, 32);
         break;
       }
     }
     break;
+  case Instruction::ExtractElement:
+    // Look through extract element. At the moment we keep this simple and skip
+    // tracking the specific element. But at least we might find information
+    // valid for all elements of the vector (for example if vector is sign
+    // extended, shifted, etc).
+    computeKnownBits(I->getOperand(0), KnownZero, KnownOne, Depth + 1, Q);
+    break;
   case Instruction::ExtractValue:
     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I->getOperand(0))) {
       const ExtractValueInst *EVI = cast<ExtractValueInst>(I);
       if (EVI->getNumIndices() != 1) break;
       if (EVI->getIndices()[0] == 0) {
         switch (II->getIntrinsicID()) {
         default: break;
         case Intrinsic::uadd_with_overflow:
case Instruction::PHI: {
     }
     return Tmp;
   }
 
   case Instruction::Trunc:
     // FIXME: it's tricky to do anything useful for this, but it is an important
     // case for targets like X86.
     break;
+
+  case Instruction::ExtractElement:
+    // Look through extract element. At the moment we keep this simple and skip
+    // tracking the specific element. But at least we might find information
+    // valid for all elements of the vector (for example if vector is sign
+    // extended, shifted, etc).
+    return ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
   }
 
   // Finally, if we can prove that the top bits of the result are 0's or 1's,
   // use this information.
 
   // If we can examine all elements of a vector constant successfully, we're
   // done (we can't do any better than that). If not, keep trying.
   if (unsigned VecSignBits = computeNumSignBitsVectorConstant(V, TyBits))

test/Analysis/ValueTracking/signbits-extract-elt.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instsimplify -S | FileCheck %s
+
+; If computeKnownBits can do a simple look-through for extractelement
+; then instsimplify will know that %elt1 is non-negative at icmp.
+define i1 @computeKnownBits_look_through_extractelt(<2 x i8> %vecin) {
+; CHECK-LABEL: @computeKnownBits_look_through_extractelt(
+; CHECK-NEXT:    ret i1 false
+;
+  %vec = zext <2 x i8> %vecin to <2 x i32>
+  %elt1 = extractelement <2 x i32> %vec, i32 1
+  %bool = icmp slt i32 %elt1, 0
+  ret i1 %bool
+}
+
+; If computeNumSignBits can do a simple look-through for extractelement
+; then instsimplify will remove the ashr.
+define i32 @computeNumSignBits_look_through_extractelt(<2 x i1> %vecin) {
+; CHECK-LABEL: @computeNumSignBits_look_through_extractelt(
+; CHECK-NEXT:    [[VEC:%.*]] = sext <2 x i1> [[VEC:%.*]]in to <2 x i32>
+; CHECK-NEXT:    [[ELT0:%.*]] = extractelement <2 x i32> [[VEC]], i32 0
+; CHECK-NEXT:    ret i32 [[ELT0]]
+;
+  %vec = sext <2 x i1> %vecin to <2 x i32>
+  %elt0 = extractelement <2 x i32> %vec, i32 0
+  %ashr = ashr i32 %elt0, 5
+  ret i32 %ashr
+}