llvm dev - Mar 2017 - Dereferenceable load semantics & LICM

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 have an ebb analysis around that can, in constant time, tell you there
nearest dominating may throw that occurs before a given instruction, if
any.



On Fri, Mar 31, 2017, 11:20 AM Sanjoy Das <sanjoy at
playingwithpointers.com>
wrote:
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170331/a109d0bf/attachment.html>

Here's the simpler n-log-n processing time, log n lookup version if you
wanted to throw it somewhere.
I believe it should work.


std::map<std::pair<unsigned int, unsigned int>, Instruction *>
NearestDominatingMayThrow;
DenseMap<Instruction, std::pair<unsigned int, unsigned int>>
InstrDFS;

// This is a variant of updateDFSNumbers.

void assignMayThrowDFS(){
  unsigned int DFSNum = 0;
  SmallVector<std::pair<const DomTreeNode *,
                          typename DomTreeNode::const_iterator>,
                32> WorkStack;

   auto *ThisRoot = DT->getRootNode();

    if (!ThisRoot)
      return;


    WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin()));
    ThisRoot->DFSNumIn = DFSNum++;

    while (!WorkStack.empty()) {
      const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
      typename DomTreeNodeBase<NodeT>::const_iterator ChildIt          
WorkStack.back().second;

      // If we visited all of the children of this node, "recurse"
back up
the
      // stack setting the DFOutNum.
      if (ChildIt == Node->end()) {
        for (auto *I : Node->getBlock()) {
             auto &DFSPair = InstrDFS[I]
             DFSPair.second = DFSNum++;
             if (I->mayThrow())
               NearestDominatingMayThrow[DFSPair] = I;
             }
        WorkStack.pop_back();
      } else {
        // Otherwise, recursively visit this child.
        auto *Child = *ChildIt;
        ++WorkStack.back().second;

        WorkStack.push_back(std::make_pair(Child, Child->begin()));
        Child->DFSNumIn = DFSNum++;
        for (auto *I : Child->getBlock())
             InstrDFS[I].first = DFSNum++;

      }
    }


Now, for an instruction you want to find the nearest dominating may throw,
look it up in instrdfs, and use lower_bound on the map.  Note: if your
current instruction throws, you need to start at the previous one (fixable,
i'm just lazy).

I also haven't hand verified whether std::pair will do the right thing, but
what you want is the pair closest to your instruction where dfsnumin
(.first) is < your pair's dfsnumin, and dfsnumout (.second) is > than
your
pair's dfsnumout.

(IE that it dominates you)

This instruction is guaranteed to dominate you, if it exists, and is
guaranteed to be the closest thing that dominates you.



On Fri, Mar 31, 2017 at 3:45 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
> I have an ebb analysis around that can, in constant time, tell you there
> nearest dominating may throw that occurs before a given instruction, if
> any.
>
>
>
> On Fri, Mar 31, 2017, 11:20 AM Sanjoy Das <sanjoy at
playingwithpointers.com>
> wrote:
>
>> 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
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170331/58bec05a/attachment.html>

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?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170401/2bf6a738/attachment-0001.html>

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>