dfg/DFGNaturalLoops.cpp

   1 /*
   2  * Copyright (C) 2013 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 "DFGNaturalLoops.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGGraph.h"
  32 #include "JSCInlines.h"
  33 #include <wtf/CommaPrinter.h>
  34
  35 namespace JSC { namespace DFG {
  36
  37 void NaturalLoop::dump(PrintStream& out) const
  38 {
  39     out.print("[Header: ", *header(), ", Body:");
  40     for (unsigned i = 0; i < m_body.size(); ++i)
  41         out.print(" ", *m_body[i]);
  42     out.print("]");
  43 }
  44
  45 NaturalLoops::NaturalLoops() { }
  46 NaturalLoops::~NaturalLoops() { }
  47
  48 void NaturalLoops::computeDependencies(Graph& graph)
  49 {
  50     graph.m_dominators.computeIfNecessary(graph);
  51 }
  52
  53 void NaturalLoops::compute(Graph& graph)
  54 {
  55     // Implement the classic dominator-based natural loop finder. The first
  56     // step is to find all control flow edges A -> B where B dominates A.
  57     // Then B is a loop header and A is a backward branching block. We will
  58     // then accumulate, for each loop header, multiple backward branching
  59     // blocks. Then we backwards graph search from the backward branching
  60     // blocks to their loop headers, which gives us all of the blocks in the
  61     // loop body.
  62
  63     static const bool verbose = false;
  64
  65     if (verbose) {
  66         dataLog("Dominators:\n");
  67         graph.m_dominators.dump(WTF::dataFile());
  68     }
  69
  70     m_loops.resize(0);
  71
  72     for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
  73         BasicBlock* block = graph.block(blockIndex);
  74         if (!block)
  75             continue;
  76
  77         for (unsigned i = block->numSuccessors(); i--;) {
  78             BasicBlock* successor = block->successor(i);
  79             if (!graph.m_dominators.dominates(successor, block))
  80                 continue;
  81             bool found = false;
  82             for (unsigned j = m_loops.size(); j--;) {
  83                 if (m_loops[j].header() == successor) {
  84                     m_loops[j].addBlock(block);
  85                     found = true;
  86                     break;
  87                 }
  88             }
  89             if (found)
  90                 continue;
  91             NaturalLoop loop(successor, m_loops.size());
  92             loop.addBlock(block);
  93             m_loops.append(loop);
  94         }
  95     }
  96
  97     if (verbose)
  98         dataLog("After bootstrap: ", *this, "\n");
  99
 100     FastBitVector seenBlocks;
 101     Vector<BasicBlock*, 4> blockWorklist;
 102     seenBlocks.resize(graph.numBlocks());
 103
 104     for (unsigned i = m_loops.size(); i--;) {
 105         NaturalLoop& loop = m_loops[i];
 106
 107         seenBlocks.clearAll();
 108         ASSERT(blockWorklist.isEmpty());
 109
 110         if (verbose)
 111             dataLog("Dealing with loop ", loop, "\n");
 112
 113         for (unsigned j = loop.size(); j--;) {
 114             seenBlocks.set(loop[j]->index);
 115             blockWorklist.append(loop[j]);
 116         }
 117
 118         while (!blockWorklist.isEmpty()) {
 119             BasicBlock* block = blockWorklist.takeLast();
 120
 121             if (verbose)
 122                 dataLog("    Dealing with ", *block, "\n");
 123
 124             if (block == loop.header())
 125                 continue;
 126
 127             for (unsigned j = block->predecessors.size(); j--;) {
 128                 BasicBlock* predecessor = block->predecessors[j];
 129                 if (seenBlocks.get(predecessor->index))
 130                     continue;
 131
 132                 loop.addBlock(predecessor);
 133                 blockWorklist.append(predecessor);
 134                 seenBlocks.set(predecessor->index);
 135             }
 136         }
 137     }
 138
 139     // Figure out reverse mapping from blocks to loops.
 140     for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
 141         BasicBlock* block = graph.block(blockIndex);
 142         if (!block)
 143             continue;
 144         for (unsigned i = BasicBlock::numberOfInnerMostLoopIndices; i--;)
 145             block->innerMostLoopIndices[i] = UINT_MAX;
 146     }
 147     for (unsigned loopIndex = m_loops.size(); loopIndex--;) {
 148         NaturalLoop& loop = m_loops[loopIndex];
 149
 150         for (unsigned blockIndexInLoop = loop.size(); blockIndexInLoop--;) {
 151             BasicBlock* block = loop[blockIndexInLoop];
 152
 153             for (unsigned i = 0; i < BasicBlock::numberOfInnerMostLoopIndices; ++i) {
 154                 unsigned thisIndex = block->innerMostLoopIndices[i];
 155                 if (thisIndex == UINT_MAX || loop.size() < m_loops[thisIndex].size()) {
 156                     insertIntoBoundedVector(
 157                         block->innerMostLoopIndices, BasicBlock::numberOfInnerMostLoopIndices,
 158                         loopIndex, i);
 159                     break;
 160                 }
 161             }
 162         }
 163     }
 164
 165     // Now each block knows its inner-most loop and its next-to-inner-most loop. Use
 166     // this to figure out loop parenting.
 167     for (unsigned i = m_loops.size(); i--;) {
 168         NaturalLoop& loop = m_loops[i];
 169         RELEASE_ASSERT(loop.header()->innerMostLoopIndices[0] == i);
 170
 171         loop.m_outerLoopIndex = loop.header()->innerMostLoopIndices[1];
 172     }
 173
 174     if (validationEnabled()) {
 175         // Do some self-verification that we've done some of this correctly.
 176
 177         for (BlockIndex blockIndex = graph.numBlocks(); blockIndex--;) {
 178             BasicBlock* block = graph.block(blockIndex);
 179             if (!block)
 180                 continue;
 181
 182             Vector<const NaturalLoop*> simpleLoopsOf;
 183
 184             for (unsigned i = m_loops.size(); i--;) {
 185                 if (m_loops[i].contains(block))
 186                     simpleLoopsOf.append(&m_loops[i]);
 187             }
 188
 189             Vector<const NaturalLoop*> fancyLoopsOf = loopsOf(block);
 190
 191             std::sort(simpleLoopsOf.begin(), simpleLoopsOf.end());
 192             std::sort(fancyLoopsOf.begin(), fancyLoopsOf.end());
 193
 194             RELEASE_ASSERT(simpleLoopsOf == fancyLoopsOf);
 195         }
 196     }
 197
 198     if (verbose)
 199         dataLog("Results: ", *this, "\n");
 200 }
 201
 202 Vector<const NaturalLoop*> NaturalLoops::loopsOf(BasicBlock* block) const
 203 {
 204     Vector<const NaturalLoop*> result;
 205     for (const NaturalLoop* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop))
 206         result.append(loop);
 207     return result;
 208 }
 209
 210 void NaturalLoops::dump(PrintStream& out) const
 211 {
 212     out.print("NaturalLoops:{");
 213     CommaPrinter comma;
 214     for (unsigned i = 0; i < m_loops.size(); ++i)
 215         out.print(comma, m_loops[i]);
 216     out.print("}");
 217 }
 218
 219 } } // namespace JSC::DFG
 220
 221 #endif // ENABLE(DFG_JIT)
 222