<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p>JFYI, the addition of 'A' and 'C' in your example complicates
cost modeling a bunch.</p>
<p>I'll review the patch, just sharing a meta comment here.</p>
<p>Philip<br>
</p>
<div class="moz-cite-prefix">On 5/11/21 5:49 AM, Jingu Kang wrote:<br>
</div>
<blockquote type="cite"
cite="mid:HE1PR08MB2937FD49D06ADE3DDC7CB43799539@HE1PR08MB2937.eurprd08.prod.outlook.com">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="Generator" content="Microsoft Word 15 (filtered
medium)">
<style>@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";}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.EmailStyle22
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}.MsoChpDefault
{mso-style-type:export-only;
font-size:10.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]-->
<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 have extended your suggestion slightly
more as below.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"> newbound1
= min(n, c)<o:p></o:p></p>
<p class="MsoNormal"> newbound2
= max(n, c)<o:p></o:p></p>
<p class="MsoNormal"> while (iv < n) {
while(iv < newbound1) {<o:p></o:p></p>
<p class="MsoNormal"> A A<o:p></o:p></p>
<p class="MsoNormal"> if (iv < c) B<o:p></o:p></p>
<p class="MsoNormal"> B C<o:p></o:p></p>
<p class="MsoNormal"> C }<o:p></o:p></p>
<p class="MsoNormal"> } iv =
newbound1<o:p></o:p></p>
<p class="MsoNormal"> while (iv
< newbound2) {<o:p></o:p></p>
<p class="MsoNormal"> A<o:p></o:p></p>
<p class="MsoNormal"> C<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 have implemented a simple pass to split
bound of loop, which has conditional branch with IV, as above
example.
<a href="https://reviews.llvm.org/D102234"
moz-do-not-send="true">https://reviews.llvm.org/D102234</a>
It is initial version. If possible, please review it.<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> Jingu Kang
<a class="moz-txt-link-rfc2396E" href="mailto:Jingu.Kang@arm.com"><Jingu.Kang@arm.com></a> <br>
<b>Sent:</b> 04 May 2021 12:45<br>
<b>To:</b> Philip Reames
<a class="moz-txt-link-rfc2396E" href="mailto:listmail@philipreames.com"><listmail@philipreames.com></a>; Jingu Kang
<a class="moz-txt-link-rfc2396E" href="mailto:Jingu.Kang@arm.com"><Jingu.Kang@arm.com></a><br>
<b>Cc:</b> <a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<b>Subject:</b> RE: [llvm-dev] Enabling IRCE pass or
Adding something similar in the pipeline of new pass
manager<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Philip, I appreciate your kind comments.<o:p></o:p></p>
<p><span style="font-size:10.0pt;font-family:"Courier
New"">>In this example, forming the full
pre/main/post loop structure of IRCE is overkill.
Instead, we could simply restrict the loop bounds in the
following manner:<o:p></o:p></span></p>
<pre>><a href="http://loop.ph" target="_blank" moz-do-not-send="true">loop.ph</a>:<o:p></o:p></pre>
<pre>> ;; Warning: psuedo code, might have edge conditions wrong<o:p></o:p></pre>
<pre>> %c = icmp sgt %iv, %n<o:p></o:p></pre>
<pre>> %min = umax(%n, %a)<o:p></o:p></pre>
<pre>> br i1 %c, label %exit, label %<a href="http://loop.ph" target="_blank" moz-do-not-send="true">loop.ph</a><o:p></o:p></pre>
<pre>><o:p> </o:p></pre>
<pre>>loop.ph.split:<o:p></o:p></pre>
<pre>> br label %loop<o:p></o:p></pre>
<pre>><o:p> </o:p></pre>
<pre>>loop:<o:p></o:p></pre>
<pre>> %iv = phi i64 [ %inc, %loop ], [ 1, %<a href="http://loop.ph" target="_blank" moz-do-not-send="true">loop.ph</a> ]<o:p></o:p></pre>
<pre>> %src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv <o:p></o:p></pre>
<pre>> %val = load i64, i64* %src.arrayidx<o:p></o:p></pre>
<pre>> %dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv <o:p></o:p></pre>
<pre>> store i64 %val, i64* %dst.arrayidx<o:p></o:p></pre>
<pre>> %inc = add nuw nsw i64 %iv, 1<o:p></o:p></pre>
<pre>> %cond = icmp eq i64 %inc, %min<o:p></o:p></pre>
<pre>> br i1 %cond, label %exit, label %loop<o:p></o:p></pre>
<pre>><o:p> </o:p></pre>
<pre>>exit:<o:p></o:p></pre>
<pre>> ret void<o:p></o:p></pre>
<pre>>}<o:p></o:p></pre>
<pre>><o:p> </o:p></pre>
<pre>>I'm not quite sure what to call this transform, but it's not IRCE. If this example is actually general enough to cover your use cases, it's going to be a lot easier to judge profitability on than the general form of iteration set splitting<o:p></o:p></pre>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I agree with you. If the llvm community
is ok to accept above approach as a pass or a part of a
certain pass, I would be happy to implement it because I am
aiming to handle this case with llvm upstream.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p><span style="font-size:10.0pt;font-family:"Courier
New"">>Another way to frame this special case
might be to recognize the conditional block can be
inverted into an early exit. (Reasoning: %iv is strictly
increasing, condition is monotonic, path if not taken has
no observable effect) Consider:<o:p></o:p></span></p>
<pre>><a href="http://loop.ph" target="_blank" moz-do-not-send="true">loop.ph</a>:<o:p></o:p></pre>
<pre>> br label %loop<o:p></o:p></pre>
<pre>><o:p> </o:p></pre>
<pre>>loop:<o:p></o:p></pre>
<pre>> %iv = phi i64 [ %inc, %for.inc ], [ 1, %<a href="http://loop.ph" target="_blank" moz-do-not-send="true">loop.ph</a> ]<o:p></o:p></pre>
<pre>> %cmp = icmp sge i64 %iv, %a<o:p></o:p></pre>
<pre>> br i1 %cmp, label %exit, label %for.inc<o:p></o:p></pre>
<pre>><o:p> </o:p></pre>
<pre>>for.inc:<o:p></o:p></pre>
<pre>> %src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv <o:p></o:p></pre>
<pre>> %val = load i64, i64* %src.arrayidx<o:p></o:p></pre>
<pre>> %dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv <o:p></o:p></pre>
<pre>> store i64 %val, i64* %dst.arrayidx<o:p></o:p></pre>
<pre>> %inc = add nuw nsw i64 %iv, 1<o:p></o:p></pre>
<pre>> %cond = icmp eq i64 %inc, %n<o:p></o:p></pre>
<pre>> br i1 %cond, label %exit, label %loop<o:p></o:p></pre>
<pre>><o:p> </o:p></pre>
<pre>>exit:<o:p></o:p></pre>
<pre>> ret void<o:p></o:p></pre>
<pre>>}<o:p></o:p></pre>
<p><span style="font-size:10.0pt;font-family:"Courier
New"">>Once that's done, the multiple exit
vectorization work should vectorize this loop. Thinking
about it, I really like this variant.
<o:p></o:p></span></p>
<p class="MsoNormal"> I have not looked at the multiple exit
vectorization work yet but it looks we could consider the
inverted condition as early exit’s condition.<o:p></o:p></p>
<p><span style="font-size:10.0pt;font-family:"Courier
New"">>The costing here seems quite off. I have
not looked at how the vectorize costs predicated loads on
hardware without predication, but needing to scalarize a
conditional VF-times and form a vector again does not have
a cost of 3 million. This could definitely be improved.<o:p></o:p></span></p>
<p class="MsoNormal">I agree with you.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Additionally, if possible, I would like
to suggest to enable or add transformations in order to help
vectorization. For example, as removing conditional branch
inside loop, we could split a loop with dependency, which
blocks vectorization, into vectorizable loop and
non-vectorizable one using transformations like loop
distribution. I am not sure why these features have not been
enabled as default on pass manager but it would make more
loops vectorizable.<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>
</div>
</div>
</blockquote>
</body>
</html>