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