FTL should lower its abstract heaps to B3 heap ranges
[WebKit-https.git] / Source / JavaScriptCore / ftl / FTLAbstractHeap.cpp
1 /*
2  * Copyright (C) 2013, 2015-2016 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 #include "config.h"
27 #include "FTLAbstractHeap.h"
28
29 #if ENABLE(FTL_JIT)
30
31 #include "DFGCommon.h"
32 #include "FTLAbbreviatedTypes.h"
33 #include "FTLAbstractHeapRepository.h"
34 #include "FTLOutput.h"
35 #include "FTLTypedPointer.h"
36 #include "JSCInlines.h"
37 #include "Options.h"
38
39 namespace JSC { namespace FTL {
40
41 using namespace B3;
42
43 AbstractHeap::AbstractHeap(AbstractHeap* parent, const char* heapName, ptrdiff_t offset)
44     : m_offset(offset)
45     , m_heapName(heapName)
46 {
47     changeParent(parent);
48 }
49
50 void AbstractHeap::changeParent(AbstractHeap* parent)
51 {
52     if (m_parent) {
53         bool result = m_parent->m_children.removeFirst(this);
54         RELEASE_ASSERT(result);
55     }
56
57     m_parent = parent;
58
59     if (parent) {
60         ASSERT(!m_parent->m_children.contains(this));
61         m_parent->m_children.append(this);
62     }
63 }
64
65 void AbstractHeap::compute(unsigned begin)
66 {
67     // This recursively computes the ranges of the tree. This solves the following constraints
68     // in linear time:
69     //
70     // - A node's end is greater than its begin.
71     // - A node's begin is greater than or equal to its parent's begin.
72     // - A node's end is less than or equal to its parent's end.
73     // - The ranges are as small as possible.
74     //
75     // It's OK to recurse because we keep the depth of our abstract heap hierarchy fairly sane.
76     // I think that it gets 4 deep at most.
77
78     if (m_children.isEmpty()) {
79         // Must special-case leaves so that they use just one slot on the number line.
80         m_range = HeapRange(begin);
81         return;
82     }
83
84     unsigned current = begin;
85     for (AbstractHeap* child : m_children) {
86         child->compute(current);
87         current = child->range().end();
88     }
89
90     m_range = HeapRange(begin, current);
91 }
92
93 void AbstractHeap::shallowDump(PrintStream& out) const
94 {
95     out.print(heapName(), "(", m_offset, ")");
96     if (m_range)
97         out.print("<", m_range, ">");
98 }
99
100 void AbstractHeap::dump(PrintStream& out) const
101 {
102     shallowDump(out);
103     if (m_parent)
104         out.print("->", *m_parent);
105 }
106
107 void AbstractHeap::deepDump(PrintStream& out, unsigned indent) const
108 {
109     auto printIndent = [&] () {
110         for (unsigned i = indent; i--;)
111             out.print("    ");
112     };
113
114     printIndent();
115     shallowDump(out);
116
117     if (m_children.isEmpty()) {
118         out.print("\n");
119         return;
120     }
121
122     out.print(":\n");
123     for (AbstractHeap* child : m_children)
124         child->deepDump(out, indent + 1);
125 }
126
127 void AbstractHeap::badRangeError() const
128 {
129     dataLog("Heap does not have range: ", *this, "\n");
130     RELEASE_ASSERT_NOT_REACHED();
131 }
132
133 IndexedAbstractHeap::IndexedAbstractHeap(AbstractHeap* parent, const char* heapName, ptrdiff_t offset, size_t elementSize)
134     : m_heapForAnyIndex(parent, heapName)
135     , m_heapNameLength(strlen(heapName))
136     , m_offset(offset)
137     , m_elementSize(elementSize)
138 {
139 }
140
141 IndexedAbstractHeap::~IndexedAbstractHeap()
142 {
143 }
144
145 TypedPointer IndexedAbstractHeap::baseIndex(Output& out, LValue base, LValue index, JSValue indexAsConstant, ptrdiff_t offset)
146 {
147     if (indexAsConstant.isInt32())
148         return out.address(base, at(indexAsConstant.asInt32()), offset);
149
150     LValue result = out.add(base, out.mul(index, out.constIntPtr(m_elementSize)));
151     
152     return TypedPointer(atAnyIndex(), out.addPtr(result, m_offset + offset));
153 }
154
155 const AbstractHeap& IndexedAbstractHeap::atSlow(ptrdiff_t index)
156 {
157     ASSERT(static_cast<size_t>(index) >= m_smallIndices.size());
158     
159     if (UNLIKELY(!m_largeIndices))
160         m_largeIndices = std::make_unique<MapType>();
161
162     std::unique_ptr<AbstractHeap>& field = m_largeIndices->add(index, nullptr).iterator->value;
163     if (!field) {
164         field = std::make_unique<AbstractHeap>();
165         initialize(*field, index);
166     }
167
168     return *field;
169 }
170
171 void IndexedAbstractHeap::initialize(AbstractHeap& field, ptrdiff_t signedIndex)
172 {
173     // Build up a name of the form:
174     //
175     //    heapName_hexIndex
176     //
177     // or:
178     //
179     //    heapName_neg_hexIndex
180     //
181     // For example if you access an indexed heap called FooBar at index 5, you'll
182     // get:
183     //
184     //    FooBar_5
185     //
186     // Or if you access an indexed heap called Blah at index -10, you'll get:
187     //
188     //    Blah_neg_A
189     //
190     // This naming convention comes from our previous use of LLVM. It's not clear that we need
191     // it anymore, though it is sort of nifty. Basically, B3 doesn't need string names for
192     // abstract heaps, but the fact that we have a reasonably efficient way to always name the
193     // heaps will probably come in handy for debugging.
194     
195     static const char* negSplit = "_neg_";
196     static const char* posSplit = "_";
197     
198     bool negative;
199     size_t index;
200     if (signedIndex < 0) {
201         negative = true;
202         index = -signedIndex;
203     } else {
204         negative = false;
205         index = signedIndex;
206     }
207     
208     for (unsigned power = 4; power <= sizeof(void*) * 8; power += 4) {
209         if (isGreaterThanNonZeroPowerOfTwo(index, power))
210             continue;
211         
212         unsigned numHexlets = power >> 2;
213         
214         size_t stringLength = m_heapNameLength + (negative ? strlen(negSplit) : strlen(posSplit)) + numHexlets;
215         char* characters;
216         m_largeIndexNames.append(CString::newUninitialized(stringLength, characters));
217         
218         memcpy(characters, m_heapForAnyIndex.heapName(), m_heapNameLength);
219         if (negative)
220             memcpy(characters + m_heapNameLength, negSplit, strlen(negSplit));
221         else
222             memcpy(characters + m_heapNameLength, posSplit, strlen(posSplit));
223         
224         size_t accumulator = index;
225         for (unsigned i = 0; i < numHexlets; ++i) {
226             characters[stringLength - i - 1] = lowerNibbleToASCIIHexDigit(accumulator);
227             accumulator >>= 4;
228         }
229         
230         field.initialize(&m_heapForAnyIndex, characters, m_offset + signedIndex * m_elementSize);
231         return;
232     }
233     
234     RELEASE_ASSERT_NOT_REACHED();
235 }
236
237 void IndexedAbstractHeap::dump(PrintStream& out) const
238 {
239     out.print("Indexed:", atAnyIndex());
240 }
241
242 NumberedAbstractHeap::NumberedAbstractHeap(AbstractHeap* heap, const char* heapName)
243     : m_indexedHeap(heap, heapName, 0, 1)
244 {
245 }
246
247 NumberedAbstractHeap::~NumberedAbstractHeap()
248 {
249 }
250
251 void NumberedAbstractHeap::dump(PrintStream& out) const
252 {
253     out.print("Numbered: ", atAnyNumber());
254 }
255
256 AbsoluteAbstractHeap::AbsoluteAbstractHeap(AbstractHeap* heap, const char* heapName)
257     : m_indexedHeap(heap, heapName, 0, 1)
258 {
259 }
260
261 AbsoluteAbstractHeap::~AbsoluteAbstractHeap()
262 {
263 }
264
265 void AbsoluteAbstractHeap::dump(PrintStream& out) const
266 {
267     out.print("Absolute:", atAnyAddress());
268 }
269
270 } } // namespace JSC::FTL
271
272 #endif // ENABLE(FTL_JIT)
273