<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:SimSun;
panose-1:2 1 6 0 3 1 1 1 1 1;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:SimSun;
panose-1:2 1 6 0 3 1 1 1 1 1;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 90.0pt 72.0pt 90.0pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:1352955469;
mso-list-type:hybrid;
mso-list-template-ids:1994007132 67698703 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l0:level1
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l0:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoNormal">Hi,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I have a program where during compilation <b>an unreachable subcomponent of the CFG was created after an edge is removed by jump threading</b>. Looks like this situation is not handled currently in jump threading. It would be great if anyone
can give some advice.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">The snippet of the IR:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><i>11: ; preds = %32, %10<o:p></o:p></i></p>
<p class="MsoNormal"><i> %12 = phi i16 [ undef, %10 ], [ %21, %32 ] ; after jump threading, [%21, %32] will remain but %32 is already made unreachable<o:p></o:p></i></p>
<p class="MsoNormal"><i> %13 = load i1, i1* @f, align 8<o:p></o:p></i></p>
<p class="MsoNormal"><i> %14 = zext i1 %13 to i16<o:p></o:p></i></p>
<p class="MsoNormal"><i> br label %17<o:p></o:p></i></p>
<p class="MsoNormal"><i><o:p> </o:p></i></p>
<p class="MsoNormal"><i>15: ; preds = %22<o:p></o:p></i></p>
<p class="MsoNormal"><i> %16 = icmp slt i16 %23, 77<o:p></o:p></i></p>
<p class="MsoNormal"><i> br i1 %16, label %25, label %27<o:p></o:p></i></p>
<p class="MsoNormal"><i><o:p> </o:p></i></p>
<p class="MsoNormal"><i>17: ; preds = %25, %11<o:p></o:p></i></p>
<p class="MsoNormal"><i> %18 = phi i16 [ 0, %11 ], [ %26, %25 ]<o:p></o:p></i></p>
<p class="MsoNormal"><i> %19 = phi i16 [ %12, %11 ], [ %21, %25 ]<o:p></o:p></i></p>
<p class="MsoNormal"><i> br label %20<o:p></o:p></i></p>
<p class="MsoNormal"><i><o:p> </o:p></i></p>
<p class="MsoNormal"><i>; CHECK: or<o:p></o:p></i></p>
<p class="MsoNormal"><i>20: ; preds = %17<o:p></o:p></i></p>
<p class="MsoNormal"><i> %21 = or i16 %19, %14<o:p></o:p></i></p>
<p class="MsoNormal"><i> store i16 %21, i16* %1, align 4, !tbaa !15<o:p></o:p></i></p>
<p class="MsoNormal"><i> br label %22<o:p></o:p></i></p>
<p class="MsoNormal"><i><o:p> </o:p></i></p>
<p class="MsoNormal"><i>22: ; preds = %20<o:p></o:p></i></p>
<p class="MsoNormal"><i> %23 = add i16 %18, 1<o:p></o:p></i></p>
<p class="MsoNormal"><i> %24 = icmp slt i16 %23, 7<o:p></o:p></i></p>
<p class="MsoNormal"><i> br i1 %24, label %25, label %15<o:p></o:p></i></p>
<p class="MsoNormal"><i><o:p> </o:p></i></p>
<p class="MsoNormal"><i>25: ; preds = %22, %15<o:p></o:p></i></p>
<p class="MsoNormal"><i> %26 = phi i16 [ %23, %22 ], [ 0, %15 ]<o:p></o:p></i></p>
<p class="MsoNormal"><i> br label %17, !llvm.loop !17<o:p></o:p></i></p>
<p class="MsoNormal"><i><o:p> </o:p></i></p>
<p class="MsoNormal"><i>; This bb will be deleted because in bb15 the jump to here is removed.<o:p></o:p></i></p>
<p class="MsoNormal"><i>27: ; preds = %15<o:p></o:p></i></p>
<p class="MsoNormal"><i> br label %28<o:p></o:p></i></p>
<p class="MsoNormal"><i><o:p> </o:p></i></p>
<p class="MsoNormal"><i>; This bb will become unreachable because bb27 is deleted, but it<o:p></o:p></i></p>
<p class="MsoNormal"><i>; still has predecessor %32 so it won't be trivally deleted.<o:p></o:p></i></p>
<p class="MsoNormal"><i>; CHECK-NOT: load i1, i1* @d<o:p></o:p></i></p>
<p class="MsoNormal"><i>28: ; preds = %27, %32<o:p></o:p></i></p>
<p class="MsoNormal"><i> %29 = phi i16 [ %33, %32 ], [ %23, %27 ]<o:p></o:p></i></p>
<p class="MsoNormal"><i> %30 = load i1, i1* @d, align 4<o:p></o:p></i></p>
<p class="MsoNormal"><i> br i1 %30, label %32, label %31<o:p></o:p></i></p>
<p class="MsoNormal"><i><o:p> </o:p></i></p>
<p class="MsoNormal"><i>; This bb will become unreachable because bb27 is deleted.<o:p></o:p></i></p>
<p class="MsoNormal"><i>; CHECK-NOT: store i1 true, i1* @f<o:p></o:p></i></p>
<p class="MsoNormal"><i>31: ; preds = %28<o:p></o:p></i></p>
<p class="MsoNormal"><i> store i1 true, i1* @f, align 8<o:p></o:p></i></p>
<p class="MsoNormal"><i> br label %32<o:p></o:p></i></p>
<p class="MsoNormal"><i><o:p> </o:p></i></p>
<p class="MsoNormal"><i>; This bb will become unreachable because bb27 is deleted.<o:p></o:p></i></p>
<p class="MsoNormal"><i>; CHECK-NOT: store i1 false, i1* @d<o:p></o:p></i></p>
<p class="MsoNormal"><i>32: ; preds = %31, %28<o:p></o:p></i></p>
<p class="MsoNormal"><i> %33 = and i16 %29, 11<o:p></o:p></i></p>
<p class="MsoNormal"><i> store i1 false, i1* @d, align 4<o:p></o:p></i></p>
<p class="MsoNormal"><i> %34 = icmp eq i16 %33, 0<o:p></o:p></i></p>
<p class="MsoNormal"><i> br i1 %34, label %11, label %28, !llvm.loop !19<o:p></o:p></i></p>
<p class="MsoNormal"><i><o:p> </o:p></i></p>
<p class="MsoNormal">As described in the IR comments, the branch to bb28 will be removed by jump threading, then bb28, bb31, and bb32 will become unreachable, but %12 uses bb32 as incoming block which causes problems in later passes.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">In the current jump threading implementation, if an incoming edge to a block is removed and there is no predecessor left, the block will be deleted. But this does not cover the situation above, because the unreachable blocks are connected
to each other. This is probably a corner case, but Iet me ask: should we enhance jump threading to capture this scenario?
<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I can think of two fixes:<o:p></o:p></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l0 level1 lfo1"><![if !supportLists]><span style="mso-list:Ignore">1.<span style="font:7.0pt "Times New Roman"">
</span></span><![endif]>Do some clean up to eliminate unreachable blocks at the end of jump threading. This seems to violate some existing assumption. E.g. I saw this comment from existing code: <i>“ // JumpThreading must not processes blocks unreachable
from entry. It's a waste of compute time and can potentially lead to hangs.</i>”<o:p></o:p></p>
<p class="MsoListParagraph" style="text-indent:-18.0pt;mso-list:l0 level1 lfo1"><![if !supportLists]><span style="mso-list:Ignore">2.<span style="font:7.0pt "Times New Roman"">
</span></span><![endif]>When each block is processed, identity the above scenario and deal with it. This probably requires update of DT for every iteration? Which could be very expensive.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Any advice/suggestion is greatly appreciated!<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Thanks,<o:p></o:p></p>
<p class="MsoNormal">Duanyang<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</body>
</html>