From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 61397 invoked by alias); 16 Nov 2019 01:18:09 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 58862 invoked by uid 89); 16 Nov 2019 01:17:45 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-21.5 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,KAM_SHORT autolearn=ham version=3.3.1 spammy=ORIGIN, typedefs X-HELO: us-smtp-delivery-1.mimecast.com Received: from us-smtp-1.mimecast.com (HELO us-smtp-delivery-1.mimecast.com) (205.139.110.61) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sat, 16 Nov 2019 01:17:40 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1573867058; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=6v9pJgjObxZY7ESnBFDkoznWyEtIszfqAxTvhTBdq/U=; b=OoF28fZw4tDfVC3RzDW7PECHzgl3bBsjdi4HyckUAEaw6Fb0ne+fFybgcYdke8SVTqRhN0 y4fd7eR37lrixouvrylgDGoc2TW9IzVRn6dqAl/JTTvghPtPaC1EKJfSJLlgrUV45c6trg J4h/YknxNW4oK0YSV5DZPKK6xXVx6RU= Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-98-mWW4S-WAPwWWrTvhHRYbkQ-1; Fri, 15 Nov 2019 20:17:36 -0500 Received: from smtp.corp.redhat.com (int-mx07.intmail.prod.int.phx2.redhat.com [10.5.11.22]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 199E21005500 for ; Sat, 16 Nov 2019 01:17:36 +0000 (UTC) Received: from c64.redhat.com (ovpn-112-32.phx2.redhat.com [10.3.112.32]) by smtp.corp.redhat.com (Postfix) with ESMTP id 380F910246FB; Sat, 16 Nov 2019 01:17:35 +0000 (UTC) From: David Malcolm To: gcc-patches@gcc.gnu.org Cc: David Malcolm Subject: [PATCH 26/49] analyzer: new files: digraph.{cc|h} and shortest-paths.h Date: Sat, 16 Nov 2019 01:18:00 -0000 Message-Id: <1573867416-55618-27-git-send-email-dmalcolm@redhat.com> In-Reply-To: <1573867416-55618-1-git-send-email-dmalcolm@redhat.com> References: <1573867416-55618-1-git-send-email-dmalcolm@redhat.com> X-Mimecast-Spam-Score: 0 Content-Type: text/plain; charset=WINDOWS-1252 Content-Transfer-Encoding: quoted-printable X-IsSubscribed: yes X-SW-Source: 2019-11/txt/msg01527.txt.bz2 This patch adds template classes for directed graphs, their nodes and edges, and for finding the shortest path through such a graph. gcc/ChangeLog: * analyzer/digraph.cc: New file. * analyzer/digraph.h: New file. * analyzer/shortest-paths.h: New file. --- gcc/analyzer/digraph.cc | 189 ++++++++++++++++++++++++++++++++ gcc/analyzer/digraph.h | 248 ++++++++++++++++++++++++++++++++++++++= ++++ gcc/analyzer/shortest-paths.h | 147 +++++++++++++++++++++++++ 3 files changed, 584 insertions(+) create mode 100644 gcc/analyzer/digraph.cc create mode 100644 gcc/analyzer/digraph.h create mode 100644 gcc/analyzer/shortest-paths.h diff --git a/gcc/analyzer/digraph.cc b/gcc/analyzer/digraph.cc new file mode 100644 index 0000000..c1fa46e --- /dev/null +++ b/gcc/analyzer/digraph.cc @@ -0,0 +1,189 @@ +/* Template classes for directed graphs. + Copyright (C) 2019 Free Software Foundation, Inc. + Contributed by David Malcolm . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "gcc-plugin.h" +#include "system.h" +#include "coretypes.h" +#include "diagnostic.h" +#include "analyzer/graphviz.h" +#include "analyzer/digraph.h" +#include "analyzer/shortest-paths.h" +#include "selftest.h" + +#if CHECKING_P + +namespace selftest { + +/* A family of digraph classes for writing selftests. */ + +struct test_node; +struct test_edge; +struct test_graph; +struct test_dump_args_t {}; +struct test_cluster; + +struct test_graph_traits +{ + typedef test_node node_t; + typedef test_edge edge_t; + typedef test_graph graph_t; + typedef test_dump_args_t dump_args_t; + typedef test_cluster cluster_t; +}; + +struct test_node : public dnode +{ + test_node (const char *name, int index) : m_name (name), m_index (index)= {} + void dump_dot (graphviz_out *, const dump_args_t &) const OVERRIDE + { + } + + const char *m_name; + int m_index; +}; + +struct test_edge : public dedge +{ + test_edge (node_t *src, node_t *dest) + : dedge (src, dest) + {} + + void dump_dot (graphviz_out *gv, const dump_args_t &) const OVERRIDE + { + gv->println ("%s -> %s;", m_src->m_name, m_dest->m_name); + } +}; + +struct test_graph : public digraph +{ + test_node *add_test_node (const char *name) + { + test_node *result =3D new test_node (name, m_nodes.length ()); + add_node (result); + return result; + } + + test_edge *add_test_edge (test_node *src, test_node *dst) + { + test_edge *result =3D new test_edge (src, dst); + add_edge (result); + return result; + } +}; + +struct test_cluster : public cluster +{ +}; + +struct test_path +{ + auto_vec m_edges; +}; + +/* Smoketest of digraph dumping. */ + +static void +test_dump_to_dot () +{ + test_graph g; + test_node *a =3D g.add_test_node ("a"); + test_node *b =3D g.add_test_node ("b"); + g.add_test_edge (a, b); + + pretty_printer pp; + pp.buffer->stream =3D NULL; + test_dump_args_t dump_args; + g.dump_dot_to_pp (&pp, NULL, dump_args); + + ASSERT_STR_CONTAINS (pp_formatted_text (&pp), + "a -> b;\n"); +} + +/* Test shortest paths from A in this digraph, + where edges run top-to-bottom if not otherwise labeled: + + A + / \ + B C-->D + | | + E | + \ / + F. */ + +static void +test_shortest_paths () +{ + test_graph g; + test_node *a =3D g.add_test_node ("a"); + test_node *b =3D g.add_test_node ("b"); + test_node *c =3D g.add_test_node ("d"); + test_node *d =3D g.add_test_node ("d"); + test_node *e =3D g.add_test_node ("e"); + test_node *f =3D g.add_test_node ("f"); + + test_edge *ab =3D g.add_test_edge (a, b); + test_edge *ac =3D g.add_test_edge (a, c); + test_edge *cd =3D g.add_test_edge (c, d); + test_edge *be =3D g.add_test_edge (b, e); + g.add_test_edge (e, f); + test_edge *cf =3D g.add_test_edge (c, f); + + shortest_paths sp (g, a); + + test_path path_to_a =3D sp.get_shortest_path (a); + ASSERT_EQ (path_to_a.m_edges.length (), 0); + + test_path path_to_b =3D sp.get_shortest_path (b); + ASSERT_EQ (path_to_b.m_edges.length (), 1); + ASSERT_EQ (path_to_b.m_edges[0], ab); + + test_path path_to_c =3D sp.get_shortest_path (c); + ASSERT_EQ (path_to_c.m_edges.length (), 1); + ASSERT_EQ (path_to_c.m_edges[0], ac); + + test_path path_to_d =3D sp.get_shortest_path (d); + ASSERT_EQ (path_to_d.m_edges.length (), 2); + ASSERT_EQ (path_to_d.m_edges[0], ac); + ASSERT_EQ (path_to_d.m_edges[1], cd); + + test_path path_to_e =3D sp.get_shortest_path (e); + ASSERT_EQ (path_to_e.m_edges.length (), 2); + ASSERT_EQ (path_to_e.m_edges[0], ab); + ASSERT_EQ (path_to_e.m_edges[1], be); + + test_path path_to_f =3D sp.get_shortest_path (f); + ASSERT_EQ (path_to_f.m_edges.length (), 2); + ASSERT_EQ (path_to_f.m_edges[0], ac); + ASSERT_EQ (path_to_f.m_edges[1], cf); +} + +/* Run all of the selftests within this file. */ + +void +analyzer_digraph_cc_tests () +{ + test_dump_to_dot (); + test_shortest_paths (); +} + +} // namespace selftest + +#endif /* #if CHECKING_P */ diff --git a/gcc/analyzer/digraph.h b/gcc/analyzer/digraph.h new file mode 100644 index 0000000..5c6a496 --- /dev/null +++ b/gcc/analyzer/digraph.h @@ -0,0 +1,248 @@ +/* Template classes for directed graphs. + Copyright (C) 2019 Free Software Foundation, Inc. + Contributed by David Malcolm . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#ifndef GCC_ANALYZER_DIGRAPH_H +#define GCC_ANALYZER_DIGRAPH_H + +#include "diagnostic.h" +#include "tree-diagnostic.h" /* for default_tree_printer. */ +#include "analyzer/graphviz.h" + +/* Templates for a family of classes: digraph, node, edge, and cluster. + This assumes a traits type with the following typedefs: + node_t: the node class + edge_t: the edge class + dump_args_t: additional args for dot-dumps + cluster_t: the cluster class (for use when generating .dot files). + + Using a template allows for typesafe nodes and edges: a node's + predecessor and successor edges can be of a node-specific edge + subclass, without needing casting. */ + +/* Abstract base class for a node in a directed graph. */ + +template +class dnode +{ + public: + typedef typename GraphTraits::edge_t edge_t; + typedef typename GraphTraits::dump_args_t dump_args_t; + + virtual ~dnode () {} + virtual void dump_dot (graphviz_out *gv, const dump_args_t &args) const = =3D 0; + + auto_vec m_preds; + auto_vec m_succs; +}; + +/* Abstract base class for an edge in a directed graph. */ + +template +class dedge +{ + public: + typedef typename GraphTraits::node_t node_t; + typedef typename GraphTraits::dump_args_t dump_args_t; + + dedge (node_t *src, node_t *dest) + : m_src (src), m_dest (dest) {} + + virtual ~dedge () {} + + virtual void dump_dot (graphviz_out *gv, const dump_args_t &args) const = =3D 0; + + node_t *const m_src; + node_t *const m_dest; +}; + +/* Abstract base class for a directed graph. + This class maintains the vectors of nodes and edges, + and owns the nodes and edges. */ + +template +class digraph +{ + public: + typedef typename GraphTraits::node_t node_t; + typedef typename GraphTraits::edge_t edge_t; + typedef typename GraphTraits::dump_args_t dump_args_t; + typedef typename GraphTraits::cluster_t cluster_t; + + digraph () {} + virtual ~digraph () {} + + void dump_dot_to_pp (pretty_printer *pp, + cluster_t *root_cluster, + const dump_args_t &args) const; + void dump_dot_to_file (FILE *fp, + cluster_t *root_cluster, + const dump_args_t &args) const; + void dump_dot (const char *path, + cluster_t *root_cluster, + const dump_args_t &args) const; + + void add_node (node_t *node); + void add_edge (edge_t *edge); + + auto_delete_vec m_nodes; + auto_delete_vec m_edges; +}; + +/* Abstract base class for splitting dnodes into hierarchical clusters + in the generated .dot file. + + See "Subgraphs and Clusters" within + https://www.graphviz.org/doc/info/lang.html + and e.g. + https://graphviz.gitlab.io/_pages/Gallery/directed/cluster.html + + If a root_cluster is passed to dump_dot*, then all nodes will be + added to it at the start of dumping, via calls to add_node. + + The root cluster can organize the nodes into a hierarchy of + child clusters. + + After all nodes are added to the root cluster, dump_dot will then + be called on it (and not on the nodes themselves). */ + +template +class cluster +{ + public: + typedef typename GraphTraits::node_t node_t; + typedef typename GraphTraits::dump_args_t dump_args_t; + + virtual ~cluster () {} + + virtual void add_node (node_t *node) =3D 0; + + /* Recursively dump the cluster, all nodes, and child clusters. */ + virtual void dump_dot (graphviz_out *gv, const dump_args_t &) const =3D = 0; +}; + +//////////////////////////////////////////////////////////////////////////= // + +/* Write .dot information for this graph to PP, passing ARGS to the nodes + and edges. + If ROOT_CLUSTER is non-NULL, use it to organize the nodes into clusters= . */ + +template +inline void +digraph::dump_dot_to_pp (pretty_printer *pp, + cluster_t *root_cluster, + const dump_args_t &args) const +{ + graphviz_out gv (pp); + + pp_string (pp, "digraph \""); + pp_string (pp, "base"); + pp_string (pp, "\" {\n"); + + gv.indent (); + + pp_string (pp, "overlap=3Dfalse;\n"); + pp_string (pp, "compound=3Dtrue;\n"); + + /* If using clustering, emit all nodes via clusters. */ + if (root_cluster) + { + int i; + node_t *n; + FOR_EACH_VEC_ELT (m_nodes, i, n) + root_cluster->add_node (n); + root_cluster->dump_dot (&gv, args); + } + else + { + /* Otherwise, display all nodes at top level. */ + int i; + node_t *n; + FOR_EACH_VEC_ELT (m_nodes, i, n) + n->dump_dot (&gv, args); + } + + /* Edges. */ + int i; + edge_t *e; + FOR_EACH_VEC_ELT (m_edges, i, e) + e->dump_dot (&gv, args); + + /* Terminate "digraph" */ + gv.outdent (); + pp_string (pp, "}"); + pp_newline (pp); +} + +/* Write .dot information for this graph to FP, passing ARGS to the nodes + and edges. + If ROOT_CLUSTER is non-NULL, use it to organize the nodes into clusters= . */ + +template +inline void +digraph::dump_dot_to_file (FILE *fp, + cluster_t *root_cluster, + const dump_args_t &args) const +{ + pretty_printer pp; + // TODO: + pp_format_decoder (&pp) =3D default_tree_printer; + pp.buffer->stream =3D fp; + dump_dot_to_pp (&pp, root_cluster, args); + pp_flush (&pp); +} + +/* Write .dot information for this graph to a file at PATH, passing ARGS + to the nodes and edges. + If ROOT_CLUSTER is non-NULL, use it to organize the nodes into clusters= . */ + +template +inline void +digraph::dump_dot (const char *path, + cluster_t *root_cluster, + const dump_args_t &args) const +{ + FILE *fp =3D fopen (path, "w"); + dump_dot_to_file (fp, root_cluster, args); + fclose (fp); +} + +/* Add NODE to this DIGRAPH, taking ownership. */ + +template +inline void +digraph::add_node (node_t *node) +{ + m_nodes.safe_push (node); +} + +/* Add EDGE to this digraph, and to the preds/succs of its endpoints. + Take ownership of EDGE. */ + +template +inline void +digraph::add_edge (edge_t *edge) +{ + m_edges.safe_push (edge); + edge->m_dest->m_preds.safe_push (edge); + edge->m_src->m_succs.safe_push (edge); + +} + +#endif /* GCC_ANALYZER_DIGRAPH_H */ diff --git a/gcc/analyzer/shortest-paths.h b/gcc/analyzer/shortest-paths.h new file mode 100644 index 0000000..4738f18 --- /dev/null +++ b/gcc/analyzer/shortest-paths.h @@ -0,0 +1,147 @@ +/* Template class for Dijkstra's algorithm on directed graphs. + Copyright (C) 2019 Free Software Foundation, Inc. + Contributed by David Malcolm . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#ifndef GCC_ANALYZER_SHORTEST_PATHS_H +#define GCC_ANALYZER_SHORTEST_PATHS_H + +#include "timevar.h" + +/* A record of the shortest path to each node in an graph + from the origin node. + The constructor runs Dijkstra's algorithm, and the results are + stored in this class. */ + +template +class shortest_paths +{ +public: + typedef typename GraphTraits::graph_t graph_t; + typedef typename GraphTraits::node_t node_t; + typedef typename GraphTraits::edge_t edge_t; + typedef Path_t path_t; + + shortest_paths (const graph_t &graph, const node_t *origin); + + path_t get_shortest_path (const node_t *to) const; + +private: + const graph_t &m_graph; + + /* For each node (by index), the minimal distance to that node from the + origin. */ + auto_vec m_dist; + + /* For each exploded_node (by index), the previous edge in the shortest + path from the origin. */ + auto_vec m_prev; +}; + +//////////////////////////////////////////////////////////////////////////= // + +/* shortest_paths's constructor. + + Use Dijkstra's algorithm relative to ORIGIN to populate m_dist and + m_prev with enough information to be able to generate Path_t instances + to give the shortest path to any node in GRAPH from ORIGIN. */ + +template +inline +shortest_paths::shortest_paths (const graph_t &graph, + const node_t *origin) +: m_graph (graph), + m_dist (graph.m_nodes.length ()), + m_prev (graph.m_nodes.length ()) +{ + auto_client_timevar tv ("shortest_paths"); + + auto_vec queue (graph.m_nodes.length ()); + + for (unsigned i =3D 0; i < graph.m_nodes.length (); i++) + { + m_dist.quick_push (INT_MAX); + m_prev.quick_push (NULL); + queue.quick_push (i); + } + m_dist[origin->m_index] =3D 0; + + while (queue.length () > 0) + { + /* Get minimal distance in queue. + FIXME: this is O(N^2); replace with a priority queue. */ + int idx_with_min_dist =3D -1; + int idx_in_queue_with_min_dist =3D -1; + int min_dist =3D INT_MAX; + for (unsigned i =3D 0; i < queue.length (); i++) + { + int idx =3D queue[i]; + if (m_dist[queue[i]] < min_dist) + { + min_dist =3D m_dist[idx]; + idx_with_min_dist =3D idx; + idx_in_queue_with_min_dist =3D i; + } + } + gcc_assert (idx_with_min_dist !=3D -1); + gcc_assert (idx_in_queue_with_min_dist !=3D -1); + + // FIXME: this is confusing: there are two indices here + + queue.unordered_remove (idx_in_queue_with_min_dist); + + node_t *n + =3D static_cast (m_graph.m_nodes[idx_with_min_dist]); + + int i; + edge_t *succ; + FOR_EACH_VEC_ELT (n->m_succs, i, succ) + { + // TODO: only for dest still in queue + node_t *dest =3D succ->m_dest; + int alt =3D m_dist[n->m_index] + 1; + if (alt < m_dist[dest->m_index]) + { + m_dist[dest->m_index] =3D alt; + m_prev[dest->m_index] =3D succ; + } + } + } +} + +/* Generate an Path_t instance giving the shortest path to the node + TO from the origin node. */ + +template +inline Path_t +shortest_paths::get_shortest_path (const node_t *to) = const +{ + Path_t result; + + while (m_prev[to->m_index]) + { + result.m_edges.safe_push (m_prev[to->m_index]); + to =3D m_prev[to->m_index]->m_src; + } + + result.m_edges.reverse (); + + return result; +} + +#endif /* GCC_ANALYZER_SHORTEST_PATHS_H */ --=20 1.8.5.3