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


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;

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.

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].


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 *.