Merged revisions 196607-196608,196611-196614,196625,196629-196634,196636,196639,196645-196647,196649-196650,196654-196659,196666,196669,196671-196675,196682-196683,196694-196695,196697-196698,196700-196701,196704-196706,196709,196721-196748,196750-196751,196753,196755-196758,196762,196764-196765,196767-196771,196773-196779,196781-196784,196788-196792,196795-196797,196799-196800,196804-196807,196810-196814,196821,196823-196825,196828-196829,196831-196832,196834,196841-196842,196847-196853,196855-196856,196858,196860-196861,196864-196866,196868,196870-196872,196874,196876,196878-196879,196882,196884-196890,196896-196897,196899-196902,196954,196956-196961,196964-196965,196970,196977-196978,196981-196983,196989,197002-197005,197007,197011-197012,197016-197019,197021,197023-197025,197029-197034,197036-197042 via svnmerge from cxx-conversion

svn+ssh://gcc.gnu.org/svn/gcc/trunk



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/cxx-conversion@197098 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 289 insertions, 198 deletions

diff --git a/gcc/tree-ssa-structalias.c b/gcc/tree-ssa-structalias.c
index 48b4008e5ec..bbb84cfd925 100644
--- a/gcc/tree-ssa-structalias.c
+++ b/gcc/tree-ssa-structalias.c
@@ -268,8 +268,12 @@ struct variable_info
   /* True if this represents a IPA function info.  */
   unsigned int is_fn_info : 1;
 
-  /* A link to the variable for the next field in this structure.  */
-  struct variable_info *next;
+  /* The ID of the variable for the next field in this structure
+     or zero for the last field in this structure.  */
+  unsigned next;
+
+  /* The ID of the variable for the first field in this structure.  */
+  unsigned head;
 
   /* Offset of this variable, in bits, from the base variable  */
   unsigned HOST_WIDE_INT offset;
@@ -319,10 +323,20 @@ get_varinfo (unsigned int n)
   return varmap[n];
 }
 
-/* Static IDs for the special variables.  */
-enum { nothing_id = 0, anything_id = 1, readonly_id = 2,
-       escaped_id = 3, nonlocal_id = 4,
-       storedanything_id = 5, integer_id = 6 };
+/* Return the next variable in the list of sub-variables of VI
+   or NULL if VI is the last sub-variable.  */
+
+static inline varinfo_t
+vi_next (varinfo_t vi)
+{
+  return get_varinfo (vi->next);
+}
+
+/* Static IDs for the special variables.  Variable ID zero is unused
+   and used as terminator for the sub-variable chain.  */
+enum { nothing_id = 1, anything_id = 2, readonly_id = 3,
+       escaped_id = 4, nonlocal_id = 5,
+       storedanything_id = 6, integer_id = 7 };
 
 /* Return a new variable info structure consisting for a variable
    named NAME, and using constraint graph node NODE.  Append it
@@ -355,7 +369,8 @@ new_var_info (tree t, const char *name)
 			      && DECL_HARD_REGISTER (t)));
   ret->solution = BITMAP_ALLOC (&pta_obstack);
   ret->oldsolution = NULL;
-  ret->next = NULL;
+  ret->next = 0;
+  ret->head = ret->id;
 
   stats.total_vars++;
 
@@ -387,12 +402,14 @@ get_call_vi (gimple call)
   vi->fullsize = 2;
   vi->is_full_var = true;
 
-  vi->next = vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED");
+  vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED");
   vi2->offset = 1;
   vi2->size = 1;
   vi2->fullsize = 2;
   vi2->is_full_var = true;
 
+  vi->next = vi2->id;
+
   *slot_p = (void *) vi;
   return vi;
 }
@@ -422,7 +439,7 @@ lookup_call_clobber_vi (gimple call)
   if (!uses)
     return NULL;
 
-  return uses->next;
+  return vi_next (uses);
 }
 
 /* Lookup or create the variable for the call statement CALL representing
@@ -440,7 +457,7 @@ get_call_use_vi (gimple call)
 static varinfo_t ATTRIBUTE_UNUSED
 get_call_clobber_vi (gimple call)
 {
-  return get_call_vi (call)->next;
+  return vi_next (get_call_vi (call));
 }
 
 
@@ -581,7 +598,7 @@ static constraint_graph_t graph;
 static unsigned int
 find (unsigned int node)
 {
-  gcc_assert (node < graph->size);
+  gcc_checking_assert (node < graph->size);
   if (graph->rep[node] != node)
     return graph->rep[node] = find (graph->rep[node]);
   return node;
@@ -595,7 +612,7 @@ find (unsigned int node)
 static bool
 unite (unsigned int to, unsigned int from)
 {
-  gcc_assert (to < graph->size && from < graph->size);
+  gcc_checking_assert (to < graph->size && from < graph->size);
   if (to != from && graph->rep[from] != to)
     {
       graph->rep[from] = to;
@@ -701,8 +718,10 @@ dump_constraint_graph (FILE *file)
 
   /* The next lines print the nodes in the graph together with the
      complex constraints attached to them.  */
