dfg/DFGClobberize.h

   1  /*
   2  * Copyright (C) 2013, 2014 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 #ifndef DFGClobberize_h
  27 #define DFGClobberize_h
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGAbstractHeap.h"
  32 #include "DFGEdgeUsesStructure.h"
  33 #include "DFGGraph.h"
  34
  35 namespace JSC { namespace DFG {
  36
  37 template<typename ReadFunctor, typename WriteFunctor>
  38 void clobberizeForAllocation(ReadFunctor& read, WriteFunctor& write)
  39 {
  40     read(GCState);
  41     read(BarrierState);
  42     write(GCState);
  43     write(BarrierState);
  44 }
  45
  46 template<typename ReadFunctor, typename WriteFunctor>
  47 void clobberize(Graph& graph, Node* node, ReadFunctor& read, WriteFunctor& write)
  48 {
  49     // Some notes:
  50     //
  51     // - We cannot hoist, or sink, anything that has effects. This means that the
  52     //   easiest way of indicating that something cannot be hoisted is to claim
  53     //   that it side-effects some miscellaneous thing.
  54     //
  55     // - We cannot hoist forward-exiting nodes without some additional effort. I
  56     //   believe that what it comes down to is that forward-exiting generally have
  57     //   their NodeExitsForward cleared upon hoist, except for forward-exiting
  58     //   nodes that take bogus state as their input. Those are substantially
  59     //   harder. We disable it for now. In the future we could enable it by having
  60     //   versions of those nodes that backward-exit instead, but I'm not convinced
  61     //   of the soundness.
  62     //
  63     // - Some nodes lie, and claim that they do not read the JSCell_structureID, JSCell_typeInfoFlags, etc.
  64     //   These are nodes that use the structure in a way that does not depend on
  65     //   things that change under structure transitions.
  66     //
  67     // - It's implicitly understood that OSR exits read the world. This is why we
  68     //   generally don't move or eliminate stores. Every node can exit, so the
  69     //   read set does not reflect things that would be read if we exited.
  70     //   Instead, the read set reflects what the node will have to read if it
  71     //   *doesn't* exit.
  72     //
  73     // - Broadly, we don't say that we're reading something if that something is
  74     //   immutable.
  75     //
  76     // - We try to make this work even prior to type inference, just so that we
  77     //   can use it for IR dumps. No promises on whether the answers are sound
  78     //   prior to type inference - though they probably could be if we did some
  79     //   small hacking.
  80
  81     if (edgesUseStructure(graph, node))
  82         read(JSCell_structureID);
  83
  84     switch (node->op()) {
  85     case JSConstant:
  86     case DoubleConstant:
  87     case Int52Constant:
  88     case WeakJSConstant:
  89     case Identity:
  90     case Phantom:
  91     case HardPhantom:
  92     case BitAnd:
  93     case BitOr:
  94     case BitXor:
  95     case BitLShift:
  96     case BitRShift:
  97     case BitURShift:
  98     case ValueToInt32:
  99     case ArithAdd:
 100     case ArithSub:
 101     case ArithNegate:
 102     case ArithMul:
 103     case ArithIMul:
 104     case ArithDiv:
 105     case ArithMod:
 106     case ArithAbs:
 107     case ArithMin:
 108     case ArithMax:
 109     case ArithSqrt:
 110     case ArithFRound:
 111     case ArithSin:
 112     case ArithCos:
 113     case GetScope:
 114     case SkipScope:
 115     case CheckFunction:
 116     case StringCharCodeAt:
 117     case StringFromCharCode:
 118     case CompareEqConstant:
 119     case CompareStrictEq:
 120     case IsUndefined:
 121     case IsBoolean:
 122     case IsNumber:
 123     case IsString:
 124     case LogicalNot:
 125     case ExtractOSREntryLocal:
 126     case CheckInBounds:
 127     case ConstantStoragePointer:
 128     case UInt32ToNumber:
 129     case DoubleAsInt32:
 130     case Check:
 131     case DoubleRep:
 132     case ValueRep:
 133     case Int52Rep:
 134     case BooleanToNumber:
 135     case FiatInt52:
 136         return;
 137
 138     case MovHint:
 139     case ZombieHint:
 140     case Upsilon:
 141     case Phi:
 142     case Flush:
 143     case PhantomLocal:
 144     case SetArgument:
 145     case PhantomArguments:
 146     case Jump:
 147     case Branch:
 148     case Switch:
 149     case Throw:
 150     case ForceOSRExit:
 151     case Return:
 152     case Unreachable:
 153     case CheckTierUpInLoop:
 154     case CheckTierUpAtReturn:
 155     case CheckTierUpAndOSREnter:
 156     case LoopHint:
 157     case InvalidationPoint:
 158     case Breakpoint:
 159     case ProfileWillCall:
 160     case ProfileDidCall:
 161         write(SideState);
 162         return;
 163
 164     case VariableWatchpoint:
 165     case TypedArrayWatchpoint:
 166         read(Watchpoint_fire);
 167         write(SideState);
 168         return;
 169
 170     case NotifyWrite:
 171         write(Watchpoint_fire);
 172         write(SideState);
 173         return;
 174
 175     case CreateActivation:
 176     case CreateArguments:
 177         clobberizeForAllocation(read, write);
 178         write(SideState);
 179         write(Watchpoint_fire);
 180         return;
 181
 182     case FunctionReentryWatchpoint:
 183         read(Watchpoint_fire);
 184         return;
 185
 186     case ToThis:
 187     case CreateThis:
 188         read(MiscFields);
 189         clobberizeForAllocation(read, write);
 190         return;
 191
 192     case VarInjectionWatchpoint:
 193     case AllocationProfileWatchpoint:
 194     case IsObject:
 195     case IsFunction:
 196     case TypeOf:
 197         read(MiscFields);
 198         return;
 199
 200     case GetById:
 201     case GetByIdFlush:
 202     case PutById:
 203     case PutByIdFlush:
 204     case PutByIdDirect:
 205     case ArrayPush:
 206     case ArrayPop:
 207     case Call:
 208     case Construct:
 209     case ToPrimitive:
 210     case In:
 211     case GetMyArgumentsLengthSafe:
 212     case GetMyArgumentByValSafe:
 213     case ValueAdd:
 214         read(World);
 215         write(World);
 216         return;
 217
 218     case GetCallee:
 219         read(AbstractHeap(Variables, JSStack::Callee));
 220         return;
 221
 222     case GetLocal:
 223     case GetArgument:
 224         read(AbstractHeap(Variables, node->local()));
 225         return;
 226
 227     case SetLocal:
 228         write(AbstractHeap(Variables, node->local()));
 229         return;
 230
 231     case GetLocalUnlinked:
 232         read(AbstractHeap(Variables, node->unlinkedLocal()));
 233         return;
 234
 235     case GetByVal: {
 236         ArrayMode mode = node->arrayMode();
 237         switch (mode.type()) {
 238         case Array::SelectUsingPredictions:
 239         case Array::Unprofiled:
 240         case Array::Undecided:
 241             // Assume the worst since we don't have profiling yet.
 242             read(World);
 243             write(World);
 244             return;
 245
 246         case Array::ForceExit:
 247             write(SideState);
 248             return;
 249
 250         case Array::Generic:
 251             read(World);
 252             write(World);
 253             return;
 254
 255         case Array::String:
 256             if (mode.isOutOfBounds()) {
 257                 read(World);
 258                 write(World);
 259                 return;
 260             }
 261             // This appears to read nothing because it's only reading immutable data.
 262             return;
 263
 264         case Array::Arguments:
 265             read(Arguments_registers);
 266             read(Variables);
 267             return;
 268
 269         case Array::Int32:
 270             if (mode.isInBounds()) {
 271                 read(Butterfly_publicLength);
 272                 read(Butterfly_vectorLength);
 273                 read(IndexedInt32Properties);
 274                 return;
 275             }
 276             read(World);
 277             write(World);
 278             return;
 279
 280         case Array::Double:
 281             if (mode.isInBounds()) {
 282                 read(Butterfly_publicLength);
 283                 read(Butterfly_vectorLength);
 284                 read(IndexedDoubleProperties);
 285                 return;
 286             }
 287             read(World);
 288             write(World);
 289             return;
 290
 291         case Array::Contiguous:
 292             if (mode.isInBounds()) {
 293                 read(Butterfly_publicLength);
 294                 read(Butterfly_vectorLength);
 295                 read(IndexedContiguousProperties);
 296                 return;
 297             }
 298             read(World);
 299             write(World);
 300             return;
 301
 302         case Array::ArrayStorage:
 303         case Array::SlowPutArrayStorage:
 304             // Give up on life for now.
 305             read(World);
 306             write(World);
 307             return;
 308
 309         case Array::Int8Array:
 310         case Array::Int16Array:
 311         case Array::Int32Array:
 312         case Array::Uint8Array:
 313         case Array::Uint8ClampedArray:
 314         case Array::Uint16Array:
 315         case Array::Uint32Array:
 316         case Array::Float32Array:
 317         case Array::Float64Array:
 318             read(TypedArrayProperties);
 319             read(JSArrayBufferView_vector);
 320             read(JSArrayBufferView_length);
 321             return;
 322         }
 323         RELEASE_ASSERT_NOT_REACHED();
 324         return;
 325     }
 326
 327     case PutByValDirect:
 328     case PutByVal:
 329     case PutByValAlias: {
 330         ArrayMode mode = node->arrayMode();
 331         switch (mode.modeForPut().type()) {
 332         case Array::SelectUsingPredictions:
 333         case Array::Unprofiled:
 334         case Array::Undecided:
 335         case Array::String:
 336             // Assume the worst since we don't have profiling yet.
 337             read(World);
 338             write(World);
 339             return;
 340
 341         case Array::ForceExit:
 342             write(SideState);
 343             return;
 344
 345         case Array::Generic:
 346             read(World);
 347             write(World);
 348             return;
 349
 350         case Array::Arguments:
 351             read(Arguments_registers);
 352             read(Arguments_numArguments);
 353             read(Arguments_slowArguments);
 354             write(Variables);
 355             return;
 356
 357         case Array::Int32:
 358             if (node->arrayMode().isOutOfBounds()) {
 359                 read(World);
 360                 write(World);
 361                 return;
 362             }
 363             read(Butterfly_publicLength);
 364             read(Butterfly_vectorLength);
 365             read(IndexedInt32Properties);
 366             write(IndexedInt32Properties);
 367             return;
 368
 369         case Array::Double:
 370             if (node->arrayMode().isOutOfBounds()) {
 371                 read(World);
 372                 write(World);
 373                 return;
 374             }
 375             read(Butterfly_publicLength);
 376             read(Butterfly_vectorLength);
 377             read(IndexedDoubleProperties);
 378             write(IndexedDoubleProperties);
 379             return;
 380
 381         case Array::Contiguous:
 382             if (node->arrayMode().isOutOfBounds()) {
 383                 read(World);
 384                 write(World);
 385                 return;
 386             }
 387             read(Butterfly_publicLength);
 388             read(Butterfly_vectorLength);
 389             read(IndexedContiguousProperties);
 390             write(IndexedContiguousProperties);
 391             return;
 392
 393         case Array::ArrayStorage:
 394         case Array::SlowPutArrayStorage:
 395             // Give up on life for now.
 396             read(World);
 397             write(World);
 398             return;
 399
 400         case Array::Int8Array:
 401         case Array::Int16Array:
 402         case Array::Int32Array:
 403         case Array::Uint8Array:
 404         case Array::Uint8ClampedArray:
 405         case Array::Uint16Array:
 406         case Array::Uint32Array:
 407         case Array::Float32Array:
 408         case Array::Float64Array:
 409             read(JSArrayBufferView_vector);
 410             read(JSArrayBufferView_length);
 411             write(TypedArrayProperties);
 412             return;
 413         }
 414         RELEASE_ASSERT_NOT_REACHED();
 415         return;
 416     }
 417
 418     case CheckStructure:
 419     case StructureTransitionWatchpoint:
 420     case InstanceOf:
 421         read(JSCell_structureID);
 422         return;
 423
 424     case CheckArray:
 425         read(JSCell_indexingType);
 426         read(JSCell_typeInfoType);
 427         read(JSCell_structureID);
 428         return;
 429
 430     case CheckHasInstance:
 431         read(JSCell_typeInfoFlags);
 432         return;
 433
 434     case CheckExecutable:
 435         read(JSFunction_executable);
 436         return;
 437
 438     case PutStructure:
 439     case PhantomPutStructure:
 440         write(JSCell_structureID);
 441         write(JSCell_typeInfoType);
 442         write(JSCell_typeInfoFlags);
 443         write(JSCell_indexingType);
 444         return;
 445
 446     case AllocatePropertyStorage:
 447         write(JSObject_butterfly);
 448         clobberizeForAllocation(read, write);
 449         return;
 450
 451     case ReallocatePropertyStorage:
 452         read(JSObject_butterfly);
 453         write(JSObject_butterfly);
 454         clobberizeForAllocation(read, write);
 455         return;
 456
 457     case GetButterfly:
 458         read(JSObject_butterfly);
 459         return;
 460
 461     case Arrayify:
 462     case ArrayifyToStructure:
 463         read(JSCell_structureID);
 464         read(JSCell_indexingType);
 465         read(JSObject_butterfly);
 466         write(JSCell_structureID);
 467         write(JSCell_indexingType);
 468         write(JSObject_butterfly);
 469         write(Watchpoint_fire);
 470         clobberizeForAllocation(read, write);
 471         return;
 472
 473     case GetIndexedPropertyStorage:
 474         if (node->arrayMode().type() == Array::String)
 475             return;
 476         read(JSArrayBufferView_vector);
 477         return;
 478
 479     case GetTypedArrayByteOffset:
 480         read(JSArrayBufferView_vector);
 481         read(JSArrayBufferView_mode);
 482         read(Butterfly_arrayBuffer);
 483         read(ArrayBuffer_data);
 484         return;
 485
 486     case GetByOffset:
 487         read(AbstractHeap(NamedProperties, graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber));
 488         return;
 489
 490     case MultiGetByOffset:
 491         read(JSCell_structureID);
 492         read(JSObject_butterfly);
 493         read(AbstractHeap(NamedProperties, node->multiGetByOffsetData().identifierNumber));
 494         return;
 495
 496     case MultiPutByOffset:
 497         read(JSCell_structureID);
 498         read(JSObject_butterfly);
 499         write(AbstractHeap(NamedProperties, node->multiPutByOffsetData().identifierNumber));
 500         if (node->multiPutByOffsetData().writesStructures())
 501             write(JSCell_structureID);
 502         if (node->multiPutByOffsetData().reallocatesStorage()) {
 503             write(JSObject_butterfly);
 504             clobberizeForAllocation(read, write);
 505         }
 506         return;
 507
 508     case PutByOffset:
 509         write(AbstractHeap(NamedProperties, graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber));
 510         return;
 511
 512     case GetArrayLength: {
 513         ArrayMode mode = node->arrayMode();
 514         switch (mode.type()) {
 515         case Array::Int32:
 516         case Array::Double:
 517         case Array::Contiguous:
 518         case Array::ArrayStorage:
 519         case Array::SlowPutArrayStorage:
 520             read(Butterfly_publicLength);
 521             return;
 522
 523         case Array::String:
 524             return;
 525
 526         case Array::Arguments:
 527             read(Arguments_overrideLength);
 528             read(Arguments_numArguments);
 529             return;
 530
 531         default:
 532             read(JSArrayBufferView_length);
 533             return;
 534         }
 535     }
 536
 537     case GetMyScope:
 538         read(AbstractHeap(Variables, JSStack::ScopeChain));
 539         return;
 540
 541     case SkipTopScope:
 542         read(AbstractHeap(Variables, graph.activationRegister()));
 543         return;
 544
 545     case GetClosureRegisters:
 546         read(JSVariableObject_registers);
 547         return;
 548
 549     case GetClosureVar:
 550         read(AbstractHeap(Variables, node->varNumber()));
 551         return;
 552
 553     case PutClosureVar:
 554         write(AbstractHeap(Variables, node->varNumber()));
 555         return;
 556
 557     case GetGlobalVar:
 558         read(AbstractHeap(Absolute, node->registerPointer()));
 559         return;
 560
 561     case PutGlobalVar:
 562         write(AbstractHeap(Absolute, node->registerPointer()));
 563         return;
 564
 565     case NewObject:
 566     case NewArray:
 567     case NewArrayWithSize:
 568     case NewArrayBuffer:
 569     case NewRegexp:
 570     case NewStringObject:
 571     case MakeRope:
 572     case NewFunctionNoCheck:
 573     case NewFunction:
 574     case NewFunctionExpression:
 575         clobberizeForAllocation(read, write);
 576         return;
 577
 578     case NewTypedArray:
 579         clobberizeForAllocation(read, write);
 580         switch (node->child1().useKind()) {
 581         case Int32Use:
 582             return;
 583         case UntypedUse:
 584             read(World);
 585             write(World);
 586             return;
 587         default:
 588             RELEASE_ASSERT_NOT_REACHED();
 589             return;
 590         }
 591
 592     case RegExpExec:
 593     case RegExpTest:
 594         read(RegExpState);
 595         write(RegExpState);
 596         return;
 597
 598     case StringCharAt:
 599         if (node->arrayMode().isOutOfBounds()) {
 600             read(World);
 601             write(World);
 602             return;
 603         }
 604         return;
 605
 606     case CompareEq:
 607     case CompareLess:
 608     case CompareLessEq:
 609     case CompareGreater:
 610     case CompareGreaterEq:
 611         if (!node->isBinaryUseKind(UntypedUse))
 612             return;
 613         read(World);
 614         write(World);
 615         return;
 616
 617     case ToString:
 618         switch (node->child1().useKind()) {
 619         case StringObjectUse:
 620         case StringOrStringObjectUse:
 621             return;
 622
 623         case CellUse:
 624         case UntypedUse:
 625             read(World);
 626             write(World);
 627             return;
 628
 629         default:
 630             RELEASE_ASSERT_NOT_REACHED();
 631             return;
 632         }
 633
 634     case TearOffActivation:
 635         write(JSVariableObject_registers);
 636         return;
 637
 638     case TearOffArguments:
 639         write(Arguments_registers);
 640         return;
 641
 642     case GetMyArgumentsLength:
 643         read(AbstractHeap(Variables, graph.argumentsRegisterFor(node->origin.semantic)));
 644         read(AbstractHeap(Variables, JSStack::ArgumentCount));
 645         return;
 646
 647     case GetMyArgumentByVal:
 648         read(Variables);
 649         return;
 650
 651     case CheckArgumentsNotCreated:
 652         read(AbstractHeap(Variables, graph.argumentsRegisterFor(node->origin.semantic)));
 653         return;
 654
 655     case ThrowReferenceError:
 656         write(SideState);
 657         clobberizeForAllocation(read, write);
 658         return;
 659
 660     case CountExecution:
 661     case CheckWatchdogTimer:
 662         read(InternalState);
 663         write(InternalState);
 664         return;
 665
 666     case StoreBarrier:
 667     case StoreBarrierWithNullCheck:
 668         read(BarrierState);
 669         write(BarrierState);
 670         return;
 671
 672     case LastNodeType:
 673         RELEASE_ASSERT_NOT_REACHED();
 674         return;
 675     }
 676
 677     RELEASE_ASSERT_NOT_REACHED();
 678 }
 679
 680 class NoOpClobberize {
 681 public:
 682     NoOpClobberize() { }
 683     void operator()(AbstractHeap) { }
 684 };
 685
 686 class CheckClobberize {
 687 public:
 688     CheckClobberize()
 689         : m_result(false)
 690     {
 691     }
 692
 693     void operator()(AbstractHeap) { m_result = true; }
 694
 695     bool result() const { return m_result; }
 696
 697 private:
 698     bool m_result;
 699 };
 700
 701 bool doesWrites(Graph&, Node*);
 702
 703 class AbstractHeapOverlaps {
 704 public:
 705     AbstractHeapOverlaps(AbstractHeap heap)
 706         : m_heap(heap)
 707         , m_result(false)
 708     {
 709     }
 710
 711     void operator()(AbstractHeap otherHeap)
 712     {
 713         if (m_result)
 714             return;
 715         m_result = m_heap.overlaps(otherHeap);
 716     }
 717
 718     bool result() const { return m_result; }
 719
 720 private:
 721     AbstractHeap m_heap;
 722     bool m_result;
 723 };
 724
 725 bool writesOverlap(Graph&, Node*, AbstractHeap);
 726
 727 } } // namespace JSC::DFG
 728
 729 #endif // ENABLE(DFG_JIT)
 730
 731 #endif // DFGClobberize_h
 732