1/*
2 * Copyright (C) 2011 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#include "config.h"
27#include "DFGDominators.h"
28
29#if ENABLE(DFG_JIT)
30
31#include "DFGGraph.h"
32#include "JSCInlines.h"
33
34namespace JSC { namespace DFG {
35
36Dominators::Dominators()
37{
38}
39
40Dominators::~Dominators()
41{
42}
43
44void Dominators::compute(Graph& graph)
45{
46    // This implements a naive dominator solver.
47
48    ASSERT(graph.block(0)->predecessors.isEmpty());
49
50    unsigned numBlocks = graph.numBlocks();
51
52    // Allocate storage for the dense dominance matrix.
53    if (numBlocks > m_results.size()) {
54        m_results.grow(numBlocks);
55        for (unsigned i = numBlocks; i--;)
56            m_results[i].resize(numBlocks);
57        m_scratch.resize(numBlocks);
58    }
59
60    // We know that the entry block is only dominated by itself.
61    m_results[0].clearAll();
62    m_results[0].set(0);
63
64    // Find all of the valid blocks.
65    m_scratch.clearAll();
66    for (unsigned i = numBlocks; i--;) {
67        if (!graph.block(i))
68            continue;
69        m_scratch.set(i);
70    }
71
72    // Mark all nodes as dominated by everything.
73    for (unsigned i = numBlocks; i-- > 1;) {
74        if (!graph.block(i) || graph.block(i)->predecessors.isEmpty())
75            m_results[i].clearAll();
76        else
77            m_results[i].set(m_scratch);
78    }
79
80    // Iteratively eliminate nodes that are not dominator.
81    bool changed;
82    do {
83        changed = false;
84        // Prune dominators in all non entry blocks: forward scan.
85        for (unsigned i = 1; i < numBlocks; ++i)
86            changed |= pruneDominators(graph, i);
87
88        if (!changed)
89            break;
90
91        // Prune dominators in all non entry blocks: backward scan.
92        changed = false;
93        for (unsigned i = numBlocks; i-- > 1;)
94            changed |= pruneDominators(graph, i);
95    } while (changed);
96}
97
98bool Dominators::pruneDominators(Graph& graph, BlockIndex idx)
99{
100    BasicBlock* block = graph.block(idx);
101
102    if (!block || block->predecessors.isEmpty())
103        return false;
104
105    // Find the intersection of dom(preds).
106    m_scratch.set(m_results[block->predecessors[0]->index]);
107    for (unsigned j = block->predecessors.size(); j-- > 1;)
108        m_scratch.filter(m_results[block->predecessors[j]->index]);
109
110    // The block is also dominated by itself.
111    m_scratch.set(idx);
112
113    return m_results[idx].setAndCheck(m_scratch);
114}
115
116void Dominators::dump(Graph& graph, PrintStream& out) const
117{
118    for (BlockIndex blockIndex = 0; blockIndex < graph.numBlocks(); ++blockIndex) {
119        BasicBlock* block = graph.block(blockIndex);
120        if (!block)
121            continue;
122        out.print("    Block ", *block, ":");
123        for (BlockIndex otherIndex = 0; otherIndex < graph.numBlocks(); ++otherIndex) {
124            if (!dominates(block->index, otherIndex))
125                continue;
126            out.print(" #", otherIndex);
127        }
128        out.print("\n");
129    }
130}
131
132} } // namespace JSC::DFG
133
134#endif // ENABLE(DFG_JIT)
135
136