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