<div dir="ltr">as I know, current IRCE implementation relies on some preconditions. it's intended to language runtime with garbage collection, not for loop vectorization.<div>the same is true for loop predication, which is also helpful for eliminating condition check within a loop.</div><div><br></div><div>Jie He</div><div>B.R</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, 11 May 2021 at 20:50, Jingu Kang via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div lang="EN-US" style="overflow-wrap: break-word;">
<div class="gmail-m_6473269197180563542WordSection1">
<p class="MsoNormal">Hi Philip,<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">I have extended your suggestion slightly more as below.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal"> newbound1 = min(n, c)<u></u><u></u></p>
<p class="MsoNormal"> newbound2 = max(n, c)<u></u><u></u></p>
<p class="MsoNormal"> while (iv < n) { while(iv < newbound1) {<u></u><u></u></p>
<p class="MsoNormal"> A A<u></u><u></u></p>
<p class="MsoNormal"> if (iv < c) B<u></u><u></u></p>
<p class="MsoNormal"> B C<u></u><u></u></p>
<p class="MsoNormal"> C }<u></u><u></u></p>
<p class="MsoNormal"> } iv = newbound1<u></u><u></u></p>
<p class="MsoNormal"> while (iv < newbound2) {<u></u><u></u></p>
<p class="MsoNormal"> A<u></u><u></u></p>
<p class="MsoNormal"> C<u></u><u></u></p>
<p class="MsoNormal"> }<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></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" target="_blank">https://reviews.llvm.org/D102234</a> It is initial version. If possible, please review it.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Thanks<u></u><u></u></p>
<p class="MsoNormal">JinGu Kang<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<div style="border-top:none;border-right:none;border-bottom:none;border-left:1.5pt solid blue;padding:0cm 0cm 0cm 4pt">
<div>
<div style="border-right:none;border-bottom:none;border-left:none;border-top:1pt solid rgb(225,225,225);padding:3pt 0cm 0cm">
<p class="MsoNormal"><b>From:</b> Jingu Kang <<a href="mailto:Jingu.Kang@arm.com" target="_blank">Jingu.Kang@arm.com</a>> <br>
<b>Sent:</b> 04 May 2021 12:45<br>
<b>To:</b> Philip Reames <<a href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>>; Jingu Kang <<a href="mailto:Jingu.Kang@arm.com" target="_blank">Jingu.Kang@arm.com</a>><br>
<b>Cc:</b> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">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<u></u><u></u></p>
</div>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Philip, I appreciate your kind comments.<u></u><u></u></p>
<p><span style="font-size:10pt;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:<u></u><u></u></span></p>
<pre>><a href="http://loop.ph" target="_blank">loop.ph</a>:<u></u><u></u></pre>
<pre>> ;; Warning: psuedo code, might have edge conditions wrong<u></u><u></u></pre>
<pre>> %c = icmp sgt %iv, %n<u></u><u></u></pre>
<pre>> %min = umax(%n, %a)<u></u><u></u></pre>
<pre>> br i1 %c, label %exit, label %<a href="http://loop.ph" target="_blank">loop.ph</a><u></u><u></u></pre>
<pre>><u></u> <u></u></pre>
<pre>>loop.ph.split:<u></u><u></u></pre>
<pre>> br label %loop<u></u><u></u></pre>
<pre>><u></u> <u></u></pre>
<pre>>loop:<u></u><u></u></pre>
<pre>> %iv = phi i64 [ %inc, %loop ], [ 1, %<a href="http://loop.ph" target="_blank">loop.ph</a> ]<u></u><u></u></pre>
<pre>> %src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv <u></u><u></u></pre>
<pre>> %val = load i64, i64* %src.arrayidx<u></u><u></u></pre>
<pre>> %dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv <u></u><u></u></pre>
<pre>> store i64 %val, i64* %dst.arrayidx<u></u><u></u></pre>
<pre>> %inc = add nuw nsw i64 %iv, 1<u></u><u></u></pre>
<pre>> %cond = icmp eq i64 %inc, %min<u></u><u></u></pre>
<pre>> br i1 %cond, label %exit, label %loop<u></u><u></u></pre>
<pre>><u></u> <u></u></pre>
<pre>>exit:<u></u><u></u></pre>
<pre>> ret void<u></u><u></u></pre>
<pre>>}<u></u><u></u></pre>
<pre>><u></u> <u></u></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<u></u><u></u></pre>
<p class="MsoNormal"><u></u> <u></u></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.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p><span style="font-size:10pt;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:<u></u><u></u></span></p>
<pre>><a href="http://loop.ph" target="_blank">loop.ph</a>:<u></u><u></u></pre>
<pre>> br label %loop<u></u><u></u></pre>
<pre>><u></u> <u></u></pre>
<pre>>loop:<u></u><u></u></pre>
<pre>> %iv = phi i64 [ %inc, %for.inc ], [ 1, %<a href="http://loop.ph" target="_blank">loop.ph</a> ]<u></u><u></u></pre>
<pre>> %cmp = icmp sge i64 %iv, %a<u></u><u></u></pre>
<pre>> br i1 %cmp, label %exit, label %for.inc<u></u><u></u></pre>
<pre>><u></u> <u></u></pre>
<pre>>for.inc:<u></u><u></u></pre>
<pre>> %src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv <u></u><u></u></pre>
<pre>> %val = load i64, i64* %src.arrayidx<u></u><u></u></pre>
<pre>> %dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv <u></u><u></u></pre>
<pre>> store i64 %val, i64* %dst.arrayidx<u></u><u></u></pre>
<pre>> %inc = add nuw nsw i64 %iv, 1<u></u><u></u></pre>
<pre>> %cond = icmp eq i64 %inc, %n<u></u><u></u></pre>
<pre>> br i1 %cond, label %exit, label %loop<u></u><u></u></pre>
<pre>><u></u> <u></u></pre>
<pre>>exit:<u></u><u></u></pre>
<pre>> ret void<u></u><u></u></pre>
<pre>>}<u></u><u></u></pre>
<p><span style="font-size:10pt;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.
<u></u><u></u></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.<u></u><u></u></p>
<p><span style="font-size:10pt;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.<u></u><u></u></span></p>
<p class="MsoNormal">I agree with you.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></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.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Thanks<u></u><u></u></p>
<p class="MsoNormal">JinGu Kang<u></u><u></u></p>
</div>
</div>
</div>
_______________________________________________<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" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature">Best Regards<br>He Jie 何杰</div>