tree-ssa-pre.c (bb_value_sets_t): Add antic_safe_loads.

2006-02-06  Daniel Berlin  <dberlin@dberlin.org>

	* tree-ssa-pre.c (bb_value_sets_t): Add antic_safe_loads.
	(ANTIC_SAFE_LOADS): New macro.
	(find_or_generate_expression): Add prototype.
	(set_contains_value): Allow null set for sake of not always having
	to allocate ANTIC_SAFE_LOADS.
	(phi_translate): Move placement of AGGREGATE_TYPE_P check.
	Allow COMPONENT_REF too.
	(valid_in_set): Allow COMPONENT_REF.
	Check ANTIC_SAFE_LOADS too.
	(compute_antic_aux): Print out ANTIC_SAFE_LOADS.
	(compute_rvuse_and_antic_safe): Add ANTIC_SAFE computation, and
	rename.
	(can_PRE_operation): Add COMPONENT_REF.
	(create_component_ref_by_pieces): New function.
	(create_expression_by_pieces): Use create_component_ref_by_pieces.
	(insert_aux): Move AGGREGATE_TYPE_P check here.
	(compute_avail): Set bb local stmt uids.
	(pass_pre): Use TODO_update_ssa_only_virtuals.

2006-02-06  Daniel Berlin  <dberlin@dberlin.org>

	* gcc.dg/tree-ssa/loadpre10.c: New test.
	* gcc.dg/tree-ssa/loadpre11.c: Ditto.
	* gcc.dg/tree-ssa/loadpre6.c: Expect one more elimination.
	* gcc.dg/tree-ssa/loadpre4.c: This should pass now.

From-SVN: r110644

1 files changed, 201 insertions, 28 deletions

diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 4c4cec5..0df5a19 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -53,6 +53,11 @@ Boston, MA 02110-1301, USA.  */
       we can repair later on.
    3. We can do back-substitution or smarter value numbering to catch
       commutative expressions split up over multiple statements.
+   4. ANTIC_SAFE_LOADS could be a lot smarter than it is now.
+      Right now, it is simply calculating loads that occur before
+      any store in a block, instead of loads that occur before
+      stores that affect them.  This is relatively more expensive, and
+      it's not clear how much more it will buy us.
 */   
 
 /* For ease of terminology, "expression node" in the below refers to
@@ -258,6 +263,11 @@ typedef struct bb_value_sets
   bitmap rvuse_out;
   bitmap rvuse_gen;
   bitmap rvuse_kill;
+
+  /* For actually occuring loads, as long as they occur before all the
+     other stores in the block, we know they are antic at the top of
+     the block, regardless of RVUSE_KILL.  */
+  value_set_t antic_safe_loads;
 } *bb_value_sets_t;
 
 #define EXP_GEN(BB)	((bb_value_sets_t) ((BB)->aux))->exp_gen
@@ -270,6 +280,7 @@ typedef struct bb_value_sets
 #define RVUSE_KILL(BB)   ((bb_value_sets_t) ((BB)->aux))->rvuse_kill
 #define RVUSE_OUT(BB)    ((bb_value_sets_t) ((BB)->aux))->rvuse_out
 #define NEW_SETS(BB)	((bb_value_sets_t) ((BB)->aux))->new_sets
+#define ANTIC_SAFE_LOADS(BB) ((bb_value_sets_t) ((BB)->aux))->antic_safe_loads
 
 /* This structure is used to keep track of statistics on what
    optimization PRE was able to perform.  */
@@ -302,6 +313,7 @@ static bitmap_set_t bitmap_set_new (void);
 static value_set_t set_new  (bool);
 static bool is_undefined_value (tree);
 static tree create_expression_by_pieces (basic_block, tree, tree);
+static tree find_or_generate_expression (basic_block, tree, tree);
 
 
 /* We can add and remove elements and entries to and from sets
@@ -701,7 +713,7 @@ set_contains_value (value_set_t set, tree val)
   if (is_gimple_min_invariant (val))
     return true;
   
-  if (set->length == 0)
+  if (!set || set->length == 0)
     return false;
   
   return value_exists_in_set_bitmap (set, val);
@@ -1102,6 +1114,18 @@ phi_translate (tree expr, value_set_t set, basic_block pred,
 		tree newval;
 		if (oldval)
 		  {
+		    /* This may seem like a weird place for this
+		       check, but it's actually the easiest place to
+		       do it.  We can't do it lower on in the
+		       recursion because it's valid for pieces of a
+		       component ref to be of AGGREGATE_TYPE, as long
+		       as the outermost one is not.
+		       To avoid *that* case, we have a check for
+		       AGGREGATE_TYPE_P in insert_aux.  However, that
+		       check will *not* catch this case because here
+		       it occurs in the argument list.  */
+		    if (AGGREGATE_TYPE_P (TREE_TYPE (oldval)))
+		      return NULL;
 		    newval = phi_translate (find_leader (set, oldval),
 					    set, pred, phiblock);
 		    if (newval == NULL)
