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

[bugzilla-daemon at cs.uiuc.edu]

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>

Loop for.cond3.preheader: backedge-taken count is
scev: (-1 + %tmp34)
Linear expression: -1 + %tmp34

Or this one:
%add15 = add i32 %indvar, %tmp17                ; <i32> [#uses=1]
  -->  {{(800 + %b),+,2}<for.cond3.preheader>,+,1}<for.body9> 
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.