Ehsan Amiri via llvm-dev
2016-Aug-25 20:30 UTC
[llvm-dev] Canonicalize induction variables
But even for a very simple loop:
int test1 (int *x, int *y, int *z, int k) {
int sum = 0;
for (int i = 10; i < k; i++) {
z[i] = x[i] / y[i];
}
return sum;
}
The initial value of induction variable is not zero after compiling with
-O3 -mcpu=power8 x.cpp -S -c -emit-llvm -fno-unroll-loops (see bottom of
the email for IR)
Also I can write somewhat more complicated loop where step size is a
constant > 1, and the conditions are so that IV will not overflow:
int test2 (int *x, int *y, int *z, int k) {
int sum = 0;
for (int i = 10; i < k && i < k-5; i+=5) {
z[i] = x[i] / y[i];
}
return sum;
}
again this is not canonicalized in the above sense (see IR at the end of
the email). Maybe this condition is too complicated?
IR for test1
for.body: ; preds %for.body.preheader,
%for.body
* %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 10,
%for.body.preheader ]*
%arrayidx = getelementptr inbounds i32, i32* %x, i64 %indvars.iv
%0 = load i32, i32* %arrayidx, align 4, !tbaa !1
%arrayidx2 = getelementptr inbounds i32, i32* %y, i64 %indvars.iv
%1 = load i32, i32* %arrayidx2, align 4, !tbaa !1
%div = sdiv i32 %0, %1
%arrayidx4 = getelementptr inbounds i32, i32* %z, i64 %indvars.iv
store i32 %div, i32* %arrayidx4, align 4, !tbaa !1
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
%exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count
br i1 %exitcond, label %for.cond.cleanup, label %for.body
IR for test2
for.body: ; preds %for.body.preheader,
%for.body
* %indvars.iv = phi i64 [ 10, %for.body.preheader ], [ %indvars.iv.next,
%for.body ]*
%arrayidx = getelementptr inbounds i32, i32* %x, i64 %indvars.iv
%2 = load i32, i32* %arrayidx, align 4, !tbaa !1
%arrayidx3 = getelementptr inbounds i32, i32* %y, i64 %indvars.iv
%3 = load i32, i32* %arrayidx3, align 4, !tbaa !1
%div = sdiv i32 %2, %3
%arrayidx5 = getelementptr inbounds i32, i32* %z, i64 %indvars.iv
store i32 %div, i32* %arrayidx5, align 4, !tbaa !1
* %indvars.iv.next = add nuw i64 %indvars.iv, 5*
%cmp = icmp slt i64 %indvars.iv.next, %1
%cmp1 = icmp slt i64 %indvars.iv.next, %0
%or.cond = and i1 %cmp, %cmp1
br i1 %or.cond, label %for.body, label %for.cond.cleanup.loopexit
On Thu, Aug 25, 2016 at 4:02 PM, Michael Kruse via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Not sure whether these are the actual reasons, but to explain the
> difficulties with those loops.
>
> 2016-08-25 3:48 GMT+02:00 Yaoqing Gao via llvm-dev <
> llvm-dev at lists.llvm.org>:
> > I just subscribed this group. This is my first time to post a
question
> (not
> > sure if this is a right place for discussion) after I have a brief
look
> at
> > LLVM OPT (dev trunk). I would expect loop simplification and
induction
> > variable canonicalization pass (IndVarSimplify pass) should be able to
> > convert the following loops into a simple canonical form, i.e., there
is
> a
> > canonical induction variable which starts at zero and steps by one,
> > getCanonicalInductionVariable() returns the first PHI node in the
loop
> > header block.
> >
> > int test1 (int x[], int k, int s) {
> > int sum = 0;
> > for (int i = 0; i < k; i+=s) {
> > sum += x[i];
> > }
> > return sum;
> > }
>
> s could be zero making this an endless loop (C has some rules saying
> that it can assume that certain loops do terminate, but I think it
> does not apply to LLVM IR)
>
>
> > int test2(int x[], int k, int s) {
> > int sum = 0;
> > for (int i = k; i > 0; i--) {
> > sum += x[i];
> > }
> > return sum;
> > }
>
> with k = INT_MIN where is no upper limit in that range. Neither
>
> for (int j = 0; j < -INT_MIN; j++)
>
> nor
>
> for (int j = 0; j <= INT_MAX; j++)
>
> do work here.
>
> >
> > Anyone can help explain why the current LLVM cannot canonicalize
> induction
> > variables for the above loops (by design or a limitation to be fixed
in
> the
> > future)? Thanks.
>
> The first could be tackled with loop versioning of the s==0 case. The
> second might be converted to
>
> for (int j = -1; j < -(k+1); j++)
>
> although this isn't the canonical form.
>
>
> Michael
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160825/c2f1a537/attachment.html>
Hi,
I have a "back to square one question -- why do you care about
having a canonical induction variable?
- If it is for easier analysis, a somewhat better approach is to lean
on SCEV to "understand" induction variables as much as possible.
- If it is for better codegen, then this should be solved in
LoopStrengthReduce.
That is not to say you're wrong in demanding this of LLVM, but I'd
like to understand your motivation a little better.
-- Sanjoy
Michael Kruse via llvm-dev
2016-Aug-31 14:10 UTC
[llvm-dev] Canonicalize induction variables
Hi again, I looked into the code of IndVarSimplify but found no code that changes the start value of the induction variable. It only modifies the exit test. However, the file's comment gives an example: // 1. The exit condition for the loop is canonicalized to compare the // induction value against the exit value. This turns loops like: // 'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)' I ran the example and it turns the loop into for (i = 7; i != 32; ++i) The part that makes induction variables start at zero may have been removed. Michael 2016-08-25 22:30 GMT+02:00 Ehsan Amiri <ehsanamiri at gmail.com>:> But even for a very simple loop: > > int test1 (int *x, int *y, int *z, int k) { > int sum = 0; > for (int i = 10; i < k; i++) { > z[i] = x[i] / y[i]; > } > return sum; > } > > The initial value of induction variable is not zero after compiling with -O3 > -mcpu=power8 x.cpp -S -c -emit-llvm -fno-unroll-loops (see bottom of the > email for IR) > > Also I can write somewhat more complicated loop where step size is a > constant > 1, and the conditions are so that IV will not overflow: > > int test2 (int *x, int *y, int *z, int k) { > int sum = 0; > for (int i = 10; i < k && i < k-5; i+=5) { > z[i] = x[i] / y[i]; > } > return sum; > } > > again this is not canonicalized in the above sense (see IR at the end of the > email). Maybe this condition is too complicated? > > > > > > > > > > > > > > > > IR for test1 > > > for.body: ; preds > %for.body.preheader, %for.body > %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 10, > %for.body.preheader ] > %arrayidx = getelementptr inbounds i32, i32* %x, i64 %indvars.iv > %0 = load i32, i32* %arrayidx, align 4, !tbaa !1 > %arrayidx2 = getelementptr inbounds i32, i32* %y, i64 %indvars.iv > %1 = load i32, i32* %arrayidx2, align 4, !tbaa !1 > %div = sdiv i32 %0, %1 > %arrayidx4 = getelementptr inbounds i32, i32* %z, i64 %indvars.iv > store i32 %div, i32* %arrayidx4, align 4, !tbaa !1 > %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 > %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count > br i1 %exitcond, label %for.cond.cleanup, label %for.body > > IR for test2 > > for.body: ; preds > %for.body.preheader, %for.body > %indvars.iv = phi i64 [ 10, %for.body.preheader ], [ %indvars.iv.next, > %for.body ] > %arrayidx = getelementptr inbounds i32, i32* %x, i64 %indvars.iv > %2 = load i32, i32* %arrayidx, align 4, !tbaa !1 > %arrayidx3 = getelementptr inbounds i32, i32* %y, i64 %indvars.iv > %3 = load i32, i32* %arrayidx3, align 4, !tbaa !1 > %div = sdiv i32 %2, %3 > %arrayidx5 = getelementptr inbounds i32, i32* %z, i64 %indvars.iv > store i32 %div, i32* %arrayidx5, align 4, !tbaa !1 > %indvars.iv.next = add nuw i64 %indvars.iv, 5 > %cmp = icmp slt i64 %indvars.iv.next, %1 > %cmp1 = icmp slt i64 %indvars.iv.next, %0 > %or.cond = and i1 %cmp, %cmp1 > br i1 %or.cond, label %for.body, label %for.cond.cleanup.loopexit > > > > On Thu, Aug 25, 2016 at 4:02 PM, Michael Kruse via llvm-dev > <llvm-dev at lists.llvm.org> wrote: >> >> Not sure whether these are the actual reasons, but to explain the >> difficulties with those loops. >> >> 2016-08-25 3:48 GMT+02:00 Yaoqing Gao via llvm-dev >> <llvm-dev at lists.llvm.org>: >> > I just subscribed this group. This is my first time to post a question >> > (not >> > sure if this is a right place for discussion) after I have a brief look >> > at >> > LLVM OPT (dev trunk). I would expect loop simplification and induction >> > variable canonicalization pass (IndVarSimplify pass) should be able to >> > convert the following loops into a simple canonical form, i.e., there is >> > a >> > canonical induction variable which starts at zero and steps by one, >> > getCanonicalInductionVariable() returns the first PHI node in the loop >> > header block. >> > >> > int test1 (int x[], int k, int s) { >> > int sum = 0; >> > for (int i = 0; i < k; i+=s) { >> > sum += x[i]; >> > } >> > return sum; >> > } >> >> s could be zero making this an endless loop (C has some rules saying >> that it can assume that certain loops do terminate, but I think it >> does not apply to LLVM IR) >> >> >> > int test2(int x[], int k, int s) { >> > int sum = 0; >> > for (int i = k; i > 0; i--) { >> > sum += x[i]; >> > } >> > return sum; >> > } >> >> with k = INT_MIN where is no upper limit in that range. Neither >> >> for (int j = 0; j < -INT_MIN; j++) >> >> nor >> >> for (int j = 0; j <= INT_MAX; j++) >> >> do work here. >> >> > >> > Anyone can help explain why the current LLVM cannot canonicalize >> > induction >> > variables for the above loops (by design or a limitation to be fixed in >> > the >> > future)? Thanks. >> >> The first could be tackled with loop versioning of the s==0 case. The >> second might be converted to >> >> for (int j = -1; j < -(k+1); j++) >> >> although this isn't the canonical form. >> >> >> Michael >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > >
[+CC llvm-dev] On Wed, Aug 31, 2016 at 1:36 PM, Yaoqing Gao <yaoqing.gao at gmail.com> wrote:> Hi, > Regarding the question about "why do you care about having a canonical > induction variable", we expect it can simplify loop transformations without > redundant analysis. Some loop (nest) transformations can be skipped earlier > if they don't have a canonical induction variable.Can you be more specific here (about the transforms and analyses that you expect to be able to simplify)? I'm asking because while it won't be super difficult to make indvars turn as many induction variables into canonical induction variables, I'd like to understand the problem you're trying to solve first. -- Sanjoy
Tobias Grosser via llvm-dev
2016-Aug-31 21:30 UTC
[llvm-dev] Canonicalize induction variables
On Wed, Aug 31, 2016, at 10:39 PM, Sanjoy Das via llvm-dev wrote:> [+CC llvm-dev] > > On Wed, Aug 31, 2016 at 1:36 PM, Yaoqing Gao <yaoqing.gao at gmail.com> > wrote: > > Hi, > > Regarding the question about "why do you care about having a canonical > > induction variable", we expect it can simplify loop transformations without > > redundant analysis. Some loop (nest) transformations can be skipped earlier > > if they don't have a canonical induction variable. > > Can you be more specific here (about the transforms and analyses > that you expect to be able to simplify)? > > I'm asking because while it won't be super difficult to make indvars > turn as many > induction variables into canonical induction variables, I'd like to > understand > the problem you're trying to solve first.Also, just as a historical note. indvars was at some point able to do this, but this "feature" has been removed as it introduced performance regressions on hand optimized code that have been very difficult to avoid in the strenght reduce phase. Best, Tobias