[InstrSimplify,NewGVN] Add option to ignore additional instr info when simplifying.

[fhahn]

Summary

NewGVN uses InstructionSimplify for simplifications of leaders of
congruence classes. It is not guaranteed that the metadata or other
flags/keywords (like nsw or exact) of the leader is available for all members
in a congruence class, so we cannot use it for simplification.

This patch adds a InstrInfoQuery struct with a boolean field
UseInstrInfo (which defaults to true to keep the current behavior as
default) and a set of helper methods to get metadata/keywords for a
given instruction, if UseInstrInfo is true. The whole thing might need a
better name, to avoid confusion with TargetInstrInfo but I am not sure
what a better name would be.

The current patch threads through InstrInfoQuery to the required
places, which is messier then it would need to be, if
InstructionSimplify and ValueTracking would share the same Query struct.

The reason I added it as a separate struct is that it can be shared
between InstructionSimplify and ValueTracking's query objects. Also,
some places do not need a full query object, just the InstrInfoQuery.

It also updates some interfaces that do not take a Query object, but a
set of optional parameters to take an additional boolean UseInstrInfo.

See https://bugs.llvm.org/show_bug.cgi?id=37540.

[fhahn]

We could probably do something more clever and propagate the nonnull metadata, if we can ensure that nothing in between can change the nonnullness.

[nikic]

This is going to affect more than only nonnull metadata. For example the same issue can also be reproduced using range metadata:

define i1 @test(i32* %arg, i1 %arg2) {
    br i1 %arg2, label %bb1, label %bb2

bb1:
    %load1 = load i32, i32* %arg
    %cmp1 = icmp eq i32 %load1, 0 
    ret i1 %cmp1

bb2:
    %load2 = load i32, i32* %arg, !range !1
    %cmp2 = icmp eq i32 %load2, 0 
    ret i1 %cmp2
}

!1 = !{ i32 1, i32 10 }

[• dberlin]