-  for (i = 0; i < graph->size; i++)
+  for (i = 1; i < graph->size; i++)
     {
+      if (i == FIRST_REF_NODE)
+	continue;
       if (find (i) != i)
 	continue;
       if (i < FIRST_REF_NODE)
@@ -726,7 +745,7 @@ dump_constraint_graph (FILE *file)
 
   /* Go over the edges.  */
   fprintf (file, "\n  // Edges in the constraint graph:\n");
-  for (i = 0; i < graph->size; i++)
+  for (i = 1; i < graph->size; i++)
     {
       unsigned j;
       bitmap_iterator bi;
@@ -881,63 +900,71 @@ constraint_set_union (vec<constraint_t> *to,
     }
 }
 
-/* Expands the solution in SET to all sub-fields of variables included.
-   Union the expanded result into RESULT.  */
+/* Expands the solution in SET to all sub-fields of variables included.  */
 
 static void
-solution_set_expand (bitmap result, bitmap set)
+solution_set_expand (bitmap set)
 {
   bitmap_iterator bi;
-  bitmap vars = NULL;
   unsigned j;
 
-  /* In a first pass record all variables we need to add all
-     sub-fields off.  This avoids quadratic behavior.  */
+  /* In a first pass expand to the head of the variables we need to
+     add all sub-fields off.  This avoids quadratic behavior.  */
   EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
     {
       varinfo_t v = get_varinfo (j);
       if (v->is_artificial_var
 	  || v->is_full_var)
 	continue;
-      v = lookup_vi_for_tree (v->decl);
-      if (vars == NULL)
-	vars = BITMAP_ALLOC (NULL);
-      bitmap_set_bit (vars, v->id);
+      bitmap_set_bit (set, v->head);
     }
 
-  /* In the second pass now do the addition to the solution and
-     to speed up solving add it to the delta as well.  */
-  if (vars != NULL)
+  /* In the second pass now expand all head variables with subfields.  */
+  EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi)
     {
-      EXECUTE_IF_SET_IN_BITMAP (vars, 0, j, bi)
-	{
-	  varinfo_t v = get_varinfo (j);
-	  for (; v != NULL; v = v->next)
-	    bitmap_set_bit (result, v->id);
-	}
-      BITMAP_FREE (vars);
+      varinfo_t v = get_varinfo (j);
+      if (v->is_artificial_var
+	  || v->is_full_var
+	  || v->head != j)
+	continue;
+      for (v = vi_next (v); v != NULL; v = vi_next (v))
+	bitmap_set_bit (set, v->id);
     }
 }
 
-/* Take a solution set SET, add OFFSET to each member of the set, and
-   overwrite SET with the result when done.  */
+/* Union solution sets TO and FROM, and add INC to each member of FROM in the
+   process.  */
 
-static void
-solution_set_add (bitmap set, HOST_WIDE_INT offset)
+static bool
+set_union_with_increment  (bitmap to, bitmap from, HOST_WIDE_INT inc)
 {
-  bitmap result = BITMAP_ALLOC (&iteration_obstack);
-  unsigned int i;
+  bool changed = false;
   bitmap_iterator bi;
+  unsigned int i;
+
+  /* If the solution of FROM contains anything it is good enough to transfer
+     this to TO.  */
+  if (bitmap_bit_p (from, anything_id))
+    return bitmap_set_bit (to, anything_id);
+
+  /* For zero offset simply union the solution into the destination.  */
+  if (inc == 0)
+    return bitmap_ior_into (to, from);
 
   /* If the offset is unknown we have to expand the solution to
      all subfields.  */
-  if (offset == UNKNOWN_OFFSET)
+  if (inc == UNKNOWN_OFFSET)
     {
-      solution_set_expand (set, set);
-      return;
+      bitmap tmp = BITMAP_ALLOC (&iteration_obstack);
+      bitmap_copy (tmp, from);
+      solution_set_expand (tmp);
+      changed |= bitmap_ior_into (to, tmp);
+      BITMAP_FREE (tmp);
+      return changed;
     }
 
-  EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
+  /* For non-zero offset union the offsetted solution into the destination.  */
+  EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
     {
       varinfo_t vi = get_varinfo (i);
 
@@ -946,54 +973,30 @@ solution_set_add (bitmap set, HOST_WIDE_INT offset)
       if (vi->is_artificial_var
 	  || vi->is_unknown_size_var
 	  || vi->is_full_var)
-	bitmap_set_bit (result, i);
+	changed |= bitmap_set_bit (to, i);
       else
 	{
-	  unsigned HOST_WIDE_INT fieldoffset = vi->offset + offset;
+	  unsigned HOST_WIDE_INT fieldoffset = vi->offset + inc;
 
 	  /* If the offset makes the pointer point to before the
 	     variable use offset zero for the field lookup.  */
-	  if (offset < 0
+	  if (inc < 0
 	      && fieldoffset > vi->offset)
 	    fieldoffset = 0;
 
-	  if (offset != 0)
-	    vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
+	  vi = first_or_preceding_vi_for_offset (vi, fieldoffset);
 
-	  bitmap_set_bit (result, vi->id);
+	  changed |= bitmap_set_bit (to, vi->id);
 	  /* If the result is not exactly at fieldoffset include the next
 	     field as well.  See get_constraint_for_ptr_offset for more
 	     rationale.  */
 	  if (vi->offset != fieldoffset
-	      && vi->next != NULL)
-	    bitmap_set_bit (result, vi->next->id);
+	      && vi->next != 0)
+	    changed |= bitmap_set_bit (to, vi->next);
 	}
     }
 
-  bitmap_copy (set, result);
-  BITMAP_FREE (result);
-}
-
-/* Union solution sets TO and FROM, and add INC to each member of FROM in the
-   process.  */
-
-static bool
-set_union_with_increment  (bitmap to, bitmap from, HOST_WIDE_INT inc)
-{
-  if (inc == 0)
-    return bitmap_ior_into (to, from);
-  else
-    {
-      bitmap tmp;
-      bool res;
-
-      tmp = BITMAP_ALLOC (&iteration_obstack);
-      bitmap_copy (tmp, from);
-      solution_set_add (tmp, inc);
-      res = bitmap_ior_into (to, tmp);
-      BITMAP_FREE (tmp);
-      return res;
-    }
+  return changed;
 }
 
 /* Insert constraint C into the list of complex constraints for graph
@@ -1023,7 +1026,7 @@ merge_node_constraints (constraint_graph_t graph, unsigned int to,
   unsigned int i;
   constraint_t c;
 
-  gcc_assert (find (from) == to);
+  gcc_checking_assert (find (from) == to);
 
   /* Move all complex constraints from src node into to node  */
   FOR_EACH_VEC_ELT (graph->complex[from], i, c)
