[Bug middle-end/37375] New: [graphite] Parameter detection and scev only take a surrounding loop as border

["grosser at gcc dot gnu dot org" <gcc-bugzilla at gcc dot gnu dot org>]

We detect this SCoP: 

for (i ...)
{
  foo(); // Difficult

  // ScoP entry

  for (j ...)
    B;

  a = 5 + i;

  for (k ...)
    C;

  // SCoP exit
}

To find the parameters we have to "instantiate_scev" for every bb.
"instantiate_scev" requires an argument "outermost_loop" to define,
which loop iterators are constant.

If we use (outermost_loop == j), 'i' would be a parameter for calculations
in B. If we use (outermost_loop == i), 'i' would be an loop iterator.

The only loop in this SCoP, that would contain all statements, is 'i'.
If we use (outermost_loop == i), 'i' is handled like an loop iterator.
So the scev of 'a' is {5, +, 1}_1. This is wrong, as 'i' is a parameter
in our SCoP.

But for statement a, there does not exist any other loop, we could use as
outermost loop.

For C we could use (outermost_loop == k). If C uses 'a' in its scev functions,
'a' will remain a parameter in the scev of 'C'. That is wrong, as 'a' is no
parameter of this SCoP, but is calculated.

A possible solution would be to extend the scev framework.
Instead of outermost_loop we could use:

- "outermost_loop_depth" to define the minimal depth, until loop iterators are
variable. 
With (outermost_loop_depth == 2) loops 'j' and 'k' change, but 'i' not.

- "scev_entry" to define the start if the scev region.


for (i ...)
{

  x = 83 + i;

  par = 52 + x;

  foo(); // Difficult

  // ScoP entry

  for (j ...)
    B;

  v = par;

  // SCoP exit
}

The evaluation of v should stop at scev_entry and evaluate to v = {par} and not
continue
to v = {135 + i}.


-- 
           Summary: [graphite] Parameter detection and scev only take a
                    surrounding loop as border
           Product: gcc
           Version: 4.4.0
            Status: UNCONFIRMED
          Keywords: FIXME
          Severity: enhancement
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: grosser at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37375