Patchwork Fix PR middle-end/39976, 200.sixtrack degradation

login
register
mail settings
Submitter William J. Schmidt
Date Dec. 1, 2011, 10:13 p.m.
Message ID <1322777636.19158.1.camel@gnopaine>
Download mbox | patch
Permalink /patch/128772/
State New
Headers show

Comments

William J. Schmidt - Dec. 1, 2011, 10:13 p.m.
Greetings,

Bug 39976 reported a degradation to 200.sixtrack wherein a hot
single-block loop is broken into two blocks.  Investigation showed the
cause to be a redundant PHI statement in the block, which the
tree-outof-ssa logic doesn't handle well.  Currently we don't have code
following the introduction of the redundant PHI that can clean it up.

This patch modifies the dom pass to include redundant PHIs in the logic
that removes redundant computations.  With the patch applied, the extra
block is no longer created and the 200.sixtrack degradation is removed.
This improves its performance by 7.3% on PowerPC64 32-bit and by 5.0% on
PowerPC64 64-bit.

Bootstrapped and regtested on powerpc64-linux.  OK for trunk?

Thanks,
Bill


2011-11-29  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

	PR middle-end/39976
	* tree-ssa-dom.c (enum expr_kind): Add EXPR_PHI.
	(struct hashable_expr): Add struct phi field.
	(initialize_hash_element): Handle phis.
	(hashable_expr_equal_p): Likewise.
	(iterative_hash_hashable_expr): Likewise.
	(print_expr_hash_elt): Likewise.
	(dom_opt_enter_block): Create equivalences from redundant phis.
	(eliminate_redundant_computations): Handle redundant phis.
