<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)">
<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;}
@font-face
{font-family:"Malgun Gothic";
panose-1:2 11 5 3 2 0 0 2 0 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
@font-face
{font-family:"\@Malgun Gothic";}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0cm;
font-size:10.0pt;
font-family:"Courier New";}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:Consolas;}
span.EmailStyle21
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
--></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" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal">Hi Philip,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I appreciate your kind guide.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">As you mentioned, the IndVars tries to widen the IV from the example. The SCEV fails to generate AddRecExpr from the zext because there could be overflow in `%inc = add i32 %i.0, 1`.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Let me check why clang does not set the NUW flag to `%inc = add i32 %i.0, 1`.<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">JinGu Kang<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b>From:</b> llvm-dev <llvm-dev-bounces@lists.llvm.org> <b>On Behalf Of
</b>Philip Reames via llvm-dev<br>
<b>Sent:</b> 29 November 2021 17:58<br>
<b>To:</b> Jingu Kang <Jingu.Kang@arm.com>; llvm-dev@lists.llvm.org<br>
<b>Subject:</b> Re: [llvm-dev] Question about supporting zext on IVUsers and LSR<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p>First, there are no "simple" question about LSR. :)<o:p></o:p></p>
<p>Second, I wouldn't view your example as an LSR problem, but a failed IR canonicalization. In the example, we'd try to widen the IV in IndVars, and LSR would expect the widening to have already been done. I'd take a look into why we're not widening the
IV as your next step.<o:p></o:p></p>
<p>Philip<o:p></o:p></p>
<div>
<p class="MsoNormal">On 11/25/21 6:37 AM, Jingu Kang via llvm-dev wrote:<o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal">Hi All,<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">I am looking at a simple example as below.<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"<o:p></o:p></p>
<p class="MsoNormal">target triple = "aarch64-unknown-linux-gnu"<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">%struct.base_s = type { %struct.range, i64, i64, i64*, i32, [4 x i32], [274 x %struct.match], i32, i32, i8, i8, i8, i32, i32, i32, [16 x [768 x i16]], [12 x [16 x i16]], [12 x i16], [12 x i16], [12 x i16], [12 x i16], [12 x [16 x i16]],
[4 x [64 x i16]], [114 x i16], [16 x i16], %struct.length, %struct.length, [4 x [64 x i32]], [4 x [128 x i32]], i32, i32, [16 x i32], i32, i32, i32, [4096 x %struct.opt] }<o:p></o:p></p>
<p class="MsoNormal">%struct.range = type { i64, i64, i32, i8, i64, i32, i32, [53 x i32], [53 x i16*] }<o:p></o:p></p>
<p class="MsoNormal">%struct.match = type { i32, i32 }<o:p></o:p></p>
<p class="MsoNormal">%struct.length = type { i16, i16, [16 x [8 x i16]], [16 x [8 x i16]], [256 x i16], [16 x [272 x i32]], i32, [16 x i32] }<o:p></o:p></p>
<p class="MsoNormal">%struct.opt = type { i32, i8, i8, i32, i32, i32, i32, i32, [4 x i32] }<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">define i32 @test(i32 %len, %struct.base_s* nocapture readonly %obj) {<o:p></o:p></p>
<p class="MsoNormal">entry:<o:p></o:p></p>
<p class="MsoNormal"> br label %while.cond<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">while.cond: ; preds = %while.cond, %entry<o:p></o:p></p>
<p class="MsoNormal"> %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]<o:p></o:p></p>
<p class="MsoNormal"> %idxprom = zext i32 %i.0 to i64<o:p></o:p></p>
<p class="MsoNormal"> %len1 = getelementptr inbounds %struct.base_s, %struct.base_s* %obj, i64 0, i32 6, i64 %idxprom, i32 0
<o:p></o:p></p>
<p class="MsoNormal"> %0 = load i32, i32* %len1, align 4<o:p></o:p></p>
<p class="MsoNormal"> %cmp = icmp ult i32 %0, %len<o:p></o:p></p>
<p class="MsoNormal"> %inc = add i32 %i.0, 1<o:p></o:p></p>
<p class="MsoNormal"> br i1 %cmp, label %while.cond, label %while.end<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">while.end: ; preds = %while.cond<o:p></o:p></p>
<p class="MsoNormal"> ret i32 %i.0<o:p></o:p></p>
<p class="MsoNormal">}<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">I expected the LSR pass extracts the loop invariant part from `%len1 = getelementptr` and hoists it to preheader. It could cause a new IV for the loop dependent part from gep inside loop and `%0 = load` could use it. However, it looks the
`IVUsers` does process the `%idxprom = zext`. I can see the `SCEVAddRecExpr` and `SCEVAddExpr` are handled in `isInteresting` function. It seems LSR pass does not also handle the `zext` for `IVChain`. If I remove the `%idxprom = zext` manually on above example,
I can see LSR works as the expectation. Does anyone know why the `zext` is not supported on IVUsers and LSR? Does it make LSR difficult to construct formulas and compare them? If I missed something, please let me know.<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">For reference, the assembly output of above example with `-O3` is as below.<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">test:<o:p></o:p></p>
<p class="MsoNormal"> mov w8, w0<o:p></o:p></p>
<p class="MsoNormal"> mov w0, #-1<o:p></o:p></p>
<p class="MsoNormal">.LBB0_1:<o:p></o:p></p>
<p class="MsoNormal"> add w0, w0, #1<o:p></o:p></p>
<p class="MsoNormal"> add x9, x1, w0, uxtw #3<o:p></o:p></p>
<p class="MsoNormal"> ldr w9, [x9, #724]<o:p></o:p></p>
<p class="MsoNormal"> cmp w9, w8<o:p></o:p></p>
<p class="MsoNormal"> b.lo .LBB0_1<o:p></o:p></p>
<p class="MsoNormal"> Ret<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">If I remove the `zext`, the output is as below and the loop has one less instruction against above output.<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">test:<o:p></o:p></p>
<p class="MsoNormal"> add x9, x1, #724<o:p></o:p></p>
<p class="MsoNormal"> mov x8, #-1<o:p></o:p></p>
<p class="MsoNormal">.LBB0_1:<o:p></o:p></p>
<p class="MsoNormal"> ldr w10, [x9], #8<o:p></o:p></p>
<p class="MsoNormal"> add x8, x8, #1<o:p></o:p></p>
<p class="MsoNormal"> cmp w10, w0<o:p></o:p></p>
<p class="MsoNormal"> b.lo .LBB0_1<o:p></o:p></p>
<p class="MsoNormal"> mov x0, x8<o:p></o:p></p>
<p class="MsoNormal"> ret<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">The IR code, in which the `zext` is removed, is as below.<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"<o:p></o:p></p>
<p class="MsoNormal">target triple = "aarch64-unknown-linux-gnu"<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">%struct.base_s = type { %struct.range, i64, i64, i64*, i32, [4 x i32], [274 x %struct.match], i32, i32, i8, i8, i8, i32, i32, i32, [16 x [768 x i16]], [12 x [16 x i16]], [12 x i16], [12 x i16], [12 x i16], [12 x i16], [12 x [16 x i16]],
[4 x [64 x i16]], [114 x i16], [16 x i16], %struct.length, %struct.length, [4 x [64 x i32]], [4 x [128 x i32]], i32, i32, [16 x i32], i32, i32, i32, [4096 x %struct.opt] }<o:p></o:p></p>
<p class="MsoNormal">%struct.range = type { i64, i64, i32, i8, i64, i32, i32, [53 x i32], [53 x i16*] }<o:p></o:p></p>
<p class="MsoNormal">%struct.match = type { i32, i32 }<o:p></o:p></p>
<p class="MsoNormal">%struct.length = type { i16, i16, [16 x [8 x i16]], [16 x [8 x i16]], [256 x i16], [16 x [272 x i32]], i32, [16 x i32] }<o:p></o:p></p>
<p class="MsoNormal">%struct.opt = type { i32, i8, i8, i32, i32, i32, i32, i32, [4 x i32] }<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">;define i32 @test(i32 %len, %struct.base_s* nocapture readonly %obj) {<o:p></o:p></p>
<p class="MsoNormal">define i64 @test(i32 %len, %struct.base_s* nocapture readonly %obj) {<o:p></o:p></p>
<p class="MsoNormal">entry:<o:p></o:p></p>
<p class="MsoNormal"> br label %while.cond<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">while.cond: ; preds = %while.cond, %entry<o:p></o:p></p>
<p class="MsoNormal">; %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]<o:p></o:p></p>
<p class="MsoNormal"> %i.0 = phi i64 [ 0, %entry ], [ %inc, %while.cond ]<o:p></o:p></p>
<p class="MsoNormal">; %idxprom = zext i32 %i.0 to i64<o:p></o:p></p>
<p class="MsoNormal">; %len1 = getelementptr inbounds %struct.base_s, %struct.base_s* %obj, i64 0, i32 6, i64 %idxprom, i32 0<o:p></o:p></p>
<p class="MsoNormal"> %len1 = getelementptr inbounds %struct.base_s, %struct.base_s* %obj, i64 0, i32 6, i64 %i.0, i32 0<o:p></o:p></p>
<p class="MsoNormal"> %0 = load i32, i32* %len1, align 4<o:p></o:p></p>
<p class="MsoNormal"> %cmp = icmp ult i32 %0, %len<o:p></o:p></p>
<p class="MsoNormal">; %inc = add i32 %i.0, 1<o:p></o:p></p>
<p class="MsoNormal"> %inc = add i64 %i.0, 1<o:p></o:p></p>
<p class="MsoNormal"> br i1 %cmp, label %while.cond, label %while.end<o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal">while.end: ; preds = %while.cond<o:p></o:p></p>
<p class="MsoNormal">; ret i32 %i.0<o:p></o:p></p>
<p class="MsoNormal"> ret i64 %i.0<o:p></o:p></p>
<p class="MsoNormal">}<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">JinGu Kang<o:p></o:p></p>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<pre>_______________________________________________<o:p></o:p></pre>
<pre>LLVM Developers mailing list<o:p></o:p></pre>
<pre><a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><o:p></o:p></pre>
<pre><a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p></o:p></pre>
</blockquote>
</div>
</div>
</body>
</html>