# [LLVMbugs] [Bug 5936] New: [LLVMPoly] Convert scalar evolution results to linear expression

bugzilla-daemon at cs.uiuc.edu bugzilla-daemon at cs.uiuc.edu
Mon Jan 4 13:53:09 PST 2010

```http://llvm.org/bugs/show_bug.cgi?id=5936

Summary: [LLVMPoly] Convert scalar evolution results to linear
expression
Product: libraries
Version: trunk
Platform: All
URL: http://wiki.llvm.org/Polyhedral_optimization_framework#T
oDo
OS/Version: All
Status: NEW
Severity: enhancement
Priority: P2
Component: Loop Optimizer
AssignedTo: unassignedbugs at nondot.org
ReportedBy: grosser at fim.uni-passau.de
CC: llvmbugs at cs.uiuc.edu, grosser at fim.uni-passau.de

Created an attachment (id=4003)
--> (http://llvm.org/bugs/attachment.cgi?id=4003)
A simple test file

It would be great to have a pass that takes a chain of recurrences, obtained by
calling the scalar evolution analysis for a value and converts this chain of
recurrences to a linear expression if possible.

Example:

int A[200];

int *foo(unsigned int b, unsigned int c) {
unsigned int i, j;
int x;

for (i = 0; i < 100 + 5 * b; i++)    // A
for (j = i; j < 200 + 7 * c; j++) {// B
x = i + j + 800 + b;
A[i * j] = x;
}

return A;
}

Here we could obtain the scalar evolution for every scalar value in this C
program by calling "opt -O3 -scalar-evolution -analyze test.bc" on the bytecode
of test.c.

Here are some of these chain of recurrences and what I would expect to get.
The values in <> are the virtual induction variables of the loops. They are
supposed to count the loop iterations. % values are parameters.

Loop for.body9: backedge-taken count is
scev: {(199 + (7 * %c)),+,-1}<for.cond3.preheader>
Linear expression: 199 + 7 c - <for.cond3.preheader>

scev: (-1 + %tmp34)
Linear expression: -1 + %tmp34

Or this one:
Linear expression: 800 + %b + 2 * <for.cond3.preheader> + <for.body9>

As a first draft it should be enough to print the linear expressions, if called
with "opt -analyze" for all the scevs available.

--
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

```