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#include "config.h"
27#include "B3Value.h"
28
29#if ENABLE(B3_JIT)
30
31#include "B3ArgumentRegValue.h"
32#include "B3AtomicValue.h"
33#include "B3BasicBlockInlines.h"
34#include "B3BottomProvider.h"
35#include "B3CCallValue.h"
36#include "B3FenceValue.h"
37#include "B3MemoryValue.h"
38#include "B3OriginDump.h"
39#include "B3ProcedureInlines.h"
40#include "B3SlotBaseValue.h"
41#include "B3StackSlot.h"
42#include "B3UpsilonValue.h"
43#include "B3ValueInlines.h"
44#include "B3ValueKeyInlines.h"
45#include "B3VariableValue.h"
46#include "B3WasmBoundsCheckValue.h"
47#include <wtf/CommaPrinter.h>
48#include <wtf/ListDump.h>
49#include <wtf/StringPrintStream.h>
50#include <wtf/Vector.h>
51
52namespace JSC { namespace B3 {
53
54const char* const Value::dumpPrefix = "@";
55void DeepValueDump::dump(PrintStream& out) const
56{
57 if (m_value)
58 m_value->deepDump(m_proc, out);
59 else
60 out.print("<null>");
61}
62
63Value::~Value()
64{
65 if (m_numChildren == VarArgs)
66 bitwise_cast<Vector<Value*, 3> *>(childrenAlloc())->Vector<Value*, 3>::~Vector();
67}
68
69void Value::replaceWithIdentity(Value* value)
70{
71 // This is a bit crazy. It does an in-place replacement of whatever Value subclass this is with
72 // a plain Identity Value. We first collect all of the information we need, then we destruct the
73 // previous value in place, and then we construct the Identity Value in place.
74
75 RELEASE_ASSERT(m_type == value->m_type);
76 ASSERT(value != this);
77
78 if (m_type == Void)
79 replaceWithNopIgnoringType();
80 else
81 replaceWith(Identity, m_type, this->owner, value);
82}
83
84void Value::replaceWithBottom(InsertionSet& insertionSet, size_t index)
85{
86 replaceWithBottom(BottomProvider(insertionSet, index));
87}
88
89void Value::replaceWithNop()
90{
91 RELEASE_ASSERT(m_type == Void);
92 replaceWithNopIgnoringType();
93}
94
95void Value::replaceWithNopIgnoringType()
96{
97 replaceWith(Nop, Void, this->owner);
98}
99
100void Value::replaceWithPhi()
101{
102 if (m_type == Void) {
103 replaceWithNop();
104 return;
105 }
106
107 replaceWith(Phi, m_type, this->owner);
108}
109
110void Value::replaceWithJump(BasicBlock* owner, FrequentedBlock target)
111{
112 RELEASE_ASSERT(owner->last() == this);
113 replaceWith(Jump, Void, this->owner);
114 owner->setSuccessors(target);
115}
116
117void Value::replaceWithOops(BasicBlock* owner)
118{
119 RELEASE_ASSERT(owner->last() == this);
120 replaceWith(Oops, Void, this->owner);
121 owner->clearSuccessors();
122}
123
124void Value::replaceWithJump(FrequentedBlock target)
125{
126 replaceWithJump(owner, target);
127}
128
129void Value::replaceWithOops()
130{
131 replaceWithOops(owner);
132}
133
134void Value::replaceWith(Kind kind, Type type, BasicBlock* owner)
135{
136 unsigned index = m_index;
137
138 this->~Value();
139
140 new (this) Value(kind, type, m_origin);
141
142 this->m_index = index;
143 this->owner = owner;
144}
145
146void Value::replaceWith(Kind kind, Type type, BasicBlock* owner, Value* value)
147{
148 unsigned index = m_index;
149
150 this->~Value();
151
152 new (this) Value(kind, type, m_origin, value);
153
154 this->m_index = index;
155 this->owner = owner;
156}
157
158void Value::dump(PrintStream& out) const
159{
160 bool isConstant = false;
161
162 switch (opcode()) {
163 case Const32:
164 out.print("$", asInt32(), "(");
165 isConstant = true;
166 break;
167 case Const64:
168 out.print("$", asInt64(), "(");
169 isConstant = true;
170 break;
171 case ConstFloat:
172 out.print("$", asFloat(), "(");
173 isConstant = true;
174 break;
175 case ConstDouble:
176 out.print("$", asDouble(), "(");
177 isConstant = true;
178 break;
179 default:
180 break;
181 }
182
183 out.print(dumpPrefix, m_index);
184
185 if (isConstant)
186 out.print(")");
187}
188
189void Value::dumpChildren(CommaPrinter& comma, PrintStream& out) const
190{
191 for (Value* child : children())
192 out.print(comma, pointerDump(child));
193}
194
195void Value::deepDump(const Procedure* proc, PrintStream& out) const
196{
197 out.print(m_type, " ", dumpPrefix, m_index, " = ", m_kind);
198
199 out.print("(");
200 CommaPrinter comma;
201 dumpChildren(comma, out);
202
203 dumpMeta(comma, out);
204
205 {
206 CString string = toCString(effects());
207 if (string.length())
208 out.print(comma, string);
209 }
210
211 if (m_origin)
212 out.print(comma, OriginDump(proc, m_origin));
213
214 out.print(")");
215}
216
217void Value::dumpSuccessors(const BasicBlock* block, PrintStream& out) const
218{
219 // Note that this must not crash if we have the wrong number of successors, since someone
220 // debugging a number-of-successors bug will probably want to dump IR!
221
222 if (opcode() == Branch && block->numSuccessors() == 2) {
223 out.print("Then:", block->taken(), ", Else:", block->notTaken());
224 return;
225 }
226
227 out.print(listDump(block->successors()));
228}
229
230Value* Value::negConstant(Procedure&) const
231{
232 return nullptr;
233}
234
235Value* Value::addConstant(Procedure&, int32_t) const
236{
237 return nullptr;
238}
239
240Value* Value::addConstant(Procedure&, const Value*) const
241{
242 return nullptr;
243}
244
245Value* Value::subConstant(Procedure&, const Value*) const
246{
247 return nullptr;
248}
249
250Value* Value::mulConstant(Procedure&, const Value*) const
251{
252 return nullptr;
253}
254
255Value* Value::checkAddConstant(Procedure&, const Value*) const
256{
257 return nullptr;
258}
259
260Value* Value::checkSubConstant(Procedure&, const Value*) const
261{
262 return nullptr;
263}
264
265Value* Value::checkMulConstant(Procedure&, const Value*) const
266{
267 return nullptr;
268}
269
270Value* Value::checkNegConstant(Procedure&) const
271{
272 return nullptr;
273}
274
275Value* Value::divConstant(Procedure&, const Value*) const
276{
277 return nullptr;
278}
279
280Value* Value::uDivConstant(Procedure&, const Value*) const
281{
282 return nullptr;
283}
284
285Value* Value::modConstant(Procedure&, const Value*) const
286{
287 return nullptr;
288}
289
290Value* Value::uModConstant(Procedure&, const Value*) const
291{
292 return nullptr;
293}
294
295Value* Value::bitAndConstant(Procedure&, const Value*) const
296{
297 return nullptr;
298}
299
300Value* Value::bitOrConstant(Procedure&, const Value*) const
301{
302 return nullptr;
303}
304
305Value* Value::bitXorConstant(Procedure&, const Value*) const
306{
307 return nullptr;
308}
309
310Value* Value::shlConstant(Procedure&, const Value*) const
311{
312 return nullptr;
313}
314
315Value* Value::sShrConstant(Procedure&, const Value*) const
316{
317 return nullptr;
318}
319
320Value* Value::zShrConstant(Procedure&, const Value*) const
321{
322 return nullptr;
323}
324
325Value* Value::rotRConstant(Procedure&, const Value*) const
326{
327 return nullptr;
328}
329
330Value* Value::rotLConstant(Procedure&, const Value*) const
331{
332 return nullptr;
333}
334
335Value* Value::bitwiseCastConstant(Procedure&) const
336{
337 return nullptr;
338}
339
340Value* Value::iToDConstant(Procedure&) const
341{
342 return nullptr;
343}
344
345Value* Value::iToFConstant(Procedure&) const
346{
347 return nullptr;
348}
349
350Value* Value::doubleToFloatConstant(Procedure&) const
351{
352 return nullptr;
353}
354
355Value* Value::floatToDoubleConstant(Procedure&) const
356{
357 return nullptr;
358}
359
360Value* Value::absConstant(Procedure&) const
361{
362 return nullptr;
363}
364
365Value* Value::ceilConstant(Procedure&) const
366{
367 return nullptr;
368}
369
370Value* Value::floorConstant(Procedure&) const
371{
372 return nullptr;
373}
374
375Value* Value::sqrtConstant(Procedure&) const
376{
377 return nullptr;
378}
379
380TriState Value::equalConstant(const Value*) const
381{
382 return MixedTriState;
383}
384
385TriState Value::notEqualConstant(const Value*) const
386{
387 return MixedTriState;
388}
389
390TriState Value::lessThanConstant(const Value*) const
391{
392 return MixedTriState;
393}
394
395TriState Value::greaterThanConstant(const Value*) const
396{
397 return MixedTriState;
398}
399
400TriState Value::lessEqualConstant(const Value*) const
401{
402 return MixedTriState;
403}
404
405TriState Value::greaterEqualConstant(const Value*) const
406{
407 return MixedTriState;
408}
409
410TriState Value::aboveConstant(const Value*) const
411{
412 return MixedTriState;
413}
414
415TriState Value::belowConstant(const Value*) const
416{
417 return MixedTriState;
418}
419
420TriState Value::aboveEqualConstant(const Value*) const
421{
422 return MixedTriState;
423}
424
425TriState Value::belowEqualConstant(const Value*) const
426{
427 return MixedTriState;
428}
429
430TriState Value::equalOrUnorderedConstant(const Value*) const
431{
432 return MixedTriState;
433}
434
435Value* Value::invertedCompare(Procedure& proc) const
436{
437 if (numChildren() != 2)
438 return nullptr;
439 if (Optional<Opcode> invertedOpcode = B3::invertedCompare(opcode(), child(0)->type())) {
440 ASSERT(!kind().hasExtraBits());
441 return proc.add<Value>(*invertedOpcode, type(), origin(), child(0), child(1));
442 }
443 return nullptr;
444}
445
446bool Value::isRounded() const
447{
448 ASSERT(isFloat(type()));
449 switch (opcode()) {
450 case Floor:
451 case Ceil:
452 case IToD:
453 case IToF:
454 return true;
455
456 case ConstDouble: {
457 double value = asDouble();
458 return std::isfinite(value) && value == ceil(value);
459 }
460
461 case ConstFloat: {
462 float value = asFloat();
463 return std::isfinite(value) && value == ceilf(value);
464 }
465
466 default:
467 return false;
468 }
469}
470
471bool Value::returnsBool() const
472{
473 if (type() != Int32)
474 return false;
475
476 switch (opcode()) {
477 case Const32:
478 return asInt32() == 0 || asInt32() == 1;
479 case BitAnd:
480 return child(0)->returnsBool() || child(1)->returnsBool();
481 case BitOr:
482 case BitXor:
483 return child(0)->returnsBool() && child(1)->returnsBool();
484 case Select:
485 return child(1)->returnsBool() && child(2)->returnsBool();
486 case Identity:
487 return child(0)->returnsBool();
488 case Equal:
489 case NotEqual:
490 case LessThan:
491 case GreaterThan:
492 case LessEqual:
493 case GreaterEqual:
494 case Above:
495 case Below:
496 case AboveEqual:
497 case BelowEqual:
498 case EqualOrUnordered:
499 case AtomicWeakCAS:
500 return true;
501 case Phi:
502 // FIXME: We should have a story here.
503 // https://bugs.webkit.org/show_bug.cgi?id=150725
504 return false;
505 default:
506 return false;
507 }
508}
509
510TriState Value::asTriState() const
511{
512 switch (opcode()) {
513 case Const32:
514 return triState(!!asInt32());
515 case Const64:
516 return triState(!!asInt64());
517 case ConstDouble:
518 // Use "!= 0" to really emphasize what this mean with respect to NaN and such.
519 return triState(asDouble() != 0);
520 case ConstFloat:
521 return triState(asFloat() != 0.);
522 default:
523 return MixedTriState;
524 }
525}
526
527Effects Value::effects() const
528{
529 Effects result;
530 switch (opcode()) {
531 case Nop:
532 case Identity:
533 case Opaque:
534 case Const32:
535 case Const64:
536 case ConstDouble:
537 case ConstFloat:
538 case SlotBase:
539 case ArgumentReg:
540 case FramePointer:
541 case Add:
542 case Sub:
543 case Mul:
544 case Neg:
545 case BitAnd:
546 case BitOr:
547 case BitXor:
548 case Shl:
549 case SShr:
550 case ZShr:
551 case RotR:
552 case RotL:
553 case Clz:
554 case Abs:
555 case Ceil:
556 case Floor:
557 case Sqrt:
558 case BitwiseCast:
559 case SExt8:
560 case SExt16:
561 case SExt32:
562 case ZExt32:
563 case Trunc:
564 case IToD:
565 case IToF:
566 case FloatToDouble:
567 case DoubleToFloat:
568 case Equal:
569 case NotEqual:
570 case LessThan:
571 case GreaterThan:
572 case LessEqual:
573 case GreaterEqual:
574 case Above:
575 case Below:
576 case AboveEqual:
577 case BelowEqual:
578 case EqualOrUnordered:
579 case Select:
580 case Depend:
581 break;
582 case Div:
583 case UDiv:
584 case Mod:
585 case UMod:
586 result.controlDependent = true;
587 break;
588 case Load8Z:
589 case Load8S:
590 case Load16Z:
591 case Load16S:
592 case Load: {
593 const MemoryValue* memory = as<MemoryValue>();
594 result.reads = memory->range();
595 if (memory->hasFence()) {
596 result.writes = memory->fenceRange();
597 result.fence = true;
598 }
599 result.controlDependent = true;
600 break;
601 }
602 case Store8:
603 case Store16:
604 case Store: {
605 const MemoryValue* memory = as<MemoryValue>();
606 result.writes = memory->range();
607 if (memory->hasFence()) {
608 result.reads = memory->fenceRange();
609 result.fence = true;
610 }
611 result.controlDependent = true;
612 break;
613 }
614 case AtomicWeakCAS:
615 case AtomicStrongCAS:
616 case AtomicXchgAdd:
617 case AtomicXchgAnd:
618 case AtomicXchgOr:
619 case AtomicXchgSub:
620 case AtomicXchgXor:
621 case AtomicXchg: {
622 const AtomicValue* atomic = as<AtomicValue>();
623 result.reads = atomic->range() | atomic->fenceRange();
624 result.writes = atomic->range() | atomic->fenceRange();
625 if (atomic->hasFence())
626 result.fence = true;
627 result.controlDependent = true;
628 break;
629 }
630 case WasmAddress:
631 result.readsPinned = true;
632 break;
633 case Fence: {
634 const FenceValue* fence = as<FenceValue>();
635 result.reads = fence->read;
636 result.writes = fence->write;
637 result.fence = true;
638 break;
639 }
640 case CCall:
641 result = as<CCallValue>()->effects;
642 break;
643 case Patchpoint:
644 result = as<PatchpointValue>()->effects;
645 break;
646 case CheckAdd:
647 case CheckSub:
648 case CheckMul:
649 case Check:
650 result = Effects::forCheck();
651 break;
652 case WasmBoundsCheck:
653 switch (as<WasmBoundsCheckValue>()->boundsType()) {
654 case WasmBoundsCheckValue::Type::Pinned:
655 result.readsPinned = true;
656 break;
657 case WasmBoundsCheckValue::Type::Maximum:
658 break;
659 }
660 result.exitsSideways = true;
661 break;
662 case Upsilon:
663 case Set:
664 result.writesLocalState = true;
665 break;
666 case Phi:
667 case Get:
668 result.readsLocalState = true;
669 break;
670 case Jump:
671 case Branch:
672 case Switch:
673 case Return:
674 case Oops:
675 case EntrySwitch:
676 result.terminal = true;
677 break;
678 }
679 if (traps()) {
680 result.exitsSideways = true;
681 result.reads = HeapRange::top();
682 }
683 return result;
684}
685
686ValueKey Value::key() const
687{
688 // NOTE: Except for exotic things like CheckAdd and friends, we want every case here to have a
689 // corresponding case in ValueKey::materialize().
690 switch (opcode()) {
691 case FramePointer:
692 return ValueKey(kind(), type());
693 case Identity:
694 case Opaque:
695 case Abs:
696 case Ceil:
697 case Floor:
698 case Sqrt:
699 case SExt8:
700 case SExt16:
701 case SExt32:
702 case ZExt32:
703 case Clz:
704 case Trunc:
705 case IToD:
706 case IToF:
707 case FloatToDouble:
708 case DoubleToFloat:
709 case Check:
710 case BitwiseCast:
711 case Neg:
712 case Depend:
713 return ValueKey(kind(), type(), child(0));
714 case Add:
715 case Sub:
716 case Mul:
717 case Div:
718 case UDiv:
719 case Mod:
720 case UMod:
721 case BitAnd:
722 case BitOr:
723 case BitXor:
724 case Shl:
725 case SShr:
726 case ZShr:
727 case RotR:
728 case RotL:
729 case Equal:
730 case NotEqual:
731 case LessThan:
732 case GreaterThan:
733 case Above:
734 case Below:
735 case AboveEqual:
736 case BelowEqual:
737 case EqualOrUnordered:
738 case CheckAdd:
739 case CheckSub:
740 case CheckMul:
741 return ValueKey(kind(), type(), child(0), child(1));
742 case Select:
743 return ValueKey(kind(), type(), child(0), child(1), child(2));
744 case Const32:
745 return ValueKey(Const32, type(), static_cast<int64_t>(asInt32()));
746 case Const64:
747 return ValueKey(Const64, type(), asInt64());
748 case ConstDouble:
749 return ValueKey(ConstDouble, type(), asDouble());
750 case ConstFloat:
751 return ValueKey(ConstFloat, type(), asFloat());
752 case ArgumentReg:
753 return ValueKey(
754 ArgumentReg, type(),
755 static_cast<int64_t>(as<ArgumentRegValue>()->argumentReg().index()));
756 case SlotBase:
757 return ValueKey(
758 SlotBase, type(),
759 static_cast<int64_t>(as<SlotBaseValue>()->slot()->index()));
760 default:
761 return ValueKey();
762 }
763}
764
765Value* Value::foldIdentity() const
766{
767 Value* current = const_cast<Value*>(this);
768 while (current->opcode() == Identity)
769 current = current->child(0);
770 return current;
771}
772
773bool Value::performSubstitution()
774{
775 bool result = false;
776 for (Value*& child : children()) {
777 if (child->opcode() == Identity) {
778 result = true;
779 child = child->foldIdentity();
780 }
781 }
782 return result;
783}
784
785bool Value::isFree() const
786{
787 switch (opcode()) {
788 case Const32:
789 case Const64:
790 case ConstDouble:
791 case ConstFloat:
792 case Identity:
793 case Opaque:
794 case Nop:
795 return true;
796 default:
797 return false;
798 }
799}
800
801void Value::dumpMeta(CommaPrinter&, PrintStream&) const
802{
803}
804
805Type Value::typeFor(Kind kind, Value* firstChild, Value* secondChild)
806{
807 switch (kind.opcode()) {
808 case Identity:
809 case Opaque:
810 case Add:
811 case Sub:
812 case Mul:
813 case Div:
814 case UDiv:
815 case Mod:
816 case UMod:
817 case Neg:
818 case BitAnd:
819 case BitOr:
820 case BitXor:
821 case Shl:
822 case SShr:
823 case ZShr:
824 case RotR:
825 case RotL:
826 case Clz:
827 case Abs:
828 case Ceil:
829 case Floor:
830 case Sqrt:
831 case CheckAdd:
832 case CheckSub:
833 case CheckMul:
834 case Depend:
835 return firstChild->type();
836 case FramePointer:
837 return pointerType();
838 case SExt8:
839 case SExt16:
840 case Equal:
841 case NotEqual:
842 case LessThan:
843 case GreaterThan:
844 case LessEqual:
845 case GreaterEqual:
846 case Above:
847 case Below:
848 case AboveEqual:
849 case BelowEqual:
850 case EqualOrUnordered:
851 return Int32;
852 case Trunc:
853 return firstChild->type() == Int64 ? Int32 : Float;
854 case SExt32:
855 case ZExt32:
856 return Int64;
857 case FloatToDouble:
858 case IToD:
859 return Double;
860 case DoubleToFloat:
861 case IToF:
862 return Float;
863 case BitwiseCast:
864 switch (firstChild->type()) {
865 case Int64:
866 return Double;
867 case Double:
868 return Int64;
869 case Int32:
870 return Float;
871 case Float:
872 return Int32;
873 case Void:
874 ASSERT_NOT_REACHED();
875 }
876 return Void;
877 case Nop:
878 case Jump:
879 case Branch:
880 case Return:
881 case Oops:
882 case EntrySwitch:
883 case WasmBoundsCheck:
884 return Void;
885 case Select:
886 ASSERT(secondChild);
887 return secondChild->type();
888 default:
889 RELEASE_ASSERT_NOT_REACHED();
890 }
891}
892
893void Value::badKind(Kind kind, unsigned numArgs)
894{
895 dataLog("Bad kind ", kind, " with ", numArgs, " args.\n");
896 RELEASE_ASSERT_NOT_REACHED();
897}
898
899} } // namespace JSC::B3
900
901#endif // ENABLE(B3_JIT)
902