dfg/DFGNaturalLoops.h

   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
  35 namespace JSC { namespace DFG {
  36
  37 class NaturalLoops;
  38
  39 class NaturalLoop {
  40 public:
  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;
  80 private:
  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
  91 class NaturalLoops : public Analysis<NaturalLoops> {
  92 public:
  93     NaturalLoops();
  94     ~NaturalLoops();
  95
  96     void computeDependencies(Graph&);
  97     void compute(Graph&);
  98
  99     unsigned numLoops() const
 100     {
 101         ASSERT(isValid());
 102         return m_loops.size();
 103     }
 104     const NaturalLoop& loop(unsigned i) const
 105     {
 106         ASSERT(isValid());
 107         return m_loops[i];
 108     }
 109
 110     // Return either null if the block isn't a loop header, or the
 111     // loop it belongs to.
 112     const NaturalLoop* headerOf(BasicBlock* block) const
 113     {
 114         ASSERT(isValid());
 115         const NaturalLoop* loop = innerMostLoopOf(block);
 116         if (!loop)
 117             return 0;
 118         if (loop->header() == block)
 119             return loop;
 120         if (!ASSERT_DISABLED) {
 121             for (; loop; loop = innerMostOuterLoop(*loop))
 122                 ASSERT(loop->header() != block);
 123         }
 124         return 0;
 125     }
 126
 127     const NaturalLoop* innerMostLoopOf(BasicBlock* block) const
 128     {
 129         ASSERT(isValid());
 130         unsigned index = block->innerMostLoopIndices[0];
 131         if (index == UINT_MAX)
 132             return 0;
 133         return &m_loops[index];
 134     }
 135
 136     const NaturalLoop* innerMostOuterLoop(const NaturalLoop& loop) const
 137     {
 138         ASSERT(isValid());
 139         if (loop.m_outerLoopIndex == UINT_MAX)
 140             return 0;
 141         return &m_loops[loop.m_outerLoopIndex];
 142     }
 143
 144     bool belongsTo(BasicBlock* block, const NaturalLoop& candidateLoop) const
 145     {
 146         ASSERT(isValid());
 147         // It's faster to do this test using the loop itself, if it's small.
 148         if (candidateLoop.size() < 4)
 149             return candidateLoop.contains(block);
 150
 151         for (const NaturalLoop* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop)) {
 152             if (loop == &candidateLoop)
 153                 return true;
 154         }
 155         return false;
 156     }
 157
 158     unsigned loopDepth(BasicBlock* block) const
 159     {
 160         unsigned depth = 0;
 161         for (const NaturalLoop* loop = innerMostLoopOf(block); loop; loop = innerMostOuterLoop(*loop))
 162             depth++;
 163         return depth;
 164     }
 165
 166     // Return the indices of all loops this belongs to.
 167     Vector<const NaturalLoop*> loopsOf(BasicBlock*) const;
 168
 169     void dump(PrintStream&) const;
 170 private:
 171     // If we ever had a scalability problem in our natural loop finder, we could
 172     // use some HashMap's here. But it just feels a heck of a lot less convenient.
 173     Vector<NaturalLoop, 4> m_loops;
 174 };
 175
 176 } } // namespace JSC::DFG
 177
 178 #endif // ENABLE(DFG_JIT)
 179
 180 #endif // DFGNaturalLoops_h
 181