Constraint graph in points-to-analysis

Constraint graph in points-to-analysis

[Fernando Magno Quintao Pereira]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 815 bytes --]


Description
     This patch adds to gcc's points-to-analysis module the capacity to 
dump the constraint graph produced by the analysis in dot format. It also 
adds a command line tag to specify that this information should be 
printed.

ChangeLog
2008-06-30  Fernando Pereira <fernando@cs.ucla.edu>

 	* tree-ssa-structalias.c (compute_points_to_sets): Add call to
 	dump_constraint_graph.
 	(dump_constraint_edge): New function.
 	(dump_constraint_graph): New function.
 	(debug_constraint_graph): New function.
 	(dump_constraint): Removed useless comparison.
 	* tree-ssa-structalias.h (dump_constraint_edge): Declare.
 	(dump_constraint_graph): Declare.
 	(debug_constraint_graph): Declare.
 	* tree-dump.c (struct dump_option_value_info): Declare
 	TDF_DETAILS.

Bootstrapping and testing
 	i686-apple-darwin

[-- Attachment #2: Type: TEXT/PLAIN, Size: 5824 bytes --]

==== //depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.c#67 - /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.c ====
--- /var/folders/zz/zzzivhrRnAmviuee++37O++-GKU/-Tmp-/g4-84328/cache/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.c#672008-06-30 14:32:01.000000000 -0400
+++ /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.c	2008-06-30 15:06:02.000000000 -0400
@@ -565,9 +565,7 @@
 void
 dump_constraint (FILE *file, constraint_t c)
 {
-  if (c->lhs.type == ADDRESSOF)
-    fprintf (file, "&");
-  else if (c->lhs.type == DEREF)
+  if (c->lhs.type == DEREF)
     fprintf (file, "*");
   fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
   if (c->lhs.offset != 0)
@@ -610,6 +608,84 @@
   dump_constraints (stderr);
 }
 
+/* Print out to FILE the edge in the constraint graph that is created by
+   constraint c. */
+
+void
+dump_constraint_edge (FILE *file, constraint_t c)
+{
+  if(c->rhs.type != ADDRESSOF)
+    {
+      const char * src = get_varinfo_fc (c->rhs.var)->name;
+      const char * dst = get_varinfo_fc (c->lhs.var)->name;
+      fprintf(file, "  \"%s\" -> \"%s\" ", src, dst);
+      // Due to preprossecing of constraints, code like *a = *b is illegal
+      if (c->lhs.type == DEREF)
+        fprintf(file, " [ label=\"*=\"] ;\n");
+      else if (c->rhs.type == DEREF)
+        fprintf(file, " [ label=\"=*\"] ;\n");
+      else
+        fprintf(file, " ;\n");
+    }
+}
+
+/* Print the constraint graph in dot format.  */
+
+void
+dump_constraint_graph (FILE *file)
+{
+  unsigned int i=0;
+  constraint_t c;
+
+  // Only print the graph if it has already been initialized:
+  if(!graph)
+    return;
+
+  // Print the constraints that give origin to the constraint graph. The
+  // constraints will be printed as comments in the dot file:
+  fprintf(file, "\n\n/*\n");
+  fprintf(file, "Constraints used to produce the constraint graph:\n");
+  dump_constraints (file);
+  fprintf(file, "*/\n");
+
+  // Prints the header of the dot file:
+  fprintf(file, "\n\n// The constraing graph in dot format:\n");
+  fprintf(file, "strict digraph {\n");
+  fprintf(file, "  node [\n    shape = box\n    fontsize = \"10\"\n  ]\n");
+  fprintf(file, "  edge [\n    fontsize = \"12\"\n  ]\n");
+  fprintf(file, "\n  // List of nodes in the constraint graph:\n");
+
+  // The next lines print the nodes in the graph. In order to get the
+  // number of nodes in the graph, we must choose the minimum between the
+  // vector VEC(varinfo_t, varmap) and graph->size. If the graph has not
+  // yet been initialized, then graph->size == 0, otherwise we must only
+  // read nodes that have an entry in VEC(varinfo_t, varmap).
+  unsigned int size = VEC_length (varinfo_t, varmap);
+  size = size < graph->size ? size : graph->size;
+  for (i = 0; i < size; i++)
+    {
+      const char * name = get_varinfo_fc(graph->rep[i])->name;
+      fprintf(file, "  \"%s\" ;\n", name);
+    }
+
+  // Go over the list of constraints printing the edges in the constraint
+  // graph.
+  fprintf(file, "\n  // The constraint edges:\n");
+  for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
+    dump_constraint_edge (file, c);
+
+  // Prints the tail of the dot file. By now, only the closing bracket.
+  fprintf(file, "}\n");
+}
+
+/* Print out the constraint graph to stderr.  */
+
+void
+debug_constraint_graph (void)
+{
+  dump_constraint_graph (stderr);
+}
+
 /* SOLVER FUNCTIONS
 
    The solver is a simple worklist solver, that works on the following
@@ -5328,6 +5404,10 @@
   free_var_substitution_info (si);
 
   build_succ_graph ();
+
+  if (dump_file && (dump_flags & TDF_GRAPH))
+    dump_constraint_graph (dump_file);
+
   move_complex_constraints (graph);
 
   if (dump_file)
==== //depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.h#9 - /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.h ====
--- /var/folders/zz/zzzivhrRnAmviuee++37O++-GKU/-Tmp-/g4-84328/cache/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.h#9	2008-06-30 14:32:01.000000000 -0400
+++ /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.h	2008-06-30 13:40:50.000000000 -0400
@@ -64,9 +64,12 @@
 extern void compute_points_to_sets (struct alias_info *);
 extern void delete_points_to_sets (void);
 extern void dump_constraint (FILE *, constraint_t);
+extern void dump_constraint_edge (FILE *, constraint_t);
 extern void dump_constraints (FILE *);
+extern void dump_constraint_graph (FILE *);
 extern void debug_constraint (constraint_t);
 extern void debug_constraints (void);
+extern void debug_constraint_graph (void);
 extern void dump_solution_for_var (FILE *, unsigned int);
 extern void debug_solution_for_var (unsigned int);
 extern void dump_sa_points_to_info (FILE *);
==== //depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-dump.c#19 - /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-dump.c ====
--- /var/folders/zz/zzzivhrRnAmviuee++37O++-GKU/-Tmp-/g4-84328/cache/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-dump.c#19	2008-06-30 15:42:25.000000000 -0400
+++ /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-dump.c	2008-06-30 15:12:50.000000000 -0400
@@ -814,6 +814,7 @@
   {"address", TDF_ADDRESS},
   {"slim", TDF_SLIM},
   {"raw", TDF_RAW},
+  {"graph", TDF_GRAPH},
   {"details", TDF_DETAILS},
   {"stats", TDF_STATS},
   {"blocks", TDF_BLOCKS},

Re: Constraint graph in points-to-analysis

[Fernando Magno Quintao Pereira]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1215 bytes --]


Dear all,

     thank you for your comments. I am sending you a patch that addresses 
your points. Please, send me new feedback. I have regression tested the 
patch on an i686-darwin machine, and there were no new regressions.

best,

Fernando

=========================================================================
Description
     This patch adds to gcc's points-to-analysis module the capacity to
dump the constraint graph produced by the analysis in dot format. It
also adds a command line tag to specify that this information should be
printed.

ChangeLog
2008-06-30  Fernando Pereira <fernando@cs.ucla.edu>

         * tree-ssa-structalias.c (compute_points_to_sets): Add call to
         dump_constraint_graph.
         (dump_constraint_edge): New function.
         (dump_constraint_graph): New function.
         (debug_constraint_graph): New function.
         (dump_constraint): Removed useless comparison.
         * tree-ssa-structalias.h (dump_constraint_edge): Declare.
         (dump_constraint_graph): Declare.
         (debug_constraint_graph): Declare.
         * tree-dump.c (struct dump_option_value_info): Declare
         TDF_DETAILS.

Bootstrapping and testing
         i686-apple-darwin

[-- Attachment #2: Type: TEXT/PLAIN, Size: 5918 bytes --]

==== //depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.c#67 - /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.c ====
--- /var/folders/zz/zzzivhrRnAmviuee++37O++-GKU/-Tmp-/g4-84328/cache/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.c#67	2008-07-01 15:23:51.000000000 -0400
+++ /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.c	2008-07-01 15:21:19.000000000 -0400
@@ -565,9 +565,7 @@
 void
 dump_constraint (FILE *file, constraint_t c)
 {
-  if (c->lhs.type == ADDRESSOF)
-    fprintf (file, "&");
-  else if (c->lhs.type == DEREF)
+  if (c->lhs.type == DEREF)
     fprintf (file, "*");
   fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
   if (c->lhs.offset != 0)
@@ -610,6 +608,85 @@
   dump_constraints (stderr);
 }
 
+/* Print out to FILE the edge in the constraint graph that is created by
+   constraint c.  */
+
+void
+dump_constraint_edge (FILE *file, constraint_t c)
+{
+  if(c->rhs.type != ADDRESSOF)
+    {
+      const char * src = get_varinfo_fc (c->rhs.var)->name;
+      const char * dst = get_varinfo_fc (c->lhs.var)->name;
+      fprintf(file, "  \"%s\" -> \"%s\" ", src, dst);
+      /* Due to preprossecing of constraints, instructions like *a = *b are
+         illegal; thus, we do not have to handle such cases.  */
+      if (c->lhs.type == DEREF)
+        fprintf(file, " [ label=\"*=\"] ;\n");
+      else if (c->rhs.type == DEREF)
+        fprintf(file, " [ label=\"=*\"] ;\n");
+      else
+        fprintf(file, " ;\n");
+    }
+}
+
+/* Print the constraint graph in dot format.  */
+
+void
+dump_constraint_graph (FILE *file)
+{
+  unsigned int i=0;
+  constraint_t c;
+
+  /* Only print the graph if it has already been initialized:  */
+  if(!graph)
+    return;
+
+  /* Print the constraints that give origin to the constraint graph. The
+     constraints will be printed as comments in the dot file:  */
+  fprintf(file, "\n\n/*\n");
+  fprintf(file, "Constraints used to produce the constraint graph:\n");
+  dump_constraints (file);
+  fprintf(file, "*/\n");
+
+  /* Prints the header of the dot file:  */
+  fprintf(file, "\n\n// The constraing graph in dot format:\n");
+  fprintf(file, "strict digraph {\n");
+  fprintf(file, "  node [\n    shape = box\n    fontsize = \"10\"\n  ]\n");
+  fprintf(file, "  edge [\n    fontsize = \"12\"\n  ]\n");
+  fprintf(file, "\n  // List of nodes in the constraint graph:\n");
+
+  /* The next lines print the nodes in the graph. In order to get the
+     number of nodes in the graph, we must choose the minimum between the
+     vector VEC(varinfo_t, varmap) and graph->size. If the graph has not
+     yet been initialized, then graph->size == 0, otherwise we must only
+     read nodes that have an entry in VEC(varinfo_t, varmap).  */
+  unsigned int size = VEC_length (varinfo_t, varmap);
+  size = size < graph->size ? size : graph->size;
+  for (i = 0; i < size; i++)
+    {
+      const char * name = get_varinfo_fc(graph->rep[i])->name;
+      fprintf(file, "  \"%s\" ;\n", name);
+    }
+
+  /* Go over the list of constraints printing the edges in the constraint
+     graph.  */
+  fprintf(file, "\n  // The constraint edges:\n");
+  for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
+    dump_constraint_edge (file, c);
+
+  /* Prints the tail of the dot file. By now, only the closing bracket.  */
+  fprintf(file, "}\n");
+}
+
+/* Print out the constraint graph to stderr.  */
+
+void
+debug_constraint_graph (void)
+{
+  dump_constraint_graph (stderr);
+}
+
 /* SOLVER FUNCTIONS
 
    The solver is a simple worklist solver, that works on the following
@@ -5328,6 +5405,10 @@
   free_var_substitution_info (si);
 
   build_succ_graph ();
+
+  if (dump_file && (dump_flags & TDF_GRAPH))
+    dump_constraint_graph (dump_file);
+
   move_complex_constraints (graph);
 
   if (dump_file)
==== //depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.h#9 - /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.h ====
--- /var/folders/zz/zzzivhrRnAmviuee++37O++-GKU/-Tmp-/g4-84328/cache/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.h#9	2008-07-01 15:23:51.000000000 -0400
+++ /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.h	2008-06-30 13:40:50.000000000 -0400
@@ -64,9 +64,12 @@
 extern void compute_points_to_sets (struct alias_info *);
 extern void delete_points_to_sets (void);
 extern void dump_constraint (FILE *, constraint_t);
+extern void dump_constraint_edge (FILE *, constraint_t);
 extern void dump_constraints (FILE *);
+extern void dump_constraint_graph (FILE *);
 extern void debug_constraint (constraint_t);
 extern void debug_constraints (void);
+extern void debug_constraint_graph (void);
 extern void dump_solution_for_var (FILE *, unsigned int);
 extern void debug_solution_for_var (unsigned int);
 extern void dump_sa_points_to_info (FILE *);
==== //depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-dump.c#19 - /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-dump.c ====
--- /var/folders/zz/zzzivhrRnAmviuee++37O++-GKU/-Tmp-/g4-84328/cache/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-dump.c#19	2008-07-01 15:23:52.000000000 -0400
+++ /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-dump.c	2008-06-30 15:12:50.000000000 -0400
@@ -814,6 +814,7 @@
   {"address", TDF_ADDRESS},
   {"slim", TDF_SLIM},
   {"raw", TDF_RAW},
+  {"graph", TDF_GRAPH},
   {"details", TDF_DETAILS},
   {"stats", TDF_STATS},
   {"blocks", TDF_BLOCKS},

Re: Constraint graph in points-to-analysis

[Tom Tromey]

>>>>> "Fernando" == Fernando Magno Quintao Pereira <fernando@CS.UCLA.EDU> writes:

Fernando> Please, send me new feedback.

A couple formatting nits...

Fernando> +  if(c->rhs.type != ADDRESSOF)

You need a space before the '('.
This occurs in many places, e.g. the fprintf()s in this function.

Fernando> +      const char * src = get_varinfo_fc (c->rhs.var)->name;

No space after the "*" in gcc style.
This occurs in a couple places.

Tom

Re: Constraint graph in points-to-analysis

[Fernando Magno Quintao Pereira]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1195 bytes --]


Thank you all for the feedback.

I have fixed the formatting, added new comments and added code to label 
constraints with offsets. Please, send further comments. I have recompiled 
and tested the new patch.

best,

Fernando

=======================================================================

Description
     This patch adds to gcc's points-to-analysis module the capacity to
dump the constraint graph produced by the analysis in dot format. It
also adds a command line tag to specify that this information should be
printed.

ChangeLog
2008-06-30  Fernando Pereira <fernando@cs.ucla.edu>

         * tree-ssa-structalias.c (compute_points_to_sets): Add call to
         dump_constraint_graph.
         (dump_constraint_edge): New function.
         (dump_constraint_graph): New function.
         (debug_constraint_graph): New function.
         (dump_constraint): Removed useless comparison.
         * tree-ssa-structalias.h (dump_constraint_edge): Declare.
         (dump_constraint_graph): Declare.
         (debug_constraint_graph): Declare.
         * tree-dump.c (struct dump_option_value_info): Declare
         TDF_DETAILS.

Bootstrapping and testing
         i686-apple-darwin

[-- Attachment #2: Type: TEXT/PLAIN, Size: 6512 bytes --]

==== //depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.c#67 - /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.c ====
--- /var/folders/zz/zzzivhrRnAmviuee++37O++-GKU/-Tmp-/g4-84328/cache/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.c#67	2008-07-01 15:23:51.000000000 -0400
+++ /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.c	2008-07-01 17:18:26.000000000 -0400
@@ -565,9 +565,7 @@
 void
 dump_constraint (FILE *file, constraint_t c)
 {
-  if (c->lhs.type == ADDRESSOF)
-    fprintf (file, "&");
-  else if (c->lhs.type == DEREF)
+  if (c->lhs.type == DEREF)
     fprintf (file, "*");
   fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
   if (c->lhs.offset != 0)
@@ -610,6 +608,96 @@
   dump_constraints (stderr);
 }
 
+/* Print out to FILE the edge in the constraint graph that is created by
+   constraint c. The edge may have a label, depending on the type of
+   constraint that it represents. If complex1, e.g: a = *b, then the label
+   is "=*", if complex2, e.g: *a = b, then the label is "*=", if
+   complex with an offset, e.g: a = b + 8, then the label is "+".
+   Otherwise the edge has no label.  */
+
+void
+dump_constraint_edge (FILE *file, constraint_t c)
+{
+  if (c->rhs.type != ADDRESSOF)
+    {
+      const char *src = get_varinfo_fc (c->rhs.var)->name;
+      const char *dst = get_varinfo_fc (c->lhs.var)->name;
+      fprintf (file, "  \"%s\" -> \"%s\" ", src, dst);
+      /* Due to preprossecing of constraints, instructions like *a = *b are
+         illegal; thus, we do not have to handle such cases.  */
+      if (c->lhs.type == DEREF)
+        fprintf (file, " [ label=\"*=\" ] ;\n");
+      else if (c->rhs.type == DEREF)
+        fprintf (file, " [ label=\"=*\" ] ;\n");
+      else
+        {
+          /* We must check the case where the constraint is an offset.
+             In this case, it is treated as a complex constraint.  */
+          if (c->rhs.offset != c->lhs.offset)
+            fprintf (file, " [ label=\"+\" ] ;\n");
+          else
+            fprintf (file, " ;\n");
+        }
+    }
+}
+
+/* Print the constraint graph in dot format.  */
+
+void
+dump_constraint_graph (FILE *file)
+{
+  unsigned int i=0;
+  constraint_t c;
+
+  /* Only print the graph if it has already been initialized:  */
+  if (!graph)
+    return;
+
+  /* Print the constraints that give origin to the constraint graph. The
+     constraints will be printed as comments in the dot file:  */
+  fprintf (file, "\n\n/*\n");
+  fprintf (file, "Constraints used to produce the constraint graph:\n");
+  dump_constraints (file);
+  fprintf (file, "*/\n");
+
+  /* Prints the header of the dot file:  */
+  fprintf (file, "\n\n// The constraing graph in dot format:\n");
+  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 in the constraint graph:\n");
+
+  /* The next lines print the nodes in the graph. In order to get the
+     number of nodes in the graph, we must choose the minimum between the
+     vector VEC (varinfo_t, varmap) and graph->size. If the graph has not
+     yet been initialized, then graph->size == 0, otherwise we must only
+     read nodes that have an entry in VEC (varinfo_t, varmap).  */
+  unsigned int size = VEC_length (varinfo_t, varmap);
+  size = size < graph->size ? size : graph->size;
+  for (i = 0; i < size; i++)
+    {
+      const char *name = get_varinfo_fc (graph->rep[i])->name;
+      fprintf (file, "  \"%s\" ;\n", name);
+    }
+
+  /* Go over the list of constraints printing the edges in the constraint
+     graph.  */
+  fprintf (file, "\n  // The constraint edges:\n");
+  for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
+    dump_constraint_edge (file, c);
+
+  /* Prints the tail of the dot file. By now, only the closing bracket.  */
+  fprintf (file, "}\n\n\n");
+}
+
+/* Print out the constraint graph to stderr.  */
+
+void
+debug_constraint_graph (void)
+{
+  dump_constraint_graph (stderr);
+}
+
 /* SOLVER FUNCTIONS
 
    The solver is a simple worklist solver, that works on the following
@@ -5328,6 +5416,10 @@
   free_var_substitution_info (si);
 
   build_succ_graph ();
+
+  if (dump_file && (dump_flags & TDF_GRAPH))
+    dump_constraint_graph (dump_file);
+
   move_complex_constraints (graph);
 
   if (dump_file)
==== //depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.h#9 - /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.h ====
--- /var/folders/zz/zzzivhrRnAmviuee++37O++-GKU/-Tmp-/g4-84328/cache/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.h#9	2008-07-01 15:23:51.000000000 -0400
+++ /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.h	2008-06-30 13:40:50.000000000 -0400
@@ -64,9 +64,12 @@
 extern void compute_points_to_sets (struct alias_info *);
 extern void delete_points_to_sets (void);
 extern void dump_constraint (FILE *, constraint_t);
+extern void dump_constraint_edge (FILE *, constraint_t);
 extern void dump_constraints (FILE *);
+extern void dump_constraint_graph (FILE *);
 extern void debug_constraint (constraint_t);
 extern void debug_constraints (void);
+extern void debug_constraint_graph (void);
 extern void dump_solution_for_var (FILE *, unsigned int);
 extern void debug_solution_for_var (unsigned int);
 extern void dump_sa_points_to_info (FILE *);
==== //depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-dump.c#19 - /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-dump.c ====
--- /var/folders/zz/zzzivhrRnAmviuee++37O++-GKU/-Tmp-/g4-84328/cache/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-dump.c#19	2008-07-01 15:23:52.000000000 -0400
+++ /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-dump.c	2008-06-30 15:12:50.000000000 -0400
@@ -814,6 +814,7 @@
   {"address", TDF_ADDRESS},
   {"slim", TDF_SLIM},
   {"raw", TDF_RAW},
+  {"graph", TDF_GRAPH},
   {"details", TDF_DETAILS},
   {"stats", TDF_STATS},
   {"blocks", TDF_BLOCKS},

Re: Constraint graph in points-to-analysis

[Ralf Wildenhues]

Hello Fernando,

a couple of typo nits:

* Fernando Magno Quintao Pereira wrote on Tue, Jul 01, 2008 at 11:39:26PM CEST:
> --- /var/folders/zz/zzzivhrRnAmviuee++37O++-GKU/-Tmp-/g4-84328/cache/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.c#67	2008-07-01 15:23:51.000000000 -0400
> +++ /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.c	2008-07-01 17:18:26.000000000 -0400

> +void
> +dump_constraint_edge (FILE *file, constraint_t c)
> +{
> +  if (c->rhs.type != ADDRESSOF)
> +    {
> +      const char *src = get_varinfo_fc (c->rhs.var)->name;
> +      const char *dst = get_varinfo_fc (c->lhs.var)->name;
> +      fprintf (file, "  \"%s\" -> \"%s\" ", src, dst);
> +      /* Due to preprossecing of constraints, instructions like *a = *b are

s/preprossecing/preprocessing/

> +         illegal; thus, we do not have to handle such cases.  */

> +  /* Prints the header of the dot file:  */
> +  fprintf (file, "\n\n// The constraing graph in dot format:\n");

s/constraing/constraint/

Cheers,
Ralf

Re: Constraint graph in points-to-analysis

[Fernando Magno Quintao Pereira]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1111 bytes --]


