Re: [PATCH]: Structure aliasing, take 2

[Diego Novillo <dnovillo at redhat dot com>]

On Tue, May 31, 2005 at 06:10:12PM -0400, Daniel Berlin wrote:

> Okay for mainline?
> 
Yes.

I found it easier to edit tree-ssa-structalias.c to give
you feedback.  The changes are minor, as your implementation is
pretty clean (thanks).  Mostly clarifying comments and some
spacing.  Grep for 'FIXME'.

Unless you are working on it now, I will start removing the old
analyzer.  That'll help identify bugs in the new analyzer.


Diego.


--- tree-ssa-structalias.c	2005-06-07 16:13:05.809369862 -0400
+++ tree-ssa-structalias.c.new	2005-06-07 16:11:53.308181560 -0400
@@ -110,8 +110,8 @@ Foundation, Inc., 59 Temple Place, Suite
    bar -> id 3, size 32, offset 0, fullsize 32, next NULL
 
    
-In order to solve the system of set constraints, the following is
-done:
+  In order to solve the system of set constraints, the following is
+  done:
 
   1. Each constraint variable x has a solution set associated with it,
   Sol(x).
@@ -143,23 +143,22 @@ done:
   8. The process of walking the graph is iterated until no solution
   sets change.
 
+  Prior to walking the graph in steps 6 and 7, We perform static
+  cycle elimination on the constraint graph, as well 
+  as off-line variable substitution.
+  
+  TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
+  on and turned into anything), but isn't.  You can just see what offset
+  inside the pointed-to struct it's going to access.
+  
+  TODO: Constant bounded arrays can be handled as if they were structs of the
+  same number of elements. 
 
-   Prior to walking the graph in steps 6 and 7, We perform static
-   cycle elimination on the constraint graph, as well 
-   as off-line variable substitution.
-   
-   TODO: Adding offsets to pointer-to-structures can be handled (IE not punted
-   on and turned into anything), but isn't.  You can just see what offset
-   inside the pointed-to struct it's going to access.
-   
-   TODO: Constant bounded arrays can be handled as if they were structs of the
-   same number of elements. 
-
-   TODO: Modeling heap and incoming pointers becomes much better if we
-   add fields to them as we discover them, which we could do.
+  TODO: Modeling heap and incoming pointers becomes much better if we
+  add fields to them as we discover them, which we could do.
 
-   TODO: We could handle unions, but to be honest, it's probably not
-   worth the pain or slowdown.  */
+  TODO: We could handle unions, but to be honest, it's probably not
+  worth the pain or slowdown.  */
 
 static bool use_field_sensitive = true;
 static unsigned int create_variable_info_for (tree, const char *);
@@ -243,6 +242,7 @@ DEF_VEC_P(varinfo_t);
 
 DEF_VEC_ALLOC_P(varinfo_t, gc);
 
+/* FIXME.  Description?  */
 static VEC(varinfo_t,gc) *varmap;
 #define get_varinfo(n) VEC_index(varinfo_t, varmap, n)
 
@@ -270,6 +270,7 @@ static unsigned int integer_id;
 
 /* Return a new variable info structure consisting for a variable
    named NAME, ending at id END, and using constraint graph node
+               ^^^^^^^^^^^^^^^^ FIXME: Hmm?
    NODE.  */
 
 static varinfo_t
@@ -988,6 +989,7 @@ static sbitmap changed;
 DEF_VEC_I(uint);
 DEF_VEC_ALLOC_I(uint,heap);
 
+
 /* Strongly Connected Component visitation info.  */
 
 struct scc_info
@@ -1002,6 +1004,7 @@ struct scc_info
 
 
 /* Recursive routine to find strongly connected components in GRAPH.
+   FIXME: Document SI and N.
    
    This is Tarjan's strongly connected component finding algorithm, as
    modified by Nuutila to keep only non-root nodes on the stack.  
@@ -1035,9 +1038,7 @@ scc_visit (constraint_graph_t graph, str
 	      unsigned int t = get_varinfo (w)->node;
 	      unsigned int nnode = get_varinfo (n)->node;
 	      if (si->visited_index[t] < si->visited_index[nnode])
-		{
-		  get_varinfo (n)->node = t;
-		}
+		get_varinfo (n)->node = t;
 	    }
 	}
     }
@@ -1061,6 +1062,7 @@ scc_visit (constraint_graph_t graph, str
     VEC_safe_push (uint, heap, si->scc_stack, n);
 }
 
+
 /* Collapse two variables into one variable.  */
 
 static void
