[LLVMdev] Proposal: function prefix data

[Sean Silva]

On Thu, Jul 18, 2013 at 12:13 PM, Peter Collingbourne <peter at pcc.me.uk>wrote:

> On Wed, Jul 17, 2013 at 07:50:58PM -0700, Sean Silva wrote:
> > On Wed, Jul 17, 2013 at 6:06 PM, Peter Collingbourne <peter at pcc.me.uk
> >wrote:
> >
> > > Hi,
> > >
> > > I would like to propose that we introduce a mechanism in IR to allow
> > > arbitrary data to be stashed before a function body.  The purpose of
> > > this would be to allow additional data about a function to be looked
> > > up via a function pointer.  Two use cases come to mind:
> > >
> > > 1) We'd like to be able to use UBSan to check that the type of the
> > >    function pointer of an indirect function call matches the type of
> > >    the function being called.  This can't really be done efficiently
> > >    without storing type information near the function.
> > >
> >
> > How efficient does it have to be? Have some alternatives already proven
> to
> > be "too slow"? (e.g. a binary search into a sorted table)
>
> This has admittedly not been measured.  It depends on the rate at
> which the program performs indirect function calls.  But given the
> other use cases for this feature


So far you only seem to have presented the GHC ABI use case (and see just
below about UBSan). Do you know of any other use cases?


> we might as well use it in UBSan as
> opposed to something which is going to be strictly slower.
>

Below you use UBSan's use case as a motivating example, which seems
incongruous to this "might as well use it in UBSan" attitude. Without
having evaluated alternatives as being "too slow" for UBSan, I don't think
that UBSan's use case should be used to drive this proposal.


>
> > > 2) Allowing GHC's tables-next-to-code ABI [1] to be implemented.
> > >    In general, I imagine this feature could be useful for the
> > >    implementation of languages which require runtime metadata for
> > >    each function.
> > >
> > > The proposal is that an IR function definition acquires a constant
> > > operand which contains the data to be emitted immediately before
> > > the function body (known as the prefix data).  To access the data
> > > for a given function, a program may bitcast the function pointer to
> > > a pointer to the constant's type.  This implies that the IR symbol
> > > points to the start of the prefix data.
> > >
> > > To maintain the semantics of ordinary function calls, the prefix data
> > > must have a particular format.  Specifically, it must begin with a
> > > sequence of bytes which decode to a sequence of machine instructions,
> > > valid for the module's target, which transfer control to the point
> > > immediately succeeding the prefix data, without performing any other
> > > visible action.  This allows the inliner and other passes to reason
> > > about the semantics of the function definition without needing to
> > > reason about the prefix data.  Obviously this makes the format of the
> > > prefix data highly target dependent.
> > >
> >
> > I'm not sure that something this target dependent is the right choice.
> Your
> > example below suggests that the frontend would then need to know magic to
> > put "raw" in the instruction stream. Have you considered having the
> feature
> > expose just the intent "store this data attached to the function, to be
> > accessed very quickly", and then have an intrinsic
> > ("llvm.getfuncdata.i{8,16,32,64}"?) which extracts the data in a
> > target-dependent way?
>
> The problem is that things like UBSan need to be able to understand
> the instruction stream anyway (to a certain extent).  In UBSan's case,
> determining at runtime whether a function has prefix data depends on
> a specific signature of instructions at the start of the program.
> There are a wide variety of signatures that can be used here and
> I believe we shouldn't try to constrain the frontend author with a
> signature (at least partly) of our own design.
>
> I think that if someone wants a target-independent way of
> embedding prefix data it should be done as a library on top of the
> target-dependent facilities provided in IR.  One could imagine a set
> of routines like this:
>
> /// Given some constant data, attach valid prefix data.
> void attachPrefixData(Function *F, Constant *Data);
>
> /// Returns an i1 indicating whether prefix data is present for FP.
> Value *hasPrefixData(Value *FP);
>
> /// Returns a pointer to the prefix data for FP.
> Value *getPrefixDataPointer(Value *FP, Type *DataType);
>
> > Forcing clients to embed deep
> > target-specific-machine-code knowledge in their frontends seems like a
> step
> > in the wrong direction for LLVM.
>
> Given a set of routines such as the ones described above, I think we
> can give frontends a choice of whether to do this or not.  Besides,
> LLVM already contains plenty of target-specific information in its IR.
> Varargs, inline asm, calling conventions, etc.  I don't think making
> all aspects of the IR target-independent should be a worthwhile goal
> for LLVM.
>

I don't have an issue with target-dependent things per se; I just think
that they should be given a bit more thought and not added unless existing
mechanisms are insufficient. For example, could this be implemented as a
late IR pass that adds a piece of inline-asm to the beginning of the
function?

-- Sean Silva


>
> > > This requirement could be relaxed when combined with my earlier symbol
> > > offset proposal [2] as applied to functions.  However, this is outside
> > > the scope of the current proposal.
> > >
> > > Example:
> > >
> > > %0 = type <{ i32, i8* }>
> > >
> > > define void @f() prefix %0 <{ i32 1413876459, i8* bitcast ({ i8*, i8*
> }*
> > > @_ZTIFvvE to i8*) }> {
> > >   ret void
> > > }
> > >
> > > This is an example of something that UBSan might generate on an
> > > x86_64 machine.  It consists of a signature of 4 bytes followed by a
> > > pointer to the RTTI data for the type 'void ()'.  The signature when
> > > laid out as a little endian 32-bit integer decodes to the instruction
> > > 'jmp .+0x0c' (which jumps to the instruction immediately succeeding
> > > the 12-byte prefix) followed by the bytes 'F' and 'T' which identify
> > > the prefix as a UBSan function type prefix.
> > >
> >
> > Do you know whether OoO CPU's will still attempt to decode the "garbage"
> in
> > the instruction stream, even if there is a jump over it? (IIRC they will
> > decode ahead of the PC and hiccup (but not fault) on garbage). Maybe it
> > would be better to steganographically encode the value inside the
> > instruction stream? On x86 you could use 48b8<imm64> which only has 2
> bytes
> > overhead for an i64 (putting a move like that, which moves into a
> > caller-saved register on entry, would effectively be a noop).
>
> On the contrary, I think this is a good argument for allowing
> (not forcing) frontends to encode the prefix data as they please,
> thus enabling this kind of creativity.
>
> > This is some
> > pretty gnarly target-dependent stuff which seems like it would best be
> > hidden in the backend (e.g. architectures that have "constant
> island"-like
> > passes might want to stash the data in there instead).
>
> I think that adding support for things like constant islands is
> something that can be added incrementally at a later stage.  One could
> consider for example an additional llvm::Function field which specifies
> the number of bytes that the backend may use at the beginning of the
> function such that the prefix data may be of any format.  (Once this
> is in place the aforementioned library routines could become relatively
> trivial.)  The backend could use this space to, say, insert a relative
> branch that skips the prefix data and a first constant island.
>
> Thanks,
> --
> Peter
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130718/40dde1c0/attachment.html>