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