[Bug tree-optimization/37705] New: [graphite] Fix problems with SCoPs, that contain more than one loop

[Bug tree-optimization/37705] New: [graphite] Fix problems with SCoPs, that contain more than one loop

[grosser at gcc dot gnu dot org]

Graphite calls limit_scops() to ensure, that every SCoP contains a single
surrounding loop, as graphite - at the moment - is not able to handle SCoPs
with two outermost loops or a bb not contained in any loop.

In theory that is possible without problems, only some little bugs are in the
way.

So fix the bugs, remove limit_scops() and make theory reality.


-- 
           Summary: [graphite] Fix problems with SCoPs, that contain more
                    than one loop
           Product: gcc
           Version: 4.4.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: grosser at gcc dot gnu dot org
        ReportedBy: grosser at gcc dot gnu dot org


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

[Bug tree-optimization/37705] [graphite] Fix problems with SCoPs, that contain more than one loop

[grosser at gcc dot gnu dot org]

-- 

grosser at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
           Priority|P3                          |P4
   Last reconfirmed|0000-00-00 00:00:00         |2008-10-01 17:16:46
               date|                            |


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

[Bug tree-optimization/37705] [graphite] Fix problems with SCoPs, that contain more than one loop

[grosser at gcc dot gnu dot org]

------- Comment #1 from grosser at gcc dot gnu dot org  2008-10-16 05:20 -------
Created an attachment (id=16505)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16505&action=view)
Fix loop_affine_expr to remove limit_scops () - This is a HACK looking for
smarter solution

Problem 1:

Scalar evolution functions in loop limits and conditions have to be constant or 
affine to be allowed in a SCoP.
During SCoP detection we check this with:

if (evolution_function_is_invariant_p (scev, n)
        || evolution_function_is_affine_multivariate_p (scev, n));

in loop_affine_expr().
If this expression is true, it is allowed in a SCoP.

But e.g. the constant expr "p_1 * p_2" is allow in a SCoP, but we can not
represent it using the polyhedron model.

The matrix would be

p_1      p_2      Const
x        y        z

with x*p_1 + y*p_2 + z

There is no way to represent p_1 * p_2, so we fail in scan_tree_for_params
trying to generate the matrix.

There are two solutions:

1. This expression is representable, if we introduce a new parameter p_3 = p_1
* p_2 and calculate it before the SCoP.

2. We detect this cases and do not allow them in any SCoP.

I would like to start with solution two. Later on we can implement solution
one.

I attached a patch, that simply copies scan_tree_for_params() and returns true,
if a expression can be handled by scan_tree_for_params() otherwise false.

This works on polyhedron using -fgraphite, but seems not to be the cleanest
solution. I would prefer to keep

if (evolution_function_is_invariant_p (scev, n)
        || evolution_function_is_affine_multivariate_p (scev, n));

and add only
    && (no_multiplication_in_parameters (scev)).


-- 


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

[Bug tree-optimization/37705] [graphite] Remove limit_scops() workaround

[grosser at gcc dot gnu dot org]

-- 

grosser at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2008-10-01 17:16:46         |2008-10-16 05:33:30
               date|                            |
            Summary|[graphite] Remove           |[graphite] Remove
                   |limit_scops workaround      |limit_scops() workaround


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

[Bug tree-optimization/37705] [graphite] Remove limit_scops() workaround

[spop at gcc dot gnu dot org]

------- Comment #2 from spop at gcc dot gnu dot org  2008-10-16 13:59 -------
I prefer the second solution: if (multiplication_in_parameters (n)) then
insert a new parameter on the BB preceding the scop, and use 
force_gimple_operand to gimplify the sequence of stmts for n.  
This returns a sequence of stmts that you can insert on the src of the 
entry edge of the scop.


-- 


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

[Bug tree-optimization/37705] [graphite] Remove limit_scops() workaround

[spop at gcc dot gnu dot org]

------- Comment #3 from spop at gcc dot gnu dot org  2008-10-16 15:46 -------
Created an attachment (id=16511)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16511&action=view)
patch for solution 2

Patch as discussed at today's graphite call: detect multiplications of
parameters, then gimplify and add new parameters for these multiplication
expressions. 


-- 


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

[Bug tree-optimization/37705] [graphite] Remove limit_scops() workaround

[spop at gcc dot gnu dot org]

------- Comment #4 from spop at gcc dot gnu dot org  2008-12-11 21:13 -------
I would consider this at a very low priority right now: I'm thus marking it as
enhancement level.
If you can get a fix for this one that would be great, otherwise let's fix this
one in GCC4.5.

Sebastian


-- 

spop at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement


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

[Bug tree-optimization/37705] [graphite] Remove limit_scops() workaround

[tobi-grosser at web dot de]

------- Comment #5 from tobi-grosser at web dot de  2008-12-11 21:30 -------
Subject: Re:  [graphite] Remove limit_scops()
        workaround

On Thu, 2008-12-11 at 21:13 +0000, spop at gcc dot gnu dot org wrote:
> 
> ------- Comment #4 from spop at gcc dot gnu dot org  2008-12-11 21:13 -------
> I would consider this at a very low priority right now: I'm thus marking it as
> enhancement level.
> If you can get a fix for this one that would be great, otherwise let's fix this
> one in GCC4.5.

Actually I would like to get this one out soon. But I am afraid, that
there will show up new bugs. So lets stay fixing the current ones and
get something working.

My plan for this is:

1. Get nightly builds running
2. Get Polyhedron compiling correct and gcc bootstrapping with
-fgraphite-identity.
3. Remove limit_scops()
4. Fix the bugs that where hidden before.

See you
Tobi


-- 


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

[Bug tree-optimization/37705] [graphite] Remove limit_scops() workaround

[spop at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37705

Sebastian Pop <spop at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
                 CC|                            |spop at gcc dot gnu.org
         Resolution|---                         |FIXED

--- Comment #6 from Sebastian Pop <spop at gcc dot gnu.org> ---
Fixed in r227567.