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]

[tree-ssa] verify_stmts and verify_ssa


Hi,
here is version of checking code that I think is good enought for SSA branch.
With the aliasing and addressof fixes I sent into queue, I can bootstrap with
verify_stmts enabled (so we don't do any invalid sharing and all produced
statements are gimple).  These bugs ineed solved the tail recursion issues too,
so at least the checker seems to be usefull.  verify_ssa is currently passing
only up to SRA pass.  SRA introduces dead definitions and SSAPRE introduces
uses not dominated by definitions.  THese bugs don't seem to be completely
trivial to fix, so hope this can be done later.  Currently we don't call the checkers
at all.

I would propose to call it in tree-optimize.c after each pass that is now known
to preserve the invariants correctly.
OK?

Fell free to suggest new checks.  On other machine I already added code
verifying that uses/defs are valid gimple operands, while vuses/vdefs
are not.  I am not sure what other parts of variable annotations can be
machine verified.  For instantce default definition for variables
probably can, but I am not sure how...

Also verify_ssa seems to be bit slow.  The bottleneck is
get_stmt_operands.  Any idea how to get it faster?  Or are the
annotations required to be up to date all the time?

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 01:32:29 -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)
--- 2779,2784 ----
*************** 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))
--- 2786,2791 ----
*************** tree_verify_flow_info (void)
*** 3027,3032 ****
--- 2993,3362 ----
    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);
+       if (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) == STRING_CST
+ 	  || TREE_CODE (x) == LABEL_DECL
+ 	  || TREE_CODE (x) == FUNCTION_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;
+   if ((TREE_CODE (t) == ARRAY_REF
+        || TREE_CODE (t) == COMPONENT_REF)
+       && DECL_P (TREE_OPERAND (t, 0))
+       && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
+     return true;
+   if ((TREE_CODE (t) == REALPART_EXPR
+        || TREE_CODE (t) == INDIRECT_REF
+        || TREE_CODE (t) == IMAGPART_EXPR)
+       && is_gimple_min_invariant (TREE_OPERAND (t, 0)))
+     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.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 01:32:29 -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: 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 01:32:29 -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-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 01:32:29 -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 Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]