llvm dev - May 2011 - [LLVMdev] Loop transformations using LLVM

Hi

I am trying to write up a transformation for the following code where
instead of incrementing the loop variable by 1, I increment it by 2 ie.

for (i=0; i < THRES; *i++*) {
  //do something
}

gets transformed to

for (i=0; i < THRES; *i+=2*) {
  //do something
}

I am thinking of transforming the llvm  bit-code in the following way.
Iterate over the function for the original code till I get the basicBlock
for the for loop, then iterate over the instructions till I get the
increment instruction and then add the same increment instruction so that
the increment happens twice.

I am still getting familiar with the llvm infrastructure and I am not sure
if the above approach is even going to work. It'll be great if someone can
suggest a better or more concrete way of doing the above transformation ? Is
there already something similar in the source tree  that can I look up for
ideas ?

Thanks!
Malveeka
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110505/0edf031c/attachment.html>

Malveeka, 

You can use the LoopInfo analysis to find the induction variable. 

http://llvm.org/docs/doxygen/html/classllvm_1_1Loop.html#a72bbf45d2e00971f56bf8cfe4e1df01c

Cheers,
Nadav


From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On
Behalf Of Malveeka Tewari
Sent: Thursday, May 05, 2011 14:51
To: llvmdev at cs.uiuc.edu
Subject: [LLVMdev] Loop transformations using LLVM

Hi 

I am trying to write up a transformation for the following code where instead of
incrementing the loop variable by 1, I increment it by 2 ie.

for (i=0; i < THRES; i++) {
  //do something 
} 

gets transformed to 

for (i=0; i < THRES; i+=2) {
  //do something 
} 

I am thinking of transforming the llvm  bit-code in the following way.
Iterate over the function for the original code till I get the basicBlock for
the for loop, then iterate over the instructions till I get the increment
instruction and then add the same increment instruction so that the increment
happens twice. 

I am still getting familiar with the llvm infrastructure and I am not sure if
the above approach is even going to work. It'll be great if someone can
suggest a better or more concrete way of doing the above transformation ? Is
there already something similar in the source tree  that can I look up for ideas
?

Thanks!
Malveeka
---------------------------------------------------------------------
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.

On May 5, 2011, at 5:11 AM, Rotem, Nadav wrote:
> Malveeka, 
> 
> You can use the LoopInfo analysis to find the induction variable. 
> 
>
http://llvm.org/docs/doxygen/html/classllvm_1_1Loop.html#a72bbf45d2e00971f56bf8cfe4e1df01c
> 
> Cheers,
> Nadav
getCanonicalInductionVariable is a good example of finding IVs without iterating
over instructions. But you may need to generalize it a bit for your purpose.

A completely general approach to IV analysis is ScalarEvolution. You can query
the expression for a loop header phi using ScalarEvolution::getSCEV. If it
returns SCEVAddRecExpr with getLoop() == ThisLoop, then you've found an IV.
You can build a new IV by replacing the "step" with SCEVAddExpr(1 +
OrigStep). To materialize it in IR, you need to use a SCEVExpander. ...probably
more complicated than you need.

-Andy

> 
> 
> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
cs.uiuc.edu] On Behalf Of Malveeka Tewari
> Sent: Thursday, May 05, 2011 14:51
> To: llvmdev at cs.uiuc.edu
> Subject: [LLVMdev] Loop transformations using LLVM
> 
> Hi 
> 
> I am trying to write up a transformation for the following code where
instead of incrementing the loop variable by 1, I increment it by 2 ie.
> 
> for (i=0; i < THRES; i++) {
>   //do something 
> } 
> 
> gets transformed to 
> 
> for (i=0; i < THRES; i+=2) {
>   //do something 
> } 
> 
> I am thinking of transforming the llvm  bit-code in the following way.
> Iterate over the function for the original code till I get the basicBlock
for the for loop, then iterate over the instructions till I get the increment
instruction and then add the same increment instruction so that the increment
happens twice.
> 
> I am still getting familiar with the llvm infrastructure and I am not sure
if the above approach is even going to work. It'll be great if someone can
suggest a better or more concrete way of doing the above transformation ? Is
there already something similar in the source tree  that can I look up for ideas
?
> 
> Thanks!
> Malveeka
> ---------------------------------------------------------------------
> Intel Israel (74) Limited
> 
> This e-mail and any attachments may contain confidential material for
> the sole use of the intended recipient(s). Any review or distribution
> by others is strictly prohibited. If you are not the intended
> recipient, please contact the sender and delete all copies.
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev