1 : // Copyright 2013 Google Inc. All Rights Reserved.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 : //
15 : /// A class that performs a structural control flow analysis of a subgraph.
16 : //
17 : #ifndef SYZYGY_BLOCK_GRAPH_ANALYSIS_CONTROL_FLOW_ANALYSIS_H_
18 : #define SYZYGY_BLOCK_GRAPH_ANALYSIS_CONTROL_FLOW_ANALYSIS_H_
19 :
20 : #include <vector>
21 :
22 : #include "syzygy/block_graph/basic_block.h"
23 : #include "syzygy/block_graph/basic_block_subgraph.h"
24 :
25 : namespace block_graph {
26 : namespace analysis {
27 :
28 : // This class implements control-flow analysis on a SubGraph.
29 : //
30 : // Control-Flow Ordering
31 : // ----------------------------
32 : // The control-flow analysis provides an ordering analysis. The order allows two
33 : // directions for traversing the flow graph: Post-Order and Reverse Post-Order.
34 : //
35 : // Post-Order:
36 : // This is a typical iteration order for backward data-flow problems. In
37 : // post-order iteration, a node is visited after all its successor nodes
38 : // have been visited.
39 : //
40 : // Reverse Post-Order:
41 : // This is a typical iteration order for forward data-flow problems. In
42 : // reverse post-order iteration, a node is visited before any of its
43 : // successor nodes has been visited (except for back edges).
44 : //
45 : // Example:
46 : //
47 : // const BBCollection& basic_blocks = subgraph->basic_blocks();
48 : // BasicBlockOrdering order;
49 : // ControlFlowAnalysis::FlattenBasicBlocksInPostOrder(basic_blocks, &order);
50 : // BasicBlockOrdering::const_reverse_iterator it = order.rbegin();
51 : // for (; it != order.rend(); ++it) {
52 : // // Perform an action in reverse post order.
53 : // }
54 : //
55 : // This graph will be flattened to: [n5, n4, n2, n3, n1, n0].
56 : //
57 : // /--\
58 : // (n0) |
59 : // / |
60 : // (n1) |
61 : // / \ |
62 : // (n2) (n3) |
63 : // \ / |
64 : // (n4) |
65 : // / \------/
66 : // (n5)
67 : //
68 : // Structural Analysis
69 : // ----------------------------
70 : // The structural analysis is a conservative analysis which tries to reduce the
71 : // flow graph to a structural tree. A structural tree is composed of the basic
72 : // flow operators found in programming language: statement, if, while, loop.
73 : //
74 : // See: "Advanced Compiler Design Implementation", by Steven S. Muchnick.
75 : // Chapter 7.7 Structural Analysis.
76 : //
77 : // Example:
78 : //
79 : // BasicBlockSubGraph subgraph;
80 : // ControlFlowAnalysis::StructuralTree tree;
81 : // bool reducible = ControlFlowAnalysis::BuildStructuralTree(&subgraph, &tree);
82 : // if (reducible) {
83 : // std::string txt;
84 : // CHECK(tree->ToString(&txt));
85 : // LOG(INFO) << "Reduce to:\n" << txt'
86 : // }
87 : //
88 : // The graph on the left reduces to the tree on the right:
89 : //
90 : // /--\ Sequence
91 : // (n0) | / \
92 : // / | Repeat n5
93 : // (n1) | |
94 : // / \ | Sequence
95 : // (n2) (n3) | / \
96 : // \ / | n0 Sequence
97 : // (n4) | / \
98 : // / \------/ IfThenElse \
99 : // (n5) / | \ \
100 : // n1 n2 n3 n4
101 :
102 : class ControlFlowAnalysis {
103 : public:
104 : typedef block_graph::BasicBlockSubGraph BasicBlockSubGraph;
105 : typedef BasicBlockSubGraph::BBCollection BBCollection;
106 : typedef std::vector<const BasicCodeBlock*> BasicBlockOrdering;
107 :
108 : // Forward declaration.
109 : class StructuralNode;
110 : typedef std::unique_ptr<StructuralNode> StructuralTree;
111 :
112 : // Constructor.
113 : ControlFlowAnalysis() { }
114 :
115 : // Construct a structural representation of a given control flow graph.
116 : // @param subgraph SubGraph to apply the structural analysis.
117 : // @param tree receives the structural tree.
118 : // @returns true on success, false otherwise.
119 : static bool BuildStructuralTree(const BasicBlockSubGraph* subgraph,
120 : StructuralTree* tree);
121 :
122 : // Traverse basic blocks in depth first and push basic blocks in post order.
123 : // @param basic_blocks The basic blocks to order.
124 : // @param order Receives the basic blocks in post order.
125 : static void FlattenBasicBlocksInPostOrder(
126 : const BBCollection& basic_blocks,
127 : BasicBlockOrdering* order);
128 :
129 : private:
130 : DISALLOW_COPY_AND_ASSIGN(ControlFlowAnalysis);
131 : };
132 :
133 : // StructuralNode is the building block of the StructuralTree produced by the
134 : // control-flow analysis. The structural tree recursively divides the
135 : // control-flow graph into regions with a single entry node and a single exit
136 : // node. A StructuralNode has a kind which represents the semantics of the
137 : // region and has different child nodes (depending on the kind of node).
138 : //
139 : // Base:
140 : // ===========
141 : // (entry)
142 : // |
143 : // basic-block
144 : //
145 : // Sequential:
146 : // ===========
147 : // Sequence IfThen IfThenElse
148 : //
149 : // (entry) (entry) (entry)
150 : // | | \ / \
151 : // (sequence) | (then) (then) (else)
152 : // | | / \ /
153 : // |/ \ /
154 : // Looping:
155 : // ===========
156 : // Repeat While Loop
157 : //
158 : // | /---\ | /---\ | /---\
159 : // (entry) | (entry) \ (entry) |
160 : // / \----/ / \ | \-----/
161 : // / / (body) |
162 : // \--/
163 :
164 : class ControlFlowAnalysis::StructuralNode {
165 : public:
166 : typedef ControlFlowAnalysis::StructuralTree StructuralTree;
167 :
168 : // Structural node kinds.
169 : enum Kind {
170 : kBaseNode,
171 : kSequenceNode,
172 : kIfThenNode,
173 : kIfThenElseNode,
174 : kRepeatNode,
175 : kWhileNode,
176 : kLoopNode,
177 : // Below this point: internal nodes should not occur in the resulting tree.
178 : kStartNode,
179 : kStopNode,
180 : };
181 :
182 : // @name Constructors.
183 : // @{
184 : // @param kind the kind of the region.
185 : // @param root the entry basic block of the region.
186 : // @param entry_node the entry node of the tree.
187 : // @param child1 the first child of the tree.
188 : // @param child2 the second child of the tree.
189 : explicit StructuralNode(Kind kind);
190 : StructuralNode(Kind kind, const BasicCodeBlock* root);
191 : StructuralNode(Kind kind, StructuralTree entry_node);
192 : StructuralNode(Kind kind,
193 : StructuralTree entry_node,
194 : StructuralTree child1);
195 : StructuralNode(Kind kind,
196 : StructuralTree entry_node,
197 : StructuralTree child1,
198 : StructuralTree child2);
199 : // @}
200 :
201 : // @returns the kind of the region.
202 E : Kind kind() const { return kind_; }
203 :
204 : // @returns the first basic block of the region.
205 : const BasicCodeBlock* root() const;
206 :
207 : // @name Accessors.
208 : // @note The kind of region is validated by the accessors. It is invalid to
209 : // access a field that is not defined for the given node type.
210 : // @{
211 : const StructuralNode* entry_node() const;
212 : const StructuralNode* sequence_node() const;
213 : const StructuralNode* then_node() const;
214 : const StructuralNode* else_node() const;
215 : const StructuralNode* body_node() const;
216 : // @}
217 :
218 : // Produce a textual representation of the tree.
219 : // @param str receives the resulting text.
220 : // @returns true on success, false otherwise.
221 : bool ToString(std::string* str) const;
222 :
223 : private:
224 : // The region kind.
225 : Kind kind_;
226 :
227 : // The entry basic block of the region.
228 : const BasicCodeBlock* root_;
229 :
230 : // Sub-trees of this node.
231 : StructuralTree entry_node_;
232 : StructuralTree child1_;
233 : StructuralTree child2_;
234 : };
235 :
236 : } // namespace analysis
237 : } // namespace block_graph
238 :
239 : #endif // SYZYGY_BLOCK_GRAPH_ANALYSIS_CONTROL_FLOW_ANALYSIS_H_
|