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
  34 namespace JSC { namespace DFG {
  35
  36 NaiveDominators::NaiveDominators()
  37 {
  38 }
  39
  40 NaiveDominators::~NaiveDominators()
  41 {
  42 }
  43
  44 void 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
  98 bool 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
 116 void 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