Using Scalar Evolution to Identify Expressions Evolving in terms of Loop induction variables

Hi,

I am using Scalar Evolution to extract access expressions (for load and store instructions) in terms of the loop induction variables.
I observe that the Scalar Evolution analysis is returning more expressions than I expect - including ones that are not defined
in terms of the loop induction variable. For instance in the following code:

for(unsigned long int bid = 0; bid < no_of_queries; bid++){

unsigned long int currNode = no_of_nodes / 2;
// process levels of the tree
for(int i = 0; i < logN; i++){

if((knodes[currNode].key) > keys[bid]){
currNode = knodes[currNode].left_id;
}
else if ((knodes[currNode].key) < keys[bid]){
currNode = knodes[currNode].right_id;
}
else{
break;
}
}
}

I expect to extract a SCEV expression for the variable keys, however, using ScalarEvolution I also get an expression

(using SE->getSCEV) for knodes. Since knodes does not evolve in terms of the loop induction variable I wasn’t expecting to receive a SCEV

expression for it. Can anyone please point out how SCEV expressions evolving in terms of the loop induction variable

can be distinguished from expressions that are not.

-Hashim
University of Illinois at Urbana-Champaign

Hi Hashim,

Scalar evolution determines evolution of scalar in terms of expression chain driving it.

Try dumping the detailed log using opt -analyze -scalar-evolution <.ll> -S , and look for LoopDispositions
corresponding to different expression which shows variance characteristics of a particular expression w.r.t
loop i.e. [computable/variant/invariant].

Thanks

Hi, Jatin,

Thanks for the response - that is helpful!

Indeed the ScalarEvolution class contains a function getLoopDisposition that returns
the disposition {variant, invariant, computable} for a given SCEV expression, and a given loop.
Considering that it takes the target loop as an argument it seems like the SCEV expressions
should be extracted at the scope of a particular loop using getSCEVAtScope(Loop *.
Thoughts?

Thanks,
Hashim