refactor metadata propagation for consistency and completeness

[Quuxplusone]

Bugzilla Link	PR31518
Status	NEW
Importance	P normal
Reported by	Sanjay Patel (spatel+llvm@rotateright.com)
Reported on	2017-01-03 10:06:49 -0800
Last modified on	2017-07-01 06:09:44 -0700
Version	trunk
Hardware	PC All
CC	ditaliano@apple.com, efriedma@quicinc.com, hfinkel@anl.gov, llvm-bugs@lists.llvm.org
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also	PR31512, PR31142

As Davide noted in the post-commit thread for r290844:
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20170102/416121.html

...we have many implementations/variations for propagating metadata in
individual passes. Some of these may require different behavior, but there must
be some functionality that can be shared amongst:

GVN::patchReplacementInstruction()
GVNHoist::combineKnownMetadata()
SimplifyCFG::HoistThenElseCodeToIf()
BBVectorize::fuseChosenPairs()
VectorUtils:propagateMetadata()

We have Local.cpp -> llvm::combineMetadataForCSE(). Can it be used in these
cases?

[Quuxplusone]

• Eli who introduced combineMetadataForCSE

[Quuxplusone]

Yes, combineMetadataForCSE can be used in more places; I just didn't get around to tracking them all down.

[Quuxplusone]

For background, the example I'm looking at:

define i8* @isa_impl_wrap(i8** %x) {
  %t2 = alloca i8*
  %t4 = load i8*, i8** %x
  store i8* %t4, i8** %t2
  %t6 = load i8*, i8** %t2, !nonnull !0
  ret i8* %t6
}
!0 = !{}

The nonnull disappears with any of these passes, and these all appear to have
independent ways of optimizing the code.

$ ./opt -S cse_nonnull.ll -instcombine
...
define i8* @isa_impl_wrap(i8** %x) {
  %t4 = load i8*, i8** %x, align 8
  ret i8* %t4
}

$ ./opt -S cse_nonnull.ll -early-cse
...
define i8* @isa_impl_wrap(i8** %x) {
  %t2 = alloca i8*
  %t4 = load i8*, i8** %x
  store i8* %t4, i8** %t2
  ret i8* %t4
}

$ ./opt -S cse_nonnull.ll -mem2reg
...
define i8* @isa_impl_wrap(i8** %x) {
  %t4 = load i8*, i8** %x
  ret i8* %t4
}

However, if the nonnull metadata appears on the 1st load only, then it survives
all of these passes.

[Quuxplusone]

(In reply to comment #3)
> For background, the example I'm looking at:
>
> define i8* @isa_impl_wrap(i8** %x) {
>   %t2 = alloca i8*
>   %t4 = load i8*, i8** %x
>   store i8* %t4, i8** %t2
>   %t6 = load i8*, i8** %t2, !nonnull !0
>   ret i8* %t6
> }
> !0 = !{}
>
> The nonnull disappears with any of these passes, and these all appear to
> have independent ways of optimizing the code.
>
> $ ./opt -S cse_nonnull.ll -instcombine
> ...
> define i8* @isa_impl_wrap(i8** %x) {
>   %t4 = load i8*, i8** %x, align 8
>   ret i8* %t4
> }
>
> $ ./opt -S cse_nonnull.ll -early-cse
> ...
> define i8* @isa_impl_wrap(i8** %x) {
>   %t2 = alloca i8*
>   %t4 = load i8*, i8** %x
>   store i8* %t4, i8** %t2
>   ret i8* %t4
> }
>
> $ ./opt -S cse_nonnull.ll -mem2reg
> ...
> define i8* @isa_impl_wrap(i8** %x) {
>   %t4 = load i8*, i8** %x
>   ret i8* %t4
> }
>
>
> However, if the nonnull metadata appears on the 1st load only, then it
> survives all of these passes.

It seems like you don't have an available load? Please note that the load you
have is dead (EarlyCSE and InstCombine both look at the load and the store
immediately preceding it).

[Quuxplusone]

(In reply to comment #3)
> For background, the example I'm looking at:
>
> define i8* @isa_impl_wrap(i8** %x) {
>   %t2 = alloca i8*
>   %t4 = load i8*, i8** %x
>   store i8* %t4, i8** %t2
>   %t6 = load i8*, i8** %t2, !nonnull !0
>   ret i8* %t6
> }
> !0 = !{}

See also https://reviews.llvm.org/D27114 .

[Quuxplusone]

(In reply to comment #5)
>
> See also https://reviews.llvm.org/D27114 .

Thanks for the link! I was looking at solving bug 31512 using an assume to
attribute transform ( similar to https://reviews.llvm.org/D5951 ), but if we're
looking to canonicalize in the other direction, that approach is DOA. :)

[Quuxplusone]

OK, I'm starting to understand this slightly more. :)
Sorry for the diversion from the original point of this bug.

Let's look at some possible GVN tests:

define i8 @nonnull1(i8** %p) {
  %a = load i8*, i8** %p, !nonnull !0
  %b = load i8*, i8** %p
  %a1 = load i8, i8* %a
  %b1 = load i8, i8* %b
  %c = add i8 %a1, %b1
  ret i8 %c
}

define i8 @nonnull2(i8** %p) {
  %a = load i8*, i8** %p
  %b = load i8*, i8** %p, !nonnull !0
  %a1 = load i8, i8* %a
  %b1 = load i8, i8* %b
  %c = add i8 %a1, %b1
  ret i8 %c
}

define i8 @nonnull3(i8** %p) {
  %a = load i8*, i8** %p, !nonnull !0
  %b = load i8*, i8** %p, !nonnull !0
  %a1 = load i8, i8* %a
  %b1 = load i8, i8* %b
  %c = add i8 %a1, %b1
  ret i8 %c
}

Currently, we drop the nonnull in all cases with 'opt -gvn' because MD_nonnull
isn't in the list of KnownIDs.

1. Is the ideal behavior to preserve nonnull in all cases?
2. If yes, is that true for all GVN transforms, or is this a special simple
case?
3. Should GVN have different behavior than combineMetadataForCSE?

[Quuxplusone]

For nonnull in particular, the best way to understand the semantics is probably to translate from !nonnull->assume; then the obvious redundancy rules apply.

[Quuxplusone]

(In reply to comment #8)
> For nonnull in particular, the best way to understand the semantics is
> probably to translate from !nonnull->assume; then the obvious redundancy
> rules apply.

Please correct me if I'm misunderstanding, but if it's easier to reason about
using assumes, that's another vote to reverse the current instcombine
canonicalization.

I like the compactness of the metadata, but given how easily it is lost, I'm
seeing the advantage of the assume now.

[Quuxplusone]

Sort of, yes... I mean, nonnull isn't really a property of the load; it's a property of the produced value, so attaching it to the load doesn't really make sense. But llvm.assume has a terrible design which tends to screw up other optimizations, so nobody really wants to use it.

[Quuxplusone]

The BBVectorizer was removed from trunk:
https://reviews.llvm.org/rL306797