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