<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p>Let me start by copying my comment for the review. <br>
</p>
<div class="phabricator-remarkup"><span class="transaction-comment"
data-sigil="transaction-comment" data-meta="0_34">
<div class="phabricator-remarkup">
<p><a href="https://reviews.llvm.org/p/mkazantsev/"
class="phui-tag-view phui-tag-type-person "
data-sigil="hovercard" data-meta="0_23"><span
class="phui-tag-core phui-tag-color-person">@mkazantsev</span></a>
and I have spent a lot of time working on vectorization of
similar loops. If you want to talk through this, I'd be
happy to jump on a call. You may also find my talk at last
years llvm conference on multiple exit loops useful
background.</p>
<p>A couple of general comments.</p>
<p>I really don't think that extending IRCE is the right path
forward here. IRCE has some serious design defects, and I'm
honestly quite nervous about it's correctness. I think that
iteration set splitting (the basic transform IRCE uses) is
absolutely something we should implement for the main
pipeline, but I'd approach it as building new infrastructure
to replace IRCE, not as getting IRCE on by default. In
particular, I suspect the value comes primarily from a cost
model driven approach to splitting, not IRCE's unconditional
one.</p>
<p>Second, I advise being very cautious about going directly
for the general case here. The general case for this is
*really really hard*. If it wasn't, we'd already have robust
solutions. If you can describe your motivating examples in a
bit more depth (maybe offline), we can see if we can find a
specific sub-case which is both tractable and profitable.</p>
<p>Thank you for continuing the conversation on llvm-dev, a
specific suggestion inline below. <br>
</p>
<p>I also forgot to mention the ongoing (currently stalled)
work on multiple exit vectorization. That might also be of
interest. <br>
</p>
</div>
</span></div>
<div class="moz-cite-prefix">On 4/29/21 7:58 AM, Jingu Kang via
llvm-dev wrote:<br>
</div>
<blockquote type="cite"
cite="mid:VI1PR08MB294106FD23B268BEC4FFECF1995F9@VI1PR08MB2941.eurprd08.prod.outlook.com">
<pre class="moz-quote-pre" wrap="">Hi All,
I am trying to vectorize some loops. Let 's see a simple loop.
while() {
...
if ()
...
}
As you can see, there is if statement inside loop. As you know, LoopVectorizer tries to predicate the block of if statement with its condition and it asks target machines the cost of the instructions. If there are load or store instructions in the block to be predicated and target machine does not support masked load and store, LoopVectorizer assigns big number to the load and store instructions and it means the loop is not vectorized with loop vectorizer. In this case, it is important to remove the if statement inside loop before LoopVectorizer.
We need to consider two cases to remove the if statement inside loop as below.
1. if statement's condition with loop invariant variables
2. if statement's condition with induction variables
For the first one, UnSwitch/SimpleUnSwitch pass handles the case. The passes hoist the loop invariant condition outside loop and unswitch loop.
For the second one, there could be several transformations but I think the IRCE pass is general solution. The pass splits the iteration space following the condition with induction variable.
At this moment, the only SimpleUnSwitch pass is in pipeline of new pass manager but IRCE is not.
Let's see an IR function to see the impact of IRCE pass.
target triple = "aarch64"
define void @foo(i64 %a, i64* noalias %src, i64* noalias %dst, i64 %n) {
entry:
br label %bb
bb:
%if.cond = icmp slt i64 1, %n
br i1 %if.cond, label %if.then, label %exit
if.then:
%if.cond.2 = icmp slt i64 10, %n
br i1 %if.cond.2, label %loop.ph, label %if.then.else
if.then.else:
br label %loop.ph
loop.ph:
br label %loop
loop:
%iv = phi i64 [ %inc, %for.inc ], [ 1, %loop.ph ]
%cmp = icmp slt i64 %iv, %a
br i1 %cmp, label %if.then.2, label %for.inc
if.then.2:
%src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv
%val = load i64, i64* %src.arrayidx
%dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv
store i64 %val, i64* %dst.arrayidx
br label %for.inc
for.inc:
%inc = add nuw nsw i64 %iv, 1
%cond = icmp eq i64 %inc, %n
br i1 %cond, label %exit, label %loop
exit:
ret void
}</pre>
</blockquote>
<p>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:</p>
<pre class="moz-quote-pre" wrap="">loop.ph:
;; Warning: psuedo code, might have edge conditions wrong
%c = icmp sgt %iv, %n
%min = umax(%n, %a)
br i1 %c, label %exit, label %loop.ph
loop.ph.split:
br label %loop
loop:
%iv = phi i64 [ %inc, %loop ], [ 1, %loop.ph ]
%src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv
%val = load i64, i64* %src.arrayidx
%dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv
store i64 %val, i64* %dst.arrayidx
%inc = add nuw nsw i64 %iv, 1
%cond = icmp eq i64 %inc, %min
br i1 %cond, label %exit, label %loop
exit:
ret void
}</pre>
<p>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. <br>
</p>
<p>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:</p>
<pre class="moz-quote-pre" wrap="">loop.ph:
br label %loop
loop:
%iv = phi i64 [ %inc, %for.inc ], [ 1, %loop.ph ]
%cmp = icmp sge i64 %iv, %a
br i1 %cmp, label %exit, label %for.inc
for.inc:
%src.arrayidx = getelementptr inbounds i64, i64* %src, i64 %iv
%val = load i64, i64* %src.arrayidx
%dst.arrayidx = getelementptr inbounds i64, i64* %dst, i64 %iv
store i64 %val, i64* %dst.arrayidx
%inc = add nuw nsw i64 %iv, 1
%cond = icmp eq i64 %inc, %n
br i1 %cond, label %exit, label %loop
exit:
ret void
}
</pre>
<p>Once that's done, the multiple exit vectorization work should
vectorize this loop. Thinking about it, I really like this
variant. <br>
</p>
<blockquote type="cite"
cite="mid:VI1PR08MB294106FD23B268BEC4FFECF1995F9@VI1PR08MB2941.eurprd08.prod.outlook.com">
<pre class="moz-quote-pre" wrap="">
If we try to vectorize above code, we can see below debug output.
opt -loop-vectorize -S ./test.ll -debug-only=loop-vectorize
LV: Scalar loop costs: 5.
...
LV: Found an estimated cost of 3000000 for VF 2 For instruction: %val = load i64, i64* %src.arrayidx, align 4
LV: Vector loop of width 2 costs: 1500004.
...
LV: Vectorization is possible but not beneficial</pre>
</blockquote>
<p>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.</p>
<blockquote type="cite"
cite="mid:VI1PR08MB294106FD23B268BEC4FFECF1995F9@VI1PR08MB2941.eurprd08.prod.outlook.com">
<pre class="moz-quote-pre" wrap="">
If we run IRCE pass ahead of loop vectorizer with SCEV changes <a class="moz-txt-link-freetext" href="https://reviews.llvm.org/D101409">https://reviews.llvm.org/D101409</a> and <a class="moz-txt-link-freetext" href="https://reviews.llvm.org/D100566">https://reviews.llvm.org/D100566</a>, we can see the loop is vectorized with below debug output.
opt -irce -irce-skip-profitability-checks -simplifycfg -instcombine -loop-vectorize -S ./test.ll -debug-only=loop-vectorize
LV: Scalar loop costs: 6.
LV: Vector loop of width 2 costs: 2.
In order to vectorize more loops which has conditional branch inside, we need to enable IRCE pass or add something similar ahead of loop vectorizer in the pipeline of new pass manager.
I had a short discussion with Philip and Nikita on <a class="moz-txt-link-freetext" href="https://reviews.llvm.org/D101409">https://reviews.llvm.org/D101409</a> and it looks we need more effort for IRCE pass or something similar features. If you have experience or idea about this, please share it.
Thanks
JinGu Kang
_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
</body>
</html>