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

On Fri, Jul 15, 2016 at 12:21 PM, Sanjoy Das <sanjoy at
playingwithpointers.com
> wrote:
> Hi Daniel,
>
> Daniel Berlin wrote:
> >          As a starting point, LLVM will conservatively not speculate
such
> >          loads and stores; and will leave open the potential to
upstream
> >          logic that will have a more precise sense of when these loads
> and
> >          stores are safe to speculate.
> >
> >
> > I think you need to define what you mean by control dependence here. 
If
> > you mean speculation, you should say speculation :)
>
> Apologies for being non-specific -- this is really just "don't
> speculate".
>
> > As you describe below, it is not enough to simply not speculate them.
>
> I'm not sure where I said that?


>
>
> > You also are saying you don't want to change the conditions on
which
> > they execute.
> > That is very different from speculation.
>
> If I implied that somehow then I (or the example) was wrong. :)
>
:)

>
> We can't speculate these instructions (without special knowledge of
> the GC and the Java type system), and that's it.
Okey.

>
>
> > FWIW: This raises one of the same issues we have now with may-throw,
> > which is that, if all you have is a flag on the instruction, now you
> > have to look at every instruction in every block to know whether a
*CFG*
> > transform is correct.
> >
> > That means any pass that wants to just touch the CFG can't do so
without
> > also looking at the instruction stream.  It will also make a bunch of
> > things currently O(N), O(N^2) (see the sets of patches fixing
may-throw
> > places, and extrapolate to more places).
>
> As I said, I'm only proposing a "don't speculate" flag,
so this does
> not (?) apply.
>
As long as it applies only to the instructions, and they do not act as
"barriers" to hoisting/sinking, then yes, it should not apply.

(In theory it still means things have to look at instructions, but they had
to look at them anyway at that point :P)
>
> 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:

See:
[PATCH] D21007: DSE: Don't remove stores made live by a call which unwinds.
for the latter

[llvm] r270828 - [MergedLoadStoreMotion] Don't transform across may-throw
calls
for the former.

"It is unsafe to hoist a load before a function call which may throw, the
throw might prevent a pointer dereference.

Likewise, it is unsafe to sink a store after a call which may throw.
The caller might be able to observe the difference."

This then leads to the problem i mentioned - because the may-throwness is
not expressed at the bb level (or in the CFG, by having the call end the
block, or at the least, a fake abnormal CFG edge), everything has to go
checking every instruction along the entire path they want to hoist,
whereas hoisting is normally just a simple dataflow problem with BB level
properties :)

>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160715/a94f4e87/attachment.html>

>
>
>> This then leads to the problem i mentioned - because the may-throwness
is
> not expressed at the bb level (or in the CFG, by having the call end the
> block, or at the least, a fake abnormal CFG edge), everything has to go
> checking every instruction along the entire path they want to hoist,
> whereas hoisting is normally just a simple dataflow problem with BB level
> properties :)
>
>
and to be clear, i'm just being colloquial about "expressed at the bb
level". An analysis that everything used/kept up to date if it decided to
insert throwing calls or make calls nounwind would have the same effect.  I
happen to be more used to these things being flags on basic blocks, but
whatever works.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160715/8b69393f/attachment.html>

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)" and
"while(true) {
*volatile_ptr = 42; }" too?  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) {...}").

-- Sanjoy

 > See:
 > [PATCH] D21007: DSE: Don't remove stores made live by a call which 
unwinds.
 > for the latter
 >
 > [llvm] r270828 - [MergedLoadStoreMotion] Don't transform across
 > may-throw calls
 > for the former.
 >
 > "It is unsafe to hoist a load before a function call which maythrow,
the
 > throw might prevent a pointer dereference.
 >
 > Likewise, it is unsafe to sink a store after a call which maythrow.
 > The caller might be able to observe the difference."
 >
 > This then leads to the problem i mentioned - because the may-throwness
 > is not expressed at the bb level (or in the CFG, by having the call end
 > the block, or at the least, a fake abnormal CFG edge), everything has to
 > go checking every instruction along the entire path they want to hoist,
 > whereas hoisting is normally just a simple dataflow problem with BB
 > level properties :)
 >
 >
 >

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>