--- a/gcc/tree-ssa-loop-im.c	Fri Feb 12 23:41:23 2010 +0900
+++ b/gcc/tree-ssa-loop-im.c	Mon May 24 12:47:05 2010 +0900
@@ -1,6 +1,6 @@
 /* Loop invariant motion.
-   Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Free Software
-   Foundation, Inc.
+   Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2010
+   Free Software Foundation, Inc.
 
 This file is part of GCC.
 
@@ -23,12 +23,12 @@
 #include "coretypes.h"
 #include "tm.h"
 #include "tree.h"
-#include "rtl.h"
 #include "tm_p.h"
-#include "hard-reg-set.h"
 #include "basic-block.h"
 #include "output.h"
 #include "diagnostic.h"
+#include "gimple-pretty-print.h"
+#include "tree-pretty-print.h"
 #include "tree-flow.h"
 #include "tree-dump.h"
 #include "timevar.h"
@@ -37,7 +37,6 @@
 #include "params.h"
 #include "tree-pass.h"
 #include "flags.h"
-#include "real.h"
 #include "hashtab.h"
 #include "tree-affine.h"
 #include "pointer-set.h"
@@ -359,6 +358,12 @@
       return MOVE_POSSIBLE;
     }
 
+  if (gimple_code (stmt) == GIMPLE_PHI
+      && gimple_phi_num_args (stmt) <= 2
+      && is_gimple_reg (gimple_phi_result (stmt))
+      && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt)))
+    return MOVE_POSSIBLE;
+
   if (gimple_get_lhs (stmt) == NULL_TREE)
     return MOVE_IMPOSSIBLE;
 
@@ -513,7 +518,8 @@
   unsigned cost = 1;
 
   /* Always try to create possibilities for unswitching.  */
-  if (gimple_code (stmt) == GIMPLE_COND)
+  if (gimple_code (stmt) == GIMPLE_COND
+      || gimple_code (stmt) == GIMPLE_PHI)
     return LIM_EXPENSIVE;
 
   /* Hoisting memory references out should almost surely be a win.  */
@@ -651,6 +657,63 @@
   return ref;
 }
 
