loop canonical variables

Hello,

I need to perform the analysis of loop induction variables. However, as I understood, directly it is possible to extract only a canonical induction variable which is only one. If I have multiple induction variables with the step not one, are there any methods to extract their phi node?

int a[10];
int b[10];
for (int i = 0, j = 1; i < 10, j < 10; i++, j+=2) {
a[i] = i+1;
b[j] = j+1;
}
printf(“%d”,(b[1] + a[1]));
return (b[1] + a[1]);

this is a brief example, I want to track i and j (smth is not initialized in this code, but it doesn’t matter)

There is Loop::getCanonicalInductionVariable()

You may need to run the "-indvars" (IndVarSimplify) pass before it
returns a value. I am not sure it normalizes the step size to 1 in all
cases.

Michael

I call this function and it returns only “i” in my example. Are there any ways to return “j” also?

That would contradict it being the /canonical/ induction variable, wouldn't it?

If you look into the imlplementation of
getCanonicalInductionVariable(), it just walks the IR instructions and
checks some conditions. You can have your own implementation that,
instead of returning the first matching PHI, return all matching PHIs.
SimplifyIndVar won't try to canonicalize, though.

Michael

Hi Anastasiya,

If it fits you use case, you can consider walking the loop header and
calling getSCEV() on all of the PHI nodes in the header. This will
give you a SCEV* which should be easier to analyze than manually
inspecting PHI cycles.

Thanks!
-- Sanjoy

Great, thanks a lot!

Still, there a question:

  1. does loop analysis always find only outermost loop? I can’t make it finding all innermost ones (LoopInfo &LI = getAnalysis().getLoopInfo()). With other means it is possible,but not so convenient;

  2. is the trip count value determined only when there is one exit block (I have seen such assert in code, but maybe there are other functions, that can overcome this difficulty)? In this example I have not fully optimized version but still I can’t be sure that this will not happen even after full optimization pass:

define i32 @main() #0 {
br label %1

; :1 ; preds = %0, %4
%i.03 = phi i32 [ 0, %0 ], [ %5, %4 ]
%a.02 = phi i32 [ 0, %0 ], [ %2, %4 ]
%2 = add i32 %a.02, %i.03
%3 = icmp sgt i32 %i.03, 7
br i1 %3, label %.loopexit, label %4

; :4 ; preds = %1
%5 = add nsw i32 %i.03, 1
%6 = icmp ne i32 %5, 10
br i1 %6, label %1, label %.loopexit

.loopexit: ; preds = %4, %1
%a.1 = phi i32 [ %2, %1 ], [ %2, %4 ]
ret i32 %a.1
}

the c code

unsigned a = 0;
for (int i = 0; i != 10; i++) {
a+=i;
if (i > 7)
break;
}
return a;

of course if I will apply instcombine with indvars passes, then it will look more logical, but anyway the loop trip count here is 7 , not 10, not 0 ( the max number we can enter the loop). But it can’t be determined with the help of information from ScalarEvolution.

Hi Anastasiya,

Still, there a question:
1) does loop analysis always find only outermost loop? I can't make it
finding all innermost ones (LoopInfo &LI =
getAnalysis<LoopInfoWrapperPass>().getLoopInfo()). With other means it is
possible,but not so convenient;

LoopInfo returns the roots of the loop nest. For each llvm::Loop in LoopInfo,
Loop::getSubLoops() returns the set of loops totally contained within the
llvm::Loop.

2) is the trip count value determined only when there is one exit block (I
have seen such assert in code, but maybe there are other functions, that can
overcome this difficulty)? In this example I have not fully optimized
version but still I can't be sure that this will not happen even after full
optimization pass:

define i32 @main() #0 {
  br label %1

; <label>:1 ; preds = %0, %4
  %i.03 = phi i32 [ 0, %0 ], [ %5, %4 ]
  %a.02 = phi i32 [ 0, %0 ], [ %2, %4 ]
  %2 = add i32 %a.02, %i.03
  %3 = icmp sgt i32 %i.03, 7
  br i1 %3, label %.loopexit, label %4

; <label>:4 ; preds = %1
  %5 = add nsw i32 %i.03, 1
  %6 = icmp ne i32 %5, 10
  br i1 %6, label %1, label %.loopexit

.loopexit: ; preds = %4, %1
  %a.1 = phi i32 [ %2, %1 ], [ %2, %4 ]
  ret i32 %a.1
}

the c code

    unsigned a = 0;
    for (int i = 0; i != 10; i++) {
      a+=i;
      if (i > 7)
        break;
    }
    return a;

I think SCEV can be made smarter in this case -- can you please file a
bug? For the time being, you can consider using
getMaxBackedgeTakenCount.

-- Sanjoy