@@ -1090,7 +1092,8 @@ collapse_nodes (constraint_graph_t graph
 }
 
 
-/* Unify nodes that we have found to be part of a cycle.  */
+/* Unify nodes in GRAPH that we have found to be part of a cycle.
+   FIXME: Document SI and UPDATE_CHANGED.  */
 
 static void
 process_unification_queue (constraint_graph_t graph, struct scc_info *si,
@@ -1122,9 +1125,7 @@ process_unification_queue (constraint_gr
 	Merge tmp into solution for rep, marking rep changed if this
 	changed rep's solution.
 	
-	Delete any 0 weighted self-edges we now have for rep.
-  */
-
+	Delete any 0 weighted self-edges we now have for rep.  */
   while (i != VEC_length (uint, si->unification_queue))
     {
       unsigned int tounify = VEC_index (uint, si->unification_queue, i);
@@ -1190,6 +1191,7 @@ process_unification_queue (constraint_gr
   BITMAP_FREE (tmp);
 }
 
+
 /* Information needed to compute the topological ordering of a graph.  */
 
 struct topo_info
@@ -1201,6 +1203,7 @@ struct topo_info
   VEC(uint,heap) *topo_order;
 };
 
+
 /* Initialize and return a topological info structure.  */
 
 static struct topo_info *
@@ -1214,6 +1217,7 @@ init_topo_info (void)
   return ti;
 }
 
+
 /* Free the topological sort info pointed to by TI.  */
 
 static void
@@ -1555,6 +1559,7 @@ perform_var_substitution (constraint_gra
 	      break;
 	    }
 	  w = get_varinfo (ce->dest)->node;
+
 	  /* We can't eliminate the node if one of the predecessors is
 	     part of a different strongly connected component.  */
 	  if (!okay_to_elim)
@@ -1567,6 +1572,7 @@ perform_var_substitution (constraint_gra
 	      okay_to_elim = false;
 	      break;
 	    }
+
 	  /* Theorem 4 in Rountev and Chandra: If i is a direct node,
 	     then Solution(i) is a subset of Solution (w), where w is a
 	     predecessor in the graph.  
@@ -1584,6 +1590,7 @@ perform_var_substitution (constraint_gra
 	    }
 	  BITMAP_FREE (tmp);
 	}
+
       /* See if the root is different than the original node. 
 	 If so, we've found an equivalence.  */
       if (root != get_varinfo (i)->node && okay_to_elim)
@@ -1598,10 +1605,13 @@ perform_var_substitution (constraint_gra
 	  stats.collapsed_vars++;
 	}
     }
+
   free_topo_info (ti);
 }
 
-/* Solve the constraint graph GRAPH using our worklist solver.  */
+
+/* Solve the constraint graph GRAPH using our worklist solver.
+   FIXME: Add some high-level description.  */
 
 static void
 solve_graph (constraint_graph_t graph)
@@ -1629,14 +1639,17 @@ solve_graph (constraint_graph_t graph)
       
       if (edge_added)
 	{
-	  /* We already did cycle elimination once, when we did variable
-	     substitution, so we don't need it again for the first iteration.  */
+	  /* We already did cycle elimination once, when we did
+	     variable substitution, so we don't need it again for the
+	     first iteration.  */
 	  if (stats.iterations > 1)
 	    find_and_collapse_graph_cycles (graph, true);
 	  
 	  edge_added = false;
 	}
+
       compute_topo_order (graph, ti);
+
       while (VEC_length (uint, ti->topo_order) != 0)
 	{
 	  i = VEC_pop (uint, ti->topo_order);
@@ -1690,6 +1703,7 @@ solve_graph (constraint_graph_t graph)
       free_topo_info (ti);
       bitmap_obstack_release (&iteration_obstack);
     }
+
   sbitmap_free (changed);
 }
 
@@ -1742,7 +1756,7 @@ insert_id_for_tree (tree t, int id)
   *slot = (void *)new_pair;
 }
 
