1/*
2 * Copyright (C) 2015-2017 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 "B3Bank.h"
31#include "B3Effects.h"
32#include "B3FrequentedBlock.h"
33#include "B3Kind.h"
34#include "B3Origin.h"
35#include "B3SparseCollection.h"
36#include "B3Type.h"
37#include "B3ValueKey.h"
38#include "B3Width.h"
39#include <wtf/CommaPrinter.h>
40#include <wtf/FastMalloc.h>
41#include <wtf/Noncopyable.h>
42#include <wtf/StdLibExtras.h>
43#include <wtf/TriState.h>
44
45namespace JSC { namespace B3 {
46
47class BasicBlock;
48class CheckValue;
49class InsertionSet;
50class PhiChildren;
51class Procedure;
52
53class JS_EXPORT_PRIVATE Value {
54 WTF_MAKE_FAST_ALLOCATED;
55public:
56 typedef Vector<Value*, 3> AdjacencyList;
57
58 static const char* const dumpPrefix;
59
60 static bool accepts(Kind) { return true; }
61
62 virtual ~Value();
63
64 unsigned index() const { return m_index; }
65
66 // Note that the kind is immutable, except for replacing values with:
67 // Identity, Nop, Oops, Jump, and Phi. See below for replaceWithXXX() methods.
68 Kind kind() const { return m_kind; }
69
70 Opcode opcode() const { return kind().opcode(); }
71
72 // Note that the kind is meant to be immutable. Do this when you know that this is safe. It's not
73 // usually safe.
74 void setKindUnsafely(Kind kind) { m_kind = kind; }
75 void setOpcodeUnsafely(Opcode opcode) { m_kind.setOpcode(opcode); }
76
77 // It's good practice to mirror Kind methods here, so you can say value->isBlah()
78 // instead of value->kind().isBlah().
79 bool isChill() const { return kind().isChill(); }
80 bool traps() const { return kind().traps(); }
81
82 Origin origin() const { return m_origin; }
83 void setOrigin(Origin origin) { m_origin = origin; }
84
85 Value*& child(unsigned index) { return m_children[index]; }
86 Value* child(unsigned index) const { return m_children[index]; }
87
88 Value*& lastChild() { return m_children.last(); }
89 Value* lastChild() const { return m_children.last(); }
90
91 unsigned numChildren() const { return m_children.size(); }
92
93 Type type() const { return m_type; }
94 void setType(Type type) { m_type = type; }
95
96 // This is useful when lowering. Note that this is only valid for non-void values.
97 Bank resultBank() const { return bankForType(type()); }
98 Width resultWidth() const { return widthForType(type()); }
99
100 AdjacencyList& children() { return m_children; }
101 const AdjacencyList& children() const { return m_children; }
102
103 // If you want to replace all uses of this value with a different value, then replace this
104 // value with Identity. Then do a pass of performSubstitution() on all of the values that use
105 // this one. Usually we do all of this in one pass in pre-order, which ensures that the
106 // X->replaceWithIdentity() calls happen before the performSubstitution() calls on X's users.
107 void replaceWithIdentity(Value*);
108
109 // It's often necessary to kill a value. It's tempting to replace the value with Nop or to
110 // just remove it. But unless you are sure that the value is Void, you will probably still
111 // have other values that use this one. Sure, you may kill those later, or you might not. This
112 // method lets you kill a value safely. It will replace Void values with Nop and non-Void
113 // values with Identities on bottom constants. For this reason, this takes a callback that is
114 // responsible for creating bottoms. There's a utility for this, see B3BottomProvider.h. You
115 // can also access that utility using replaceWithBottom(InsertionSet&, size_t).
116 //
117 // You're guaranteed that bottom is zero.
118 template<typename BottomProvider>
119 void replaceWithBottom(const BottomProvider&);
120
121 void replaceWithBottom(InsertionSet&, size_t index);
122
123 // Use this if you want to kill a value and you are sure that the value is Void.
124 void replaceWithNop();
125
126 // Use this if you want to kill a value and you are sure that nobody is using it anymore.
127 void replaceWithNopIgnoringType();
128
129 void replaceWithPhi();
130
131 // These transformations are only valid for terminals.
132 void replaceWithJump(BasicBlock* owner, FrequentedBlock);
133 void replaceWithOops(BasicBlock* owner);
134
135 // You can use this form if owners are valid. They're usually not valid.
136 void replaceWithJump(FrequentedBlock);
137 void replaceWithOops();
138
139 void dump(PrintStream&) const;
140 void deepDump(const Procedure*, PrintStream&) const;
141
142 virtual void dumpSuccessors(const BasicBlock*, PrintStream&) const;
143
144 // This is how you cast Values. For example, if you want to do something provided that we have a
145 // ArgumentRegValue, you can do:
146 //
147 // if (ArgumentRegValue* argumentReg = value->as<ArgumentRegValue>()) {
148 // things
149 // }
150 //
151 // This will return null if this kind() != ArgumentReg. This works because this returns nullptr
152 // if T::accepts(kind()) returns false.
153 template<typename T>
154 T* as();
155 template<typename T>
156 const T* as() const;
157
158 // What follows are a bunch of helpers for inspecting and modifying values. Note that we have a
159 // bunch of different idioms for implementing such helpers. You can use virtual methods, and
160 // override from the various Value subclasses. You can put the method inside Value and make it
161 // non-virtual, and the implementation can switch on kind. The method could be inline or not.
162 // If a method is specific to some Value subclass, you could put it in the subclass, or you could
163 // put it on Value anyway. It's fine to pick whatever feels right, and we shouldn't restrict
164 // ourselves to any particular idiom.
165
166 bool isConstant() const;
167 bool isInteger() const;
168
169 virtual Value* negConstant(Procedure&) const;
170 virtual Value* addConstant(Procedure&, int32_t other) const;
171 virtual Value* addConstant(Procedure&, const Value* other) const;
172 virtual Value* subConstant(Procedure&, const Value* other) const;
173 virtual Value* mulConstant(Procedure&, const Value* other) const;
174 virtual Value* checkAddConstant(Procedure&, const Value* other) const;
175 virtual Value* checkSubConstant(Procedure&, const Value* other) const;
176 virtual Value* checkMulConstant(Procedure&, const Value* other) const;
177 virtual Value* checkNegConstant(Procedure&) const;
178 virtual Value* divConstant(Procedure&, const Value* other) const; // This chooses Div<Chill> semantics for integers.
179 virtual Value* uDivConstant(Procedure&, const Value* other) const;
180 virtual Value* modConstant(Procedure&, const Value* other) const; // This chooses Mod<Chill> semantics.
181 virtual Value* uModConstant(Procedure&, const Value* other) const;
182 virtual Value* bitAndConstant(Procedure&, const Value* other) const;
183 virtual Value* bitOrConstant(Procedure&, const Value* other) const;
184 virtual Value* bitXorConstant(Procedure&, const Value* other) const;
185 virtual Value* shlConstant(Procedure&, const Value* other) const;
186 virtual Value* sShrConstant(Procedure&, const Value* other) const;
187 virtual Value* zShrConstant(Procedure&, const Value* other) const;
188 virtual Value* rotRConstant(Procedure&, const Value* other) const;
189 virtual Value* rotLConstant(Procedure&, const Value* other) const;
190 virtual Value* bitwiseCastConstant(Procedure&) const;
191 virtual Value* iToDConstant(Procedure&) const;
192 virtual Value* iToFConstant(Procedure&) const;
193 virtual Value* doubleToFloatConstant(Procedure&) const;
194 virtual Value* floatToDoubleConstant(Procedure&) const;
195 virtual Value* absConstant(Procedure&) const;
196 virtual Value* ceilConstant(Procedure&) const;
197 virtual Value* floorConstant(Procedure&) const;
198 virtual Value* sqrtConstant(Procedure&) const;
199
200 virtual TriState equalConstant(const Value* other) const;
201 virtual TriState notEqualConstant(const Value* other) const;
202 virtual TriState lessThanConstant(const Value* other) const;
203 virtual TriState greaterThanConstant(const Value* other) const;
204 virtual TriState lessEqualConstant(const Value* other) const;
205 virtual TriState greaterEqualConstant(const Value* other) const;
206 virtual TriState aboveConstant(const Value* other) const;
207 virtual TriState belowConstant(const Value* other) const;
208 virtual TriState aboveEqualConstant(const Value* other) const;
209 virtual TriState belowEqualConstant(const Value* other) const;
210 virtual TriState equalOrUnorderedConstant(const Value* other) const;
211
212 // If the value is a comparison then this returns the inverted form of that comparison, if
213 // possible. It can be impossible for double comparisons, where for example LessThan and
214 // GreaterEqual behave differently. If this returns a value, it is a new value, which must be
215 // either inserted into some block or deleted.
216 Value* invertedCompare(Procedure&) const;
217
218 bool hasInt32() const;
219 int32_t asInt32() const;
220 bool isInt32(int32_t) const;
221
222 bool hasInt64() const;
223 int64_t asInt64() const;
224 bool isInt64(int64_t) const;
225
226 bool hasInt() const;
227 int64_t asInt() const;
228 bool isInt(int64_t value) const;
229
230 bool hasIntPtr() const;
231 intptr_t asIntPtr() const;
232 bool isIntPtr(intptr_t) const;
233
234 bool hasDouble() const;
235 double asDouble() const;
236 bool isEqualToDouble(double) const; // We say "isEqualToDouble" because "isDouble" would be a bit equality.
237
238 bool hasFloat() const;
239 float asFloat() const;
240
241 bool hasNumber() const;
242 template<typename T> bool isRepresentableAs() const;
243 template<typename T> T asNumber() const;
244
245 // Booleans in B3 are Const32(0) or Const32(1). So this is true if the type is Int32 and the only
246 // possible return values are 0 or 1. It's OK for this method to conservatively return false.
247 bool returnsBool() const;
248
249 bool isNegativeZero() const;
250
251 bool isRounded() const;
252
253 TriState asTriState() const;
254 bool isLikeZero() const { return asTriState() == FalseTriState; }
255 bool isLikeNonZero() const { return asTriState() == TrueTriState; }
256
257 Effects effects() const;
258
259 // This returns a ValueKey that describes that this Value returns when it executes. Returns an
260 // empty ValueKey if this Value is impure. Note that an operation that returns Void could still
261 // have a non-empty ValueKey. This happens for example with Check operations.
262 ValueKey key() const;
263
264 Value* foldIdentity() const;
265
266 // Makes sure that none of the children are Identity's. If a child points to Identity, this will
267 // repoint it at the Identity's child. For simplicity, this will follow arbitrarily long chains
268 // of Identity's.
269 bool performSubstitution();
270
271 // Free values are those whose presence is guaranteed not to hurt code. We consider constants,
272 // Identities, and Nops to be free. Constants are free because we hoist them to an optimal place.
273 // Identities and Nops are free because we remove them.
274 bool isFree() const;
275
276 // Walk the ancestors of this value (i.e. the graph of things it transitively uses). This
277 // either walks phis or not, depending on whether PhiChildren is null. Your callback gets
278 // called with the signature:
279 //
280 // (Value*) -> WalkStatus
281 enum WalkStatus {
282 Continue,
283 IgnoreChildren,
284 Stop
285 };
286 template<typename Functor>
287 void walk(const Functor& functor, PhiChildren* = nullptr);
288
289 // B3 purposefully only represents signed 32-bit offsets because that's what x86 can encode, and
290 // ARM64 cannot encode anything bigger. The IsLegalOffset type trait is then used on B3 Value
291 // methods to prevent implicit conversions by C++ from invalid offset types: these cause compilation
292 // to fail, instead of causing implementation-defined behavior (which often turns to exploit).
293 // OffsetType isn't sufficient to determine offset validity! Each Value opcode further has an
294 // isLegalOffset runtime method used to determine value legality at runtime. This is exposed to users
295 // of B3 to force them to reason about the target's offset.
296 typedef int32_t OffsetType;
297 template<typename Int>
298 struct IsLegalOffset : std::conjunction<
299 typename std::enable_if<std::is_integral<Int>::value>::type,
300 typename std::enable_if<std::is_signed<Int>::value>::type,
301 typename std::enable_if<sizeof(Int) <= sizeof(OffsetType)>::type
302 > { };
303
304
305protected:
306 virtual Value* cloneImpl() const;
307
308 virtual void dumpChildren(CommaPrinter&, PrintStream&) const;
309 virtual void dumpMeta(CommaPrinter&, PrintStream&) const;
310
311private:
312 friend class Procedure;
313 friend class SparseCollection<Value>;
314
315 // Checks that this kind is valid for use with B3::Value.
316 ALWAYS_INLINE static void checkKind(Kind kind, unsigned numArgs)
317 {
318 switch (kind.opcode()) {
319 case FramePointer:
320 case Nop:
321 case Phi:
322 case Jump:
323 case Oops:
324 case EntrySwitch:
325 if (UNLIKELY(numArgs))
326 badKind(kind, numArgs);
327 break;
328 case Return:
329 if (UNLIKELY(numArgs > 1))
330 badKind(kind, numArgs);
331 break;
332 case Identity:
333 case Opaque:
334 case Neg:
335 case Clz:
336 case Abs:
337 case Ceil:
338 case Floor:
339 case Sqrt:
340 case SExt8:
341 case SExt16:
342 case Trunc:
343 case SExt32:
344 case ZExt32:
345 case FloatToDouble:
346 case IToD:
347 case DoubleToFloat:
348 case IToF:
349 case BitwiseCast:
350 case Branch:
351 case Depend:
352 if (UNLIKELY(numArgs != 1))
353 badKind(kind, numArgs);
354 break;
355 case Add:
356 case Sub:
357 case Mul:
358 case Div:
359 case UDiv:
360 case Mod:
361 case UMod:
362 case BitAnd:
363 case BitOr:
364 case BitXor:
365 case Shl:
366 case SShr:
367 case ZShr:
368 case RotR:
369 case RotL:
370 case Equal:
371 case NotEqual:
372 case LessThan:
373 case GreaterThan:
374 case LessEqual:
375 case GreaterEqual:
376 case Above:
377 case Below:
378 case AboveEqual:
379 case BelowEqual:
380 case EqualOrUnordered:
381 if (UNLIKELY(numArgs != 2))
382 badKind(kind, numArgs);
383 break;
384 case Select:
385 if (UNLIKELY(numArgs != 3))
386 badKind(kind, numArgs);
387 break;
388 default:
389 badKind(kind, numArgs);
390 break;
391 }
392 }
393
394protected:
395 enum CheckedOpcodeTag { CheckedOpcode };
396
397 Value(const Value&) = default;
398 Value& operator=(const Value&) = default;
399
400 // Instantiate values via Procedure.
401 // This form requires specifying the type explicitly:
402 template<typename... Arguments>
403 explicit Value(CheckedOpcodeTag, Kind kind, Type type, Origin origin, Value* firstChild, Arguments... arguments)
404 : m_kind(kind)
405 , m_type(type)
406 , m_origin(origin)
407 , m_children{ firstChild, arguments... }
408 {
409 }
410 // This form is for specifying the type explicitly when the opcode has no children:
411 explicit Value(CheckedOpcodeTag, Kind kind, Type type, Origin origin)
412 : m_kind(kind)
413 , m_type(type)
414 , m_origin(origin)
415 {
416 }
417 // This form is for those opcodes that can infer their type from the opcode and first child:
418 template<typename... Arguments>
419 explicit Value(CheckedOpcodeTag, Kind kind, Origin origin, Value* firstChild)
420 : m_kind(kind)
421 , m_type(typeFor(kind, firstChild))
422 , m_origin(origin)
423 , m_children{ firstChild }
424 {
425 }
426 // This form is for those opcodes that can infer their type from the opcode and first and second child:
427 template<typename... Arguments>
428 explicit Value(CheckedOpcodeTag, Kind kind, Origin origin, Value* firstChild, Value* secondChild, Arguments... arguments)
429 : m_kind(kind)
430 , m_type(typeFor(kind, firstChild, secondChild))
431 , m_origin(origin)
432 , m_children{ firstChild, secondChild, arguments... }
433 {
434 }
435 // This form is for those opcodes that can infer their type from the opcode alone, and that don't
436 // take any arguments:
437 explicit Value(CheckedOpcodeTag, Kind kind, Origin origin)
438 : m_kind(kind)
439 , m_type(typeFor(kind, nullptr))
440 , m_origin(origin)
441 {
442 }
443 // Use this form for varargs.
444 explicit Value(CheckedOpcodeTag, Kind kind, Type type, Origin origin, const AdjacencyList& children)
445 : m_kind(kind)
446 , m_type(type)
447 , m_origin(origin)
448 , m_children(children)
449 {
450 }
451 explicit Value(CheckedOpcodeTag, Kind kind, Type type, Origin origin, AdjacencyList&& children)
452 : m_kind(kind)
453 , m_type(type)
454 , m_origin(origin)
455 , m_children(WTFMove(children))
456 {
457 }
458
459 // This is the constructor you end up actually calling, if you're instantiating Value
460 // directly.
461 template<typename... Arguments>
462 explicit Value(Kind kind, Type type, Origin origin)
463 : Value(CheckedOpcode, kind, type, origin)
464 {
465 checkKind(kind, 0);
466 }
467 template<typename... Arguments>
468 explicit Value(Kind kind, Type type, Origin origin, Value* firstChild, Arguments&&... arguments)
469 : Value(CheckedOpcode, kind, type, origin, firstChild, std::forward<Arguments>(arguments)...)
470 {
471 checkKind(kind, 1 + sizeof...(arguments));
472 }
473 template<typename... Arguments>
474 explicit Value(Kind kind, Type type, Origin origin, const AdjacencyList& children)
475 : Value(CheckedOpcode, kind, type, origin, children)
476 {
477 checkKind(kind, children.size());
478 }
479 template<typename... Arguments>
480 explicit Value(Kind kind, Type type, Origin origin, AdjacencyList&& children)
481 : Value(CheckedOpcode, kind, type, origin, WTFMove(children))
482 {
483 checkKind(kind, m_children.size());
484 }
485 template<typename... Arguments>
486 explicit Value(Kind kind, Origin origin, Arguments&&... arguments)
487 : Value(CheckedOpcode, kind, origin, std::forward<Arguments>(arguments)...)
488 {
489 checkKind(kind, sizeof...(arguments));
490 }
491
492private:
493 friend class CheckValue; // CheckValue::convertToAdd() modifies m_kind.
494
495 static Type typeFor(Kind, Value* firstChild, Value* secondChild = nullptr);
496
497 // This group of fields is arranged to fit in 64 bits.
498protected:
499 unsigned m_index { UINT_MAX };
500private:
501 Kind m_kind;
502 Type m_type;
503
504 Origin m_origin;
505 AdjacencyList m_children;
506
507 NO_RETURN_DUE_TO_CRASH static void badKind(Kind, unsigned);
508
509public:
510 BasicBlock* owner { nullptr }; // computed by Procedure::resetValueOwners().
511};
512
513class DeepValueDump {
514public:
515 DeepValueDump(const Procedure* proc, const Value* value)
516 : m_proc(proc)
517 , m_value(value)
518 {
519 }
520
521 void dump(PrintStream& out) const
522 {
523 if (m_value)
524 m_value->deepDump(m_proc, out);
525 else
526 out.print("<null>");
527 }
528
529private:
530 const Procedure* m_proc;
531 const Value* m_value;
532};
533
534inline DeepValueDump deepDump(const Procedure& proc, const Value* value)
535{
536 return DeepValueDump(&proc, value);
537}
538inline DeepValueDump deepDump(const Value* value)
539{
540 return DeepValueDump(nullptr, value);
541}
542
543} } // namespace JSC::B3
544
545#endif // ENABLE(B3_JIT)
546