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

[Filip Pizlo]

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>
	%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.

-Filip


> 
> -Hal
> 
>> 
>> 
>> 
>> 
>> 
>> It's not clear how that is better than any of the other proposals to
>> represent constraint systems in the IR via "ephemeral" uses.
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>> 
> 
> -- 
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory

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