[JumpThreading] See through Cast Instructions

[haicheng]

Summary

This patch helps JumpThreading capture more optimization opportunities. No significant performance change in SpecINT.

[haicheng]

Fix a typo.

[gberry]

It is not clear to me from looking at the added test case what new optimization is being added. I would expect to see some CHECKs of new folded constants if I understand the change correctly.

test/Transforms/JumpThreading/basic.ll

495

These 3 lines are indented funny (tabs?)

[haicheng]

In D16809#344366, @gberry wrote:

It is not clear to me from looking at the added test case what new optimization is being added. I would expect to see some CHECKs of new folded constants if I understand the change correctly.

This patch allows the Entry block threads over the merge block. See the first CHECK-NEXT

[haicheng]

Fix the format of the test case. Thank you, Geoff.

[gberry]

test/Transforms/JumpThreading/basic.ll

493

It seems like this change to JumpThreading would not be needed if the Merge block code had been simplified to the following:

Merge:
  %B = phi i32 [1, %Entry], [%v1, %F1]
  %M = icmp eq i32 %B, 0 
  br i1 %M, label %T2, label %F2

Are we missing this simplification, or is there something more complex going on in the code this was extracted from that prevents it from happening?

[haicheng]

test/Transforms/JumpThreading/basic.ll

493

The simplification is missing. InstCombine can optimize it, but it is called after jumpthreading.

[bmakam]

test/Transforms/JumpThreading/basic.ll

493

InstSimplify can also optimize it. Have you considered just using the simplified value if the instruction can be simplified? This frequently happens due to phi translation and I think there is an instance where we use this in DuplicateCondBranchOnPHIIntoPred

[haicheng]

Thank you, Balaram. Is this the update that you suggest?

[majnemer]

lib/Transforms/Scalar/JumpThreading.cpp

413

Please use auto * for the left hand side of the assignment.

[bmakam]

LGTM once you've addressed the comments.

lib/Transforms/Scalar/JumpThreading.cpp

415

You might need to RAUW NewV,
NewV->replaceAllUsesWith(V);
V->eraseFromParent();

[bmakam]

lib/Transforms/Scalar/JumpThreading.cpp

415

I meant V->replaceAllUsesWith(NewV)

[haicheng]

Address David and Balaram's comments. Thank you.

[mcrosier]

Does this patch include the test case for r260110?

[haicheng]

In D16809#349908, @mcrosier wrote:

Does this patch include the test case for r260110?

test17 is the test case for r260110.

[mcrosier]

Seems reasonable to me, but I'll let @bmakam's or someone else more familiar with the patch give the final approval.

[gberry]

lib/Transforms/Scalar/JumpThreading.cpp

414

It seems like this block deserves a single-line comment explaining why it is being done.

test/Transforms/JumpThreading/basic.ll

514

Can you give some indication of what kind of crash/assert you are testing for here?

[haicheng]

Address Geoff's comments.

[haicheng]

Kindly ping.

[haicheng]

Kindly ping

[bmakam]

Sorry, did not realize this was waiting for my approval. LGTM.

[haicheng]

Committed in r261981.

lib/Transforms/Scalar/JumpThreading.cpp

ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB, PredValueInfo &Result,
   // and terminate the search if we loop back to them
   if (!RecursionSet.insert(std::make_pair(V, BB)).second)
     return false;
 
   // An RAII help to remove this pair from the recursion set once the recursion
   // stack pops back out again.
   RecursionSetRemover remover(RecursionSet, std::make_pair(V, BB));
 
   // If V is a constant, then it is known in all predecessors.
   if (Constant *KC = getKnownConstant(V, Preference)) {
     for (BasicBlock *Pred : predecessors(BB))
       Result.push_back(std::make_pair(KC, Pred));
 
     return true;
   }
 
   // If V is a non-instruction value, or an instruction in a different block,
   // then it can't be derived from a PHI.
   Instruction *I = dyn_cast<Instruction>(V);
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.
+  if (CastInst *CI = dyn_cast<CastInst>(I)) {
+    ComputeValueKnownInPredecessors(CI->getOperand(0), BB, Result, Preference,
+                                    CxtI);
+    if (Result.empty())
+      return false;
+
+    // Invert 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

 ; CHECK-NOT: ret i32 2
   ret i32 2
 
 exit1:
   ret i32 1
 ; CHECK: }
 }
 
+
+;;; Verify that we can handle constraint propagation through cast.
+define i32 @test16(i1 %cond) {
+Entry:
+; CHECK-LABEL: @test16(
+  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 [1, %Entry], [%v1, %F1]
+        %M = icmp eq i32 %B, 0 
+        %M1 = zext i1 %M to i32
+        %N = icmp eq i32 %M1, 1 
+  br i1 %N, label %T2, label %F2
+
+; CHECK: Merge:
+; CHECK-NOT: phi
+; CHECK-NEXT:   %v1 = call i32 @f1()
+
+T2:
+  %Q = zext i1 %M to i32
+  ret i32 %Q
+
+F2:
+  ret i32 %B
+; CHECK: F2:
+; CHECK-NEXT: phi i32
+}
+
+
+
 ; In this test we check that block duplication is inhibited by the presence
 ; of a function with the 'noduplicate' attribute.
 
 declare void @g()
 declare void @j()
 declare void @k()
 
 ; CHECK-LABEL: define void @h(i32 %p) {