[Bug tree-optimization/43934] New: LIM should handle PHI nodes

[Bug tree-optimization/43934] New: LIM should handle PHI nodes

[rguenth at gcc dot gnu dot org]

Currently LIM does not handle moving invariant PHIs.

void bar (int);
void foo (int n, int m)
{
  unsigned i;
  for (i = 0; i < n; ++i)
    {
      int x;
      if (m < 0)
        x = 1;
      else
        x = m;
      bar (x);
    }
}

we should move the computation of x out of the loop.

For simple cases like this, a single invariant PHI node controlled by
the predicate

  if (m_6(D) < 0)
    goto <bb 4>;
  else
    goto <bb 9>;

<bb 9>:
  goto <bb 5>;

<bb 4>:

<bb 5>:
  # x_2 = PHI <1(4), m_6(D)(9)>

we can hoist x_2 by inserting an assignment from a COND_EXPR.  Multiple
PHI nodes and/or not trivially empty intermediate blocks should be moved
as CFG pieces instead.

Thus hacking the simple case into LIM is the same as converting such
CFG pieces to COND_EXPRs similar to what if-conversion for the vectorizer
does.


-- 
           Summary: LIM should handle PHI nodes
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: rguenth at gcc dot gnu dot org


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

[Bug tree-optimization/43934] LIM should handle PHI nodes

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2010-04-29 14:16 -------
I have a patch.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rguenth at gcc dot gnu dot
                   |dot org                     |org
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2010-04-29 14:16:00
               date|                            |


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

[Bug tree-optimization/43934] LIM should handle PHI nodes

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2010-05-06 09:04 -------
Subject: Bug 43934

Author: rguenth
Date: Thu May  6 09:04:00 2010
New Revision: 159099

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=159099
Log:
2010-05-06  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/43934
        * tree-ssa-loop-im.c (movement_possibility): Handle PHI nodes.
        (stmt_cost): Likewise.
        (extract_true_false_args_from_phi): New helper.
        (determine_max_movement): For PHI nodes verify we can hoist them
        and compute their cost.
        (determine_invariantness_stmt): Handle PHI nodes.
        (move_computations_stmt): Likewise.  Hoist PHI nodes in
        if-converted form using COND_EXPRs.
        (move_computations): Return TODO_cleanup_cfg if we hoisted PHI
        nodes.
        (tree_ssa_lim): Likewise.
        * tree-flow.h (tree_ssa_lim): Adjust prototype.
        * tree-ssa-loop.c (tree_ssa_loop_im): Return todo.

        * gcc.dg/tree-ssa/ssa-lim-9.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-lim-9.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-flow.h
    trunk/gcc/tree-ssa-loop-im.c
    trunk/gcc/tree-ssa-loop.c


-- 


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

[Bug tree-optimization/43934] LIM should handle PHI nodes

[rguenth at gcc dot gnu dot org]

------- Comment #3 from rguenth at gcc dot gnu dot org  2010-05-06 13:56 -------
Fixed.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.6.0


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