llvm dev - Mar 2017 - Dereferenceable load semantics & LICM

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>

Thanks guys!
I have another small example:

struct A {
   virtual void foo();
};

void indirect(A *a, int n) {
   for (int i = 0 ; i < n; i++)
     a->foo();
}

generates:

define void @_Z8indirectP1Ai(%struct.A* %a, i32 %n) local_unnamed_addr #0 {
entry:
  %cmp3 = icmp sgt i32 %n, 0
  br i1 %cmp3, label %for.body.lr.ph, label %for.cond.cleanup

for.body.lr.ph:                                   ; preds = %entry
  %0 = bitcast %struct.A* %a to void (%struct.A*)***
  br label %for.body

for.cond.cleanup.loopexit:                        ; preds = %for.body
  br label %for.cond.cleanup

for.cond.cleanup:                                 ; preds
%for.cond.cleanup.loopexit, %entry
  ret void

for.body:                                         ; preds = %for.body, %
for.body.lr.ph
  %i.04 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]
  %vtable = load void (%struct.A*)**, void (%struct.A*)*** %0, align 8,
!tbaa !4, !invariant.group !7
  %1 = load void (%struct.A*)*, void (%struct.A*)** %vtable, align 8,
!invariant.load !8
  tail call void %1(%struct.A* %a)
  %inc = add nuw nsw i32 %i.04, 1
  %exitcond = icmp eq i32 %inc, %n
  br i1 %exitcond, label %for.cond.cleanup.loopexit, label %for.body
}


So now `a` is not dereferenceable and I was counting that because we have
loop preheader that only executes if the loop executes,
it will be hoisted. for invariant.group load the isGuaranteedToExecute
returns with (!SafetyInfo->HeaderMayThrow).
The isGuaranteedToTransferExecutionToSuccessor called on the %vtable
instruction returns true,
but few instructions later, the call of %1 may throw.
Do I understand it correctly, that it is legal to do the hoist because all
of the instructions above  %vtable does not throw?
Are there any plans to fix it in the future? The fix doesn't seem hard to
write and I can do it, but I am not sure if it won't be too expensive.

Piotr

PS: please review the https://reviews.llvm.org/D31539


2017-03-31 19:33 GMT+02:00 Daniel Berlin <dberlin at dberlin.org>:
>
>
> 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/169b5f4b/attachment.html>

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