[LLVMdev] alloc_size metadata

[Hal Finkel]

On Fri, 1 Jun 2012 07:37:26 +0100
"Nuno Lopes" <nunoplopes at sapo.pt> wrote:

> Hi,
> 
> Sorry for the delay; comments below.
> 
> >>>> This is actually non-trivial to accomplish.
> >>>> Metadata doesn't count as a user, so internal functions with no
> >>>> other usage will get removed.
> >>>
> >>> I thought that it is possible to have passes run before the
> >>> optimizer performs such deletions. Is this not practical? Another
> >>> option is to change the current implementation delete such
> >>> functions in two phases: in the first phase we leave functions
> >>> with metadata references. In the second phase (which runs near
> >>> the end of the pipeline) we delete functions regardless of
> >>> metadata references.
> >>
> >> Right now, if you list the users of a Value, the references coming
> >> from metadata won't appear. Metadata is not an user and doesn't
> >> count towards the number of uses of a value.  That's why using
> >> anything about constant expressions risks disappearing.
> >> Leaving non-used functions to be removed after all optimizations
> >> could be done. But then you would probably want to, for example,
> >> patch the pass manager so that it didn't run a function pass over
> >> dead functions, and so on.

Yes; I think the following would be better: For all functions that are
unused but still referenced by metadata, queue the passes on them that
would have run. If a pass then wants to inline one of these functions,
those queued passes can be run first.

> >
> > the functions could be declared to have linkonce_odr linkage.  That
> > way they will be zapped after the inliner runs, but shouldn't be
> > removed before.
> 
> I'm certainly not convinced. You cannot force all analysis to be run
> before inlining. You're basically saying that all passes that do
> analysis on buffer size must run quite early. 

I don't think that anyone said that ;) -- But even it it were true, I
think the premise is incorrect. What is true is that analysis that
deals with tracking things tied to specific call sites should run prior
to inlining (which must be true because inlining can otherwise make
those call sites disappear, merge them with other calls, etc.).

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).
Then, after more cleanup has been done by other optimization passes,
run the pass that instruments the memory accesses (then DCE anything
that you did not end up actually using).

> The inliner is run
> pretty early! At least in the case of the buffer overflow pass, I
> want it to run late, after most cleanups were done. Asan does exactly
> the same.
> 
> 
> >>>> Another thing that bothers me is the implementation on the
> >>>> objectsize intrinsic. This intrinsic returns the *constant* size
> >>>> of the pointed object given as argument (if the object has a
> >>>> constant size). However, with this function scheme, the
> >>>> implementation would be a bit heavy, since it would need to
> >>>> inline the @lo and @hi functions, simplify the resulting
> >>>> expression, and then check if the result is a ConstantInt. And
> >>>> remember that in general these functions can be arbitrary
> >>>> complex.
> >>>
> >>> I agree; we'd need to use SCEV or some other heavyweight
> >>> mechanism to do the analysis. In some sense, however, that would
> >>> be the price of generality. On the other hand, I see no reason
> >>> why we could not write a utility function that could accomplish
> >>> all of that, so we'd only need to work out the details once.
> >>
> >> SCEV is not the answer here. You just want to know if the result
> >> of a function is constant given a set of parameters. Inlining +
> >> simplifications should do it.  But doing an inlining trial is
> >> expensive.
> >
> > The hi/lo functions could be declared always_inline.  Thus they
> > will always
> > be inlined, either by the always-inliner pass or the usual one.
> > You would need to insert the instrumentation code or whatever that
> > uses hi/lo before any inliner runs, and run optimizations such as
> > turning objectsize into a constant after the inliner runs.
> 
> The semantics of the objectsize intrinsic is that it returns a
> constant value if it can figure out the objectsize, and return 0/-1
> otherwise. So you cannot simply inline the functions and hope for the
> best.  You need to run an inline trial:  inline; try to fold the
> resulting expression into a constant; remove inlined code if it
> didn't fold to a constant. You may say this is the price of
> generality. I don't know how slow would it be, though.

My thought when proposing this mechanism was that DCE would eliminate
any unneeded instructions added by inlining.

> 
> 
> Today, after playing around with these things, I found another
> problem: inlining functions with this alloc metadata.  Assuming that
> we attach the metadata to call sites in the front-end, if the
> function later gets inlined, then the metadata is lost.  We can,
> however, allow the metadata to be attached to arbitrary instructions,
> so that the inliner can be taught to attach it to the returned
> expression.

I don't understand how this would work exactly. Can you explain? Would
it be better to do the instrumentation prior to inlining?

Thanks again,
Hal

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