Constraint graph in points-to-analysis
Fernando Magno Quintao Pereira
fernando@CS.UCLA.EDU
Wed Jul 2 15:39:00 GMT 2008
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
-------------- next part --------------
==== //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},
More information about the Gcc-patches
mailing list