[NewGVN] Take in account incoming edges computing congruent PhiExpression(s)

[davide]

Summary

I may be completely off on this one, please bear with me :)
The way we currently define congruency for two PHIExpression(s) is:

1. The operands to the phi functions are congruent
2. The PHIs are defined in the same Basic Block.

The attached testcase contains the following:

patatino:
  %meh = phi i16 [ %0, %winky ], [ %conv1, %tinky ]
  %banana = phi i16 [ %0, %tinky ], [ %conv1, %winky ]
  br label %end

Looking at the NewGVN debug we believe that %meh and %banana are congruent. I don't think they are, in fact this causes a miscompile (you can run the following on the testcase).

Processing instruction   %meh = phi i16 [ %0, %winky ], [ %conv1, %tinky ]
Created new congruence class for   %meh = phi i16 [ %0, %winky ], [ %conv1, %tinky ] using expression { ExpressionTypePhi, opcode = 53, operands = {[0] = i16 %0  [1] = i16 %conv1  } bb = 0x486b1e0} at 10 and leader   %meh = phi i16 [ %0, %winky ], [ %conv1, %tinky ]
New class 10 for expression { ExpressionTypePhi, opcode = 53, operands = {[0] = i16 %0  [1] = i16 %conv1  } bb = 0x486b1e0}
Processing instruction   %banana = phi i16 [ %0, %tinky ], [ %conv1, %winky ]
New class 10 for expression { ExpressionTypePhi, opcode = 53, operands = {[0] = i16 %0  [1] = i16 %conv1  } bb = 0x486b1e0}

[davide@cupiditate bin]$ ./opt -newgvn phi.ll | ./lli
65535
65535
[davide@cupiditate bin]$ ./opt -gvn phi.ll | ./lli
0
65535

I'm under the impression the problem is that we don't take in consideration the incoming edges for congruency. This patch makes sure we only consider congruent phis if the incoming BBs are the same.
If we shouldn't, I'll appreciate suggestions on how to fix alternatively :)

[• dberlin]

I may be completely off on this one, please bear with me :)
The way we currently define congruency for two PHIExpression(s) is:

1. The operands to the phi functions are congruent
2. The PHIs are defined in the same Basic Block.

This is correct. We assume operand order is always the same between phis in the same block.

The attached testcase contains the following:

patatino:
  %meh = phi i16 [ %0, %winky ], [ %conv1, %tinky ]
  %banana = phi i16 [ %0, %tinky ], [ %conv1, %winky ]
  br label %end

So, NewGVN assumes the operands are in the order of predecessors to the block. Or at least, a consistent order.
I believed LLVM always puts them that way.
I'm not sure we are even the only thing that assumes this.
But it's honestly pretty silly to not have that invariant (Otherwise, you have to linearly search phi nodes to find edges from predecessors).

Let's assume it's not true. We should probably make it true. I have trouble seeing a downside. I'm not sure where you would be messing up the edges separately from the phi nodes in a sane way ....
For now, let's fix this NewGVN bug though.

I'm under the impression the problem is that we don't take in consideration the incoming edges for congruency. This patch makes sure we only consider congruent phis if the incoming BBs are the same.

This is the wrong way to do this.
The right way, if we have to, is to always sort them into the same operand order :)

IE sort the operands into pred order before adding them.

It will actually just suffice to sort them in pointer order of the incoming blocks.
The phi nodes of a given bb must have the same incoming blocks.
So the only thing one must do to put them in that order is to sort the incoming blocks into the same order.

It should suffice to do this:
push all operands (use's) into a small vector
sort by getIncomingBlock(Use)
(getIncomingBlock(Use) is constant time)

Add to phi expression in that order.

include/llvm/Transforms/Scalar/GVNExpression.h

503 ↗

(On Diff #98244)

This would actually be wrong.
They are congruent if the same incoming bbs have the same arguments ,and for a given block, the set of incomingbbs is always the same.
The only issue here is the order of the incoming bbs.

[• dberlin]

include/llvm/Transforms/Scalar/GVNExpression.h

503 ↗

(On Diff #98244)

IE the following phis are congruent

phi i16 [0, %foo], [1, %bar]
phi i16 [1, %bar], [0, %foo]

[davide]

In D32990#749362, @dberlin wrote:

I may be completely off on this one, please bear with me :)
The way we currently define congruency for two PHIExpression(s) is:

1. The operands to the phi functions are congruent
2. The PHIs are defined in the same Basic Block.

This is correct. We assume operand order is always the same between phis in the same block.

The attached testcase contains the following:

patatino:
  %meh = phi i16 [ %0, %winky ], [ %conv1, %tinky ]
  %banana = phi i16 [ %0, %tinky ], [ %conv1, %winky ]
  br label %end

So, NewGVN assumes the operands are in the order of predecessors to the block. Or at least, a consistent order.
I believed LLVM always puts them that way.
I'm not sure we are even the only thing that assumes this.
But it's honestly pretty silly to not have that invariant (Otherwise, you have to linearly search phi nodes to find edges from predecessors).

Let's assume it's not true. We should probably make it true. I have trouble seeing a downside. I'm not sure where you would be messing up the edges separately from the phi nodes in a sane way ....

I thought so too. I have a C program that generates this that I'll post/examine independently. I agree it's silly not having a consistent order but this is what we have right now :)

For now, let's fix this NewGVN bug though.

I'm under the impression the problem is that we don't take in consideration the incoming edges for congruency. This patch makes sure we only consider congruent phis if the incoming BBs are the same.

This is the wrong way to do this.
The right way, if we have to, is to always sort them into the same operand order :)

