[NewGVN] Add phi-of-ops operands if no real PHI is created.

[fhahn]

Summary

If the PHI-of-ops simplifies to an existing value, no real PHI is
created, which means the dependencies between the
PHI-of-ops and its operands is not materialized in IR. At the
moment, we fail to create a real PHI node for the PHI-of-ops,
because the PHI-of-ops root instruction is not re-visited if
one of the PHI-of-ops operands changes. We need to add the
operands as additional users in this case.

Even with this patch, there are still some dependencies
missing. I will continue tackling the outstanding
reporeted crashes in this area.

Fixes PR36501, PR42422, PR42557.

[fhahn]

ping

[fhahn]

ping

[fhahn]

ping

[efriedma]

If nobody else steps up to review, I will, I guess... although I probably won't have time next week.

Some very basic questions to help me get up to speed:

1. It looks like AdditionalUsers is related to the "In order to make the GVN mostly-complete" paragraph in the top of the file? What's the general rule for figuring out whether a given user needs to be marked?
2. It looks like there are currently seven callers of addAdditionalUsers, and this patch brings it up to 8. Do you think with this patch, we've covered all the places that need to call it? Are there any patterns related to addAdditionalUsers which could be refactored?

[fhahn]

Rebased & updated patch to be more targeted; we only need to add the operands as users if we do not create a real PHI node. In that case, the link between operands and PHI-of-ops is not materialized in IR.

In D66924#1852508, @efriedma wrote:

If nobody else steps up to review, I will, I guess... although I probably won't have time next week.

Sorry for not getting back to you sooner Eli!

Some very basic questions to help me get up to speed:

1. It looks like AdditionalUsers is related to the "In order to make the GVN mostly-complete" paragraph in the top of the file? What's the general rule for figuring out whether a given user needs to be marked?

I think the purpose is slightly different and described here: https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Scalar/NewGVN.cpp#L545

I'll try to summarize as I understand it:

NewGVN works by notifying all users of a value, if the number of that value changed (e.g. because there's a new leader or a value to moved to a new CC). The problem with PHI-of-ops is that those are new PHIs that potentially get created along the way. Once we created an actual PHI node for a PHI-of-ops, there is a real IR instruction with real operands, so if any of those operands change, the updates will reach the PHI through the def-use chains in the IR.

But there are cases where we do not create a real PHI node (e.g. because it is not possible at the moment, or because it simplifies to an existing value). In those cases, we need to track values that may cause us to create a real PHI later on. This is done by adding values as 'additional' users of the PHI-of-ops root instruction. The main case is if we cannot find a valid operand for a PHI-of-ops in one of the predecessors. If any of the operands change, we might be able to create a real PHI-of-ops, so we need to re-visit the PHI-of-ops. We need to add the operands as additional users. (line 2735).

In the case this patch fixes, we do not create a real PHI node, because it simplifies to an existing value *at the moment*. No real PHI created means in this case the dependency between the PHI-of-op and its operands is not materialized in the IR. If any of the operands changes later on, we might not be able to simplify the PHI-of-ops to an existing value and we may need to create a real PHI. But in order to do so, we need to be notified once one of the operands to the PHI-of-ops changes. To do so, we need to add the operands as additional users.

2. It looks like there are currently seven callers of addAdditionalUsers, and this patch brings it up to 8. Do you think with this patch, we've covered all the places that need to call it? Are there any patterns related to addAdditionalUsers which could be refactored?

I think there's at least another case we are missing, which is causing https://bugs.llvm.org/show_bug.cgi?id=35074. I'll take another look at the underlying issue there.

I am not sure if there's a way to make this more general, while retaining the original intent. From my previous discussions with Daniel Berlin on this topic, my impression was that we should aim to populate AdditionalUsers as surgical as possible. For example, we could catch most/all issues in this area by always adding all operands of a PHI-of-ops as additional users. But this means we have to process many unnecessary and redundant users in a lot of cases and it effectively hides the places were we fail to track the right dependencies.

After writing all this reasoning up, I also think adding the additional users around lines 2752-2753 is actually unnecessary. But I think that's probably best addressed as follow-up.

[fhahn]

remove individual test files, move to a single test.

[fhahn]

ping :)

[fhahn]

ping :)

[asbirlea]

