[JumpThreading] Let ProcessImpliedCondition look into freeze instructions

[aqjune]

Summary

This patch makes JumpThreading's ProcessImpliedCondition deal with frozen
conditions.

[efriedma]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

1258

Would it make sense to improve isImpliedCondition, instead of manipulating the result here? (I haven't looked at the other users of isImpliedCondition, but it seems like the sort of thing isImpliedCondition should handle.)

[aqjune]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

1258

Actually, I have to say that it's hard to answer; After isImpliedCondition says something about an expression having freeze, the freeze should be properly consumed. This is needed to prevent other analyses/optimizations from concluding different result from the expression.

For example, let's consider this example:

c = freeze undef
if (c) {
  c2 = freeze undef
  print(c2)
  print(c2) // These two prints should show the same result
}

If two prints are optimized by different analyses/transformations, they may print inconsistent values, which should be avoided.
I looked through other uses of isImpliedCondition, and whether this consistency could be met (by consuming the freeze) wasn't clear to me.

Another issue was that, the semantics of existing analysis functions (computeKnownBits, isImpliedCondition, isTruePredicate, etc) isn't clear when undef/poison is involved. I mean, at least documentation-wise. I believe this is another big thing to be clarified in the future... maybe along with the semantics of attributes like nonnull/align/etc.

[aqjune]

Fix another failing test

[aqjune]

ping

[aqjune]

Rebase

[nikic]

LGTM

llvm/lib/Transforms/Scalar/JumpThreading.cpp

1231

nit: "or a nondeterministic value"

[xbolva00]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

1258

Maybe extra parameter for isImpliedCondition to peek thru freezeinst?

[nikic]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

1258

I don't think that's a good idea: An important aspect here is that the freeze is one-use and is dropped as part of the transform. I don't think this can be incorporated into the isImpliedCondition() API in a way that makes sense.

[aqjune]

Make test show diff, add a description about why @and_noopt is not optimized yet, update comments in ProcessImpliedCondition

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
 //
 //===----------------------------------------------------------------------===//
 //

 }
 
 bool JumpThreadingPass::ProcessImpliedCondition(BasicBlock *BB) {
   auto *BI = dyn_cast<BranchInst>(BB->getTerminator());
   if (!BI || !BI->isConditional())
     return false;
 
   Value *Cond = BI->getCondition();
+  // Assuming that predecessor's branch was taken, if pred's branch condition
+  // V implies Cond, Cond is either true, undef, or poison. In this case,
+  // freeze(Cond) is either true or nondeterministic value.
+  // If freeze(Cond) has only one use, we can freely fold freeze(Cond) to true
+  // without affecting other instructions.
+  auto *FICond = dyn_cast<FreezeInst>(Cond);
+  if (FICond && FICond->hasOneUse())
+    Cond = FICond->getOperand(0);
+  else
+    FICond = nullptr;
+
   BasicBlock *CurrentBB = BB;
   BasicBlock *CurrentPred = BB->getSinglePredecessor();
   unsigned Iter = 0;
 
   auto &DL = BB->getModule()->getDataLayout();
 
   while (CurrentPred && Iter++ < ImplicationSearchThreshold) {
     auto *PBI = dyn_cast<BranchInst>(CurrentPred->getTerminator());
     if (!PBI || !PBI->isConditional())
       return false;
     if (PBI->getSuccessor(0) != CurrentBB && PBI->getSuccessor(1) != CurrentBB)
       return false;
 
     bool CondIsTrue = PBI->getSuccessor(0) == CurrentBB;
     Optional<bool> Implication =
         isImpliedCondition(PBI->getCondition(), Cond, DL, CondIsTrue);
+
+    // If the branch conditions of BB and CurrentPred is the same freeze
+    // instruction, predecessor's branch condition implies FICond.
+    if (!Implication && FICond && isa<FreezeInst>(PBI->getCondition())) {
+      if (cast<FreezeInst>(PBI->getCondition())->getOperand(0) ==
+          FICond->getOperand(0))
+        Implication = CondIsTrue;
+    }
+
     if (Implication) {
       BasicBlock *KeepSucc = BI->getSuccessor(*Implication ? 0 : 1);
       BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);
       RemoveSucc->removePredecessor(BB);
       BranchInst *UncondBI = BranchInst::Create(KeepSucc, BI);
       UncondBI->setDebugLoc(BI->getDebugLoc());
       BI->eraseFromParent();
+      if (FICond)
+        FICond->eraseFromParent();
+
       DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, RemoveSucc}});
       return true;
     }
     CurrentBB = CurrentPred;
     CurrentPred = CurrentBB->getSinglePredecessor();
   }
 
   return false;

