<div dir="ltr">Hi,<div><br clear="all"><div>I've been investigating the StructurizeCFG pass, and it looks like it has trouble handling CFG edges that break out of a loop and go directly to the function exit. Am I running up against a bug in the structurizer, or a general limitation of the algorithm used? As an aside, is there any documentation for the algorithm used? Is it based on a published paper?</div><div><br></div><div><br></div><div>The input IR I have is the following:</div><div><br></div><div><div><font face="monospace, monospace">define <4 x float> @structurizer_test(<4 x float> %inp.coerce) {</font></div><div><font face="monospace, monospace"> %1 = extractelement <4 x float> %inp.coerce, i32 0</font></div><div><font face="monospace, monospace"> %2 = fcmp ogt float %1, 0.000000e+00</font></div><div><font face="monospace, monospace"> br i1 %2, label %.lr.ph.i, label %._crit_edge.i</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">.lr.ph.i: ; preds = %7, %0</font></div><div><font face="monospace, monospace"> %i.03.i = phi float [ %8, %7 ], [ 0.000000e+00, %0 ]</font></div><div><font face="monospace, monospace"> %ret.02.i = phi <4 x float> [ %5, %7 ], [ <float 1.000000e+00, float 1.000000e+00, float 1.000000e+00, float 1.000000e+00>, %0 ]</font></div><div><font face="monospace, monospace"> %3 = extractelement <4 x float> %ret.02.i, i32 0</font></div><div><font face="monospace, monospace"> %4 = fadd fast float %3, 0xBFB99999A0000000</font></div><div><font face="monospace, monospace"> %5 = insertelement <4 x float> %ret.02.i, float %4, i32 0</font></div><div><font face="monospace, monospace"> %6 = fcmp olt float %4, 5.000000e-01</font></div><div><font face="monospace, monospace"> br i1 %6, label %_Z9get_colorDv2_f.exit, label %7</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:7 ; preds = %.lr.ph.i</font></div><div><font face="monospace, monospace"> %8 = fadd fast float %i.03.i, 1.000000e+01</font></div><div><font face="monospace, monospace"> %9 = fcmp olt float %8, %1</font></div><div><font face="monospace, monospace"> br i1 %9, label %.lr.ph.i, label %._crit_edge.i</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">._crit_edge.i: ; preds = %7, %0</font></div><div><font face="monospace, monospace"> %ret.0.lcssa.i = phi <4 x float> [ <float 1.000000e+00, float 1.000000e+00, float 1.000000e+00, float 1.000000e+00>, %0 ], [ %5, %7 ]</font></div><div><font face="monospace, monospace"> %10 = insertelement <4 x float> %ret.0.lcssa.i, float 0.000000e+00, i32 2</font></div><div><font face="monospace, monospace"> br label %_Z9get_colorDv2_f.exit</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">_Z9get_colorDv2_f.exit: ; preds = %._crit_edge.i, %.lr.ph.i</font></div><div><font face="monospace, monospace"> %.0.i = phi <4 x float> [ %10, %._crit_edge.i ], [ %5, %.lr.ph.i ]</font></div><div><font face="monospace, monospace"> ret <4 x float> %.0.i</font></div><div><font face="monospace, monospace">}</font></div></div><div><br></div><div>After structurization, I have a module that has what looks like a reasonable CFG, but bad branch conditions and PHIs:</div><div><br></div><div><div><font face="monospace, monospace">define <4 x float> @structurizer_test(<4 x float> %inp.coerce) {</font></div><div><font face="monospace, monospace"> %1 = extractelement <4 x float> %inp.coerce, i32 0</font></div><div><font face="monospace, monospace"> %2 = fcmp ogt float %1, 0.000000e+00</font></div><div><font face="monospace, monospace"> %3 = xor i1 %2, true</font></div><div><font face="monospace, monospace"> br label %Flow</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">Flow: ; preds = %Flow1, %0</font></div><div><font face="monospace, monospace"> %4 = phi <4 x float> [ %14, %Flow1 ], [ <float 1.000000e+00, float 1.000000e+00, float 1.000000e+00, float 1.000000e+00>, %0 ]</font></div><div><font face="monospace, monospace"> %5 = phi <4 x float> [ %16, %Flow1 ], [ <float 1.000000e+00, float 1.000000e+00, float 1.000000e+00, float 1.000000e+00>, %0 ]</font></div><div><font face="monospace, monospace"> %6 = phi float [ %17, %Flow1 ], [ 0.000000e+00, %0 ]</font></div><div><font face="monospace, monospace"> %7 = phi i1 [ %18, %Flow1 ], [ %3, %0 ]</font></div><div><font face="monospace, monospace"> %8 = phi i1 [ false, %Flow1 ], [ %2, %0 ]</font></div><div><font face="monospace, monospace"> br i1 %8, label %.lr.ph.i, label %Flow1</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">.lr.ph.i: ; preds = %Flow</font></div><div><font face="monospace, monospace"> %i.03.i = phi float [ %6, %Flow ]</font></div><div><font face="monospace, monospace"> %ret.02.i = phi <4 x float> [ %5, %Flow ]</font></div><div><font face="monospace, monospace"> %9 = extractelement <4 x float> %ret.02.i, i32 0</font></div><div><font face="monospace, monospace"> %10 = fadd fast float %9, 0xBFB99999A0000000</font></div><div><font face="monospace, monospace"> %11 = insertelement <4 x float> %ret.02.i, float %10, i32 0</font></div><div><font face="monospace, monospace"> %12 = fcmp olt float %10, 5.000000e-01</font></div><div><font face="monospace, monospace"> %13 = xor i1 %12, true</font></div><div><font face="monospace, monospace"> br i1 %13, label %19, label %Flow2</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">Flow1: ; preds = %Flow2, %Flow</font></div><div><font face="monospace, monospace"> %14 = phi <4 x float> [ %23, %Flow2 ], [ %4, %Flow ]</font></div><div><font face="monospace, monospace"> %15 = phi <4 x float> [ %11, %Flow2 ], [ <b>undef</b>, %Flow ]</font></div><div><font face="monospace, monospace"> %16 = phi <4 x float> [ %24, %Flow2 ], [ %5, %Flow ]</font></div><div><font face="monospace, monospace"> %17 = phi float [ %25, %Flow2 ], [ %6, %Flow ]</font></div><div><font face="monospace, monospace"> %18 = phi i1 [ %26, %Flow2 ], [ %7, %Flow ]</font></div><div><font face="monospace, monospace"> br i1 <b>true</b>, label %Flow3, label %Flow</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">; <label>:19 ; preds = %.lr.ph.i</font></div><div><font face="monospace, monospace"> %20 = fadd fast float %i.03.i, 1.000000e+01</font></div><div><font face="monospace, monospace"> %21 = fcmp olt float %20, %1</font></div><div><font face="monospace, monospace"> %22 = xor i1 %21, true</font></div><div><font face="monospace, monospace"> br label %Flow2</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">Flow2: ; preds = %19, %.lr.ph.i</font></div><div><font face="monospace, monospace"> %23 = phi <4 x float> [ %11, %19 ], [ %4, %.lr.ph.i ]</font></div><div><font face="monospace, monospace"> %24 = phi <4 x float> [ %11, %19 ], [ <b>undef</b>, %.lr.ph.i ]</font></div><div><font face="monospace, monospace"> %25 = phi float [ %20, %19 ], [ undef, %.lr.ph.i ]</font></div><div><font face="monospace, monospace"> %26 = phi i1 [ %22, %19 ], [ %7, %.lr.ph.i ]</font></div><div><font face="monospace, monospace"> br label %Flow1</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">Flow3: ; preds = %Flow1</font></div><div><font face="monospace, monospace"> br i1 %18, label %._crit_edge.i, label %_Z9get_colorDv2_f.exit</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">._crit_edge.i: ; preds = %Flow3</font></div><div><font face="monospace, monospace"> %ret.0.lcssa.i = phi <4 x float> [ %14, %Flow3 ]</font></div><div><font face="monospace, monospace"> %27 = insertelement <4 x float> %ret.0.lcssa.i, float 0.000000e+00, i32 2</font></div><div><font face="monospace, monospace"> br label %_Z9get_colorDv2_f.exit</font></div><div><font face="monospace, monospace"><br></font></div><div><font face="monospace, monospace">_Z9get_colorDv2_f.exit: ; preds = %._crit_edge.i, %Flow3</font></div><div><font face="monospace, monospace"> %.0.i = phi <4 x float> [ %15, %Flow3 ], [ %27, %._crit_edge.i ]</font></div><div><font face="monospace, monospace"> ret <4 x float> %.0.i</font></div><div><font face="monospace, monospace">}</font></div></div><div><br></div><div>Note the undef values in some of the PHIs and 'i1 true' for the loop branch condition.</div><div><br></div><div><br></div><div><br></div>-- <br><div class="gmail_signature"><br><div>Thanks,</div><div><br></div><div>Justin Holewinski</div></div>
</div></div>