1/*
2 * Copyright (C) 2015-2019 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(B3_JIT)
29
30#include "B3HeapRange.h"
31#include "B3Kind.h"
32#include "B3Origin.h"
33#include "B3Type.h"
34#include <wtf/HashTable.h>
35
36namespace JSC { namespace B3 {
37
38class Procedure;
39class Value;
40
41// ValueKeys are useful for CSE. They abstractly describe the value that a Value returns when it
42// executes. Any Value that has the same ValueKey is guaranteed to return the same value, provided
43// that they return a non-empty ValueKey. Operations that have effects, or that can have their
44// behavior affected by other operations' effects, will return an empty ValueKey. You have to use
45// other mechanisms for doing CSE for impure operations.
46
47class ValueKey {
48public:
49 ValueKey()
50 {
51 }
52
53 ValueKey(Kind kind, Type type)
54 : m_kind(kind)
55 , m_type(type)
56 {
57 }
58
59 ValueKey(Kind, Type, Value* child);
60
61 ValueKey(Kind, Type, Value* left, Value* right);
62
63 ValueKey(Kind, Type, Value* a, Value* b, Value* c);
64
65 ValueKey(Kind kind, Type type, int64_t value)
66 : m_kind(kind)
67 , m_type(type)
68 {
69 u.value = value;
70 }
71
72 ValueKey(Kind kind, Type type, double value)
73 : m_kind(kind)
74 , m_type(type)
75 {
76 u.doubleValue = value;
77 }
78
79 ValueKey(Kind kind, Type type, float value)
80 : m_kind(kind)
81 , m_type(type)
82 {
83 // This means that upper 32bit of u.value is 0.
84 u.floatValue = value;
85 }
86
87 static ValueKey intConstant(Type type, int64_t value);
88
89 Kind kind() const { return m_kind; }
90 Opcode opcode() const { return kind().opcode(); }
91 Type type() const { return m_type; }
92 unsigned childIndex(unsigned index) const { return u.indices[index]; }
93 Value* child(Procedure&, unsigned index) const;
94 int64_t value() const { return u.value; }
95 double doubleValue() const { return u.doubleValue; }
96 float floatValue() const { return u.floatValue; }
97
98 bool operator==(const ValueKey& other) const
99 {
100 return m_kind == other.m_kind
101 && m_type == other.m_type
102 && u == other.u;
103 }
104
105 bool operator!=(const ValueKey& other) const
106 {
107 return !(*this == other);
108 }
109
110 unsigned hash() const
111 {
112 return m_kind.hash() + m_type.hash() + WTF::IntHash<int32_t>::hash(u.indices[0]) + u.indices[1] + u.indices[2];
113 }
114
115 explicit operator bool() const { return *this != ValueKey(); }
116
117 void dump(PrintStream&) const;
118
119 bool canMaterialize() const
120 {
121 if (!*this)
122 return false;
123 switch (opcode()) {
124 case CheckAdd:
125 case CheckSub:
126 case CheckMul:
127 return false;
128 default:
129 return true;
130 }
131 }
132
133 bool isConstant() const
134 {
135 return B3::isConstant(opcode());
136 }
137
138 // Attempts to materialize the Value for this ValueKey. May return nullptr if the value cannot
139 // be materialized. This happens for CheckAdd and friends. You can use canMaterialize() to check
140 // if your key is materializable.
141 Value* materialize(Procedure&, Origin) const;
142
143 ValueKey(WTF::HashTableDeletedValueType)
144 : m_type { Int32 }
145 {
146 }
147
148 bool isHashTableDeletedValue() const
149 {
150 return *this == ValueKey(WTF::HashTableDeletedValue);
151 }
152
153private:
154 Kind m_kind;
155 Type m_type { Void };
156 union U {
157 unsigned indices[3];
158 int64_t value;
159 double doubleValue;
160 float floatValue;
161
162 U()
163 {
164 indices[0] = 0;
165 indices[1] = 0;
166 indices[2] = 0;
167 }
168
169 bool operator==(const U& other) const
170 {
171 return indices[0] == other.indices[0]
172 && indices[1] == other.indices[1]
173 && indices[2] == other.indices[2];
174 }
175 } u;
176};
177
178struct ValueKeyHash {
179 static unsigned hash(const ValueKey& key) { return key.hash(); }
180 static bool equal(const ValueKey& a, const ValueKey& b) { return a == b; }
181 static constexpr bool safeToCompareToEmptyOrDeleted = true;
182};
183
184} } // namespace JSC::B3
185
186namespace WTF {
187
188template<typename T> struct DefaultHash;
189template<> struct DefaultHash<JSC::B3::ValueKey> {
190 typedef JSC::B3::ValueKeyHash Hash;
191};
192
193template<typename T> struct HashTraits;
194template<> struct HashTraits<JSC::B3::ValueKey> : public SimpleClassHashTraits<JSC::B3::ValueKey> {
195 static constexpr bool emptyValueIsZero = false;
196};
197
198} // namespace WTF
199
200#endif // ENABLE(B3_JIT)
201