<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=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@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;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:2021394760;
mso-list-template-ids:-1885843926;}
@list l0:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:1.0in;
mso-level-number-position:left;
text-indent:-.25in;}
ol
{margin-bottom:0in;}
ul
{margin-bottom:0in;}
--></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="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal">I did not open a PR for this, myself. I believe our team has temporarily marked it as a known and lower priority edge case, since the test case is sufficiently convoluted.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I’m more than willing to help review and get a fix upstream, though.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">JB<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><b>From:</b> Nemanja Ivanovic <nemanja.i.ibm@gmail.com> <br>
<b>Sent:</b> Monday, July 12, 2021 5:34 AM<br>
<b>To:</b> Sjoerd Meijer <Sjoerd.Meijer@arm.com><br>
<b>Cc:</b> llvm-dev@lists.llvm.org; Nagurne, James <j-nagurne@ti.com><br>
<b>Subject:</b> [EXTERNAL] Re: [llvm-dev] Unsigned integer underflow in HardwareLoops pass (PPC, perhaps ARM)<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">I am just curious, was a PR ever opened for this? I can certainly confirm that this causes 2^64 iterations of the loop on PPC64 so this is probably something we should fix.<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">On Mon, Mar 29, 2021 at 1:45 PM Sjoerd Meijer via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Yep, that doesn't look good and deserves a PR and some more looking into.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Wondering why we haven't seen this before: I guess at higher optimisations levels this problem is hidden by iteration count checks generated by the vectoriser or loop unroller. <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">It is a bit of a funny test, as also shown by the code produced with a higher opt level, but that shouldn't be an excuse I think.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Cheers,<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:12.0pt;color:black">Sjoerd. <o:p></o:p></span></p>
</div>
<div class="MsoNormal" align="center" style="text-align:center">
<hr size="2" width="98%" align="center">
</div>
<div id="gmail-m_7139551247050508317divRplyFwdMsg">
<p class="MsoNormal"><b><span style="color:black">From:</span></b><span style="color:black"> llvm-dev <<a href="mailto:llvm-dev-bounces@lists.llvm.org" target="_blank">llvm-dev-bounces@lists.llvm.org</a>> on behalf of Nagurne, James via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
<b>Sent:</b> 26 March 2021 18:41<br>
<b>To:</b> '<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>' <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br>
<b>Subject:</b> [llvm-dev] Unsigned integer underflow in HardwareLoops pass (PPC, perhaps ARM)</span>
<o:p></o:p></p>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p>Our team is developing on a downstream target that utilizes the HardwareLoops pass and have found that it generates unexpected code with regards to a regression test that we have. I’ve not 100% vetted the test itself with regards to the specifics of the
C standard, but logically it makes sense:<o:p></o:p></p>
<p> <o:p></o:p></p>
<p>I have the test up on Compiler Explorer, and the offending code can be duplicated from a stock trunk clang on PowerPC:
<a href="https://godbolt.org/z/KzW3nYjra" target="_blank">https://godbolt.org/z/KzW3nYjra</a><o:p></o:p></p>
<p>The test itself intends to ensure that small-width loop counters are not promoted. It does this by constructing a loop with an unsigned 8-bit value and purposefully underflowing line 20 with ‘--count’. What is expected to happen is that the 8-bit value underflows
to 0xFF, and the loop goes on to execute 256 times, exiting the loop and returning 0. In the failure case where p increments past the end of buffer, the test returns 1. I believe this failure case is optimized out as undefined behavior.<o:p></o:p></p>
<p> <o:p></o:p></p>
<p>In the PowerPC disassembly of the compiled test:<o:p></o:p></p>
<p> <o:p></o:p></p>
<p> mr 30, 3<o:p></o:p></p>
<p>…<o:p></o:p></p>
<p> mtctr 30<o:p></o:p></p>
<p>.LBB0_1: # =>This Inner Loop Header: Depth=1<o:p></o:p></p>
<p> bdnz .LBB0_1<o:p></o:p></p>
<p> <o:p></o:p></p>
<ol start="1" type="1">
<li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l0 level1 lfo1">
r3 (count) is placed into r30<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l0 level1 lfo1">
The memset (*p++ = 0) portion of the loop is factored out into an actual call to memset<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l0 level1 lfo1">
r30 (count) is placed into the CTR<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l0 level1 lfo1">
The CTR is used in bdnz <o:p></o:p></li></ol>
<ol start="4" type="1">
<ol start="1" type="a">
<li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l0 level2 lfo1">
With a quick glance at the definition of that instruction, the decrement happens before the compare. This means that the CTR may underflow, and will end up as either 0xffffffff or 0xffffffffffffffff<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l0 level2 lfo1">
The CTR will be compared to 0 and, now being a large positive value, will not be 0<o:p></o:p></li><li class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l0 level2 lfo1">
The branch will occur, repeating a-c a finite but undesirable number of times<o:p></o:p></li></ol>
</ol>
<p> <o:p></o:p></p>
<p>Digging slightly deeper into the pass itself, the inserted intrinsics don’t seem to care about the original counter type past the point where the counter is used in the hardware loop count initialization intrinsic:<o:p></o:p></p>
<p> <o:p></o:p></p>
<p>entry:<o:p></o:p></p>
<p> br label %do.body<o:p></o:p></p>
<p> <o:p></o:p></p>
<p>do.body: ; preds = %do.body, %entry<o:p></o:p></p>
<p> %count.addr.0 = phi i8 [ %count, %entry ], [ %dec, %do.body ]<o:p></o:p></p>
<p> %dec = add i8 %count.addr.0, -1<o:p></o:p></p>
<p> %cmp1.not = icmp eq i8 %dec, 0<o:p></o:p></p>
<p> br i1 %cmp1.not, label %do.end, label %do.body, !llvm.loop !2<o:p></o:p></p>
<p> <o:p></o:p></p>
<p>Becomes<o:p></o:p></p>
<p> <o:p></o:p></p>
<p>entry:<o:p></o:p></p>
<p> %0 = zext i8 %count to i32<o:p></o:p></p>
<p> call void @llvm.set.loop.iterations.i32(i32 %0)<o:p></o:p></p>
<p> br label %do.body<o:p></o:p></p>
<p> <o:p></o:p></p>
<p>do.body: ; preds = %do.body, %entry<o:p></o:p></p>
<p> %1 = call i1 @llvm.loop.decrement.i32(i32 1)<o:p></o:p></p>
<p> br i1 %1, label %do.body, label %do.end, !llvm.loop !2<o:p></o:p></p>
<p> <o:p></o:p></p>
<p>This seems like an oversight, albeit a very edge-casey one.<o:p></o:p></p>
<p> <o:p></o:p></p>
<p>J.B. Nagurne<o:p></o:p></p>
<p>Code Generation<o:p></o:p></p>
<p>Texas Instruments<o:p></o:p></p>
</div>
</div>
</div>
<p class="MsoNormal">_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p></o:p></p>
</blockquote>
</div>
</div>
</body>
</html>