[LazyValueInfo] Let getEdgeValueLocal look into freeze instructions

[aqjune]

Summary

This patch makes getEdgeValueLocal more precise when a freeze instruction is
given, by adding support for freeze into constantFoldUser

[efriedma]

Which of the changes in the patch corresponds to each testcase?

[nikic]

llvm/lib/Analysis/LazyValueInfo.cpp

1316

Wouldn't we expect such a freeze to get dropped by InstSimplify/InstCombine anyway?

[efriedma]

llvm/lib/Analysis/LazyValueInfo.cpp

1316

You mean, we should rewrite uses of a freeze in blocks where we know the operand of the freeze can't be undef/poison? I guess that's something we should do. I don't think instsimplify has the context necessary to do that sort of rewrite.

[nikic]

llvm/lib/Analysis/LazyValueInfo.cpp

1316

You're right, if there are multiple uses and only some are dominated by the condition we currently don't handle it in InstCombine. The @simple case from the test would be handled though, because the freeze gets sunk.

[aqjune]

getEdgeValueLocal's change at if (BranchInst *BI ...) { .. } corresponds to the simple example.
For the switch example, if (SwitchInst *SI ...) { ... } branch calls constantFoldUser, which is newly updated.

llvm/lib/Analysis/LazyValueInfo.cpp

1316

Would it be the right direction if I implement this optimization in InstCombine instead?

[aqjune]

Since D84940 can introduce freezes, this patch can be effective now IMO.

[nikic]

llvm/lib/Analysis/LazyValueInfo.cpp

1316

Is this code actually needed? I'm thinking that the constantFoldUser code should already take care of it. The Freeze usesOperand Condition, and should then get folded.

[aqjune]

Remove redundant check

[aqjune]

llvm/lib/Analysis/LazyValueInfo.cpp

1316

The check seemed redundant to me as well, so removed it. The unit tests still work too.

[efriedma]

LGTM

llvm/lib/Analysis/LazyValueInfo.cpp

 //===- LazyValueInfo.cpp - Value constraint analysis ------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //

 }
 
 // Return true if Usr has Op as an operand, otherwise false.
 static bool usesOperand(User *Usr, Value *Op) {
   return find(Usr->operands(), Op) != Usr->op_end();
 }
 
 // Return true if the instruction type of Val is supported by