@@ -1143,16 +1146,6 @@ add_graph_edge (constraint_graph_t graph, unsigned int to,
 }
 
 
-/* Return true if {DEST.SRC} is an existing graph edge in GRAPH.  */
-
-static bool
-valid_graph_edge (constraint_graph_t graph, unsigned int src,
-		  unsigned int dest)
-{
-  return (graph->succs[dest]
-	  && bitmap_bit_p (graph->succs[dest], src));
-}
-
 /* Initialize the constraint graph structure to contain SIZE nodes.  */
 
 static void
@@ -1200,7 +1193,7 @@ build_pred_graph (void)
   graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack);
   bitmap_clear (graph->direct_nodes);
 
-  for (j = 0; j < FIRST_REF_NODE; j++)
+  for (j = 1; j < FIRST_REF_NODE; j++)
     {
       if (!get_varinfo (j)->is_special_var)
 	bitmap_set_bit (graph->direct_nodes, j);
@@ -1254,11 +1247,11 @@ build_pred_graph (void)
           v = get_varinfo (rhsvar);
           if (!v->is_full_var)
             {
-              v = lookup_vi_for_tree (v->decl);
+              v = get_varinfo (v->head);
               do
                 {
                   bitmap_clear_bit (graph->direct_nodes, v->id);
-                  v = v->next;
+                  v = vi_next (v);
                 }
               while (v != NULL);
             }
@@ -1319,7 +1312,7 @@ build_succ_graph (void)
       else if (rhs.type == ADDRESSOF)
 	{
 	  /* x = &y */
-	  gcc_assert (find (rhs.var) == rhs.var);
+	  gcc_checking_assert (find (rhs.var) == rhs.var);
 	  bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar);
 	}
       else if (lhsvar > anything_id
@@ -1396,14 +1389,11 @@ scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
 
       if (!bitmap_bit_p (si->visited, w))
 	scc_visit (graph, si, w);
-      {
-	unsigned int t = find (w);
-	unsigned int nnode = find (n);
-	gcc_assert (nnode == n);
 
-	if (si->dfs[t] < si->dfs[nnode])
-	  si->dfs[n] = si->dfs[t];
-      }
+      unsigned int t = find (w);
+      gcc_checking_assert (find (n) == n);
+      if (si->dfs[t] < si->dfs[n])
+	si->dfs[n] = si->dfs[t];
     }
 
   /* See if any components have been identified.  */
@@ -1458,8 +1448,8 @@ static void
 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
 	     bool update_changed)
 {
+  gcc_checking_assert (to != from && find (to) == to);
 
-  gcc_assert (to != from && find (to) == to);
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "Unifying %s to %s\n",
 	     get_varinfo (from)->name,
@@ -1477,35 +1467,30 @@ unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
      as changed, decrease the changed count.  */
 
   if (update_changed
-      && bitmap_bit_p (changed, from))
-    {
-      bitmap_clear_bit (changed, from);
-      bitmap_set_bit (changed, to);
-    }
-  if (get_varinfo (from)->solution)
+      && bitmap_clear_bit (changed, from))
+    bitmap_set_bit (changed, to);
+  varinfo_t fromvi = get_varinfo (from);
+  if (fromvi->solution)
     {
       /* If the solution changes because of the merging, we need to mark
 	 the variable as changed.  */
-      if (bitmap_ior_into (get_varinfo (to)->solution,
-			   get_varinfo (from)->solution))
+      varinfo_t tovi = get_varinfo (to);
+      if (bitmap_ior_into (tovi->solution, fromvi->solution))
 	{
 	  if (update_changed)
 	    bitmap_set_bit (changed, to);
 	}
 
-      BITMAP_FREE (get_varinfo (from)->solution);
-      if (get_varinfo (from)->oldsolution)
-	BITMAP_FREE (get_varinfo (from)->oldsolution);
+      BITMAP_FREE (fromvi->solution);
+      if (fromvi->oldsolution)
+	BITMAP_FREE (fromvi->oldsolution);
 
       if (stats.iterations > 0
-	  && get_varinfo (to)->oldsolution)
-	BITMAP_FREE (get_varinfo (to)->oldsolution);
-    }
-  if (valid_graph_edge (graph, to, to))
-    {
-      if (graph->succs[to])
-	bitmap_clear_bit (graph->succs[to], to);
+	  && tovi->oldsolution)
+	BITMAP_FREE (tovi->oldsolution);
     }
+  if (graph->succs[to])
+    bitmap_clear_bit (graph->succs[to], to);
 }
 
 /* Information needed to compute the topological ordering of a graph.  */
