2008-09-01 Basile Starynkevitch <basile@starynkevitch.net>

	MERGED WITH TRUNK rev139820
	* gcc/melt/warmelt-first.bysl: added location argument to inform.
	* gcc/warmelt-first-0.c: regenerated.
	* gcc/warmelt-macro-0.c: regenerated.
	* gcc/warmelt-normal-0.c: regenerated.
	* gcc/warmelt-genobj-0.c: regenerated.
	* gcc/warmelt-outobj-0.c: regenerated.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/melt-branch@139849 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 197 insertions, 139 deletions

diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index af4060c6a1e..348382ecae3 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -39,9 +39,18 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-chrec.h"
 
 
-/* Set of SSA names found during the dominator traversal of a
-   sub-graph in find_assert_locations.  */
-static sbitmap found_in_subgraph;
+/* Set of SSA names found live during the RPO traversal of the function
+   for still active basic-blocks.  */
+static sbitmap *live;
+
+/* Return true if the SSA name NAME is live on the edge E.  */
+
+static bool
+live_on_edge (edge e, tree name)
+{
+  return (live[e->dest->index]
+	  && TEST_BIT (live[e->dest->index], SSA_NAME_VERSION (name)));
+}
 
 /* Local functions.  */
 static int compare_values (tree val1, tree val2);
@@ -91,10 +100,6 @@ static bitmap need_assert_for;
    ASSERT_EXPRs for SSA name N_I should be inserted.  */
 static assert_locus_t *asserts_for;
 
-/* Set of blocks visited in find_assert_locations.  Used to avoid
-   visiting the same block more than once.  */
-static sbitmap blocks_visited;
-
 /* Value range array.  After propagation, VR_VALUE[I] holds the range
    of values that SSA name N_I may take.  */
 static value_range_t **vr_value;
@@ -1348,6 +1353,30 @@ ssa_name_nonzero_p (const_tree t)
   return false;
 }
 
+/* If OP has a value range with a single constant value return that,
+   otherwise return NULL_TREE.  This returns OP itself if OP is a
+   constant.  */
+
+static tree
+op_with_constant_singleton_value_range (tree op)
+{
+  value_range_t *vr;
+
+  if (is_gimple_min_invariant (op))
+    return op;
+
+  if (TREE_CODE (op) != SSA_NAME)
+    return NULL_TREE;
+
+  vr = get_value_range (op);
+  if (vr->type == VR_RANGE
+      && operand_equal_p (vr->min, vr->max, 0)
+      && is_gimple_min_invariant (vr->min))
+    return vr->min;
+
+  return NULL_TREE;
+}
+
 
 /* Extract value range information from an ASSERT_EXPR EXPR and store
    it in *VR_P.  */
@@ -2028,6 +2057,22 @@ extract_range_from_binary_expr (value_range_t *vr,
       && code != TRUTH_AND_EXPR
       && code != TRUTH_OR_EXPR)
     {
+      /* We can still do constant propagation here.  */
+      tree const_op0 = op_with_constant_singleton_value_range (op0);
+      tree const_op1 = op_with_constant_singleton_value_range (op1);
+      if (const_op0 || const_op1)
+	{
+	  tree tem = fold_binary (code, expr_type,
+				  const_op0 ? const_op0 : op0,
+				  const_op1 ? const_op1 : op1);
+	  if (tem
+	      && is_gimple_min_invariant (tem)
+	      && !is_overflow_infinity (tem))
+	    {
+	      set_value_range (vr, VR_RANGE, tem, tem, NULL);
+	      return;
+	    }
+	}
       set_value_range_to_varying (vr);
       return;
     }
