1/*
2 * Copyright (C) 2011-2017 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/CommaPrinter.h>
29#include <wtf/FastBitVector.h>
30#include <wtf/GraphNodeWorklist.h>
31
32namespace WTF {
33
34// This is a utility for finding the dominators of a graph. Dominators are almost universally used
35// for control flow graph analysis, so this code will refer to the graph's "nodes" as "blocks". In
36// that regard this code is kind of specialized for the various JSC compilers, but you could use it
37// for non-compiler things if you are OK with referring to your "nodes" as "blocks".
38
39template<typename Graph>
40class Dominators {
41public:
42 using List = typename Graph::List;
43
44 Dominators(Graph& graph, bool selfCheck = false)
45 : m_graph(graph)
46 , m_data(graph.template newMap<BlockData>())
47 {
48 LengauerTarjan lengauerTarjan(m_graph);
49 lengauerTarjan.compute();
50
51 // From here we want to build a spanning tree with both upward and downward links and we want
52 // to do a search over this tree to compute pre and post numbers that can be used for dominance
53 // tests.
54
55 for (unsigned blockIndex = m_graph.numNodes(); blockIndex--;) {
56 typename Graph::Node block = m_graph.node(blockIndex);
57 if (!block)
58 continue;
59
60 typename Graph::Node idomBlock = lengauerTarjan.immediateDominator(block);
61 m_data[block].idomParent = idomBlock;
62 if (idomBlock)
63 m_data[idomBlock].idomKids.append(block);
64 }
65
66 unsigned nextPreNumber = 0;
67 unsigned nextPostNumber = 0;
68
69 // Plain stack-based worklist because we are guaranteed to see each block exactly once anyway.
70 Vector<GraphNodeWithOrder<typename Graph::Node>> worklist;
71 worklist.append(GraphNodeWithOrder<typename Graph::Node>(m_graph.root(), GraphVisitOrder::Pre));
72 while (!worklist.isEmpty()) {
73 GraphNodeWithOrder<typename Graph::Node> item = worklist.takeLast();
74 switch (item.order) {
75 case GraphVisitOrder::Pre:
76 m_data[item.node].preNumber = nextPreNumber++;
77 worklist.append(GraphNodeWithOrder<typename Graph::Node>(item.node, GraphVisitOrder::Post));
78 for (typename Graph::Node kid : m_data[item.node].idomKids)
79 worklist.append(GraphNodeWithOrder<typename Graph::Node>(kid, GraphVisitOrder::Pre));
80 break;
81 case GraphVisitOrder::Post:
82 m_data[item.node].postNumber = nextPostNumber++;
83 break;
84 }
85 }
86
87 if (selfCheck) {
88 // Check our dominator calculation:
89 // 1) Check that our range-based ancestry test is the same as a naive ancestry test.
90 // 2) Check that our notion of who dominates whom is identical to a naive (not
91 // Lengauer-Tarjan) dominator calculation.
92
93 ValidationContext context(m_graph, *this);
94
95 for (unsigned fromBlockIndex = m_graph.numNodes(); fromBlockIndex--;) {
96 typename Graph::Node fromBlock = m_graph.node(fromBlockIndex);
97 if (!fromBlock || m_data[fromBlock].preNumber == UINT_MAX)
98 continue;
99 for (unsigned toBlockIndex = m_graph.numNodes(); toBlockIndex--;) {
100 typename Graph::Node toBlock = m_graph.node(toBlockIndex);
101 if (!toBlock || m_data[toBlock].preNumber == UINT_MAX)
102 continue;
103
104 if (dominates(fromBlock, toBlock) != naiveDominates(fromBlock, toBlock))
105 context.reportError(fromBlock, toBlock, "Range-based domination check is broken");
106 if (dominates(fromBlock, toBlock) != context.naiveDominators.dominates(fromBlock, toBlock))
107 context.reportError(fromBlock, toBlock, "Lengauer-Tarjan domination is broken");
108 }
109 }
110
111 context.handleErrors();
112 }
113 }
114
115 bool strictlyDominates(typename Graph::Node from, typename Graph::Node to) const
116 {
117 return m_data[to].preNumber > m_data[from].preNumber
118 && m_data[to].postNumber < m_data[from].postNumber;
119 }
120
121 bool dominates(typename Graph::Node from, typename Graph::Node to) const
122 {
123 return from == to || strictlyDominates(from, to);
124 }
125
126 // Returns the immediate dominator of this block. Returns null for the root block.
127 typename Graph::Node idom(typename Graph::Node block) const
128 {
129 return m_data[block].idomParent;
130 }
131
132 template<typename Functor>
133 void forAllStrictDominatorsOf(typename Graph::Node to, const Functor& functor) const
134 {
135 for (typename Graph::Node block = m_data[to].idomParent; block; block = m_data[block].idomParent)
136 functor(block);
137 }
138
139 // Note: This will visit the dominators starting with the 'to' node and moving up the idom tree
140 // until it gets to the root. Some clients of this function, like B3::moveConstants(), rely on this
141 // order.
142 template<typename Functor>
143 void forAllDominatorsOf(typename Graph::Node to, const Functor& functor) const
144 {
145 for (typename Graph::Node block = to; block; block = m_data[block].idomParent)
146 functor(block);
147 }
148
149 template<typename Functor>
150 void forAllBlocksStrictlyDominatedBy(typename Graph::Node from, const Functor& functor) const
151 {
152 Vector<typename Graph::Node, 16> worklist;
153 worklist.appendVector(m_data[from].idomKids);
154 while (!worklist.isEmpty()) {
155 typename Graph::Node block = worklist.takeLast();
156 functor(block);
157 worklist.appendVector(m_data[block].idomKids);
158 }
159 }
160
161 template<typename Functor>
162 void forAllBlocksDominatedBy(typename Graph::Node from, const Functor& functor) const
163 {
164 Vector<typename Graph::Node, 16> worklist;
165 worklist.append(from);
166 while (!worklist.isEmpty()) {
167 typename Graph::Node block = worklist.takeLast();
168 functor(block);
169 worklist.appendVector(m_data[block].idomKids);
170 }
171 }
172
173 typename Graph::Set strictDominatorsOf(typename Graph::Node to) const
174 {
175 typename Graph::Set result;
176 forAllStrictDominatorsOf(
177 to,
178 [&] (typename Graph::Node node) {
179 result.add(node);
180 });
181 return result;
182 }
183
184 typename Graph::Set dominatorsOf(typename Graph::Node to) const
185 {
186 typename Graph::Set result;
187 forAllDominatorsOf(
188 to,
189 [&] (typename Graph::Node node) {
190 result.add(node);
191 });
192 return result;
193 }
194
195 typename Graph::Set blocksStrictlyDominatedBy(typename Graph::Node from) const
196 {
197 typename Graph::Set result;
198 forAllBlocksStrictlyDominatedBy(
199 from,
200 [&] (typename Graph::Node node) {
201 result.add(node);
202 });
203 return result;
204 }
205
206 typename Graph::Set blocksDominatedBy(typename Graph::Node from) const
207 {
208 typename Graph::Set result;
209 forAllBlocksDominatedBy(
210 from,
211 [&] (typename Graph::Node node) {
212 result.add(node);
213 });
214 return result;
215 }
216
217 template<typename Functor>
218 void forAllBlocksInDominanceFrontierOf(
219 typename Graph::Node from, const Functor& functor) const
220 {
221 typename Graph::Set set;
222 forAllBlocksInDominanceFrontierOfImpl(
223 from,
224 [&] (typename Graph::Node block) {
225 if (set.add(block))
226 functor(block);
227 });
228 }
229
230 typename Graph::Set dominanceFrontierOf(typename Graph::Node from) const
231 {
232 typename Graph::Set result;
233 forAllBlocksInDominanceFrontierOf(
234 from,
235 [&] (typename Graph::Node node) {
236 result.add(node);
237 });
238 return result;
239 }
240
241 template<typename Functor>
242 void forAllBlocksInIteratedDominanceFrontierOf(const List& from, const Functor& functor)
243 {
244 forAllBlocksInPrunedIteratedDominanceFrontierOf(
245 from,
246 [&] (typename Graph::Node block) -> bool {
247 functor(block);
248 return true;
249 });
250 }
251
252 // This is a close relative of forAllBlocksInIteratedDominanceFrontierOf(), which allows the
253 // given functor to return false to indicate that we don't wish to consider the given block.
254 // Useful for computing pruned SSA form.
255 template<typename Functor>
256 void forAllBlocksInPrunedIteratedDominanceFrontierOf(
257 const List& from, const Functor& functor)
258 {
259 typename Graph::Set set;
260 forAllBlocksInIteratedDominanceFrontierOfImpl(
261 from,
262 [&] (typename Graph::Node block) -> bool {
263 if (!set.add(block))
264 return false;
265 return functor(block);
266 });
267 }
268
269 typename Graph::Set iteratedDominanceFrontierOf(const List& from) const
270 {
271 typename Graph::Set result;
272 forAllBlocksInIteratedDominanceFrontierOfImpl(
273 from,
274 [&] (typename Graph::Node node) -> bool {
275 return result.add(node);
276 });
277 return result;
278 }
279
280 void dump(PrintStream& out) const
281 {
282 for (unsigned blockIndex = 0; blockIndex < m_data.size(); ++blockIndex) {
283 if (m_data[blockIndex].preNumber == UINT_MAX)
284 continue;
285
286 out.print(" Block #", blockIndex, ": idom = ", m_graph.dump(m_data[blockIndex].idomParent), ", idomKids = [");
287 CommaPrinter comma;
288 for (unsigned i = 0; i < m_data[blockIndex].idomKids.size(); ++i)
289 out.print(comma, m_graph.dump(m_data[blockIndex].idomKids[i]));
290 out.print("], pre/post = ", m_data[blockIndex].preNumber, "/", m_data[blockIndex].postNumber, "\n");
291 }
292 }
293
294private:
295 // This implements Lengauer and Tarjan's "A Fast Algorithm for Finding Dominators in a Flowgraph"
296 // (TOPLAS 1979). It uses the "simple" implementation of LINK and EVAL, which yields an O(n log n)
297 // solution. The full paper is linked below; this code attempts to closely follow the algorithm as
298 // it is presented in the paper; in particular sections 3 and 4 as well as appendix B.
299 // https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf
300 //
301 // This code is very subtle. The Lengauer-Tarjan algorithm is incredibly deep to begin with. The
302 // goal of this code is to follow the code in the paper, however our implementation must deviate
303 // from the paper when it comes to recursion. The authors had used recursion to implement DFS, and
304 // also to implement the "simple" EVAL. We convert both of those into worklist-based solutions.
305 // Finally, once the algorithm gives us immediate dominators, we implement dominance tests by
306 // walking the dominator tree and computing pre and post numbers. We then use the range inclusion
307 // check trick that was first discovered by Paul F. Dietz in 1982 in "Maintaining order in a linked
308 // list" (see http://dl.acm.org/citation.cfm?id=802184).
309
310 class LengauerTarjan {
311 public:
312 LengauerTarjan(Graph& graph)
313 : m_graph(graph)
314 , m_data(graph.template newMap<BlockData>())
315 {
316 for (unsigned blockIndex = m_graph.numNodes(); blockIndex--;) {
317 typename Graph::Node block = m_graph.node(blockIndex);
318 if (!block)
319 continue;
320 m_data[block].label = block;
321 }
322 }
323
324 void compute()
325 {
326 computeDepthFirstPreNumbering(); // Step 1.
327 computeSemiDominatorsAndImplicitImmediateDominators(); // Steps 2 and 3.
328 computeExplicitImmediateDominators(); // Step 4.
329 }
330
331 typename Graph::Node immediateDominator(typename Graph::Node block)
332 {
333 return m_data[block].dom;
334 }
335
336 private:
337 void computeDepthFirstPreNumbering()
338 {
339 // Use a block worklist that also tracks the index inside the successor list. This is
340 // necessary for ensuring that we don't attempt to visit a successor until the previous
341 // successors that we had visited are fully processed. This ends up being revealed in the
342 // output of this method because the first time we see an edge to a block, we set the
343 // block's parent. So, if we have:
344 //
345 // A -> B
346 // A -> C
347 // B -> C
348 //
349 // And we're processing A, then we want to ensure that if we see A->B first (and hence set
350 // B's prenumber before we set C's) then we also end up setting C's parent to B by virtue
351 // of not noticing A->C until we're done processing B.
352
353 ExtendedGraphNodeWorklist<typename Graph::Node, unsigned, typename Graph::Set> worklist;
354 worklist.push(m_graph.root(), 0);
355
356 while (GraphNodeWith<typename Graph::Node, unsigned> item = worklist.pop()) {
357 typename Graph::Node block = item.node;
358 unsigned successorIndex = item.data;
359
360 // We initially push with successorIndex = 0 regardless of whether or not we have any
361 // successors. This is so that we can assign our prenumber. Subsequently we get pushed
362 // with higher successorIndex values, but only if they are in range.
363 ASSERT(!successorIndex || successorIndex < m_graph.successors(block).size());
364
365 if (!successorIndex) {
366 m_data[block].semiNumber = m_blockByPreNumber.size();
367 m_blockByPreNumber.append(block);
368 }
369
370 if (successorIndex < m_graph.successors(block).size()) {
371 unsigned nextSuccessorIndex = successorIndex + 1;
372 if (nextSuccessorIndex < m_graph.successors(block).size())
373 worklist.forcePush(block, nextSuccessorIndex);
374
375 typename Graph::Node successorBlock = m_graph.successors(block)[successorIndex];
376 if (worklist.push(successorBlock, 0))
377 m_data[successorBlock].parent = block;
378 }
379 }
380 }
381
382 void computeSemiDominatorsAndImplicitImmediateDominators()
383 {
384 for (unsigned currentPreNumber = m_blockByPreNumber.size(); currentPreNumber-- > 1;) {
385 typename Graph::Node block = m_blockByPreNumber[currentPreNumber];
386 BlockData& blockData = m_data[block];
387
388 // Step 2:
389 for (typename Graph::Node predecessorBlock : m_graph.predecessors(block)) {
390 typename Graph::Node intermediateBlock = eval(predecessorBlock);
391 blockData.semiNumber = std::min(
392 m_data[intermediateBlock].semiNumber, blockData.semiNumber);
393 }
394 unsigned bucketPreNumber = blockData.semiNumber;
395 ASSERT(bucketPreNumber <= currentPreNumber);
396 m_data[m_blockByPreNumber[bucketPreNumber]].bucket.append(block);
397 link(blockData.parent, block);
398
399 // Step 3:
400 for (typename Graph::Node semiDominee : m_data[blockData.parent].bucket) {
401 typename Graph::Node possibleDominator = eval(semiDominee);
402 BlockData& semiDomineeData = m_data[semiDominee];
403 ASSERT(m_blockByPreNumber[semiDomineeData.semiNumber] == blockData.parent);
404 BlockData& possibleDominatorData = m_data[possibleDominator];
405 if (possibleDominatorData.semiNumber < semiDomineeData.semiNumber)
406 semiDomineeData.dom = possibleDominator;
407 else
408 semiDomineeData.dom = blockData.parent;
409 }
410 m_data[blockData.parent].bucket.clear();
411 }
412 }
413
414 void computeExplicitImmediateDominators()
415 {
416 for (unsigned currentPreNumber = 1; currentPreNumber < m_blockByPreNumber.size(); ++currentPreNumber) {
417 typename Graph::Node block = m_blockByPreNumber[currentPreNumber];
418 BlockData& blockData = m_data[block];
419
420 if (blockData.dom != m_blockByPreNumber[blockData.semiNumber])
421 blockData.dom = m_data[blockData.dom].dom;
422 }
423 }
424
425 void link(typename Graph::Node from, typename Graph::Node to)
426 {
427 m_data[to].ancestor = from;
428 }
429
430 typename Graph::Node eval(typename Graph::Node block)
431 {
432 if (!m_data[block].ancestor)
433 return block;
434
435 compress(block);
436 return m_data[block].label;
437 }
438
439 void compress(typename Graph::Node initialBlock)
440 {
441 // This was meant to be a recursive function, but we don't like recursion because we don't
442 // want to blow the stack. The original function will call compress() recursively on the
443 // ancestor of anything that has an ancestor. So, we populate our worklist with the
444 // recursive ancestors of initialBlock. Then we process the list starting from the block
445 // that is furthest up the ancestor chain.
446
447 typename Graph::Node ancestor = m_data[initialBlock].ancestor;
448 ASSERT(ancestor);
449 if (!m_data[ancestor].ancestor)
450 return;
451
452 Vector<typename Graph::Node, 16> stack;
453 for (typename Graph::Node block = initialBlock; block; block = m_data[block].ancestor)
454 stack.append(block);
455
456 // We only care about blocks that have an ancestor that has an ancestor. The last two
457 // elements in the stack won't satisfy this property.
458 ASSERT(stack.size() >= 2);
459 ASSERT(!m_data[stack[stack.size() - 1]].ancestor);
460 ASSERT(!m_data[m_data[stack[stack.size() - 2]].ancestor].ancestor);
461
462 for (unsigned i = stack.size() - 2; i--;) {
463 typename Graph::Node block = stack[i];
464 typename Graph::Node& labelOfBlock = m_data[block].label;
465 typename Graph::Node& ancestorOfBlock = m_data[block].ancestor;
466 ASSERT(ancestorOfBlock);
467 ASSERT(m_data[ancestorOfBlock].ancestor);
468
469 typename Graph::Node labelOfAncestorOfBlock = m_data[ancestorOfBlock].label;
470
471 if (m_data[labelOfAncestorOfBlock].semiNumber < m_data[labelOfBlock].semiNumber)
472 labelOfBlock = labelOfAncestorOfBlock;
473 ancestorOfBlock = m_data[ancestorOfBlock].ancestor;
474 }
475 }
476
477 struct BlockData {
478 BlockData()
479 : parent(nullptr)
480 , preNumber(UINT_MAX)
481 , semiNumber(UINT_MAX)
482 , ancestor(nullptr)
483 , label(nullptr)
484 , dom(nullptr)
485 {
486 }
487
488 typename Graph::Node parent;
489 unsigned preNumber;
490 unsigned semiNumber;
491 typename Graph::Node ancestor;
492 typename Graph::Node label;
493 Vector<typename Graph::Node> bucket;
494 typename Graph::Node dom;
495 };
496
497 Graph& m_graph;
498 typename Graph::template Map<BlockData> m_data;
499 Vector<typename Graph::Node> m_blockByPreNumber;
500 };
501
502 class NaiveDominators {
503 public:
504 NaiveDominators(Graph& graph)
505 : m_graph(graph)
506 {
507 // This implements a naive dominator solver.
508
509 ASSERT(!graph.predecessors(graph.root()).size());
510
511 unsigned numBlocks = graph.numNodes();
512
513 // Allocate storage for the dense dominance matrix.
514 m_results.grow(numBlocks);
515 for (unsigned i = numBlocks; i--;)
516 m_results[i].resize(numBlocks);
517 m_scratch.resize(numBlocks);
518
519 // We know that the entry block is only dominated by itself.
520 m_results[0].clearAll();
521 m_results[0][0] = true;
522
523 // Find all of the valid blocks.
524 m_scratch.clearAll();
525 for (unsigned i = numBlocks; i--;) {
526 if (!graph.node(i))
527 continue;
528 m_scratch[i] = true;
529 }
530
531 // Mark all nodes as dominated by everything.
532 for (unsigned i = numBlocks; i-- > 1;) {
533 if (!graph.node(i) || !graph.predecessors(graph.node(i)).size())
534 m_results[i].clearAll();
535 else
536 m_results[i] = m_scratch;
537 }
538
539 // Iteratively eliminate nodes that are not dominator.
540 bool changed;
541 do {
542 changed = false;
543 // Prune dominators in all non entry blocks: forward scan.
544 for (unsigned i = 1; i < numBlocks; ++i)
545 changed |= pruneDominators(i);
546
547 if (!changed)
548 break;
549
550 // Prune dominators in all non entry blocks: backward scan.
551 changed = false;
552 for (unsigned i = numBlocks; i-- > 1;)
553 changed |= pruneDominators(i);
554 } while (changed);
555 }
556
557 bool dominates(unsigned from, unsigned to) const
558 {
559 return m_results[to][from];
560 }
561
562 bool dominates(typename Graph::Node from, typename Graph::Node to) const
563 {
564 return dominates(m_graph.index(from), m_graph.index(to));
565 }
566
567 void dump(PrintStream& out) const
568 {
569 for (unsigned blockIndex = 0; blockIndex < m_graph.numNodes(); ++blockIndex) {
570 typename Graph::Node block = m_graph.node(blockIndex);
571 if (!block)
572 continue;
573 out.print(" Block ", m_graph.dump(block), ":");
574 for (unsigned otherIndex = 0; otherIndex < m_graph.numNodes(); ++otherIndex) {
575 if (!dominates(m_graph.index(block), otherIndex))
576 continue;
577 out.print(" ", m_graph.dump(m_graph.node(otherIndex)));
578 }
579 out.print("\n");
580 }
581 }
582
583 private:
584 bool pruneDominators(unsigned idx)
585 {
586 typename Graph::Node block = m_graph.node(idx);
587
588 if (!block || !m_graph.predecessors(block).size())
589 return false;
590
591 // Find the intersection of dom(preds).
592 m_scratch = m_results[m_graph.index(m_graph.predecessors(block)[0])];
593 for (unsigned j = m_graph.predecessors(block).size(); j-- > 1;)
594 m_scratch &= m_results[m_graph.index(m_graph.predecessors(block)[j])];
595
596 // The block is also dominated by itself.
597 m_scratch[idx] = true;
598
599 return m_results[idx].setAndCheck(m_scratch);
600 }
601
602 Graph& m_graph;
603 Vector<FastBitVector> m_results; // For each block, the bitvector of blocks that dominate it.
604 FastBitVector m_scratch; // A temporary bitvector with bit for each block. We recycle this to save new/deletes.
605 };
606
607 struct ValidationContext {
608 ValidationContext(Graph& graph, Dominators& dominators)
609 : graph(graph)
610 , dominators(dominators)
611 , naiveDominators(graph)
612 {
613 }
614
615 void reportError(typename Graph::Node from, typename Graph::Node to, const char* message)
616 {
617 Error error;
618 error.from = from;
619 error.to = to;
620 error.message = message;
621 errors.append(error);
622 }
623
624 void handleErrors()
625 {
626 if (errors.isEmpty())
627 return;
628
629 dataLog("DFG DOMINATOR VALIDATION FAILED:\n");
630 dataLog("\n");
631 dataLog("For block domination relationships:\n");
632 for (unsigned i = 0; i < errors.size(); ++i) {
633 dataLog(
634 " ", graph.dump(errors[i].from), " -> ", graph.dump(errors[i].to),
635 " (", errors[i].message, ")\n");
636 }
637 dataLog("\n");
638 dataLog("Control flow graph:\n");
639 for (unsigned blockIndex = 0; blockIndex < graph.numNodes(); ++blockIndex) {
640 typename Graph::Node block = graph.node(blockIndex);
641 if (!block)
642 continue;
643 dataLog(" Block ", graph.dump(graph.node(blockIndex)), ": successors = [");
644 CommaPrinter comma;
645 for (auto successor : graph.successors(block))
646 dataLog(comma, graph.dump(successor));
647 dataLog("], predecessors = [");
648 comma = CommaPrinter();
649 for (auto predecessor : graph.predecessors(block))
650 dataLog(comma, graph.dump(predecessor));
651 dataLog("]\n");
652 }
653 dataLog("\n");
654 dataLog("Lengauer-Tarjan Dominators:\n");
655 dataLog(dominators);
656 dataLog("\n");
657 dataLog("Naive Dominators:\n");
658 naiveDominators.dump(WTF::dataFile());
659 dataLog("\n");
660 dataLog("Graph at time of failure:\n");
661 dataLog(graph);
662 dataLog("\n");
663 dataLog("DFG DOMINATOR VALIDATION FAILIED!\n");
664 CRASH();
665 }
666
667 Graph& graph;
668 Dominators& dominators;
669 NaiveDominators naiveDominators;
670
671 struct Error {
672 typename Graph::Node from;
673 typename Graph::Node to;
674 const char* message;
675 };
676
677 Vector<Error> errors;
678 };
679
680 bool naiveDominates(typename Graph::Node from, typename Graph::Node to) const
681 {
682 for (typename Graph::Node block = to; block; block = m_data[block].idomParent) {
683 if (block == from)
684 return true;
685 }
686 return false;
687 }
688
689 template<typename Functor>
690 void forAllBlocksInDominanceFrontierOfImpl(
691 typename Graph::Node from, const Functor& functor) const
692 {
693 // Paraphrasing from http://en.wikipedia.org/wiki/Dominator_(graph_theory):
694 // "The dominance frontier of a block 'from' is the set of all blocks 'to' such that
695 // 'from' dominates an immediate predecessor of 'to', but 'from' does not strictly
696 // dominate 'to'."
697 //
698 // A useful corner case to remember: a block may be in its own dominance frontier if it has
699 // a loop edge to itself, since it dominates itself and so it dominates its own immediate
700 // predecessor, and a block never strictly dominates itself.
701
702 forAllBlocksDominatedBy(
703 from,
704 [&] (typename Graph::Node block) {
705 for (typename Graph::Node to : m_graph.successors(block)) {
706 if (!strictlyDominates(from, to))
707 functor(to);
708 }
709 });
710 }
711
712 template<typename Functor>
713 void forAllBlocksInIteratedDominanceFrontierOfImpl(
714 const List& from, const Functor& functor) const
715 {
716 List worklist = from;
717 while (!worklist.isEmpty()) {
718 typename Graph::Node block = worklist.takeLast();
719 forAllBlocksInDominanceFrontierOfImpl(
720 block,
721 [&] (typename Graph::Node otherBlock) {
722 if (functor(otherBlock))
723 worklist.append(otherBlock);
724 });
725 }
726 }
727
728 struct BlockData {
729 BlockData()
730 : idomParent(nullptr)
731 , preNumber(UINT_MAX)
732 , postNumber(UINT_MAX)
733 {
734 }
735
736 Vector<typename Graph::Node> idomKids;
737 typename Graph::Node idomParent;
738
739 unsigned preNumber;
740 unsigned postNumber;
741 };
742
743 Graph& m_graph;
744 typename Graph::template Map<BlockData> m_data;
745};
746
747} // namespace WTF
748
749using WTF::Dominators;
750