Thanks, Ralf and Tom.

I have fixed the typos and formatting, and I am resending the patch. 
Please, send further comments.

best,

Fernando

=======================================================================

Description
     This patch adds to gcc's points-to-analysis module the capacity to
dump the constraint graph produced by the analysis in dot format. It
also adds a command line tag to specify that this information should be
printed.

ChangeLog
2008-06-30  Fernando Pereira <fernando@cs.ucla.edu>

         * tree-ssa-structalias.c (compute_points_to_sets): Add call to
         dump_constraint_graph.
         (dump_constraint_edge): New function.
         (dump_constraint_graph): New function.
         (debug_constraint_graph): New function.
         (dump_constraint): Removed useless comparison.
         * tree-ssa-structalias.h (dump_constraint_edge): Declare.
         (dump_constraint_graph): Declare.
         (debug_constraint_graph): Declare.
         * tree-dump.c (struct dump_option_value_info): Declare
         TDF_DETAILS.

Bootstrapping and testing
         i686-apple-darwin

[-- Attachment #2: Type: TEXT/PLAIN, Size: 6508 bytes --]

==== //depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.c#67 - /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.c ====
--- /var/folders/zz/zzzivhrRnAmviuee++37O++-GKU/-Tmp-/g4-84328/cache/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.c#67	2008-07-02 11:18:25.000000000 -0400
+++ /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.c	2008-07-02 11:16:54.000000000 -0400
@@ -565,9 +565,7 @@
 void
 dump_constraint (FILE *file, constraint_t c)
 {
-  if (c->lhs.type == ADDRESSOF)
-    fprintf (file, "&");
-  else if (c->lhs.type == DEREF)
+  if (c->lhs.type == DEREF)
     fprintf (file, "*");
   fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name);
   if (c->lhs.offset != 0)
@@ -610,6 +608,96 @@
   dump_constraints (stderr);
 }
 