@@ -1581,7 +1566,7 @@ do_sd_constraint (constraint_graph_t graph, constraint_t c,
   HOST_WIDE_INT roffset = c->rhs.offset;
 
   /* Our IL does not allow this.  */
-  gcc_assert (c->lhs.offset == 0);
+  gcc_checking_assert (c->lhs.offset == 0);
 
   /* If the solution of Y contains anything it is good enough to transfer
      this to the LHS.  */
@@ -1596,7 +1581,7 @@ do_sd_constraint (constraint_graph_t graph, constraint_t c,
      dereferenced at all valid offsets.  */
   if (roffset == UNKNOWN_OFFSET)
     {
-      solution_set_expand (delta, delta);
+      solution_set_expand (delta);
       /* No further offset processing is necessary.  */
       roffset = 0;
     }
@@ -1636,10 +1621,10 @@ do_sd_constraint (constraint_graph_t graph, constraint_t c,
 	  /* If the variable is not exactly at the requested offset
 	     we have to include the next one.  */
 	  if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
-	      || v->next == NULL)
+	      || v->next == 0)
 	    break;
 
-	  v = v->next;
+	  v = vi_next (v);
 	  fieldoffset = v->offset;
 	}
       while (1);
@@ -1668,7 +1653,7 @@ do_ds_constraint (constraint_t c, bitmap delta)
   bool escaped_p = false;
 
   /* Our IL does not allow this.  */
-  gcc_assert (c->rhs.offset == 0);
+  gcc_checking_assert (c->rhs.offset == 0);
 
   /* If the solution of y contains ANYTHING simply use the ANYTHING
      solution.  This avoids needlessly increasing the points-to sets.  */
@@ -1694,7 +1679,7 @@ do_ds_constraint (constraint_t c, bitmap delta)
      dereferenced at all valid offsets.  */
   if (loff == UNKNOWN_OFFSET)
     {
-      solution_set_expand (delta, delta);
+      solution_set_expand (delta);
       loff = 0;
     }
 
@@ -1742,10 +1727,10 @@ do_ds_constraint (constraint_t c, bitmap delta)
 	  /* If the variable is not exactly at the requested offset
 	     we have to include the next one.  */
 	  if (v->offset == (unsigned HOST_WIDE_INT)fieldoffset
-	      || v->next == NULL)
+	      || v->next == 0)
 	    break;
 
-	  v = v->next;
+	  v = vi_next (v);
 	  fieldoffset = v->offset;
 	}
       while (1);
@@ -1782,17 +1767,14 @@ do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta)
       bitmap solution;
       bool flag = false;
 
-      gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
+      gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR);
       solution = get_varinfo (c->rhs.var)->solution;
       tmp = get_varinfo (c->lhs.var)->solution;
 
       flag = set_union_with_increment (tmp, solution, c->rhs.offset);
 
       if (flag)
-	{
-	  get_varinfo (c->lhs.var)->solution = tmp;
-	  bitmap_set_bit (changed, c->lhs.var);
-	}
+	bitmap_set_bit (changed, c->lhs.var);
     }
 }
 
@@ -1998,7 +1980,7 @@ condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
   bitmap_iterator bi;
   unsigned int my_dfs;
 
-  gcc_assert (si->node_mapping[n] == n);
+  gcc_checking_assert (si->node_mapping[n] == n);
   bitmap_set_bit (si->visited, n);
   si->dfs[n] = si->current_index ++;
   my_dfs = si->dfs[n];
@@ -2013,14 +1995,11 @@ condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
 
       if (!bitmap_bit_p (si->visited, w))
 	condense_visit (graph, si, w);
-      {
-	unsigned int t = si->node_mapping[w];
-	unsigned int nnode = si->node_mapping[n];
-	gcc_assert (nnode == n);
 
-	if (si->dfs[t] < si->dfs[nnode])
-	  si->dfs[n] = si->dfs[t];
-      }
+      unsigned int t = si->node_mapping[w];
+      gcc_checking_assert (si->node_mapping[n] == n);
+      if (si->dfs[t] < si->dfs[n])
+	si->dfs[n] = si->dfs[t];
     }
 
   /* Visit all the implicit predecessors.  */
@@ -2033,14 +2012,11 @@ condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
 
       if (!bitmap_bit_p (si->visited, w))
 	condense_visit (graph, si, w);
-      {
-	unsigned int t = si->node_mapping[w];
-	unsigned int nnode = si->node_mapping[n];
-	gcc_assert (nnode == n);
 
-	if (si->dfs[t] < si->dfs[nnode])
-	  si->dfs[n] = si->dfs[t];
-      }
+      unsigned int t = si->node_mapping[w];
+      gcc_assert (si->node_mapping[n] == n);
+      if (si->dfs[t] < si->dfs[n])
+	si->dfs[n] = si->dfs[t];
     }
 
   /* See if any components have been identified.  */
@@ -2170,6 +2146,77 @@ label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
     }
 }
 