Richard Guenther - Dec. 2, 2011, 9:24 a.m.
On Thu, Dec 1, 2011 at 11:13 PM, William J. Schmidt
<wschmidt@linux.vnet.ibm.com> wrote:
> Greetings,
>
> Bug 39976 reported a degradation to 200.sixtrack wherein a hot
> single-block loop is broken into two blocks.  Investigation showed the
> cause to be a redundant PHI statement in the block, which the
> tree-outof-ssa logic doesn't handle well.  Currently we don't have code
> following the introduction of the redundant PHI that can clean it up.
>
> This patch modifies the dom pass to include redundant PHIs in the logic
> that removes redundant computations.  With the patch applied, the extra
> block is no longer created and the 200.sixtrack degradation is removed.
> This improves its performance by 7.3% on PowerPC64 32-bit and by 5.0% on
> PowerPC64 64-bit.
>
> Bootstrapped and regtested on powerpc64-linux.  OK for trunk?
>
> Thanks,
> Bill
>
>
> 2011-11-29  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>
>
>        PR middle-end/39976
>        * tree-ssa-dom.c (enum expr_kind): Add EXPR_PHI.
>        (struct hashable_expr): Add struct phi field.
>        (initialize_hash_element): Handle phis.
>        (hashable_expr_equal_p): Likewise.
>        (iterative_hash_hashable_expr): Likewise.
>        (print_expr_hash_elt): Likewise.
>        (dom_opt_enter_block): Create equivalences from redundant phis.
>        (eliminate_redundant_computations): Handle redundant phis.
>
>
> Index: gcc/tree-ssa-dom.c
> ===================================================================
> --- gcc/tree-ssa-dom.c  (revision 181501)
> +++ gcc/tree-ssa-dom.c  (working copy)
> @@ -52,7 +52,8 @@ enum expr_kind
>   EXPR_UNARY,
>   EXPR_BINARY,
>   EXPR_TERNARY,
> -  EXPR_CALL
> +  EXPR_CALL,
> +  EXPR_PHI
>  };
>
>  struct hashable_expr
> @@ -65,6 +66,7 @@ struct hashable_expr
>     struct { enum tree_code op;  tree opnd0, opnd1; } binary;
>     struct { enum tree_code op;  tree opnd0, opnd1, opnd2; } ternary;
>     struct { gimple fn_from; bool pure; size_t nargs; tree *args; } call;
> +    struct { size_t nargs; tree *args; } phi;
>   } ops;
>  };
>
> @@ -281,6 +283,19 @@ initialize_hash_element (gimple stmt, tree lhs,
>       expr->kind = EXPR_SINGLE;
>       expr->ops.single.rhs = gimple_goto_dest (stmt);
>     }
> +  else if (code == GIMPLE_PHI)
> +    {
> +      size_t nargs = gimple_phi_num_args (stmt);
> +      size_t i;
> +
> +      expr->type = TREE_TYPE (gimple_phi_result (stmt));
> +      expr->kind = EXPR_PHI;
> +      expr->ops.phi.nargs = nargs;
> +      expr->ops.phi.args = (tree *) xcalloc (nargs, sizeof (tree));
> +
> +      for (i = 0; i < nargs; i++)
> +        expr->ops.phi.args[i] = gimple_phi_arg_def (stmt, i);
> +    }
>   else
>     gcc_unreachable ();
>
> @@ -439,6 +454,21 @@ hashable_expr_equal_p (const struct hashable_expr
>         return true;
>       }
>
> +    case EXPR_PHI:
> +      {
> +        size_t i;
> +
> +        if (expr0->ops.phi.nargs !=  expr1->ops.phi.nargs)
> +          return false;
> +
> +        for (i = 0; i < expr0->ops.phi.nargs; i++)
> +          if (! operand_equal_p (expr0->ops.phi.args[i],
> +                                 expr1->ops.phi.args[i], 0))
> +            return false;
> +
> +        return true;
> +      }
> +
>     default:
>       gcc_unreachable ();
>     }
> @@ -516,6 +546,15 @@ iterative_hash_hashable_expr (const struct hashabl
>       }
>       break;
>
> +    case EXPR_PHI:
> +      {
> +        size_t i;
> +
> +        for (i = 0; i < expr->ops.phi.nargs; i++)
> +          val = iterative_hash_expr (expr->ops.phi.args[i], val);
> +      }
> +      break;
> +
>     default:
>       gcc_unreachable ();
>     }
> @@ -588,6 +627,22 @@ print_expr_hash_elt (FILE * stream, const struct e
>           fprintf (stream, ")");
>         }
>         break;
> +
> +      case EXPR_PHI:
> +        {
> +          size_t i;
> +          size_t nargs = element->expr.ops.phi.nargs;
> +
> +          fprintf (stream, "PHI <");
> +          for (i = 0; i < nargs; i++)
> +            {
> +              print_generic_expr (stream, element->expr.ops.phi.args[i], 0);
> +              if (i + 1 < nargs)
> +                fprintf (stream, ", ");
> +            }
> +          fprintf (stream, ">");
> +        }
> +        break;
>     }
>   fprintf (stream, "\n");
>
> @@ -1688,6 +1743,10 @@ dom_opt_enter_block (struct dom_walk_data *walk_da
>   /* PHI nodes can create equivalences too.  */
>   record_equivalences_from_phis (bb);
>
> +  /* Create equivalences from redundant PHIs.  */
> +  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> +    eliminate_redundant_computations (&gsi);
> +
>   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
>     optimize_stmt (bb, gsi);
>
> @@ -1818,13 +1877,27 @@ eliminate_redundant_computations (gimple_stmt_iter
>  {
>   tree expr_type;
>   tree cached_lhs;
> +  tree def;
>   bool insert = true;
>   bool assigns_var_p = false;
> +  size_t i;
>
>   gimple stmt = gsi_stmt (*gsi);
>
> -  tree def = gimple_get_lhs (stmt);
> +  /* If this is a PHI, we only want to consider it if all of its
> +     arguments are SSA names (which are known to be defined in a
> +     single place).  This avoids errors when dealing with if-temps,
> +     for example.  */
> +  if (gimple_code (stmt) == GIMPLE_PHI)
> +    for (i = 0; i < gimple_phi_num_args (stmt); i++)
> +      if (TREE_CODE (gimple_phi_arg_def (stmt, i)) != SSA_NAME)
> +       return;

Can you elaborate on this?  Why are for example constants not ok
(which are the only things besides SSA names that should occur
here)?

Thanks,
Richard.

>
> +  if (gimple_code (stmt) == GIMPLE_PHI)
> +    def = gimple_phi_result (stmt);
> +  else
> +    def = gimple_get_lhs (stmt);
> +
>   /* Certain expressions on the RHS can be optimized away, but can not
>      themselves be entered into the hash tables.  */
>   if (! def
> @@ -1857,6 +1930,16 @@ eliminate_redundant_computations (gimple_stmt_iter
>     }
>   else if (gimple_code (stmt) == GIMPLE_SWITCH)
>     expr_type = TREE_TYPE (gimple_switch_index (stmt));
> +  else if (gimple_code (stmt) == GIMPLE_PHI)
> +    /* We can't propagate into a phi, so the logic below doesn't apply.
> +       Instead record an equivalence between the cached LHS and the
> +       PHI result of this statement.  This should be sufficient to
> +       kill the redundant phi.  */
> +    {
> +      if (def && cached_lhs)
> +       record_const_or_copy (def, cached_lhs);
> +      return;
> +    }
>   else
>     gcc_unreachable ();
>
> @@ -2299,8 +2382,11 @@ lookup_avail_expr (gimple stmt, bool insert)
>   tree temp;
>   struct expr_hash_elt element;
>
> -  /* Get LHS of assignment or call, else NULL_TREE.  */
> -  lhs = gimple_get_lhs (stmt);
> +  /* Get LHS of phi, assignment, or call; else NULL_TREE.  */
> +  if (gimple_code (stmt) == GIMPLE_PHI)
> +    lhs = gimple_phi_result (stmt);
> +  else
> +    lhs = gimple_get_lhs (stmt);
>
>   initialize_hash_element (stmt, lhs, &element);
>
>
>
William J. Schmidt - Dec. 2, 2011, 1:35 p.m.
On Fri, 2011-12-02 at 10:24 +0100, Richard Guenther wrote:
> On Thu, Dec 1, 2011 at 11:13 PM, William J. Schmidt
> <wschmidt@linux.vnet.ibm.com> wrote:
> > Greetings,
> >
> > Bug 39976 reported a degradation to 200.sixtrack wherein a hot
> > single-block loop is broken into two blocks.  Investigation showed the
> > cause to be a redundant PHI statement in the block, which the
> > tree-outof-ssa logic doesn't handle well.  Currently we don't have code
> > following the introduction of the redundant PHI that can clean it up.
> >
> > This patch modifies the dom pass to include redundant PHIs in the logic
> > that removes redundant computations.  With the patch applied, the extra
> > block is no longer created and the 200.sixtrack degradation is removed.
> > This improves its performance by 7.3% on PowerPC64 32-bit and by 5.0% on
> > PowerPC64 64-bit.
> >
> > Bootstrapped and regtested on powerpc64-linux.  OK for trunk?
> >
> > Thanks,
> > Bill
> >
> >
> > 2011-11-29  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>
> >
> >        PR middle-end/39976
> >        * tree-ssa-dom.c (enum expr_kind): Add EXPR_PHI.
> >        (struct hashable_expr): Add struct phi field.
> >        (initialize_hash_element): Handle phis.
> >        (hashable_expr_equal_p): Likewise.
> >        (iterative_hash_hashable_expr): Likewise.
> >        (print_expr_hash_elt): Likewise.
> >        (dom_opt_enter_block): Create equivalences from redundant phis.
> >        (eliminate_redundant_computations): Handle redundant phis.
> >
> >
> > Index: gcc/tree-ssa-dom.c
> > ===================================================================
> > --- gcc/tree-ssa-dom.c  (revision 181501)
> > +++ gcc/tree-ssa-dom.c  (working copy)
> > @@ -52,7 +52,8 @@ enum expr_kind
> >   EXPR_UNARY,
> >   EXPR_BINARY,
> >   EXPR_TERNARY,
> > -  EXPR_CALL
> > +  EXPR_CALL,
> > +  EXPR_PHI
> >  };
> >
> >  struct hashable_expr
> > @@ -65,6 +66,7 @@ struct hashable_expr
> >     struct { enum tree_code op;  tree opnd0, opnd1; } binary;
> >     struct { enum tree_code op;  tree opnd0, opnd1, opnd2; } ternary;
> >     struct { gimple fn_from; bool pure; size_t nargs; tree *args; } call;
> > +    struct { size_t nargs; tree *args; } phi;
> >   } ops;
> >  };
> >
> > @@ -281,6 +283,19 @@ initialize_hash_element (gimple stmt, tree lhs,
> >       expr->kind = EXPR_SINGLE;
> >       expr->ops.single.rhs = gimple_goto_dest (stmt);
> >     }
> > +  else if (code == GIMPLE_PHI)
> > +    {
> > +      size_t nargs = gimple_phi_num_args (stmt);
> > +      size_t i;
> > +
> > +      expr->type = TREE_TYPE (gimple_phi_result (stmt));
> > +      expr->kind = EXPR_PHI;
> > +      expr->ops.phi.nargs = nargs;
> > +      expr->ops.phi.args = (tree *) xcalloc (nargs, sizeof (tree));
> > +
> > +      for (i = 0; i < nargs; i++)
> > +        expr->ops.phi.args[i] = gimple_phi_arg_def (stmt, i);
> > +    }
> >   else
> >     gcc_unreachable ();
> >
> > @@ -439,6 +454,21 @@ hashable_expr_equal_p (const struct hashable_expr
> >         return true;
> >       }
> >
> > +    case EXPR_PHI:
> > +      {
> > +        size_t i;
> > +
> > +        if (expr0->ops.phi.nargs !=  expr1->ops.phi.nargs)
> > +          return false;
> > +
> > +        for (i = 0; i < expr0->ops.phi.nargs; i++)
> > +          if (! operand_equal_p (expr0->ops.phi.args[i],
> > +                                 expr1->ops.phi.args[i], 0))
> > +            return false;
> > +
> > +        return true;
> > +      }
> > +
> >     default:
> >       gcc_unreachable ();
> >     }
> > @@ -516,6 +546,15 @@ iterative_hash_hashable_expr (const struct hashabl
> >       }
> >       break;
> >
> > +    case EXPR_PHI:
> > +      {
> > +        size_t i;
> > +
> > +        for (i = 0; i < expr->ops.phi.nargs; i++)
> > +          val = iterative_hash_expr (expr->ops.phi.args[i], val);
> > +      }
> > +      break;
> > +
> >     default:
> >       gcc_unreachable ();
> >     }
> > @@ -588,6 +627,22 @@ print_expr_hash_elt (FILE * stream, const struct e
> >           fprintf (stream, ")");
> >         }
> >         break;
> > +
> > +      case EXPR_PHI:
> > +        {
> > +          size_t i;
> > +          size_t nargs = element->expr.ops.phi.nargs;
> > +
> > +          fprintf (stream, "PHI <");
> > +          for (i = 0; i < nargs; i++)
> > +            {
> > +              print_generic_expr (stream, element->expr.ops.phi.args[i], 0);
> > +              if (i + 1 < nargs)
> > +                fprintf (stream, ", ");
> > +            }
> > +          fprintf (stream, ">");
> > +        }
> > +        break;
> >     }
> >   fprintf (stream, "\n");
> >
> > @@ -1688,6 +1743,10 @@ dom_opt_enter_block (struct dom_walk_data *walk_da
> >   /* PHI nodes can create equivalences too.  */
> >   record_equivalences_from_phis (bb);
> >
> > +  /* Create equivalences from redundant PHIs.  */
> > +  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> > +    eliminate_redundant_computations (&gsi);
> > +
> >   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> >     optimize_stmt (bb, gsi);
> >
> > @@ -1818,13 +1877,27 @@ eliminate_redundant_computations (gimple_stmt_iter
> >  {
> >   tree expr_type;
> >   tree cached_lhs;
> > +  tree def;
> >   bool insert = true;
> >   bool assigns_var_p = false;
> > +  size_t i;
> >
> >   gimple stmt = gsi_stmt (*gsi);
> >
> > -  tree def = gimple_get_lhs (stmt);
> > +  /* If this is a PHI, we only want to consider it if all of its
> > +     arguments are SSA names (which are known to be defined in a
> > +     single place).  This avoids errors when dealing with if-temps,
> > +     for example.  */
> > +  if (gimple_code (stmt) == GIMPLE_PHI)
> > +    for (i = 0; i < gimple_phi_num_args (stmt); i++)
> > +      if (TREE_CODE (gimple_phi_arg_def (stmt, i)) != SSA_NAME)
> > +       return;
> 
> Can you elaborate on this?  Why are for example constants not ok
> (which are the only things besides SSA names that should occur
> here)?

I ran into a bootstrap problem in gengtype.c without this that took me a
while to track down.  Control flow was like this:

        10
       / |
      11 |
       \ |
        12
       / |
      13 |
       \ |
        14
       
Blocks 12 and 14 contained iftmp PHI statements of constants that looked
identical, but the constants were "defined" in different blocks.  Blocks
11 and 13 were empty.

In block 12:

	iftmp.132_1 = PHI<", "(10), ""(11)>;

In block 14:

	iftmp.133_7 = PHI<", "(12), ""(13)>;

These kinds of PHIs are redundant when in the same block with the same
predecessors, but aren't redundant in this situation (they effectively
depend upon comparisons in blocks 10 and 12).  The constants don't have
the "defined-once" property.  Without the extra check, the last
statement became a copy "iftmp.133_7 = iftmp.132_1", which was
incorrect.

The alternative would be to add some extra logic to avoid the copy
replacement when constants are involved and the PHIs aren't in the same
block, but I wasn't sure that was worth messing with the rest of the
machinery.  Thoughts?

Thanks,
Bill

> 
> Thanks,
> Richard.
> 
> >
> > +  if (gimple_code (stmt) == GIMPLE_PHI)
> > +    def = gimple_phi_result (stmt);
> > +  else
> > +    def = gimple_get_lhs (stmt);
> > +
> >   /* Certain expressions on the RHS can be optimized away, but can not
> >      themselves be entered into the hash tables.  */
> >   if (! def
> > @@ -1857,6 +1930,16 @@ eliminate_redundant_computations (gimple_stmt_iter
> >     }
> >   else if (gimple_code (stmt) == GIMPLE_SWITCH)
> >     expr_type = TREE_TYPE (gimple_switch_index (stmt));
> > +  else if (gimple_code (stmt) == GIMPLE_PHI)
> > +    /* We can't propagate into a phi, so the logic below doesn't apply.
> > +       Instead record an equivalence between the cached LHS and the
> > +       PHI result of this statement.  This should be sufficient to
> > +       kill the redundant phi.  */
> > +    {
> > +      if (def && cached_lhs)
> > +       record_const_or_copy (def, cached_lhs);
> > +      return;
> > +    }
> >   else
> >     gcc_unreachable ();
> >
> > @@ -2299,8 +2382,11 @@ lookup_avail_expr (gimple stmt, bool insert)
> >   tree temp;
> >   struct expr_hash_elt element;
> >
> > -  /* Get LHS of assignment or call, else NULL_TREE.  */
> > -  lhs = gimple_get_lhs (stmt);
> > +  /* Get LHS of phi, assignment, or call; else NULL_TREE.  */
> > +  if (gimple_code (stmt) == GIMPLE_PHI)
> > +    lhs = gimple_phi_result (stmt);
> > +  else
> > +    lhs = gimple_get_lhs (stmt);
> >
> >   initialize_hash_element (stmt, lhs, &element);
> >
> >
> >
>
Michael Matz - Dec. 2, 2011, 1:59 p.m.
Hi,

On Fri, 2 Dec 2011, William J. Schmidt wrote:

> > > -  tree def = gimple_get_lhs (stmt);
> > > +  /* If this is a PHI, we only want to consider it if all of its
> > > +     arguments are SSA names (which are known to be defined in a
> > > +     single place).  This avoids errors when dealing with if-temps,
> > > +     for example.  */
> > > +  if (gimple_code (stmt) == GIMPLE_PHI)
> > > +    for (i = 0; i < gimple_phi_num_args (stmt); i++)
> > > +      if (TREE_CODE (gimple_phi_arg_def (stmt, i)) != SSA_NAME)
> > > +       return;
> > 
> > Can you elaborate on this?  Why are for example constants not ok
> > (which are the only things besides SSA names that should occur
> > here)?
> 
> I ran into a bootstrap problem in gengtype.c without this that took me a
> while to track down.  Control flow was like this:
> 
>         10
>        / |
>       11 |
>        \ |
>         12
>        / |
>       13 |
>        \ |
>         14
>        
> Blocks 12 and 14 contained iftmp PHI statements of constants that looked
> identical, but the constants were "defined" in different blocks.  Blocks
> 11 and 13 were empty.
> 
> In block 12:
> 
> 	iftmp.132_1 = PHI<", "(10), ""(11)>;
> 
> In block 14:
> 
> 	iftmp.133_7 = PHI<", "(12), ""(13)>;

You never can regard same-looking PHI nodes from different blocks as 
equivalent.  Checking for non-SSA-names is not sufficient, the arguments 
need to have the same control dependence.  Replace the above constants 
with SSA names to see it breaking too (assume x_2 and x_3 are defined at 
function start for instance):

bb12
       iftmp.132_1 = PHI<x_2(10), x_3(11)>;

bb14:
       iftmp.133_7 = PHI<x_2(12), x_3(13)>;

Again, if the two conditions in bb10 and bb12 are different the phi 
results will be different (x_2 vs x_3).  I'd punt and simply deal only 
with PHI nodes in the current block, i.e. don't remember any PHI states 
during the walking.


Ciao,
Michael.
William J. Schmidt - Dec. 2, 2011, 2:16 p.m.
On Fri, 2011-12-02 at 14:59 +0100, Michael Matz wrote:
> Hi,
> 
> On Fri, 2 Dec 2011, William J. Schmidt wrote:
> 
> > > > -  tree def = gimple_get_lhs (stmt);
> > > > +  /* If this is a PHI, we only want to consider it if all of its
> > > > +     arguments are SSA names (which are known to be defined in a
> > > > +     single place).  This avoids errors when dealing with if-temps,
> > > > +     for example.  */
> > > > +  if (gimple_code (stmt) == GIMPLE_PHI)
> > > > +    for (i = 0; i < gimple_phi_num_args (stmt); i++)
> > > > +      if (TREE_CODE (gimple_phi_arg_def (stmt, i)) != SSA_NAME)
> > > > +       return;
> > > 
> > > Can you elaborate on this?  Why are for example constants not ok
> > > (which are the only things besides SSA names that should occur
> > > here)?
> > 
> > I ran into a bootstrap problem in gengtype.c without this that took me a
> > while to track down.  Control flow was like this:
> > 
> >         10
> >        / |
> >       11 |
> >        \ |
> >         12
> >        / |
> >       13 |
> >        \ |
> >         14
> >        
> > Blocks 12 and 14 contained iftmp PHI statements of constants that looked
> > identical, but the constants were "defined" in different blocks.  Blocks
> > 11 and 13 were empty.
> > 
> > In block 12:
> > 
> > 	iftmp.132_1 = PHI<", "(10), ""(11)>;
> > 
> > In block 14:
> > 
> > 	iftmp.133_7 = PHI<", "(12), ""(13)>;
> 
> You never can regard same-looking PHI nodes from different blocks as 
> equivalent.  Checking for non-SSA-names is not sufficient, the arguments 
> need to have the same control dependence.  Replace the above constants 
> with SSA names to see it breaking too (assume x_2 and x_3 are defined at 
> function start for instance):
> 
> bb12
>        iftmp.132_1 = PHI<x_2(10), x_3(11)>;
> 
> bb14:
>        iftmp.133_7 = PHI<x_2(12), x_3(13)>;
> 
> Again, if the two conditions in bb10 and bb12 are different the phi 
> results will be different (x_2 vs x_3).  I'd punt and simply deal only 
> with PHI nodes in the current block, i.e. don't remember any PHI states 
> during the walking.
> 

Ah, of course, you're right.  I wasn't thinking about that properly.
I'll revisit this.

Thanks,
Bill

> 
> Ciao,
> Michael.
>

Patch

Index: gcc/tree-ssa-dom.c
===================================================================
--- gcc/tree-ssa-dom.c	(revision 181501)
+++ gcc/tree-ssa-dom.c	(working copy)
@@ -52,7 +52,8 @@  enum expr_kind
   EXPR_UNARY,
   EXPR_BINARY,
   EXPR_TERNARY,
-  EXPR_CALL
+  EXPR_CALL,
+  EXPR_PHI
 };
 
 struct hashable_expr
@@ -65,6 +66,7 @@  struct hashable_expr
     struct { enum tree_code op;  tree opnd0, opnd1; } binary;
     struct { enum tree_code op;  tree opnd0, opnd1, opnd2; } ternary;
     struct { gimple fn_from; bool pure; size_t nargs; tree *args; } call;
+    struct { size_t nargs; tree *args; } phi;
   } ops;
 };
 