Yes, my bad, this makes much more sense. I'll update the patch.

IE sort the operands into pred order before adding them.

It will actually just suffice to sort them in pointer order of the incoming blocks.
The phi nodes of a given bb must have the same incoming blocks.
So the only thing one must do to put them in that order is to sort the incoming blocks into the same order.

It should suffice to do this:
push all operands (use's) into a small vector
sort by getIncomingBlock(Use)
(getIncomingBlock(Use) is constant time)

Add to phi expression in that order.

[• dberlin]

In D32990#749367, @davide wrote:

In D32990#749362, @dberlin wrote:

I may be completely off on this one, please bear with me :)
The way we currently define congruency for two PHIExpression(s) is:

1. The operands to the phi functions are congruent
2. The PHIs are defined in the same Basic Block.

This is correct. We assume operand order is always the same between phis in the same block.

The attached testcase contains the following:

patatino:
  %meh = phi i16 [ %0, %winky ], [ %conv1, %tinky ]
  %banana = phi i16 [ %0, %tinky ], [ %conv1, %winky ]
  br label %end

So, NewGVN assumes the operands are in the order of predecessors to the block. Or at least, a consistent order.
I believed LLVM always puts them that way.
I'm not sure we are even the only thing that assumes this.
But it's honestly pretty silly to not have that invariant (Otherwise, you have to linearly search phi nodes to find edges from predecessors).

Let's assume it's not true. We should probably make it true. I have trouble seeing a downside. I'm not sure where you would be messing up the edges separately from the phi nodes in a sane way ....

I thought so too. I have a C program that generates this that I'll post/examine independently. I agree it's silly not having a consistent order but this is what we have right now :)

Sigh.

The only reason we have separate phi edge arrays at all right now is because predecessors are slow to access.

(Removing phi arguments in the middle is already not constant time right now anyway, see the comment in removeIncomingValue. We are already doing the thing we would have to do if we didn't store the phi edges)

Otherwise, they are a complete waste of space and time; it would be faster/better to always have them in pred order and make PhiNode->getIncomingBlock(index) == PhiNode->getParent()->getPred(index).

Yes, my bad, this makes much more sense. I'll update the patch.

Thanks!

[davide]

I'll look at the phi node story tomorrow morning early. Between cyclic args and this, they're quickly becoming a bane :)

include/llvm/Transforms/Scalar/GVNExpression.h

503 ↗

