Hi Hal, On 02/06/12 14:28, Hal Finkel wrote:> On Sat, 02 Jun 2012 09:56:30 +0200 > Duncan Sands<baldrick at free.fr> wrote: > >> Hi Hal, >> >>> To do bounds checking you need two things: First you need to know >>> the bounds (this requires tracking calls to allocation functions), >>> and then you need to look at memory accesses. My guess is that >>> running the analysis late helps much more with the second part than >>> with the first. So I would split this into two pieces. Prior to >>> inlining, add whatever is necessary around each call site so that >>> you get the bounds data that you need. You can tag these resulting >>> values so that they're easily recognizable to the later parts of >>> the analysis (you might need to artificially makes these 'used' so >>> that DCE won't get rid of them). >> >> in that case, why not have the front-end do this part? I mean, rather >> than the front-end outputting hi/lo functions and metadata so that >> some LLVM pass can insert a few markers or whatever around/on >> call-sites that a later LLVM pass recognizes, why not have the >> front-end insert those "markers" directly? > > So long as this does not violate the "don't pay for what you don't > use" rule, I don't see any reason why not.the question then arises of what those "markers" should be, and kind of brings things full circle to Nuno's original suggestion of calculating the hi/lo bounds explicitly just before the call to wonder_malloc, and sticking metadata on the call to say "this value holds the lower bound and this one the upper". The problem with that is presumably that the optimizers will just zap the apparently unused hi/lo values. Ciao, Duncan.
On Sat, 02 Jun 2012 14:45:32 +0200 Duncan Sands <baldrick at free.fr> wrote:> Hi Hal, > > On 02/06/12 14:28, Hal Finkel wrote: > > On Sat, 02 Jun 2012 09:56:30 +0200 > > Duncan Sands<baldrick at free.fr> wrote: > > > >> Hi Hal, > >> > >>> To do bounds checking you need two things: First you need to know > >>> the bounds (this requires tracking calls to allocation functions), > >>> and then you need to look at memory accesses. My guess is that > >>> running the analysis late helps much more with the second part > >>> than with the first. So I would split this into two pieces. Prior > >>> to inlining, add whatever is necessary around each call site so > >>> that you get the bounds data that you need. You can tag these > >>> resulting values so that they're easily recognizable to the later > >>> parts of the analysis (you might need to artificially makes these > >>> 'used' so that DCE won't get rid of them). > >> > >> in that case, why not have the front-end do this part? I mean, > >> rather than the front-end outputting hi/lo functions and metadata > >> so that some LLVM pass can insert a few markers or whatever > >> around/on call-sites that a later LLVM pass recognizes, why not > >> have the front-end insert those "markers" directly? > > > > So long as this does not violate the "don't pay for what you don't > > use" rule, I don't see any reason why not. > > the question then arises of what those "markers" should be, and kind > of brings things full circle to Nuno's original suggestion of > calculating the hi/lo bounds explicitly just before the call to > wonder_malloc, and sticking metadata on the call to say "this value > holds the lower bound and this one the upper". The problem with that > is presumably that the optimizers will just zap the apparently unused > hi/lo values.I think this depends on when the passes run; looking at PassManagerBuilder::populateFunctionPassManager it seems that the DCE passes are all scheduled at the end. On the other hand, I recall that other earlier passes also do some amount of DCE as well. That being the case, if there is problem, we could develop some way to mark the relevant values as 'used' and then remove those tags just prior to running the real DCE passes at the end of the sequence. -Hal> > Ciao, Duncan.-- Hal Finkel Postdoctoral Appointee Leadership Computing Facility Argonne National Laboratory
Hi,
So here is a new proposal:
!0 = metadata !{ alloc_siz_fn, offset_fn, parameters* }
alloc_size_fn and offset_fn are functions that return either i32/i64
depending on the platform, and they must have the same number of
arguments (not necessarily the same as the as allocation function).
The parameters are given in the metadata as well.
To accommodate the common case, offer_fn can be null, meaning it is a
zero offset.
The usage would be something like this:
%r = call i8* @my_realloc(i32* %ptr, i32 %n), !alloc_size !0
!0 = metadata !{ i32 (i32)* @size, null, i32 %n }
Even if my_realloc() gets inlined later, the metadata can still be
applied to the returned value (since it is not really specific to a
call site). Of course some parameters of the allocation function may
be deleted if the function gets inlined (i.e., nulled in the
metadata), but I don't think we can workaround that problem. This is a
best-effort approach, anyway.
To avoid these functions being removed, I propose a new linkage type.
Something like internal_metadata (or hopefully a better name). This
linkage would mean that a function can only be removed in codegen, and
if it has no users. The difference to internal linkage, is that
internal functions with no users can be deleted at any time.
So, what do you think about this new proposal? I guess it addresses
all issues raised so far.
Thanks,
Nuno
On Jun 4, 2012, at 10:37 AM, Nuno Lopes <nunoplopes at sapo.pt> wrote:> So here is a new proposal: > > !0 = metadata !{ alloc_siz_fn, offset_fn, parameters* }The parameters are a separate metadata array or the alloc_size metadata is variable length? You'll probably want to write up some docs for the website on how this is supposed to be laid out and work. -eric
On Mon, 04 Jun 2012 18:37:31 +0100 Nuno Lopes <nunoplopes at sapo.pt> wrote:> Hi, > > So here is a new proposal: > > !0 = metadata !{ alloc_siz_fn, offset_fn, parameters* } > > alloc_size_fn and offset_fn are functions that return either i32/i64 > depending on the platform, and they must have the same number of > arguments (not necessarily the same as the as allocation function). > The parameters are given in the metadata as well. > To accommodate the common case, offer_fn can be null, meaning it is > a zero offset. > > The usage would be something like this: > > %r = call i8* @my_realloc(i32* %ptr, i32 %n), !alloc_size !0 > !0 = metadata !{ i32 (i32)* @size, null, i32 %n } > > Even if my_realloc() gets inlined later, the metadata can still be > applied to the returned value (since it is not really specific to a > call site). Of course some parameters of the allocation function may > be deleted if the function gets inlined (i.e., nulled in the > metadata), but I don't think we can workaround that problem. This is > a best-effort approach, anyway. > > > To avoid these functions being removed, I propose a new linkage > type. Something like internal_metadata (or hopefully a better name). > This linkage would mean that a function can only be removed in > codegen, and if it has no users. The difference to internal linkage, > is that internal functions with no users can be deleted at any time.Is it possible to determine which functions are referenced in metadata even though the metadata is not listed as a user? It seems like we could do this without defining another linkage class.> > So, what do you think about this new proposal? I guess it addresses > all issues raised so far.I think this is good. -Hal> > Thanks, > Nuno > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev-- Hal Finkel Postdoctoral Appointee Leadership Computing Facility Argonne National Laboratory
Hi Nuno,> So here is a new proposal: > > !0 = metadata !{ alloc_siz_fn, offset_fn, parameters* } > > alloc_size_fn and offset_fn are functions that return either i32/i64 > depending on the platform, and they must have the same number of > arguments (not necessarily the same as the as allocation function). > The parameters are given in the metadata as well. > To accommodate the common case, offer_fn can be null, meaning it is a > zero offset. > > The usage would be something like this: > > %r = call i8* @my_realloc(i32* %ptr, i32 %n), !alloc_size !0 > !0 = metadata !{ i32 (i32)* @size, null, i32 %n }suppose the size is %n+4. Then in the function you have to compute %s = add i32 %n, 4 and then put %s in the metadata !0 = metadata !{ i32 (i32)* @size, null, i32 %s } However then the only use of %s is in the metadata, so basically any optimization pass will zap it, right? So won't this only work if the size etc calculation doesn't actually require any calculation, eg it would work if you only pass function parameters and globals but that's about it. Am I missing something? Ciao, Duncan.