llvm dev - Apr 2017 - Dereferenceable load semantics & LICM

2017-04-01 15:59 GMT+02:00 Piotr Padlewski <piotr.padlewski at gmail.com>:
>
>
> 2017-03-31 23:20 GMT+02:00 Sanjoy Das <sanjoy at
playingwithpointers.com>:
>
>> Hi Piotr,
>>
>> On March 31, 2017 at 1:07:12 PM, Piotr Padlewski
>> (piotr.padlewski at gmail.com) wrote:
>> > [snip]
>> > Do I understand it correctly, that it is legal to do the hoist
because
>> all
>> > of the instructions above %vtable does not throw?
>>
>> Yes, I think you're right.  HeaderMayThrow is a conservative
>> approximation, and the conservativeness is biting us here.
>>
>> > Are there any plans to fix it in the future? The fix doesn't
seem hard
>> to
>>
>> Not to my knowledge.
>>
>> > write and I can do it, but I am not sure if it won't be too
expensive.
>>
>> Maybe we can do it (relatively) cheaply:
>>
>>  - Remember the first throwing instruction in the header, instead of a
>>    boolean, in LoopSafetyInfo
>>
>>  - In hoistRegion, remember if you've seen the first throwing
>>    instruction yet
>>
>>  - Pass the above as a boolean parameter to isGuaranteedToExecute, and
>>    instead of
>>      if (Inst.getParent() == CurLoop->getHeader())
>>        return !SafetyInfo->HeaderMayThrow;
>>    do something like
>>      if (Inst.getParent() == CurLoop->getHeader())
>>        return IsBeforeThrowingInst;
>>
>> -- Sanjoy
>>
> I was thinking about something very similar and it seems to be a good
> approach to me because it has much lower complexity.
>
> In the review Sanjoy correctly spoted that I am not discarding
> invariant.group metadata when hoisting, which is incorrect in general.
> This generates a big problem to devirtualization, because discarding
> metadata when hoisting vtable load might be worse than not hoisting when
> there might be another load/store with !invariant.group dominating it
> (e.g. after inlining).
>
> I don't see any way to model it right now in LLVM, but I see a one
simple
> solution:
>  add extra information to the metadata nodes indicating that this property
> is non-local:
>
> %0 = load... %p, !invariant.group !1, !dereferenceable !2
> %1 = load ... %0, !invariant.load !0, !dereferenceable !2
>
> !0 = !{!"GlobalProperty"}
> !1 = !{!"MyType", !"GlobalProperty"}
> !2 = !{i64 8, !"GlobalProperty}
>
> With that we would strip only the metadata not containing this information.
>
> For devirtualization it would make sense with invariant.load,
> invariant.group and dereferenceable.
>
> What do you think about this idea?
>
> Do you have any comments? I would like to know if the idea does even make
sense, so I won't start writing prototype that will be throwed to thrash
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170403/790f612b/attachment.html>

On Mon, Apr 3, 2017 at 2:01 PM Piotr Padlewski <piotr.padlewski at
gmail.com>
wrote:
> 2017-04-01 15:59 GMT+02:00 Piotr Padlewski <piotr.padlewski at
gmail.com>:
>
>
>
> 2017-03-31 23:20 GMT+02:00 Sanjoy Das <sanjoy at
playingwithpointers.com>:
>
> Hi Piotr,
>
> On March 31, 2017 at 1:07:12 PM, Piotr Padlewski
> (piotr.padlewski at gmail.com) wrote:
> > [snip]
> > Do I understand it correctly, that it is legal to do the hoist because
> all
> > of the instructions above %vtable does not throw?
>
> Yes, I think you're right.  HeaderMayThrow is a conservative
> approximation, and the conservativeness is biting us here.
>
> > Are there any plans to fix it in the future? The fix doesn't seem
hard to
>
> Not to my knowledge.
>
> > write and I can do it, but I am not sure if it won't be too
expensive.
>
> Maybe we can do it (relatively) cheaply:
>
>  - Remember the first throwing instruction in the header, instead of a
>    boolean, in LoopSafetyInfo
>
>  - In hoistRegion, remember if you've seen the first throwing
>    instruction yet
>
>  - Pass the above as a boolean parameter to isGuaranteedToExecute, and
>    instead of
>      if (Inst.getParent() == CurLoop->getHeader())
>        return !SafetyInfo->HeaderMayThrow;
>    do something like
>      if (Inst.getParent() == CurLoop->getHeader())
>        return IsBeforeThrowingInst;
>
> -- Sanjoy
>
> I was thinking about something very similar and it seems to be a good
> approach to me because it has much lower complexity.
>
> In the review Sanjoy correctly spoted that I am not discarding
> invariant.group metadata when hoisting, which is incorrect in general.
> This generates a big problem to devirtualization, because discarding
> metadata when hoisting vtable load might be worse than not hoisting when
> there might be another load/store with !invariant.group dominating it
> (e.g. after inlining).
>
> I don't see any way to model it right now in LLVM, but I see a one
simple
> solution:
>  add extra information to the metadata nodes indicating that this property
> is non-local:
>
> %0 = load... %p, !invariant.group !1, !dereferenceable !2
> %1 = load ... %0, !invariant.load !0, !dereferenceable !2
>
> !0 = !{!"GlobalProperty"}
> !1 = !{!"MyType", !"GlobalProperty"}
> !2 = !{i64 8, !"GlobalProperty}
>
> With that we would strip only the metadata not containing this information.
>
> For devirtualization it would make sense with invariant.load,
> invariant.group and dereferenceable.
>
> What do you think about this idea?
>
> Do you have any comments? I would like to know if the idea does even make
> sense, so I won't start writing prototype that will be throwed to
thrash
>
I don't really see why you need a separate property....

It seems plausible that rather than having the hoisting logic handle
invariant metadata generically (by stripping it when hoisting) it could
instead be aware of invariant metadata and try to avoid hoisting the load.

But this will end up being yet another way in which enabling invariants
obstructs normal optimizations to get devirtualization. I'm increasingly
worried that the cost is going to outweigh the gain.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170404/5e7ad414/attachment.html>

2017-04-04 19:15 GMT+02:00 Chandler Carruth <chandlerc at google.com>:
> On Mon, Apr 3, 2017 at 2:01 PM Piotr Padlewski <piotr.padlewski at
gmail.com>
> wrote:
>
>> 2017-04-01 15:59 GMT+02:00 Piotr Padlewski <piotr.padlewski at
gmail.com>:
>>
>>
>>
>> 2017-03-31 23:20 GMT+02:00 Sanjoy Das <sanjoy at
playingwithpointers.com>:
>>
>> Hi Piotr,
>>
>> On March 31, 2017 at 1:07:12 PM, Piotr Padlewski
>> (piotr.padlewski at gmail.com) wrote:
>> > [snip]
>> > Do I understand it correctly, that it is legal to do the hoist
because
>> all
>> > of the instructions above %vtable does not throw?
>>
>> Yes, I think you're right.  HeaderMayThrow is a conservative
>> approximation, and the conservativeness is biting us here.
>>
>> > Are there any plans to fix it in the future? The fix doesn't
seem hard
>> to
>>
>> Not to my knowledge.
>>
>> > write and I can do it, but I am not sure if it won't be too
expensive.
>>
>> Maybe we can do it (relatively) cheaply:
>>
>>  - Remember the first throwing instruction in the header, instead of a
>>    boolean, in LoopSafetyInfo
>>
>>  - In hoistRegion, remember if you've seen the first throwing
>>    instruction yet
>>
>>  - Pass the above as a boolean parameter to isGuaranteedToExecute, and
>>    instead of
>>      if (Inst.getParent() == CurLoop->getHeader())
>>        return !SafetyInfo->HeaderMayThrow;
>>    do something like
>>      if (Inst.getParent() == CurLoop->getHeader())
>>        return IsBeforeThrowingInst;
>>
>> -- Sanjoy
>>
>> I was thinking about something very similar and it seems to be a good
>> approach to me because it has much lower complexity.
>>
>> In the review Sanjoy correctly spoted that I am not discarding
>> invariant.group metadata when hoisting, which is incorrect in general.
>> This generates a big problem to devirtualization, because discarding
>> metadata when hoisting vtable load might be worse than not hoisting
when
>> there might be another load/store with !invariant.group dominating it
>> (e.g. after inlining).
>>
>> I don't see any way to model it right now in LLVM, but I see a one
simple
>> solution:
>>  add extra information to the metadata nodes indicating that this
>> property is non-local:
>>
>> %0 = load... %p, !invariant.group !1, !dereferenceable !2
>> %1 = load ... %0, !invariant.load !0, !dereferenceable !2
>>
>> !0 = !{!"GlobalProperty"}
>> !1 = !{!"MyType", !"GlobalProperty"}
>> !2 = !{i64 8, !"GlobalProperty}
>>
>> With that we would strip only the metadata not containing this
>> information.
>>
>> For devirtualization it would make sense with invariant.load,
>> invariant.group and dereferenceable.
>>
>> What do you think about this idea?
>>
>> Do you have any comments? I would like to know if the idea does even
make
>> sense, so I won't start writing prototype that will be throwed to
thrash
>>
>
> I don't really see why you need a separate property....
>
> It seems plausible that rather than having the hoisting logic handle
> invariant metadata generically (by stripping it when hoisting) it could
> instead be aware of invariant metadata and try to avoid hoisting the load.
>
> So when we hoist based on the guarantee that it will be executed it seems
to be safe to keep the metadata. LICM always discard.
So we could only hoist invariant.group loads if they are guarantee to
execute.
Right now LICM will not hoist any invariant.group load, because it doesn't
know it is invariant.

It would be still nice to hoist it when we know that it is safe to load
from vptr and from vtable, but we can't do it if we will discard medata
(for this
case we need dereferenceable)

> But this will end up being yet another way in which enabling invariants
> obstructs normal optimizations to get devirtualization. I'm
increasingly
> worried that the cost is going to outweigh the gain.
>
What kind of cost you are reffering?
If we would add a way to say that specific metadata is a global property,
then I don't think the cost of maitanence (understanding idea, fixing
documentation
and fixing passes) would be higher than the gains, because I assume it
would be very low.
It does not seem to be that complicated to understand and use,
and to implement this we would only need function like
`dropAllUnknownLocalMetadata` that would replace `dropAllUnknownMedatata`
in most of the
places. We could even firstly fix LICM, and then fix other passes, because
the global properties would not guarantee that they would be not discarded.

When we add medata in the frontend then in most cases (probably all,
because it is not that easy to add metadata depending on the BB) it is a
non local property. Because of this it seems weird that we can only model
it as a local property.


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

Hi Piotr,

On Mon, Apr 3, 2017 at 2:01 PM, Piotr Padlewski
<piotr.padlewski at gmail.com> wrote:
>> I don't see any way to model it right now in LLVM, but I see a one
simple
>> solution:
>>  add extra information to the metadata nodes indicating that this
property
>> is non-local:
>>
>> %0 = load... %p, !invariant.group !1, !dereferenceable !2
>> %1 = load ... %0, !invariant.load !0, !dereferenceable !2
>>
>> !0 = !{!"GlobalProperty"}
>> !1 = !{!"MyType", !"GlobalProperty"}
>> !2 = !{i64 8, !"GlobalProperty}
>>
>> With that we would strip only the metadata not containing this
>> information.
>>
>> For devirtualization it would make sense with invariant.load,
>> invariant.group and dereferenceable.
>>
>> What do you think about this idea?
I'm sorry for being *this* annoying, but I'm not on board with this.  :)

I think this will run into the same dead-code-can-affect-behavior
issue discussed in https://reviews.llvm.org/D20116.

Specifically, if your program is:

if (false) {
  ptr = load i8*, i8** %ptrptr, !dereferenceable !{i64 8, !"GlobalProperty}
  // ptr is not actually dereferenceable, even the load above has UB
  // (since the metadata is "wrong"), but it is never executed so all
is well.
  int val = *ptr;
}

then you could transform it to

ptr = load i8*, i8** %ptrptr, !dereferenceable !{i64 8, !"GlobalProperty}
// ptr is not actually dereferenceable
int val = *ptr;
if (false) {
}

and you'd have gone from a program with no UB to one with UB.

-- Sanjoy

2017-04-05 18:30 GMT+02:00 Sanjoy Das <sanjoy at playingwithpointers.com>:
> Hi Piotr,
>
> On Mon, Apr 3, 2017 at 2:01 PM, Piotr Padlewski
> <piotr.padlewski at gmail.com> wrote:
> >> I don't see any way to model it right now in LLVM, but I see a
one
> simple
> >> solution:
> >>  add extra information to the metadata nodes indicating that this
> property
> >> is non-local:
> >>
> >> %0 = load... %p, !invariant.group !1, !dereferenceable !2
> >> %1 = load ... %0, !invariant.load !0, !dereferenceable !2
> >>
> >> !0 = !{!"GlobalProperty"}
> >> !1 = !{!"MyType", !"GlobalProperty"}
> >> !2 = !{i64 8, !"GlobalProperty}
> >>
> >> With that we would strip only the metadata not containing this
> >> information.
> >>
> >> For devirtualization it would make sense with invariant.load,
> >> invariant.group and dereferenceable.
> >>
> >> What do you think about this idea?
>
> I'm sorry for being *this* annoying, but I'm not on board with
this.  :)
>
> I think this will run into the same dead-code-can-affect-behavior
> issue discussed in https://reviews.llvm.org/D20116.
>
> Specifically, if your program is:
>
> if (false) {
>   ptr = load i8*, i8** %ptrptr, !dereferenceable !{i64 8,
!"GlobalProperty}
>   // ptr is not actually dereferenceable, even the load above has UB
>   // (since the metadata is "wrong"), but it is never executed so
all is
> well.
>   int val = *ptr;
> }
>
> then you could transform it to
>
> ptr = load i8*, i8** %ptrptr, !dereferenceable !{i64 8,
!"GlobalProperty}
> // ptr is not actually dereferenceable
> int val = *ptr;
> if (false) {
> }
>
> and you'd have gone from a program with no UB to one with UB.
>
> -- Sanjoy
>
I disagree, I find it different than the patch you mentioned. We don't have
any problems with code like this:

ptr = load i8*, i8** %ptrptr, !dereferenceable !{i64 8}
if (false) {

  // ptr is not actually dereferenceable, even the load above has UB
  // (since the metadata is "wrong"), but it is never executed so all
is
well.
  int val = *ptr;
}

because we rely on the information provided by someone else that ptr is
dereferenceable, so we can transform it to

ptr = load i8*, i8** %ptrptr, !dereferenceable !{i64 8}
// ptr is not actually dereferenceable
int val = *ptr;
if (false) {
}

And this is exactly how we treat any other UB.
It is also important to mention that in order to perform optimization you
have mentioned we need to know that %ptrptr is also dereferenceable.
The vptr and vtable properties are non local, so I don't see how
hoisting vptr load could be dangerous:

void foo(A& a) {
  if (false)
    a.foo();
}

will be:

void foo(A* dereferenceable(8) %a) {
  if (false)
    %vptr = load %a, !dereferenceable !{VtableSize, "GlobalProperty"},
!invariant.group !0
    %vfunction = load %vptr, !invariant.load !0
    call %vfunction();
}

and after hoisting:

void foo(A* dereferenceable(8) %a) {
  %vptr = load %a, !dereferenceable !{VtableSize, "GlobalProperty"},
!invariant.group !{"GlobalProperty"}
  %vfunction = load %vptr, !invariant.load !{"GlobalProperty"}
  if (false)
    call %vfunction();
}
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170406/ed368791/attachment.html>