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#ifndef DFGNaturalLoops_h 27#define DFGNaturalLoops_h 28 29#if ENABLE(DFG_JIT) 30 31#include "DFGAnalysis.h" 32#include "DFGBasicBlock.h" 33#include "DFGCommon.h" 34 35namespace JSC { namespace DFG { 36 37class NaturalLoops; 38 39class NaturalLoop { 40public: 41 NaturalLoop() 42 : m_header(0) 43 , m_outerLoopIndex(UINT_MAX) 44 { 45 } 46 47 NaturalLoop(BasicBlock* header, unsigned index) 48 : m_header(header) 49 , m_outerLoopIndex(UINT_MAX) 50 , m_index(index) 51 { 52 } 53 54 BasicBlock* header() const { return m_header; } 55 56 unsigned size() const { return m_body.size(); } 57 BasicBlock* at(unsigned i) const { return m_body[i]; } 58 BasicBlock* operator[](unsigned i) const { return at(i); } 59 60 // This is the slower, but simpler, way of asking if a block belongs to 61 // a natural loop. It's faster to call NaturalLoops::belongsTo(), which 62 // tries to be O(loop depth) rather than O(loop size). Loop depth is 63 // almost always smaller than loop size. A *lot* smaller. 64 bool contains(BasicBlock* block) const 65 { 66 for (unsigned i = m_body.size(); i--;) { 67 if (m_body[i] == block) 68 return true; 69 } 70 ASSERT(block != header()); // Header should be contained. 71 return false; 72 } 73 74 // The index of this loop in NaturalLoops. 75 unsigned index() const { return m_index; } 76 77 bool isOuterMostLoop() const { return m_outerLoopIndex == UINT_MAX; } 78 79 void dump(PrintStream&) const; 80private: 81 friend class NaturalLoops; 82 83 void addBlock(BasicBlock* block) { m_body.append(block); } 84 85 BasicBlock* m_header; 86 Vector<BasicBlock*, 4> m_body; 87 unsigned m_outerLoopIndex; 88 unsigned m_index; 89}; 90 91class NaturalLoops : public Analysis<NaturalLoops> { 92public: 93 NaturalLoops(); 94 ~NaturalLoops(); 95 96 void compute(Graph&); 97 98 unsigned numLoops() const 99 { 100 ASSERT(isValid()); 101 return m_loops.size(); 102 } 103 const NaturalLoop& loop(unsigned i) const 104 { 105 ASSERT(isValid()); 106 return m_loops[i]; 107 } 108 109 // Return either null if the block isn't a loop header, or the 110 // loop it belongs to. 111 const NaturalLoop* headerOf(BasicBlock* block) const 112 { 113 ASSERT(isValid()); 114 const NaturalLoop* loop = innerMostLoopOf(block); 115 if (!loop) 116 return 0; 117 if (loop->header() == block) 118 return loop; 119 if (!ASSERT_DISABLED) { 120 for (; loop; loop = innerMostOuterLoop(*loop)) 121 ASSERT(loop->header() != block); 122 } 123 return 0; 124 } 125 126 const NaturalLoop* innerMostLoopOf(BasicBlock* block) const 127 { 128 ASSERT(isValid()); 129 unsigned index = block->innerMostLoopIndices[0]; 130 if (index == UINT_MAX) 131 return 0; 132 return &m_loops[index]; 133 } 134 135 const NaturalLoop* innerMostOuterLoop(const NaturalLoop& loop) const 136 { 137 ASSERT(isValid()); 138 if (loop.m_outerLoopIndex == UINT_MAX) 139 return 0; 140 return &m_loops[loop.m_outerLoopIndex]; 141 } 142 143 bool belongsTo(BasicBlock* block, const NaturalLoop& candidateLoop) const 144 { 145 ASSERT(isValid()); 146 // It's faster to do this test using the loop itself, if it's small. 147 if (candidateLoop.size() < 4) 148 return candidateLoop.contains(block); 149 150 for (const NaturalLoop* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop)) { 151 if (loop == &candidateLoop) 152 return true; 153 } 154 return false; 155 } 156 157 unsigned loopDepth(BasicBlock* block) const 158 { 159 unsigned depth = 0; 160 for (const NaturalLoop* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop)) 161 depth++; 162 return depth; 163 } 164 165 // Return the indices of all loops this belongs to. 166 Vector<const NaturalLoop*> loopsOf(BasicBlock*) const; 167 168 void dump(PrintStream&) const; 169private: 170 // If we ever had a scalability problem in our natural loop finder, we could 171 // use some HashMap's here. But it just feels a heck of a lot less convenient. 172 Vector<NaturalLoop, 4> m_loops; 173}; 174 175} } // namespace JSC::DFG 176 177#endif // ENABLE(DFG_JIT) 178 179#endif // DFGNaturalLoops_h 180 181