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