tree.h (VALUE_HANDLE_VUSES): New.

2005-12-29  Daniel Berlin  <dberlin@dberlin.org>

	* tree.h (VALUE_HANDLE_VUSES): New.
	(struct tree_value_handle): Add vuses.

	* tree-vn.c (struct val_expr_pair_d): Remove stmt, add vuses.
	(vn_compute): Remove stmt argument.
	Don't use vuses in hash value computation.
	(val_expr_pair_eq): Compare vuse lists.
	(copy_vuses_from_stmt): New function.
	(shared_vuses_from_stmt): Ditto.
	(vn_add): Rewrite in terms of vn_add_with_vuses.
	(vn_add_with_vuses): New function.
	(vn_lookup): Rewrite in terms of vn_lookup_with_vuses.
	(vn_lookup_with_vuses): New function.
	(vuses_compare): New function.
	(print_creation_to_file): Ditto.
	(vn_lookup_or_add): Rewrite to handle vuses.
	(sort_vuses): New function.
	(vn_lookup_or_add_with_vuses): Ditto.
	(vn_init): Initialize shared_lookup_vuses.
	(vn_delete): Free shared_lookup_vuses.

	* tree-ssa-pre.c: Update todo list.
	(bb_value_sets_t): Add rvuse_in, rvuse_out, rvuse_gen, and
	rvuse_kill.
	(RVUSE_IN): New macro.
	(RVUSE_GEN): Ditto.
	(RVUSE_KILL): Ditto.
	(RVUSE_OUT): Ditto.
	(modify_expr_node_pool): New function.
	(pretemp): New.
	(storetemp): Ditto.
	(mergephitemp): Ditto.
	(prephitemp): Ditto.
	(struct expr_pred_trans_d): Add vuses member.
	(expr_pred_trans_eq): Compare vuses.
	(phi_trans_lookup): Add vuses argument.
	(phi_trans_add): Ditto.
	(translate_vuses_through_block): New function.
	(phi_translate): Use vuses to ask about those expressions that can
	have vuses.
	Properly translate virtual uses through phis, and use
	vn_lookup_or_add_with vuses.  Handle tcc_reference.
	(phi_translate_set): Don't add pointless translations to the
	cache.
	(get_representative): New function.
	(vuses_dies_in_block_x): Ditto.
	(valid_in_set): Add block argument.  Check virtual use validity.
	(clean): Add block argument. Update call to valid_in_set
	(compute_antic_aux): Update call to clean.
	(dump_bitmap_of_names): New function.
	(compute_vuse_representatives): Ditto.
	(compute_rvuse): Ditto.
	(can_value_number_call): Modified to accept calls with vuses.
	(can_value_number_operation): New function.
	(can_PRE_operation): Ditto.
	(need_creation): New vector of stores that may need creation.
	(find_or_generate_expression): use can_PRE_operation.
	(create_expression_by_pieces): Handle INDIRECT_REF.
	Only create one temp until we have to change types.
	Mark new vars for renaming.
	(insert_into_preds_of_block): Ignore loopiness of loads.
	Use can_PRE_operation.
	Only create one temp until we have to chnge types.
	(insert_aux): Use can_PRE_operation.
	Don't pass name to insert_into_preds_of_block.
	(insert_extra_phis): Only use one temp until we have to change
	types.
	(poolify_tree): New function.
	(modify_expr_template): New var.
	(poolify_modify_expr): New function.
	(insert_fake_stores): Ditto.
	(realify_fake_stores): Ditto.
	(compute_avail): Use can_value_number_operation.
	(mark_operand_necessary): Return NULL for non-SSA names.
	(remove_dead_inserted_code): Update comment.
	(init_pre): Initialize pretemp, need_creation, storetemp,
	mergephitemp, prephitemp.
	Create modify_expr_node_pool.
	(fini_pre): Free modify_expr_node_pool and need_creation array.
	(execute_pre): Call insert_fake_stores, compute_rvuse, and
	realify_fake_stores. 
	* tree-flow.h (vn_compute): Fix prototype.
	(vn_add): Ditto.
	(vn_lookup): Ditto.
	(sort_vuses): New.
	(vn_lookup_or_add_with_vuses): Ditto.
	(vn_add_with_vuses): Ditto.
	(vn_lookup_with_vuses): Ditto.
	* passes.c (pass_may_alias): Add.

