[llvm-dev] Using Scalar Evolution to Identify Expressions Evolving in terms of Loop induction variables

[Sharif, Hashim via llvm-dev]

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


________________________________
From: soft.devl81 at gmail.com [soft.devl81 at gmail.com] on behalf of Jatin Bhateja [jatin.bhateja at gmail.com]
Sent: Thursday, November 30, 2017 11:44 PM
To: Sharif, Hashim
Cc: llvm-dev at lists.llvm.org
Subject: Re: [llvm-dev] Using Scalar Evolution to Identify Expressions Evolving in terms of Loop induction variables

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

On Fri, Dec 1, 2017 at 10:20 AM, Sharif, Hashim via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:

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


_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://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/20171201/cc9760d6/attachment.html>