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 : // The structural analysis is a control flow analysis applied on a flow graph
16 : // of basic blocks which produces a structural tree. The algorithm reduces the
17 : // graph by applying iteratively applying basic block reduction patterns on a
18 : // root node until a stable state (no more reductions are possible). If the
19 : // resulting graph is a single node, the graph is reducible, otherwise it cannot
20 : // be represented as a tree.
21 : //
22 : // Each basic pattern matches a region with a single entry node and single exit
23 : // node (SESE). By definition, incoming edges to a child are forbidden. Thus,
24 : // a pattern reduces the smallest reducible region.
25 : //
26 : // Matching patterns must not overlap otherwise the reduction will not be
27 : // deterministic. In the current implementation, the Sequence reduction is not
28 : // deterministic thus it is possible to obtain different valid trees for the
29 : // same flow graph.
30 : // TODO(etienneb): Add a canonical form for the Sequence nodes.
31 : //
32 : // Example:
33 : //
34 : // (a) /--\ (b) /--\ (c) /--\
35 : // (n0) | (n0) | (n0) |
36 : // / | / | / |
37 : // (n1) | | | | |
38 : // / \ | (n123) | (n1234) |
39 : // (n2) (n3) | | | | |
40 : // \ / | | | | |
41 : // (n4) | (n4) | | |
42 : // / \------/ / \---/ / \---/
43 : // (n5) (n5) (n5)
44 : //
45 : //
46 : // (d) /--\ (e) (n01234) (f) n(012345)
47 : // | | |
48 : // (n01234)| (n5)
49 : // | |
50 : // / \--/
51 : // (n5)
52 : //
53 : // The above graph (also present in the header file) reduces by applying the
54 : // following sequence of transformation:
55 : //
56 : // a) Original graph
57 : // b) Reduce an IfThenElse on (n1), produce (n123).
58 : // c) Reduce a Sequence on (n123), produce (n1234).
59 : // d) Reduce a Repeat on (n1234), produce (n1234) without the back edge.
60 : // e) Reduce a Sequence on (n012345), produce n(012345)
61 : // f) The resulting graph.
62 :
63 : #include "syzygy/block_graph/analysis/control_flow_analysis.h"
64 :
65 : #include <list>
66 : #include <set>
67 : #include <sstream>
68 : #include <stack>
69 :
70 : namespace block_graph {
71 : namespace analysis {
72 : namespace {
73 :
74 : typedef block_graph::analysis::ControlFlowAnalysis::StructuralNode
75 : StructuralNode;
76 : typedef block_graph::BasicBlockSubGraph::BasicBlock BasicBlock;
77 : typedef block_graph::BasicBlockSubGraph::BasicCodeBlock BasicCodeBlock;
78 : typedef block_graph::BasicBlockSubGraph::BasicBlock::Successors Successors;
79 : typedef block_graph::BasicBlockSubGraph::BBCollection BBCollection;
80 : typedef block_graph::BasicBlockSubGraph::BlockDescriptionList
81 : BlockDescriptionList;
82 :
83 : typedef ControlFlowAnalysis::StructuralTree StructuralTree;
84 : typedef std::map<const BasicCodeBlock*, StructuralTree> BasicBlocksRemap;
85 : typedef std::list<StructuralTree*> StructuralTreeList;
86 : typedef std::map<StructuralTree*, StructuralTreeList> AbstractLinks;
87 :
88 : void AddLink(StructuralTree* from,
89 : StructuralTree* to,
90 : AbstractLinks* forward_list,
91 E : AbstractLinks* backward_list) {
92 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), from);
93 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), to);
94 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), forward_list);
95 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), backward_list);
96 E : (*forward_list)[from].push_back(to);
97 E : (*backward_list)[to].push_back(from);
98 E : }
99 :
100 : void RemoveLink(StructuralTree* from,
101 : StructuralTree* to,
102 : AbstractLinks* forward_list,
103 E : AbstractLinks* backward_list) {
104 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), from);
105 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), to);
106 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), forward_list);
107 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), backward_list);
108 :
109 E : StructuralTreeList& sources = (*forward_list)[from];
110 E : StructuralTreeList& destinations = (*backward_list)[to];
111 E : sources.remove(to);
112 E : destinations.remove(from);
113 :
114 E : if (sources.empty())
115 E : forward_list->erase(from);
116 E : if (destinations.empty())
117 E : backward_list->erase(to);
118 E : }
119 :
120 : void MoveLinks(StructuralTree* from,
121 : StructuralTree* to,
122 : AbstractLinks* forward_list,
123 E : AbstractLinks* backward_list) {
124 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), from);
125 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), to);
126 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), forward_list);
127 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), backward_list);
128 :
129 : // Need a copy of the sources because they are updated via RemoveLink/AddLink.
130 E : StructuralTreeList sources = (*forward_list)[from];
131 E : StructuralTreeList::iterator it = sources.begin();
132 E : for (; it != sources.end(); ++it) {
133 E : RemoveLink(from, *it, forward_list, backward_list);
134 E : AddLink(to, *it, forward_list, backward_list);
135 E : }
136 E : }
137 :
138 E : bool SwapNode(bool swap, StructuralTree** node1, StructuralTree** node2) {
139 E : DCHECK_NE(reinterpret_cast<StructuralTree**>(NULL), node1);
140 E : DCHECK_NE(reinterpret_cast<StructuralTree**>(NULL), node2);
141 E : if (swap) {
142 E : StructuralTree* tmp = *node1;
143 E : *node1 = *node2;
144 E : *node2 = tmp;
145 : }
146 :
147 E : return true;
148 E : }
149 :
150 E : bool CheckDistinct(StructuralTree* node1, StructuralTree* node2) {
151 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), node1);
152 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), node2);
153 E : DCHECK_NE(reinterpret_cast<StructuralNode*>(NULL), node1->get());
154 E : DCHECK_NE(reinterpret_cast<StructuralNode*>(NULL), node2->get());
155 E : return node1 != node2;
156 E : }
157 :
158 : bool CheckDistinct(StructuralTree* node1,
159 : StructuralTree* node2,
160 E : StructuralTree* node3) {
161 : if (!CheckDistinct(node1, node2) ||
162 E : !CheckDistinct(node1, node3) ||
163 : !CheckDistinct(node2, node3)) {
164 i : return false;
165 : }
166 E : return true;
167 E : }
168 :
169 : // If |current| has only exactly one link into |links|, returns it into target.
170 : // Otherwise, returns false.
171 : bool MatchUniqueLink(const AbstractLinks& links,
172 : StructuralTree* current,
173 E : StructuralTree** target) {
174 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), current);
175 E : DCHECK_NE(reinterpret_cast<StructuralTree**>(NULL), target);
176 :
177 E : AbstractLinks::const_iterator look = links.find(current);
178 E : if (look == links.end())
179 i : return false;
180 :
181 E : const StructuralTreeList& lst = look->second;
182 E : if (lst.size() != 1)
183 E : return false;
184 :
185 E : *target = lst.front();
186 E : return true;
187 E : }
188 :
189 : // If |current| has only exactly two links into |links|, returns them into
190 : // target1 and target2. Otherwise, returns false.
191 : bool MatchTwoLinks(const AbstractLinks& links,
192 : StructuralTree* current,
193 : StructuralTree** target1,
194 E : StructuralTree** target2) {
195 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), current);
196 E : DCHECK_NE(reinterpret_cast<StructuralTree**>(NULL), target1);
197 E : DCHECK_NE(reinterpret_cast<StructuralTree**>(NULL), target2);
198 :
199 E : AbstractLinks::const_iterator look = links.find(current);
200 E : if (look == links.end())
201 i : return false;
202 :
203 E : const StructuralTreeList& lst = look->second;
204 E : if (lst.size() != 2)
205 E : return false;
206 :
207 E : *target1 = lst.front();
208 E : *target2 = lst.back();
209 E : return true;
210 E : }
211 :
212 : // Check if |current| has only one link into |links|, and validate that this
213 : // link is to |target|. Otherwise, returns false.
214 : bool CheckUniqueLink(const AbstractLinks& links,
215 : StructuralTree* current,
216 E : StructuralTree* target) {
217 E : StructuralTree* matched_target = NULL;
218 E : if (!MatchUniqueLink(links, current, &matched_target))
219 E : return false;
220 :
221 E : if (target != matched_target)
222 E : return false;
223 :
224 E : return true;
225 E : }
226 :
227 : // Check if |current| has only two links into |links|, and validate that those
228 : // links are |target1| and |target2|. Otherwise, returns false.
229 : bool CheckTwoLinks(const AbstractLinks& links,
230 : StructuralTree* current,
231 : StructuralTree* target1,
232 : StructuralTree* target2) {
233 : StructuralTree* matched_target1 = NULL;
234 : StructuralTree* matched_target2 = NULL;
235 : if (!MatchTwoLinks(links, current, &matched_target1, &matched_target2))
236 : return false;
237 :
238 : if (target1 != matched_target1 || target2 != matched_target2)
239 : return false;
240 :
241 : return true;
242 : }
243 :
244 : // Try to reduce a Sequence pattern on |current_node|. Match when |current_node|
245 : // has only one successor and this successor has only |current_node| as
246 : // predecessor. No incoming edges are allowed into the successor.
247 : bool MatchSequenceNode(StructuralTree* current_node,
248 : AbstractLinks* predecessor_links,
249 E : AbstractLinks* successor_links) {
250 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), current_node);
251 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), predecessor_links);
252 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), successor_links);
253 :
254 E : StructuralTree* end_node = NULL;
255 :
256 : // Try to match a SequenceNode.
257 : if (MatchUniqueLink(*successor_links, current_node, &end_node) &&
258 : CheckUniqueLink(*predecessor_links, end_node, current_node) &&
259 E : end_node->get()->kind() != StructuralNode::kStopNode &&
260 : CheckDistinct(current_node, end_node)) {
261 E : current_node->reset(new StructuralNode(StructuralNode::kSequenceNode,
262 : std::move(*current_node),
263 : std::move(*end_node)));
264 :
265 : // Remove internal links.
266 E : RemoveLink(current_node, end_node, successor_links, predecessor_links);
267 :
268 : // Move successor of end_node to current_node links.
269 E : MoveLinks(end_node, current_node, successor_links, predecessor_links);
270 :
271 E : return true;
272 : }
273 :
274 E : return false;
275 E : }
276 :
277 : // Try to reduce an IfThen pattern on |current_node|. A pattern is found when
278 : // |current_node| has only two successors: (then), (end). The (then) node does
279 : // not have other predecessor, except (entry). The (then) node has (end) as
280 : // successor. No incoming edges are allowed into (then).
281 : //
282 : // (entry) (entry,then)
283 : // | \ |
284 : // | (then) -> |
285 : // | / (end)
286 : // |/
287 : // (end)
288 : bool MatchIfThenNode(StructuralTree* current_node,
289 : AbstractLinks* predecessor_links,
290 : AbstractLinks* successor_links,
291 E : bool swap) {
292 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), current_node);
293 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), predecessor_links);
294 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), successor_links);
295 :
296 E : StructuralTree* then_node = NULL;
297 E : StructuralTree* end_node = NULL;
298 :
299 : // Try to match an IfThenNode.
300 : if (MatchTwoLinks(*successor_links, current_node, &then_node, &end_node) &&
301 : SwapNode(swap, &then_node, &end_node) &&
302 : CheckUniqueLink(*successor_links, then_node, end_node) &&
303 E : CheckUniqueLink(*predecessor_links, then_node, current_node) &&
304 : CheckDistinct(current_node, then_node)) {
305 E : current_node->reset(new StructuralNode(StructuralNode::kIfThenNode,
306 : std::move(*current_node),
307 : std::move(*then_node)));
308 :
309 : // Remove internal links.
310 E : RemoveLink(current_node, then_node, successor_links, predecessor_links);
311 E : RemoveLink(then_node, end_node, successor_links, predecessor_links);
312 E : RemoveLink(current_node, end_node, successor_links, predecessor_links);
313 :
314 : // Add the new link.
315 E : AddLink(current_node, end_node, successor_links, predecessor_links);
316 :
317 E : return true;
318 : }
319 :
320 E : return false;
321 E : }
322 :
323 : // Try to reduce an IfThenElse pattern on |current_node|. A pattern is found
324 : // when |current_node| has only two successors: (then), (else). The (then) and
325 : // (else) nodes do not have other predecessor, except (entry). Both (then) and
326 : // (else) nodes have (end) as successor. No incoming edges are allowed into
327 : // (then) and (else).
328 : //
329 : // (entry) (entry,then,else)
330 : // / \ |
331 : // (then) (else) -> |
332 : // \ / (end)
333 : // \ /
334 : // (end)
335 : bool MatchIfThenElseNode(StructuralTree* current_node,
336 : AbstractLinks* predecessor_links,
337 E : AbstractLinks* successor_links) {
338 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), current_node);
339 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), predecessor_links);
340 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), successor_links);
341 :
342 E : StructuralTree* then_node = NULL;
343 E : StructuralTree* else_node = NULL;
344 E : StructuralTree* end_node = NULL;
345 :
346 : // Try to match an IfThenElseNode.
347 : if (MatchTwoLinks(*successor_links, current_node, &then_node, &else_node) &&
348 : MatchUniqueLink(*successor_links, then_node, &end_node) &&
349 : CheckUniqueLink(*successor_links, else_node, end_node) &&
350 : CheckUniqueLink(*predecessor_links, then_node, current_node) &&
351 E : CheckUniqueLink(*predecessor_links, else_node, current_node) &&
352 : CheckDistinct(current_node, then_node, else_node)) {
353 E : current_node->reset(new StructuralNode(
354 : StructuralNode::kIfThenElseNode, std::move(*current_node),
355 : std::move(*then_node), std::move(*else_node)));
356 :
357 : // Remove internal links.
358 E : RemoveLink(current_node, then_node, successor_links, predecessor_links);
359 E : RemoveLink(current_node, else_node, successor_links, predecessor_links);
360 E : RemoveLink(then_node, end_node, successor_links, predecessor_links);
361 E : RemoveLink(else_node, end_node, successor_links, predecessor_links);
362 :
363 : // Add the new link.
364 E : AddLink(current_node, end_node, successor_links, predecessor_links);
365 :
366 E : return true;
367 : }
368 :
369 E : return false;
370 E : }
371 :
372 : // Try to reduce a Repeat pattern on |current_node|. A pattern is found when
373 : // |current_node| has two successors and a back edge to itself.
374 : //
375 : // | /---\ |
376 : // (entry) | -> (entry)
377 : // / \---/ |
378 : // /
379 : //
380 : bool MatchRepeatNode(StructuralTree* current_node,
381 : AbstractLinks* predecessor_links,
382 : AbstractLinks* successor_links,
383 E : bool swap) {
384 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), current_node);
385 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), predecessor_links);
386 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), successor_links);
387 :
388 E : StructuralTree* end_node = NULL;
389 E : StructuralTree* body_node = NULL;
390 :
391 : // Try to match a RepeatNode.
392 : if (MatchTwoLinks(*successor_links, current_node, &body_node, &end_node) &&
393 : SwapNode(swap, &body_node, &end_node) &&
394 E : body_node == current_node &&
395 : body_node != end_node) {
396 E : current_node->reset(
397 : new StructuralNode(StructuralNode::kRepeatNode, std::move(*body_node)));
398 :
399 : // Remove internal links.
400 E : RemoveLink(current_node, current_node, successor_links, predecessor_links);
401 E : RemoveLink(current_node, end_node, successor_links, predecessor_links);
402 :
403 : // Add the new link.
404 E : AddLink(current_node, end_node, successor_links, predecessor_links);
405 :
406 E : return true;
407 : }
408 :
409 E : return false;
410 E : }
411 :
412 : // Try to reduce a While pattern on |current_node|. A pattern is found when
413 : // |current_node| has two successors. The (body) node has a successor to
414 : // (entry), the back edge of the loop. No incoming edges are allowed into
415 : // (body).
416 : //
417 : // | /---\ |
418 : // (entry) \ -> (entry)
419 : // / \ | |
420 : // / (body) |
421 : // \--/
422 : bool MatchWhileNode(StructuralTree* current_node,
423 : AbstractLinks* predecessor_links,
424 : AbstractLinks* successor_links,
425 E : bool swap) {
426 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), current_node);
427 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), predecessor_links);
428 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), successor_links);
429 :
430 E : StructuralTree* body_node = NULL;
431 E : StructuralTree* end_node = NULL;
432 :
433 : // Try to match a RepeatNode.
434 : if (MatchTwoLinks(*successor_links, current_node, &body_node, &end_node) &&
435 : SwapNode(swap, &body_node, &end_node) &&
436 : CheckUniqueLink(*predecessor_links, body_node, current_node) &&
437 E : CheckUniqueLink(*successor_links, body_node, current_node) &&
438 : CheckDistinct(current_node, body_node)) {
439 E : current_node->reset(new StructuralNode(StructuralNode::kWhileNode,
440 : std::move(*current_node),
441 : std::move(*body_node)));
442 :
443 : // Remove internal links.
444 E : RemoveLink(current_node, body_node, successor_links, predecessor_links);
445 E : RemoveLink(body_node, current_node, successor_links, predecessor_links);
446 E : RemoveLink(current_node, end_node, successor_links, predecessor_links);
447 :
448 : // Add the new link.
449 E : AddLink(current_node, end_node, successor_links, predecessor_links);
450 :
451 E : return true;
452 : }
453 :
454 E : return false;
455 E : }
456 :
457 : // Try to reduce a Loop pattern on |current_node|. An infinite loop has only
458 : // one successor to itself.
459 : //
460 : // | /--\ |
461 : // (entry) | -> (entry)
462 : // \--/
463 : bool MatchLoopNode(StructuralTree* current_node,
464 : StructuralTree* stop_node,
465 : AbstractLinks* predecessor_links,
466 E : AbstractLinks* successor_links) {
467 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), current_node);
468 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), predecessor_links);
469 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), successor_links);
470 :
471 E : StructuralTree* body_node = NULL;
472 :
473 : // Try to match a LoopNode.
474 E : if (MatchUniqueLink(*successor_links, current_node, &body_node) &&
475 : body_node == current_node) {
476 E : current_node->reset(new StructuralNode(StructuralNode::kLoopNode,
477 : std::move(*current_node)));
478 :
479 : // Remove internal links.
480 E : RemoveLink(current_node, current_node, successor_links, predecessor_links);
481 :
482 : // Add the new link.
483 E : AddLink(current_node, stop_node, successor_links, predecessor_links);
484 :
485 E : return true;
486 : }
487 :
488 E : return false;
489 E : }
490 :
491 : void DumpStructuralTreeToString(const StructuralNode* tree,
492 : size_t indent,
493 : std::stringstream* out) {
494 : DCHECK_NE(reinterpret_cast<const StructuralNode* >(NULL), tree);
495 : DCHECK_NE(reinterpret_cast<std::stringstream*>(NULL), out);
496 :
497 : std::string indent_string(4 * indent, ' ');
498 :
499 : switch (tree->kind()) {
500 : case StructuralNode::kBaseNode: {
501 : const BasicCodeBlock* bb = tree->root();
502 : BasicCodeBlock::Instructions::const_iterator it =
503 : bb->instructions().begin();
504 : for (; it != bb->instructions().end(); ++it) {
505 : std::string instruction_string;
506 : if (!it->ToString(&instruction_string)) {
507 : *out << "<error>\n";
508 : } else {
509 : *out << indent_string << instruction_string << "\n";
510 : }
511 : }
512 : break;
513 : }
514 : case StructuralNode::kSequenceNode: {
515 : DumpStructuralTreeToString(tree->entry_node(), indent, out);
516 : DumpStructuralTreeToString(tree->sequence_node(), indent, out);
517 : break;
518 : }
519 : case StructuralNode::kIfThenNode: {
520 : *out << indent_string << "IF {\n";
521 : DumpStructuralTreeToString(tree->entry_node(), indent + 1, out);
522 : *out << indent_string << "} THEN {\n";
523 : DumpStructuralTreeToString(tree->then_node(), indent + 1, out);
524 : *out << indent_string << "}\n";
525 : break;
526 : }
527 : case StructuralNode::kIfThenElseNode: {
528 : *out << indent_string << "IF {\n";
529 : DumpStructuralTreeToString(tree->entry_node(), indent + 1, out);
530 : *out << indent_string << "} THEN {\n";
531 : DumpStructuralTreeToString(tree->then_node(), indent + 1, out);
532 : *out << indent_string << "} ELSE {\n";
533 : DumpStructuralTreeToString(tree->else_node(), indent + 1, out);
534 : *out << indent_string << "}\n";
535 : break;
536 : }
537 : case StructuralNode::kRepeatNode: {
538 : *out << indent_string << "REPEAT {\n";
539 : DumpStructuralTreeToString(tree->entry_node(), indent + 1, out);
540 : *out << indent_string << "}";
541 : break;
542 : case StructuralNode::kWhileNode:
543 : *out << indent_string << "WHILE {\n";
544 : DumpStructuralTreeToString(tree->entry_node(), indent + 1, out);
545 : *out << indent_string << "} DO {\n";
546 : DumpStructuralTreeToString(tree->body_node(), indent + 1, out);
547 : *out << indent_string << "}\n";
548 : break;
549 : }
550 : case StructuralNode::kLoopNode: {
551 : *out << indent_string << "LOOP {\n";
552 : DumpStructuralTreeToString(tree->entry_node(), indent + 1, out);
553 : *out << indent_string << "}\n";
554 : break;
555 : }
556 : default: {
557 : NOTREACHED() << "Invalid structural node.";
558 : }
559 : }
560 : }
561 :
562 : } // namespace
563 :
564 : StructuralNode::StructuralNode(Kind kind)
565 E : : kind_(kind), root_(NULL) {
566 E : DCHECK(kind == kStartNode || kind == kStopNode);
567 E : }
568 :
569 : StructuralNode::StructuralNode(Kind kind, const BasicCodeBlock* root)
570 E : : kind_(kind), root_(root) {
571 E : DCHECK_EQ(kBaseNode, kind);
572 E : DCHECK_NE(reinterpret_cast<const BasicCodeBlock*>(NULL), root);
573 E : }
574 :
575 : StructuralNode::StructuralNode(Kind kind, StructuralTree entry_node)
576 E : : kind_(kind), root_(NULL), entry_node_(std::move(entry_node)) {
577 E : root_ = entry_node_->root();
578 E : }
579 :
580 : StructuralNode::StructuralNode(Kind kind,
581 : StructuralTree entry_node,
582 : StructuralTree child1)
583 E : : kind_(kind),
584 E : root_(NULL),
585 E : entry_node_(std::move(entry_node)),
586 E : child1_(std::move(child1)) {
587 E : root_ = entry_node_->root();
588 E : }
589 :
590 : StructuralNode::StructuralNode(Kind kind,
591 : StructuralTree entry_node,
592 : StructuralTree child1,
593 : StructuralTree child2)
594 E : : kind_(kind),
595 E : root_(NULL),
596 E : entry_node_(std::move(entry_node)),
597 E : child1_(std::move(child1)),
598 E : child2_(std::move(child2)) {
599 E : root_ = entry_node_->root();
600 E : }
601 :
602 E : const BasicCodeBlock* StructuralNode::root() const {
603 E : DCHECK_NE(reinterpret_cast<const BasicCodeBlock*>(NULL), root_);
604 E : return root_;
605 E : }
606 :
607 E : const StructuralNode* StructuralNode::entry_node() const {
608 E : DCHECK_NE(reinterpret_cast<const StructuralNode*>(NULL), entry_node_.get());
609 E : return entry_node_.get();
610 E : }
611 :
612 E : const StructuralNode* StructuralNode::sequence_node() const {
613 E : DCHECK_EQ(kind_, kSequenceNode);
614 E : DCHECK_NE(reinterpret_cast<const StructuralNode*>(NULL), child1_.get());
615 E : return child1_.get();
616 E : }
617 :
618 E : const StructuralNode* StructuralNode::then_node() const {
619 E : DCHECK(kind_ == kIfThenNode || kind_ == kIfThenElseNode);
620 E : DCHECK_NE(reinterpret_cast<const StructuralNode*>(NULL), child1_.get());
621 E : return child1_.get();
622 E : }
623 :
624 E : const StructuralNode* StructuralNode::else_node() const {
625 E : DCHECK_EQ(kind_, kIfThenElseNode);
626 E : DCHECK_NE(reinterpret_cast<const StructuralNode*>(NULL), child2_.get());
627 E : return child2_.get();
628 E : }
629 :
630 E : const StructuralNode* StructuralNode::body_node() const {
631 E : DCHECK_EQ(kind_, kWhileNode);
632 E : DCHECK_NE(reinterpret_cast<const StructuralNode*>(NULL), child1_.get());
633 E : return child1_.get();
634 E : }
635 :
636 : bool ControlFlowAnalysis::BuildStructuralTree(
637 : const BasicBlockSubGraph* subgraph,
638 E : StructuralTree* tree) {
639 E : DCHECK_NE(reinterpret_cast<BasicBlockSubGraph*>(NULL), subgraph);
640 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), tree);
641 :
642 : // Get a basic block ordering to reduce graph in reverse order.
643 E : BasicBlockOrdering order;
644 E : FlattenBasicBlocksInPostOrder(subgraph->basic_blocks(), &order);
645 :
646 : // Create a base StructuralNode for each basic block.
647 E : BasicBlocksRemap basic_block_map;
648 E : BasicBlockOrdering::iterator it = order.begin();
649 E : for (; it != order.end(); ++it) {
650 E : basic_block_map[*it].reset(
651 : new StructuralNode(StructuralNode::kBaseNode, *it));
652 E : }
653 :
654 : // Add predecessors/successors to abstract nodes.
655 E : AbstractLinks successor_links;
656 E : AbstractLinks predecessor_links;
657 E : BasicBlocksRemap::iterator node = basic_block_map.begin();
658 E : for (; node != basic_block_map.end(); ++node) {
659 E : const BasicCodeBlock* bb = node->first;
660 E : StructuralTree* current_node = &node->second;
661 :
662 : // For each successor add links between predecessor and successor.
663 E : const Successors& successors = bb->successors();
664 E : Successors::const_iterator succ = successors.begin();
665 E : for (; succ != successors.end(); ++succ) {
666 : BasicCodeBlock* next_bb =
667 E : BasicCodeBlock::Cast(succ->reference().basic_block());
668 E : if (next_bb == NULL)
669 i : continue;
670 E : StructuralTree* succ_node = &basic_block_map[next_bb];
671 E : AddLink(current_node, succ_node, &successor_links, &predecessor_links);
672 E : }
673 E : }
674 :
675 : // Create a start and a stop node to manage block entry/exit. Those node
676 : // must never be folded by the fixed-point reduction.
677 E : StructuralTree start_node;
678 E : StructuralTree stop_node;
679 E : start_node.reset(new StructuralNode(StructuralNode::kStartNode));
680 E : stop_node.reset(new StructuralNode(StructuralNode::kStopNode));
681 :
682 E : const BlockDescriptionList& descriptions = subgraph->block_descriptions();
683 E : DCHECK(!descriptions.empty());
684 E : BlockDescriptionList::const_iterator description = descriptions.begin();
685 E : for (; description != descriptions.end(); ++description) {
686 E : CHECK(!description->basic_block_order.empty());
687 : const BasicCodeBlock* bb =
688 E : BasicCodeBlock::Cast(description->basic_block_order.front());
689 E : if (bb == NULL)
690 i : return false;
691 E : StructuralTree& current = basic_block_map[bb];
692 E : AddLink(&start_node, ¤t, &successor_links, &predecessor_links);
693 E : }
694 :
695 : // Find unconnected starting and ending nodes and add missing links.
696 E : node = basic_block_map.begin();
697 E : for (; node != basic_block_map.end(); ++node) {
698 E : StructuralTree& current = node->second;
699 E : if (successor_links.find(¤t) == successor_links.end())
700 E : AddLink(¤t, &stop_node, &successor_links, &predecessor_links);
701 E : if (predecessor_links.find(¤t) == predecessor_links.end())
702 E : AddLink(&start_node, ¤t, &successor_links, &predecessor_links);
703 E : }
704 :
705 : // Fixed-point reduction. To guarantee ending of the algorithm, the number of
706 : // active nodes/links must be smaller at each iteration.
707 : bool changed;
708 : do {
709 E : changed = false;
710 :
711 E : BasicBlockOrdering::iterator bb = order.begin();
712 E : while (bb != order.end()) {
713 E : BasicBlocksRemap::iterator look = basic_block_map.find(*bb);
714 :
715 : // This node is already reduced.
716 E : if (look == basic_block_map.end()) {
717 E : ++bb;
718 E : continue;
719 : }
720 :
721 : // This node has been reduced, but not removed from active set.
722 E : if (look->second.get() == NULL) {
723 E : basic_block_map.erase(look);
724 E : changed = true;
725 E : continue;
726 : }
727 :
728 : // Try to match a pattern at a given root node.
729 E : StructuralTree* current_node = &look->second;
730 : if (MatchSequenceNode(current_node,
731 : &predecessor_links,
732 : &successor_links) ||
733 : MatchIfThenNode(current_node,
734 : &predecessor_links,
735 : &successor_links,
736 : false) ||
737 : MatchIfThenNode(current_node,
738 : &predecessor_links,
739 : &successor_links,
740 : true) ||
741 : MatchIfThenElseNode(current_node,
742 : &predecessor_links,
743 : &successor_links) ||
744 : MatchRepeatNode(current_node,
745 : &predecessor_links,
746 : &successor_links,
747 : false) ||
748 : MatchRepeatNode(current_node,
749 : &predecessor_links,
750 : &successor_links,
751 : true) ||
752 : MatchWhileNode(current_node,
753 : &predecessor_links,
754 : &successor_links,
755 : false) ||
756 : MatchWhileNode(current_node,
757 : &predecessor_links,
758 : &successor_links,
759 E : true) ||
760 : MatchLoopNode(current_node,
761 : &stop_node,
762 : &predecessor_links,
763 : &successor_links)) {
764 E : changed = true;
765 E : continue;
766 : }
767 :
768 : // Move to the next basic block.
769 E : ++bb;
770 E : }
771 E : } while (changed);
772 :
773 : // The graph must be reduced to a unique root node.
774 E : if (basic_block_map.size() != 1)
775 E : return false;
776 :
777 : // If reducing the graph is successful, returns the reduced tree.
778 : // The reduced graph must be: start -> tree -> stop.
779 E : StructuralTree* reduced_tree = NULL;
780 : if (MatchUniqueLink(successor_links, &start_node, &reduced_tree) &&
781 : CheckUniqueLink(predecessor_links, reduced_tree, &start_node) &&
782 E : CheckUniqueLink(successor_links, reduced_tree, &stop_node) &&
783 : CheckUniqueLink(predecessor_links, &stop_node, reduced_tree)) {
784 E : *tree = std::move(*reduced_tree);
785 E : return true;
786 : }
787 :
788 : // TODO(etienneb): Return a forest of (partially reduced) trees when the graph
789 : // is irreducible.
790 i : return false;
791 E : }
792 :
793 : bool ControlFlowAnalysis::StructuralNode::ToString(std::string* str) const {
794 : std::stringstream out;
795 : DumpStructuralTreeToString(this, 0, &out);
796 : *str = out.str();
797 : return true;
798 : }
799 :
800 : void ControlFlowAnalysis::FlattenBasicBlocksInPostOrder(
801 : const BBCollection& basic_blocks,
802 E : std::vector<const BasicCodeBlock*>* order) {
803 E : DCHECK(order != NULL);
804 :
805 : // Build a reverse post-order (RPO) ordering of basic blocks. This is needed
806 : // for faster fix-point convergence, but works with any ordering.
807 E : std::set<BasicBlock*> marked;
808 E : std::stack<BasicBlock*> working;
809 :
810 : // For each basic block, flatten its reachable sub-tree in post-order.
811 E : BBCollection::const_iterator iter_end = basic_blocks.end();
812 E : for (BBCollection::const_iterator iter = basic_blocks.begin();
813 E : iter != iter_end; ++iter) {
814 : // When not marked, mark it and add it to working stack.
815 E : if (marked.insert(*iter).second)
816 E : working.push(*iter);
817 :
818 : // Flatten this tree without following back edges, push them in post-order.
819 E : while (!working.empty()) {
820 E : const BasicBlock* top = working.top();
821 :
822 : // Skip data basic block.
823 E : const BasicCodeBlock* bb = BasicCodeBlock::Cast(top);
824 E : if (bb == NULL) {
825 E : working.pop();
826 E : continue;
827 : }
828 :
829 : // Add unvisited child to the working stack.
830 E : bool has_unvisited_child = false;
831 E : const BasicBlock::Successors& successors = bb->successors();
832 E : Successors::const_iterator succ_end = successors.end();
833 E : for (Successors::const_iterator succ = successors.begin();
834 E : succ != succ_end; ++succ) {
835 E : BasicBlock* basic_block = succ->reference().basic_block();
836 : // When not marked, mark it and add it to working stack.
837 E : if (marked.insert(basic_block).second) {
838 E : working.push(basic_block);
839 E : has_unvisited_child = true;
840 E : break;
841 : }
842 E : }
843 :
844 E : if (!has_unvisited_child) {
845 : // Push this basic block in post-order in the ordering.
846 E : order->push_back(bb);
847 E : working.pop();
848 : }
849 E : }
850 E : }
851 E : }
852 :
853 : } // namespace analysis
854 : } // namespace block_graph
|