<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Fri, Feb 13, 2015 at 1:37 PM, Kaylor, Andrew <span dir="ltr"><<a href="mailto:andrew.kaylor@intel.com" target="_blank">andrew.kaylor@intel.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div lang="EN-US" link="blue" vlink="purple">
<div>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">(Moving this discussion on list as this could be of general interest.)<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">My current work-in-progress implementation is attempting to map out the blocks used by a landing pad before it starts outlining. It creates a table of catch
and cleanup handlers with the block at which each one starts. During outlining I intend to have another mechanism to check to see if we’ve already outlined the handler at the specified start block (which handles the case of handlers shared between landing
pads) and if not starts the outlining process at that block. For cleanup handlers I’m treating any catch dispatch block (identified by looking for the eh_typeid_for+cmp+conditional branch pattern) as a stopping point for the cloning process.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">Here’s a snippet of comments explaining how I am doing the block mapping.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// The landing pad sequence will have this basic shape:<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">//<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// <cleanup handler><u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// <selector comparison><u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// <catch handler><u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// <cleanup handler><u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// <selector comparison><u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// <catch handler><u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// <cleanup handler><u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// ...<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">//<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// Any of the cleanup slots may be absent. The cleanup slots may be occupied by<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// any arbitrary control flow, but all paths through the cleanup code must<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// eventually reach the next selector comparison and no path can skip to a<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// different selector comparisons, though some paths may terminate abnormally.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// Therefore, we will use a depth first search from the start of any given<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// cleanup block and stop searching when we find the next selector comparison.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">//<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// The catch handlers may also have any control structure, but we are only<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// interested in the start of the catch handlers, so we don't need to actually<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// follow the flow of the catch handlers. The start of the catch handlers can<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// be located from the compare instructions, but they can be skipped in the<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">// flow by following the contrary branch.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">//<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">This has a flaw in that cleanup code could contain blocks that are shared with control flows outside the cleanup block and use phi-dependent branching. If
the shared flow isn’t part of another cleanup handler this is only an efficiency problem as the non-cleanup flow will reach a landingpad or a function terminator before it hits a selector. However, if the shared block is shared with another cleanup handler,
it could lead to a catch dispatch that has nothing to do with the current block.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">It turns out that the cloning code handles this problem of shared blocks really well. It just clones everything and prunes the unwanted code paths based on
phi resolution and subsequent instruction simplification. I suppose I could clone the entire landing pad to do the block mapping and just discard the clone when I’m done, but that seems really horrific as a way of resolving this corner case problem. What
I’d like is to have a way to determine whether the successors of a block are phi-dependent and if so find a way to limit the search to paths that result from predecessors I’ve already seen. I can do this easily enough for simple phi dependence (like constant
phi values and a single comparison to choose a branch target) but I haven’t tried to see if the process I have in mind work would for arbitrarily complex cases. If you have any suggestions on this (like maybe a “isSuccessorPhiDependent()” function tucked
away somewhere that I haven’t noticed), I’d love to hear them.</span></p></div></div></blockquote><div><br></div><div>I think complex cases are unlikely and should be handled conservatively by cloning. A good example of the simple case is the way we lower __finally. Internally Clang has the invariant that it cannot double-emit local declarations twice while emitting a function. So for this test case, we had to make the exceptional cleanup path branch into normal path with a phi, and then have a conditional branch back over to the exceptional path.</div><div><br></div><div>// C++:</div><div>void f() {</div><div> __try { might_crash(); }</div><div> __finally {</div><div> mylabel: // better not emit twice!</div><div> int r; // better not emit twice!<br></div><div> r = do_cleanup();</div><div> if (!r)</div><div> goto mylabel;<br> }<br>}</div><div><br></div><div>// Simplified IR:</div><div><br></div><div>define void @f() {</div><div> %abnormal_termination = alloca i8</div><div> invoke void @might_crash()</div><div> to label %cont unwind label %lpad</div><div>cont:</div><div> store i8 0, i8* %abnormal_termination</div><div> br label %__finally</div><div>lpad:</div><div> landingpad { i8*, i32 } personality i32 (...)* @__C_specific_handler</div><div> cleanup</div><div><div> store i8 1, i8* %abnormal_termination</div><div> br label %__finally</div></div><div>__finally: ; code simplified for brevity</div><div> %r = call i1 @do_cleanup()</div><div> br i1 %r, label %__finally, label %done</div><div>done:</div><div> %ab = load i8* %abnormal_termination</div><div> %tobool = icmp eq i8 %ab, i8 0</div><div> br i1 %tobool, label %ret, label %resume</div><div>ret:</div><div> ret void</div><div>resume:</div><div> resume</div><div>}</div><div><br></div><div>You can see at -O0 we have these loads and stores, but at -O1 we'll have a phi-dependent branch that's really easy to analyze. It'd be good if the preparation pass could understand this much, and no more. :)</div></div></div></div>