This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [tree-ssa] verify_stmts and verify_ssa


> 
> Again a while loop.  Here you have to be more clever though,
> since you've got to check is_gimple_min_invariant for each
> ARRAY_REF index.  Also, is_gimple_min_invariant is wrong to
> apply to the FIELD_DECL of a COMPONENT_REF; I'm surprised
> nothing went wrong.
Apparently just because the whole effect function has is to decide on
sharing and we never share these.
I am attaching updated patch.  OK now?
The situation with tree is still the same - ADDRESSOF tests breaks but
are fixed by my two patch, SSAPRE breaks dominance, SRA keep
uninitialized SSA names for reasons I can't understand.  Apparently the
SSA is re-computed for given variable but the old PHI nodes remains when
the variable is dead now.

Honza

2003-11-21  Jan Hubicka  <jh@suse.cz>
	* tree-cfg (verify_flow_info): Break out PHI checking to ...
	(verify_ssa): ... here; do more SSA checking.
	(verify_stmt, verify_stmts): New global functions.
	(verify_addr_expr, verify_node_sharing, tree_node_shared_p, verify_def,
	verify_use): New static function.
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.221
diff -c -3 -p -r1.1.4.221 tree-cfg.c
*** tree-cfg.c	20 Nov 2003 20:54:39 -0000	1.1.4.221
--- tree-cfg.c	21 Nov 2003 11:48:08 -0000
*************** tree_verify_flow_info (void)
*** 2774,2781 ****
      {
        edge e;
        bool found_ctrl_stmt = false;
-       tree phi;
-       int i;
  
        for (e = bb->pred; e; e = e->pred_next)
  	if (e->aux)
--- 2774,2779 ----
*************** tree_verify_flow_info (void)
*** 2783,2825 ****
  	    error ("Aux pointer initialized for edge %d->%d\n", e->src->index, e->dest->index);
  	    err = 1;
  	  }
-       phi = phi_nodes (bb);
-       for ( ; phi; phi = TREE_CHAIN (phi))
- 	{
- 	  int phi_num_args = PHI_NUM_ARGS (phi);
- 
- 	  for (e = bb->pred; e; e = e->pred_next)
- 	    e->aux = (void *)1;
- 	  for (i = 0; i < phi_num_args; i++)
- 	    {
- 	      e = PHI_ARG_EDGE (phi, i);
- 	      if (e->dest != bb)
- 		{
- 		  error ("Phi node for edge %d->%d in %d\n", e->src->index, e->dest->index, bb->index);
- 		  err = 1;
- 		}
- 	      if (e->aux == (void *)0)
- 		{
- 		  error ("Phi node for dead edge %d->%d\n", e->src->index, e->dest->index);
- 		  err = 1;
- 		}
- 	      if (e->aux == (void *)2)
- 		{
- 		  error ("Phi node duplicated for edge %d->%d\n", e->src->index, e->dest->index);
- 		  err = 1;
- 		}
- 	      e->aux = (void *)2;
- 	    }
- 	  for (e = bb->pred; e; e = e->pred_next)
- 	    {
- 	      if (e->aux != (void *)2)
- 		{
- 		  error ("Edge %d->%d miss phi node entry\n", e->src->index, e->dest->index);
- 		  err = 1;
- 		}
- 	      e->aux = (void *)0;
- 	    }
- 	}
  
        /* Skip labels on the start of basic block.  */
        for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
--- 2781,2786 ----
*************** tree_verify_flow_info (void)
*** 3027,3032 ****
--- 2988,3354 ----
    return err;
  }
  