@@ -281,6 +283,19 @@  initialize_hash_element (gimple stmt, tree lhs,
       expr->kind = EXPR_SINGLE;
       expr->ops.single.rhs = gimple_goto_dest (stmt);
     }
+  else if (code == GIMPLE_PHI)
+    {
+      size_t nargs = gimple_phi_num_args (stmt);
+      size_t i;
+
+      expr->type = TREE_TYPE (gimple_phi_result (stmt));
+      expr->kind = EXPR_PHI;
+      expr->ops.phi.nargs = nargs;
+      expr->ops.phi.args = (tree *) xcalloc (nargs, sizeof (tree));
+
+      for (i = 0; i < nargs; i++)
+        expr->ops.phi.args[i] = gimple_phi_arg_def (stmt, i);
+    }
   else
     gcc_unreachable ();
 
@@ -439,6 +454,21 @@  hashable_expr_equal_p (const struct hashable_expr
         return true;
       }
 
+    case EXPR_PHI:
+      {
+        size_t i;
+
+        if (expr0->ops.phi.nargs !=  expr1->ops.phi.nargs)
+          return false;
+
+        for (i = 0; i < expr0->ops.phi.nargs; i++)
+          if (! operand_equal_p (expr0->ops.phi.args[i],
+                                 expr1->ops.phi.args[i], 0))
+            return false;
+
+        return true;
+      }
+
     default:
       gcc_unreachable ();
     }