llvm/test/Transforms/JumpThreading/freeze-impliescond.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -jump-threading -S < %s | FileCheck %s
+
+declare void @f()
+
+define void @test1(i1 %cond, i1 %dummycond) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    br i1 [[DUMMYCOND:%.*]], label [[REACHABLE:%.*]], label [[DUMMY:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    br i1 [[DUMMYCOND]], label [[REACHABLE]], label [[DUMMY]]
+; CHECK:       REACHABLE:
+; CHECK-NEXT:    call void @f()
+; CHECK-NEXT:    ret void
+; CHECK:       DUMMY:
+; CHECK-NEXT:    ret void
+;
+  br i1 %cond, label %A, label %B
+A:
+  br i1 %dummycond, label %A2, label %DUMMY
+A2:
+  %cond.fr = freeze i1 %cond
+  br i1 %cond.fr, label %REACHABLE, label %UNREACHABLE
+B:
+  br i1 %dummycond, label %B2, label %DUMMY
+B2:
+  %cond.fr2 = freeze i1 %cond
+  br i1 %cond.fr2, label %UNREACHABLE, label %REACHABLE
+
+REACHABLE:
+  call void @f()
+  ret void
+UNREACHABLE:
+  ret void
+DUMMY:
+  ret void
+}
+
+define void @test2(i1 %cond, i1 %dummycond) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:    [[COND_FR0:%.*]] = freeze i1 [[COND:%.*]]
+; CHECK-NEXT:    br i1 [[COND_FR0]], label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    br i1 [[DUMMYCOND:%.*]], label [[REACHABLE:%.*]], label [[DUMMY:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    br i1 [[DUMMYCOND]], label [[REACHABLE]], label [[DUMMY]]
+; CHECK:       REACHABLE:
+; CHECK-NEXT:    call void @f()
+; CHECK-NEXT:    ret void
+; CHECK:       DUMMY:
+; CHECK-NEXT:    ret void
+;
+  %cond.fr0 = freeze i1 %cond
+  br i1 %cond.fr0, label %A, label %B
+A:
+  br i1 %dummycond, label %A2, label %DUMMY
+A2:
+  %cond.fr = freeze i1 %cond
+  br i1 %cond.fr, label %REACHABLE, label %UNREACHABLE
+B:
+  br i1 %dummycond, label %B2, label %DUMMY
+B2:
+  %cond.fr2 = freeze i1 %cond
+  br i1 %cond.fr2, label %UNREACHABLE, label %REACHABLE
+
+REACHABLE:
+  call void @f()
+  ret void
+UNREACHABLE:
+  ret void
+DUMMY:
+  ret void
+}
+
+define void @and_noopt(i32 %x, i1 %cond2, i1 %dummycond) {
+; CHECK-LABEL: @and_noopt(
+; CHECK-NEXT:    [[COND1:%.*]] = icmp slt i32 0, [[X:%.*]]
+; CHECK-NEXT:    [[COND:%.*]] = and i1 [[COND1]], [[COND2:%.*]]
+; CHECK-NEXT:    [[COND_FR0:%.*]] = freeze i1 [[COND]]
+; CHECK-NEXT:    br i1 [[COND_FR0]], label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    br i1 [[DUMMYCOND:%.*]], label [[A2:%.*]], label [[DUMMY:%.*]]
+; CHECK:       A2:
+; CHECK-NEXT:    [[COND_FR:%.*]] = freeze i1 [[COND1]]
+; CHECK-NEXT:    br i1 [[COND_FR]], label [[REACHABLE:%.*]], label [[UNREACHABLE:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    br i1 [[DUMMYCOND]], label [[B2:%.*]], label [[DUMMY]]
+; CHECK:       B2:
+; CHECK-NEXT:    [[COND_FR2:%.*]] = freeze i1 [[COND1]]
+; CHECK-NEXT:    br i1 [[COND_FR2]], label [[UNREACHABLE]], label [[REACHABLE]]
+; CHECK:       REACHABLE:
+; CHECK-NEXT:    call void @f()
+; CHECK-NEXT:    ret void
+; CHECK:       UNREACHABLE:
+; CHECK-NEXT:    ret void
+; CHECK:       DUMMY:
+; CHECK-NEXT:    ret void
+;
+  %cond1 = icmp slt i32 0, %x
+  %cond = and i1 %cond1, %cond2
+  %cond.fr0 = freeze i1 %cond
+  br i1 %cond.fr0, label %A, label %B
+A:
+  br i1 %dummycond, label %A2, label %DUMMY
+A2:
+  %cond.fr = freeze i1 %cond1
+  br i1 %cond.fr, label %REACHABLE, label %UNREACHABLE
+B:
+  br i1 %dummycond, label %B2, label %DUMMY
+B2:
+  %cond.fr2 = freeze i1 %cond1
+  br i1 %cond.fr2, label %UNREACHABLE, label %REACHABLE
+
+REACHABLE:
+  call void @f()
+  ret void
+UNREACHABLE:
+  ret void
+DUMMY:
+  ret void
+}
+
+define void @and(i32 %x, i1 %cond2, i1 %dummycond) {
+; CHECK-LABEL: @and(
+; CHECK-NEXT:    [[COND1:%.*]] = icmp slt i32 0, [[X:%.*]]
+; CHECK-NEXT:    [[COND:%.*]] = and i1 [[COND1]], [[COND2:%.*]]
+; CHECK-NEXT:    br i1 [[COND]], label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    br i1 [[DUMMYCOND:%.*]], label [[REACHABLE:%.*]], label [[DUMMY:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    br i1 [[DUMMYCOND]], label [[B2:%.*]], label [[DUMMY]]
+; CHECK:       B2:
+; CHECK-NEXT:    [[COND_FR2:%.*]] = freeze i1 [[COND1]]
+; CHECK-NEXT:    br i1 [[COND_FR2]], label [[REACHABLE]], label [[REACHABLE2:%.*]]
+; CHECK:       REACHABLE:
+; CHECK-NEXT:    call void @f()
+; CHECK-NEXT:    ret void
+; CHECK:       REACHABLE2:
+; CHECK-NEXT:    call void @f()
+; CHECK-NEXT:    ret void
+; CHECK:       DUMMY:
+; CHECK-NEXT:    ret void
+;
+  %cond1 = icmp slt i32 0, %x
+  %cond = and i1 %cond1, %cond2
+  br i1 %cond, label %A, label %B
+A:
+  br i1 %dummycond, label %A2, label %DUMMY
+A2:
+  %cond.fr = freeze i1 %cond1
+  br i1 %cond.fr, label %REACHABLE, label %UNREACHABLE
+B:
+  br i1 %dummycond, label %B2, label %DUMMY
+B2:
+  %cond.fr2 = freeze i1 %cond1
+  br i1 %cond.fr2, label %REACHABLE, label %REACHABLE2
+
+REACHABLE:
+  call void @f()
+  ret void
+REACHABLE2:
+  call void @f()
+  ret void
+UNREACHABLE:
+  ret void
+DUMMY:
+  ret void
+}

llvm/test/Transforms/JumpThreading/freeze-lvi-edgevaluelocal.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -jump-threading -S < %s | FileCheck %s
 
 declare void @f()
 declare void @f2()
 declare void @f3()
 
 ; br on cond.fr should be removed & ENTRY -> A -> B should be threaded
 define i32 @simple(i1 %cond) {
 ; CHECK-LABEL: @simple(
 ; CHECK-NEXT:  ENTRY:
-; CHECK-NEXT:    [[COND_FR:%.*]] = freeze i1 [[COND:%.*]]
-; CHECK-NEXT:    br i1 [[COND]], label [[A:%.*]], label [[EXIT:%.*]]
-; CHECK:       A:
-; CHECK-NEXT:    br i1 [[COND_FR]], label [[B:%.*]], label [[EXIT]]
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[B:%.*]], label [[EXIT:%.*]]
 ; CHECK:       B:
 ; CHECK-NEXT:    call void @f()
 ; CHECK-NEXT:    ret i32 1
 ; CHECK:       EXIT:
 ; CHECK-NEXT:    ret i32 0
 ;
 ENTRY:
   %cond.fr = freeze i1 %cond