thr3ads.net - llvm dev - [llvm-dev] Can't get an induction variable by getInductionVariable API [Oct 2020]

If this information is useful, please help other people find it:
Share via:

ZIN MOON via llvm-dev

2020-Oct-23 08:23 UTC

[llvm-dev] Can't get an induction variable by getInductionVariable API

Dear All

I have a question about the getInductionVariable API.
I was trying to get an induction variable (indvar) in the code below using
the getInductionVariable API (LoopInfo class).

*C file*
void test(int val) {
  int sum = 0, i = 0;
  for (i = 0; i < val; i++) {
      sum += i;
  }
}

*IR (with mem2reg pass)*
; Function Attrs: nounwind
define dso_local void @test(i32 %0) #0 {
  br label %2
2:                                                ; preds = %6, %1
  %.01 = phi i32 [ 0, %1 ], [ %5, %6 ]
  %.0 = phi i32 [ 0, %1 ], [ %7, %6 ]
  %3 = icmp slt i32 %.0, %0
  br i1 %3, label %4, label %8 <- *Why don't check this BranchInst ?*
4:                                                ; preds = %2
  %5 = add nsw i32 %.01, %.0
  br label %6
6:                                                ; preds = %4
  %7 = add nsw i32 %.0, 1
 * br label %2  <- checked it whether isCondition by getLatchCmpInst
API(called by getInductionVariable API)*
8:                                                ; preds = %2
  ret void
}

Then I got null (no indvar) because BranchInst's number of operands was
less than 2.(red block).

A CmpInst(compare with induction variable) is contained in the header of
the loop.
But the getInductionVariable API checks only in a latch block(contains a
branch back to the header of the loop)
is there a missing case that contains CmpInst in the header?

And if I use the getCanonicalInductionVariable API, I can get the variable
'i'(%. 01) as an indvar.

I checked the code implementing getInductionVariable and
getCanonicalInductionVariable.
It seems that indvar and canonical indvar differ only in the starting
number (0 or none).
Why not use the same way to detect the indvar between getInductionVariable
and getCanonicalInductionVariable.

BR
ZIN
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20201023/c5989609/attachment.html>

Florian Hahn via llvm-dev

2020-Oct-23 08:49 UTC

head link

[llvm-dev] Can't get an induction variable by getInductionVariable API

Hi,
> On Oct 23, 2020, at 09:23, ZIN MOON via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Dear All
> 
> I have a question about the getInductionVariable API.
> I was trying to get an induction variable (indvar) in the code below using
the getInductionVariable API (LoopInfo class).
> 
> C file
> void test(int val) {
>   int sum = 0, i = 0;
>   for (i = 0; i < val; i++) {
>       sum += i;
>   }
> }
> 
> IR (with mem2reg pass)
> ; Function Attrs: nounwind
> define dso_local void @test(i32 %0) #0 {
>   br label %2
> 2:                                                ; preds = %6, %1
>   %.01 = phi i32 [ 0, %1 ], [ %5, %6 ]
>   %.0 = phi i32 [ 0, %1 ], [ %7, %6 ]
>   %3 = icmp slt i32 %.0, %0
>   br i1 %3, label %4, label %8 <- Why don't check this BranchInst ?
> 4:                                                ; preds = %2
>   %5 = add nsw i32 %.01, %.0
>   br label %6
> 6:                                                ; preds = %4
>   %7 = add nsw i32 %.0, 1
>   br label %2  <- checked it whether isCondition by getLatchCmpInst
API(called by getInductionVariable API)
> 8:                                                ; preds = %2
>   ret void
> }
> 
> Then I got null (no indvar) because BranchInst's number of operands was
less than 2.(red block).
> 
> A CmpInst(compare with induction variable) is contained in the header of
the loop.
> But the getInductionVariable API checks only in a latch block(contains a
branch back to the header of the loop)
> is there a missing case that contains CmpInst in the header?
> 
> And if I use the getCanonicalInductionVariable API, I can get the variable
'i'(%. 01) as an indvar.
> 
> I checked the code implementing getInductionVariable and
getCanonicalInductionVariable.
> It seems that indvar and canonical indvar differ only in the starting
number (0 or none).
> Why not use the same way to detect the indvar between getInductionVariable
and getCanonicalInductionVariable.

