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