llvm dev - May 2017 - Handling invariant.groups with equality + marking it as experimental

Hi folks,
I would like to ask for some help with handling invariant.group metadata
for pointer comparison. Currently, we have a problem with devirtualization
of this code:

void compare() {
    A* a = new A;
    a->foo();
    A* b = new(a) B;
    if (a == b) {
        b->foo();
    }
}


Now because it is legal to replace b with an in the branch the vtable load
will use old pointer operand with !invariant.group, which will lead to
devirtualization to A::foo().
I tried to fix that in the frontend by introducing barriers for dynamic
objects comparison, like:

if (barrier(a) == barrier(b))

Unfortunately, it didn't work out for all of the cases. Example by Hubert
Tong

struct A {
  virtual void foo() { printf("%s\n", __PRETTY_FUNCTION__); }
  int m;
  int *zip() { return &m; }
};
struct B : A {
  virtual void foo() { printf("%s\n", __PRETTY_FUNCTION__); }
};
int main(void) {
  A *ap = new A;
  ap->foo();
  int *const apz = ap->zip();
  B *bp = new (ap) B;
  if (apz == bp->zip()) {
    bp->foo();
  }
}


Here we don't compare vptrs, but pointers with small offset like:

a+4 == b+4


And because we can transform it to a == b, it breaks.


I started thinking about handling it in the LLVM instead, and my first
idea was as folows:

Because the invariant.group is associated with the pointer value,
preserving the invariant.group information when changing pointer seems
invalid.

If we replace one pointer with another, based on the comparision, we
could strip all of the invariant.group information from it.

This idea is good enough to solve the above code, but it not gonna
work for all the cases, like passing the pointer to a function or
returning it -

by doing later inlining we could get the same situation and we would
not know that we should strip invariant.group metadata.


Other idea is following:

We can replace the pointer by another pointer after barrier like:


if (a == b)

  use(b)

=>

if (a == b)

  use(barrier(a))


This would be probablly correct, but I am not sure if it is a good
solution, because It might actually make it worse from optimization
point of view.

I am also not sure what should be the semantics of the
barrier(constant) - should we constantfold it to constant? I am not
sure if constant pointer

can carry any invariant.group information - I am pretty sure that
*null* and *undef* does not carry it
(https://reviews.llvm.org/D32423).


The third solution I am thinking of is just not to propagate the new
value to every dominated use -

especially to instructions like calls, return or load/store with
invariant.group information.

To validate this idea I need some help from GVN wizzards - would it
break any important optimizations, etc?

Please help.




Also, Sanjoy proposed to mark invariant.group features as
experimental, so we will not be afraid to break behavior of frontends
that already use it.

Right now I am pretty sure that clang is the only one that curently
uses it (and not by default).

Is anyone ok with it?



Best

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

Hi folks,
I really need help to move forward, so any comments will be appreciated.

Piotr

2017-05-04 15:44 GMT+02:00 Piotr Padlewski <piotr.padlewski at gmail.com>:
> Hi folks,
> I would like to ask for some help with handling invariant.group metadata
> for pointer comparison. Currently, we have a problem with devirtualization
> of this code:
>
> void compare() {
>     A* a = new A;
>     a->foo();
>     A* b = new(a) B;
>     if (a == b) {
>         b->foo();
>     }
> }
>
>
> Now because it is legal to replace b with an in the branch the vtable load
> will use old pointer operand with !invariant.group, which will lead to
> devirtualization to A::foo().
> I tried to fix that in the frontend by introducing barriers for dynamic
> objects comparison, like:
>
> if (barrier(a) == barrier(b))
>
> Unfortunately, it didn't work out for all of the cases. Example by
Hubert
> Tong
>
> struct A {
>   virtual void foo() { printf("%s\n", __PRETTY_FUNCTION__); }
>   int m;
>   int *zip() { return &m; }
> };
> struct B : A {
>   virtual void foo() { printf("%s\n", __PRETTY_FUNCTION__); }
> };
> int main(void) {
>   A *ap = new A;
>   ap->foo();
>   int *const apz = ap->zip();
>   B *bp = new (ap) B;
>   if (apz == bp->zip()) {
>     bp->foo();
>   }
> }
>
>
> Here we don't compare vptrs, but pointers with small offset like:
>
> a+4 == b+4
>
>
> And because we can transform it to a == b, it breaks.
>
>
> I started thinking about handling it in the LLVM instead, and my first idea
was as folows:
>
> Because the invariant.group is associated with the pointer value,
preserving the invariant.group information when changing pointer seems invalid.
>
> If we replace one pointer with another, based on the comparision, we could
strip all of the invariant.group information from it.
>
> This idea is good enough to solve the above code, but it not gonna work for
all the cases, like passing the pointer to a function or returning it -
>
> by doing later inlining we could get the same situation and we would not
know that we should strip invariant.group metadata.
>
>
> Other idea is following:
>
> We can replace the pointer by another pointer after barrier like:
>
>
> if (a == b)
>
>   use(b)
>
> =>
>
> if (a == b)
>
>   use(barrier(a))
>
>
> This would be probablly correct, but I am not sure if it is a good
solution, because It might actually make it worse from optimization point of
view.
>
> I am also not sure what should be the semantics of the barrier(constant) -
should we constantfold it to constant? I am not sure if constant pointer
>
> can carry any invariant.group information - I am pretty sure that *null*
and *undef* does not carry it (https://reviews.llvm.org/D32423).
>
>
> The third solution I am thinking of is just not to propagate the new value
to every dominated use -
>
> especially to instructions like calls, return or load/store with
invariant.group information.
>
> To validate this idea I need some help from GVN wizzards - would it break
any important optimizations, etc?
>
> Please help.
>
>
>
>
> Also, Sanjoy proposed to mark invariant.group features as experimental, so
we will not be afraid to break behavior of frontends that already use it.
>
> Right now I am pretty sure that clang is the only one that curently uses it
(and not by default).
>
> Is anyone ok with it?
>
>
>
> Best
>
> Piotr
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170507/e783d29c/attachment.html>

Hi Piotr,

On Thu, May 4, 2017 at 6:44 AM, Piotr Padlewski
<piotr.padlewski at gmail.com> wrote:
> Also, Sanjoy proposed to mark invariant.group features as experimental, so
> we will not be afraid to break behavior of frontends that already use it.
>
> Right now I am pretty sure that clang is the only one that curently uses it
> (and not by default).
Firstly, yes, I think we should definitely make the barrier stuff
experimental.  I don't think it has been ironed out enough for
generally use.

Secondly, at this point I'm wondering if the barrier/invariant.group
is the right abstraction at all.  Are there other designs you
considered early on that we can revisit in the light of these issues?

-- Sanjoy