[LLVMdev] Proposal for safe-to-execute meta-data for heap accesses

[Andrew Trick]

On Nov 8, 2013, at 1:18 PM, Filip Pizlo <fpizlo at apple.com> wrote:

> 
> On Nov 8, 2013, at 11:20 AM, Hal Finkel <hfinkel at anl.gov> wrote:
> 
>> ----- Original Message -----
>>> 
>>> 
>>> 
>>> 
>>> 
>>> On Nov 8, 2013, at 1:13 AM, Chandler Carruth < chandlerc at google.com >
>>> wrote:
>>> 
>>> 
>>> 
>>> 
>>> 
>>> 
>>> 
>>> 
>>> On Thu, Nov 7, 2013 at 9:39 PM, Filip Pizlo < fpizlo at apple.com >
>>> wrote:
>>> 
>>> 
>>> 
>>> NEW PROPOSAL
>>> 
>>> The solution is to introduce meta-data that is explicit about how the
>>> safe-to-execute condition ought to be evaluated. Instead of an SSA
>>> use, we can have meta-data that says:
>>> 
>>> %v = load %p !notrap !{ @f, <args> }
>>> 
>>> where @f is a function in the current module and this function
>>> returns i1, and <args> is zero or more arguments to pass to @f. As
>>> with any meta-data, this doesn’t imply anything different if you
>>> wanted to just execute the code: executing the load doesn’t imply
>>> calling @f; indeed if you dropped the meta-data the execution of
>>> this would still be the same.
>>> 
>>> So, first a clarifying question:
>>> 
>>> 
>>> Is the expectation that to utilize this metadata an optimization pass
>>> would have to inspect the body of @f and reason about its behavior
>>> given <args>?
>>> 
>>> 
>>> Yes.
>>> 
>>> 
>>> 
>>> 
>>> 
>>> 
>>> 
>>> If so, then I think this is pretty bad. If we ever want to
>>> parallelize function passes, then they can't inspect the innards of
>>> other functions.
>>> 
>>> 
>>> I must be missing something. Can't you do some simple locking? Lock a
>>> function if it's being transformed, or if you want to inspect it...
>>> 
>> 
>> I think we'd exclude these functions from being acted upon by the regular optimization passes. These functions would need to be special anyway: they are functions with a special internal linkage that should not be deleted as dead, even if 'unused' (likely we'd want them to survive in memory through CodeGen), but CodeGen itself should ignore the functions (no code for them should ever be generated).
>> 
>>> 
>>> 
>>> 
>>> 
>>> So this would significantly constrain the utility here.
>>> 
>>> 
>>> I think we can engineer around this problem. For example, the
>>> function @f is meant to contain basically hand-written IR; it ought
>>> not be necessary to optimize it in order to make use of it for
>>> safe-to-execute. It's also reasonable to expect these to be small.
>>> 
>>> 
>>> Hence you can imagine freezing a copy of those functions that are
>>> used in this meta-data.
>>> 
>>> 
>>> 
>>> 
>>> 
>>> 
>>> 
>>> Also, this would create uses of the arguments that were "ephemeral"
>>> uses.
>>> 
>>> 
>>> I think they're ephemeral in a very different sense than the previous
>>> !notrap; for example here the used continue to be meaningful even
>>> after replaceAllUsesWith.
>> 
>> I think that, to Chandler's point, it would be the responsibility of the function creator to insure that the special 'functions' would not need any non-constant values without other reasonable uses. It seems like this can be arranged for things like pointer alignment checks, pointer not-null assertions, pointer dereferencability (indicated by a load in the function I suppose), simple value constraints. I think that covers most of the intended use cases.
> 
> Yeah, I think it is reasonable to say that given anything like:
> 
> 	%v = load %p !notrap !{ @f, %a1, %a2, …, %an }
> 
> It must be the case that %a1…%an are reachable from %p in the sense that ADCE could only kill %a1…%an if it killed %p.
> 
> Here are some concrete examples:
> 
> - Load that requires a pointer to be null-checked:
> 	
> 	%p = getelementptr %object, <things>
> 	%v = load %p !notrap !{ @isNotNull, %object }
> 
> - Load that requires a null check and an array bounds check:
> 
> 	%p = getelementptr %object, %index  (possibly other things also depending on your array object model)
> 	%v = load %p !notrap !{ @isNotNullAndInBounds,%object, %index }
> 
> - Load that requires tagged value encoding and that an object to have a particular shape and involves a doubly-indirected object model (for example when implementing dynamic language heap accesses):
> 
> 	%object = inttoptr %value
> 	%p1 = getelementptr %object, <things>
> 	%p2 = load %p1 !notrap !{ @isObject, %value }
> 	%p3 = getelementptr %p3, <more things>

	%p3 = getelementptr %object, <more things>

> 	%v = load %p3 !notrap !{ @hasShape, %object, 0xstuff } // 0xstuff will be a compile-time constant
> 
> I can’t think of any examples where you’d want to use safe-to-execute and where Hal’s rule won’t hold.

This is way more awesome then any of our other proposals. All of these examples have a data dependence from the argument to the !notrap instruction. That makes it much less likely for the meta-data to become invalid. And not being tied to the CFG is great.

We still have to be careful with RAUW.

Say we copy a block containing the @Check argument ‘a’ splitting the control flow (maybe we tail-dup, peel or unswitch):

call @Check(x)
if (p) {
  a = p ? x : y
  b = a + ofs
  call @Check(a)
}
else {
  a' = p ? x : y
  b' = a' + ofs
  call @Check(a’)
}
b-merge = phi(b, b’)
= *b-merge !notrap @Check a

Then we simplify:

call @Check(x)
...
if (p) {
  b = x + ofs
  call @Check(x)
}
else {
  b' = y + ofs
  call @Check(y)
}
b-merge = phi(b, b’)
= *b-merge !notrap @Check x

Now we can incorrectly hoist *b-merge above Check(y).

I think this is workable because, in general, I don’t think we should replace meta-data uses without checking dominance. We can either fail to update the !notrap use, which I *think* should be safe, or just drop it if we’re not sure.

-Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131108/3fa3a5ef/attachment.html>