-/* Find the variable id for tree T in the hashtable.  If T does not
+/* Find the variable id for tree T in ID_FOR_TREE.  If T does not
    exist in the hash table, return false, otherwise, return true and
    set *ID to the id we found.  */
 
@@ -1907,10 +1921,11 @@ static unsigned HOST_WIDE_INT
 bitpos_of_field (const tree fdecl)
 {
   return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8) 
-    + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
+         + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1);
 }
 
-/* Given a COMPONENT_REF, return the constraint_expr for it.  */
+
+/* Given a COMPONENT_REF T, return the constraint_expr for it.  */
 
 static struct constraint_expr
 get_constraint_for_component_ref (tree t)
@@ -1930,7 +1945,6 @@ get_constraint_for_component_ref (tree t
 
   /* Some people like to do cute things like take the address of
      &0->a.b */
-
   forzero = t;
   while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero))
       forzero = TREE_OPERAND (forzero, 0);
@@ -1976,12 +1990,14 @@ get_constraint_for_component_ref (tree t
       else
 	if (dump_file && (dump_flags & TDF_DETAILS))
 	  fprintf (dump_file, "Access to past the end of variable, ignoring\n");
+
       result.offset = 0;
     }
   
   return result;
 }
 
+
 /* Dereference the constraint expression CONS, and return the result.
    DEREF (ADDRESSOF) = SCALAR
    DEREF (SCALAR) = DEREF
@@ -2012,22 +2028,22 @@ do_deref (struct constraint_expr cons)
   gcc_unreachable ();
 }
 
-/* Given a TREE, return the constraint expression for it.  */
+
+/* Given a tree T, return the constraint expression for it.  */
 
 static struct constraint_expr
 get_constraint_for (tree t)
 {
   struct constraint_expr temp;
 
-  /* x = integer is all glommed to a single variable, which doesn't point to
-     anything by itself.
-     That is, of course, unless it is an integer constant being treated as a
-     pointer, in which case, we will return that this is really the addressof
-     anything.  This happens below, since it will fall into the default case.
-     
-     The only case we know something about an integer treated like a pointer
-     is when it is the NULL pointer, and then we just say it points to NULL.
-     */
+  /* x = integer is all glommed to a single variable, which doesn't
+     point to anything by itself.  That is, of course, unless it is an
+     integer constant being treated as a pointer, in which case, we
+     will return that this is really the addressof anything.  This
+     happens below, since it will fall into the default case. The only
+     case we know something about an integer treated like a pointer is
+     when it is the NULL pointer, and then we just say it points to
+     NULL.  */
   if (TREE_CODE (t) == INTEGER_CST
       && !POINTER_TYPE_P (TREE_TYPE (t)))
     {
@@ -2065,9 +2081,7 @@ get_constraint_for (tree t)
 	    
 	    /* XXX: In interprocedural mode, if we didn't have the
 	       body, we would need to do *each pointer argument =
-	       &ANYTHING added.
-	    */
-
+	       &ANYTHING added.  */
 	    if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
 	      {
 		tree heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
@@ -2241,10 +2255,10 @@ do_rhs_deref_structure_copy (const struc
     }
 }
 
-/* Handle the structure copy case where we have a  structure copy between a
-   aggregate on the RHS and a dereference of a pointer on the LHS
-   that is of SIZE (in bits) 
-  
+/* Handle the structure copy case where we have a structure copy
+   between a aggregate on the RHS and a dereference of a pointer on
+   the LHS that is of SIZE (in bits) 
+
    For each field of the rhs variable (rhsfield)
        lhs.offset = rhsfield->offset
        add the constraint lhs = rhsfield
@@ -2280,6 +2294,7 @@ do_lhs_deref_structure_copy (const struc
     }
 }
 
+
 /* Handle aggregate copies by expanding into copies of the respective
    fields of the structures.  */
 
@@ -2321,7 +2336,6 @@ do_structure_copy (tree lhsop, tree rhso
     }
   else
     {
-      
       if (rhs.type == SCALAR && lhs.type == SCALAR)  
 	do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize));
       else if (lhs.type != DEREF && rhs.type == DEREF)
@@ -2345,6 +2359,7 @@ do_structure_copy (tree lhsop, tree rhso
     }
 }
 
