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