[WTF] Import std::optional reference implementation as WTF::Optional
[WebKit-https.git] / Source / JavaScriptCore / jit / PCToCodeOriginMap.cpp
1 /*
2  * Copyright (C) 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 "PCToCodeOriginMap.h"
28
29 #if ENABLE(JIT)
30
31 #include "B3PCToOriginMap.h"
32 #include "DFGNode.h"
33 #include "LinkBuffer.h"
34
35 #if COMPILER(MSVC)
36 // See https://msdn.microsoft.com/en-us/library/4wz07268.aspx
37 #pragma warning(disable: 4333)
38 #endif
39
40 namespace JSC {
41
42 namespace {
43
44 class DeltaCompressionBuilder {
45 public:
46     DeltaCompressionBuilder(size_t maxSize)
47         : m_offset(0)
48         , m_maxSize(maxSize)
49     {
50         m_buffer = static_cast<uint8_t*>(fastMalloc(m_maxSize));
51     }
52
53     template <typename T>
54     void write(T item)
55     {
56         RELEASE_ASSERT(m_offset + sizeof(T) <= m_maxSize);
57         static const uint8_t mask = std::numeric_limits<uint8_t>::max();
58         for (unsigned i = 0; i < sizeof(T); i++) {
59             *(m_buffer + m_offset) = static_cast<uint8_t>(item & mask);
60             item = item >> (sizeof(uint8_t) * 8);
61             m_offset += 1;
62         }
63     }
64
65     uint8_t* m_buffer; 
66     size_t m_offset;
67     size_t m_maxSize;
68 };
69
70 class DeltaCompresseionReader {
71 public:
72     DeltaCompresseionReader(uint8_t* buffer, size_t size)
73         : m_buffer(buffer)
74         , m_size(size)
75         , m_offset(0)
76     { }
77
78     template <typename T>
79     T read()
80     {
81         RELEASE_ASSERT(m_offset + sizeof(T) <= m_size);
82         T result = 0;
83         for (unsigned i = 0; i < sizeof(T); i++) {
84             uint8_t bitsAsInt8 = *(m_buffer + m_offset);
85             T bits = static_cast<T>(bitsAsInt8);
86             bits = bits << (sizeof(uint8_t) * 8 * i);
87             result |= bits;
88             m_offset += 1;
89         }
90         return result;
91     }
92
93 private:
94     uint8_t* m_buffer;
95     size_t m_size;
96     size_t m_offset;
97 };
98
99 } // anonymous namespace
100
101 PCToCodeOriginMapBuilder::PCToCodeOriginMapBuilder(VM& vm)
102     : m_vm(vm)
103     , m_shouldBuildMapping(vm.shouldBuilderPCToCodeOriginMapping())
104 { }
105
106 PCToCodeOriginMapBuilder::PCToCodeOriginMapBuilder(PCToCodeOriginMapBuilder&& other)
107     : m_vm(other.m_vm)
108     , m_codeRanges(WTFMove(other.m_codeRanges))
109     , m_shouldBuildMapping(other.m_shouldBuildMapping)
110 { }
111
112 #if ENABLE(FTL_JIT)
113 PCToCodeOriginMapBuilder::PCToCodeOriginMapBuilder(VM& vm, B3::PCToOriginMap&& b3PCToOriginMap)
114     : m_vm(vm)
115     , m_shouldBuildMapping(vm.shouldBuilderPCToCodeOriginMapping())
116 {
117     if (!m_shouldBuildMapping)
118         return;
119
120     for (const B3::PCToOriginMap::OriginRange& originRange : b3PCToOriginMap.ranges()) {
121         DFG::Node* node = bitwise_cast<DFG::Node*>(originRange.origin.data());
122         if (node)
123             appendItem(originRange.label, node->origin.semantic);
124         else
125             appendItem(originRange.label, PCToCodeOriginMapBuilder::defaultCodeOrigin());
126     }
127 }
128 #endif
129
130 void PCToCodeOriginMapBuilder::appendItem(MacroAssembler::Label label, const CodeOrigin& codeOrigin)
131 {
132     if (!m_shouldBuildMapping)
133         return;
134
135     if (m_codeRanges.size()) {
136         if (m_codeRanges.last().end == label)
137             return;
138         m_codeRanges.last().end = label;
139         if (m_codeRanges.last().codeOrigin == codeOrigin || !codeOrigin)
140             return;
141     }
142
143     m_codeRanges.append(CodeRange{label, label, codeOrigin});
144 }
145
146
147 static const uint8_t sentinelPCDelta = 0;
148 static const int8_t sentinelBytecodeDelta = 0;
149
150 PCToCodeOriginMap::PCToCodeOriginMap(PCToCodeOriginMapBuilder&& builder, LinkBuffer& linkBuffer)
151 {
152     RELEASE_ASSERT(builder.didBuildMapping());
153
154     if (!builder.m_codeRanges.size()) {
155         m_pcRangeStart = std::numeric_limits<uintptr_t>::max();
156         m_pcRangeEnd = std::numeric_limits<uintptr_t>::max();
157
158         m_compressedPCBufferSize = 0;
159         m_compressedPCs = nullptr;
160
161         m_compressedCodeOriginsSize = 0;
162         m_compressedCodeOrigins = nullptr;
163
164         return;
165     }
166
167     // We do a final touch-up on the last range here because of how we generate the table.
168     // The final range (if non empty) would be ignored if we didn't append any (arbitrary)
169     // range as the last item of the vector.
170     PCToCodeOriginMapBuilder::CodeRange& last = builder.m_codeRanges.last();
171     if (!(last.start == last.end))
172         builder.m_codeRanges.append(PCToCodeOriginMapBuilder::CodeRange{ last.end, last.end, last.codeOrigin }); // This range will never actually be found, but it ensures the real last range is found.
173
174     DeltaCompressionBuilder pcCompressor((sizeof(uintptr_t) + sizeof(uint8_t)) * builder.m_codeRanges.size());
175     void* lastPCValue = nullptr;
176     auto buildPCTable = [&] (void* pcValue) {
177         RELEASE_ASSERT(pcValue > lastPCValue);
178         uintptr_t delta = bitwise_cast<uintptr_t>(pcValue) - bitwise_cast<uintptr_t>(lastPCValue);
179         RELEASE_ASSERT(delta != sentinelPCDelta);
180         lastPCValue = pcValue;
181         if (delta > std::numeric_limits<uint8_t>::max()) {
182             pcCompressor.write<uint8_t>(sentinelPCDelta);
183             pcCompressor.write<uintptr_t>(delta);
184             return;
185         }
186
187         pcCompressor.write<uint8_t>(static_cast<uint8_t>(delta));
188     };
189
190     DeltaCompressionBuilder codeOriginCompressor((sizeof(intptr_t) + sizeof(int8_t) + sizeof(int8_t) + sizeof(InlineCallFrame*)) * builder.m_codeRanges.size());
191     CodeOrigin lastCodeOrigin(0, nullptr);
192     auto buildCodeOriginTable = [&] (const CodeOrigin& codeOrigin) {
193         intptr_t delta = static_cast<intptr_t>(codeOrigin.bytecodeIndex) - static_cast<intptr_t>(lastCodeOrigin.bytecodeIndex);
194         lastCodeOrigin = codeOrigin;
195         if (delta > std::numeric_limits<int8_t>::max() || delta < std::numeric_limits<int8_t>::min() || delta == sentinelBytecodeDelta) {
196             codeOriginCompressor.write<int8_t>(sentinelBytecodeDelta);
197             codeOriginCompressor.write<intptr_t>(delta);
198         } else
199             codeOriginCompressor.write<int8_t>(static_cast<int8_t>(delta));
200
201         int8_t hasInlineCallFrameByte = codeOrigin.inlineCallFrame ? 1 : 0;
202         codeOriginCompressor.write<int8_t>(hasInlineCallFrameByte);
203         if (hasInlineCallFrameByte)
204             codeOriginCompressor.write<uintptr_t>(bitwise_cast<uintptr_t>(codeOrigin.inlineCallFrame));
205     };
206
207     m_pcRangeStart = bitwise_cast<uintptr_t>(linkBuffer.locationOf(builder.m_codeRanges.first().start).dataLocation());
208     m_pcRangeEnd = bitwise_cast<uintptr_t>(linkBuffer.locationOf(builder.m_codeRanges.last().end).dataLocation());
209     m_pcRangeEnd -= 1;
210
211     for (unsigned i = 0; i < builder.m_codeRanges.size(); i++) {
212         PCToCodeOriginMapBuilder::CodeRange& codeRange = builder.m_codeRanges[i];
213         void* start = linkBuffer.locationOf(codeRange.start).dataLocation();
214         void* end = linkBuffer.locationOf(codeRange.end).dataLocation();
215         ASSERT(m_pcRangeStart <= bitwise_cast<uintptr_t>(start));
216         ASSERT(m_pcRangeEnd >= bitwise_cast<uintptr_t>(end) - 1);
217         if (start == end)
218             ASSERT(i == builder.m_codeRanges.size() - 1);
219         if (i > 0)
220             ASSERT(linkBuffer.locationOf(builder.m_codeRanges[i - 1].end).dataLocation() == start);
221
222         buildPCTable(start);
223         buildCodeOriginTable(codeRange.codeOrigin);
224     }
225
226     m_compressedPCBufferSize = pcCompressor.m_offset;
227     m_compressedPCs = static_cast<uint8_t*>(fastRealloc(pcCompressor.m_buffer, m_compressedPCBufferSize));
228
229     m_compressedCodeOriginsSize = codeOriginCompressor.m_offset;
230     m_compressedCodeOrigins = static_cast<uint8_t*>(fastRealloc(codeOriginCompressor.m_buffer, m_compressedCodeOriginsSize));
231 }
232
233 PCToCodeOriginMap::~PCToCodeOriginMap()
234 {
235     if (m_compressedPCs)
236         fastFree(m_compressedPCs);
237     if (m_compressedCodeOrigins)
238         fastFree(m_compressedCodeOrigins);
239 }
240
241 double PCToCodeOriginMap::memorySize()
242 {
243     double size = 0;
244     size += m_compressedPCBufferSize;
245     size += m_compressedCodeOriginsSize;
246     return size;
247 }
248
249 std::optional<CodeOrigin> PCToCodeOriginMap::findPC(void* pc) const
250 {
251     uintptr_t pcAsInt = bitwise_cast<uintptr_t>(pc);
252     if (!(m_pcRangeStart <= pcAsInt && pcAsInt <= m_pcRangeEnd))
253         return std::nullopt;
254
255     uintptr_t currentPC = 0;
256     CodeOrigin currentCodeOrigin(0, nullptr);
257
258     DeltaCompresseionReader pcReader(m_compressedPCs, m_compressedPCBufferSize);
259     DeltaCompresseionReader codeOriginReader(m_compressedCodeOrigins, m_compressedCodeOriginsSize);
260     while (true) {
261         uintptr_t previousPC = currentPC;
262         {
263             uint8_t value = pcReader.read<uint8_t>();
264             uintptr_t delta;
265             if (value == sentinelPCDelta)
266                 delta = pcReader.read<uintptr_t>();
267             else
268                 delta = value;
269             currentPC += delta;
270         }
271
272         CodeOrigin previousOrigin = currentCodeOrigin;
273         {
274             int8_t value = codeOriginReader.read<int8_t>();
275             intptr_t delta;
276             if (value == sentinelBytecodeDelta)
277                 delta = codeOriginReader.read<intptr_t>();
278             else
279                 delta = static_cast<intptr_t>(value);
280
281             currentCodeOrigin.bytecodeIndex = static_cast<unsigned>(static_cast<intptr_t>(currentCodeOrigin.bytecodeIndex) + delta);
282
283             int8_t hasInlineFrame = codeOriginReader.read<int8_t>();
284             ASSERT(hasInlineFrame == 0 || hasInlineFrame == 1);
285             if (hasInlineFrame)
286                 currentCodeOrigin.inlineCallFrame = bitwise_cast<InlineCallFrame*>(codeOriginReader.read<uintptr_t>());
287             else
288                 currentCodeOrigin.inlineCallFrame = nullptr;
289         }
290
291         if (previousPC) {
292             uintptr_t startOfRange = previousPC;
293             // We subtract 1 because we generate end points inclusively in this table, even though we are interested in ranges of the form: [previousPC, currentPC)
294             uintptr_t endOfRange = currentPC - 1;
295             if (startOfRange <= pcAsInt && pcAsInt <= endOfRange)
296                 return std::optional<CodeOrigin>(previousOrigin); // We return previousOrigin here because CodeOrigin's are mapped to the startValue of the range.
297         }
298     }
299
300     RELEASE_ASSERT_NOT_REACHED();
301     return std::nullopt;
302 }
303
304 } // namespace JSC
305
306 #endif // ENABLE(JIT)