+
 /* Return true if REF, a COMPONENT_REF, has an INDIRECT_REF somewhere
    in it.  */
 
@@ -2360,6 +2375,7 @@ ref_contains_indirect_ref (tree ref)
   return false;
 }
 
+
 /*  Tree walker that is the heart of the aliasing infrastructure.
     TP is a pointer to the current tree.
     WALK_SUBTREES specifies whether to continue traversing subtrees or
@@ -2379,6 +2395,7 @@ find_func_aliases (tree t)
     case PHI_NODE:
       {
 	int i;
+
 	/* Only care about pointers and structures containing
 	   pointers.  */
 	if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
@@ -2393,11 +2410,13 @@ find_func_aliases (tree t)
 	  }
       }
       break;
+
     case MODIFY_EXPR:
       {
 	tree lhsop = TREE_OPERAND (t, 0);
 	tree rhsop = TREE_OPERAND (t, 1);
 	int i;	
+
 	if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop)) 
 	    && AGGREGATE_TYPE_P (TREE_TYPE (rhsop)))
 	  {
@@ -2405,14 +2424,14 @@ find_func_aliases (tree t)
 	  }
 	else
 	  {
-	    /* Only care about operations with pointers, structures containing
-	       pointers, dereferences, and call expressions*/
+	    /* Only care about operations with pointers, structures
+	       containing pointers, dereferences, and call
+	       expressions.  */
 	    if (POINTER_TYPE_P (TREE_TYPE (lhsop))
 		|| AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
 		|| ref_contains_indirect_ref (lhsop)
 		|| TREE_CODE (rhsop) == CALL_EXPR)
 	      {
-		
 		lhs = get_constraint_for (lhsop);
 		switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
 		  {
@@ -2430,7 +2449,8 @@ find_func_aliases (tree t)
 		      process_constraint (new_constraint (lhs, rhs));
 		    }
 		    break;
-		    /* other classes, we walk each operator */
+
+		    /* Otherwise, walk each operand.  */
 		  default:
 		    for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
 		      {
@@ -2443,11 +2463,13 @@ find_func_aliases (tree t)
 	  }
       }
       break;
+
     default:
       break;
     }
 }
 
+
 /* Find the first varinfo in the same variable as START that overlaps with
    OFFSET.
    Effectively, walk the chain of fields for the variable START to find the
@@ -2468,9 +2490,11 @@ first_vi_for_offset (varinfo_t start, un
 	return curr;
       curr = curr->next;
     }
+
   gcc_unreachable ();
 }
 
+
 /* Insert the varinfo FIELD into the field list for BASE, ordered by
    offset.  */
 
@@ -2499,6 +2523,7 @@ insert_into_field_list (varinfo_t base, 
     }
 }
 
+
 /* This structure is simply used during pushing fields onto the fieldstack
    to track the offset of the field, since bitpos_of_field gives it relative
    to its immediate containing type, and we want it relative to the ultimate
@@ -2513,6 +2538,7 @@ typedef struct fieldoff
 DEF_VEC_O (fieldoff_s);
 DEF_VEC_ALLOC_O(fieldoff_s,heap);
 
+
 /* qsort comparison function for two fieldoff's PA and PB */
 
 static int 
@@ -2539,6 +2565,8 @@ fieldoff_compare (const void *pa, const 
    HAS_UNION is set to true if we find a union type as a field of
    TYPE.  */
 
+/* FIXME: Dup of tree-ssa-alias.c:push_fields_onto_fieldstack.  */
+
 static int
 push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack, 
 			     HOST_WIDE_INT offset, bool *has_union)
@@ -2577,6 +2605,7 @@ push_fields_onto_fieldstack (tree type, 
 	    count++;
 	  }
       }
+
   return count;
 }
 
@@ -2596,8 +2625,9 @@ make_constraint_to_anything (varinfo_t v
 }
 
 
-/* Create a varinfo structure for NAME and DECL, and add it to the varmap.
-   This will also create any variable infos necessary for fields of DECL.  */
+/* Create a varinfo structure for NAME and DECL, and add it to VARMAP.
+   This will also create any varinfo structures necessary for fields
+   of DECL.  */
 
 static unsigned int
 create_variable_info_for (tree decl, const char *name)