+ /* Callback for walk_tree, check that all elements with address taken are
+    properly noticed as such.  */
+ 
+ static tree
+ verify_addr_expr (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
+ 		  void *data ATTRIBUTE_UNUSED)
+ {
+   if (TREE_CODE (*tp) == ADDR_EXPR)
+     {
+       tree x = TREE_OPERAND (*tp, 0);
+       while (TREE_CODE (x) == ARRAY_REF
+ 	     || TREE_CODE (x) == COMPONENT_REF
+ 	     || TREE_CODE (x) == REALPART_EXPR
+ 	     || TREE_CODE (x) == IMAGPART_EXPR)
+ 	x = TREE_OPERAND (x, 0);
+       if (TREE_CODE (x) != VAR_DECL && TREE_CODE (x) != PARM_DECL)
+ 	return NULL;
+       if (!TREE_ADDRESSABLE (x))
+         return x;
+     }
+   return NULL;
+ }
+ 
+ /* Verify the STMT, return true if STMT is missformed.
+    Always keep global so it can be called via GDB. 
+ 
+    TODO: Implement type checking.  */
+ bool
+ verify_stmt (tree stmt)
+ {
+   tree addr;
+ 
+   if (!is_gimple_stmt (stmt))
+     {
+       debug_generic_stmt (stmt);
+       error ("Is not valid gimple statement.");
+       return true;
+     }
+   addr = walk_tree (&stmt, verify_addr_expr, NULL, NULL);
+   if (addr)
+     {
+       debug_generic_stmt (addr);
+       error ("Address taken, but ADDRESABLE bit not set");
+       return true;
+     }
+   return false;
+ }
+ 
+ /* Return true when the T can be shared.  */
+ static bool
+ tree_node_shared_p (tree t)
+ {
+   if (TYPE_P (t) || DECL_P (t)
+       || is_gimple_min_invariant (t)
+       || TREE_CODE (t) == SSA_NAME)
+     return true;
+   while (((TREE_CODE (t) == ARRAY_REF
+           || TREE_CODE (t) == COMPONENT_REF)
+           && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
+ 	 || (TREE_CODE (t) == REALPART_EXPR
+ 	     || TREE_CODE (t) == INDIRECT_REF
+ 	     || TREE_CODE (t) == IMAGPART_EXPR))
+     t = TREE_OPERAND (t, 0);
+   if (DECL_P (t))
+     return true;
+   return false;
+ }
+ 
+ /* Called via walk_trees.  Verify tree sharing.  */
+ static tree
+ verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
+ {
+   htab_t htab = (htab_t) data;
+   void **slot;
+ 
+   if (tree_node_shared_p (*tp))
+     {
+       *walk_subtrees = false;
+       return NULL;
+     }
+   slot = htab_find_slot (htab, *tp, INSERT);
+   if (*slot)
+     return *slot;
+   *slot = *tp;
+   return NULL;
+ }
+ 
+ 
+ /* Verify GIMPLE stmt chain.  */
+ void
+ verify_stmts (void)
+ {
+   basic_block bb;
+   block_stmt_iterator bsi;
+   bool err = false;
+   htab_t htab;
+   tree addr;
+ 
+   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
+ 
+   FOR_EACH_BB (bb)
+     {
+       tree phi;
+       int i;
+ 
+       phi = phi_nodes (bb);
+       for (; phi; phi = TREE_CHAIN (phi))
+ 	{
+ 	  int phi_num_args = PHI_NUM_ARGS (phi);
+ 
+ 	  for (i = 0; i < phi_num_args; i++)
+ 	    {
+ 	      tree t = PHI_ARG_DEF (phi, i);
+ 	      tree addr;
+ 
+ 	      /* Addressable variables do have SSA_NAMEs but they
+ 	         are not considered gimple values.  */
+ 	      if (TREE_CODE (t) != SSA_NAME
+ 		  && TREE_CODE (t) != FUNCTION_DECL
+ 		  && !is_gimple_val (t))
+ 		{
+ 		  debug_generic_stmt (phi);
+ 		  debug_generic_stmt (t);
+ 		  error ("PHI def is not GIMPLE value");
+ 		  err |= true;
+ 		}
+ 	      addr = walk_tree (&t, verify_addr_expr, NULL, NULL);
+ 	      if (addr)
+ 		{
+ 		  debug_generic_stmt (addr);
+ 		  error ("Address taken, but ADDRESABLE bit not set");
+ 		  err |= true;
+ 		}
+ 	      addr = walk_tree (&t, verify_node_sharing, htab, NULL);
+ 	      if (addr)
+ 		{
+ 		  debug_generic_stmt (phi);
+ 		  debug_generic_stmt (addr);
+ 		  error ("Wrong sharing of tree nodes");
+ 		  err |= true;
+ 		}
+ 	    }
+ 	}
+       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ 	{
+ 	  tree stmt = bsi_stmt (bsi);
+ 	  err |= verify_stmt (stmt);
+ 	  addr = walk_tree (&stmt, verify_node_sharing, htab, NULL);
+ 	  if (addr)
+ 	    {
+ 	      debug_generic_stmt (stmt);
+ 	      debug_generic_stmt (addr);
+ 	      error ("Wrong sharing of tree nodes");
+ 	      err |= true;
+ 	    }
+ 	}
+     }
+   if (err)
+     internal_error ("verify_stmts failed.");
+   htab_delete (htab);
+ }
+ 
+ /* Used by verify_ssa.  Do sanity checking on OP defined by SSA in block BB.  */
+ static bool
+ verify_def (basic_block bb, basic_block * definition_block, tree op,
+     	    tree stmt)
+ {
+   bool err = false;
+   if (definition_block[SSA_NAME_VERSION (op)])
+     {
+       debug_generic_stmt (stmt);
+       debug_generic_stmt (op);
+       error ("SSA_NAME set in BB %i and %i",
+ 	     definition_block[SSA_NAME_VERSION (op)]->index, bb->index);
+       err = 1;
+     }
+   definition_block[SSA_NAME_VERSION (op)] = bb;
+   if (SSA_NAME_DEF_STMT (op) != stmt)
+     {
+       debug_generic_stmt (stmt);
+       error ("SSA_NAME_DEF_STMT wrong");
+       err = 1;
+     }
+   return err;
+ }
+ 
+ /* Used by verify_ssa.  Do sanity checking on OP used by SSA in block BB.  */
+ static bool
+ verify_use (basic_block bb, basic_block * definition_block, tree op,
+ 	    tree stmt, dominance_info idom, bool abnormal)
+ {
+   basic_block dbb = definition_block [SSA_NAME_VERSION (op)];
+   bool err = false;
+ 
+   if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (op)))
+     ;
+   else if (!dbb)
+     {
+       debug_generic_stmt (stmt);
+       debug_generic_stmt (op);
+       error ("Definition is missing");
+       err = 1;
+     }
+   else if (bb != dbb && !dominated_by_p (idom, bb, dbb))
+     {
+       debug_generic_stmt (stmt);
+       debug_generic_stmt (op);
+       error ("Definition in bb %i does not dominate use in bb %i",
+ 	     dbb->index, bb->index);
+       err = 1;
+     }
+   if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op) && abnormal)
+     {
+       debug_generic_stmt (stmt);
+       error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI shall be set");
+       err = 1;
+     }
+   return err;
+ }
+ /* Verify common invariants about SSA graph.
+    TODO: verify the variable annotations.  */
+ void
+ verify_ssa (void)
+ {
+   int err = 0;
+   basic_block bb;
+   dominance_info idom;
+   basic_block *definition_block = xcalloc (highest_ssa_version,
+ 		  			   sizeof (basic_block));
+ 
+   idom = calculate_dominance_info (CDI_DOMINATORS);
+   FOR_EACH_BB (bb)
+   {
+     tree phi;
+     block_stmt_iterator bsi;
+ 
+     phi = phi_nodes (bb);
+     for (; phi; phi = TREE_CHAIN (phi))
+       err |= verify_def (bb, definition_block, PHI_RESULT (phi),
+ 	  		 phi);
+     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+       {
+ 	tree stmt = bsi_stmt (bsi);
+ 	unsigned int j;
+ 	varray_type vdefs;
+ 	varray_type defs;
+ 
+ 	get_stmt_operands (stmt);
+ 	vdefs = vdef_ops (stmt_ann (stmt));
+ 
+ 	for (j = 0; vdefs && j < VARRAY_ACTIVE_SIZE (vdefs); j++)
+ 	  {
+ 	    tree op = VDEF_RESULT (VARRAY_TREE (vdefs, j));
+ 	    err |= verify_def (bb, definition_block, op, stmt);
+ 	  }
+ 	defs = def_ops (stmt_ann (stmt));
+ 	
+ 	for (j = 0; defs && j < VARRAY_ACTIVE_SIZE (defs); j++)
+ 	  {
+             tree op = *VARRAY_TREE_PTR (defs, j);
+ 	    err |= verify_def (bb, definition_block, op, stmt);
+ 	  }
+       }
+   }
+   FOR_EACH_BB (bb)
+   {
+     edge e;
+     tree phi;
+     block_stmt_iterator bsi;
+     int i;
+ 
+     for (e = bb->pred; e; e = e->pred_next)
+       {
+ 	if (e->aux)
+ 	  {
+ 	    error ("Aux pointer initialized for edge %d->%d\n", e->src->index,
+ 		   e->dest->index);
+ 	    err = 1;
+ 	  }
+       }
+     phi = phi_nodes (bb);
+     for (; phi; phi = TREE_CHAIN (phi))
+       {
+ 	int phi_num_args = PHI_NUM_ARGS (phi);
+ 	for (e = bb->pred; e; e = e->pred_next)
+ 	  e->aux = (void *) 1;
+ 	for (i = 0; i < phi_num_args; i++)
+ 	  {
+ 	    tree op = PHI_ARG_DEF (phi, i);
+ 
+ 	    e = PHI_ARG_EDGE (phi, i);
+ 	    if (!is_gimple_min_invariant (op))
+ 	      err |= verify_use (e->src, definition_block, op, phi, idom,
+ 			         e->flags & EDGE_ABNORMAL);
+ 	    if (e->dest != bb)
+ 	      {
+ 		error ("Phi node for edge %d->%d in %d\n", e->src->index,
+ 		       e->dest->index, bb->index);
+ 		err = 1;
+ 	      }
+ 	    if (e->aux == (void *) 0)
+ 	      {
+ 		error ("Phi node for dead edge %d->%d\n", e->src->index,
+ 		       e->dest->index);
+ 		err = 1;
+ 	      }
+ 	    if (e->aux == (void *) 2)
+ 	      {
+ 		error ("Phi node duplicated for edge %d->%d\n", e->src->index,
+ 		       e->dest->index);
+ 		err = 1;
+ 	      }
+ 	    e->aux = (void *) 2;
+ 
+ 	  }
+ 	for (e = bb->pred; e; e = e->pred_next)
+ 	  {
+ 	    if (e->aux != (void *) 2)
+ 	      {
+ 		error ("Edge %d->%d miss phi node entry\n", e->src->index,
+ 		       e->dest->index);
+ 		err = 1;
+ 	      }
+ 	    e->aux = (void *) 0;
+ 	  }
+       }
+ 
+     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+       {
+ 	tree stmt = bsi_stmt (bsi);
+ 	unsigned int j;
+ 	varray_type vuses;
+ 	varray_type uses;
+ 
+ 	get_stmt_operands (stmt);
+ 	vuses = vuse_ops (stmt_ann (stmt));
+ 
+ 	/* For each VDEF on the original statement, we want to create a
+ 	   VUSE of the VDEF result on the new statement.  */
+ 	for (j = 0; vuses && j < VARRAY_ACTIVE_SIZE (vuses); j++)
+ 	  {
+             tree op = VARRAY_TREE (vuses, j);
+ 
+ 	    err |= verify_use (bb, definition_block, op, stmt, idom, false);
+ 	  }
+ 	uses = use_ops (stmt_ann (stmt));
+ 	
+ 	for (j = 0; uses && j < VARRAY_ACTIVE_SIZE (uses); j++)
+ 	  {
+             tree op = *VARRAY_TREE_PTR (uses, j);
+ 
+ 	    err |= verify_use (bb, definition_block, op, stmt, idom, false);
+ 	  }
+       }
+   }
+ 
+   free_dominance_info (idom);
+   free (definition_block);
+   if (err)
+     internal_error ("verify_ssa failed.");
+ }
  
  /* Split BB into entry part and rest; if REDIRECT_LATCH, redirect edges
     marked as latch into entry part, analogically for REDIRECT_NONLATCH.
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.158
diff -c -3 -p -r1.1.4.158 tree-flow.h
*** tree-flow.h	20 Nov 2003 20:54:39 -0000	1.1.4.158
--- tree-flow.h	21 Nov 2003 11:48:08 -0000
*************** extern void bsi_commit_edge_inserts (boo
*** 448,453 ****
--- 448,456 ----
  extern void bsi_insert_on_edge_immediate (edge, tree);
  extern void notice_special_calls (tree);
  extern void clear_special_calls (void);
+ extern bool verify_stmt (tree);
+ extern void verify_stmts (void);
+ extern void verify_ssa (void);
  
  /* In tree-pretty-print.c.  */
  extern void dump_generic_bb (FILE *, basic_block, int, int);
