[JumpThreading] Don't limit the type of an operand

[aqjune]

Summary

Compared to the optimized code with branch conditions never frozen,
limiting the type of freeze's operand causes generation of suboptimal code in
some cases.
I would like to suggest removing the constraint, as this patch does.
If the number of freeze instructions becomes significant, this can be revisited.

[efriedma]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

685

Oh, hmm, I misintepreted this comment, and didn't read the code carefully enough. The "if" is actually a heuristic that suppresses potential optimizations.

Do you have any idea what the actual compile-time impact would be if we just recursed over all casts?

[aqjune]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

685

I ran a test, and actually it brought a slight speedup when compiled with -O3 (without LTO):

+-----------------------------------------------+-------+-------+------------+
|                   unit:sec.                   | base  | cast  | speedup(%) |
+-----------------------------------------------+-------+-------+------------+
| CTMark/7zip/7zip-benchmark.test               | 90.18 | 89.83 | 0.39%      |
| CTMark/Bullet/bullet.test                     | 63.11 | 62.92 | 0.31%      |
| CTMark/ClamAV/clamscan.test                   | 27.00 | 26.98 | 0.05%      |
| CTMark/SPASS/SPASS.test                       | 26.27 | 26.14 | 0.52%      |
| CTMark/consumer-typeset/consumer-typeset.test | 19.73 | 19.74 | -0.02%     |
| CTMark/kimwitu++/kc.test                      | 26.60 | 26.51 | 0.37%      |
| CTMark/lencod/lencod.test                     | 34.64 | 34.65 | -0.03%     |
| CTMark/mafft/pairlocalalign.test              | 16.24 | 16.24 | 0.00%      |
| CTMark/sqlite3/sqlite3.test                   | 24.61 | 24.68 | -0.27%     |
| CTMark/tramp3d-v4/tramp3d-v4.test             | 49.35 | 49.24 | 0.22%      |
+-----------------------------------------------+-------+-------+------------+

Would it be a right direction if I remove this condition in a separate patch?

[lebedev.ri]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

685

Compile time != run time

[aqjune]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

685

The table depicts compile time.

Compilation becomes slightly faster (or almost equivalent, assuming that they are errors) if the conditions are removed, interestingly.

[lebedev.ri]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

685

http://llvm-compile-time-tracker.com/compare.php?from=03116a9f8c2fc98577e153083aaf9b6a701ab8f9&to=503a232ea5a630ddacde3ba01498776b61c4c8d4&stat=instructions
So it doesn't look like the cost is too great

[efriedma]

LGTM

llvm/lib/Transforms/Scalar/JumpThreading.cpp

685

Sure, we can do it in a separate patch.

706

Maybe tweak this comment, if we're going to drop the check for cmpinst.

[aqjune]

Update the comment

llvm/lib/Transforms/Scalar/JumpThreading.cpp

 //===- JumpThreading.cpp - Thread control through conditional blocks ------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
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, 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) &&
         !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;
+    // Unlike cast, don't limit the type of Source because it generates a
+    // sub-optimal code compared to the case when branch conditions are unfrozen
     ComputeValueKnownInPredecessorsImpl(Source, BB, Result, Preference,
                                         RecursionSet, CxtI);
 
     erase_if(Result, [](auto &Pair) {
       return !isGuaranteedNotToBeUndefOrPoison(Pair.first);
     });
 
     return !Result.empty();

llvm/test/Transforms/JumpThreading/freeze.ll

T2:
   ret i32 %B
 
 F2:
   ret i32 %B
 }
 
 define i32 @test1_cast2(i1 %cond) {
 ; CHECK-LABEL: @test1_cast2(
-; CHECK-NEXT:    br i1 [[COND:%.*]], label [[MERGE_THREAD:%.*]], label [[MERGE:%.*]]
-; CHECK:       Merge.thread:
-; CHECK-NEXT:    [[V1:%.*]] = call i32 @f1()
-; CHECK-NEXT:    br label [[T2:%.*]]
-; CHECK:       Merge:
-; 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 [[COND:%.*]], label [[T2:%.*]], label [[F2:%.*]]
 ; CHECK:       T2:
-; CHECK-NEXT:    [[B5:%.*]] = phi i32 [ [[V1]], [[MERGE_THREAD]] ], [ [[V2]], [[MERGE]] ]
+; CHECK-NEXT:    [[V1:%.*]] = call i32 @f1()
 ; CHECK-NEXT:    call void @f3()
-; CHECK-NEXT:    ret i32 [[B5]]
+; CHECK-NEXT:    ret i32 [[V1]]
 ; CHECK:       F2:
+; CHECK-NEXT:    [[V2:%.*]] = call i32 @f2()
+; CHECK-NEXT:    [[A0_FR:%.*]] = freeze i32 0
 ; CHECK-NEXT:    ret i32 [[V2]]
 ;
   br i1 %cond, label %T1, label %F1
 
 T1:
   %v1 = call i32 @f1()
   br label %Merge