[Bug tree-optimization/18181] New: vectorizer: problem in the peeling mechanism in the presence of loop invariants that are used after the loop

[Bug tree-optimization/18181] New: vectorizer: problem in the peeling mechanism in the presence of loop invariants that are used after the loop

[dorit at il dot ibm dot com]

The loop peeling mechanism in the vectorizer (which is used to force alignment 
of stores - by peeling the first few iterations, and to support unknown loop 
bound - by peeling te last few iterations) does not handle correctly the case 
where a loop invariant is used after the loop; there are two problems:
- When updating ssa-names the peeling utility assumes that anything that needs 
to be considered has a phi node at the loop header (which is not the case for 
loop invariants).
- The peeling utility creats a path that did not exist before - from the loop 
prolog to the loop exit - and there is no value to assign for this variable on 
this path (as it is only defined inside the loop).

This situation should rarely occur, but it did come up in the following case 
(complete testcase attached in 
http://gcc.gnu.org/ml/gcc-patches/2004-10/msg00981.html):

for i
  for j
    a[i][j]= [i+1][j]

This is represented as follows:

outer_loop_start
	i = phi (0, i')
inner_loop_start
	j = phi (0, j')
	k = i + 1
	a[i][j] = a[k][j]
	j' = j + 1
inner_loop_end
	i' = phi (k) 

k is the invariant defined in the inner-loop and used after the inner-loop (it 
was actually moved into the inner loop by PRE...).

This problem does not show up currently because it needs Devang's dependence-
distance patch (without it the vectorizer does not attempt to vectorize this 
loop). But as soon as his patch goes in -
http://gcc.gnu.org/ml/gcc-patches/2004-10/msg01046.html, 
the problem in this testcase will show up.

A patch to solve this is in the works.

-- 
           Summary: vectorizer: problem in the peeling mechanism in the
                    presence of loop invariants that are used after the loop
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: dorit at il dot ibm dot com
        ReportedBy: dorit at il dot ibm dot com
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: powerpc-apple-darwin7.0.0
  GCC host triplet: powerpc-apple-darwin7.0.0
GCC target triplet: powerpc-apple-darwin7.0.0


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

[Bug tree-optimization/18181] vectorizer: problem in the peeling mechanism in the presence of loop invariants that are used after the loop

[dorit at il dot ibm dot com]

------- Additional Comments From dorit at il dot ibm dot com  2004-11-04 09:17 -------
Created an attachment (id=7471)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=7471&action=view)
testcase

Here's a testcase that fails on execution with current mainline snapshot (no
need for any pending patches to get this loop vectorized, and fail).

-- 


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

[Bug tree-optimization/18181] vectorizer: problem in the peeling mechanism in the presence of loop invariants that are used after the loop

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-11-04 13:43 -------
Confirmed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
           Keywords|                            |wrong-code
   Last reconfirmed|0000-00-00 00:00:00         |2004-11-04 13:43:29
               date|                            |


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

[Bug tree-optimization/18181] vectorizer: problem in the peeling mechanism in the presence of loop invariants that are used after the loop

[dorit at il dot ibm dot com]

------- Additional Comments From dorit at il dot ibm dot com  2004-11-04 14:45 -------
patch: http://gcc.gnu.org/ml/gcc-patches/2004-11/msg00283.html

-- 


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

[Bug tree-optimization/18181] vectorizer: problem in the peeling mechanism in the presence of loop invariants that are used after the loop

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2004-11-19 19:39 -------
Subject: Bug 18181

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	dorit@gcc.gnu.org	2004-11-19 19:39:40

Modified files:
	gcc            : ChangeLog tree-vectorizer.c 
	gcc/testsuite  : ChangeLog 
Added files:
	gcc/testsuite/gcc.dg/vect: vect-85.c vect-86.c vect-87.c 
	                           vect-88.c 

Log message:
	PR tree-opt/18181
	* tree-vectorizer.c (slpeel_tree_peel_loop_to_edge): Peeling scheme
	changed to suppoer uses-after-loop and to void creating flow paths
	that shouldn't exist.
	(slpeel_update_phi_nodes_for_guard): Takes additional two arguments.
	Modified to fit the new peeling scheme. Avoid quadratic behavior.
	(slpeel_add_loop_guard): Takes additional argument.
	(slpeel_verify_cfg_after_peeling): New function.
	(vect_update_ivs_after_vectorizer): Takes additional argument. Updated
	documentation. Use 'exit-bb' instead of creating 'new-bb'.
	(rename_variables_in_bb): Don't update phis for BBs out of loop, to fit
	the new peeling scheme.
	(copy_phi_nodes): Function removed. Its functionality moved to
	update_phis_for_duplicate_loop.
	(slpeel_update_phis_for_duplicate_loop): Functionality of copy_phi_nodes
	moved here. Added documentation. Modified to fit the new peeling scheme.
	(slpeel_make_loop_iterate_ntimes): Setting loop->single_exit not not
	needed - done in slpeel_tree_peel_loop_to_edge.
	(slpeel_tree_duplicate_loop_to_edge_cfg): Debug printouts compacted.
	(vect_do_peeling_for_loop_bound): Add documentation. Call
	slpeel_verify_cfg_after_peeling. Call vect_update_ivs_after_vectorizer
	with additional argument.
	(vect_do_peeling_for_alignment): Call slpeel_verify_cfg_after_peeling.
	
	(vect_finish_stmt_generation): Avoid 80 column oveflow.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.6421&r2=2.6422
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-vectorizer.c.diff?cvsroot=gcc&r1=2.34&r2=2.35
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&r1=1.4620&r2=1.4621
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/vect/vect-85.c.diff?cvsroot=gcc&r1=NONE&r2=1.1
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/vect/vect-86.c.diff?cvsroot=gcc&r1=NONE&r2=1.1
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/vect/vect-87.c.diff?cvsroot=gcc&r1=NONE&r2=1.1
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/vect/vect-88.c.diff?cvsroot=gcc&r1=NONE&r2=1.1



-- 


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

[Bug tree-optimization/18181] vectorizer: problem in the peeling mechanism in the presence of loop invariants that are used after the loop

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-11-19 20:14 -------
Fixed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.0.0


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