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