[JumpThreading] See through Cast Instructions

[haicheng]

Summary

Let JumpThreading to thread over blocks like following Merge block

Merge:

%B = phi i32 [0, %Entry], [%v1, %F1]
%N = trunc i32 %B to i1
br i1 %N, label %T2, label %F2

[gberry]

Would it not be better to fix SimplifyICmpInst to have some way of returning that it has done some simplification?

[haicheng]

In D17663#364437, @gberry wrote:

Would it not be better to fix SimplifyICmpInst to have some way of returning that it has done some simplification?

I am not sure. Currently, SimplifyICmpInst either return a ConstantInt or an existing value. Is it safe to let it return a new value? Will it break anything?
.
ComputeValueKnownInPredecessors() is very similar to SimplifyInstruction(). Many cases handled in ComputeValueKnownInPredecessors() (e.g., xor 1 x => not x ) are also the targets of SimplifyInstruction(). However, there are still some subtle differences between them (e.g. they treat undef differently) so that we cannot replace one by the other. So, I think it might be better just enhancing ComputeValueKnownInPredecessors().

[gberry]

I see what you're saying, but perhaps a better motivating example would be a case where the zext was of a phi value that was only constant on some paths?
The example (and test) you give above seems more like a phase-ordering issue, since simplifying away the zext completely seems like something that should already be happening outside of JumpThreading.

lib/Transforms/Scalar/JumpThreading.cpp

485

This comment is incorrect, right?

[haicheng]

Thank you very much, Geoff.

I changed the test case. Please let me know if it is better.

[gberry]

Making ComputeValueKnownInPredecessors() recursive for any cast instruction seems like it might be a bit heavy handed. Perhaps you could limit it to casts of phi nodes as is done with CmpInsts farther down to reduce the compile time impact?

Perhaps someone more familiar with this pass (@majnemer, @sanjoy ?) could comment on this?

[bmakam]

I share the same concern as Geoff. A recursive solution is compile time heavy for catching some corner cases. Most cases will already be handled by SimplifyInst. Do you have any data on how much impact this has on compile times?

[haicheng]

Only see through Cast when the source is PHI or Cmp, two types of instructions that are most important to JumpThreading. This version makes less changes and takes much less compilation time. The measured compilation time shows the difference is within the noise range.

[gberry]

Could you limit this a bit further by only looking at phis of type i1?

[haicheng]

Further restricting the source type to be i1 only. Thank you, Geoff.

[haicheng]

Add the diff context.

[mcrosier]

LGTM, but I'll defer the official accept to @bmakam and/or @gberry as they my have some additional comments.

[bmakam]

LGTM.

[gberry]

This LGTM as well, with the one minor comment request.
This code doesn't seem to have an owner, so I don't know if there is someone else who can more authoritatively approve it.

test/Transforms/JumpThreading/basic.ll

514

Can you add a comment explaining what this test is checking for?

[mcrosier]

Per Balaram/Geoff. Please add a comment to the test case.

[haicheng]

Add a test case comment. I will land it soon.

[haicheng]

landed in r263618.

lib/Transforms/Scalar/JumpThreading.cpp

for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
         if (Constant *KC = getKnownConstant(CI, Preference))
           Result.push_back(std::make_pair(KC, PN->getIncomingBlock(i)));
       }
     }
 
     return !Result.empty();
   }
 
+  // Handle Cast instructions.  Only see through Cast when the source operand is
+  // PHI or Cmp and the source type is i1 to save the compilation time.
+  if (CastInst *CI = dyn_cast<CastInst>(I)) {
+    Value *Source = CI->getOperand(0);
+    if (!Source->getType()->isIntegerTy(1))
+      return false;
+    if (!isa<PHINode>(Source) && !isa<CmpInst>(Source))
+      return false;
+    ComputeValueKnownInPredecessors(Source, BB, Result, Preference, Changed,
+                                    CxtI);
+    if (Result.empty())
+      return false;
+
+    // Convert the known values.
+    for (auto &R : Result)
+      R.first = ConstantExpr::getCast(CI->getOpcode(), R.first, CI->getType());
+
+    return true;
+  }
+
   PredValueInfoTy LHSVals, RHSVals;
 
   // Handle some boolean conditions.
   if (I->getType()->getPrimitiveSizeInBits() == 1) {
     assert(Preference == WantInteger && "One-bit non-integer type?");
     // X | true -> true
     // X & false -> false
     if (I->getOpcode() == Instruction::Or ||

test/Transforms/JumpThreading/basic.ll

T2:
   ret i32 %Q
 
 F2:
   ret i32 %B
 ; CHECK: F2:
 ; CHECK-NEXT: phi i32
 }
 
+;;; Verify that we can handle constraint propagation through cast.
+define i32 @test17(i1 %cond) {
+Entry:
+; CHECK-LABEL: @test17(
+  br i1 %cond, label %Merge, label %F1
+
+; CHECK: Entry:
+; CHECK-NEXT:  br i1 %cond, label %F2, label %Merge
+
+F1:
+  %v1 = call i32 @f1()
+  br label %Merge
+
+Merge:
+  %B = phi i32 [0, %Entry], [%v1, %F1]
+  %M = icmp eq i32 %B, 0 
+  %M1 = zext i1 %M to i32
+  %N = icmp eq i32 %M1, 0 
+  br i1 %N, label %T2, label %F2
+
+; CHECK: Merge:
+; CHECK-NOT: phi
+; CHECK-NEXT:   %v1 = call i32 @f1()
+
+T2:
+  %Q = call i32 @f2() 
+  ret i32 %Q
+
+F2:
+  ret i32 %B
+; CHECK: F2:
+; CHECK-NEXT: phi i32
+}
+
 ;;; Just check that ComputeValueKnownInPredecessors() does not return true with
 ;;; no values and triggers the assert in ProcessThreadableEdges().
-define i32 @test17() {
+define i32 @test18() {
 entry:
   %A = add i32 0, 1
   %B = icmp eq i32 %A, 0
   br i1 %B, label %T, label %F
 T:
   %v1 = call i32 @f1()
   ret i32 %v1
 F: