This is an archive of the discontinued LLVM Phabricator instance.

Clarify wording in the LangRef around !invariant.load
ClosedPublic

Authored by reames on Nov 20 2014, 3:29 PM.

Details

Summary

This is my attempt to clarify the wording in the LangRef w.r.t. the implied semantics of the !invariant.load metadata. To the best of my knowledge, the revised wording respects the actual implementation and understanding of issues involved highlighted in the recent 'Optimization hints for "constant" loads' thread on LLVMDev.

In particular, I'm aiming for the following results:

  • To clarify that an invariant.load can fault and must respect control dependence. In particular, it is not sound to unconditionally pull an invariant load out of a loop if that loop would potentially never execute.
  • To clarify that the invariant nature of a given pointer does not preclude the modification of that location through a pointer which is unrelated to the load operand. In particular, initializing a location and then passing a pointer through an opaque intrinsic which produces a new unrelated pointer, should behave as expected provided that the intrinsic is memory dependent on the initializing store.
  • To clarify that storing a value to an invariant location is defined. It can not, for example, be considered unreachable. The value stored can be assumed to be equal to the value of any previous (or following!) invariant load, but the store itself is defined.

I would really appreciate some careful thought by others familiar with the semantics here. Are the revised semantics consistent with our actual implementation? With the expectations of current users? With the optimizations we'd like to see applied going forward?

Once we agree on the semantics here, my plan is to extend a couple of places in the optimizer with support for invariant loads. In particular, EarlyCSE & GVN can do more aggressive value forwarding and dead store elimination for locations touched by invariant loads. An InstCombine rule of the form store (store (load x invariant), x) -> (nop) also seems useful.

Diff Detail

Event Timeline

reames updated this revision to Diff 16455.Nov 20 2014, 3:29 PM
reames retitled this revision from to Clarify wording in the LangRef around !invariant.load.
reames updated this object.
reames edited the test plan for this revision. (Show Details)
reames added a subscriber: Unknown Object (MLST).
sanjoy edited edge metadata.Nov 20 2014, 4:14 PM

To clarify that the invariant nature of a given pointer does not preclude the modification of that location through a pointer which is unrelated to the load operand. In particular, initializing a location and then passing a pointer through an opaque intrinsic which produces a new unrelated pointer, should behave as expected provided that the intrinsic is memory dependent on the initializing store.

Does this mean you cannot common loads for escaped memory over calls? The call could have modified the pointed-to location using another pointer.

After offline discussion w/Sanjoy, I'm revising my proposed wording to
the following:
"The optional `!invariant.load` metadata must reference a single
metadata name `<index>` corresponding to a metadata node with no
entries. The existence of the `!invariant.load` metadata on the
instruction tells the optimizer and code generator that the address
operand to this load points to memory which can be assumed unchanged
by any store. Being invariant does not
imply that a location is dereferenceable, but it does imply that once
the location is known dereferenceable it's value is henceforth unchanging. "

These aren't intended to be semantic changes, but they remove some
confusion in the wording. (There's no need to explicitly mention
aliasing or dynamic paths.)

Something I think needs clarification is whether !invariant.load is a
dynamic property or a static property. In other words, is the pointer
being loaded from specified to be constant only once an
!invariant.load has executed, or is it constant by the virtue of there
*existing* an invariant.load?

If the pointer being loaded from is specified being constant only once
an !invariant.load has executed, it means !invariant.loads cannot be
hoisted above control dependencies in general:

transforming

int *x = < known dereferenceable >
if (t) {
  m = load(x) !invariant.load
}
*x = 42

to

int *x = < known dereferenceable >
m = load(x) !invariant.load
if (t) {
}
*x = 42

makes a well-defined program undefined when t is false. Hoisting invariant loads through control dependencies can introduce UB.

If the pointer being loaded from is specified being constant if there
*exists* a use of the pointer in an !invariant.load, then:

transforming

int *x = < known dereferenceable >
*x = 42

to

int *x = < known dereferenceable >
if (false) {
  m = load(x) !invariant.load
}
*x = 42

introduces UB. This is counter-intuitive -- introducing a load that
will *never be executed* makes the program undefined.

Personally, I think the load is incorrect place to annotate
invariance -- invariance should be just like dereferenceable, an
attribute on a *pointer* + offset range.

hfinkel edited edge metadata.Nov 20 2014, 7:17 PM

which can be assumed unchanged by any store.

First, "unchanged by any store" seems redundant (and over-specific); "unchanged" would be fine.

However, this leaves open the question of when and for how long? Does it imply invariance only during the execution of the function? or must it have the same value during every invocation? At what point does the invariance start?

docs/LangRef.rst
5216

it's -> its

atrick accepted this revision.Nov 20 2014, 10:15 PM
atrick edited edge metadata.

Great. Thanks for getting this clarified.

I still think it's hard to understand the semantics. I think the best way to improve it is to define a more general system for invariant attributes then define the metadata version in terms of that.

LGTM for now.

This revision is now accepted and ready to land.Nov 20 2014, 10:15 PM
reames closed this revision.Nov 24 2014, 2:33 PM
reames updated this revision to Diff 16585.

Closed by commit rL222700 (authored by @reames).