B3 trapping memory accesses should be documented
[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     if (traps()) {
639         result.exitsSideways = true;
640         result.reads = HeapRange::top();
641     }
642     return result;
643 }
644
645 ValueKey Value::key() const
646 {
647     switch (opcode()) {
648     case FramePointer:
649         return ValueKey(kind(), type());
650     case Identity:
651     case Abs:
652     case Ceil:
653     case Floor:
654     case Sqrt:
655     case SExt8:
656     case SExt16:
657     case SExt32:
658     case ZExt32:
659     case Clz:
660     case Trunc:
661     case IToD:
662     case IToF:
663     case FloatToDouble:
664     case DoubleToFloat:
665     case Check:
666     case BitwiseCast:
667     case Neg:
668         return ValueKey(kind(), type(), child(0));
669     case Add:
670     case Sub:
671     case Mul:
672     case Div:
673     case Mod:
674     case BitAnd:
675     case BitOr:
676     case BitXor:
677     case Shl:
678     case SShr:
679     case ZShr:
680     case Equal:
681     case NotEqual:
682     case LessThan:
683     case GreaterThan:
684     case Above:
685     case Below:
686     case AboveEqual:
687     case BelowEqual:
688     case EqualOrUnordered:
689     case CheckAdd:
690     case CheckSub:
691     case CheckMul:
692         return ValueKey(kind(), type(), child(0), child(1));
693     case Select:
694         return ValueKey(kind(), type(), child(0), child(1), child(2));
695     case Const32:
696         return ValueKey(Const32, type(), static_cast<int64_t>(asInt32()));
697     case Const64:
698         return ValueKey(Const64, type(), asInt64());
699     case ConstDouble:
700         return ValueKey(ConstDouble, type(), asDouble());
701     case ConstFloat:
702         return ValueKey(ConstFloat, type(), asFloat());
703     case ArgumentReg:
704         return ValueKey(
705             ArgumentReg, type(),
706             static_cast<int64_t>(as<ArgumentRegValue>()->argumentReg().index()));
707     case SlotBase:
708         return ValueKey(
709             SlotBase, type(),
710             static_cast<int64_t>(as<SlotBaseValue>()->slot()->index()));
711     default:
712         return ValueKey();
713     }
714 }
715
716 void Value::performSubstitution()
717 {
718     for (Value*& child : children()) {
719         while (child->opcode() == Identity)
720             child = child->child(0);
721     }
722 }
723
724 bool Value::isFree() const
725 {
726     switch (opcode()) {
727     case Const32:
728     case Const64:
729     case ConstDouble:
730     case ConstFloat:
731     case Identity:
732     case Nop:
733         return true;
734     default:
735         return false;
736     }
737 }
738
739 void Value::dumpMeta(CommaPrinter&, PrintStream&) const
740 {
741 }
742
743 Type Value::typeFor(Kind kind, Value* firstChild, Value* secondChild)
744 {
745     switch (kind.opcode()) {
746     case Identity:
747     case Add:
748     case Sub:
749     case Mul:
750     case Div:
751     case Mod:
752     case Neg:
753     case BitAnd:
754     case BitOr:
755     case BitXor:
756     case Shl:
757     case SShr:
758     case ZShr:
759     case Clz:
760     case Abs:
761     case Ceil:
762     case Floor:
763     case Sqrt:
764     case CheckAdd:
765     case CheckSub:
766     case CheckMul:
767         return firstChild->type();
768     case FramePointer:
769         return pointerType();
770     case SExt8:
771     case SExt16:
772     case Trunc:
773     case Equal:
774     case NotEqual:
775     case LessThan:
776     case GreaterThan:
777     case LessEqual:
778     case GreaterEqual:
779     case Above:
780     case Below:
781     case AboveEqual:
782     case BelowEqual:
783     case EqualOrUnordered:
784         return Int32;
785     case SExt32:
786     case ZExt32:
787         return Int64;
788     case FloatToDouble:
789     case IToD:
790         return Double;
791     case DoubleToFloat:
792     case IToF:
793         return Float;
794     case BitwiseCast:
795         switch (firstChild->type()) {
796         case Int64:
797             return Double;
798         case Double:
799             return Int64;
800         case Int32:
801             return Float;
802         case Float:
803             return Int32;
804         case Void:
805             ASSERT_NOT_REACHED();
806         }
807         return Void;
808     case Nop:
809     case Jump:
810     case Branch:
811     case Return:
812     case Oops:
813     case EntrySwitch:
814         return Void;
815     case Select:
816         ASSERT(secondChild);
817         return secondChild->type();
818     default:
819         RELEASE_ASSERT_NOT_REACHED();
820     }
821 }
822
823 void Value::badKind(Kind kind, unsigned numArgs)
824 {
825     dataLog("Bad kind ", kind, " with ", numArgs, " args.\n");
826     RELEASE_ASSERT_NOT_REACHED();
827 }
828
829 } } // namespace JSC::B3
830
831 #endif // ENABLE(B3_JIT)