[LLVMdev] SCEV and induction variable identification

[Andrew Trick]

On Apr 22, 2014, at 10:49 AM, Paul Vario <paul.paul.mit at gmail.com> wrote:

> Hi Fellows,
> 
>     The goal is to find the induction variable for a loop, where the induction variable increments with the multiplication, division or shift operations, like this one:
> 
> sz = 8;
> do {
>   
>   ... ...   
> 
>    sz = sz / 2;
> } while (sz)
> 
>     Is SCEV capable of detecting the induction variable 'sz' in this case? The code snippet I am using to solve the problem is 
> 
> for each basic-block in a loop
>     for each instruction J in a basic block
>           if ( J is a PHINode) {
>               const SCEV *S = SE->getSCEV(J);
>               const SCEVAddRecExpr *SARE = dyn_cast<SCEVAddRecExpr>(S);
> 
>               if (SARE) {
>                  const Loop *CurLoop = SARE->getLoop();
>              
>                  if (CurLoop == L) {
>                      /* => J is the induction variable*/
>                 }
>               } 
>             }
>   
>      SCEVAddRecExpr is said to be able to handle any polynomial recurrence on the trip count of the loop. However, for my sample program, The dyn_cast result SARE is always NULL ... hence getting me to think that SCEV is not capable of handling cases like i=i/2, which contradicts what was said in the LLVM API documentation. Thanks.


Hi Paul,

SCEV can reason about unsigned division. But it will only be able to express your phi as an AddRec expression if it is a recurrence in which each iteration *adds* some expression to the previous value. The AddRec is linear if it adds a constant each time, and polynomial if it adds another AddRec each time.

I don’t think you really care about the AddRec and just want to find the induction variables. You could get the SCEV expression for the phi’s backedge value, and see if it is based on the phi itself. e.g. in this case (%phi /u 2). But you probably don’t need SCEV as it’s pretty easy to walk to use-def chain looking for a cycle including your phi.

-Andy