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 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;
 169 private:
 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