1/*
2 * Copyright (C) 2016-2019 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#include <wtf/FastMalloc.h>
29#include <wtf/GraphNodeWorklist.h>
30#include <wtf/Noncopyable.h>
31#include <wtf/SingleRootGraph.h>
32#include <wtf/SpanningTree.h>
33#include <wtf/StdLibExtras.h>
34
35namespace WTF {
36
37template<typename Graph>
38class BackwardsGraph {
39 WTF_MAKE_NONCOPYABLE(BackwardsGraph);
40 WTF_MAKE_FAST_ALLOCATED;
41public:
42 using Node = SingleRootGraphNode<Graph>;
43 using Set = SingleRootGraphSet<Graph>;
44 template <typename T> using Map = SingleRootMap<T, Graph>;
45 typedef Vector<Node, 4> List;
46
47 BackwardsGraph(Graph& graph)
48 : m_graph(graph)
49 {
50 GraphNodeWorklist<typename Graph::Node, typename Graph::Set> worklist;
51
52 auto addRootSuccessor = [&] (typename Graph::Node node) {
53 if (worklist.push(node)) {
54 m_rootSuccessorList.append(node);
55 m_rootSuccessorSet.add(node);
56 while (typename Graph::Node node = worklist.pop())
57 worklist.pushAll(graph.predecessors(node));
58 }
59 };
60
61 {
62 // Loops are a form of terminality (you can loop forever). To have a loop, you need to
63 // have a back edge. An edge u->v is a back edge when u is a descendent of v in the
64 // DFS spanning tree of the Graph.
65 SpanningTree<Graph> spanningTree(graph);
66 for (unsigned i = 0; i < graph.numNodes(); ++i) {
67 if (typename Graph::Node node = graph.node(i)) {
68 for (typename Graph::Node successor : graph.successors(node)) {
69 if (spanningTree.isDescendent(node, successor)) {
70 addRootSuccessor(node);
71 break;
72 }
73 }
74 }
75 }
76 }
77
78 for (unsigned i = 0; i < graph.numNodes(); ++i) {
79 if (typename Graph::Node node = graph.node(i)) {
80 if (!graph.successors(node).size())
81 addRootSuccessor(node);
82 }
83 }
84
85 // At this point there will be some nodes in the graph that aren't known to the worklist. We
86 // could add any or all of them to the root successors list. Adding all of them would be a bad
87 // pessimisation. Ideally we would pick the ones that have backward edges but no forward
88 // edges. That would require thinking, so we just use a rough heuristic: add the highest
89 // numbered nodes first, which is totally fine if the input program is already sorted nicely.
90 for (unsigned i = graph.numNodes(); i--;) {
91 if (typename Graph::Node node = graph.node(i))
92 addRootSuccessor(node);
93 }
94 }
95
96 Node root() { return Node::root(); }
97
98 template<typename T>
99 Map<T> newMap() { return Map<T>(m_graph); }
100
101 List successors(const Node& node) const
102 {
103 if (node.isRoot())
104 return m_rootSuccessorList;
105 List result;
106 for (typename Graph::Node predecessor : m_graph.predecessors(node.node()))
107 result.append(predecessor);
108 return result;
109 }
110
111 List predecessors(const Node& node) const
112 {
113 if (node.isRoot())
114 return { };
115
116 List result;
117
118 if (m_rootSuccessorSet.contains(node.node()))
119 result.append(Node::root());
120
121 for (typename Graph::Node successor : m_graph.successors(node.node()))
122 result.append(successor);
123
124 return result;
125 }
126
127 unsigned index(const Node& node) const
128 {
129 if (node.isRoot())
130 return 0;
131 return m_graph.index(node.node()) + 1;
132 }
133
134 Node node(unsigned index) const
135 {
136 if (!index)
137 return Node::root();
138 return m_graph.node(index - 1);
139 }
140
141 unsigned numNodes() const
142 {
143 return m_graph.numNodes() + 1;
144 }
145
146 CString dump(Node node) const
147 {
148 StringPrintStream out;
149 if (!node)
150 out.print("<null>");
151 else if (node.isRoot())
152 out.print(Node::rootName());
153 else
154 out.print(m_graph.dump(node.node()));
155 return out.toCString();
156 }
157
158 void dump(PrintStream& out) const
159 {
160 for (unsigned i = 0; i < numNodes(); ++i) {
161 Node node = this->node(i);
162 if (!node)
163 continue;
164 out.print(dump(node), ":\n");
165 out.print(" Preds: ");
166 CommaPrinter comma;
167 for (Node predecessor : predecessors(node))
168 out.print(comma, dump(predecessor));
169 out.print("\n");
170 out.print(" Succs: ");
171 comma = CommaPrinter();
172 for (Node successor : successors(node))
173 out.print(comma, dump(successor));
174 out.print("\n");
175 }
176 }
177
178private:
179 Graph& m_graph;
180 List m_rootSuccessorList;
181 typename Graph::Set m_rootSuccessorSet;
182};
183
184} // namespace WTF
185
186using WTF::BackwardsGraph;
187