+/* Print out to FILE the edge in the constraint graph that is created by
+   constraint c. The edge may have a label, depending on the type of
+   constraint that it represents. If complex1, e.g: a = *b, then the label
+   is "=*", if complex2, e.g: *a = b, then the label is "*=", if
+   complex with an offset, e.g: a = b + 8, then the label is "+".
+   Otherwise the edge has no label.  */
+
+void
+dump_constraint_edge (FILE *file, constraint_t c)
+{
+  if (c->rhs.type != ADDRESSOF)
+    {
+      const char *src = get_varinfo_fc (c->rhs.var)->name;
+      const char *dst = get_varinfo_fc (c->lhs.var)->name;
+      fprintf (file, "  \"%s\" -> \"%s\" ", src, dst);
+      /* Due to preprocessing of constraints, instructions like *a = *b are
+         illegal; thus, we do not have to handle such cases.  */
+      if (c->lhs.type == DEREF)
+        fprintf (file, " [ label=\"*=\" ] ;\n");
+      else if (c->rhs.type == DEREF)
+        fprintf (file, " [ label=\"=*\" ] ;\n");
+      else
+        {
+          /* We must check the case where the constraint is an offset.
+             In this case, it is treated as a complex constraint.  */
+          if (c->rhs.offset != c->lhs.offset)
+            fprintf (file, " [ label=\"+\" ] ;\n");
+          else
+            fprintf (file, " ;\n");
+        }
+    }
+}
+
+/* Print the constraint graph in dot format.  */
+
+void
+dump_constraint_graph (FILE *file)
+{
+  unsigned int i=0;
+  constraint_t c;
+
+  /* Only print the graph if it has already been initialized:  */
+  if (!graph)
+    return;
+
+  /* Print the constraints used to produce the constraint graph. The
+     constraints will be printed as comments in the dot file:  */
+  fprintf (file, "\n\n/*\n");
+  fprintf (file, "Constraints used to produce the constraint graph:\n");
+  dump_constraints (file);
+  fprintf (file, "*/\n");
+
+  /* Prints the header of the dot file:  */
+  fprintf (file, "\n\n// The constraint graph in dot format:\n");
+  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 in the constraint graph:\n");
+
+  /* The next lines print the nodes in the graph. In order to get the
+     number of nodes in the graph, we must choose the minimum between the
+     vector VEC (varinfo_t, varmap) and graph->size. If the graph has not
+     yet been initialized, then graph->size == 0, otherwise we must only
+     read nodes that have an entry in VEC (varinfo_t, varmap).  */
+  unsigned int size = VEC_length (varinfo_t, varmap);
+  size = size < graph->size ? size : graph->size;
+  for (i = 0; i < size; i++)
+    {
+      const char *name = get_varinfo_fc (graph->rep[i])->name;
+      fprintf (file, "  \"%s\" ;\n", name);
+    }
+
+  /* Go over the list of constraints printing the edges in the constraint
+     graph.  */
+  fprintf (file, "\n  // The constraint edges:\n");
+  for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
+    dump_constraint_edge (file, c);
+
+  /* Prints the tail of the dot file. By now, only the closing bracket.  */
+  fprintf (file, "}\n\n\n");
+}
+
+/* Print out the constraint graph to stderr.  */
+
+void
+debug_constraint_graph (void)
+{
+  dump_constraint_graph (stderr);
+}
+
 /* SOLVER FUNCTIONS
 
    The solver is a simple worklist solver, that works on the following
@@ -5328,6 +5416,10 @@
   free_var_substitution_info (si);
 
   build_succ_graph ();
+
+  if (dump_file && (dump_flags & TDF_GRAPH))
+    dump_constraint_graph (dump_file);
+
   move_complex_constraints (graph);
 
   if (dump_file)
==== //depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.h#9 - /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.h ====
--- /var/folders/zz/zzzivhrRnAmviuee++37O++-GKU/-Tmp-/g4-84328/cache/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.h#9	2008-07-02 11:18:25.000000000 -0400
+++ /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-ssa-structalias.h	2008-06-30 13:40:50.000000000 -0400
@@ -64,9 +64,12 @@
 extern void compute_points_to_sets (struct alias_info *);
 extern void delete_points_to_sets (void);
 extern void dump_constraint (FILE *, constraint_t);
+extern void dump_constraint_edge (FILE *, constraint_t);
 extern void dump_constraints (FILE *);
+extern void dump_constraint_graph (FILE *);
 extern void debug_constraint (constraint_t);
 extern void debug_constraints (void);
+extern void debug_constraint_graph (void);
 extern void dump_solution_for_var (FILE *, unsigned int);
 extern void debug_solution_for_var (unsigned int);
 extern void dump_sa_points_to_info (FILE *);
==== //depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-dump.c#19 - /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-dump.c ====
--- /var/folders/zz/zzzivhrRnAmviuee++37O++-GKU/-Tmp-/g4-84328/cache/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-dump.c#19	2008-07-02 11:18:25.000000000 -0400
+++ /Users/fpereira/clientgcc/depot2/gcctools/google_vendor_src_branch/gcc/trunk/gcc/tree-dump.c	2008-06-30 15:12:50.000000000 -0400
@@ -814,6 +814,7 @@
   {"address", TDF_ADDRESS},
   {"slim", TDF_SLIM},
   {"raw", TDF_RAW},
+  {"graph", TDF_GRAPH},
   {"details", TDF_DETAILS},
   {"stats", TDF_STATS},
   {"blocks", TDF_BLOCKS},

Re: Constraint graph in points-to-analysis

[Daniel Berlin]

This is fine, please check it in

On Wed, Jul 2, 2008 at 11:36 AM, Fernando Magno Quintao Pereira
<fernando@cs.ucla.edu> wrote:
>
> Thanks, Ralf and Tom.
>
> I have fixed the typos and formatting, and I am resending the patch. Please,
> send further comments.
>
> best,
>
> Fernando
>
> =======================================================================
>
> Description
>    This patch adds to gcc's points-to-analysis module the capacity to
> dump the constraint graph produced by the analysis in dot format. It
> also adds a command line tag to specify that this information should be
> printed.
>
> ChangeLog
> 2008-06-30  Fernando Pereira <fernando@cs.ucla.edu>
>
>        * tree-ssa-structalias.c (compute_points_to_sets): Add call to
>        dump_constraint_graph.
>        (dump_constraint_edge): New function.
>        (dump_constraint_graph): New function.
>        (debug_constraint_graph): New function.
>        (dump_constraint): Removed useless comparison.
>        * tree-ssa-structalias.h (dump_constraint_edge): Declare.
>        (dump_constraint_graph): Declare.
>        (debug_constraint_graph): Declare.
>        * tree-dump.c (struct dump_option_value_info): Declare
>        TDF_DETAILS.
>
> Bootstrapping and testing
>        i686-apple-darwin