Hey Florian,
Thanks for looking at this:
IMHO, We should be storing and hashing/comparing the relevant info in the loadexpression (IE store a bit that it's nonnull)
I really do not want to end up with complex business logic in the equals function, that's a thing the callers should be worrying about.

[• dberlin]

Yeah, some of this metadata travels backwards in time (IE if you can prove they are equivalent, the metadata must apply) and some of it is not.

This is the moral equivalent of some of the GVN bugs we also have where we use things we discover later to prove earlier things.

[fhahn]

In D47143#1106573, @dberlin wrote:

Hey Florian,
Thanks for looking at this:
IMHO, We should be storing and hashing/comparing the relevant info in the loadexpression (IE store a bit that it's nonnull)
I really do not want to end up with complex business logic in the equals function, that's a thing the callers should be worrying about.

Will do thanks. As @nikic mentioned we have to account for more than nonnull, which I'll do once nonnull is dealt with properly.

[• dberlin]

So, actually, this *is* a variant the same issue we have elsewhere with Simplify* (and there are a few newgvn bugs open about it). These actually *are* congruent, we just don't want it simplifying this hard.

I don't think you want to say these are non-congruent, because you can in fact replace load2 with load1 and load1 with load2, we would just merge metadata.
I think we want to be able to tell it what information it's allowed to use when simplifying.

I believe NewGVN is always going to be able to discover things that will be confusing to the simplifier as long as the simplifier is doing super-complex IR walking and understanding.

[fhahn]

In D47143#1106580, @dberlin wrote:

So, actually, this *is* a variant the same issue we have elsewhere with Simplify* (and there are a few newgvn bugs open about it). These actually *are* congruent, we just don't want it simplifying this hard.

I don't think you want to say these are non-congruent, because you can in fact replace load2 with load1 and load1 with load2, we would just merge metadata.
I think we want to be able to tell it what information it's allowed to use when simplifying.

Right, that was what I thought initially as well. We should be better off if we manage to limit simplifications. Unfortunately, there seems to be no option to ignore certain metadata by Simplify*. I suppose we could drop the metadata before we pass instructions to Simplify or maintain a set merged metadata for the congruence classes and use that when passing an instruction to Simplify*. The latter would still allow us to use the nonnull metadata for example, if all members have it, but it may not be worth maintaining a set of merged metadata...

Or do you think it would be better to teach Simplify* to ignore (some) metadata? This seems like a non-trivial change.

What do you think?

[• dberlin]

One of the reasons i moved Simplify* to take a SimplifyQuery is so that things like this are possible to add without a tremendous amount of work in Simplify*.

Part of me thinks anything else would be too fragile, but i'm open to ideas.
We are basically using it as a more advanced constant folder that does some reassociation and simplification.

[nikic]

@fhahn It's probably not feasible to remove metadata or explicitly pass merged metadata as the relevant metadata may be somewhere further up the chain. E.g. we might not be looking at ICmp(Load, null) but at something like ICmp(BitCast(GEP(Load)), null), which will probably be subject to the same issues, as these checks are recursive.

Having the option to ignore metadata (or maybe have a lambda that determines whether metadata can be used, e.g. based on common metadata in all members of the congruence, or because of a dominating leader) sounds like a more robust solution.

[• dberlin]

Right, this is why we haven't done anything yet past taht - i ran out of time to start driving through a real plan :)

[nikic]

For reference, another bug relating to NewGVN + Simplify is https://bugs.llvm.org/show_bug.cgi?id=34093. In that case it's not a matter of metadata, but an equivalence that was established based on predicateinfo is assumed to hold prior to the corresponding ssa.copy, resulting in incorrect simplification.

https://bugs.llvm.org/show_bug.cgi?id=31792 is not a miscompile but rather a missed optimization. GVN knows that two GEPs reference the same base, but simplification doesn't.

I'm finding it hard to put these three issues under one umbrella. They all need some kind of additional interaction with simplification to be resolved, but the specifics seem to be quite different in each case, it's not just a matter of a single flag.

[• dberlin]

Sure, you will never find a single flag to control all of this, my goal was to be able to have flags at all to control the various issues.

(the alternative is to move back to ConstantFold* instead of Simplify*, which would require reimplementing our own simplification and reassociation stuff that we care about.)

[fhahn]

Thanks for the excellent feedback. I'll look into teaching Simplify* to skip (some) metadata

[• dberlin]

SGTM.
If it turns out to be way too ugly. let's circle back and figure out what
we want to do.

[fhahn]

Updated to ignore metadata while simplifying with InstructionSimplify. I've updated the description with details.

It adds a very crude way to disable the use of metadata. Not sure if we want a more fine grained approach. The cosmetics of the UseMetadata handling can be improved slightly, happy to do that if the overall approach is sensible.

[fhahn]

ping

[fhahn]

ping. This introduces a way to prevent InstructionSimplify from using metadata when simplifying for NewGVN. This fixes a correctness problem, where we currently make a simplification based on metadata of the leader, which not necessarily is available for all instructions in a congruence class. Any feedback on the general approach would be great.

[efriedma]

Is this supposed to apply specifically to metadata, or just anything that NewGVN doesn't consider while numbering? Some InstSimplify transforms check, for example, nsw.

You need to make sure you don't call into other places that might query metadata. It looks like you caught isKnownNonEqual/isKnownNonZero, but there's also computeKnownBits and isKnownToBeAPowerOfTwo.

[fhahn]

In D47143#1174501, @efriedma wrote:

Is this supposed to apply specifically to metadata, or just anything that NewGVN doesn't consider while numbering? Some InstSimplify transforms check, for example, nsw.

I think we cannot use anything for simplification that's not available for all members of a congruence class. Thanks for pointing me to nsw, I'll have a look and see how to best generalize this.

You need to make sure you don't call into other places that might query metadata. It looks like you caught isKnownNonEqual/isKnownNonZero, but there's also computeKnownBits and isKnownToBeAPowerOfTwo.

Ah yes thanks! Unfortunately there's quite a big set of functions to cover. If this kind of interface makes sense, I'll take another close look.

[fhahn]

I've updated the patch to have a query object which provides convenience wrappers around getMetadata, hasNo* and isExact, which return conservative results if it's not safe to use any of those. I've also threaded this through at a lot more places and added a few test cases with nsw/exact.

I also updated the title and the description with more details. What do you think of the overall approach? There is some refactoring which might make this slightly less invasive, as using the function versions that take a Query object everywhere internally in ValueTracking.cpp/InstructionSimplify.cpp

[fhahn]

ping

[hiraditya]

LGTM with the minor nit.

include/llvm/Analysis/InstructionSimplify.h

85 ↗

(On Diff #158525)

I see other places use isa to first check if BinaryOperator isa PossiblyExactOperator , or a dyn_cast maybe.

[fhahn]

In D47143#1199218, @hiraditya wrote:

LGTM with the minor nit.

Thanks for having a look!

I went through the list of outstanding NewGVN issues today and the issue fixed in this patch was causing 3-4 reported miscompiles with NewGVN. Unfortunately there are some cases where we could still use metadata while simplifying (e.g. if all members of the congruence class have the same metadata), but I don't see a sane way of ensuring that (e.g. new members without metadata could be added to a class after we simplified the leader).

include/llvm/Analysis/InstructionSimplify.h

85 ↗

(On Diff #158525)

Will update before committing, thanks!

[hiraditya]

Accepting because there are no alternate suggestions, and this patch fixes miscompiles preventing NewGVN to be used in some cases.

lib/Transforms/Scalar/NewGVN.cpp

 template <typename T>
 static bool equalsLoadStoreHelper(const T &LHS, const Expression &RHS) {
   if (!isa<LoadExpression>(RHS) && !isa<StoreExpression>(RHS))
     return false;
   return LHS.MemoryExpression::equals(RHS);
 }
 
 bool LoadExpression::equals(const Expression &Other) const {
-  return equalsLoadStoreHelper(*this, Other);
+  if (!equalsLoadStoreHelper(*this, Other))
+    return false;
+  // Check that the nonnull metadata agrees.
+  if (const auto *L = dyn_cast<LoadExpression>(&Other))
+    return Load->getMetadata(LLVMContext::MD_nonnull) ==
+           L->Load->getMetadata(LLVMContext::MD_nonnull);
+  return true;
 }
 
 bool StoreExpression::equals(const Expression &Other) const {
   if (!equalsLoadStoreHelper(*this, Other))
     return false;
   // Make sure that store vs store includes the value operand.
   if (const auto *S = dyn_cast<StoreExpression>(&Other))
     if (getStoredValue() != S->getStoredValue())

test/Transforms/NewGVN/load-nonnull.ll

+; RUN: opt < %s -S -newgvn | FileCheck %s
+
+; CHECK-LABEL: bb1:
+; CHECK-NEXT: %load1 = load {}*, {}** %arg
+; CHECK-NEXT: %cmp1 = icmp eq {}* %load1, null
+
+; CHECK-LABEL: bb2:
+; CHECK: ret i1 false
+
+define i1 @test({}** %arg, i1 %arg2) {
+  br i1 %arg2, label %bb1, label %bb2
+
+bb1:
+  %load1 = load {}*, {}** %arg
+  %cmp1 = icmp eq {}* %load1, null
+  ret i1 %cmp1
+
+bb2:
+  %load2 = load {}*, {}** %arg, !nonnull !1
+  %cmp2 = icmp eq {}* %load2, null
+  ret i1 %cmp2
+}
+
+!1 = !{}