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

login
register
mail settings
Submitter William J. Schmidt
Date Dec. 2, 2011, 5:04 p.m.
Message ID <1322845466.2548.23.camel@gnopaine>
Download mbox | patch
Permalink /patch/128922/
State New
Headers show

Comments

William J. Schmidt - Dec. 2, 2011, 5:04 p.m.
Sorry for the previous brain-fart!  Here's a revised patch.

It seems like a fair amount of rip-up to avoid keeping the PHI state
around between blocks, so I just check to ensure the PHI definitions
occur in the same block before recording their equivalence.
lookup_avail_expr may return a constant when a PHI has been proven
equivalent to a constant; I skip these since there's nothing further
that needs to be done with them.

Bootstrapped and regression tested on powerpc64-linux.  Ok for trunk?

Thanks,
Bill


2011-12-02  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.
	(lookup_avail_expr): Handle phis.
Michael Matz - Dec. 2, 2011, 5:40 p.m.
Hi,

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

> It seems like a fair amount of rip-up to avoid keeping the PHI state 
> around between blocks, so I just check to ensure the PHI definitions 
> occur in the same block before recording their equivalence. 

Then you should at least mix the BB number into the hash value (and 
possibly also check it already in hashable_expr_equal_p) in order to 
reduce number of collissions.

But I wonder why it's not enough to just do a push/pop sequence on 
avail_exprs_stack around your new PHI processing in dom_opt_enter_block, 
ala

+  VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
   /* Create equivalences from redundant PHIs.  */
   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     eliminate_redundant_computations (&gsi);
+  remove_local_expressions_from_table ();

on top of your current version.  That ought to remove the added PHI 
expressions (and only them) from the hash table but retain the information 
of equality in the const_or_copies_stack.  Checking the BB wouldn't be 
required then.
 