@@ -1160,7 +1184,7 @@ phi_translate (tree expr, value_set_t set, basic_block pred,
 	VEC (tree, gc) * newvuses = NULL;
 
 	if (TREE_CODE (expr) != INDIRECT_REF
-	    || AGGREGATE_TYPE_P (TREE_TYPE (expr)))
+	    && TREE_CODE (expr) != COMPONENT_REF)
 	  return NULL;
 
 	newop1 = phi_translate (find_leader (set, oldop1),
@@ -1435,12 +1459,11 @@ vuses_dies_in_block_x (VEC (tree, gc) *vuses, basic_block block)
 
   for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
     {
-      /* Any places where this is too conservative, are  places
+      /* Any places where this is too conservative, are places
 	 where we created a new version and shouldn't have.  */
 
       if (!bitmap_bit_p (RVUSE_IN (block), SSA_NAME_VERSION (vuse))
-	  || bitmap_bit_p (RVUSE_KILL (block), SSA_NAME_VERSION
-			   (vuse)))
+	  || bitmap_bit_p (RVUSE_KILL (block), SSA_NAME_VERSION (vuse)))
 	return true;
     }
   return false;
@@ -1501,7 +1524,8 @@ valid_in_set (value_set_t set, tree expr, basic_block block)
       
     case tcc_reference:
       {
-	if (TREE_CODE (expr) == INDIRECT_REF)
+	if (TREE_CODE (expr) == INDIRECT_REF 
+	    || TREE_CODE (expr) == COMPONENT_REF)
 	  {
 	    tree op0 = TREE_OPERAND (expr, 0);
 	    if (is_gimple_min_invariant (op0)
@@ -1509,8 +1533,12 @@ valid_in_set (value_set_t set, tree expr, basic_block block)
 	      {
 		bool retval = set_contains_value (set, op0);
 		if (retval)
-		  return !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh),
+		  {
+		    return set_contains_value (ANTIC_SAFE_LOADS (block),
+					       vh)
+		      || !vuses_dies_in_block_x (VALUE_HANDLE_VUSES (vh),
 						 block);
+		  }
 		return false;
 	      }
 	  }
@@ -1649,7 +1677,12 @@ compute_antic_aux (basic_block block, bool block_has_abnormal_pred_edge)
     {
       if (ANTIC_OUT)
 	print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
+
+      if (ANTIC_SAFE_LOADS (block))
+	print_value_set (dump_file, ANTIC_SAFE_LOADS (block), 
+			 "ANTIC_SAFE_LOADS", block->index);
       print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
+
       if (S)
 	print_value_set (dump_file, S, "S", block->index);
     }
@@ -1803,16 +1836,37 @@ compute_vuse_representatives (void)
   VEC_free (tree, heap, phis);
 }
 
-/* Compute reaching vuses.  This is a small bit of iterative dataflow
-   to determine what virtual uses reach what blocks.  Because we can't
-   generate overlapping virtual uses, and virtual uses *do* actually
-   die, this ends up being faster in most cases than continually
-   walking the virtual use/def chains to determine whether we are
-   inside a block where a given virtual is still available to be
-   used.  */
+/* Compute reaching vuses and antic safe loads.  RVUSE computation is
+   is a small bit of iterative dataflow to determine what virtual uses
+   reach what blocks.  Because we can't generate overlapping virtual
+   uses, and virtual uses *do* actually die, this ends up being faster
+   in most cases than continually walking the virtual use/def chains
+   to determine whether we are inside a block where a given virtual is
+   still available to be used.  
+
+   ANTIC_SAFE_LOADS are those loads that actually occur before any kill to
+   their vuses in the block,and thus, are safe at the top of the
+   block.  
+
+   An example:
+
+   <block begin>
+   b = *a
+   *a = 9
+   <block end>
+   
+   b = *a is an antic safe load because it still safe to consider it
+   ANTIC at the top of the block.
+
+   We currently compute a conservative approximation to
+   ANTIC_SAFE_LOADS.  We compute those loads that occur before *any*
+   stores in the block.  This is not because it is difficult to
+   compute the precise answer, but because it is expensive.  More
+   testing is necessary to determine whether it is worth computing the
+   precise answer.  */
 
 static void
