<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">Hi Justin,<br>
<br>
yeah entirely possible that this case isn't handled correctly.<br>
<br>
<blockquote type="cite"><span class="">As an aside, is there any
documentation for the algorithm used? Is it based on a
published paper?</span></blockquote>
Not really. IIRC I read about the general idea in some paper about
efficient code generation for DSPs, but essentially I came up with
most of the algorithm myself.<br>
<br>
Basically it just does the following. Assuming you have a control
flow like this:<br>
<br>
while (x) {<br>
a();<br>
if (b())<br>
break;<br>
c();<br>
}<br>
<br>
It reworks the flow into something like this:<br>
<br>
flow = true;<br>
while (x && flow) {<br>
a();<br>
if (b())<br>
flow = false;<br>
if (flow)<br>
c();<br>
}<br>
<br>
This is done by ordering all the basic blocks so you have as less
back edges as possible and as less dependencies as possible
between the basic blocks.<br>
<br>
Then all the conditions that result in the execution of a block
are noted in the maps and hash tables.<br>
<br>
And last all the edges that don't fit into a structurized form are
replaced with conditional execution.<br>
<br>
Regards,<br>
Christian.<br>
<br>
On 02.11.2015 18:43, Justin Holewinski wrote:<br>
</div>
<blockquote
cite="mid:CAJgxuadDrh1dMH0qOBJotsuRHZBomwuq4bvG7jZAdVK-0VCWjQ@mail.gmail.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<div dir="ltr"><a moz-do-not-send="true"
href="https://llvm.org/bugs/show_bug.cgi?id=25378">https://llvm.org/bugs/show_bug.cgi?id=25378</a><br>
<div><br>
</div>
<div>Thanks!</div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Mon, Nov 2, 2015 at 12:26 PM, Tom
Stellard <span dir="ltr"><<a moz-do-not-send="true"
href="mailto:tom@stellard.net" target="_blank">tom@stellard.net</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">+
Christian<br>
<span class=""><br>
On Mon, Nov 02, 2015 at 12:14:46PM -0500, Justin
Holewinski via llvm-dev wrote:<br>
> Hi,<br>
><br>
> I've been investigating the StructurizeCFG pass, and
it looks like it has<br>
> trouble handling CFG edges that break out of a loop
and go directly to the<br>
> function exit. Am I running up against a bug in the
structurizer, or a<br>
> general limitation of the algorithm used? As an
aside, is there any<br>
> documentation for the algorithm used? Is it based on
a published paper?<br>
><br>
<br>
</span>I'm not aware of any limitations, so this is a bug.
Can you file one at<br>
<a moz-do-not-send="true" href="http://llvm.org/bugs"
rel="noreferrer" target="_blank">llvm.org/bugs</a>.<br>
<br>
-Tom<br>
<div>
<div class="h5"><br>
><br>
> The input IR I have is the following:<br>
><br>
> define <4 x float> @structurizer_test(<4 x
float> %inp.coerce) {<br>
> %1 = extractelement <4 x float>
%inp.coerce, i32 0<br>
> %2 = fcmp ogt float %1, 0.000000e+00<br>
> br i1 %2, label %.lr.ph.i, label %._crit_edge.i<br>
><br>
> .lr.ph.i: ;
preds = %7, %0<br>
> %i.03.i = phi float [ %8, %7 ], [ 0.000000e+00,
%0 ]<br>
> %ret.02.i = phi <4 x float> [ %5, %7 ], [
<float 1.000000e+00, float<br>
> 1.000000e+00, float 1.000000e+00, float
1.000000e+00>, %0 ]<br>
> %3 = extractelement <4 x float> %ret.02.i,
i32 0<br>
> %4 = fadd fast float %3, 0xBFB99999A0000000<br>
> %5 = insertelement <4 x float> %ret.02.i,
float %4, i32 0<br>
> %6 = fcmp olt float %4, 5.000000e-01<br>
> br i1 %6, label %_Z9get_colorDv2_f.exit, label %7<br>
><br>
> ; <label>:7
; preds = %.lr.ph.i<br>
> %8 = fadd fast float %i.03.i, 1.000000e+01<br>
> %9 = fcmp olt float %8, %1<br>
> br i1 %9, label %.lr.ph.i, label %._crit_edge.i<br>
><br>
> ._crit_edge.i: ;
preds = %7, %0<br>
> %ret.0.lcssa.i = phi <4 x float> [
<float 1.000000e+00, float<br>
> 1.000000e+00, float 1.000000e+00, float
1.000000e+00>, %0 ], [ %5, %7 ]<br>
> %10 = insertelement <4 x float>
%ret.0.lcssa.i, float 0.000000e+00, i32 2<br>
> br label %_Z9get_colorDv2_f.exit<br>
><br>
> _Z9get_colorDv2_f.exit: ;
preds = %._crit_edge.i,<br>
> %.lr.ph.i<br>
> %.0.i = phi <4 x float> [ %10,
%._crit_edge.i ], [ %5, %.lr.ph.i ]<br>
> ret <4 x float> %.0.i<br>
> }<br>
><br>
> After structurization, I have a module that has
what looks like a<br>
> reasonable CFG, but bad branch conditions and PHIs:<br>
><br>
> define <4 x float> @structurizer_test(<4 x
float> %inp.coerce) {<br>
> %1 = extractelement <4 x float>
%inp.coerce, i32 0<br>
> %2 = fcmp ogt float %1, 0.000000e+00<br>
> %3 = xor i1 %2, true<br>
> br label %Flow<br>
><br>
> Flow: ;
preds = %Flow1, %0<br>
> %4 = phi <4 x float> [ %14, %Flow1 ], [
<float 1.000000e+00, float<br>
> 1.000000e+00, float 1.000000e+00, float
1.000000e+00>, %0 ]<br>
> %5 = phi <4 x float> [ %16, %Flow1 ], [
<float 1.000000e+00, float<br>
> 1.000000e+00, float 1.000000e+00, float
1.000000e+00>, %0 ]<br>
> %6 = phi float [ %17, %Flow1 ], [ 0.000000e+00,
%0 ]<br>
> %7 = phi i1 [ %18, %Flow1 ], [ %3, %0 ]<br>
> %8 = phi i1 [ false, %Flow1 ], [ %2, %0 ]<br>
> br i1 %8, label %.lr.ph.i, label %Flow1<br>
><br>
> .lr.ph.i: ;
preds = %Flow<br>
> %i.03.i = phi float [ %6, %Flow ]<br>
> %ret.02.i = phi <4 x float> [ %5, %Flow ]<br>
> %9 = extractelement <4 x float> %ret.02.i,
i32 0<br>
> %10 = fadd fast float %9, 0xBFB99999A0000000<br>
> %11 = insertelement <4 x float> %ret.02.i,
float %10, i32 0<br>
> %12 = fcmp olt float %10, 5.000000e-01<br>
> %13 = xor i1 %12, true<br>
> br i1 %13, label %19, label %Flow2<br>
><br>
> Flow1: ;
preds = %Flow2, %Flow<br>
> %14 = phi <4 x float> [ %23, %Flow2 ], [
%4, %Flow ]<br>
</div>
</div>
> %15 = phi <4 x float> [ %11, %Flow2 ], [
*undef*, %Flow ]<br>
<span class="">> %16 = phi <4 x float> [ %24,
%Flow2 ], [ %5, %Flow ]<br>
> %17 = phi float [ %25, %Flow2 ], [ %6, %Flow ]<br>
> %18 = phi i1 [ %26, %Flow2 ], [ %7, %Flow ]<br>
</span>> br i1 *true*, label %Flow3, label %Flow<br>
<span class="">><br>
> ; <label>:19
; preds = %.lr.ph.i<br>
> %20 = fadd fast float %i.03.i, 1.000000e+01<br>
> %21 = fcmp olt float %20, %1<br>
> %22 = xor i1 %21, true<br>
> br label %Flow2<br>
><br>
> Flow2: ;
preds = %19, %.lr.ph.i<br>
> %23 = phi <4 x float> [ %11, %19 ], [ %4,
%.lr.ph.i ]<br>
</span>> %24 = phi <4 x float> [ %11, %19 ], [
*undef*, %.lr.ph.i ]<br>
<span class="">> %25 = phi float [ %20, %19 ], [ undef,
%.lr.ph.i ]<br>
> %26 = phi i1 [ %22, %19 ], [ %7, %.lr.ph.i ]<br>
> br label %Flow1<br>
><br>
> Flow3: ;
preds = %Flow1<br>
> br i1 %18, label %._crit_edge.i, label
%_Z9get_colorDv2_f.exit<br>
><br>
> ._crit_edge.i: ;
preds = %Flow3<br>
> %ret.0.lcssa.i = phi <4 x float> [ %14,
%Flow3 ]<br>
> %27 = insertelement <4 x float>
%ret.0.lcssa.i, float 0.000000e+00, i32 2<br>
> br label %_Z9get_colorDv2_f.exit<br>
><br>
> _Z9get_colorDv2_f.exit: ;
preds = %._crit_edge.i,<br>
> %Flow3<br>
> %.0.i = phi <4 x float> [ %15, %Flow3 ], [
%27, %._crit_edge.i ]<br>
> ret <4 x float> %.0.i<br>
> }<br>
><br>
> Note the undef values in some of the PHIs and 'i1
true' for the loop branch<br>
> condition.<br>
><br>
><br>
><br>
> --<br>
><br>
> Thanks,<br>
><br>
> Justin Holewinski<br>
<br>
<br>
</span>> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
> <a moz-do-not-send="true"
href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"
rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
<br>
</blockquote>
</div>
<br>
<br clear="all">
<div><br>
</div>
-- <br>
<div class="gmail_signature"><br>
<div>Thanks,</div>
<div><br>
</div>
<div>Justin Holewinski</div>
</div>
</div>
</blockquote>
<br>
</body>
</html>