+/* From a controlling predicate in DOM determine the arguments from
+   the PHI node PHI that are chosen if the predicate evaluates to
+   true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
+   they are non-NULL.  Returns true if the arguments can be determined,
+   else return false.  */
+
+static bool
+extract_true_false_args_from_phi (basic_block dom, gimple phi,
+				  tree *true_arg_p, tree *false_arg_p)
+{
+  basic_block bb = gimple_bb (phi);
+  edge true_edge, false_edge, tem;
+  tree arg0 = NULL_TREE, arg1 = NULL_TREE;
+
+  /* We have to verify that one edge into the PHI node is dominated
+     by the true edge of the predicate block and the other edge
+     dominated by the false edge.  This ensures that the PHI argument
+     we are going to take is completely determined by the path we
+     take from the predicate block.  */
+  extract_true_false_edges_from_block (dom, &true_edge, &false_edge);
+  tem = EDGE_PRED (bb, 0);
+  if (tem == true_edge
+      || tem->src == true_edge->dest
+      || dominated_by_p (CDI_DOMINATORS,
+			 tem->src, true_edge->dest))
+    arg0 = PHI_ARG_DEF (phi, tem->dest_idx);
+  else if (tem == false_edge
+	   || tem->src == false_edge->dest
+	   || dominated_by_p (CDI_DOMINATORS,
+			      tem->src, false_edge->dest))
+    arg1 = PHI_ARG_DEF (phi, tem->dest_idx);
+  else
+    return false;
+  tem = EDGE_PRED (bb, 1);
+  if (tem == true_edge
+      || tem->src == true_edge->dest
+      || dominated_by_p (CDI_DOMINATORS,
+			 tem->src, true_edge->dest))
+    arg0 = PHI_ARG_DEF (phi, tem->dest_idx);
+  else if (tem == false_edge
+	   || tem->src == false_edge->dest
+	   || dominated_by_p (CDI_DOMINATORS,
+			      tem->src, false_edge->dest))
+    arg1 = PHI_ARG_DEF (phi, tem->dest_idx);
+  else
+    return false;
+  if (!arg0 || !arg1)
+    return false;
+
+  if (true_arg_p)
+    *true_arg_p = arg0;
+  if (false_arg_p)
+    *false_arg_p = arg1;
+
+  return true;
+}
+
 /* Determine the outermost loop to that it is possible to hoist a statement
    STMT and store it to LIM_DATA (STMT)->max_loop.  To do this we determine
    the outermost loop in that the value computed by STMT is invariant.
@@ -677,9 +740,81 @@
     level = superloop_at_depth (loop, 1);
   lim_data->max_loop = level;
 
-  FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
-    if (!add_dependency (val, lim_data, loop, true))
-      return false;
+  if (gimple_code (stmt) == GIMPLE_PHI)
+    {
+      use_operand_p use_p;
+      unsigned min_cost = UINT_MAX;
+      unsigned total_cost = 0;
+      struct lim_aux_data *def_data;
+
+      /* We will end up promoting dependencies to be unconditionally
+	 evaluated.  For this reason the PHI cost (and thus the
+	 cost we remove from the loop by doing the invariant motion)
+	 is that of the cheapest PHI argument dependency chain.  */
+      FOR_EACH_PHI_ARG (use_p, stmt, iter, SSA_OP_USE)
+	{
+	  val = USE_FROM_PTR (use_p);
+	  if (TREE_CODE (val) != SSA_NAME)
+	    continue;
+	  if (!add_dependency (val, lim_data, loop, false))
+	    return false;
+	  def_data = get_lim_data (SSA_NAME_DEF_STMT (val));
+	  if (def_data)
+	    {
+	      min_cost = MIN (min_cost, def_data->cost);
+	      total_cost += def_data->cost;
+	    }
+	}
+
+      lim_data->cost += min_cost;
+
+      if (gimple_phi_num_args (stmt) > 1)
+	{
+	  basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
+	  gimple cond;
+	  if (gsi_end_p (gsi_last_bb (dom)))
+	    return false;
+	  cond = gsi_stmt (gsi_last_bb (dom));
+	  if (gimple_code (cond) != GIMPLE_COND)
+	    return false;
+	  /* Verify that this is an extended form of a diamond and
+	     the PHI arguments are completely controlled by the
+	     predicate in DOM.  */
+	  if (!extract_true_false_args_from_phi (dom, stmt, NULL, NULL))
+	    return false;
+
+	  /* Fold in dependencies and cost of the condition.  */
+	  FOR_EACH_SSA_TREE_OPERAND (val, cond, iter, SSA_OP_USE)
+	    {
+	      if (!add_dependency (val, lim_data, loop, false))
+		return false;
+	      def_data = get_lim_data (SSA_NAME_DEF_STMT (val));
+	      if (def_data)
+		total_cost += def_data->cost;
+	    }
+
+	  /* We want to avoid unconditionally executing very expensive
+	     operations.  As costs for our dependencies cannot be
+	     negative just claim we are not invariand for this case.
+	     We also are not sure whether the control-flow inside the
+	     loop will vanish.  */
+	  if (total_cost - min_cost >= 2 * LIM_EXPENSIVE
+	      && !(min_cost != 0
+		   && total_cost / min_cost <= 2))
+	    return false;
+
+	  /* Assume that the control-flow in the loop will vanish.
+	     ???  We should verify this and not artificially increase
+	     the cost if that is not the case.  */
+	  lim_data->cost += stmt_cost (stmt);
+	}
+
+      return true;
+    }
+  else
+    FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
+      if (!add_dependency (val, lim_data, loop, true))
+	return false;
 
   if (gimple_vuse (stmt))
     {
@@ -920,6 +1055,43 @@
     fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
 	     bb->index, bb->loop_father->num, loop_depth (bb->loop_father));
 
