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)