-compute_rvuse (void)
+compute_rvuse_and_antic_safe (void)
 {
 
   size_t i;
@@ -1820,7 +1874,10 @@ compute_rvuse (void)
   basic_block bb;
   int *postorder;
   bool changed = true;
+  unsigned int *first_store_uid;
 
+  first_store_uid = xcalloc (n_basic_blocks, sizeof (unsigned int));
+  
   compute_vuse_representatives ();
 
   FOR_ALL_BB (bb)
@@ -1829,9 +1886,9 @@ compute_rvuse (void)
       RVUSE_GEN (bb) = BITMAP_ALLOC (&grand_bitmap_obstack);
       RVUSE_KILL (bb) = BITMAP_ALLOC (&grand_bitmap_obstack);
       RVUSE_OUT (bb) = BITMAP_ALLOC (&grand_bitmap_obstack);
+      ANTIC_SAFE_LOADS (bb) = NULL;
     }
 
-
   /* Mark live on entry */
   for (i = 0; i < num_ssa_names; i++)
     {
@@ -1854,10 +1911,18 @@ compute_rvuse (void)
       def_operand_p defp;
       use_operand_p usep;
 
-
       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 	{
 	  tree stmt = bsi_stmt (bsi);
+	  
+	  if (first_store_uid[bb->index] == 0 
+	      && !ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYUSE | SSA_OP_VMAYDEF 
+				     | SSA_OP_VMUSTDEF | SSA_OP_VMUSTKILL))
+	    {
+	      first_store_uid[bb->index] = stmt_ann (stmt)->uid;
+	    }
+	  
+
 	  FOR_EACH_SSA_USE_OPERAND (usep, stmt, iter, SSA_OP_VIRTUAL_KILLS
 				    | SSA_OP_VMAYUSE)
 	    {
@@ -1950,6 +2015,40 @@ compute_rvuse (void)
 	  dump_bitmap_of_names (dump_file, RVUSE_OUT (bb));
 	}
     }
+
+  FOR_EACH_BB (bb)
+    {      
+      value_set_node_t node;
+      if (bitmap_empty_p (RVUSE_KILL (bb)))
+	continue;
+      
+      for (node = EXP_GEN (bb)->head; node; node = node->next)
+	{
+	  if (REFERENCE_CLASS_P (node->expr))
+	    {
+	      tree vh = get_value_handle (node->expr);
+	      tree maybe = bitmap_find_leader (AVAIL_OUT (bb), vh);
+	      
+	      if (maybe)
+		{
+		  tree def = SSA_NAME_DEF_STMT (maybe);
+
+		  if (bb_for_stmt (def) != bb)
+		    continue;
+		  
+		  if (TREE_CODE (def) == PHI_NODE
+		      || stmt_ann (def)->uid < first_store_uid[bb->index])
+		    {
+		      if (ANTIC_SAFE_LOADS (bb) == NULL)
+			ANTIC_SAFE_LOADS (bb) = set_new (true);
+		      value_insert_into_set (ANTIC_SAFE_LOADS (bb), 
+					     node->expr);
+		    }
+		}
+	    }
+	}
+    }
+  free (first_store_uid);
 }
 
 /* Return true if we can value number the call in STMT.  This is true
@@ -1991,6 +2090,7 @@ can_PRE_operation (tree op)
     || BINARY_CLASS_P (op)
     || COMPARISON_CLASS_P (op)
     || TREE_CODE (op) == INDIRECT_REF
+    || TREE_CODE (op) == COMPONENT_REF
     || TREE_CODE (op) == CALL_EXPR;
 }
 
@@ -2005,6 +2105,70 @@ static VEC(tree,heap) *inserted_exprs;
    to see which expressions need to be put into GC'able memory  */
 static VEC(tree, heap) *need_creation;
 
