f0b06e0b1d8472393aff3cf4bc152ff3bb6f8429
[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::modConstant(Procedure&, const Value*) const
302 {
303     return nullptr;
304 }
305
306 Value* Value::bitAndConstant(Procedure&, const Value*) const
307 {
308     return nullptr;
309 }
310
311 Value* Value::bitOrConstant(Procedure&, const Value*) const
312 {
313     return nullptr;
314 }
315
316 Value* Value::bitXorConstant(Procedure&, const Value*) const
317 {
318     return nullptr;
319 }
320
321 Value* Value::shlConstant(Procedure&, const Value*) const
322 {
323     return nullptr;
324 }
325
326 Value* Value::sShrConstant(Procedure&, const Value*) const
327 {
328     return nullptr;
329 }
330
331 Value* Value::zShrConstant(Procedure&, const Value*) const
332 {
333     return nullptr;
334 }
335
336 Value* Value::bitwiseCastConstant(Procedure&) const
337 {
338     return nullptr;
339 }
340
341 Value* Value::iToDConstant(Procedure&) const
342 {
343     return nullptr;
344 }
345
346 Value* Value::iToFConstant(Procedure&) const
347 {
348     return nullptr;
349 }
350
351 Value* Value::doubleToFloatConstant(Procedure&) const
352 {
353     return nullptr;
354 }
355
356 Value* Value::floatToDoubleConstant(Procedure&) const
357 {
358     return nullptr;
359 }
360
361 Value* Value::absConstant(Procedure&) const
362 {
363     return nullptr;
364 }
365
366 Value* Value::ceilConstant(Procedure&) const
367 {
368     return nullptr;
369 }
370
371 Value* Value::floorConstant(Procedure&) const
372 {
373     return nullptr;
374 }
375
376 Value* Value::sqrtConstant(Procedure&) const
377 {
378     return nullptr;
379 }
380
381 TriState Value::equalConstant(const Value*) const
382 {
383     return MixedTriState;
384 }
385
386 TriState Value::notEqualConstant(const Value*) const
387 {
388     return MixedTriState;
389 }
390
391 TriState Value::lessThanConstant(const Value*) const
392 {
393     return MixedTriState;
394 }
395
396 TriState Value::greaterThanConstant(const Value*) const
397 {
398     return MixedTriState;
399 }
400
401 TriState Value::lessEqualConstant(const Value*) const
402 {
403     return MixedTriState;
404 }
405
406 TriState Value::greaterEqualConstant(const Value*) const
407 {
408     return MixedTriState;
409 }
410
411 TriState Value::aboveConstant(const Value*) const
412 {
413     return MixedTriState;
414 }
415
416 TriState Value::belowConstant(const Value*) const
417 {
418     return MixedTriState;
419 }
420
421 TriState Value::aboveEqualConstant(const Value*) const
422 {
423     return MixedTriState;
424 }
425
426 TriState Value::belowEqualConstant(const Value*) const
427 {
428     return MixedTriState;
429 }
430
431 TriState Value::equalOrUnorderedConstant(const Value*) const
432 {
433     return MixedTriState;
434 }
435
436 Value* Value::invertedCompare(Procedure& proc) const
437 {
438     if (!numChildren())
439         return nullptr;
440     if (Optional<Opcode> invertedOpcode = B3::invertedCompare(opcode(), child(0)->type())) {
441         ASSERT(!kind().hasExtraBits());
442         return proc.add<Value>(*invertedOpcode, type(), origin(), children());
443     }
444     return nullptr;
445 }
446
447 bool Value::isRounded() const
448 {
449     ASSERT(isFloat(type()));
450     switch (opcode()) {
451     case Floor:
452     case Ceil:
453     case IToD:
454     case IToF:
455         return true;
456
457     case ConstDouble: {
458         double value = asDouble();
459         return std::isfinite(value) && value == ceil(value);
460     }
461
462     case ConstFloat: {
463         float value = asFloat();
464         return std::isfinite(value) && value == ceilf(value);
465     }
466
467     default:
468         return false;
469     }
470 }
471
472 bool Value::returnsBool() const
473 {
474     if (type() != Int32)
475         return false;
476     switch (opcode()) {
477     case Const32:
478         return asInt32() == 0 || asInt32() == 1;
479     case BitAnd:
480         return child(1)->isInt32(1)
481             || (child(0)->returnsBool() && child(1)->hasInt() && child(1)->asInt() & 1);
482     case Equal:
483     case NotEqual:
484     case LessThan:
485     case GreaterThan:
486     case LessEqual:
487     case GreaterEqual:
488     case Above:
489     case Below:
490     case AboveEqual:
491     case BelowEqual:
492     case EqualOrUnordered:
493         return true;
494     case Phi:
495         // FIXME: We should have a story here.
496         // https://bugs.webkit.org/show_bug.cgi?id=150725
497         return false;
498     default:
499         return false;
500     }
501 }
502
503 TriState Value::asTriState() const
504 {
505     switch (opcode()) {
506     case Const32:
507         return triState(!!asInt32());
508     case Const64:
509         return triState(!!asInt64());
510     case ConstDouble:
511         // Use "!= 0" to really emphasize what this mean with respect to NaN and such.
512         return triState(asDouble() != 0);
513     case ConstFloat:
514         return triState(asFloat() != 0.);
515     default:
516         return MixedTriState;
517     }
518 }
519
520 Effects Value::effects() const
521 {
522     Effects result;
523     switch (opcode()) {
524     case Nop:
525     case Identity:
526     case Const32:
527     case Const64:
528     case ConstDouble:
529     case ConstFloat:
530     case SlotBase:
531     case ArgumentReg:
532     case FramePointer:
533     case Add:
534     case Sub:
535     case Mul:
536     case Neg:
537     case BitAnd:
538     case BitOr:
539     case BitXor:
540     case Shl:
541     case SShr:
542     case ZShr:
543     case Clz:
544     case Abs:
545     case Ceil:
546     case Floor:
547     case Sqrt:
548     case BitwiseCast:
549     case SExt8:
550     case SExt16:
551     case SExt32:
552     case ZExt32:
553     case Trunc:
554     case IToD:
555     case IToF:
556     case FloatToDouble:
557     case DoubleToFloat:
558     case Equal:
559     case NotEqual:
560     case LessThan:
561     case GreaterThan:
562     case LessEqual:
563     case GreaterEqual:
564     case Above:
565     case Below:
566     case AboveEqual:
567     case BelowEqual:
568     case EqualOrUnordered:
569     case Select:
570         break;
571     case Div:
572     case Mod:
573         result.controlDependent = true;
574         break;
575     case Load8Z:
576     case Load8S:
577     case Load16Z:
578     case Load16S:
579     case Load:
580         result.reads = as<MemoryValue>()->range();
581         result.controlDependent = true;
582         break;
583     case Store8:
584     case Store16:
585     case Store:
586         result.writes = as<MemoryValue>()->range();
587         result.controlDependent = true;
588         break;
589     case Fence: {
590         const FenceValue* fence = as<FenceValue>();
591         result.reads = fence->read;
592         result.writes = fence->write;
593         
594         // Prevent killing of fences that claim not to write anything. It's a bit weird that we use
595         // local state as the way to do this, but it happens to work: we must assume that we cannot
596         // kill writesLocalState unless we understands exactly what the instruction is doing (like
597         // the way that fixSSA understands Set/Get and the way that reduceStrength and others
598         // understand Upsilon). This would only become a problem if we had some analysis that was
599         // looking to use the writesLocalState bit to invalidate a CSE over local state operations.
600         // Then a Fence would look block, say, the elimination of a redundant Get. But it like
601         // that's not at all how our optimizations for Set/Get/Upsilon/Phi work - they grok their
602         // operations deeply enough that they have no need to check this bit - so this cheat is
603         // fine.
604         result.writesLocalState = true;
605         break;
606     }
607     case CCall:
608         result = as<CCallValue>()->effects;
609         break;
610     case Patchpoint:
611         result = as<PatchpointValue>()->effects;
612         break;
613     case CheckAdd:
614     case CheckSub:
615     case CheckMul:
616     case Check:
617         result.exitsSideways = true;
618         // The program could read anything after exiting, and it's on us to declare this.
619         result.reads = HeapRange::top();
620         break;
621     case Upsilon:
622     case Set:
623         result.writesLocalState = true;
624         break;
625     case Phi:
626     case Get:
627         result.readsLocalState = true;
628         break;
629     case Jump:
630     case Branch:
631     case Switch:
632     case Return:
633     case Oops:
634     case EntrySwitch:
635         result.terminal = true;
636         break;
637     }
638     result.exitsSideways |= traps();
639     return result;
640 }
641
642 ValueKey Value::key() const
643 {
644     switch (opcode()) {
645     case FramePointer:
646         return ValueKey(kind(), type());
647     case Identity:
648     case Abs:
649     case Ceil:
650     case Floor:
651     case Sqrt:
652     case SExt8:
653     case SExt16:
654     case SExt32:
655     case ZExt32:
656     case Clz:
657     case Trunc:
658     case IToD:
659     case IToF:
660     case FloatToDouble:
661     case DoubleToFloat:
662     case Check:
663     case BitwiseCast:
664     case Neg:
665         return ValueKey(kind(), type(), child(0));
666     case Add:
667     case Sub:
668     case Mul:
669     case Div:
670     case Mod:
671     case BitAnd:
672     case BitOr:
673     case BitXor:
674     case Shl:
675     case SShr:
676     case ZShr:
677     case Equal:
678     case NotEqual:
679     case LessThan:
680     case GreaterThan:
681     case Above:
682     case Below:
683     case AboveEqual:
684     case BelowEqual:
685     case EqualOrUnordered:
686     case CheckAdd:
687     case CheckSub:
688     case CheckMul:
689         return ValueKey(kind(), type(), child(0), child(1));
690     case Select:
691         return ValueKey(kind(), type(), child(0), child(1), child(2));
692     case Const32:
693         return ValueKey(Const32, type(), static_cast<int64_t>(asInt32()));
694     case Const64:
695         return ValueKey(Const64, type(), asInt64());
696     case ConstDouble:
697         return ValueKey(ConstDouble, type(), asDouble());
698     case ConstFloat:
699         return ValueKey(ConstFloat, type(), asFloat());
700     case ArgumentReg:
701         return ValueKey(
702             ArgumentReg, type(),
703             static_cast<int64_t>(as<ArgumentRegValue>()->argumentReg().index()));
704     case SlotBase:
705         return ValueKey(
706             SlotBase, type(),
707             static_cast<int64_t>(as<SlotBaseValue>()->slot()->index()));
708     default:
709         return ValueKey();
710     }
711 }
712
713 void Value::performSubstitution()
714 {
715     for (Value*& child : children()) {
716         while (child->opcode() == Identity)
717             child = child->child(0);
718     }
719 }
720
721 bool Value::isFree() const
722 {
723     switch (opcode()) {
724     case Const32:
725     case Const64:
726     case ConstDouble:
727     case ConstFloat:
728     case Identity:
729     case Nop:
730         return true;
731     default:
732         return false;
733     }
734 }
735
736 void Value::dumpMeta(CommaPrinter&, PrintStream&) const
737 {
738 }
739
740 Type Value::typeFor(Kind kind, Value* firstChild, Value* secondChild)
741 {
742     switch (kind.opcode()) {
743     case Identity:
744     case Add:
745     case Sub:
746     case Mul:
747     case Div:
748     case Mod:
749     case Neg:
750     case BitAnd:
751     case BitOr:
752     case BitXor:
753     case Shl:
754     case SShr:
755     case ZShr:
756     case Clz:
757     case Abs:
758     case Ceil:
759     case Floor:
760     case Sqrt:
761     case CheckAdd:
762     case CheckSub:
763     case CheckMul:
764         return firstChild->type();
765     case FramePointer:
766         return pointerType();
767     case SExt8:
768     case SExt16:
769     case Trunc:
770     case Equal:
771     case NotEqual:
772     case LessThan:
773     case GreaterThan:
774     case LessEqual:
775     case GreaterEqual:
776     case Above:
777     case Below:
778     case AboveEqual:
779     case BelowEqual:
780     case EqualOrUnordered:
781         return Int32;
782     case SExt32:
783     case ZExt32:
784         return Int64;
785     case FloatToDouble:
786     case IToD:
787         return Double;
788     case DoubleToFloat:
789     case IToF:
790         return Float;
791     case BitwiseCast:
792         switch (firstChild->type()) {
793         case Int64:
794             return Double;
795         case Double:
796             return Int64;
797         case Int32:
798             return Float;
799         case Float:
800             return Int32;
801         case Void:
802             ASSERT_NOT_REACHED();
803         }
804         return Void;
805     case Nop:
806     case Jump:
807     case Branch:
808     case Return:
809     case Oops:
810     case EntrySwitch:
811         return Void;
812     case Select:
813         ASSERT(secondChild);
814         return secondChild->type();
815     default:
816         RELEASE_ASSERT_NOT_REACHED();
817     }
818 }
819
820 void Value::badKind(Kind kind, unsigned numArgs)
821 {
822     dataLog("Bad kind ", kind, " with ", numArgs, " args.\n");
823     RELEASE_ASSERT_NOT_REACHED();
824 }
825
826 } } // namespace JSC::B3
827
828 #endif // ENABLE(B3_JIT)