+/* Print the pred graph in dot format.  */
+
+static void
+dump_pred_graph (struct scc_info *si, FILE *file)
+{
+  unsigned int i;
+
+  /* Only print the graph if it has already been initialized:  */
+  if (!graph)
+    return;
+
+  /* Prints the header of the dot file:  */
+  fprintf (file, "strict digraph {\n");
+  fprintf (file, "  node [\n    shape = box\n  ]\n");
+  fprintf (file, "  edge [\n    fontsize = \"12\"\n  ]\n");
+  fprintf (file, "\n  // List of nodes and complex constraints in "
+	   "the constraint graph:\n");
+
+  /* The next lines print the nodes in the graph together with the
+     complex constraints attached to them.  */
+  for (i = 1; i < graph->size; i++)
+    {
+      if (i == FIRST_REF_NODE)
+	continue;
+      if (si->node_mapping[i] != i)
+	continue;
+      if (i < FIRST_REF_NODE)
+	fprintf (file, "\"%s\"", get_varinfo (i)->name);
+      else
+	fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
+      if (graph->points_to[i]
+	  && !bitmap_empty_p (graph->points_to[i]))
+	{
+	  fprintf (file, "[label=\"%s = {", get_varinfo (i)->name);
+	  unsigned j;
+	  bitmap_iterator bi;
+	  EXECUTE_IF_SET_IN_BITMAP (graph->points_to[i], 0, j, bi)
+	    fprintf (file, " %d", j);
+	  fprintf (file, " }\"]");
+	}
+      fprintf (file, ";\n");
+    }
+
+  /* Go over the edges.  */
+  fprintf (file, "\n  // Edges in the constraint graph:\n");
+  for (i = 1; i < graph->size; i++)
+    {
+      unsigned j;
+      bitmap_iterator bi;
+      if (si->node_mapping[i] != i)
+	continue;
+      EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[i], 0, j, bi)
+	{
+	  unsigned from = si->node_mapping[j];
+	  if (from < FIRST_REF_NODE)
+	    fprintf (file, "\"%s\"", get_varinfo (from)->name);
+	  else
+	    fprintf (file, "\"*%s\"", get_varinfo (from - FIRST_REF_NODE)->name);
+	  fprintf (file, " -> ");
+	  if (i < FIRST_REF_NODE)
+	    fprintf (file, "\"%s\"", get_varinfo (i)->name);
+	  else
+	    fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name);
+	  fprintf (file, ";\n");
+	}
+    }
+
+  /* Prints the tail of the dot file.  */
+  fprintf (file, "}\n");
+}
+
 /* Perform offline variable substitution, discovering equivalence
    classes, and eliminating non-pointer variables.  */
 
@@ -2188,18 +2235,26 @@ perform_var_substitution (constraint_graph_t graph)
 
   /* Condense the nodes, which means to find SCC's, count incoming
      predecessors, and unite nodes in SCC's.  */
-  for (i = 0; i < FIRST_REF_NODE; i++)
+  for (i = 1; i < FIRST_REF_NODE; i++)
     if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
       condense_visit (graph, si, si->node_mapping[i]);
 
+  if (dump_file && (dump_flags & TDF_GRAPH))
+    {
+      fprintf (dump_file, "\n\n// The constraint graph before var-substitution "
+	       "in dot format:\n");
+      dump_pred_graph (si, dump_file);
+      fprintf (dump_file, "\n\n");
+    }
+
   bitmap_clear (si->visited);
   /* Actually the label the nodes for pointer equivalences  */
-  for (i = 0; i < FIRST_REF_NODE; i++)
+  for (i = 1; i < FIRST_REF_NODE; i++)
     if (!bitmap_bit_p (si->visited, si->node_mapping[i]))
       label_visit (graph, si, si->node_mapping[i]);
 
   /* Calculate location equivalence labels.  */
-  for (i = 0; i < FIRST_REF_NODE; i++)
+  for (i = 1; i < FIRST_REF_NODE; i++)
     {
       bitmap pointed_by;
       bitmap_iterator bi;
@@ -2237,7 +2292,7 @@ perform_var_substitution (constraint_graph_t graph)
     }
 
   if (dump_file && (dump_flags & TDF_DETAILS))