+/* For COMPONENT_REF's, we can't have any intermediates for the
+   COMPONENT_REF or INDIRECT_REF portion, because we'd end up with
+   trying to rename aggregates into ssa form directly, which is a no
+   no.
+
+   Thus, this routine doesn't create temporaries, it just builds a
+   single access expression for the array, calling
+   find_or_generate_expression to build the innermost pieces.
+   
+   This function is a subroutine of create_expression_by_pieces, and
+   should not be called on it's own unless you really know what you
+   are doing.
+*/
+static tree
+create_component_ref_by_pieces (basic_block block, tree expr, tree stmts)
+{
+  tree genop = expr;
+  tree folded;
+
+  if (TREE_CODE (genop) == VALUE_HANDLE)
+    {
+      tree found = bitmap_find_leader (AVAIL_OUT (block), expr);
+      if (found)
+	return found;
+    }
+  
+  if (TREE_CODE (genop) == VALUE_HANDLE)
+    genop = VALUE_HANDLE_EXPR_SET (expr)->head->expr;
+
+  switch TREE_CODE (genop)
+    {
+    case COMPONENT_REF:
+      {
+	tree op0;
+	tree op1;
+	op0 = create_component_ref_by_pieces (block, 
+					      TREE_OPERAND (genop, 0),
+					      stmts);
+	op1 = VALUE_HANDLE_EXPR_SET (TREE_OPERAND (genop, 1))->head->expr;
+	folded = fold_build3 (COMPONENT_REF, TREE_TYPE (genop), op0, op1, 
+			      NULL_TREE);
+	return folded;
+      }
+      break;
+    case INDIRECT_REF:
+      {
+	tree op1 = TREE_OPERAND (genop, 0);
+	tree genop1 = find_or_generate_expression (block, op1, stmts);
+	
+	folded = fold_build1 (TREE_CODE (genop), TREE_TYPE (genop),
+			      genop1);
+	return folded;
+      }
+      break;
+    case VAR_DECL:
+    case PARM_DECL:
+    case SSA_NAME:
+      return genop;
+    default:
+      gcc_unreachable ();      
+    }
+
+  return NULL_TREE;
+}
 
 /* Find a leader for an expression, or generate one using
    create_expression_by_pieces if it's ANTIC but
@@ -2093,13 +2257,19 @@ create_expression_by_pieces (basic_block block, tree expr, tree stmts)
       }
       break;
     case tcc_reference:
-      gcc_assert (TREE_CODE (expr) == INDIRECT_REF);
       {
-	tree op1 = TREE_OPERAND (expr, 0);
-	tree genop1 = find_or_generate_expression (block, op1, stmts);
-
-	folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
-			      genop1);
+	if (TREE_CODE (expr) == COMPONENT_REF)
+	  {
+	    folded = create_component_ref_by_pieces (block, expr, stmts);
+	  }
+	else
+	  {
+	    tree op1 = TREE_OPERAND (expr, 0);
+	    tree genop1 = find_or_generate_expression (block, op1, stmts);
+	    
+	    folded = fold_build1 (TREE_CODE (expr), TREE_TYPE (expr),
+				  genop1);
+	  }
 	break;
       }
       
@@ -2404,7 +2574,8 @@ insert_aux (basic_block block)
 		   node;
 		   node = node->next)
 		{
-		  if (can_PRE_operation (node->expr))
+		  if (can_PRE_operation (node->expr)
+		      && !AGGREGATE_TYPE_P (TREE_TYPE (node->expr)))
 		    {
 		      tree *avail;
 		      tree val;
@@ -2746,7 +2917,7 @@ insert_extra_phis (basic_block block, basic_block dom)
 
       FOR_EACH_EDGE (e, ei, block->preds)
 	{
-	  /* We cannot handle abnormal incomming edges correctly.  */
+	  /* We cannot handle abnormal incoming edges correctly.  */
 	  if (e->flags & EDGE_ABNORMAL)
 	    return;
 
@@ -3076,7 +3247,6 @@ compute_avail (void)
   basic_block *worklist;
   size_t sp = 0;
   tree param;
-
   /* For arguments with default definitions, we pretend they are
      defined in the entry block.  */
   for (param = DECL_ARGUMENTS (current_function_decl);
@@ -3121,6 +3291,7 @@ compute_avail (void)
       block_stmt_iterator bsi;
       tree stmt, phi;
       basic_block dom;
+      unsigned int stmt_uid = 1;
 
       /* Pick a block from the worklist.  */
       block = worklist[--sp];
@@ -3152,6 +3323,8 @@ compute_avail (void)
 
 	  stmt = bsi_stmt (bsi);
 	  ann = stmt_ann (stmt);
+	  
+	  ann->uid = stmt_uid++;
 
 	  /* For regular value numbering, we are only interested in
 	     assignments of the form X_i = EXPR, where EXPR represents
@@ -3597,7 +3770,7 @@ execute_pre (bool do_fre)
   if (!do_fre && n_basic_blocks < 4000)
     {
       vuse_names = XCNEWVEC (bitmap, num_ssa_names);
-      compute_rvuse ();
+      compute_rvuse_and_antic_safe ();
       compute_antic ();
       insert ();
       free (vuse_names);
@@ -3655,7 +3828,7 @@ struct tree_opt_pass pass_pre =
   0,					/* properties_provided */
   0,					/* properties_destroyed */
   0,					/* todo_flags_start */
-  TODO_update_ssa | TODO_dump_func | TODO_ggc_collect 
+  TODO_update_ssa_only_virtuals | TODO_dump_func | TODO_ggc_collect 
   | TODO_verify_ssa, /* todo_flags_finish */
   0					/* letter */
 };