+  /* Look at PHI nodes, but only if there is at most two.
+     ???  We could relax this further by post-processing the inserted
+     code and transforming adjacent cond-exprs with the same predicate
+     to control flow again.  */
+  bsi = gsi_start_phis (bb);
+  if (!gsi_end_p (bsi)
+      && ((gsi_next (&bsi), gsi_end_p (bsi))
+	  || (gsi_next (&bsi), gsi_end_p (bsi))))
+    for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+      {
+	stmt = gsi_stmt (bsi);
+
+	pos = movement_possibility (stmt);
+	if (pos == MOVE_IMPOSSIBLE)
+	  continue;
+
+	lim_data = init_lim_data (stmt);
+	lim_data->always_executed_in = outermost;
+
+	if (!determine_max_movement (stmt, false))
+	  {
+	    lim_data->max_loop = NULL;
+	    continue;
+	  }
+
+	if (dump_file && (dump_flags & TDF_DETAILS))
+	  {
+	    print_gimple_stmt (dump_file, stmt, 2, 0);
+	    fprintf (dump_file, "  invariant up to level %d, cost %d.\n\n",
+		     loop_depth (lim_data->max_loop),
+		     lim_data->cost);
+	  }
+
+	if (lim_data->cost >= LIM_EXPENSIVE)
+	  set_profitable_level (stmt);
+      }
+
   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
     {
       stmt = gsi_stmt (bsi);
@@ -1021,7 +1193,7 @@
    for walk_dominator_tree.  */
 
 static void
-move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
+move_computations_stmt (struct dom_walk_data *dw_data,
 			basic_block bb)
 {
   struct loop *level;
@@ -1033,6 +1205,67 @@
   if (!loop_outer (bb->loop_father))
     return;
 
+  for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); )
+    {
+      gimple new_stmt;
+      stmt = gsi_stmt (bsi);
+
+      lim_data = get_lim_data (stmt);
+      if (lim_data == NULL)
+	{
+	  gsi_next (&bsi);
+	  continue;
+	}
+
+      cost = lim_data->cost;
+      level = lim_data->tgt_loop;
+      clear_lim_data (stmt);
+
+      if (!level)
+	{
+	  gsi_next (&bsi);
+	  continue;
+	}
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "Moving PHI node\n");
+	  print_gimple_stmt (dump_file, stmt, 0, 0);
+	  fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
+		   cost, level->num);
+	}
+
+      if (gimple_phi_num_args (stmt) == 1)
+	{
+	  tree arg = PHI_ARG_DEF (stmt, 0);
+	  new_stmt = gimple_build_assign_with_ops (TREE_CODE (arg),
+						   gimple_phi_result (stmt),
+						   arg, NULL_TREE);
+	  SSA_NAME_DEF_STMT (gimple_phi_result (stmt)) = new_stmt;
+	}
+      else
+	{
+	  basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
+	  gimple cond = gsi_stmt (gsi_last_bb (dom));
+	  tree arg0 = NULL_TREE, arg1 = NULL_TREE, t;
+	  /* Get the PHI arguments corresponding to the true and false
+	     edges of COND.  */
+	  extract_true_false_args_from_phi (dom, stmt, &arg0, &arg1);
+	  gcc_assert (arg0 && arg1);
+	  t = build2 (gimple_cond_code (cond), boolean_type_node,
+		      gimple_cond_lhs (cond), gimple_cond_rhs (cond));
+	  t = build3 (COND_EXPR, TREE_TYPE (gimple_phi_result (stmt)),
+		      t, arg0, arg1);
+	  new_stmt = gimple_build_assign_with_ops (COND_EXPR,
+						   gimple_phi_result (stmt),
+						   t, NULL_TREE);
+	  SSA_NAME_DEF_STMT (gimple_phi_result (stmt)) = new_stmt;
+	  *((unsigned int *)(dw_data->global_data)) |= TODO_cleanup_cfg;
+	}
+      gsi_insert_on_edge (loop_preheader_edge (level), new_stmt);
+      remove_phi_node (&bsi, false);
+    }
+
   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); )
     {
       stmt = gsi_stmt (bsi);
@@ -1076,12 +1309,14 @@
 /* Hoist the statements out of the loops prescribed by data stored in
    LIM_DATA structures associated with each statement.*/
 
-static void
+static unsigned int
 move_computations (void)
 {
   struct dom_walk_data walk_data;
+  unsigned int todo = 0;
 
   memset (&walk_data, 0, sizeof (struct dom_walk_data));
+  walk_data.global_data = &todo;
   walk_data.dom_direction = CDI_DOMINATORS;
   walk_data.before_dom_children = move_computations_stmt;
 
@@ -1092,6 +1327,8 @@
   gsi_commit_edge_inserts ();
   if (need_ssa_update_p (cfun))
     rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
+
+  return todo;
 }
 
 /* Checks whether the statement defining variable *INDEX can be hoisted
@@ -1776,8 +2013,8 @@
       name = get_name (TREE_OPERAND (ref, 1));
       if (!name)
 	name = "F";
-      lsm_tmp_name_add ("_");
       lsm_tmp_name_add (name);
+      break;
 
     case ARRAY_REF:
       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
@@ -1900,16 +2137,22 @@
     }
 }
 
-/* Returns true if REF is always accessed in LOOP.  */
+/* Returns true if REF is always accessed in LOOP.  If STORED_P is true
+   make sure REF is always stored to in LOOP.  */
 
 static bool
-ref_always_accessed_p (struct loop *loop, mem_ref_p ref)
+ref_always_accessed_p (struct loop *loop, mem_ref_p ref, bool stored_p)
 {
   VEC (mem_ref_loc_p, heap) *locs = NULL;
   unsigned i;
   mem_ref_loc_p loc;
   bool ret = false;
   struct loop *must_exec;
+  tree base;
+
+  base = get_base_address (ref->mem);
+  if (INDIRECT_REF_P (base))
+    base = TREE_OPERAND (base, 0);
 
   get_all_locs_in_loop (loop, ref, &locs);
   for (i = 0; VEC_iterate (mem_ref_loc_p, locs, i, loc); i++)
@@ -1917,6 +2160,22 @@
       if (!get_lim_data (loc->stmt))
 	continue;
 
+      /* If we require an always executed store make sure the statement
+         stores to the reference.  */
+      if (stored_p)
+	{
+	  tree lhs;
+	  if (!gimple_get_lhs (loc->stmt))
+	    continue;
+	  lhs = get_base_address (gimple_get_lhs (loc->stmt));
+	  if (!lhs)
+	    continue;
+	  if (INDIRECT_REF_P (lhs))
+	    lhs = TREE_OPERAND (lhs, 0);
+	  if (lhs != base)
+	    continue;
+	}
+
       must_exec = get_lim_data (loc->stmt)->always_executed_in;
       if (!must_exec)
 	continue;
@@ -2054,6 +2313,8 @@
 static bool
 can_sm_ref_p (struct loop *loop, mem_ref_p ref)
 {
+  tree base;
+
   /* Unless the reference is stored in the loop, there is nothing to do.  */
   if (!bitmap_bit_p (ref->stored, loop->num))
     return false;
@@ -2064,9 +2325,14 @@
       || !for_each_index (&ref->mem, may_move_till, loop))
     return false;
 
-  /* If it can trap, it must be always executed in LOOP.  */
-  if (tree_could_trap_p (ref->mem)
-      && !ref_always_accessed_p (loop, ref))
+  /* If it can trap, it must be always executed in LOOP.
+     Readonly memory locations may trap when storing to them, but
+     tree_could_trap_p is a predicate for rvalues, so check that
+     explicitly.  */
+  base = get_base_address (ref->mem);
+  if ((tree_could_trap_p (ref->mem)
+       || (DECL_P (base) && TREE_READONLY (base)))
+      && !ref_always_accessed_p (loop, ref, true))
     return false;
 
   /* And it must be independent on all other memory references
@@ -2299,9 +2565,11 @@
 /* Moves invariants from loops.  Only "expensive" invariants are moved out --
    i.e. those that are likely to be win regardless of the register pressure.  */
 
-void
+unsigned int
 tree_ssa_lim (void)
 {
+  unsigned int todo;
+
   tree_ssa_lim_initialize ();
 
   /* Gathers information about memory accesses in the loops.  */
@@ -2316,7 +2584,9 @@
   store_motion ();
 
   /* Move the expressions that are expensive enough.  */
-  move_computations ();
+  todo = move_computations ();
 
   tree_ssa_lim_finalize ();
+
+  return todo;
 }