Most loop transformations and utilities expect to work on ‘rotated’ loops
(https://www.llvm.org/docs/LoopTerminology.html#rotated-loops). It is probably
best to also run `-loop-rotate` before transforming analyzing/transforming the
loop.

Note that the documentation for getInductionVariable explicitly requires the
induction variable to determine the condition of the branch in the loop latch
(http://llvm.org/doxygen/classllvm_1_1Loop.html#ab05e97728516fbeeaa9426496257c800)
and uses InductionDescriptor::isInductionPHI to detect induction PHIs (plus some
other checks). There’s also isAuxiliaryInductionVariable, which does not have
the latch branch requirement or you can use InductionDescriptor directly.

Cheers,
Florian
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20201023/84cada57/attachment.html>

ZIN MOON via llvm-dev

2020-Oct-23 09:57 UTC

head link

[llvm-dev] Can't get an induction variable by getInductionVariable API

Thanks, I'll check it out.

2020년 10월 23일 (금) 오후 5:49, Florian Hahn <florian_hahn at apple.com>님이 작성:
> Hi,
>
> On Oct 23, 2020, at 09:23, ZIN MOON via llvm-dev <llvm-dev at
lists.llvm.org>
> wrote:
>
> Dear All
>
> I have a question about the getInductionVariable API.
> I was trying to get an induction variable (indvar) in the code below using
> the getInductionVariable API (LoopInfo class).
>
> *C file*
> void test(int val) {
>   int sum = 0, i = 0;
>   for (i = 0; i < val; i++) {
>       sum += i;
>   }
> }
>
> *IR (with mem2reg pass)*
> ; Function Attrs: nounwind
> define dso_local void @test(i32 %0) #0 {
>   br label %2
> 2:                                                ; preds = %6, %1
>   %.01 = phi i32 [ 0, %1 ], [ %5, %6 ]
>   %.0 = phi i32 [ 0, %1 ], [ %7, %6 ]
>   %3 = icmp slt i32 %.0, %0
>   br i1 %3, label %4, label %8 <- *Why don't check this BranchInst
?*
> 4:                                                ; preds = %2
>   %5 = add nsw i32 %.01, %.0
>   br label %6
> 6:                                                ; preds = %4
>   %7 = add nsw i32 %.0, 1
>  * br label %2  <- checked it whether isCondition by getLatchCmpInst
> API(called by getInductionVariable API)*
> 8:                                                ; preds = %2
>   ret void
> }
>
> Then I got null (no indvar) because BranchInst's number of operands was
> less than 2.(red block).
>
> A CmpInst(compare with induction variable) is contained in the header of
> the loop.
> But the getInductionVariable API checks only in a latch block(contains a
> branch back to the header of the loop)
> is there a missing case that contains CmpInst in the header?
>
> And if I use the getCanonicalInductionVariable API, I can get the variable
> 'i'(%. 01) as an indvar.
>
> I checked the code implementing getInductionVariable and
> getCanonicalInductionVariable.
> It seems that indvar and canonical indvar differ only in the starting
> number (0 or none).
> Why not use the same way to detect the indvar between getInductionVariable
> and getCanonicalInductionVariable.
>
>
>
> Most loop transformations and utilities expect to work on ‘rotated’ loops (
> https://www.llvm.org/docs/LoopTerminology.html#rotated-loops). It is
> probably best to also run `-loop-rotate` before transforming
> analyzing/transforming the loop.
>
> Note that the documentation for getInductionVariable explicitly requires
> the induction variable to determine the condition of the branch in the loop
> latch (
>
http://llvm.org/doxygen/classllvm_1_1Loop.html#ab05e97728516fbeeaa9426496257c800)
> and uses InductionDescriptor::isInductionPHI to detect induction PHIs (plus
> some other checks). There’s also isAuxiliaryInductionVariable, which does
> not have the latch branch requirement or you can use InductionDescriptor
> directly.
>
> Cheers,
> Florian
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20201023/27adda37/attachment.html>

Philip Reames via llvm-dev

2020-Oct-24 17:06 UTC

head link

[llvm-dev] Can't get an induction variable by getInductionVariable API

If this particular API is too restrictive for your use case, you can 
also consider the following two approaches:

 1. Walk the phi nodes in the header, and ask SCEV for the node
    representing each.  For any which is an AddRec within the current
    loop, you've found an induction variable.
 2. If you're using IVs to analyze loop behavior, consider using the
    exit count APIs instead.  They handle all the complexities of multi
    exit loops which can be tedious to get right by hand.

Philip

p.s. The point Florian made about rotated loops is also spot on.

On 10/23/2020 1:23 AM, ZIN MOON via llvm-dev wrote:> Dear All
>
> I have a question about the getInductionVariable API.
> I was trying to get an induction variable (indvar) in the code below 
> using the getInductionVariable API (LoopInfo class).
>
> *C file*
> void test(int val) {
>   int sum = 0, i = 0;
>   for (i = 0; i < val; i++) {
>       sum += i;
>   }
> }
>
> *IR (with mem2reg pass)*
> ; Function Attrs: nounwind
> define dso_local void @test(i32 %0) #0 {
>   br label %2
> 2:                                                ; preds = %6, %1
>   %.01 = phi i32 [ 0, %1 ], [ %5, %6 ]
>   %.0 = phi i32 [ 0, %1 ], [ %7, %6 ]
>   %3 = icmp slt i32 %.0, %0
>   br i1 %3, label %4, label %8 <- *Why don't check this BranchInst
?*
> 4:                                                ; preds = %2
>   %5 = add nsw i32 %.01, %.0
>   br label %6
> 6:                                                ; preds = %4
>   %7 = add nsw i32 %.0, 1
> *br label %2  <- checked it whether isCondition by getLatchCmpInst 
> API(called by getInductionVariable API)*
> 8:                                                ; preds = %2
>   ret void
> }
>
> Then I got null (no indvar) because BranchInst's number of operands 
> was less than 2.(red block).
>
> A CmpInst(compare with induction variable) is contained in the header 
> of the loop.
> But the getInductionVariable API checks only in a latch block(contains 
> a branch back to the header of the loop)
> is there a missing case that contains CmpInst in the header?
>
> And if I use the getCanonicalInductionVariable API, I can get the 
> variable 'i'(%. 01) as an indvar.
>
> I checked the code implementing getInductionVariable and 
> getCanonicalInductionVariable.
> It seems that indvar and canonical indvar differ only in the starting 
> number (0 or none).
> Why not use the same way to detect the indvar between 
> getInductionVariable and getCanonicalInductionVariable.
>
> BR
> ZIN
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://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/20201024/4eceb1e6/attachment.html>

llvm dev - Oct 2020 - Can't get an induction variable by getInductionVariable API

[llvm-dev] Can't get an induction variable by getInductionVariable API

[llvm-dev] Can't get an induction variable by getInductionVariable API

[llvm-dev] Can't get an induction variable by getInductionVariable API

[llvm-dev] Can't get an induction variable by getInductionVariable API