llvm dev - Mar 2017 - Dereferenceable load semantics & LICM

Hi all,
I have a question about dereferenceable metadata on load instruction. I
have a patch (https://reviews.llvm.org/D31539) for LICM that hoists loads
with !invariant.group.
The motivation example is devirtualization:

struct A {
   virtual void foo();
};
int bar();
void indirect(A &a) {
  while(bar())
       a.foo();
}

With -O2 -fstrict-vtable-pointers we get:

define void @hoist(%struct.A* dereferenceable(8)) {
entry:
  %call1 = tail call i32 @bar()
  %tobool2 = icmp eq i32 %call1, 0
  br i1 %tobool2, label %while.end, label %while.body.lr.ph

while.body.lr.ph:                                 ; preds = %entry
  %b = bitcast %struct.A* %0 to void (%struct.A*)***

  br label %while.body

while.body:                                       ; preds = %
while.body.lr.ph, %while.body
  %vtable = load void (%struct.A*)**, void (%struct.A*)*** %b, align 8,
!invariant.group !0
  %1 = load void (%struct.A*)*, void (%struct.A*)** %vtable, align 8,
!invariant.load !0
  tail call void %1(%struct.A* %0)
  %call = tail call i32 @bar()
  %tobool = icmp eq i32 %call, 0
  br i1 %tobool, label %while.end.loopexit, label %while.body

while.end.loopexit:                               ; preds = %while.body
  br label %while.end

while.end:                                        ; preds %while.end.loopexit,
%entry
  ret void
}



We know that the load of vptr and virtual function will not change in this
loop, which is indicated by !invariant.group.
Hoisting invariant.group load is legal because %b is dereferenceable, but
hoisting next load is illegal by LICM because it can't prove that %vtable
is dereferenceable.
But if I add dereferenceable metadata on vtable load like

%vtable = load void (%struct.A*)**, void (%struct.A*)*** %b, align 8,
!invariant.group !0, !dereferenceable !1
!1 = !{i64 8}

Then it doesn't help either, because LICM drops !dereferencealbe metadata
when hoisting (and adding it would be invalid, because we don't know if it
is also dereferenceable in hoisted block).

On the other hand, after performing my LICM of !invariant.group load, GVN
hoists the second load and I am not sure why it is legal then.

Any ideas?

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

Hi Piotr,

On March 31, 2017 at 9:07:42 AM, Piotr Padlewski
(piotr.padlewski at gmail.com) wrote:
> Hi all,
> I have a question about dereferenceable metadata on load instruction. I
> have a patch (https://reviews.llvm.org/D31539) for LICM that hoists loads
> with !invariant.group.
> The motivation example is devirtualization:
> ...
> [snip]
>
> On the other hand, after performing my LICM of !invariant.group load, GVN
> hoists the second load and I am not sure why it is legal then.
I suspect what's going on is that we first canonicalize the loop to:

if (precondition) {
  do {
    vptr = load vtable;
    fptr = *vptr;
    ...
  } while (backedge_condition);
}

after which it is safe to transform the program to (modulo aliasing):

if (precondition) {
  vptr = load vtable;
  fptr = *vptr;
  do {
    ...
  } while (backedge_condition);
}

since the we moved a load from a ("strongly") postdominating location.
We know that once we were in the preheader we know we're definitely
going to execute the vptr and fptr loads, so they better be
dereferenceable.  In other words, we're "exploiting undefined
behavior" here.

-- Sanjoy

On Fri, Mar 31, 2017 at 10:23 AM, Sanjoy Das <sanjoy at
playingwithpointers.com
> wrote:
> Hi Piotr,
>
> On March 31, 2017 at 9:07:42 AM, Piotr Padlewski
> (piotr.padlewski at gmail.com) wrote:
> > Hi all,
> > I have a question about dereferenceable metadata on load instruction.
I
> > have a patch (https://reviews.llvm.org/D31539) for LICM that hoists
> loads
> > with !invariant.group.
> > The motivation example is devirtualization:
> > ...
> > [snip]
> >
> > On the other hand, after performing my LICM of !invariant.group load,
GVN
> > hoists the second load and I am not sure why it is legal then.
>
> I suspect what's going on is that we first canonicalize the loop to:
>
> if (precondition) {
>   do {
>     vptr = load vtable;
>     fptr = *vptr;
>     ...
>   } while (backedge_condition);
> }
>
> after which it is safe to transform the program to (modulo aliasing):
>
> if (precondition) {
>   vptr = load vtable;
>   fptr = *vptr;
>   do {
>     ...
>   } while (backedge_condition);
> }
>
> since the we moved a load from a ("strongly") postdominating
location.
> We know that once we were in the preheader we know we're definitely
> going to execute the vptr and fptr loads, so they better be
> dereferenceable.  In other words, we're "exploiting undefined
> behavior" here.
>
Yes, this appears to be exactly the case - dominance tells us they must
execute at least once in both situations.

>
> -- Sanjoy
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170331/3d38117d/attachment.html>