llvm dev - Dec 2017 - 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171201/77fee89a/attachment.html>

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> 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
> 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/9100934a/attachment.html>

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>