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 : !CheckDistinct(node1, node3) ||
163 E : !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 : end_node->get()->kind() != StructuralNode::kStopNode &&
260 E : CheckDistinct(current_node, end_node)) {
261 : current_node->reset(new StructuralNode(StructuralNode::kSequenceNode,
262 : current_node->Pass(),
263 E : end_node->Pass()));
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 : CheckUniqueLink(*predecessor_links, then_node, current_node) &&
304 E : CheckDistinct(current_node, then_node)) {
305 : current_node->reset(new StructuralNode(StructuralNode::kIfThenNode,
306 : current_node->Pass(),
307 E : then_node->Pass()));
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 : CheckUniqueLink(*predecessor_links, else_node, current_node) &&
352 E : CheckDistinct(current_node, then_node, else_node)) {
353 : current_node->reset(new StructuralNode(StructuralNode::kIfThenElseNode,
354 : current_node->Pass(),
355 : then_node->Pass(),
356 E : else_node->Pass()));
357 :
358 : // Remove internal links.
359 E : RemoveLink(current_node, then_node, successor_links, predecessor_links);
360 E : RemoveLink(current_node, else_node, successor_links, predecessor_links);
361 E : RemoveLink(then_node, end_node, successor_links, predecessor_links);
362 E : RemoveLink(else_node, end_node, successor_links, predecessor_links);
363 :
364 : // Add the new link.
365 E : AddLink(current_node, end_node, successor_links, predecessor_links);
366 :
367 E : return true;
368 : }
369 :
370 E : return false;
371 E : }
372 :
373 : // Try to reduce a Repeat pattern on |current_node|. A pattern is found when
374 : // |current_node| has two successors and a back edge to itself.
375 : //
376 : // | /---\ |
377 : // (entry) | -> (entry)
378 : // / \---/ |
379 : // /
380 : //
381 : bool MatchRepeatNode(StructuralTree* current_node,
382 : AbstractLinks* predecessor_links,
383 : AbstractLinks* successor_links,
384 E : bool swap) {
385 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), current_node);
386 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), predecessor_links);
387 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), successor_links);
388 :
389 E : StructuralTree* end_node = NULL;
390 E : StructuralTree* body_node = NULL;
391 :
392 : // Try to match a RepeatNode.
393 : if (MatchTwoLinks(*successor_links, current_node, &body_node, &end_node) &&
394 : SwapNode(swap, &body_node, &end_node) &&
395 : body_node == current_node &&
396 E : body_node != end_node) {
397 : current_node->reset(new StructuralNode(StructuralNode::kRepeatNode,
398 E : body_node->Pass()));
399 :
400 : // Remove internal links.
401 E : RemoveLink(current_node, current_node, successor_links, predecessor_links);
402 E : RemoveLink(current_node, end_node, successor_links, predecessor_links);
403 :
404 : // Add the new link.
405 E : AddLink(current_node, end_node, successor_links, predecessor_links);
406 :
407 E : return true;
408 : }
409 :
410 E : return false;
411 E : }
412 :
413 : // Try to reduce a While pattern on |current_node|. A pattern is found when
414 : // |current_node| has two successors. The (body) node has a successor to
415 : // (entry), the back edge of the loop. No incoming edges are allowed into
416 : // (body).
417 : //
418 : // | /---\ |
419 : // (entry) \ -> (entry)
420 : // / \ | |
421 : // / (body) |
422 : // \--/
423 : bool MatchWhileNode(StructuralTree* current_node,
424 : AbstractLinks* predecessor_links,
425 : AbstractLinks* successor_links,
426 E : bool swap) {
427 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), current_node);
428 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), predecessor_links);
429 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), successor_links);
430 :
431 E : StructuralTree* body_node = NULL;
432 E : StructuralTree* end_node = NULL;
433 :
434 : // Try to match a RepeatNode.
435 : if (MatchTwoLinks(*successor_links, current_node, &body_node, &end_node) &&
436 : SwapNode(swap, &body_node, &end_node) &&
437 : CheckUniqueLink(*predecessor_links, body_node, current_node) &&
438 : CheckUniqueLink(*successor_links, body_node, current_node) &&
439 E : CheckDistinct(current_node, body_node)) {
440 : current_node->reset(new StructuralNode(StructuralNode::kWhileNode,
441 : current_node->Pass(),
442 E : body_node->Pass()));
443 :
444 : // Remove internal links.
445 E : RemoveLink(current_node, body_node, successor_links, predecessor_links);
446 E : RemoveLink(body_node, current_node, successor_links, predecessor_links);
447 E : RemoveLink(current_node, end_node, successor_links, predecessor_links);
448 :
449 : // Add the new link.
450 E : AddLink(current_node, end_node, successor_links, predecessor_links);
451 :
452 E : return true;
453 : }
454 :
455 E : return false;
456 E : }
457 :
458 : // Try to reduce a Loop pattern on |current_node|. An infinite loop has only
459 : // one successor to itself.
460 : //
461 : // | /--\ |
462 : // (entry) | -> (entry)
463 : // \--/
464 : bool MatchLoopNode(StructuralTree* current_node,
465 : StructuralTree* stop_node,
466 : AbstractLinks* predecessor_links,
467 E : AbstractLinks* successor_links) {
468 E : DCHECK_NE(reinterpret_cast<StructuralTree*>(NULL), current_node);
469 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), predecessor_links);
470 E : DCHECK_NE(reinterpret_cast<AbstractLinks*>(NULL), successor_links);
471 :
472 E : StructuralTree* body_node = NULL;
473 :
474 : // Try to match a LoopNode.
475 : if (MatchUniqueLink(*successor_links, current_node, &body_node) &&
476 E : body_node == current_node) {
477 : current_node->reset(new StructuralNode(StructuralNode::kLoopNode,
478 E : current_node->Pass()));
479 :
480 : // Remove internal links.
481 E : RemoveLink(current_node, current_node, successor_links, predecessor_links);
482 :
483 : // Add the new link.
484 E : AddLink(current_node, stop_node, successor_links, predecessor_links);
485 :
486 E : return true;
487 : }
488 :
489 E : return false;
490 E : }
491 :
492 : void DumpStructuralTreeToString(const StructuralNode* tree,
493 : size_t indent,
494 : std::stringstream* out) {
495 : DCHECK_NE(reinterpret_cast<const StructuralNode* >(NULL), tree);
496 : DCHECK_NE(reinterpret_cast<std::stringstream*>(NULL), out);
497 :
498 : std::string indent_string(4 * indent, ' ');
499 :
500 : switch (tree->kind()) {
501 : case StructuralNode::kBaseNode: {
502 : const BasicCodeBlock* bb = tree->root();
503 : BasicCodeBlock::Instructions::const_iterator it =
504 : bb->instructions().begin();
505 : for (; it != bb->instructions().end(); ++it) {
506 : std::string instruction_string;
507 : if (!it->ToString(&instruction_string)) {
508 : *out << "<error>\n";
509 : } else {
510 : *out << indent_string << instruction_string << "\n";
511 : }
512 : }
513 : break;
514 : }
515 : case StructuralNode::kSequenceNode: {
516 : DumpStructuralTreeToString(tree->entry_node(), indent, out);
517 : DumpStructuralTreeToString(tree->sequence_node(), indent, out);
518 : break;
519 : }
520 : case StructuralNode::kIfThenNode: {
521 : *out << indent_string << "IF {\n";
522 : DumpStructuralTreeToString(tree->entry_node(), indent + 1, out);
523 : *out << indent_string << "} THEN {\n";
524 : DumpStructuralTreeToString(tree->then_node(), indent + 1, out);
525 : *out << indent_string << "}\n";
526 : break;
527 : }
528 : case StructuralNode::kIfThenElseNode: {
529 : *out << indent_string << "IF {\n";
530 : DumpStructuralTreeToString(tree->entry_node(), indent + 1, out);
531 : *out << indent_string << "} THEN {\n";
532 : DumpStructuralTreeToString(tree->then_node(), indent + 1, out);
533 : *out << indent_string << "} ELSE {\n";
534 : DumpStructuralTreeToString(tree->else_node(), indent + 1, out);
535 : *out << indent_string << "}\n";
536 : break;
537 : }
538 : case StructuralNode::kRepeatNode: {
539 : *out << indent_string << "REPEAT {\n";
540 : DumpStructuralTreeToString(tree->entry_node(), indent + 1, out);
541 : *out << indent_string << "}";
542 : break;
543 : case StructuralNode::kWhileNode:
544 : *out << indent_string << "WHILE {\n";
545 : DumpStructuralTreeToString(tree->entry_node(), indent + 1, out);
546 : *out << indent_string << "} DO {\n";
547 : DumpStructuralTreeToString(tree->body_node(), indent + 1, out);
548 : *out << indent_string << "}\n";
549 : break;
550 : }
551 : case StructuralNode::kLoopNode: {
552 : *out << indent_string << "LOOP {\n";
553 : DumpStructuralTreeToString(tree->entry_node(), indent + 1, out);
554 : *out << indent_string << "}\n";
555 : break;
556 : }
557 : default: {
558 : NOTREACHED() << "Invalid structural node.";
559 : }
560 : }
561 : }
562 :
563 : } // namespace
564 :
565 : StructuralNode::StructuralNode(Kind kind)
566 E : : kind_(kind), root_(NULL) {
567 E : DCHECK(kind == kStartNode || kind == kStopNode);
568 E : }
569 :
570 : StructuralNode::StructuralNode(Kind kind, const BasicCodeBlock* root)
571 E : : kind_(kind), root_(root) {
572 E : DCHECK_EQ(kBaseNode, kind);
573 E : DCHECK_NE(reinterpret_cast<const BasicCodeBlock*>(NULL), root);
574 E : }
575 :
576 : StructuralNode::StructuralNode(Kind kind, StructuralTree entry_node)
577 : : kind_(kind), root_(NULL),
578 E : entry_node_(entry_node.Pass()) {
579 E : root_ = entry_node_->root();
580 E : }
581 :
582 : StructuralNode::StructuralNode(Kind kind,
583 : StructuralTree entry_node,
584 : StructuralTree child1)
585 : : kind_(kind), root_(NULL),
586 : entry_node_(entry_node.Pass()),
587 E : child1_(child1.Pass()) {
588 E : root_ = entry_node_->root();
589 E : }
590 :
591 : StructuralNode::StructuralNode(Kind kind,
592 : StructuralTree entry_node,
593 : StructuralTree child1,
594 : StructuralTree child2)
595 : : kind_(kind), root_(NULL),
596 : entry_node_(entry_node.Pass()),
597 : child1_(child1.Pass()),
598 E : child2_(child2.Pass()) {
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 : basic_block_map[*it].reset(
651 E : 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 : true) ||
760 : MatchLoopNode(current_node,
761 : &stop_node,
762 : &predecessor_links,
763 E : &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 : CheckUniqueLink(successor_links, reduced_tree, &stop_node) &&
783 E : CheckUniqueLink(predecessor_links, &stop_node, reduced_tree)) {
784 E : *tree = reduced_tree->Pass();
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
|