-// constantFoldUser(). Currently CastInst and BinaryOperator only.  Call this
-// before calling constantFoldUser() to find out if it's even worth attempting
-// to call it.
+// constantFoldUser(). Currently CastInst, BinaryOperator and FreezeInst only.
+// Call this before calling constantFoldUser() to find out if it's even worth
+// attempting to call it.
 static bool isOperationFoldable(User *Usr) {
-  return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr);
+  return isa<CastInst>(Usr) || isa<BinaryOperator>(Usr) || isa<FreezeInst>(Usr);
 }
 
 // Check if Usr can be simplified to an integer constant when the value of one
 // of its operands Op is an integer constant OpConstVal. If so, return it as an
 // lattice value range with a single element or otherwise return an overdefined
 // lattice value.
 static ValueLatticeElement constantFoldUser(User *Usr, Value *Op,
                                             const APInt &OpConstVal,
if (auto *CI = dyn_cast<CastInst>(Usr)) {
     assert((Op0Match || Op1Match) &&
            "Operand 0 nor Operand 1 isn't a match");
     Value *LHS = Op0Match ? OpConst : BO->getOperand(0);
     Value *RHS = Op1Match ? OpConst : BO->getOperand(1);
     if (auto *C = dyn_cast_or_null<ConstantInt>(
             SimplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) {
       return ValueLatticeElement::getRange(ConstantRange(C->getValue()));
     }
+  } else if (auto *FI = dyn_cast<FreezeInst>(Usr)) {
+    assert(FI->getOperand(0) == Op && "Operand 0 isn't Op");
+    return ValueLatticeElement::getRange(ConstantRange(OpConstVal));
   }
   return ValueLatticeElement::getOverdefined();
 }
 
 /// Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
 /// Val is not constrained on the edge.  Result is unspecified if return value
 /// is false.
 static Optional<ValueLatticeElement> getEdgeValueLocal(Value *Val,
                                                        BasicBlock *BBFrom,
                                                        BasicBlock *BBTo) {
   // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
   // know that v != 0.
   if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
     // If this is a conditional branch and only one successor goes to BBTo, then
     // we may be able to infer something from the condition.
     if (BI->isConditional() &&
         BI->getSuccessor(0) != BI->getSuccessor(1)) {
       bool isTrueDest = BI->getSuccessor(0) == BBTo;
       assert(BI->getSuccessor(!isTrueDest) == BBTo &&
              "BBTo isn't a successor of BBFrom");
       Value *Condition = BI->getCondition();
 
       // If V is the condition of the branch itself, then we know exactly what
       // it is.
-      if (Condition == Val)
+      // Since it is used as a branch conditional, Condition cannot be undef
+      // or poison. Exploit this to strip freeze from Val.
+      if (Condition == Val ||
+          (isa<FreezeInst>(Val) &&
+           Condition == cast<FreezeInst>(Val)->getOperand(0)))
         return ValueLatticeElement::get(ConstantInt::get(
                               Type::getInt1Ty(Val->getContext()), isTrueDest));
 
       // If the condition of the branch is an equality comparison, we may be
       // able to infer the value.
       ValueLatticeElement Result = getValueFromCondition(Val, Condition,
                                                          isTrueDest);
       if (!Result.isOverdefined())

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
   br i1 %cond, label %A, label %EXIT
 A:
   br i1 %cond.fr, label %B, label %EXIT
 B:
   call void @f()
   ret i32 1
 EXIT:
   ret i32 0
 }
 
 define void @switch(i32 %cond) {
 ; CHECK-LABEL: @switch(
 ; CHECK-NEXT:  ENTRY:
 ; CHECK-NEXT:    [[COND_FR:%.*]] = freeze i32 [[COND:%.*]]
 ; CHECK-NEXT:    switch i32 [[COND]], label [[DEFAULT:%.*]] [
-; CHECK-NEXT:    i32 0, label [[A:%.*]]
-; CHECK-NEXT:    i32 1, label [[B:%.*]]
+; CHECK-NEXT:    i32 0, label [[A_TAKEN:%.*]]
+; CHECK-NEXT:    i32 1, label [[B_TAKEN:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       DEFAULT:
 ; CHECK-NEXT:    switch i32 [[COND_FR]], label [[PRESERVED1:%.*]] [
 ; CHECK-NEXT:    i32 0, label [[PRESERVED2:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       PRESERVED1:
 ; CHECK-NEXT:    call void @f()
 ; CHECK-NEXT:    ret void
 ; CHECK:       PRESERVED2:
 ; CHECK-NEXT:    call void @f2()
 ; CHECK-NEXT:    ret void
-; CHECK:       A:
-; CHECK-NEXT:    switch i32 [[COND_FR]], label [[A_NOTTAKEN:%.*]] [
-; CHECK-NEXT:    i32 0, label [[A_TAKEN:%.*]]
-; CHECK-NEXT:    ]
 ; CHECK:       A_TAKEN:
 ; CHECK-NEXT:    call void @f()
 ; CHECK-NEXT:    ret void
-; CHECK:       A_NOTTAKEN:
-; CHECK-NEXT:    call void @f2()
-; CHECK-NEXT:    ret void
-; CHECK:       B:
-; CHECK-NEXT:    switch i32 [[COND_FR]], label [[B_TAKEN:%.*]] [
-; CHECK-NEXT:    i32 0, label [[B_NOTTAKEN:%.*]]
-; CHECK-NEXT:    ]
 ; CHECK:       B_TAKEN:
 ; CHECK-NEXT:    call void @f()
 ; CHECK-NEXT:    ret void
-; CHECK:       B_NOTTAKEN:
-; CHECK-NEXT:    call void @f2()
-; CHECK-NEXT:    ret void
 ;
 ENTRY:
   %cond.fr = freeze i32 %cond
   switch i32 %cond, label %DEFAULT [
   i32 0, label %A
   i32 1, label %B
   ]
 DEFAULT: