[llvm-dev] Canonicalize induction variables

[Ehsan Amiri via llvm-dev]

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>