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 FTLAbstractHeap_h
27#define FTLAbstractHeap_h
28
29#if ENABLE(FTL_JIT)
30
31#include "FTLAbbreviations.h"
32#include "JSCJSValue.h"
33#include <array>
34#include <wtf/FastMalloc.h>
35#include <wtf/HashMap.h>
36#include <wtf/Noncopyable.h>
37#include <wtf/OwnPtr.h>
38#include <wtf/Vector.h>
39#include <wtf/text/CString.h>
40
41namespace JSC { namespace FTL {
42
43// The FTL JIT tries to aid LLVM's TBAA. The FTL's notion of how this
44// happens is the AbstractHeap. AbstractHeaps are a simple type system
45// with sub-typing.
46
47class AbstractHeapRepository;
48class Output;
49class TypedPointer;
50
51class AbstractHeap {
52    WTF_MAKE_NONCOPYABLE(AbstractHeap); WTF_MAKE_FAST_ALLOCATED;
53public:
54    AbstractHeap()
55        : m_parent(0)
56        , m_heapName(0)
57        , m_tbaaMetadata(0)
58    {
59    }
60
61    AbstractHeap(AbstractHeap* parent, const char* heapName)
62        : m_parent(parent)
63        , m_heapName(heapName)
64        , m_tbaaMetadata(0)
65    {
66    }
67
68    bool isInitialized() const { return !!m_heapName; }
69
70    void initialize(AbstractHeap* parent, const char* heapName)
71    {
72        m_parent = parent;
73        m_heapName = heapName;
74    }
75
76    AbstractHeap* parent() const
77    {
78        ASSERT(isInitialized());
79        return m_parent;
80    }
81
82    const char* heapName() const
83    {
84        ASSERT(isInitialized());
85        return m_heapName;
86    }
87
88    LValue tbaaMetadata(const AbstractHeapRepository& repository) const
89    {
90        ASSERT(isInitialized());
91        if (LIKELY(!!m_tbaaMetadata))
92            return m_tbaaMetadata;
93        return tbaaMetadataSlow(repository);
94    }
95
96    void decorateInstruction(LValue instruction, const AbstractHeapRepository&) const;
97
98private:
99    friend class AbstractHeapRepository;
100
101    LValue tbaaMetadataSlow(const AbstractHeapRepository&) const;
102
103    AbstractHeap* m_parent;
104    const char* m_heapName;
105    mutable LValue m_tbaaMetadata;
106};
107
108// Think of "AbstractField" as being an "AbstractHeapWithOffset". I would have named
109// it the latter except that I don't like typing that much.
110class AbstractField : public AbstractHeap {
111public:
112    AbstractField()
113    {
114    }
115
116    AbstractField(AbstractHeap* parent, const char* heapName, ptrdiff_t offset)
117        : AbstractHeap(parent, heapName)
118        , m_offset(offset)
119    {
120    }
121
122    void initialize(AbstractHeap* parent, const char* heapName, ptrdiff_t offset)
123    {
124        AbstractHeap::initialize(parent, heapName);
125        m_offset = offset;
126    }
127
128    ptrdiff_t offset() const
129    {
130        ASSERT(isInitialized());
131        return m_offset;
132    }
133
134private:
135    ptrdiff_t m_offset;
136};
137
138class IndexedAbstractHeap {
139public:
140    IndexedAbstractHeap(LContext, AbstractHeap* parent, const char* heapName, ptrdiff_t offset, size_t elementSize);
141    ~IndexedAbstractHeap();
142
143    const AbstractHeap& atAnyIndex() const { return m_heapForAnyIndex; }
144
145    const AbstractField& at(ptrdiff_t index)
146    {
147        if (static_cast<size_t>(index) < m_smallIndices.size())
148            return returnInitialized(m_smallIndices[index], index);
149        return atSlow(index);
150    }
151
152    const AbstractField& operator[](ptrdiff_t index) { return at(index); }
153
154    TypedPointer baseIndex(Output& out, LValue base, LValue index, JSValue indexAsConstant = JSValue(), ptrdiff_t offset = 0);
155
156private:
157    const AbstractField& returnInitialized(AbstractField& field, ptrdiff_t index)
158    {
159        if (UNLIKELY(!field.isInitialized()))
160            initialize(field, index);
161        return field;
162    }
163
164    const AbstractField& atSlow(ptrdiff_t index);
165    void initialize(AbstractField& field, ptrdiff_t index);
166
167    AbstractHeap m_heapForAnyIndex;
168    size_t m_heapNameLength;
169    ptrdiff_t m_offset;
170    size_t m_elementSize;
171    LValue m_scaleTerm;
172    bool m_canShift;
173    std::array<AbstractField, 16> m_smallIndices;
174
175    struct WithoutZeroOrOneHashTraits : WTF::GenericHashTraits<ptrdiff_t> {
176        static void constructDeletedValue(ptrdiff_t& slot) { slot = 1; }
177        static bool isDeletedValue(ptrdiff_t value) { return value == 1; }
178    };
179    typedef HashMap<ptrdiff_t, std::unique_ptr<AbstractField>, WTF::IntHash<ptrdiff_t>, WithoutZeroOrOneHashTraits> MapType;
180
181    OwnPtr<MapType> m_largeIndices;
182    Vector<CString, 16> m_largeIndexNames;
183};
184
185// A numbered abstract heap is like an indexed abstract heap, except that you
186// can't rely on there being a relationship between the number you use to
187// retrieve the sub-heap, and the offset that this heap has. (In particular,
188// the sub-heaps don't have indices.)
189
190class NumberedAbstractHeap {
191public:
192    NumberedAbstractHeap(LContext, AbstractHeap* parent, const char* heapName);
193    ~NumberedAbstractHeap();
194
195    const AbstractHeap& atAnyNumber() const { return m_indexedHeap.atAnyIndex(); }
196
197    const AbstractHeap& at(unsigned number) { return m_indexedHeap.at(number); }
198    const AbstractHeap& operator[](unsigned number) { return at(number); }
199
200private:
201
202    // We use the fact that the indexed heap already has a superset of the
203    // functionality we need.
204    IndexedAbstractHeap m_indexedHeap;
205};
206
207class AbsoluteAbstractHeap {
208public:
209    AbsoluteAbstractHeap(LContext, AbstractHeap* parent, const char* heapName);
210    ~AbsoluteAbstractHeap();
211
212    const AbstractHeap& atAnyAddress() const { return m_indexedHeap.atAnyIndex(); }
213
214    const AbstractHeap& at(void* address)
215    {
216        return m_indexedHeap.at(bitwise_cast<ptrdiff_t>(address));
217    }
218
219    const AbstractHeap& operator[](void* address) { return at(address); }
220
221private:
222    // The trick here is that the indexed heap is "indexed" by a pointer-width
223    // integer. Pointers are themselves pointer-width integers. So we can reuse
224    // all of the functionality.
225    IndexedAbstractHeap m_indexedHeap;
226};
227
228} } // namespace JSC::FTL
229
230#endif // ENABLE(FTL_JIT)
231
232#endif // FTLAbstractHeap_h
233
234