Ciao,
Michael.
Jeff Law - Dec. 2, 2011, 5:52 p.m.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 12/02/11 10:40, Michael Matz wrote:
> Hi,
> 
> On Fri, 2 Dec 2011, William J. Schmidt wrote:
> 
>> It seems like a fair amount of rip-up to avoid keeping the PHI
>> state around between blocks, so I just check to ensure the PHI
>> definitions occur in the same block before recording their
>> equivalence.
> 
> Then you should at least mix the BB number into the hash value (and
>  possibly also check it already in hashable_expr_equal_p) in order
> to reduce number of collissions.
> 
> But I wonder why it's not enough to just do a push/pop sequence on
>  avail_exprs_stack around your new PHI processing in
> dom_opt_enter_block, ala
> 
> +  VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL); 
> /* Create equivalences from redundant PHIs.  */ for (gsi =
> gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 
> eliminate_redundant_computations (&gsi); +
> remove_local_expressions_from_table ();
> 
> on top of your current version.  That ought to remove the added PHI
>  expressions (and only them) from the hash table but retain the
> information of equality in the const_or_copies_stack.  Checking the
> BB wouldn't be required then.
Sorry, I haven't been following this thread and there isn't much
discussion about what problem we're trying to solve using DOM within
the PR.

I see a mention of creating equivalences for redundant PHIs?  Are we
just trying to determine that two PHIs are going to result in the same
value?

jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJO2RB6AAoJEBRtltQi2kC7niIIAJDgImG8IWhtIDjF7t7blUNj
uR8KCppurbvTkHgfuCSrn4hLRdRa14vZrY/FvP7pCaRmQ5KPBghu1IumXujVvb2i
bLtwZBggjox9mVnUjv5CizURAwJcmvPhJE5axTpEACrafzI+AuADNW8qQwO2MQmF
Ay3EXEPh27DbQi4E7IiytWQpuBsmFprh6Xu7nzW7YaK8zOGuGOEVdK5kDrZRPhLk
etq2AY4OISwClyXZHGhPqCsC4haxo80F8qzRVJ2c2EbxEMTu45CNm4fRNutR/pA4
Ly/d0WKs1YF4yTjMSEL6w5VTIFQNk1RyDAyh1OA/M01UAMWP8BHdr9tw01s4Bws=
=4X0z
-----END PGP SIGNATURE-----
William J. Schmidt - Dec. 2, 2011, 6:10 p.m.
On Fri, 2011-12-02 at 10:52 -0700, Jeff Law wrote:
> On 12/02/11 10:40, Michael Matz wrote:
> > Hi,
> > 
> > On Fri, 2 Dec 2011, William J. Schmidt wrote:
> > 
> >> It seems like a fair amount of rip-up to avoid keeping the PHI
> >> state around between blocks, so I just check to ensure the PHI
> >> definitions occur in the same block before recording their
> >> equivalence.
> > 
> > Then you should at least mix the BB number into the hash value (and
> >  possibly also check it already in hashable_expr_equal_p) in order
> > to reduce number of collissions.
> > 
> > But I wonder why it's not enough to just do a push/pop sequence on
> >  avail_exprs_stack around your new PHI processing in
> > dom_opt_enter_block, ala
> > 
> > +  VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL); 
> > /* Create equivalences from redundant PHIs.  */ for (gsi =
> > gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 
> > eliminate_redundant_computations (&gsi); +
> > remove_local_expressions_from_table ();
> > 
> > on top of your current version.  That ought to remove the added PHI
> >  expressions (and only them) from the hash table but retain the
> > information of equality in the const_or_copies_stack.  Checking the
> > BB wouldn't be required then.
> Sorry, I haven't been following this thread and there isn't much
> discussion about what problem we're trying to solve using DOM within
> the PR.
> 
> I see a mention of creating equivalences for redundant PHIs?  Are we
> just trying to determine that two PHIs are going to result in the same
> value?

Jeff, see comment #37 in
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39976.  The issue is that we
have two PHIs in the same block as follows:

  # prephitmp.35_322 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)>
  # prephitmp.35_225 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)>

The coalescing algorithm in tree-outof-ssa doesn't handle this well and
ends up splitting the back arc of a simple loop as a result.  I'm
creating an equivalence between prephitmp.35_322 and prephitmp.35_225 in
this case so that one PHI goes dead and is removed.  As pointed out in
the comments, this needs to be restricted to occur only in the same
block since the PHIs aren't necessarily equivalent otherwise.

Michael, you're quite right, I think using the extra marker and stack
pop should work quite well and would be more elegant and efficient.
I'll try it out.  I was initially thinking the PHI copies and existing
copies would be intermingled, but that's not the case.

Thanks,
Bill

> 
> jeff
Jeff Law - Dec. 2, 2011, 6:28 p.m.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 12/02/11 11:10, William J. Schmidt wrote:
> 
>> 
>> I see a mention of creating equivalences for redundant PHIs?  Are
>> we just trying to determine that two PHIs are going to result in
>> the same value?
> 
> Jeff, see comment #37 in 
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39976.  The issue is
> that we have two PHIs in the same block as follows:
> 
> # prephitmp.35_322 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)> 
> # prephitmp.35_225 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)>
OK.  Make sure you has the phi argument & its edge...  Simlarly the
equality comparison needs to check args & edges.  Or s/edge/edge->src/
if that's easier.

> 
> The coalescing algorithm in tree-outof-ssa doesn't handle this well
> and ends up splitting the back arc of a simple loop as a result.
> I'm creating an equivalence between prephitmp.35_322 and
> prephitmp.35_225 in this case so that one PHI goes dead and is
> removed.
Right.  I don't think I bothered with this because I didn't see it
happening and the comparison of the PHIs with each other gets
potentially expensive.


 As pointed out in
> the comments, this needs to be restricted to occur only in the
> same block since the PHIs aren't necessarily equivalent otherwise.
I must be missing something -- why is the equivalence only valid in
the same block?

Conceptually this situation isn't any different replacing the second
PHI with a copy
blah_225 = blah_322

And the equivalence is valid for the entire dominator subtree.

If you really need to create a temporary equiv, pushing the marker,
create the equiv and pop the marker when equiv dies is simple and easy.

Jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJO2RjmAAoJEBRtltQi2kC7I7YH/RTVZF6jzBpyg+68kMTZuHDH
hETg03jnqhSXhWOzBoALZwtR9iCJ/UehCCcnjQ3eV7o1AqsImLMnap+VrS6lYfI3
hYQXtdb2F770H70yY/fgEX/VDAdGlyduXfMqHl4mLw7Apz3mpvyBucqHqECHJ+xj
AtZf3duGXp3Fpvhm3PZ7wQa+Pl0qnJU3VxqU6xkGWn9A8et8U1IdYs/wnHPR/HPY
KP7oY3JWxwR6kpzNkFJM1OZ+Nn9XWGgScAp1uBXJhK2RLgIuxaLiM5wl6VAJR1Fs
EuMBnQbHELA1ugtqC26UsDCTkjDpLGgs02ID7ArySsVgmIYvXCVzEi0cdJA42V4=
=NKrB
-----END PGP SIGNATURE-----
William J. Schmidt - Dec. 2, 2011, 7:08 p.m.
On Fri, 2011-12-02 at 11:28 -0700, Jeff Law wrote:
> On 12/02/11 11:10, William J. Schmidt wrote:
> > 
> >> 
> >> I see a mention of creating equivalences for redundant PHIs?  Are
> >> we just trying to determine that two PHIs are going to result in
> >> the same value?
> > 
> > Jeff, see comment #37 in 
> > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39976.  The issue is
> > that we have two PHIs in the same block as follows:
> > 
> > # prephitmp.35_322 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)> 
> > # prephitmp.35_225 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)>
> OK.  Make sure you has the phi argument & its edge...  Simlarly the
> equality comparison needs to check args & edges.  Or s/edge/edge->src/
> if that's easier.
> 

OK, this is what I was missing.  Including edge->src->index in the hash
and equality test to get the actual origin of the arguments should allow
the PHIs to match when they're truly equivalent.  Thanks!

> > 
> > The coalescing algorithm in tree-outof-ssa doesn't handle this well
> > and ends up splitting the back arc of a simple loop as a result.
> > I'm creating an equivalence between prephitmp.35_322 and
> > prephitmp.35_225 in this case so that one PHI goes dead and is
> > removed.
> Right.  I don't think I bothered with this because I didn't see it
> happening and the comparison of the PHIs with each other gets
> potentially expensive.
>
>  As pointed out in
> > the comments, this needs to be restricted to occur only in the
> > same block since the PHIs aren't necessarily equivalent otherwise.
> I must be missing something -- why is the equivalence only valid in
> the same block?
> 
> Conceptually this situation isn't any different replacing the second
> PHI with a copy
> blah_225 = blah_322
> 
> And the equivalence is valid for the entire dominator subtree.

Yes, once the origin of the PHI arguments is correctly taken into
account, then equivalent PHIs can be eliminated within the subtree.

> 
> If you really need to create a temporary equiv, pushing the marker,
> create the equiv and pop the marker when equiv dies is simple and easy.
>
> Jeff

Much obliged,
Bill
William J. Schmidt - Dec. 2, 2011, 7:27 p.m.
On Fri, 2011-12-02 at 13:08 -0600, William J. Schmidt wrote:
> 
> On Fri, 2011-12-02 at 11:28 -0700, Jeff Law wrote:
> > On 12/02/11 11:10, William J. Schmidt wrote:
> > > 
> > >> 
> > >> I see a mention of creating equivalences for redundant PHIs?  Are
> > >> we just trying to determine that two PHIs are going to result in
> > >> the same value?
> > > 
> > > Jeff, see comment #37 in 
> > > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39976.  The issue is
> > > that we have two PHIs in the same block as follows:
> > > 
> > > # prephitmp.35_322 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)> 
> > > # prephitmp.35_225 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)>
> > OK.  Make sure you has the phi argument & its edge...  Simlarly the
> > equality comparison needs to check args & edges.  Or s/edge/edge->src/
> > if that's easier.
> > 
> 
> OK, this is what I was missing.  Including edge->src->index in the hash
> and equality test to get the actual origin of the arguments should allow
> the PHIs to match when they're truly equivalent.  Thanks!

Erm, wait.  How are PHIs in different blocks going to have the same
incoming edges?  (I was thinking of control dependence edges, but these
are just regular control flow incoming edges, right?)  So this really
isn't going to help.

> 
> > > 
> > > The coalescing algorithm in tree-outof-ssa doesn't handle this well
> > > and ends up splitting the back arc of a simple loop as a result.
> > > I'm creating an equivalence between prephitmp.35_322 and
> > > prephitmp.35_225 in this case so that one PHI goes dead and is
> > > removed.
> > Right.  I don't think I bothered with this because I didn't see it
> > happening and the comparison of the PHIs with each other gets
> > potentially expensive.
> >
> >  As pointed out in
> > > the comments, this needs to be restricted to occur only in the
> > > same block since the PHIs aren't necessarily equivalent otherwise.
> > I must be missing something -- why is the equivalence only valid in
> > the same block?
> > 
> > Conceptually this situation isn't any different replacing the second
> > PHI with a copy
> > blah_225 = blah_322
> > 
> > And the equivalence is valid for the entire dominator subtree.

If you go back a couple of posts in this thread, I have an example of
control flow where two control-equivalent blocks contain PHIs with
identical constant arguments.  But the constants are "defined" in
different blocks with different control dependence, so while the
constants are equivalent, the PHIs aren't.  I originally replaced this
with a copy as suggested, which broke things.

> 
> Yes, once the origin of the PHI arguments is correctly taken into
> account, then equivalent PHIs can be eliminated within the subtree.

...but none will be found...

> 
> > 
> > If you really need to create a temporary equiv, pushing the marker,
> > create the equiv and pop the marker when equiv dies is simple and easy.
> >

Yes, this still seems like the most promising thing to do.

> > Jeff
> 
> Much obliged,
> Bill
Jeff Law - Dec. 2, 2011, 8:46 p.m.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 12/02/11 12:27, William J. Schmidt wrote:

> 
> Erm, wait.  How are PHIs in different blocks going to have the
> same incoming edges?  (I was thinking of control dependence edges,
> but these are just regular control flow incoming edges, right?)  So
> this really isn't going to help.
They're not.  But if we find an equivalence between phi_1 and phi_2,
then we can replace every reference to phi_2 with phi_1.  This is safe
because any reference to phi_2 must be dominated by the assignment to
phi_2 which is in the same block as phi_1.

So while continuing to have the phis in the available expression table
is not useful beyond the current block, the equivalency created when a
redundant PHI is encountered is useful to keep.

I may have not made the distinction clearly in prior messages.  If
that's what your patch does, then you're golden.

Jeff

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJO2TktAAoJEBRtltQi2kC7hUsH/iWomNPVNnGw00FhLVBuiIVC
c/Tsirdu256H07v1yZBemoh65EEOiqy6gHbKV2ZgL8MADJYm4i17Ii/0CEJyXHt2
YpplJmVY905WKqs2KN/qWHXAo7YFQwAj2MRWSksi2VMlq0YBHL+OA0qVlPLcNRUK
3e92nyERJAHgNlQqBLzGpeMLw8ozs8ognVZj9L/fbRWf4Jgnh5v5oPu50n9pWshO
ipq+J5Qbovli9c8lHq6etFZ3EVCCxahnZ4FF1rxI3mVOKnL90xFPprBB1jL6qcqx
8O79yTLK6M7u3CTmnD8KoociAMWOhoe34o8PQIYEtJC5Pops1jKViEIbsOQg9s0=
=NXbN
-----END PGP SIGNATURE-----
William J. Schmidt - Dec. 2, 2011, 8:52 p.m.
On Fri, 2011-12-02 at 13:46 -0700, Jeff Law wrote:
> On 12/02/11 12:27, William J. Schmidt wrote:
> 
> > 
> > Erm, wait.  How are PHIs in different blocks going to have the
> > same incoming edges?  (I was thinking of control dependence edges,
> > but these are just regular control flow incoming edges, right?)  So
> > this really isn't going to help.
> They're not.  But if we find an equivalence between phi_1 and phi_2,
> then we can replace every reference to phi_2 with phi_1.  This is safe
> because any reference to phi_2 must be dominated by the assignment to
> phi_2 which is in the same block as phi_1.
> 
> So while continuing to have the phis in the available expression table
> is not useful beyond the current block, the equivalency created when a
> redundant PHI is encountered is useful to keep.
> 
> I may have not made the distinction clearly in prior messages.  If
> that's what your patch does, then you're golden.

Ah, yes.  This is what I'm doing.  Sorry for the confusion!  And thanks
for the clarification.

Bill

> 
> Jeff
>
Michael Matz - Dec. 5, 2011, 12:45 p.m.
Hi,

On Fri, 2 Dec 2011, Jeff Law wrote:

> So while continuing to have the phis in the available expression table 
> is not useful beyond the current block, the equivalency created when a 
> redundant PHI is encountered is useful to keep.

That's why I said to only clear the avail_exprs stack/vect not the 
const_or_copies one.


Ciao,
Michael.

Patch

Index: gcc/tree-ssa-dom.c
===================================================================
--- gcc/tree-ssa-dom.c	(revision 181928)
+++ 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,12 +1877,16 @@  eliminate_redundant_computations (gimple_stmt_iter
 {
   tree expr_type;
   tree cached_lhs;
+  tree def;
   bool insert = true;
   bool assigns_var_p = false;
 
   gimple stmt = gsi_stmt (*gsi);
 
-  tree def = gimple_get_lhs (stmt);
+  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.  */
@@ -1857,6 +1920,21 @@  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, provided they are in the same block.
+       This should be sufficient to kill the redundant phi.  */
+    {
+      if (def && cached_lhs && TREE_CODE (cached_lhs) == SSA_NAME)
+	{
+	  basic_block def_bb = gimple_bb (stmt);
+	  basic_block cached_bb = gimple_bb (SSA_NAME_DEF_STMT (cached_lhs));
+	  if (def_bb == cached_bb)
+	    record_const_or_copy (def, cached_lhs);
+	}
+      return;
+    }
   else
     gcc_unreachable ();
 
@@ -2299,8 +2377,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);