dfg/DFGDominators.cpp

   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
  33 namespace JSC { namespace DFG {
  34
  35 Dominators::Dominators()
  36     : m_valid(false)
  37 {
  38 }
  39
  40 Dominators::~Dominators()
  41 {
  42 }
  43
  44 void Dominators::compute(Graph& graph)
  45 {
  46     // This implements a naive dominator solver.
  47
  48     ASSERT(graph.m_blocks[0]->m_predecessors.isEmpty());
  49
  50     unsigned numBlocks = graph.m_blocks.size();
  51
  52     if (numBlocks > m_results.size()) {
  53         m_results.grow(numBlocks);
  54         for (unsigned i = numBlocks; i--;)
  55             m_results[i].resize(numBlocks);
  56         m_scratch.resize(numBlocks);
  57     }
  58
  59     m_results[0].clearAll();
  60     m_results[0].set(0);
  61
  62     m_scratch.clearAll();
  63     for (unsigned i = numBlocks; i--;) {
  64         if (!graph.m_blocks[i])
  65             continue;
  66         m_scratch.set(i);
  67     }
  68
  69     for (unsigned i = numBlocks; i-- > 1;) {
  70         if (!graph.m_blocks[i] || graph.m_blocks[i]->m_predecessors.isEmpty())
  71             m_results[i].clearAll();
  72         else
  73             m_results[i].set(m_scratch);
  74     }
  75
  76     bool changed;
  77     do {
  78         changed = false;
  79         for (unsigned i = 1; i < numBlocks; ++i)
  80             changed |= iterateForBlock(graph, i);
  81         if (!changed)
  82             break;
  83
  84         changed = false;
  85         for (unsigned i = numBlocks; i-- > 1;)
  86             changed |= iterateForBlock(graph, i);
  87     } while (changed);
  88
  89     m_valid = true;
  90 }
  91
  92 bool Dominators::iterateForBlock(Graph& graph, BlockIndex i)
  93 {
  94     BasicBlock* block = graph.m_blocks[i].get();
  95     if (!block)
  96         return false;
  97     if (block->m_predecessors.isEmpty())
  98         return false;
  99     m_scratch.set(m_results[block->m_predecessors[0]]);
 100     for (unsigned j = block->m_predecessors.size(); j-- > 1;)
 101         m_scratch.filter(m_results[block->m_predecessors[j]]);
 102     m_scratch.set(i);
 103     return m_results[i].setAndCheck(m_scratch);
 104 }
 105
 106 } } // namespace JSC::DFG
 107
 108 #endif // ENABLE(DFG_JIT)
 109