@@ -2432,6 +2477,18 @@ extract_range_from_unary_expr (value_range_t *vr, enum tree_code code,
       || code == BIT_NOT_EXPR
       || code == CONJ_EXPR)
     {
+      /* We can still do constant propagation here.  */
+      if ((op0 = op_with_constant_singleton_value_range (op0)) != NULL_TREE)
+	{
+	  tree tem = fold_unary (code, type, op0);
+	  if (tem
+	      && is_gimple_min_invariant (tem)
+	      && !is_overflow_infinity (tem))
+	    {
+	      set_value_range (vr, VR_RANGE, tem, tem, NULL);
+	      return;
+	    }
+	}
       set_value_range_to_varying (vr);
       return;
     }
@@ -2483,8 +2540,7 @@ extract_range_from_unary_expr (value_range_t *vr, enum tree_code code,
     }
 
   /* Handle unary expressions on integer ranges.  */
-  if ((code == NOP_EXPR
-       || code == CONVERT_EXPR)
+  if (CONVERT_EXPR_CODE_P (code)
       && INTEGRAL_TYPE_P (type)
       && INTEGRAL_TYPE_P (TREE_TYPE (op0)))
     {
@@ -2654,7 +2710,10 @@ extract_range_from_unary_expr (value_range_t *vr, enum tree_code code,
 	max = fold_unary_to_constant (code, type, vr0.max);
       else if (!needs_overflow_infinity (type))
 	max = TYPE_MAX_VALUE (type);
-      else if (supports_overflow_infinity (type))
+      else if (supports_overflow_infinity (type)
+	       /* We shouldn't generate [+INF, +INF] as set_value_range
+		  doesn't like this and ICEs.  */
+	       && !is_positive_overflow_infinity (min))
 	max = positive_overflow_infinity (type);
       else
 	{
@@ -3911,7 +3970,7 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
 
   /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
      reachable from E.  */
-  if (TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name))
+  if (live_on_edge (e, name)
       && !has_single_use (name))
     {
       register_new_assert_for (name, name, comp_code, val, NULL, e, bsi);
@@ -3944,8 +4003,7 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
       /* Extract NAME2 from the (optional) sign-changing cast.  */
       if (gimple_assign_cast_p (def_stmt))
 	{
-	  if ((gimple_assign_rhs_code (def_stmt) == NOP_EXPR
-	       || gimple_assign_rhs_code (def_stmt) == CONVERT_EXPR)
+	  if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
 	      && ! TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (def_stmt)))
 	      && (TYPE_PRECISION (gimple_expr_type (def_stmt))
 		  == TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt)))))
@@ -3958,7 +4016,7 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
 	  && (cst2 == NULL_TREE
 	      || TREE_CODE (cst2) == INTEGER_CST)
 	  && INTEGRAL_TYPE_P (TREE_TYPE (name3))
-	  && TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name3))
+	  && live_on_edge (e, name3)
 	  && !has_single_use (name3))
 	{
 	  tree tmp;
@@ -3987,7 +4045,7 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
       	  && TREE_CODE (name2) == SSA_NAME
 	  && TREE_CODE (cst2) == INTEGER_CST
 	  && INTEGRAL_TYPE_P (TREE_TYPE (name2))
-	  && TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name2))
+	  && live_on_edge (e, name2)
 	  && !has_single_use (name2))
 	{
 	  tree tmp;
@@ -4098,8 +4156,7 @@ register_edge_assert_for_1 (tree op, enum tree_code code,
       retval |= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def),
 					    code, e, bsi);
     }
-  else if (gimple_assign_rhs_code (op_def) == NOP_EXPR
-	   || gimple_assign_rhs_code (op_def) == CONVERT_EXPR)
+  else if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (op_def)))
     { 
       /* Recurse through the type conversion.  */
       retval |= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def),
@@ -4188,8 +4245,6 @@ register_edge_assert_for (tree name, edge e, gimple_stmt_iterator si,
 }
 
 
