[NewGVN] Use performSymbolicEvaluation instead of createExpression.

[fhahn]

Summary

performSymbolicEvaluation is used to obtain the symbolic expression when
visiting instructions and this is used to determine their congruence
class.

performSymbolicEvaluation only creates expressions for certain
instructions (via createExpression). For unsupported instructions,
'unknown' expression are created.

The use of createExpression in processOutgoingEdges means we may
simplify the condition in processOutgoingEdges to a constant in the
initial round of processing, but we use Unknown(I) for the congruence
class. If an operand of I changes the expression Unknown(I) stays the
same, so there is no update the congruence class of I. Hence I won't get
re-visited. So if an operand of I changes in a way that causes
createExpression to return different result, this update is missed.

This patch updates the code to use performSymbolicEvaluation, to be
symmetric with the congruence class updating code.

[fhahn]

ping :)

[fhahn]

Rebase on top of updated D99987

[fhahn]

Rebase after updates to D99987.

[fhahn]

ping :)

[fhahn]

Rebased after landing 2b15262f89bc

[asbirlea]

Minor typos in description.
s/no update the/no update of the
Hence I won't/Hence it won't

Thank you for this!

llvm/test/Transforms/NewGVN/compare-condition-changes.ll

8

What is the purpose of this test? I'm sorry if it's obvious, could you clarify?

[fhahn]

llvm/test/Transforms/NewGVN/compare-condition-changes.ll

8

I'll add a comment when committing. The test case is mostly to check that we handle the case where a non-constant expression is returned and we have to manually set Res.ExtraDep = nullptr. Looking back at now, it should have been added in the earlier patch.

llvm/lib/Transforms/Scalar/NewGVN.cpp

 void NewGVN::processOutgoingEdges(Instruction *TI, BasicBlock *B) {
   // Evaluate reachability of terminator instruction.
   Value *Cond;
   BasicBlock *TrueSucc, *FalseSucc;
   if (match(TI, m_Br(m_Value(Cond), TrueSucc, FalseSucc))) {
     Value *CondEvaluated = findConditionEquivalence(Cond);
     if (!CondEvaluated) {
       if (auto *I = dyn_cast<Instruction>(Cond)) {
-        auto Res = createExpression(I);
-        if (const auto *CE = dyn_cast<ConstantExpression>(Res.Expr)) {
+        SmallPtrSet<Value *, 4> Visited;
+        auto Res = performSymbolicEvaluation(I, Visited);
+        if (const auto *CE = dyn_cast_or_null<ConstantExpression>(Res.Expr)) {
           CondEvaluated = CE->getConstantValue();
           Res.addExtraUserTo(
               [this](Value *V, Value *U) { addAdditionalUsers(V, U); }, I);
         } else {
           // Did not use simplification result, no need to add the extra
           // dependency.
           Res.ExtraDep = nullptr;
         }

llvm/test/Transforms/NewGVN/compare-condition-changes.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -newgvn -S %s | FileCheck %s
+
+; Test cases to make sure the blocks are properly marked as executable, if the
+; state of the branch condition changes.
+
+define i1 @test1() {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CALL:%.*]] = tail call i1 @foo()
+; CHECK-NEXT:    br i1 [[CALL]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    ret i1 true
+; CHECK:       else:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  %call = tail call i1 @foo()
+  br i1 %call, label %then, label %else
+
+then:
+  ret i1 true
+
+else:
+  ret i1 false
+}
+
+declare i1 @foo()
+
+; Make sure state changes are propagated across freeze to branches.
+define void @test2(i1 %c) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
+; CHECK:       loop.header:
+; CHECK-NEXT:    [[P_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[LOOP_LATCH:%.*]] ]
+; CHECK-NEXT:    [[P_1:%.*]] = phi i32 [ 1, [[ENTRY]] ], [ [[P_2:%.*]], [[LOOP_LATCH]] ]
+; CHECK-NEXT:    br label [[LOOP_BB_1:%.*]]
+; CHECK:       loop.bb.1:
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[P_0]], 1
+; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[P_0]], 0
+; CHECK-NEXT:    [[C_1_FREEZE:%.*]] = freeze i1 [[C_1]]
+; CHECK-NEXT:    br i1 [[C_1_FREEZE]], label [[LOOP_BB_2:%.*]], label [[LOOP_LATCH]]
+; CHECK:       loop.bb.2:
+; CHECK-NEXT:    br label [[LOOP_LATCH]]
+; CHECK:       loop.latch:
+; CHECK-NEXT:    [[P_2]] = phi i32 [ 0, [[LOOP_BB_2]] ], [ [[P_1]], [[LOOP_BB_1]] ]
+; CHECK-NEXT:    [[C_2:%.*]] = icmp eq i32 [[P_2]], 123
+; CHECK-NEXT:    br i1 [[C_2]], label [[EXIT:%.*]], label [[LOOP_HEADER]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop.header
+
+loop.header:
+  %p.0 = phi i32 [ 0, %entry ], [ %p.3, %loop.latch ]
+  %p.1 = phi i32 [ 1, %entry ], [ %p.2, %loop.latch ]
+  br label %loop.bb.1
+
+loop.bb.1:
+  %inc = add nsw i32 %p.0, 1
+  %c.1 = icmp slt i32 %p.0, 0
+  %c.1.freeze = freeze i1 %c.1
+  br i1 %c.1.freeze, label %loop.bb.2, label %loop.latch
+
+loop.bb.2:
+  br label %loop.latch
+
+loop.latch:
+  %p.2 = phi i32 [ 0, %loop.bb.2 ], [ %p.1, %loop.bb.1 ]
+  %p.3 = phi i32 [ %inc, %loop.bb.2 ], [ %inc, %loop.bb.1 ]
+  %c.2 = icmp eq i32 %p.2, 123
+  br i1 %c.2, label %exit, label %loop.header
+
+exit:
+  ret void
+}