[JumpThreading] Add a basic support for freeze instruction

[aqjune]

Summary

This patch adds a basic support for freeze instruction to JumpThreading
by making ComputeValueKnownInPredecessorsImpl look into its operand.

[nikic]

Just as a side note, you may want to add freeze support to foldOpIntoPhi() in InstCombine, which I believe will also catch the two cases being tested here.

llvm/test/Transforms/JumpThreading/freeze.ll

30

We should also have a negative test, say for undef as phi operand.

[aqjune]

Leave diff of the test file only

[aqjune]

Add a negative test

[aqjune]

In D84598#2174395, @nikic wrote:

Just as a side note, you may want to add freeze support to foldOpIntoPhi() in InstCombine, which I believe will also catch the two cases being tested here.

Okay, I'll have a look at it.

[aqjune]

Temporarily hide the negative test because its output was a bit strange

[nikic]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

709

You can probably write this loop a bit more elegantly using something along these lines:

erase_if(Result, [](std::pair<Constant *, BasicBlock *> &Pair) {
  return !isGuaranteedNotToBeUndefOrPoison(Pair.first);
});

[aqjune]

Revive test, use erase_if

[aqjune]

erase_if seems great.

In the test, freeze undef can be folded into something. Maybe GetBestDestForJumpOnUndef can be used. I'll make this as a follow-up patch.

[nikic]

LGTM. I'm not particularly familiar with JumpThreading though, so please wait a day in case there are more comments.

[efriedma]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

699

Do we want to handle a freeze of a cast, or vice versa?

[aqjune]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

699

Yes, it sounds good.

[aqjune]

Handle a freeze of a cast and vice versa

[efriedma]

LGTM

llvm/lib/Transforms/Scalar/JumpThreading.cpp

for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
           Result.emplace_back(KC, PN->getIncomingBlock(i));
       }
     }
 
     return !Result.empty();
   }
 
   // Handle Cast instructions.  Only see through Cast when the source operand is
-  // PHI or Cmp to save the compilation time.
+  // PHI, Cmp, or Freeze to save the compilation time.
   if (CastInst *CI = dyn_cast<CastInst>(I)) {
     Value *Source = CI->getOperand(0);
-    if (!isa<PHINode>(Source) && !isa<CmpInst>(Source))
+    if (!isa<PHINode>(Source) && !isa<CmpInst>(Source) &&
+        !isa<FreezeInst>(Source))
       return false;
     ComputeValueKnownInPredecessorsImpl(Source, BB, Result, Preference,
                                         RecursionSet, 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;
   }
 
+  // Handle Freeze instructions, in a manner similar to Cast.
+  if (FreezeInst *FI = dyn_cast<FreezeInst>(I)) {
+    Value *Source = FI->getOperand(0);
+    if (!isa<PHINode>(Source) && !isa<CmpInst>(Source) &&
+        !isa<CastInst>(Source))
+      return false;
+    ComputeValueKnownInPredecessorsImpl(Source, BB, Result, Preference,
+                                        RecursionSet, CxtI);
+
+    erase_if(Result, [](auto &Pair) {
+      return !isGuaranteedNotToBeUndefOrPoison(Pair.first);
+    });
+
+    return !Result.empty();
+  }
+
   // 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 ||
         I->getOpcode() == Instruction::And) {
       PredValueInfoTy LHSVals, RHSVals;

llvm/test/Transforms/JumpThreading/freeze.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -jump-threading -S < %s | FileCheck %s
 
 declare i32 @f1()
 declare i32 @f2()
 declare void @f3()
 
 define i32 @test1(i1 %cond) {
 ; CHECK-LABEL: @test1(
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[T1:%.*]], label [[F1:%.*]]
-; CHECK:       T1:
-; CHECK-NEXT:    [[V1:%.*]] = call i32 @f1()
-; CHECK-NEXT:    br label [[MERGE:%.*]]
-; CHECK:       F1:
-; CHECK-NEXT:    [[V2:%.*]] = call i32 @f2()
-; CHECK-NEXT:    br label [[MERGE]]
-; CHECK:       Merge:
-; CHECK-NEXT:    [[A:%.*]] = phi i1 [ true, [[T1]] ], [ false, [[F1]] ]
-; CHECK-NEXT:    [[B:%.*]] = phi i32 [ [[V1]], [[T1]] ], [ [[V2]], [[F1]] ]
-; CHECK-NEXT:    [[A_FR:%.*]] = freeze i1 [[A]]
-; CHECK-NEXT:    br i1 [[A_FR]], label [[T2:%.*]], label [[F2:%.*]]
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[T2:%.*]], label [[F2:%.*]]
 ; CHECK:       T2:
+; CHECK-NEXT:    [[V1:%.*]] = call i32 @f1()
 ; CHECK-NEXT:    call void @f3()
-; CHECK-NEXT:    ret i32 [[B]]
+; CHECK-NEXT:    ret i32 [[V1]]
 ; CHECK:       F2:
-; CHECK-NEXT:    ret i32 [[B]]
+; CHECK-NEXT:    [[V2:%.*]] = call i32 @f2()
+; CHECK-NEXT:    ret i32 [[V2]]
 ;
   br i1 %cond, label %T1, label %F1
 
 T1:
   %v1 = call i32 @f1()
   br label %Merge
 
 F1:
   %v2 = call i32 @f2()
   br label %Merge
 
 Merge:
   %A = phi i1 [true, %T1], [false, %F1]
   %B = phi i32 [%v1, %T1], [%v2, %F1]
   %A.fr = freeze i1 %A
   br i1 %A.fr, label %T2, label %F2
 
 T2:
   call void @f3()
   ret i32 %B
 
 F2:
   ret i32 %B
 }
 
 define i32 @test1_cast(i1 %cond) {
 ; CHECK-LABEL: @test1_cast(
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[T1:%.*]], label [[F1:%.*]]
-; CHECK:       T1:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[MERGE_THREAD:%.*]], label [[MERGE:%.*]]
+; CHECK:       Merge.thread:
 ; CHECK-NEXT:    [[V1:%.*]] = call i32 @f1()
