<div dir="ltr">Here's the simpler n-log-n processing time, log n lookup version if you wanted to throw it somewhere.<div>I believe it should work.</div><div><br><div><br></div><div>std::map<std::pair<unsigned int, unsigned int>, Instruction *> NearestDominatingMayThrow;</div><div>DenseMap<Instruction, std::pair<unsigned int, unsigned int>> InstrDFS;</div><div><br></div><div>// This is a variant of updateDFSNumbers.</div><div><br></div><div>void assignMayThrowDFS(){</div><div> unsigned int DFSNum = 0;</div><div><div> SmallVector<std::pair<const DomTreeNode *,</div><div> typename DomTreeNode::const_iterator>,</div><div> 32> WorkStack;</div><div><br></div><div> auto *ThisRoot = DT->getRootNode();</div><div><br></div><div> if (!ThisRoot)</div><div> return;</div><div><br></div><div> </div><div> WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin()));</div><div> ThisRoot->DFSNumIn = DFSNum++;</div><div><br></div><div> while (!WorkStack.empty()) {</div><div> const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;</div><div> typename DomTreeNodeBase<NodeT>::const_iterator ChildIt =</div><div> WorkStack.back().second;</div><div><br></div><div> // If we visited all of the children of this node, "recurse" back up the</div><div> // stack setting the DFOutNum.</div><div> if (ChildIt == Node->end()) {</div><div> for (auto *I : Node->getBlock()) {</div><div> auto &DFSPair = InstrDFS[I]</div><div> DFSPair.second = DFSNum++;</div><div> if (I->mayThrow())</div><div> NearestDominatingMayThrow[DFSPair] = I;</div><div> }</div><div> WorkStack.pop_back();</div><div> } else {</div><div> // Otherwise, recursively visit this child.</div><div> auto *Child = *ChildIt;</div><div> ++WorkStack.back().second;</div><div><br></div><div> WorkStack.push_back(std::make_pair(Child, Child->begin()));</div><div> Child->DFSNumIn = DFSNum++;</div><div> for (auto *I : Child->getBlock())</div><div> InstrDFS[I].first = DFSNum++;</div><div> </div><div> }</div><div> }</div></div><div><br></div><div><br></div><div>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).</div><div><br></div><div>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.</div><div><br></div><div>(IE that it dominates you)</div><div><br></div><div>This instruction is guaranteed to dominate you, if it exists, and is guaranteed to be the closest thing that dominates you.</div><div><br></div><div><br></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Mar 31, 2017 at 3:45 PM, Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">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. <div class="HOEnZb"><div class="h5"><div><br></div><div><br><div dir="auto"><br><div class="gmail_quote"><div dir="ltr">On Fri, Mar 31, 2017, 11:20 AM Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.<wbr>com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Piotr,<br class="m_2090109623312445326gmail_msg">
<br class="m_2090109623312445326gmail_msg">
On March 31, 2017 at 1:07:12 PM, Piotr Padlewski<br class="m_2090109623312445326gmail_msg">
(<a href="mailto:piotr.padlewski@gmail.com" class="m_2090109623312445326gmail_msg" target="_blank">piotr.padlewski@gmail.com</a>) wrote:<br class="m_2090109623312445326gmail_msg">
> [snip]<br class="m_2090109623312445326gmail_msg">
> Do I understand it correctly, that it is legal to do the hoist because all<br class="m_2090109623312445326gmail_msg">
> of the instructions above %vtable does not throw?<br class="m_2090109623312445326gmail_msg">
<br class="m_2090109623312445326gmail_msg">
Yes, I think you're right. HeaderMayThrow is a conservative<br class="m_2090109623312445326gmail_msg">
approximation, and the conservativeness is biting us here.<br class="m_2090109623312445326gmail_msg">
<br class="m_2090109623312445326gmail_msg">
> Are there any plans to fix it in the future? The fix doesn't seem hard to<br class="m_2090109623312445326gmail_msg">
<br class="m_2090109623312445326gmail_msg">
Not to my knowledge.<br class="m_2090109623312445326gmail_msg">
<br class="m_2090109623312445326gmail_msg">
> write and I can do it, but I am not sure if it won't be too expensive.<br class="m_2090109623312445326gmail_msg">
<br class="m_2090109623312445326gmail_msg">
Maybe we can do it (relatively) cheaply:<br class="m_2090109623312445326gmail_msg">
<br class="m_2090109623312445326gmail_msg">
- Remember the first throwing instruction in the header, instead of a<br class="m_2090109623312445326gmail_msg">
boolean, in LoopSafetyInfo<br class="m_2090109623312445326gmail_msg">
<br class="m_2090109623312445326gmail_msg">
- In hoistRegion, remember if you've seen the first throwing<br class="m_2090109623312445326gmail_msg">
instruction yet<br class="m_2090109623312445326gmail_msg">
<br class="m_2090109623312445326gmail_msg">
- Pass the above as a boolean parameter to isGuaranteedToExecute, and<br class="m_2090109623312445326gmail_msg">
instead of<br class="m_2090109623312445326gmail_msg">
if (Inst.getParent() == CurLoop->getHeader())<br class="m_2090109623312445326gmail_msg">
return !SafetyInfo->HeaderMayThrow;<br class="m_2090109623312445326gmail_msg">
do something like<br class="m_2090109623312445326gmail_msg">
if (Inst.getParent() == CurLoop->getHeader())<br class="m_2090109623312445326gmail_msg">
return IsBeforeThrowingInst;<br class="m_2090109623312445326gmail_msg">
<br class="m_2090109623312445326gmail_msg">
-- Sanjoy<br class="m_2090109623312445326gmail_msg">
</blockquote></div></div></div></div></div></blockquote></div><br></div>