From-SVN: r109180

8 files changed, 291 insertions, 0 deletions

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loadpre1.c b/gcc/testsuite/gcc.dg/tree-ssa/loadpre1.c
new file mode 100644
index 0000000..e659751
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loadpre1.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+int main(int *a, int argc)
+{
+  int c;
+  int d, e;
+  
+  /* Should be able to eliminate the second load of *a along the main path. */
+  d = *a;
+  if (argc)
+    {
+      a = &c;
+    }
+  e = *a;
+  return d + e;
+}
+/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "pre"} } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loadpre2.c b/gcc/testsuite/gcc.dg/tree-ssa/loadpre2.c
new file mode 100644
index 0000000..8d6557a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loadpre2.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+int main(int *a, int argc)
+{
+  int b;
+  int i;
+  int d, e;
+
+  /* Should be able to hoist this out of the loop.  */
+  for (i = 0; i < argc; i++)
+    {
+      e = *a;
+    }
+  return d + e;
+}
+
+/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "pre"} } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loadpre3.c b/gcc/testsuite/gcc.dg/tree-ssa/loadpre3.c
new file mode 100644
index 0000000..8767e16
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loadpre3.c
@@ -0,0 +1,24 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+int main(int **a,int argc)
+{
+  int b;
+  int d, e;
+
+  if (argc)
+    {
+      d = *(*a);
+    }
+  else
+    {
+
+    }
+  /* Should be able to eliminate one of the *(*a)'s along the if path 
+     by pushing it into the else path. We will also eliminate
+     one of the *a's.  */
+  e = *(*a);
+  return d + e;
+}
+
+/* { dg-final { scan-tree-dump-times "Eliminated: 2" 1 "pre"} } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loadpre4.c b/gcc/testsuite/gcc.dg/tree-ssa/loadpre4.c
new file mode 100644
index 0000000..3b88615
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loadpre4.c
@@ -0,0 +1,21 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+int main(int *a, int argc)
+{
+  int b;
+  int c;
+  int i;
+  int d, e;
+
+  /* With smarter load PRE, we'd be able to recompute the value at the 
+     kill point.  arguably not worth it.  */
+  for (i = 0; i < argc; i++)
+    {
+      e = *a;
+      *a = 9;
+    }
+  return d + e;
+}
+
+/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "pre" { xfail *-*-* } } } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loadpre5.c b/gcc/testsuite/gcc.dg/tree-ssa/loadpre5.c
new file mode 100644
index 0000000..37314eb
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loadpre5.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+int p;
+int r;
+int a(void)
+{
+  return p;
+}
+int main(int argc)
+{
+  int q;
+  q = a();
+
+  /* We should be able to move the call to a into the if path.
+     in a perfect world, we'd actually decide that it can't touch
+     r, and not recompute it at all!.  */
+  if (argc)
+    r = 9;
+  return q + a();
+}
+/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "pre"} } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loadpre6.c b/gcc/testsuite/gcc.dg/tree-ssa/loadpre6.c
new file mode 100644
index 0000000..5283f20
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loadpre6.c
@@ -0,0 +1,74 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+
+union tree_node;
+typedef union tree_node *tree;
+
+struct tree_common
+{
+  tree chain;
+};
+
+struct tree_list
+{
+  struct tree_common common;
+  tree value;
+};
+
+union tree_node
+
+{
+  struct tree_common common;
+  struct tree_list list;
+};
+
+extern void abort (void) __attribute__((noreturn));
+
+void __attribute__((noinline))
+foo (void)
+{
+  abort ();
+}
+
+void __attribute__((noinline))
+remove_useless_vars (tree *unexpanded_var_list, int dump_file)
+{
+  tree var, *cell;
+  int c = 0;
+  for (cell = unexpanded_var_list; *cell; )
+    {
+      var = (*cell)->list.value;
+      if (var)
+        {
+          if (dump_file)
+            foo ();
+
+          *cell = ((*cell)->common.chain);
+          continue;
+        }
+
+      cell = &((*cell)->common.chain);
+    }
+}
+extern void *malloc (int) __attribute__ ((malloc));
+
+int
+main (void)
+{
+  int i;
+  tree unexpanded_var_list, last = (tree) 0;
+
+  for (i = 0; i < 2; i++)
+    {
+      unexpanded_var_list = malloc (sizeof (struct tree_list));
+      unexpanded_var_list->list.value = (tree) (long unsigned) (i & 1);
+      unexpanded_var_list->common.chain = last;
+      last = unexpanded_var_list;
+    }
+
+  remove_useless_vars (&unexpanded_var_list, 0);
+  return 0;
+}
+/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "pre" } } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
+
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loadpre7.c b/gcc/testsuite/gcc.dg/tree-ssa/loadpre7.c
new file mode 100644
index 0000000..7cd6838
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loadpre7.c
@@ -0,0 +1,17 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+/* We can't eliminate the *p load here in any sane way, as eshup8 may 
+   change it.  */
+void
+enormlz (x)
+     unsigned short x[];
+{
+  register unsigned short *p;
+  p = &x[2];
+  while ((*p & 0xff00) == 0)
+    {
+      eshup8 (x);
+    }
+}
+/* { dg-final { scan-tree-dump-times "Eliminated: 0" 1 "pre"} } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loadpre8.c b/gcc/testsuite/gcc.dg/tree-ssa/loadpre8.c
new file mode 100644
index 0000000..86cb1e4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loadpre8.c
@@ -0,0 +1,97 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+typedef union tree_node *tree;
+struct tree_common
+{
+  tree chain;
+}
+VEC_constructor_elt_base;
+struct tree_ssa_name
+{
+  tree var;
+};
+union tree_node
+{
+  struct tree_common common;
+  struct tree_ssa_name ssa_name;
+};
+struct edge_def
+{
+  struct basic_block_def *dest;
+};
+typedef struct edge_def *edge;
+typedef struct VEC_edge_base
+{
+}
+VEC_edge_base;
+edge
+VEC_edge_base_index (const VEC_edge_base * vec_, unsigned ix_)
+{
+}
+typedef struct VEC_edge_gc
+{
+  VEC_edge_base base;
+}
+VEC_edge_gc;
+struct basic_block_def
+{
+  VEC_edge_gc *succs;
+};
+typedef struct basic_block_def *basic_block;
+typedef struct
+{
+  unsigned index;
+  VEC_edge_gc **container;
+}
+edge_iterator;
+__inline__ VEC_edge_gc *
+ei_container (edge_iterator i)
+{
+  return *i.container;
+}
+__inline__ edge_iterator
+ei_start_1 (VEC_edge_gc ** ev)
+{
+  edge_iterator i;
+  i.container = ev;
+  return i;
+}
+ei_next (edge_iterator * i)
+{
+}
+static __inline__ edge
+ei_edge (edge_iterator i)
+{
+  return  (edge) (VEC_edge_base_index ((((ei_container (i))) ? &((ei_container (i)))->base : 0), (i.index)));
+}
+static __inline__ unsigned char
+ei_cond (edge_iterator ei, edge * p)
+{
+  *p = ei_edge (ei);
+}
+typedef tree *def_operand_p;
+extern tree *get_phi_result_ptr (tree);
+static __inline__ tree
+get_def_from_ptr (def_operand_p def)
+{
+}
+tree
+phi_nodes (basic_block bb)
+{
+}
+
+/* We can eliminate a load of the SRA'd variable edge_iterator.container */
+rewrite_add_phi_arguments (basic_block bb)
+{
+  edge e;
+  edge_iterator ei;
+  for ((ei) = ei_start_1 (&((bb->succs))); ei_cond ((ei), &(e));
+       ei_next (&(ei)))
+    {
+      tree phi;
+      for (phi = phi_nodes (e->dest); phi; phi = (((phi))->common.chain))
+	  get_reaching_def ((get_def_from_ptr (get_phi_result_ptr (phi)))->ssa_name.var);
+    }
+}
+/* { dg-final { scan-tree-dump-times "Eliminated: 1" 1 "pre"} } */
+/* { dg-final { cleanup-tree-dump "pre" } } */