Source/JavaScriptCore/dfg/DFGDominators.cpp

11/*
2  * Copyright (C) 2011 Apple Inc. All rights reserved.
 2 * Copyright (C) 2011, 2014 Apple Inc. All rights reserved.
33 *
44 * Redistribution and use in source and binary forms, with or without
55 * modification, are permitted provided that the following conditions

@@Dominators::~Dominators()
4141{
4242}
4343
44 void Dominators::compute(Graph& graph)
45 {
46  // This implements a naive dominator solver.
 44namespace {
 45
 46// This implements Lengauer and Tarjan's "A Fast Algorithm for Finding Dominators in a Flowgraph"
 47// (TOPLAS 1979). It uses the "simple" implementation of LINK and EVAL. The full paper is linked
 48// below; this code attempts to closely follow the algorithm as it is presented in the paper; in
 49// particular sections 3 and 4.
 50// https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf
 51
 52struct LangauerTarjan {
 53 LangauerTarjan(Graph& graph)
 54 : m_graph(graph)
 55 {
 56 m_data.resize(graph.numBlocks());
 57 }
 58
 59 void compute()
 60 {
 61 computeDepthFirstPreNumbering(); // Step 1.
 62 computeSemiDominatorsAndImplicitImmediateDominators(); // Steps 2 and 3.
 63 computeExplicitImmediateDominators(); // Step 4.
 64 }
4765
48  ASSERT(graph.block(0)->predecessors.isEmpty());
 66 void computeDepthFirstPreNumbering()
 67 {
 68 BitVector seen;
 69 Vector<BlockData*, 16> worklist;
 70 seen.set(0);
 71 worklist.append(m_graph.block(0));
 72
 73 unsigned nextNumber = 0;
 74
 75 while (!worklist.isEmpty()) {
 76 BasicBlock* block = worklist.takeLast();
 77 m_data[block->index].semiNumber = nextNumber++;
 78 for (unsigned i = block->numSuccessors(); i--;) {
 79 BasicBlock* successorBlock = block->successor(i);
 80 if (seen.get(successorBlock->index))
 81 continue;
 82 seen.set(successorBlock->index);
 83 worklist.append(successorBlock);
 84 }
 85 }
 86 }
4987
50  unsigned numBlocks = graph.numBlocks();
 88 void computeSemiDominatorsAndImplicitImmediateDominators()
 89 {
 90
 91 }
5192
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 
98 bool Dominators::pruneDominators(Graph& graph, BlockIndex idx)
99 {
100  BasicBlock* block = graph.block(idx);
 93 void link(BasicBlock* from, BasicBlock* to)
 94 {
 95 m_data[from->index].ancestor = to;
 96 }
 97
 98 BasicBlock* eval(BasicBlock* block)
 99 {
 100 BlockData& data = m_data[block->index];
 101 if (!data.ancestor)
 102 return block;
 103
 104 compress(block);
 105 return data[block->index].label;
 106 }
 107
 108 void compress(BasicBlock* initialBlock)
 109 {
 110 // This was meant to be a recursive function, but we don't like recursion because we don't
 111 // want to blow the stack. The original function will call compress() recursively on the
 112 // ancestor of anything that has an ancestor. So, we populate our worklist with the
 113 // recursive ancestors of initialBlock. Then we process the list starting from the block
 114 // that is furthest up the ancestor chain.
 115
 116 BasicBlock* ancestor = m_data[initialBlock->index].ancestor;
 117 ASSERT(ancestor);
 118 if (!m_data[ancestor->index].ancestor)
 119 return;
 120
 121 Vector<BasicBlock*, 16> stack;
 122 for (BasicBlock* block = initialBlock; block; block = m_data[block->index].ancestor)
 123 stack.append(block);
 124
 125 // We only care about blocks that have an ancestor that has an ancestor. The last two
 126 // elements in the stack won't satisfy this property.
 127 ASSERT(stack.size() >= 2);
 128 ASSERT(!m_data[stack[stack.size() - 1]->index].ancestor);
 129 ASSERT(!m_data[m_data[stack[stack.size() - 2]->index].ancestor->index].ancestor);
 130
 131 for (unsigned i = stack.size() - 2; i--;) {
 132 BasicBlock* block = stack[i];
 133 BasicBlock*& labelOfBlock = m_data[block->index].label;
 134 BasicBlock*& ancestorOfBlock = m_data[block->index].ancestor;
 135 ASSERT(ancestorOfBlock);
 136 ASSERT(m_data[ancestorOfBlock->index].ancestor);
 137
 138 BasicBlock* labelOfAncestorOfBlock = m_data[ancestorOfBlock->index].label;
 139
 140 if (m_data[labelOfAncesorOfBlock->index].semi < m_data[labelOfBlock->index].semi)
 141 labelOfBlock = labelOfAncestorOfBlock;
 142 ancestorOfBlock = m_data[ancestorOfBlock->index].ancestor;
 143 }
 144 }
101145
102  if (!block || block->predecessors.isEmpty())
103  return false;
 146 struct BlockData {
 147 BlockData()
 148 : preNumber(UINT_MAX)
 149 , semiNumber(UINT_MAX)
 150 , ancestor(nullptr)
 151 , label(nullptr)
 152 {
 153 }
 154
 155 unsigned preNumber;
 156 unsigned semiNumber;
 157 BasicBlock* ancestor;
 158 BasicBlock* label;
 159 };
 160
 161 Graph& m_graph;
 162 Vector<BlockData> m_data;
 163};
104164
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]);
 165} // anonymous namespace
109166
110  // The block is also dominated by itself.
111  m_scratch.set(idx);
 167void Dominators::compute(Graph& graph)
 168{
 169 LangauerTarjan langauerTarjan(graph);
 170 langauerTarjan.compute();
112171
113  return m_results[idx].setAndCheck(m_scratch);
 172 // FIXME;
114173}
115174
116175void Dominators::dump(Graph& graph, PrintStream& out) const
117176{
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  }
 177 FIXME;
130178}
131179
132180} } // namespace JSC::DFG
172947

Source/JavaScriptCore/dfg/DFGDominators.h

11/*
2  * Copyright (C) 2011 Apple Inc. All rights reserved.
 2 * Copyright (C) 2011, 2014 Apple Inc. All rights reserved.
33 *
44 * Redistribution and use in source and binary forms, with or without
55 * modification, are permitted provided that the following conditions

@@public:
4444
4545 void compute(Graph&);
4646
47  bool dominates(BlockIndex from, BlockIndex to) const
 47 bool dominates(BlockIndex fromIndex, BlockIndex toIndex) const
4848 {
4949 ASSERT(isValid());
50  return m_results[to].get(from);
 50 BlockData& from = m_data[fromIndex];
 51 BlockData& to = m_data[toIndex];
 52 return to.preNumber >= from.preNumber && to.postNumber <= from.postNumber;
5153 }
5254
5355 bool dominates(BasicBlock* from, BasicBlock* to) const

@@public:
5860 void dump(Graph&, PrintStream&) const;
5961
6062private:
61  bool pruneDominators(Graph&, BlockIndex);
 63 struct BlockData {
 64 BlockData()
 65 : idomParent(nullptr)
 66 , preNumber(UINT_MAX)
 67 , postNumber(UINT_MAX)
 68 {
 69 }
 70
 71 Vector<BasicBlock*> idomKids;
 72 BasicBlock* idomParent;
 73
 74 unsigned preNumber;
 75 unsigned postNumber;
 76 };
6277
63  Vector<FastBitVector> m_results; // For each block, the bitvector of blocks that dominate it.
64  FastBitVector m_scratch; // A temporary bitvector with bit for each block. We recycle this to save new/deletes.
 78 Vector<BlockData> m_data;
6579};
6680
6781} } // namespace JSC::DFG
172947

Source/JavaScriptCore/dfg/DFGNaiveDominators.cpp

 1/*
 2 * Copyright (C) 2011, 2014 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 "DFGNaiveDominators.h"
 28
 29#if ENABLE(DFG_JIT)
 30
 31#include "DFGGraph.h"
 32#include "JSCInlines.h"
 33
 34namespace JSC { namespace DFG {
 35
 36NaiveDominators::NaiveDominators()
 37{
 38}
 39
 40NaiveDominators::~NaiveDominators()
 41{
 42}
 43
 44void NaiveDominators::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 NaiveDominators::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 NaiveDominators::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
0

Source/JavaScriptCore/dfg/DFGNaiveDominators.h

 1/*
 2 * Copyright (C) 2011, 2014 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 DFGNaiveDominators_h
 27#define DFGNaiveDominators_h
 28
 29#if ENABLE(DFG_JIT)
 30
 31#include "DFGBasicBlock.h"
 32#include "DFGCommon.h"
 33#include <wtf/FastBitVector.h>
 34
 35namespace JSC { namespace DFG {
 36
 37class Graph;
 38
 39// This class is only used for validating the real dominators implementation.
 40
 41class NaiveDominators {
 42public:
 43 NaiveDominators();
 44 ~NaiveDominators();
 45
 46 void compute(Graph&);
 47
 48 bool dominates(BlockIndex from, BlockIndex to) const
 49 {
 50 ASSERT(isValid());
 51 return m_results[to].get(from);
 52 }
 53
 54 bool dominates(BasicBlock* from, BasicBlock* to) const
 55 {
 56 return dominates(from->index, to->index);
 57 }
 58
 59 void dump(Graph&, PrintStream&) const;
 60
 61private:
 62 bool pruneDominators(Graph&, BlockIndex);
 63
 64 Vector<FastBitVector> m_results; // For each block, the bitvector of blocks that dominate it.
 65 FastBitVector m_scratch; // A temporary bitvector with bit for each block. We recycle this to save new/deletes.
 66};
 67
 68} } // namespace JSC::DFG
 69
 70#endif // ENABLE(DFG_JIT)
 71
 72#endif // DFGNaiveDominators_h
0