-static bool find_assert_locations (basic_block bb);
-
 /* Determine whether the outgoing edges of BB should receive an
    ASSERT_EXPR for each of the operands of BB's LAST statement.
    The last statement of BB must be a COND_EXPR.
@@ -4220,35 +4275,6 @@ find_conditional_asserts (basic_block bb, gimple last)
       if (e->dest == bb)
 	continue;
 
-      /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap.
-	 Otherwise, when we finish traversing each of the sub-graphs, we
-	 won't know whether the variables were found in the sub-graphs or
-	 if they had been found in a block upstream from BB. 
-
-	 This is actually a bad idea is some cases, particularly jump
-	 threading.  Consider a CFG like the following:
-
-                    0
-                   /|
-                  1 |
-                   \|
-                    2
-                   / \
-                  3   4
-
-	 Assume that one or more operands in the conditional at the
-	 end of block 0 are used in a conditional in block 2, but not
-	 anywhere in block 1.  In this case we will not insert any
-	 assert statements in block 1, which may cause us to miss
-	 opportunities to optimize, particularly for jump threading.  */
-      FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
-	RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
-
-      /* Traverse the strictly dominated sub-graph rooted at E->DEST
-	 to determine if any of the operands in the conditional
-	 predicate are used.  */
-      need_assert |= find_assert_locations (e->dest);
-
       /* Register the necessary assertions for each operand in the
 	 conditional predicate.  */
       FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
@@ -4260,11 +4286,6 @@ find_conditional_asserts (basic_block bb, gimple last)
 	}
     }
 
-  /* Finally, indicate that we have found the operands in the
-     conditional.  */
-  FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
-    SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
-
   return need_assert;
 }
 
@@ -4312,7 +4333,12 @@ find_switch_asserts (basic_block bb, gimple last)
   edge e;
   tree vec2;
   size_t n = gimple_switch_num_labels(last);
+#if GCC_VERSION >= 4000
   unsigned int idx;
+#else
+  /* Work around GCC 3.4 bug (PR 37086).  */
+  volatile unsigned int idx;
+#endif
 
   need_assert = false;
   bsi = gsi_for_stmt (last);
@@ -4361,18 +4387,6 @@ find_switch_asserts (basic_block bb, gimple last)
       /* Find the edge to register the assert expr on.  */
       e = find_edge (bb, label_to_block (CASE_LABEL (cl)));
 
-      /* Remove the SWITCH_EXPR operand from the FOUND_IN_SUBGRAPH bitmap.
-	 Otherwise, when we finish traversing each of the sub-graphs, we
-	 won't know whether the variables were found in the sub-graphs or
-	 if they had been found in a block upstream from BB.  */
-      RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
-
-      /* Traverse the strictly dominated sub-graph rooted at E->DEST
-	 to determine if any of the operands in the conditional
-	 predicate are used.  */
-      if (e->dest != bb)
-	need_assert |= find_assert_locations (e->dest);
-
       /* Register the necessary assertions for the operand in the
 	 SWITCH_EXPR.  */
       need_assert |= register_edge_assert_for (op, e, bsi,
@@ -4389,10 +4403,6 @@ find_switch_asserts (basic_block bb, gimple last)
 	}
     }
 
-  /* Finally, indicate that we have found the operand in the
-     SWITCH_EXPR.  */
-  SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
-
   return need_assert;
 }
 
@@ -4461,42 +4471,33 @@ find_switch_asserts (basic_block bb, gimple last)
    inserted by process_assert_insertions.  */
 
 static bool