@@ -516,6 +546,15 @@  iterative_hash_hashable_expr (const struct hashabl
       }
       break;
 
+    case EXPR_PHI:
+      {
+        size_t i;
+
+        for (i = 0; i < expr->ops.phi.nargs; i++)
+          val = iterative_hash_expr (expr->ops.phi.args[i], val);
+      }
+      break;
+
     default:
       gcc_unreachable ();
     }
@@ -588,6 +627,22 @@  print_expr_hash_elt (FILE * stream, const struct e
           fprintf (stream, ")");
         }
         break;
+
+      case EXPR_PHI:
+        {
+          size_t i;
+          size_t nargs = element->expr.ops.phi.nargs;
+
+          fprintf (stream, "PHI <");
+          for (i = 0; i < nargs; i++)
+            {
+              print_generic_expr (stream, element->expr.ops.phi.args[i], 0);
+              if (i + 1 < nargs)
+                fprintf (stream, ", ");
+            }
+          fprintf (stream, ">");
+        }
+        break;
     }
   fprintf (stream, "\n");
 
@@ -1688,6 +1743,10 @@  dom_opt_enter_block (struct dom_walk_data *walk_da
   /* PHI nodes can create equivalences too.  */
   record_equivalences_from_phis (bb);
 
+  /* Create equivalences from redundant PHIs.  */
+  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    eliminate_redundant_computations (&gsi);
+
   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     optimize_stmt (bb, gsi);
 
@@ -1818,13 +1877,27 @@  eliminate_redundant_computations (gimple_stmt_iter
 {
   tree expr_type;
   tree cached_lhs;
+  tree def;
   bool insert = true;
   bool assigns_var_p = false;
+  size_t i;
 
   gimple stmt = gsi_stmt (*gsi);
 
-  tree def = gimple_get_lhs (stmt);
+  /* If this is a PHI, we only want to consider it if all of its
+     arguments are SSA names (which are known to be defined in a
+     single place).  This avoids errors when dealing with if-temps,
+     for example.  */
+  if (gimple_code (stmt) == GIMPLE_PHI)
+    for (i = 0; i < gimple_phi_num_args (stmt); i++)
+      if (TREE_CODE (gimple_phi_arg_def (stmt, i)) != SSA_NAME)
+	return;
 
+  if (gimple_code (stmt) == GIMPLE_PHI)
+    def = gimple_phi_result (stmt);
+  else
+    def = gimple_get_lhs (stmt);
+
   /* Certain expressions on the RHS can be optimized away, but can not
      themselves be entered into the hash tables.  */
   if (! def
@@ -1857,6 +1930,16 @@  eliminate_redundant_computations (gimple_stmt_iter
     }
   else if (gimple_code (stmt) == GIMPLE_SWITCH)
     expr_type = TREE_TYPE (gimple_switch_index (stmt));
+  else if (gimple_code (stmt) == GIMPLE_PHI)
+    /* We can't propagate into a phi, so the logic below doesn't apply.
+       Instead record an equivalence between the cached LHS and the
+       PHI result of this statement.  This should be sufficient to
+       kill the redundant phi.  */
+    {
+      if (def && cached_lhs)
+	record_const_or_copy (def, cached_lhs);
+      return;
+    }
   else
     gcc_unreachable ();
 
@@ -2299,8 +2382,11 @@  lookup_avail_expr (gimple stmt, bool insert)
   tree temp;
   struct expr_hash_elt element;
 
-  /* Get LHS of assignment or call, else NULL_TREE.  */
-  lhs = gimple_get_lhs (stmt);
+  /* Get LHS of phi, assignment, or call; else NULL_TREE.  */
+  if (gimple_code (stmt) == GIMPLE_PHI)
+    lhs = gimple_phi_result (stmt);
+  else
+    lhs = gimple_get_lhs (stmt);
 
   initialize_hash_element (stmt, lhs, &element);