[NewGVN] Disable SelfLookup optimization to ensure termination #82162
+120
−4
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
@llvm/pr-subscribers-llvm-transforms Author: None (ManuelJBrito) ChangesWhen creating PHI expressions, NewGVN ignores operands whose leader is the PHI itself. This allows NewGVN to discover and propagate loop-invariants. Example:
If Leader(%a.1) = %a then %a simplifies to 1. However, if we consider the class {%a, %a.1, %b}:
The optimization is not performed because %b is not the class leader, although we know that %a.1 and %b are equivalent. This becomes problematic in mutually dependent PHIs, as NewGVN repeatedly performs and undoes the optimization without converging (see pr60439.ll ). This patch changes the optimization to trigger whenever the phi and the operand are in the same congruence class. Fixes #33820 and fixes #60439. Full diff: https://github.com/llvm/llvm-project/pull/82162.diff 3 Files Affected:
diff --git a/llvm/lib/Transforms/Scalar/NewGVN.cpp b/llvm/lib/Transforms/Scalar/NewGVN.cpp
index 19ac9526b5f88b..f225515c99cef2 100644
--- a/llvm/lib/Transforms/Scalar/NewGVN.cpp
+++ b/llvm/lib/Transforms/Scalar/NewGVN.cpp
@@ -1020,6 +1020,9 @@ PHIExpression *NewGVN::createPHIExpression(ArrayRef<ValPair> PHIOperands,
E->setType(PHIOperands.begin()->first->getType());
E->setOpcode(Instruction::PHI);
+ auto *IClass = ValueToClass.lookup(I);
+ bool realPhi = isa<PHINode>(I);
+
// Filter out unreachable phi operands.
auto Filtered = make_filter_range(PHIOperands, [&](const ValPair &P) {
auto *BB = P.second;
@@ -1033,8 +1036,23 @@ PHIExpression *NewGVN::createPHIExpression(ArrayRef<ValPair> PHIOperands,
return false;
OriginalOpsConstant = OriginalOpsConstant && isa<Constant>(P.first);
HasBackedge = HasBackedge || isBackedge(BB, PHIBlock);
- return lookupOperandLeader(P.first) != I;
+
+ // Ignore phi arguments that are known to be equivalent to the phi. Only
+ // done for real PHIs (PHIOfOps may not converge).
+ bool selfLookup = realPhi && isa<PHINode>(P.first) &&
+ ValueToClass.lookup(P.first) == IClass;
+
+ return !selfLookup;
});
+
+ // Empty means that all operands are either unreachable or equivalent to the
+ // phi. Return the previous leader. Don't return a dead expression; it makes
+ // mutually dependent phis never converge.
+ if (Filtered.empty()) {
+ E->op_push_back(IClass->getLeader());
+ return E;
+ }
+
std::transform(Filtered.begin(), Filtered.end(), op_inserter(E),
[&](const ValPair &P) -> Value * {
return lookupOperandLeader(P.first);
diff --git a/llvm/test/Transforms/NewGVN/pr33820.ll b/llvm/test/Transforms/NewGVN/pr33820.ll
new file mode 100644
index 00000000000000..e8a8bc99c9d1dd
--- /dev/null
+++ b/llvm/test/Transforms/NewGVN/pr33820.ll
@@ -0,0 +1,79 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 3
+; RUN: opt -S < %s -passes=newgvn | FileCheck %s
+
+define void @hoge(i1 %c1, i1 %c2, i1 %c3, i1 %c4) {
+; CHECK-LABEL: define void @hoge(
+; CHECK-SAME: i1 [[C1:%.*]], i1 [[C2:%.*]], i1 [[C3:%.*]], i1 [[C4:%.*]]) {
+; CHECK-NEXT: bb:
+; CHECK-NEXT: br label [[BB1:%.*]]
+; CHECK: bb1:
+; CHECK-NEXT: [[TMP:%.*]] = phi i8 [ [[TMP3:%.*]], [[BB12:%.*]] ], [ 0, [[BB:%.*]] ]
+; CHECK-NEXT: br i1 [[C1]], label [[BB2:%.*]], label [[BB13:%.*]]
+; CHECK: bb2:
+; CHECK-NEXT: [[TMP3]] = phi i8 [ [[TMP]], [[BB1]] ], [ [[TMP5:%.*]], [[BB4:%.*]] ]
+; CHECK-NEXT: br i1 [[C2]], label [[BB12]], label [[BB4]]
+; CHECK: bb4:
+; CHECK-NEXT: [[TMP5]] = phi i8 [ [[TMP3]], [[BB2]] ], [ [[TMP7:%.*]], [[BB11:%.*]] ]
+; CHECK-NEXT: br i1 false, label [[BB6:%.*]], label [[BB2]]
+; CHECK: bb6:
+; CHECK-NEXT: [[TMP7]] = phi i8 [ poison, [[BB4]] ], [ [[TMP10:%.*]], [[BB9:%.*]] ]
+; CHECK-NEXT: br i1 [[C3]], label [[BB11]], label [[BB8:%.*]]
+; CHECK: bb8:
+; CHECK-NEXT: br i1 true, label [[BB8]], label [[BB9]]
+; CHECK: bb9:
+; CHECK-NEXT: [[TMP10]] = phi i8 [ [[TMP16:%.*]], [[BB15:%.*]] ], [ poison, [[BB8]] ]
+; CHECK-NEXT: br label [[BB6]]
+; CHECK: bb11:
+; CHECK-NEXT: br label [[BB4]]
+; CHECK: bb12:
+; CHECK-NEXT: br label [[BB1]]
+; CHECK: bb13:
+; CHECK-NEXT: br i1 [[C4]], label [[BB14:%.*]], label [[BB15]]
+; CHECK: bb14:
+; CHECK-NEXT: br label [[BB15]]
+; CHECK: bb15:
+; CHECK-NEXT: [[TMP16]] = phi i8 [ [[TMP]], [[BB13]] ], [ 9, [[BB14]] ]
+; CHECK-NEXT: br label [[BB9]]
+;
+bb:
+br label %bb1
+
+bb1: ; preds = %bb12, %bb
+%tmp = phi i8 [ %tmp3, %bb12 ], [ 0, %bb ]
+br i1 %c1, label %bb2, label %bb13
+
+bb2: ; preds = %bb4, %bb1
+%tmp3 = phi i8 [ %tmp, %bb1 ], [ %tmp5, %bb4 ]
+br i1 %c2, label %bb12, label %bb4
+
+bb4: ; preds = %bb11, %bb2
+%tmp5 = phi i8 [ %tmp3, %bb2 ], [ %tmp7, %bb11 ]
+br i1 false, label %bb6, label %bb2
+
+bb6: ; preds = %bb9, %bb4
+%tmp7 = phi i8 [ %tmp5, %bb4 ], [ %tmp10, %bb9 ]
+br i1 %c3, label %bb11, label %bb8
+
+bb8: ; preds = %bb8, %bb6
+br i1 true, label %bb8, label %bb9
+
+bb9: ; preds = %bb15, %bb8
+%tmp10 = phi i8 [ %tmp16, %bb15 ], [ %tmp7, %bb8 ]
+br label %bb6
+
+bb11: ; preds = %bb6
+br label %bb4
+
+bb12: ; preds = %bb2
+br label %bb1
+
+bb13: ; preds = %bb1
+br i1 %c4, label %bb14, label %bb15
+
+bb14: ; preds = %bb13
+br label %bb15
+
+bb15: ; preds = %bb14, %bb13
+%tmp16 = phi i8 [ %tmp, %bb13 ], [ 9, %bb14 ]
+br label %bb9
+}
diff --git a/llvm/test/Transforms/NewGVN/pr60439.ll b/llvm/test/Transforms/NewGVN/pr60439.ll
new file mode 100644
index 00000000000000..476cc2ce8d58a1
--- /dev/null
+++ b/llvm/test/Transforms/NewGVN/pr60439.ll
@@ -0,0 +1,32 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 3
+; RUN: opt -S < %s -passes=newgvn | FileCheck %s
+define i32 @function_1(i1 %arg, i1 %bc ) {
+; CHECK-LABEL: define i32 @function_1(
+; CHECK-SAME: i1 [[ARG:%.*]], i1 [[BC:%.*]]) {
+; CHECK-NEXT: entry_1:
+; CHECK-NEXT: br i1 [[BC]], label [[BB_5:%.*]], label [[BB_6:%.*]]
+; CHECK: bb_5:
+; CHECK-NEXT: br label [[BB_6]]
+; CHECK: bb_6:
+; CHECK-NEXT: [[A:%.*]] = phi i1 [ [[ARG]], [[BB_5]] ], [ [[A]], [[BB_4:%.*]] ], [ true, [[ENTRY_1:%.*]] ]
+; CHECK-NEXT: br label [[BB_4]]
+; CHECK: bb_4:
+; CHECK-NEXT: br i1 [[ARG]], label [[BB_6]], label [[BB_4]]
+;
+entry_1:
+ br i1 %bc, label %bb_5, label %bb_6
+
+bb_5:
+ br label %bb_6
+
+bb_6:
+ %a = phi i1 [ %arg, %bb_5 ], [ %a.1, %bb_4 ], [ 1, %entry_1 ]
+ %c = phi i1 [ %arg, %bb_5 ], [ %c.1, %bb_4 ], [ 1, %entry_1 ]
+ br label %bb_4
+
+
+bb_4:
+ %a.1 = phi i1 [ %a.1, %bb_4 ], [ %a, %bb_6 ]
+ %c.1 = phi i1 [ %c.1, %bb_4 ], [ %c, %bb_6 ]
+ br i1 %arg, label %bb_6, label %bb_4
+}
|
|
There are 3 failing tests in the build bots:
|
nunoplopes
reviewed
Feb 18, 2024
ManuelJBrito
force-pushed
the
selfLookup
branch
from
33a2bdf to
27ef9ed
Compare
ManuelJBrito
changed the title
|
To support this optimization, we need to perform SCC leader invalidation, i.e., prevent the existence of cyclic dependencies induced by leaders. For now, I will disable this optimization. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
When creating PHI expressions, NewGVN ignores operands whose leader is the PHI itself. This allows NewGVN to discover and propagate loop-invariants.
Example:
%a = phi i1 [%a.1, %bb] , [1, %entry]If Leader(%a.1) = %a then %a simplifies to 1.
However, if we consider the class {%a, %a.1, %b}:
%b = phi i1 [%a.1, %bb] , [1, %entry]The optimization is not performed because %b is not the class leader, although we know that %a.1 and %b are equivalent. This becomes problematic in mutually dependent PHIs, as NewGVN repeatedly performs and undoes the optimization without converging (see pr60439.ll ).
To fix this, we need to prevent cycles by invalidating leaders that cause them. For now, this patch disables the optimization.
Fixes #33820 and fixes #60439.