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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140422/98ba8a81/attachment.html>
On Apr 22, 2014, at 10:49 AM, Paul Vario <paul.paul.mit at gmail.com> wrote:> 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.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
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