-find_assert_locations (basic_block bb)
+find_assert_locations_1 (basic_block bb, sbitmap live)
 {
   gimple_stmt_iterator si;
   gimple last;
   gimple phi;
   bool need_assert;
-  basic_block son;
-
-  if (TEST_BIT (blocks_visited, bb->index))
-    return false;
-
-  SET_BIT (blocks_visited, bb->index);
 
   need_assert = false;
+  last = last_stmt (bb);
 
-  /* Traverse all PHI nodes in BB marking used operands.  */
-  for (si = gsi_start_phis (bb); !gsi_end_p(si); gsi_next (&si))
-    {
-      use_operand_p arg_p;
-      ssa_op_iter i;
-      phi = gsi_stmt (si);
+  /* If BB's last statement is a conditional statement involving integer
+     operands, determine if we need to add ASSERT_EXPRs.  */
+  if (last
+      && gimple_code (last) == GIMPLE_COND
+      && !fp_predicate (last)
+      && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
+    need_assert |= find_conditional_asserts (bb, last);
 
-      FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
-	{
-	  tree arg = USE_FROM_PTR (arg_p);
-	  if (TREE_CODE (arg) == SSA_NAME)
-	    {
-	      gcc_assert (is_gimple_reg (PHI_RESULT (phi)));
-	      SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg));
-	    }
-	}
-    }
+  /* If BB's last statement is a switch statement involving integer
+     operands, determine if we need to add ASSERT_EXPRs.  */
+  if (last
+      && gimple_code (last) == GIMPLE_SWITCH
+      && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
+    need_assert |= find_switch_asserts (bb, last);
 
   /* Traverse all the statements in BB marking used names and looking
      for statements that may infer assertions for their used operands.  */
-  last = NULL;
   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
     {
       gimple stmt;
@@ -4511,12 +4512,8 @@ find_assert_locations (basic_block bb)
 	  tree value;
 	  enum tree_code comp_code;
 
-	  /* Mark OP in bitmap FOUND_IN_SUBGRAPH.  If STMT is inside
-	     the sub-graph of a conditional block, when we return from
-	     this recursive walk, our parent will use the
-	     FOUND_IN_SUBGRAPH bitset to determine if one of the
-	     operands it was looking for was present in the sub-graph.  */
-	  SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
+	  /* Mark OP in our live bitmap.  */
+	  SET_BIT (live, SSA_NAME_VERSION (op));
 
 	  /* If OP is used in such a way that we can infer a value
 	     range for it, and we don't find a previous assertion for
@@ -4567,34 +4564,113 @@ find_assert_locations (basic_block bb)
 		}
 	    }
 	}
-
-      /* Remember the last statement of the block.  */
-      last = stmt;
     }
 
-  /* If BB's last statement is a conditional expression
-     involving integer operands, recurse into each of the sub-graphs
-     rooted at BB to determine if we need to add ASSERT_EXPRs.  */
-  if (last
-      && gimple_code (last) == GIMPLE_COND
-      && !fp_predicate (last)
-      && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
-    need_assert |= find_conditional_asserts (bb, last);
-
-  if (last
-      && gimple_code (last) == GIMPLE_SWITCH
-      && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
-    need_assert |= find_switch_asserts (bb, last);
+  /* Traverse all PHI nodes in BB marking used operands.  */
+  for (si = gsi_start_phis (bb); !gsi_end_p(si); gsi_next (&si))
+    {
+      use_operand_p arg_p;
+      ssa_op_iter i;
+      phi = gsi_stmt (si);
 
-  /* Recurse into the dominator children of BB.  */
-  for (son = first_dom_son (CDI_DOMINATORS, bb);
-       son;
-       son = next_dom_son (CDI_DOMINATORS, son))
-    need_assert |= find_assert_locations (son);
+      FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
+	{
+	  tree arg = USE_FROM_PTR (arg_p);
+	  if (TREE_CODE (arg) == SSA_NAME)
+	    SET_BIT (live, SSA_NAME_VERSION (arg));
+	}
+    }
 
   return need_assert;
 }
 
+/* Do an RPO walk over the function computing SSA name liveness
+   on-the-fly and deciding on assert expressions to insert.
+   Returns true if there are assert expressions to be inserted.  */
+
+static bool
+find_assert_locations (void)
+{
+  int *rpo = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
+  int *bb_rpo = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
+  int *last_rpo = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
+  int rpo_cnt, i;
+  bool need_asserts;
+
+  live = XCNEWVEC (sbitmap, last_basic_block + NUM_FIXED_BLOCKS);
+  rpo_cnt = pre_and_rev_post_order_compute (NULL, rpo, false);
+  for (i = 0; i < rpo_cnt; ++i)
+    bb_rpo[rpo[i]] = i;
+
+  need_asserts = false;
+  for (i = rpo_cnt-1; i >= 0; --i)
+    {
+      basic_block bb = BASIC_BLOCK (rpo[i]);
+      edge e;
+      edge_iterator ei;
+
+      if (!live[rpo[i]])
+	{
+	  live[rpo[i]] = sbitmap_alloc (num_ssa_names);
+	  sbitmap_zero (live[rpo[i]]);
+	}
+
+      /* Process BB and update the live information with uses in
+         this block.  */
+      need_asserts |= find_assert_locations_1 (bb, live[rpo[i]]);
+
+      /* Merge liveness into the predecessor blocks and free it.  */
+      if (!sbitmap_empty_p (live[rpo[i]]))
+	{
+	  int pred_rpo = i;
+	  FOR_EACH_EDGE (e, ei, bb->preds)
+	    {
+	      int pred = e->src->index;
+	      if (e->flags & EDGE_DFS_BACK)
+		continue;
+
+	      if (!live[pred])
+		{
+		  live[pred] = sbitmap_alloc (num_ssa_names);
+		  sbitmap_zero (live[pred]);
+		}
+	      sbitmap_a_or_b (live[pred], live[pred], live[rpo[i]]);
+
+	      if (bb_rpo[pred] < pred_rpo)
+		pred_rpo = bb_rpo[pred];
+	    }
+
+	  /* Record the RPO number of the last visited block that needs
+	     live information from this block.  */
+	  last_rpo[rpo[i]] = pred_rpo;
+	}
+      else
+	{
+	  sbitmap_free (live[rpo[i]]);
+	  live[rpo[i]] = NULL;
+	}
+
+      /* We can free all successors live bitmaps if all their
+         predecessors have been visited already.  */
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	if (last_rpo[e->dest->index] == i
+	    && live[e->dest->index])
+	  {
+	    sbitmap_free (live[e->dest->index]);
+	    live[e->dest->index] = NULL;
+	  }
+    }
+
+  XDELETEVEC (rpo);
+  XDELETEVEC (bb_rpo);
+  XDELETEVEC (last_rpo);
+  for (i = 0; i < last_basic_block + NUM_FIXED_BLOCKS; ++i)
+    if (live[i])
+      sbitmap_free (live[i]);
+  XDELETEVEC (live);
+
+  return need_asserts;
+}
 
 /* Create an ASSERT_EXPR for NAME and insert it in the location
    indicated by LOC.  Return true if we made any edge insertions.  */
@@ -4721,27 +4797,12 @@ process_assert_insertions (void)
 static void
 insert_range_assertions (void)
 {
-  edge e;
-  edge_iterator ei;
-  bool update_ssa_p;
-  
-  found_in_subgraph = sbitmap_alloc (num_ssa_names);
-  sbitmap_zero (found_in_subgraph);
-
-  blocks_visited = sbitmap_alloc (last_basic_block);
-  sbitmap_zero (blocks_visited);
-
   need_assert_for = BITMAP_ALLOC (NULL);
   asserts_for = XCNEWVEC (assert_locus_t, num_ssa_names);
 
   calculate_dominance_info (CDI_DOMINATORS);
 
-  update_ssa_p = false;
-  FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
-    if (find_assert_locations (e->dest))
-      update_ssa_p = true;
-
-  if (update_ssa_p)
+  if (find_assert_locations ())
     {
       process_assert_insertions ();
       update_ssa (TODO_update_ssa_no_phi);
@@ -4753,7 +4814,6 @@ insert_range_assertions (void)
       dump_function_to_file (current_function_decl, dump_file, dump_flags);
     }
 
-  sbitmap_free (found_in_subgraph);
   free (asserts_for);
   BITMAP_FREE (need_assert_for);
 }
@@ -5022,8 +5082,6 @@ remove_range_assertions (void)
 	else
 	  gsi_next (&si);
       }
-
-  sbitmap_free (blocks_visited);
 }