-; CHECK-NEXT:    br label [[MERGE:%.*]]
-; CHECK:       F1:
-; CHECK-NEXT:    [[V2:%.*]] = call i32 @f2()
-; CHECK-NEXT:    br label [[MERGE]]
+; CHECK-NEXT:    br label [[T2:%.*]]
 ; CHECK:       Merge:
-; CHECK-NEXT:    [[A0:%.*]] = phi i32 [ 1, [[T1]] ], [ 0, [[F1]] ]
-; CHECK-NEXT:    [[B:%.*]] = phi i32 [ [[V1]], [[T1]] ], [ [[V2]], [[F1]] ]
-; CHECK-NEXT:    [[A:%.*]] = trunc i32 [[A0]] to i1
+; CHECK-NEXT:    [[V2:%.*]] = call i32 @f2()
+; CHECK-NEXT:    [[A:%.*]] = trunc i32 0 to i1
 ; CHECK-NEXT:    [[A_FR:%.*]] = freeze i1 [[A]]
-; CHECK-NEXT:    br i1 [[A_FR]], label [[T2:%.*]], label [[F2:%.*]]
+; CHECK-NEXT:    br i1 [[A_FR]], label [[T2]], label [[F2:%.*]]
 ; CHECK:       T2:
+; CHECK-NEXT:    [[B5:%.*]] = phi i32 [ [[V1]], [[MERGE_THREAD]] ], [ [[V2]], [[MERGE]] ]
 ; CHECK-NEXT:    call void @f3()
-; CHECK-NEXT:    ret i32 [[B]]
+; CHECK-NEXT:    ret i32 [[B5]]
 ; CHECK:       F2:
-; CHECK-NEXT:    ret i32 [[B]]
+; CHECK-NEXT:    ret i32 [[V2]]
 ;
   br i1 %cond, label %T1, label %F1
 
 T1:
   %v1 = call i32 @f1()
   br label %Merge
 
 F1:
T2:
   ret i32 %B
 
 F2:
   ret i32 %B
 }
 
 define i32 @test1_cast2(i1 %cond) {
 ; CHECK-LABEL: @test1_cast2(
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[T1:%.*]], label [[F1:%.*]]
-; CHECK:       T1:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[MERGE_THREAD:%.*]], label [[MERGE:%.*]]
+; CHECK:       Merge.thread:
 ; CHECK-NEXT:    [[V1:%.*]] = call i32 @f1()
-; CHECK-NEXT:    br label [[MERGE:%.*]]
-; CHECK:       F1:
-; CHECK-NEXT:    [[V2:%.*]] = call i32 @f2()
-; CHECK-NEXT:    br label [[MERGE]]
+; CHECK-NEXT:    br label [[T2:%.*]]
 ; CHECK:       Merge:
-; CHECK-NEXT:    [[A0:%.*]] = phi i32 [ 1, [[T1]] ], [ 0, [[F1]] ]
-; CHECK-NEXT:    [[B:%.*]] = phi i32 [ [[V1]], [[T1]] ], [ [[V2]], [[F1]] ]
-; CHECK-NEXT:    [[A0_FR:%.*]] = freeze i32 [[A0]]
+; CHECK-NEXT:    [[V2:%.*]] = call i32 @f2()
+; CHECK-NEXT:    [[A0_FR:%.*]] = freeze i32 0
 ; CHECK-NEXT:    [[A_FR:%.*]] = trunc i32 [[A0_FR]] to i1
-; CHECK-NEXT:    br i1 [[A_FR]], label [[T2:%.*]], label [[F2:%.*]]
+; CHECK-NEXT:    br i1 [[A_FR]], label [[T2]], label [[F2:%.*]]
 ; CHECK:       T2:
+; CHECK-NEXT:    [[B5:%.*]] = phi i32 [ [[V1]], [[MERGE_THREAD]] ], [ [[V2]], [[MERGE]] ]
 ; CHECK-NEXT:    call void @f3()
