[llvm-dev] Dereferenceable load semantics & LICM

[Daniel Berlin via llvm-dev]

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>