@@ -2642,7 +2672,9 @@ create_variable_info_for (tree decl, con
 	  char *tempname;
 	  const char *newname;
 
-	  asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC "."HOST_WIDE_INT_PRINT_DEC, alias_get_name (decl), sv->offset, sv->size);
+	  asprintf (&tempname,
+	            "%s." HOST_WIDE_INT_PRINT_DEC "." HOST_WIDE_INT_PRINT_DEC,
+		    alias_get_name (decl), sv->offset, sv->size);
 	  newname = ggc_strdup (tempname);
 	  free (tempname);
 	  vi = new_var_info (sv->var, index, newname, index);
@@ -2794,6 +2826,7 @@ debug_solution_for_var (unsigned int var
   dump_solution_for_var (stdout, var);
 }
 
+
 /* Create varinfo structures for all of the variables in the
    function for intraprocedural mode.  */
 
@@ -2801,10 +2834,9 @@ static void
 intra_create_variable_infos (void)
 {
   tree t;
+
   /* For each incoming argument arg, ARG = &ANYTHING */
-  for (t = DECL_ARGUMENTS (current_function_decl);
-       t;
-       t = TREE_CHAIN (t))
+  for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t))
     {
       struct constraint_expr lhs;
       struct constraint_expr rhs;
@@ -2938,6 +2970,7 @@ static void
 init_base_vars (void)
 {
   struct constraint_expr lhs, rhs;
+
   /* Create the NULL variable, used to represent that a variable points
      to NULL.  */
   nothing_tree = create_tmp_var_raw (void_type_node, "NULL");
@@ -2962,9 +2995,8 @@ init_base_vars (void)
   var_anything->fullsize = ~0;
   anything_id = 1;
 
-  /* anything points to anything. This makes deref constraints just
-     work.  */
-  
+  /* Anything points to anything.  This makes deref constraints just
+     work.  FIXME: "just work"?  Some elaboration would help here.  */
   VEC_safe_push (varinfo_t, gc, varmap, var_anything);
   lhs.type = SCALAR;
   lhs.var = anything_id;
@@ -2989,7 +3021,8 @@ init_base_vars (void)
   readonly_id = 2;
   VEC_safe_push (varinfo_t, gc, varmap, var_readonly);
 
-  /* readonly memory points to anything, in order to make deref easier.  */
+  /* readonly memory points to anything, in order to make deref
+     easier.  FIXME: Refer to previous deref explanation.  */
   lhs.type = SCALAR;
   lhs.var = readonly_id;
   lhs.offset = 0;
@@ -3014,7 +3047,9 @@ init_base_vars (void)
   VEC_safe_push (varinfo_t, gc, varmap, var_integer);
 }  
 
-/* Create points-to sets for the current function.  */
+
+/* Create points-to sets for the current function.  See the comments
+   at the start of the file for an algorithmic overview.  */
 
 static void
 create_alias_vars (void)
@@ -3039,30 +3074,38 @@ create_alias_vars (void)
   init_base_vars ();
 
   intra_create_variable_infos ();
+
   /* Now walk all statements and derive aliases.  */
   FOR_EACH_BB (bb)
     {
       block_stmt_iterator bsi; 
       tree phi;
+
       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 	if (is_gimple_reg (PHI_RESULT (phi)))
 	  find_func_aliases (phi);
+
       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 	find_func_aliases (bsi_stmt (bsi));
     }
 
   build_constraint_graph ();
+
   if (dump_file)
     {
       fprintf (dump_file, "Constraints:\n");
       dump_constraints (dump_file);
     }
+
   if (dump_file)
     fprintf (dump_file, "Collapsing static cycles and doing variable substitution:\n");
+
   find_and_collapse_graph_cycles (graph, false);
   perform_var_substitution (graph);
+
   if (dump_file)
     fprintf (dump_file, "Solving graph:\n");
+
   solve_graph (graph);
 
   if (dump_file)
@@ -3118,6 +3161,3 @@ struct tree_opt_pass pass_del_pta = 
   0,                                    /* todo_flags_finish */
   0					/* letter */
 };
-
-
-