[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

1283

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

1283

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

1256

nit: "or a nondeterministic value"

[xbolva00]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

1283

Maybe extra parameter for isImpliedCondition to peek thru freezeinst?

[nikic]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

1283

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

 }
 
 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 can be either true, undef, or poison. In this case,
+  // freeze(Cond) is either true or a 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 condition of BB (which is Cond) and CurrentPred are
+    // exactly the same freeze instruction, Cond can be folded into CondIsTrue.
+    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());
       ++NumFolds;
       BI->eraseFromParent();
+      if (FICond)
+        FICond->eraseFromParent();
+
       DTU->applyUpdatesPermissive({{DominatorTree::Delete, BB, RemoveSucc}});
       if (HasProfileData)
         BPI->eraseBlock(BB);
       return true;
     }
     CurrentBB = CurrentPred;
     CurrentPred = CurrentBB->getSinglePredecessor();
   }

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

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 [[A2:%.*]], label [[DUMMY:%.*]]
-; CHECK:       A2:
-; CHECK-NEXT:    [[COND_FR:%.*]] = freeze i1 [[COND]]
-; CHECK-NEXT:    br i1 [[COND_FR]], label [[REACHABLE:%.*]], label [[UNREACHABLE:%.*]]
+; 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 [[COND]]
-; CHECK-NEXT:    br i1 [[COND_FR2]], label [[UNREACHABLE]], label [[REACHABLE]]
+; CHECK-NEXT:    br i1 [[DUMMYCOND]], label [[REACHABLE]], label [[DUMMY]]
 ; CHECK:       REACHABLE:
 ; CHECK-NEXT:    call void @f()
 ; CHECK-NEXT:    ret void
-; CHECK:       UNREACHABLE:
-; 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:
REACHABLE:
   call void @f()
   ret void
 UNREACHABLE:
   ret void
 DUMMY:
   ret void
 }
 
+; In this specific example, it is still correct to fold %cond.fr into true.
+; This case is unsupported because it is unclear what is the result of
+; isImpliedCondition if LHS is poison or undef.
+; If isImpliedCondition(poison, any value) is true,
+; isImpliedCondition(and true, poison, false) is also true because 'and' propagates poison.
+; However, freeze(and true, poison) does not imply false because the former can
+; be frozen to true. Therefore, we cannot look through the argument of freeze (%cond.fr0)
+; in general under this isImpliedCondition definition.
 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:%.*]]

 }
 
 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 [[A2:%.*]], label [[DUMMY:%.*]]
-; CHECK:       A2:
-; CHECK-NEXT:    [[COND_FR:%.*]] = freeze i1 [[COND1]]
-; CHECK-NEXT:    br i1 [[COND_FR]], label [[REACHABLE:%.*]], label [[UNREACHABLE:%.*]]
+; 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:       UNREACHABLE:
-; 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