llvm dev - Jul 2016 - RFC: Strong GC References in LLVM

On Fri, Jul 15, 2016 at 2:30 PM, Sanjoy Das <sanjoy at
playingwithpointers.com>
wrote:
> Hi Daniel,
>
> Daniel Berlin wrote:
> >     However, I didn't quite understand your point about may-throw
-- how
> >     is may-throw different from a generic side-effect (volatile store,
> >     syscall etc.)?  All of those can't be hoisted or sunk -- we
have to
> >     make sure that they execute in semantically the same conditions
that
> >     they did in the original program.
> >
> > may-throw is, AFAIK, worse. They act as barriers to sinking *other
> > things*. You cannot sink a store past a may-throw, or hoist a load
above
> > them.  You can't optimize stores across them either:
>
> Don't we have the same problems for "exit(0)"

This is a noreturn call, so yes, iit has another hidden control
flow-side-effect of a slightly different kind. GCC models it as an extra
fake edge from the BB containing a noreturn call to the exit block of the
function, so that nothing sinks below it by accident.

I do not believe we do anything special here, so yes, it also has the same
general issue as may-throw.

> and "while(true) {
> *volatile_ptr = 42; }" too?

I can move non-volatile stores past volatile stores :)

Or did you mean something else?


>   Both of these are optimization barriers
> while still being "nounwind" (i.e. could be legitimately
contained in
> a nounwind function); though not in exactly the same way as a
> may-throw call (e.g. you can DSE across exit(0) and you can sink
> non-atomic loads past "while(true) {...}").
>
I do not claim there are not other instances. Noreturn is in fact, a good
exampl). But i would also bet they are just as buggy as may-throw was for
the same reason, and they would cause the same N^2ness.

Essentially, anything that has produces hidden control flow (instead of
just depending on hidden control flow) will have this issue.
The also are things that any flag/analysis should be able to flag.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160715/664b36b8/attachment.html>

Hi Daniel,

Daniel Berlin wrote:
 >     Don't we have the same problems for "exit(0)"
 >
 >
 > This is a noreturn call, so yes, iit has another hidden control
 > flow-side-effect of a slightly different kind. GCC models it as an extra
 > fake edge from the BB containing a noreturn call to the exit block of
 > the function, so that nothing sinks below it by accident.

Just to be clear, it'd have to keep that sort of edge for all call
sites, unless it can prove that the call target does not call exit?

 > I do not believe we do anything special here, so yes, it also has the
 > same general issue as may-throw.
 >
 >     and "while(true) {
 >     *volatile_ptr = 42; }" too?
 >
 >
 > I can move non-volatile stores past volatile stores :)

I meant:

// ptr_a and ptr_b are NoAlias, ptr_a holds 0 to begin with.

ThreadA:
   while(true) { store volatile i32 42, i32* %ptr_b }
   store atomic i32 42, i32* %ptr_a

ThreadB:
   %val = load atomic i32, i32* %ptr_a
   assert(%val is not 42)  // The store is "guarded" by an inf loop


We can't reorder the store to ptr_a to before the infinite loop.  The
volatile store is there to make the infinite loop well defined.

 > Or did you mean something else?
 >
 >        Both of these are optimization barriers
 >     while still being "nounwind" (i.e. could be legitimately
contained in
 >     a nounwind function); though not in exactly the same way as a
 >     may-throw call (e.g. you can DSE across exit(0) and you can sink
 >     non-atomic loads past "while(true) {...}").
 >
 >
 > I do not claim there are not other instances. Noreturn is in fact, a
 > good exampl). But i would also bet they are just as buggy as may-throw
 > was for the same reason, and they would cause the same N^2ness.

Yes.

 > Essentially, anything that has produces hidden control flow (instead of
 > just depending on hidden control flow) will have this issue.
 > The also are things that any flag/analysis should be able to flag.

Yup.

-- Sanjoy

On Fri, Jul 15, 2016 at 2:44 PM, Sanjoy Das <sanjoy at
playingwithpointers.com>
wrote:
> Hi Daniel,
>
> Daniel Berlin wrote:
> >     Don't we have the same problems for "exit(0)"
> >
> >
> > This is a noreturn call, so yes, iit has another hidden control
> > flow-side-effect of a slightly different kind. GCC models it as an
extra
> > fake edge from the BB containing a noreturn call to the exit block of
> > the function, so that nothing sinks below it by accident.
>
> Just to be clear, it'd have to keep that sort of edge for all call
> sites, unless it can prove that the call target does not call exit?

Yes.

/* Add fake edges to the function exit for any non constant and non
    noreturn calls (or noreturn calls with EH/abnormal edges),
    volatile inline assembly in the bitmap of blocks specified by BLOCKS
    or to the whole CFG if BLOCKS is zero.
...

    The goal is to expose cases in which entering a basic block does
    not imply that all subsequent instructions must be executed.  */

> // ptr_a and ptr_b are NoAlias, ptr_a holds 0 to begin with.
>
> ThreadA:
>   while(true) { store volatile i32 42, i32* %ptr_b }
>   store atomic i32 42, i32* %ptr_a
>
> ThreadB:
>   %val = load atomic i32, i32* %ptr_a
>   assert(%val is not 42)  // The store is "guarded" by an inf
loop
>
>
> We can't reorder the store to ptr_a to before the infinite loop.  The
> volatile store is there to make the infinite loop well defined.

These do not have hidden control flow. It is actually well defined it just
literallly involves other instructions :)

Note that gcc will optionally connect the infinite loop itself to the exit
block with a fake edge if you want
(you can add/remove fake edges on a per-opt basis).


>
>
> > Or did you mean something else?
> >
> >        Both of these are optimization barriers
> >     while still being "nounwind" (i.e. could be legitimately
contained in
> >     a nounwind function); though not in exactly the same way as a
> >     may-throw call (e.g. you can DSE across exit(0) and you can sink
> >     non-atomic loads past "while(true) {...}").
> >
> >
> > I do not claim there are not other instances. Noreturn is in fact, a
> > good exampl). But i would also bet they are just as buggy as may-throw
> > was for the same reason, and they would cause the same N^2ness.
>
> Yes.
>
> > Essentially, anything that has produces hidden control flow (instead
of
> > just depending on hidden control flow) will have this issue.
> > The also are things that any flag/analysis should be able to flag.
>
> Yup.
>
> -- Sanjoy
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160715/0a316238/attachment.html>