Index: tree-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-inline.h,v
retrieving revision 1.4.2.4
diff -c -3 -p -r1.4.2.4 tree-inline.h
*** tree-inline.h	25 Oct 2003 19:42:52 -0000	1.4.2.4
--- tree-inline.h	21 Nov 2003 11:48:08 -0000
*************** Boston, MA 02111-1307, USA.  */
*** 26,35 ****
  
  void optimize_inline_calls (tree);
  bool tree_inlinable_function_p (tree);
- tree walk_tree (tree*, walk_tree_fn, void*, void*);
- tree walk_tree_without_duplicates (tree*, walk_tree_fn, void*);
  tree copy_tree_r (tree*, int*, void*);
  void clone_body (tree, tree, void*);
  void remap_save_expr (tree*, void*, tree, int*);
  int estimate_num_insns (tree expr);
  
--- 26,33 ----
  
  void optimize_inline_calls (tree);
  bool tree_inlinable_function_p (tree);
  tree copy_tree_r (tree*, int*, void*);
  void clone_body (tree, tree, void*);
  void remap_save_expr (tree*, void*, tree, int*);
  int estimate_num_insns (tree expr);
  
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.342.2.135
diff -c -3 -p -r1.342.2.135 tree.h
*** tree.h	20 Nov 2003 20:54:39 -0000	1.342.2.135
--- tree.h	21 Nov 2003 11:48:09 -0000
*************** extern void dwarf2out_return_reg (const 
*** 3531,3536 ****
--- 3531,3538 ----
  /* The type of a callback function for walking over tree structure.  */
  
  typedef tree (*walk_tree_fn) (tree *, int *, void *);
+ tree walk_tree (tree*, walk_tree_fn, void*, void*);
+ tree walk_tree_without_duplicates (tree*, walk_tree_fn, void*);
  
  /* In tree-dump.c */
  


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]