-    for (i = 0; i < FIRST_REF_NODE; i++)
+    for (i = 1; i < FIRST_REF_NODE; i++)
       {
 	unsigned j = si->node_mapping[i];
 	if (j != i)
@@ -2257,7 +2312,7 @@ perform_var_substitution (constraint_graph_t graph)
 
   /* Quickly eliminate our non-pointer variables.  */
 
-  for (i = 0; i < FIRST_REF_NODE; i++)
+  for (i = 1; i < FIRST_REF_NODE; i++)
     {
       unsigned int node = si->node_mapping[i];
 
@@ -2307,7 +2362,7 @@ find_equivalent_node (constraint_graph_t graph,
 
   if (!bitmap_bit_p (graph->address_taken, node))
     {
-      gcc_assert (label < graph->size);
+      gcc_checking_assert (label < graph->size);
 
       if (graph->eq_rep[label] != -1)
 	{
@@ -2324,7 +2379,7 @@ find_equivalent_node (constraint_graph_t graph,
     }
   else
     {
-      gcc_assert (label < graph->size);
+      gcc_checking_assert (label < graph->size);
       graph->pe[node] = label;
       if (graph->pe_rep[label] == -1)
 	graph->pe_rep[label] = node;
@@ -2344,7 +2399,7 @@ unite_pointer_equivalences (constraint_graph_t graph)
 
   /* Go through the pointer equivalences and unite them to their
      representative, if they aren't already.  */
-  for (i = 0; i < FIRST_REF_NODE; i++)
+  for (i = 1; i < FIRST_REF_NODE; i++)
     {
       unsigned int label = graph->pe[i];
       if (label)
@@ -2404,11 +2459,12 @@ rewrite_constraints (constraint_graph_t graph,
 		     struct scc_info *si)
 {
   int i;
-  unsigned int j;
   constraint_t c;
 
-  for (j = 0; j < graph->size; j++)
+#ifdef ENABLE_CHECKING
+  for (unsigned int j = 0; j < graph->size; j++)
     gcc_assert (find (j) == j);
+#endif
 
   FOR_EACH_VEC_ELT (constraints, i, c)
     {
@@ -2460,7 +2516,6 @@ rewrite_constraints (constraint_graph_t graph,
       rhsvar = find_equivalent_node (graph, rhsvar, rhslabel);
       c->lhs.var = lhsvar;
       c->rhs.var = rhsvar;
-
     }
 }
 
@@ -2521,7 +2576,7 @@ solve_graph (constraint_graph_t graph)
   changed = BITMAP_ALLOC (NULL);
 
   /* Mark all initial non-collapsed nodes as changed.  */
-  for (i = 0; i < size; i++)
+  for (i = 1; i < size; i++)
     {
       varinfo_t ivi = get_varinfo (i);
       if (find (i) == i && !bitmap_empty_p (ivi->solution)
@@ -2568,8 +2623,19 @@ solve_graph (constraint_graph_t graph)
 	      varinfo_t vi = get_varinfo (i);
 	      bool solution_empty;
 
-	      /* Compute the changed set of solution bits.  */
-	      if (vi->oldsolution)
+	      /* Compute the changed set of solution bits.  If anything
+	         is in the solution just propagate that.  */
+	      if (bitmap_bit_p (vi->solution, anything_id))
+		{
+		  /* If anything is also in the old solution there is
+		     nothing to do.
+		     ???  But we shouldn't ended up with "changed" set ...  */
+		  if (vi->oldsolution
+		      && bitmap_bit_p (vi->oldsolution, anything_id))
+		    continue;
+		  bitmap_copy (pts, get_varinfo (find (anything_id))->solution);
+		}
+	      else if (vi->oldsolution)
 		bitmap_and_compl (pts, vi->solution, vi->oldsolution);
 	      else
 		bitmap_copy (pts, vi->solution);
@@ -2633,13 +2699,10 @@ solve_graph (constraint_graph_t graph)
 		      if (i == eff_escaped_id)
 			flag = bitmap_set_bit (tmp, escaped_id);
 		      else
-			flag = set_union_with_increment (tmp, pts, 0);
+			flag = bitmap_ior_into (tmp, pts);
 
 		      if (flag)
-			{
-			  get_varinfo (to)->solution = tmp;
-			  bitmap_set_bit (changed, to);
-			}
+			bitmap_set_bit (changed, to);
 		    }
 		}
 	    }
@@ -2817,7 +2880,7 @@ get_constraint_for_ssa_var (tree t, vec<ce_s> *results, bool address_p)
   if (!address_p
       && !vi->is_full_var)
     {
-      for (; vi; vi = vi->next)
+      for (; vi; vi = vi_next (vi))
 	{
 	  cexpr.var = vi->id;
 	  results->safe_push (cexpr);
@@ -2964,7 +3027,7 @@ get_constraint_for_ptr_offset (tree ptr, tree offset,
 	       /* If we do not know the offset add all subfields.  */
 	       && rhsoffset == UNKNOWN_OFFSET)
 	{
-	  varinfo_t temp = lookup_vi_for_tree (curr->decl);
+	  varinfo_t temp = get_varinfo (curr->head);
 	  do
 	    {
 	      struct constraint_expr c2;
@@ -2973,7 +3036,7 @@ get_constraint_for_ptr_offset (tree ptr, tree offset,
 	      c2.offset = 0;
 	      if (c2.var != c.var)
 		results->safe_push (c2);
-	      temp = temp->next;
+	      temp = vi_next (temp);
 	    }
 	  while (temp);
 	}
@@ -3001,10 +3064,10 @@ get_constraint_for_ptr_offset (tree ptr, tree offset,
 	     do not result in the same or a conservative superset
 	     solution.  */
 	  if (temp->offset != offset
-	      && temp->next != NULL)
+	      && temp->next != 0)
 	    {
 	      struct constraint_expr c2;
-	      c2.var = temp->next->id;
+	      c2.var = temp->next;
 	      c2.type = ADDRESSOF;
 	      c2.offset = 0;
 	      results->safe_push (c2);
@@ -3107,7 +3170,7 @@ get_constraint_for_component_ref (tree t, vec<ce_s> *results,
 	  varinfo_t curr;
 	  results->pop ();
 	  cexpr.offset = 0;
-	  for (curr = get_varinfo (cexpr.var); curr; curr = curr->next)
+	  for (curr = get_varinfo (cexpr.var); curr; curr = vi_next (curr))
 	    {
 	      if (ranges_overlap_p (curr->offset, curr->size,
 				    bitpos, bitmaxsize))
@@ -3124,8 +3187,8 @@ get_constraint_for_component_ref (tree t, vec<ce_s> *results,
 	  if (address_p && results->length () == 0)
 	    {
 	      curr = get_varinfo (cexpr.var);
-	      while (curr->next != NULL)
-		curr = curr->next;
+	      while (curr->next != 0)
+		curr = vi_next (curr);
 	      cexpr.var = curr->id;
 	      results->safe_push (cexpr);
 	    }
@@ -3321,7 +3384,7 @@ get_constraint_for_1 (tree t, vec<ce_s> *results, bool address_p,
 		return;
 
 	      vi = get_varinfo (cs.var);
-	      curr = vi->next;
+	      curr = vi_next (vi);
 	      if (!vi->is_full_var
 		  && curr)
 		{
@@ -3330,7 +3393,7 @@ get_constraint_for_1 (tree t, vec<ce_s> *results, bool address_p,
 		    size = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (t)));
 		  else
 		    size = -1;
-		  for (; curr; curr = curr->next)
+		  for (; curr; curr = vi_next (curr))
 		    {
 		      if (curr->offset - vi->offset < size)
 			{
@@ -4200,6 +4263,29 @@ find_func_aliases_for_builtin_call (gimple t)
 	    return true;
 	  }
 	break;
+      /* String / character search functions return a pointer into the
+         source string or NULL.  */
+      case BUILT_IN_INDEX:
+      case BUILT_IN_STRCHR:
+      case BUILT_IN_STRRCHR:
+      case BUILT_IN_MEMCHR:
+      case BUILT_IN_STRSTR:
+      case BUILT_IN_STRPBRK:
+	if (gimple_call_lhs (t))
+	  {
+	    tree src = gimple_call_arg (t, 0);
+	    get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc);
+	    constraint_expr nul;
+	    nul.var = nothing_id;
+	    nul.offset = 0;
+	    nul.type = ADDRESSOF;
+	    rhsc.safe_push (nul);
+	    get_constraint_for (gimple_call_lhs (t), &lhsc);
+	    process_all_all_constraints (lhsc, rhsc);
+	    lhsc.release();
+	    rhsc.release();
+	  }
+	return true;
       /* Trampolines are special - they set up passing the static
 	 frame.  */
       case BUILT_IN_INIT_TRAMPOLINE:
@@ -5003,7 +5089,7 @@ first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
   /* If we cannot reach offset from start, lookup the first field
      and start from there.  */
   if (start->offset > offset)
-    start = lookup_vi_for_tree (start->decl);
+    start = get_varinfo (start->head);
 
   while (start)
     {
@@ -5015,7 +5101,7 @@ first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset)
 	  && (offset - start->offset) < start->size)
 	return start;
 
-      start= start->next;
+      start = vi_next (start);
     }
 
   return NULL;
@@ -5032,7 +5118,7 @@ first_or_preceding_vi_for_offset (varinfo_t start,
   /* If we cannot reach offset from start, lookup the first field
      and start from there.  */
   if (start->offset > offset)
-    start = lookup_vi_for_tree (start->decl);
+    start = get_varinfo (start->head);
 
   /* We may not find a variable in the field list with the actual
      offset when when we have glommed a structure to a variable.
@@ -5043,7 +5129,7 @@ first_or_preceding_vi_for_offset (varinfo_t start,
   while (start->next
 	 && offset >= start->offset
 	 && !((offset - start->offset) < start->size))
-    start = start->next;
+    start = vi_next (start);
 
   return start;
 }
@@ -5326,7 +5412,7 @@ create_function_info_for (tree decl, const char *name)
       clobbervi->is_full_var = true;
       clobbervi->is_global_var = false;
       gcc_assert (prev_vi->offset < clobbervi->offset);
-      prev_vi->next = clobbervi;
+      prev_vi->next = clobbervi->id;
       prev_vi = clobbervi;
 
       asprintf (&tempname, "%s.use", name);
@@ -5340,7 +5426,7 @@ create_function_info_for (tree decl, const char *name)
       usevi->is_full_var = true;
       usevi->is_global_var = false;
       gcc_assert (prev_vi->offset < usevi->offset);
-      prev_vi->next = usevi;
+      prev_vi->next = usevi->id;
       prev_vi = usevi;
     }
 
@@ -5362,7 +5448,7 @@ create_function_info_for (tree decl, const char *name)
       chainvi->is_full_var = true;
       chainvi->is_global_var = false;
       gcc_assert (prev_vi->offset < chainvi->offset);
-      prev_vi->next = chainvi;
+      prev_vi->next = chainvi->id;
       prev_vi = chainvi;
       insert_vi_for_tree (fn->static_chain_decl, chainvi);
     }
@@ -5391,7 +5477,7 @@ create_function_info_for (tree decl, const char *name)
       if (DECL_RESULT (decl))
 	resultvi->may_have_pointers = true;
       gcc_assert (prev_vi->offset < resultvi->offset);
-      prev_vi->next = resultvi;
+      prev_vi->next = resultvi->id;
       prev_vi = resultvi;
       if (DECL_RESULT (decl))
 	insert_vi_for_tree (DECL_RESULT (decl), resultvi);
@@ -5421,7 +5507,7 @@ create_function_info_for (tree decl, const char *name)
       if (arg)
 	argvi->may_have_pointers = true;
       gcc_assert (prev_vi->offset < argvi->offset);
-      prev_vi->next = argvi;
+      prev_vi->next = argvi->id;
       prev_vi = argvi;
       if (arg)
 	{
@@ -5452,7 +5538,7 @@ create_function_info_for (tree decl, const char *name)
       argvi->is_heap_var = true;
       argvi->fullsize = vi->fullsize;
       gcc_assert (prev_vi->offset < argvi->offset);
-      prev_vi->next = argvi;
+      prev_vi->next = argvi->id;
       prev_vi = argvi;
     }
 
@@ -5566,7 +5652,7 @@ create_variable_info_for_1 (tree decl, const char *name)
   vi->fullsize = TREE_INT_CST_LOW (declsize);
   for (i = 0, newvi = vi;
        fieldstack.iterate (i, &fo);
-       ++i, newvi = newvi->next)
+       ++i, newvi = vi_next (newvi))
     {
       const char *newname = "NULL";
       char *tempname;
@@ -5585,7 +5671,11 @@ create_variable_info_for_1 (tree decl, const char *name)
       newvi->may_have_pointers = fo->may_have_pointers;
       newvi->only_restrict_pointers = fo->only_restrict_pointers;
       if (i + 1 < fieldstack.length ())
-	newvi->next = new_var_info (decl, name);
+	{
+	  varinfo_t tem = new_var_info (decl, name);
+	  newvi->next = tem->id;
+	  tem->head = vi->id;
+	}
     }
 
   fieldstack.release ();
@@ -5605,7 +5695,7 @@ create_variable_info_for (tree decl, const char *name)
     return id;
 
   /* Create initial constraints for globals.  */
-  for (; vi; vi = vi->next)
+  for (; vi; vi = vi_next (vi))
     {
       if (!vi->may_have_pointers
 	  || !vi->is_global_var)
@@ -5735,7 +5825,7 @@ intra_create_variable_infos (void)
 	  rhsc.type = ADDRESSOF;
 	  rhsc.offset = 0;
 	  process_constraint (new_constraint (lhsc, rhsc));
-	  for (; vi; vi = vi->next)
+	  for (; vi; vi = vi_next (vi))
 	    if (vi->may_have_pointers)
 	      {
 		if (vi->only_restrict_pointers)
@@ -5751,7 +5841,7 @@ intra_create_variable_infos (void)
 	make_constraint_from_global_restrict (p, "PARM_RESTRICT");
       else
 	{
-	  for (; p; p = p->next)
+	  for (; p; p = vi_next (p))
 	    {
 	      if (p->only_restrict_pointers)
 		make_constraint_from_global_restrict (p, "PARM_RESTRICT");
@@ -5767,7 +5857,7 @@ intra_create_variable_infos (void)
     {
       varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (cfun->decl));
 
-      for (p = result_vi; p; p = p->next)
+      for (p = result_vi; p; p = vi_next (p))
 	make_constraint_from (p, nonlocal_id);
     }
 
@@ -5776,7 +5866,7 @@ intra_create_variable_infos (void)
     {
       varinfo_t p, chain_vi = get_vi_for_tree (cfun->static_chain_decl);
 
-      for (p = chain_vi; p; p = p->next)
+      for (p = chain_vi; p; p = vi_next (p))
 	make_constraint_from (p, nonlocal_id);
     }
 }
@@ -6299,7 +6389,7 @@ dump_sa_points_to_info (FILE *outfile)
 	       stats.num_implicit_edges);
     }
 
-  for (i = 0; i < varmap.length (); i++)
+  for (i = 1; i < varmap.length (); i++)
     {
       varinfo_t vi = get_varinfo (i);
       if (!vi->may_have_pointers)
@@ -6333,6 +6423,9 @@ init_base_vars (void)
   varinfo_t var_storedanything;
   varinfo_t var_integer;
 
+  /* Variable ID zero is reserved and should be NULL.  */
+  varmap.safe_push (NULL);
+
   /* Create the NULL variable, used to represent that a variable points
      to NULL.  */
   var_nothing = new_var_info (NULL_TREE, "NULL");
@@ -6352,7 +6445,6 @@ init_base_vars (void)
   var_anything->is_artificial_var = 1;
   var_anything->size = ~0;
   var_anything->offset = 0;
-  var_anything->next = NULL;
   var_anything->fullsize = ~0;
   var_anything->is_special_var = 1;
 
@@ -6379,7 +6471,6 @@ init_base_vars (void)
   var_readonly->offset = 0;
   var_readonly->size = ~0;
   var_readonly->fullsize = ~0;
-  var_readonly->next = NULL;
   var_readonly->is_special_var = 1;
 
   /* readonly memory points to anything, in order to make deref
@@ -6476,7 +6567,6 @@ init_base_vars (void)
   var_integer->size = ~0;
   var_integer->fullsize = ~0;
   var_integer->offset = 0;
-  var_integer->next = NULL;
   var_integer->is_special_var = 1;
 
   /* INTEGER = ANYTHING, because we don't know where a dereference of
@@ -6530,7 +6620,7 @@ remove_preds_and_fake_succs (constraint_graph_t graph)
 
   /* Clear the implicit ref and address nodes from the successor
      lists.  */
-  for (i = 0; i < FIRST_REF_NODE; i++)
+  for (i = 1; i < FIRST_REF_NODE; i++)
     {
       if (graph->succs[i])
 	bitmap_clear_range (graph->succs[i], FIRST_REF_NODE,
@@ -6538,7 +6628,7 @@ remove_preds_and_fake_succs (constraint_graph_t graph)
     }
 
   /* Free the successor list for the non-ref nodes.  */
-  for (i = FIRST_REF_NODE; i < graph->size; i++)
+  for (i = FIRST_REF_NODE + 1; i < graph->size; i++)
     {
       if (graph->succs[i])
 	BITMAP_FREE (graph->succs[i]);
@@ -6685,7 +6775,8 @@ compute_points_to_sets (void)
 
   /* Mark escaped HEAP variables as global.  */
   FOR_EACH_VEC_ELT (varmap, i, vi)
-    if (vi->is_heap_var
+    if (vi
+	&& vi->is_heap_var
 	&& !vi->is_global_var)
       DECL_EXTERNAL (vi->decl) = vi->is_global_var
 	= pt_solution_includes (&cfun->gimple_df->escaped, vi->decl);