-; CHECK-NEXT:    ret i32 [[B]]
+; CHECK-NEXT:    ret i32 [[B5]]
 ; CHECK:       F2:
-; CHECK-NEXT:    ret i32 [[B]]
+; CHECK-NEXT:    ret i32 [[V2]]
 ;
   br i1 %cond, label %T1, label %F1
 
 T1:
   %v1 = call i32 @f1()
   br label %Merge
 
 F1:
T2:
   ret i32 %B
 
 F2:
   ret i32 %B
 }
 
 define i32 @test1_undef(i1 %cond) {
 ; CHECK-LABEL: @test1_undef(
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[T1:%.*]], label [[F1:%.*]]
-; CHECK:       T1:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[MERGE_THREAD:%.*]], label [[MERGE:%.*]]
+; CHECK:       Merge.thread:
 ; CHECK-NEXT:    [[V1:%.*]] = call i32 @f1()
-; CHECK-NEXT:    br label [[MERGE:%.*]]
-; CHECK:       F1:
-; CHECK-NEXT:    [[V2:%.*]] = call i32 @f2()
-; CHECK-NEXT:    br label [[MERGE]]
+; CHECK-NEXT:    br label [[T2:%.*]]
 ; CHECK:       Merge:
-; CHECK-NEXT:    [[A:%.*]] = phi i1 [ true, [[T1]] ], [ undef, [[F1]] ]
-; CHECK-NEXT:    [[B:%.*]] = phi i32 [ [[V1]], [[T1]] ], [ [[V2]], [[F1]] ]
-; CHECK-NEXT:    [[A_FR:%.*]] = freeze i1 [[A]]
-; CHECK-NEXT:    br i1 [[A_FR]], label [[T2:%.*]], label [[F2:%.*]]
+; CHECK-NEXT:    [[V2:%.*]] = call i32 @f2()
+; CHECK-NEXT:    [[A_FR:%.*]] = freeze i1 undef
+; CHECK-NEXT:    br i1 [[A_FR]], label [[T2]], label [[F2:%.*]]
 ; CHECK:       T2:
+; CHECK-NEXT:    [[B4:%.*]] = phi i32 [ [[V1]], [[MERGE_THREAD]] ], [ [[V2]], [[MERGE]] ]
 ; CHECK-NEXT:    call void @f3()
-; CHECK-NEXT:    ret i32 [[B]]
+; CHECK-NEXT:    ret i32 [[B4]]
 ; CHECK:       F2:
-; CHECK-NEXT:    ret i32 [[B]]
+; CHECK-NEXT:    ret i32 [[V2]]
 ;
   br i1 %cond, label %T1, label %F1
 
 T1:
   %v1 = call i32 @f1()
   br label %Merge
 
 F1:
T2:
   ret i32 %B
 
 F2:
   ret i32 %B
 }
 
 define i32 @test2(i1 %cond, i1 %cond2) {
 ; CHECK-LABEL: @test2(
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[T1:%.*]], label [[F1:%.*]]
-; CHECK:       T1:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[MERGE_THREAD:%.*]], label [[MERGE:%.*]]
+; CHECK:       Merge.thread:
 ; CHECK-NEXT:    [[V1:%.*]] = call i32 @f1()
-; CHECK-NEXT:    br label [[MERGE:%.*]]
-; CHECK:       F1:
-; CHECK-NEXT:    [[V2:%.*]] = call i32 @f2()
-; CHECK-NEXT:    br label [[MERGE]]
+; CHECK-NEXT:    br label [[T2:%.*]]
 ; CHECK:       Merge:
-; CHECK-NEXT:    [[A:%.*]] = phi i1 [ true, [[T1]] ], [ [[COND2:%.*]], [[F1]] ]
-; CHECK-NEXT:    [[B:%.*]] = phi i32 [ [[V1]], [[T1]] ], [ [[V2]], [[F1]] ]
-; CHECK-NEXT:    [[A_FR:%.*]] = freeze i1 [[A]]
-; CHECK-NEXT:    br i1 [[A_FR]], label [[T2:%.*]], label [[F2:%.*]]
+; CHECK-NEXT:    [[V2:%.*]] = call i32 @f2()
+; CHECK-NEXT:    [[A_FR:%.*]] = freeze i1 [[COND2:%.*]]
+; CHECK-NEXT:    br i1 [[A_FR]], label [[T2]], label [[F2:%.*]]
 ; CHECK:       T2:
+; CHECK-NEXT:    [[B4:%.*]] = phi i32 [ [[V1]], [[MERGE_THREAD]] ], [ [[V2]], [[MERGE]] ]
 ; CHECK-NEXT:    call void @f3()
-; CHECK-NEXT:    ret i32 [[B]]
+; CHECK-NEXT:    ret i32 [[B4]]
 ; CHECK:       F2:
-; CHECK-NEXT:    ret i32 [[B]]
+; CHECK-NEXT:    ret i32 [[V2]]
 ;
   br i1 %cond, label %T1, label %F1
 
 T1:
   %v1 = call i32 @f1()
   br label %Merge
 
 F1: