[LLVMdev] SCEV and induction variable identification

[Paul Vario]

Hi Fellows,

    The goal is to find the induction variable for a loop, where the induction variable increments with the multiplication, division or shift operations, like this one:

sz = 8;
do {
 
  ... ...  

   sz = sz / 2;
} while (sz)

    Is SCEV capable of detecting the induction variable 'sz' in this case? The code snippet I am using to solve the problem is

for each basic-block in a loop
    for each instruction J in a basic block
          if ( J is a PHINode) {
              const SCEV *S = SE->getSCEV(J);
              const SCEVAddRecExpr *SARE = dyn_cast<SCEVAddRecExpr>(S);

              if (SARE) {
                 const Loop *CurLoop = SARE->getLoop();
            
                 if (CurLoop == L) {
                     /* => J is the induction variable*/
                }
              }
            }
 
     SCEVAddRecExpr is said to be able to handle any polynomial recurrence on the trip count of the loop. However, for my sample program, The dyn_cast result SARE is always NULL ... hence getting me to think that SCEV is not capable of handling cases like i=i/2, which contradicts what was said in the LLVM API documentation. Thanks.

Best,

Paul

[Andrew Trick]

Hi Paul,

SCEV can reason about unsigned division. But it will only be able to express your phi as an AddRec expression if it is a recurrence in which each iteration *adds* some expression to the previous value. The AddRec is linear if it adds a constant each time, and polynomial if it adds another AddRec each time.

I don’t think you really care about the AddRec and just want to find the induction variables. You could get the SCEV expression for the phi’s backedge value, and see if it is based on the phi itself. e.g. in this case (%phi /u 2). But you probably don’t need SCEV as it’s pretty easy to walk to use-def chain looking for a cycle including your phi.

-Andy
_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

[Dvorkin Dmitry]

Dear developers!

Is MCJIT available on ARMv5 in any version of LLVM? If no, do you have
plan to support it in near future?
I'm trying to make mcjit work in my arm development kit
(armv5te-linux-gnueabi) using this manual:
http://blog.llvm.org/2013/07/using-mcjit-with-kaleidoscope-tutorial.html

patched Kaleidoscope-Ch4 outputs:
ready> Could not create ExecutionEngine: Interpreter has not been linked in.

"/lli -use-mcjit ./hello.ll" outputs:
/lli: error creating EE: No available targets are compatible with this
triple, see -version for the available targets.

"/lli --version"
LLVM (http://llvm.org/):
LLVM version 3.4svn
DEBUG build.
Built Apr 23 2014 (17:27:27).
Default target: armv5te-linux-gnueabi
Host CPU: arm926ej-s

How LLVM was built:
CC="/home/dv/workspace/oe_core9g25.llvm.0/poky/build-atmel/tmp/sysroots/x86_64-linux/usr/bin/armv5te-poky-linux-gnueabi/arm-poky-linux-gnueabi-gcc"
CXX="/home/dv/workspace/oe_core9g25.llvm.0/poky/build-atmel/tmp/sysroots/x86_64-linux/usr/bin/armv5te-poky-linux-gnueabi/arm-poky-linux-gnueabi-g++"
CXX_FLAGS="-march=armv5te -marm
--sysroot=/home/dv/workspace/oe_core9g25.llvm.0/poky/build-atmel/tmp/sysroots/at91sam9x5ek
-DNDEBUG" C_FLAGS="-march=armv5te -marm
--sysroot=/home/dv/workspace/oe_core9g25.llvm.0/poky/build-atmel/tmp/sysroots/at91sam9x5ek
-DNDEBUG" cmake .. -DLLVM_REQUIRES_RTTI=ON
-DCMAKE_INSTALL_PREFIX=/opt/llvm-3.3.arm -DCMAKE_CROSSCOMPILING=True
-DLLVM_DEFAULT_TARGET_TRIPLE=armv5te-linux-gnueabi
-DLLVM_TARGET_ARCH=ARM -DLLVM_TARGETS_TO_BUILD=ARM
-DLLVM_BUILD_EXAMPLES=ON -DLLVM_TABLEGEN=/opt/llvm-3.4/bin/llvm-tblgen

[Renato Golin]

On 24 April 2014 03:37, Dvorkin Dmitry <dvo...@tibbo.com> wrote:
> Is MCJIT available on ARMv5 in any version of LLVM? If no, do you have plan
> to support it in near future?

Hi Dvorkin,

I don't remember intentionally removing support for ARMv5, but also,
we don't test it, so support could have been dropped by accident. Not
many people have interest in ARMv5 (with the last bot disappearing not
long ago), so it's hard to keep compatibility, especially with so many
changes to modern Linux systems...

> patched Kaleidoscope-Ch4 outputs:
> ready> Could not create ExecutionEngine: Interpreter has not been linked in.

Your parameters below for compiling look correct, I'd wait until
someone more experienced with MCJIT had a say.

> "/lli -use-mcjit ./hello.ll" outputs:
> /lli: error creating EE: No available targets are compatible with this
> triple, see -version for the available targets.

Does good old lli work?

cheers,
-renato