From patchwork Fri Dec 13 18:11:10 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: David Malcolm X-Patchwork-Id: 1209373 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-515956-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="BRDK95MV"; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.b="QPl/dP4y"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 47ZJv913rNz9sPJ for ; Sat, 14 Dec 2019 05:23:16 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-type:content-transfer-encoding; q=dns; s= default; b=hEOeWKBF6pi0pWIJrQLz9RJAB4brc73qHFKsZYs26QnNZZTcEMmJS cAGTJuX9UB8K3M4doAhoS96DZE9psye/ZnHp1qJTA5rzaaxLc3uPiNWEG/6yQf6X qxKkHgm8S1kVzkVEQ2l0LzdUaZXNN6gdPcCOGIjlM2QjE/KqnQXWj4= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-type:content-transfer-encoding; s=default; bh=/MRkFgks5GknKnhSed4FcsCyMFg=; b=BRDK95MVBqwdkqIft+tDCIO2O7UV 8/928Ew28gQt0EHyyr786oDeh7kvzWzXlcRpqVsx+CV+Tgwjx5JP7fxDZNI2sN/w 1cTvKduXW2xTb0fvnt3A4faeMqv8Mdof0CmOfA9xkm3XPyWz7qQhty8BPbTaKHlP nXrpUV7Z0PCnnIg= Received: (qmail 124955 invoked by alias); 13 Dec 2019 18:15:26 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 107812 invoked by uid 89); 13 Dec 2019 18:13:08 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-23.1 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= X-HELO: us-smtp-delivery-1.mimecast.com Received: from us-smtp-1.mimecast.com (HELO us-smtp-delivery-1.mimecast.com) (207.211.31.81) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 13 Dec 2019 18:13:03 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1576260782; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=1Ped2OM8wtQlaGSzNEdE+P4OZgMsxPlJ7y8YCe2u808=; b=QPl/dP4ymbLrl5lStlFrImMEgbU9hetKvL3HgaORZZK9bNWG+uUJ4d6FagNL1inXnmu+dR EDLQXwxRq+8OfqKYWYWzz2BBl7jWXeglOvM3gty29BvtggnExAg3FsUQhl8TKx/Ffj+nRm G/R/g0/WsDqDEZ2/XjBWjsKybL4QEZw= 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-246-2-Gi7KLePuC-QCDbp54Pxg-1; Fri, 13 Dec 2019 13:11:50 -0500 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.phx2.redhat.com [10.5.11.16]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id BDB5018A6EC1 for ; Fri, 13 Dec 2019 18:11:49 +0000 (UTC) Received: from t470.redhat.com (ovpn-117-164.phx2.redhat.com [10.3.117.164]) by smtp.corp.redhat.com (Postfix) with ESMTP id 5C42C5C241; Fri, 13 Dec 2019 18:11:49 +0000 (UTC) From: David Malcolm To: gcc-patches@gcc.gnu.org Cc: David Malcolm Subject: [PATCH 21/45] analyzer: new files: digraph.{cc|h} and shortest-paths.h Date: Fri, 13 Dec 2019 13:11:10 -0500 Message-Id: <20191213181134.1830-22-dmalcolm@redhat.com> In-Reply-To: <20191213181134.1830-1-dmalcolm@redhat.com> References: <20191213181134.1830-1-dmalcolm@redhat.com> MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-IsSubscribed: yes Changed in v4: - Moved from gcc/analyzer to gcc, renaming selftests accordingly - Remove //// comments - Replace auto_client_timevar with TV_ANALYZER_SHORTEST_PATHS This patch adds template classes for directed graphs, their nodes and edges, and for finding the shortest path through such a graph. gcc/ChangeLog: * digraph.cc: New file. * digraph.h: New file. * shortest-paths.h: New file. --- gcc/digraph.cc | 188 +++++++++++++++++++++++++++++++++ gcc/digraph.h | 246 +++++++++++++++++++++++++++++++++++++++++++ gcc/shortest-paths.h | 145 +++++++++++++++++++++++++ 3 files changed, 579 insertions(+) create mode 100644 gcc/digraph.cc create mode 100644 gcc/digraph.h create mode 100644 gcc/shortest-paths.h diff --git a/gcc/digraph.cc b/gcc/digraph.cc new file mode 100644 index 000000000000..4473fad26c50 --- /dev/null +++ b/gcc/digraph.cc @@ -0,0 +1,188 @@ +/* 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 "system.h" +#include "coretypes.h" +#include "diagnostic.h" +#include "graphviz.h" +#include "digraph.h" +#include "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 = 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 = 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 = g.add_test_node ("a"); + test_node *b = g.add_test_node ("b"); + g.add_test_edge (a, b); + + pretty_printer pp; + pp.buffer->stream = 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 = g.add_test_node ("a"); + test_node *b = g.add_test_node ("b"); + test_node *c = g.add_test_node ("d"); + test_node *d = g.add_test_node ("d"); + test_node *e = g.add_test_node ("e"); + test_node *f = g.add_test_node ("f"); + + test_edge *ab = g.add_test_edge (a, b); + test_edge *ac = g.add_test_edge (a, c); + test_edge *cd = g.add_test_edge (c, d); + test_edge *be = g.add_test_edge (b, e); + g.add_test_edge (e, f); + test_edge *cf = g.add_test_edge (c, f); + + shortest_paths sp (g, a); + + test_path path_to_a = sp.get_shortest_path (a); + ASSERT_EQ (path_to_a.m_edges.length (), 0); + + test_path path_to_b = 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 = 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 = 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 = 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 = 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 +digraph_cc_tests () +{ + test_dump_to_dot (); + test_shortest_paths (); +} + +} // namespace selftest + +#endif /* #if CHECKING_P */ diff --git a/gcc/digraph.h b/gcc/digraph.h new file mode 100644 index 000000000000..339a6eaf531e --- /dev/null +++ b/gcc/digraph.h @@ -0,0 +1,246 @@ +/* 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 "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 = 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 = 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) = 0; + + /* Recursively dump the cluster, all nodes, and child clusters. */ + virtual void dump_dot (graphviz_out *gv, const dump_args_t &) const = 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=false;\n"); + pp_string (pp, "compound=true;\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) = default_tree_printer; + pp.buffer->stream = 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 = 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/shortest-paths.h b/gcc/shortest-paths.h new file mode 100644 index 000000000000..45a0a388df7b --- /dev/null +++ b/gcc/shortest-paths.h @@ -0,0 +1,145 @@ +/* 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_timevar tv (TV_ANALYZER_SHORTEST_PATHS); + + auto_vec queue (graph.m_nodes.length ()); + + for (unsigned i = 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] = 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 = -1; + int idx_in_queue_with_min_dist = -1; + int min_dist = INT_MAX; + for (unsigned i = 0; i < queue.length (); i++) + { + int idx = queue[i]; + if (m_dist[queue[i]] < min_dist) + { + min_dist = m_dist[idx]; + idx_with_min_dist = idx; + idx_in_queue_with_min_dist = i; + } + } + gcc_assert (idx_with_min_dist != -1); + gcc_assert (idx_in_queue_with_min_dist != -1); + + // FIXME: this is confusing: there are two indices here + + queue.unordered_remove (idx_in_queue_with_min_dist); + + node_t *n + = 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 = succ->m_dest; + int alt = m_dist[n->m_index] + 1; + if (alt < m_dist[dest->m_index]) + { + m_dist[dest->m_index] = alt; + m_prev[dest->m_index] = 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 = m_prev[to->m_index]->m_src; + } + + result.m_edges.reverse (); + + return result; +} + +#endif /* GCC_ANALYZER_SHORTEST_PATHS_H */