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

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>

On Fri, Jul 15, 2016 at 2:54 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
>
>
> 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.  */
>
>
Note that this is also necessary to makes post-dominance correct (but we
already do it in most cases, but i think there are still bugs open about
correctness)

For dominance, the dominance relationship for exit blocks a noreturn blocks
reach also changes , though i don't honestly remember if it's material
or
not, and i'm a bit lazy to think about it.  But here's an example:


IE given

A (may-throw)
|
v
B
|
v
C (exit)


Here, we have A dominates B dominates C

So the dominator tree is
A
|
v
B
|
v
C

Now, if you add an edge from A to C, you have:

A dominates B
Neither B nor A dominate C (C's idom is somewhere above, so it's in a
sibling tree somewhere).


IE

A    C
 |
B


In GCC, there is a single exit block, and it is always empty (returns are
connected to the exit block).
Thus, the above will not prevent an optimization that should otherwise
happen, from happening.

Because LLVM's exit blocks contain real code, it may

You can actually get even worse (ie really wrong) situations if the
"exit"
blocks somehow have successors, but thankfully we don't have a case where
that happens that i know :)
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160715/0ae70ffe/attachment-0001.html>

Hi Daniel,

Daniel Berlin wrote:
 >     // 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 :)

As written above, sure; but the `while (true)` could be inside a
nounwind function (that does not return).  So it is not sufficient to
just look for calls to unknown functions in a function body to
conclude that it is alwaysreturn, it isn't sufficient to look for
llvm::Loop's either since we could have cycles not describable as
loops.

I'm not claiming that ^ is new information, btw, I'm justifying why I
specifically brought up the "while(true)" example. :)

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

Does GCC's notion of a "loop" (unlike LLVM) include all
potentially
infinite control flow?

-- Sanjoy

Hi Daniel,

Daniel Berlin wrote:
 >     /* 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.  */
 >
 >
 > Note that this is also necessary to makes post-dominance correct (but we
 > already do it in most cases, but i think there are still bugs open about
 > correctness)

Yeah, right now in LLVM we cannot rely on post-dominance to conclude
"guaranteed to execute" which isn't ideal.  There's at least
one place
I know where a more precise post-dominance could be used. :)

 > For dominance, the dominance relationship for exit blocks a noreturn
 > blocks reach also changes , though i don't honestly remember if
it's
 > material or not, and i'm a bit lazy to think about it.  But here's
an
 > example:
 >
 >
 > IE given
 >
 > A (may-throw)
 > |
 > v
 > B
 > |
 > v
 > C (exit)
 >
 >
 > Here, we have A dominates B dominates C
 >
 > So the dominator tree is
 > A
 > |
 > v
 > B
 > |
 > v
 > C
 >
 > Now, if you add an edge from A to C, you have:
 >
 > A dominates B
 > Neither B nor A dominate C (C's idom is somewhere above, so it's
in a
 > sibling tree somewhere).

Not sure I understand this example -- won't C's new idom be A?  The new
graph is this, right:

A -> C
A -> B
B -> C

?

 >
 >
 > IE
 >
 > A    C
 >   |
 > B
 >
 >
 > In GCC, there is a single exit block, and it is always empty (returns
 > are connected to the exit block).
 > Thus, the above will not prevent an optimization that should otherwise
 > happen, from happening.
 >
 > Because LLVM's exit blocks contain real code, it may
 >
 > You can actually get even worse (ie really wrong) situations if the
 > "exit" blocks somehow have successors, but thankfully we
don't have a
 > case where that happens that i know :)
 >
 >