(On Diff #98244)

Just one thing, for my understanding. When you say "wrong" you mean that's giving suboptimal answers, right? I think the approach of the original patch is actually too conservative in the sense that we miss some congruences but it should never give wrong results. Am I correct?

[• dberlin]

include/llvm/Transforms/Scalar/GVNExpression.h

503 ↗

(On Diff #98244)

Yes, it will claim phi nodes are not congruent that are.
It should never claim that phi nodes are congruent that aren't.

[davide]

Updated after discussing with Dan.
While you review this, I'll try to find out why LLVM doesn't always pick a consistent order for phis.

[• dberlin]

In D32990#749833, @davide wrote:

Updated after discussing with Dan.
While you review this, I'll try to find out why LLVM doesn't always pick a consistent order for phis.

I can throw it on my list of crap to work out if you have other things to do :)

[efriedma]

llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp

742 ↗

(On Diff #98317)

Is there any possibility that sorting by pointer values here will give non-deterministic output? If there isn't, please add a comment explaining why.

[davide]

llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp

742 ↗

(On Diff #98317)

I thought about this when writing the patch, and I think the answer is no (but I'm nervous when it comes to ordering based on pointers given I tracked down several non-determinism bugs because of these).
As far as I can tell, we don't actually rely on the ordering for anything significant, e.g. we don't create new instructions based on that ordering.
Does this make sense? If so, I'll add a comment. (and thanks for your feedback).

[efriedma]

llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp

742 ↗

(On Diff #98317)

Yes, that makes sense.

[davide]

llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp

742 ↗

(On Diff #98317)

r302566. Thanks.

lib/Transforms/Scalar/NewGVN.cpp

       new (ExpressionAllocator) PHIExpression(PN->getNumOperands(), PHIBlock);
 
   E->allocateOperands(ArgRecycler, ExpressionAllocator);
   E->setType(I->getType());
   E->setOpcode(I->getOpcode());
 
   unsigned PHIRPO = RPOOrdering.lookup(DT->getNode(PHIBlock));
 
+  // NewGVN assumes the operands of a PHI node are in a consistent order across
+  // PHIs. LLVM doesn't seem to always guarantee this. While we need to fix
+  // this in LLVM at some point we don't want GVN to find wrong congruences.
+  // Therefore, here we sort uses in predecessor order.
+  SmallVector<const Use *, 4> PHIOperands;
+  for (const Use &U : PN->operands())
+    PHIOperands.push_back(&U);
+  std::sort(PHIOperands.begin(), PHIOperands.end(),
+            [&](const Use *U1, const Use *U2) {
+              return PN->getIncomingBlock(*U1) < PN->getIncomingBlock(*U2);
+            });
+
   // Filter out unreachable phi operands.
-  auto Filtered = make_filter_range(PN->operands(), [&](const Use &U) {
-    return ReachableEdges.count({PN->getIncomingBlock(U), PHIBlock});
+  auto Filtered = make_filter_range(PHIOperands, [&](const Use *U) {
+    return ReachableEdges.count({PN->getIncomingBlock(*U), PHIBlock});
   });
 
   std::transform(Filtered.begin(), Filtered.end(), op_inserter(E),
-                 [&](const Use &U) -> Value * {
-                   auto *BB = PN->getIncomingBlock(U);
+                 [&](const Use *U) -> Value * {
+                   auto *BB = PN->getIncomingBlock(*U);
                    auto *DTN = DT->getNode(BB);
                    if (RPOOrdering.lookup(DTN) >= PHIRPO)
                      HasBackedge = true;
-                   AllConstant &= isa<UndefValue>(U) || isa<Constant>(U);
+                   AllConstant &= isa<UndefValue>(*U) || isa<Constant>(*U);
 
                    // Don't try to transform self-defined phis.
-                   if (U == PN)
+                   if (*U == PN)
                      return PN;
-                   return lookupOperandLeader(U);
+                   return lookupOperandLeader(*U);
                  });
   return E;
 }
 
 // Set basic expression info (Arguments, type, opcode) for Expression
 // E from Instruction I in block B.
 bool NewGVN::setBasicExpressionInfo(Instruction *I, BasicExpression *E) {
   bool AllConstant = true;

test/Transforms/NewGVN/pr32952.ll

+; PR32952: Don't erroneously consider congruent two phi nodes which
+; have the same arguments but different incoming edges.
+; RUN: opt -newgvn -S %s | FileCheck %s
+
+@a = common global i16 0, align 2
+@.str = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1
+
+define i32 @tinkywinky() {
+entry:
+  %0 = load i16, i16* @a, align 2
+  %conv = sext i16 %0 to i32
+  %neg = xor i32 %conv, -1
+  %conv1 = trunc i32 %neg to i16
+  %conv3 = zext i16 %conv1 to i32
+  %cmp = icmp slt i32 %conv, %conv3
+  br i1 %cmp, label %tinky, label %winky
+
+tinky:
+  store i16 2, i16* @a, align 2
+  br label %patatino
+
+winky:
+  br label %patatino
+
+patatino:
+; CHECK: %meh = phi i16 [ %0, %winky ], [ %conv1, %tinky ]
+; CHECK: %banana = phi i16 [ %0, %tinky ], [ %conv1, %winky ]
+  %meh = phi i16 [ %0, %winky ], [ %conv1, %tinky ]
+  %banana = phi i16 [ %0, %tinky ], [ %conv1, %winky ]
+  br label %end
+
+end:
+; CHECK: %promoted = zext i16 %banana to i32
+; CHECK: %other = zext i16 %meh to i32
+  %promoted = zext i16 %banana to i32
+  %other = zext i16 %meh to i32
+  %first = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %promoted)
+  %second = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %other)
+  ret i32 0
+}
+
+declare i32 @printf(i8*, ...)