From my understanding so far, this is the correct approach.
I am going to need a few more days to go over the entire NewGVN pass functionality for the other patches, and I will only be back at work on Monday. Apologies for the delay on this.

llvm/lib/Transforms/Scalar/NewGVN.cpp

for (auto Dep : Deps)
     addAdditionalUsers(Dep, I);
   sortPHIOps(PHIOps);
   auto *E = performSymbolicPHIEvaluation(PHIOps, I, PHIBlock);
   if (isa<ConstantExpression>(E) || isa<VariableExpression>(E)) {
     LLVM_DEBUG(
         dbgs()
         << "Not creating real PHI of ops because it simplified to existing "
            "value or constant\n");
+    // We have leaders for all operands, but do not create a real PHI node with
+    // those leaders as operands, so the link between the operands and the
+    // PHI-of-ops is not materialized in the IR. If any of those leaders
+    // changes, the PHI-of-op may change also, so we need to add the operands as
+    // additional users.
+    for (auto &O : PHIOps)
+      addAdditionalUsers(O.first, I);
+
     return E;
   }
   auto *ValuePHI = RealToTemp.lookup(I);
   bool NewPHI = false;
   if (!ValuePHI) {
     ValuePHI =
         PHINode::Create(I->getType(), OpPHI->getNumOperands(), "phiofops");
     addPhiOfOps(ValuePHI, PHIBlock, I);

llvm/test/Transforms/NewGVN/phi-of-ops-simplified-to-existing-value-then-changes-again.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -newgvn -S %s | FileCheck %s
+
+; Test cases where initially a PHI-of-ops can be simplified to an existing
+; value, but later we need to revisit the decision because the leader of
+; one of the operands used for the simplification changed.
+
+declare void @use(i1)
+
+define void @pr36501(i1 %c) {
+; CHECK-LABEL: @pr36501(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[PHI_1:%.*]] = phi i32 [ -2022207984, [[BB:%.*]] ], [ 0, [[BB7:%.*]] ]
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB3:%.*]], label [[BB2:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[PHI_2:%.*]] = phi i32 [ -1, [[BB2]] ], [ [[PHI_1]], [[BB1]] ]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[PHI_2]], 0
+; CHECK-NEXT:    br i1 [[TMP5]], label [[BB6:%.*]], label [[BB7]]
+; CHECK:       bb6:
+; CHECK-NEXT:    br label [[BB7]]
+; CHECK:       bb7:
+; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i1 [ [[TMP5]], [[BB3]] ], [ true, [[BB6]] ]
+; CHECK-NEXT:    [[PHI_3:%.*]] = phi i32 [ [[PHI_2]], [[BB3]] ], [ 0, [[BB6]] ]
+; CHECK-NEXT:    call void @use(i1 [[PHIOFOPS]])
+; CHECK-NEXT:    br label [[BB1]]
+;
+bb:
+  br label %bb1
+
+bb1:
+  %phi.1 = phi i32 [ -2022207984, %bb ], [ 0, %bb7 ]
+  br i1 %c, label %bb3, label %bb2
+
+bb2:
+  br label %bb3
+
+bb3:
+  %phi.2 = phi i32 [ -1, %bb2 ], [ %phi.1, %bb1 ]
+  %tmp5 = icmp eq i32 %phi.2, 0
+  br i1 %tmp5, label %bb6, label %bb7
+
+bb6:
+  br label %bb7
+
+bb7:                                              ; preds = %bb6, %bb3
+  %phi.3 = phi i32 [ %phi.2, %bb3 ], [ 0, %bb6 ]
+  %tmp9 = icmp eq i32 %phi.3, 0
+  call void @use(i1 %tmp9)
+  br label %bb1
+}
+
+define void @pr42422(i1 %c.1, i1 %c.2) {
+; CHECK-LABEL: @pr42422(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB2:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[TMP:%.*]] = phi i32 [ [[TMP23:%.*]], [[BB22:%.*]] ], [ 0, [[BB1]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp sle i32 [[TMP]], 1
+; CHECK-NEXT:    br i1 [[TMP3]], label [[BB4:%.*]], label [[BB24:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[BB5:%.*]], label [[BB6:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    br label [[BB19:%.*]]
+; CHECK:       bb6:
+; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[BB7:%.*]], label [[BB8:%.*]]
+; CHECK:       bb7:
+; CHECK-NEXT:    br label [[BB16:%.*]]
+; CHECK:       bb8:
+; CHECK-NEXT:    [[TMP9:%.*]] = phi i64 [ [[TMP12:%.*]], [[BB11:%.*]] ], [ 0, [[BB6]] ]
+; CHECK-NEXT:    [[TMP10:%.*]] = icmp sle i64 [[TMP9]], 1
+; CHECK-NEXT:    br i1 [[TMP10]], label [[BB11]], label [[BB13:%.*]]
+; CHECK:       bb11:
+; CHECK-NEXT:    [[TMP12]] = add nsw i64 [[TMP9]], 1
+; CHECK-NEXT:    br label [[BB8]]
+; CHECK:       bb13:
+; CHECK-NEXT:    br i1 true, label [[BB14:%.*]], label [[BB15:%.*]]
+; CHECK:       bb14:
+; CHECK-NEXT:    br label [[BB16]]
+; CHECK:       bb15:
+; CHECK-NEXT:    store i8 undef, i8* null, align 1
+; CHECK-NEXT:    br label [[BB16]]
+; CHECK:       bb16:
+; CHECK-NEXT:    [[TMP17:%.*]] = phi i32 [ undef, [[BB15]] ], [ 1, [[BB14]] ], [ 9, [[BB7]] ]
+; CHECK-NEXT:    switch i32 [[TMP17]], label [[BB19]] [
+; CHECK-NEXT:    i32 0, label [[BB6]]
+; CHECK-NEXT:    i32 9, label [[BB18:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb18:
+; CHECK-NEXT:    br label [[BB19]]
+; CHECK:       bb19:
+; CHECK-NEXT:    [[TMP20:%.*]] = phi i32 [ 0, [[BB18]] ], [ [[TMP17]], [[BB16]] ], [ 1, [[BB5]] ]
+; CHECK-NEXT:    [[TMP21:%.*]] = icmp eq i32 [[TMP20]], 0
+; CHECK-NEXT:    br i1 [[TMP21]], label [[BB22]], label [[BB25:%.*]]
+; CHECK:       bb22:
+; CHECK-NEXT:    [[TMP23]] = add nsw i32 [[TMP]], 1
+; CHECK-NEXT:    br label [[BB2]]
+; CHECK:       bb24:
+; CHECK-NEXT:    br label [[BB25]]
+; CHECK:       bb25:
+; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i1 [ true, [[BB24]] ], [ [[TMP21]], [[BB19]] ]
+; CHECK-NEXT:    [[TMP26:%.*]] = phi i32 [ [[TMP20]], [[BB19]] ], [ 0, [[BB24]] ]
+; CHECK-NEXT:    br i1 [[PHIOFOPS]], label [[BB1]], label [[BB28:%.*]]
+; CHECK:       bb28:
+; CHECK-NEXT:    ret void
+;
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb25, %bb
+  br label %bb2
+
+bb2:                                              ; preds = %bb22, %bb1
+  %tmp = phi i32 [ %tmp23, %bb22 ], [ 0, %bb1 ]
+  %tmp3 = icmp sle i32 %tmp, 1
+  br i1 %tmp3, label %bb4, label %bb24
+
+bb4:                                              ; preds = %bb2
+  br i1 %c.1, label %bb5, label %bb6
+
+bb5:                                              ; preds = %bb4
+  br label %bb19
+
+bb6:                                              ; preds = %bb16, %bb4
+  br i1 %c.2, label %bb7, label %bb8
+
+bb7:                                              ; preds = %bb6
+  br label %bb16
+
+bb8:                                              ; preds = %bb11, %bb6
+  %tmp9 = phi i64 [ %tmp12, %bb11 ], [ 0, %bb6 ]
+  %tmp10 = icmp sle i64 %tmp9, 1
+  br i1 %tmp10, label %bb11, label %bb13
+
+bb11:                                             ; preds = %bb8
+  %tmp12 = add nsw i64 %tmp9, 1
+  br label %bb8
+
+bb13:                                             ; preds = %bb8
+  br i1 true, label %bb14, label %bb15
+
+bb14:                                             ; preds = %bb13
+  br label %bb16
+
+bb15:                                             ; preds = %bb13
+  br label %bb16
+
+bb16:                                             ; preds = %bb15, %bb14, %bb7
+  %tmp17 = phi i32 [ undef, %bb15 ], [ 1, %bb14 ], [ 9, %bb7 ]
+  switch i32 %tmp17, label %bb19 [
+  i32 0, label %bb6
+  i32 9, label %bb18
+  ]
+
+bb18:                                             ; preds = %bb16
+  br label %bb19
+
+bb19:                                             ; preds = %bb18, %bb16, %bb5
+  %tmp20 = phi i32 [ 0, %bb18 ], [ %tmp17, %bb16 ], [ 1, %bb5 ]
+  %tmp21 = icmp eq i32 %tmp20, 0
+  br i1 %tmp21, label %bb22, label %bb25
+
+bb22:                                             ; preds = %bb19
+  %tmp23 = add nsw i32 %tmp, 1
+  br label %bb2
+
+bb24:                                             ; preds = %bb2
+  br label %bb25
+
+bb25:                                             ; preds = %bb24, %bb19
+  %tmp26 = phi i32 [ %tmp20, %bb19 ], [ 0, %bb24 ]
+  %tmp27 = icmp eq i32 %tmp26, 0
+  br i1 %tmp27, label %bb1, label %bb28
+
+bb28:                                             ; preds = %bb25
+  ret void
+}
+
+define void @PR42557(i32 %tmp6, i1 %c.1, i1 %c.2) {
+; CHECK-LABEL: @PR42557(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP:%.*]] = phi i32 [ 0, [[BB:%.*]] ], [ [[TMP6:%.*]], [[BB1]] ]
+; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[BB2:%.*]], label [[BB1]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[BB16:%.*]], label [[BB11:%.*]]
+; CHECK:       bb16:
+; CHECK-NEXT:    [[TMP17:%.*]] = add i32 [[TMP]], 1
+; CHECK-NEXT:    br label [[BB11]]
+; CHECK:       bb11:
+; CHECK-NEXT:    [[TMP12:%.*]] = phi i32 [ [[TMP17]], [[BB16]] ], [ 0, [[BB2]] ]
+; CHECK-NEXT:    [[TMP13:%.*]] = icmp eq i32 [[TMP12]], 0
+; CHECK-NEXT:    call void @use(i1 [[TMP13]])
+; CHECK-NEXT:    [[TMP15:%.*]] = icmp ne i32 [[TMP]], 0
+; CHECK-NEXT:    br i1 [[TMP15]], label [[BB18:%.*]], label [[BB19:%.*]]
+; CHECK:       bb18:
+; CHECK-NEXT:    br label [[BB19]]
+; CHECK:       bb19:
+; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i1 [ [[TMP13]], [[BB11]] ], [ false, [[BB18]] ]
+; CHECK-NEXT:    [[TMP20:%.*]] = phi i32 [ [[TMP12]], [[BB11]] ], [ 1, [[BB18]] ]
+; CHECK-NEXT:    call void @use(i1 [[PHIOFOPS]])
+; CHECK-NEXT:    ret void
+;
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb1, %bb
+  %tmp = phi i32 [ 0, %bb ], [ %tmp6, %bb1 ]
+  br i1 %c.1, label %bb2, label %bb1
+
+bb2:                                              ; preds = %bb1
+  br i1 %c.2, label %bb16, label %bb11
+
+bb16:                                             ; preds = %bb2
+  %tmp17 = add i32 %tmp, 1
+  br label %bb11
+
+bb11:                                             ; preds = %bb16, %bb2
+  %tmp12 = phi i32 [ %tmp17, %bb16 ], [ 0, %bb2 ]
+  %tmp13 = icmp eq i32 %tmp12, 0
+  call void @use(i1 %tmp13)
+  %tmp15 = icmp ne i32 %tmp, 0
+  br i1 %tmp15, label %bb18, label %bb19
+
+bb18:                                             ; preds = %bb11
+  br label %bb19
+
+bb19:                                             ; preds = %bb18, %bb11
+  %tmp20 = phi i32 [ %tmp12, %bb11 ], [ 1, %bb18 ]
+  %tmp21 = icmp eq i32 %tmp20, 0
+  call void @use(i1 %tmp21)
+  ret void
+}