[llvm] GVN.cpp: Do not swap when both LHS and RHS are arguments.

[hiraditya]

Summary

Prevent swapping of operands when both LHS and RHS are arguments.
Passes llvm regression

[mehdi_amini]

Test?

[hiraditya]

In D18830#393321, @joker.eph wrote:

Test?

I came across this when I was reading the code, as such I do not know how to come up with a test case for this specific case.

[• dberlin]

I don't believe this case is testable, because line 1904 should swap them
back into the right order anyway.
All this patch will do is avoid extra work.

[mcrosier]

In D18830#393392, @dberlin wrote:

I don't believe this case is testable, because line 1904 should swap them
back into the right order anyway.
All this patch will do is avoid extra work.

Am I correct in assuming this LGTY, Daniel?

[• dberlin]

yes.
LGTM

[mehdi_amini]

Oh then it is not even clear if it is worth it (avoid extra work here is doing an extra comparison to avoid a "pointer swap")

[hiraditya]

In D18830#393400, @joker.eph wrote:

Oh then it is not even clear if it is worth it (avoid extra work here is doing an extra comparison to avoid a "pointer swap")

It seems VN.lookupOrAdd only swaps operands based on value numbers. Preferring constants/arguments on RHS seems unrelated to that, although I'm not sure this preference is useful in anyway.

[chandlerc]

Please don't avoid extra work in this way IMO, unless you have a very significant compile time hit due to this.

We have a pervasive reliance on canonicalizing constants to the RHS of binary operations so those should be exceedingly rare anyways. We shouldn't fight that, we should run with it.

My two cents. If Danny, Chad, or others working more on GVN disagree, they can happily override me. =D

[mcrosier]

In D18830#394173, @chandlerc wrote:

My two cents. If Danny, Chad, or others working more on GVN disagree, they can happily override me. =D

FWIW, I don't disagree with Chandler's opinion.

[hiraditya]

In D18830#394173, @chandlerc wrote:

Please don't avoid extra work in this way IMO, unless you have a very significant compile time hit due to this.

We have a pervasive reliance on canonicalizing constants to the RHS of binary operations so those should be exceedingly rare anyways. We shouldn't fight that, we should run with it.

My two cents. If Danny, Chad, or others working more on GVN disagree, they can happily override me. =D

Thanks for the feedback. This patch will not change the order of preference (RHS should keep Constants/Arguments). it only prevents swap when both LHS and RHS are Arguments.

[• dberlin]

I think his point is more the same one i made: "we shouldn't have to swap
at all, and if we do, we should fix that"

[hiraditya]

Please approve the patch, if it looks okay.

Thanks,

[hiraditya]

@dberlin
Please approve the patch if you are fine with it.

Thanks,

[• dberlin]

Chandler explicitly requested we take a different approach, and while I
could overrule him, not sure it's worth it for this patch.
I think we have spent more time on this thank it would take to track down
every place generating it that ends up needing to be swapped and fixing it
at the source

[chandlerc]

What Danny said here.

It feels like this patch is papering over failure to canonicalize. To make
progress we need to either:

a) Show a super clear example where there *is no canonicalization*. That
is, one usage wants one canonicalization and the other wants the other, so
we have to support both. If you can show that we cannot canonicalize this
because it is in tension with other canonicalization, that is exactly the
motivation that folks have asked for to land this patch.

or...

b) Fix everything to canonicalize so this patch isn't necessary.

[hiraditya]

So to generate examples where there are redundant swaps, I used this patch.

--- a/llvm/lib/Transforms/Scalar/GVN.cpp
+++ b/llvm/lib/Transforms/Scalar/GVN.cpp
@@ -1892,8 +1892,13 @@ bool GVN::propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root,
       continue;

     // Prefer a constant on the right-hand side, or an Argument if no constants.
-    if (isa<Constant>(LHS) || (isa<Argument>(LHS) && !isa<Constant>(RHS)))
+    if (isa<Constant>(LHS)
+        || (isa<Argument>(LHS) && !isa<Constant>(RHS))){
       std::swap(LHS, RHS);
+      if (isa<Argument>(LHS) && isa<Argument>(RHS))
+        llvm_unreachable("testcase: swapped once");
+    }
+

Following 7 test cases triggered with this patch:

./bin/opt < llvm/test/Transforms/GVN/2008-07-02-Unreachable.ll -basicaa -gvn -S | grep "ret i8 [%]tmp3"

./bin/opt < llvm/test/Transforms/GVN/2007-07-26-InterlockingLoops.ll -basicaa -gvn -S

./bin/opt < llvm/test/Transforms/GVN/local-pre.ll -gvn -enable-pre -S

./bin/opt < llvm/test/Transforms/GVN/condprop.ll -basicaa -gvn -S

./bin/opt < llvm/test/Transforms/GVN/rle-semidominated.ll -basicaa -gvn -S

./bin/opt < llvm/test/Transforms/GVN/rle.ll -default-data-layout="E-p:32:32:32-p1:16:16:16-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:64:64-n32" -basicaa -gvn -S -die

./bin/opt < llvm/test/Transforms/GVN/rle-nonlocal.ll -basicaa -gvn -S

[chandlerc]

Ok, so this is eliminating swaps. But these are just pointer swaps -- what is the motivation for eliminating them? What does that improve?

llvm/lib/Transforms/Scalar/GVN.cpp

if (LHS == RHS)
       continue;
     assert(LHS->getType() == RHS->getType() && "Equality but unequal types!");
 
     // Don't try to propagate equalities between constants.
     if (isa<Constant>(LHS) && isa<Constant>(RHS))
       continue;
 
     // Prefer a constant on the right-hand side, or an Argument if no constants.
-    if (isa<Constant>(LHS) || (isa<Argument>(LHS) && !isa<Constant>(RHS)))
+    if (isa<Constant>(LHS)
+        || (isa<Argument>(LHS) && !isa<Argument>(RHS) && !isa<Constant>(RHS)))
       std::swap(LHS, RHS);
     assert((isa<Argument>(LHS) || isa<Instruction>(LHS)) && "Unexpected value!");
 
     // If there is no obvious reason to prefer the left-hand side over the
     // right-hand side, ensure the longest lived term is on the right-hand side,
     // so the shortest lived term will be replaced by the longest lived.
     // This tends to expose more simplifications.
     uint32_t LVN = VN.lookupOrAdd(LHS);