dfg/DFGArrayMode.h

   1 /*
   2  * Copyright (C) 2012-2015 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 DFGArrayMode_h
  27 #define DFGArrayMode_h
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "ArrayProfile.h"
  32 #include "DFGNodeFlags.h"
  33 #include "SpeculatedType.h"
  34
  35 namespace JSC {
  36
  37 struct CodeOrigin;
  38
  39 namespace DFG {
  40
  41 class Graph;
  42 struct AbstractValue;
  43 struct Node;
  44
  45 // Use a namespace + enum instead of enum alone to avoid the namespace collision
  46 // that would otherwise occur, since we say things like "Int8Array" and "JSArray"
  47 // in lots of other places, to mean subtly different things.
  48 namespace Array {
  49 enum Action {
  50     Read,
  51     Write
  52 };
  53
  54 enum Type {
  55     SelectUsingPredictions, // Implies that we need predictions to decide. We will never get to the backend in this mode.
  56     Unprofiled, // Implies that array profiling didn't see anything. But that could be because the operands didn't comply with basic type assumptions (base is cell, property is int). This either becomes Generic or ForceExit depending on value profiling.
  57     ForceExit, // Implies that we have no idea how to execute this operation, so we should just give up.
  58     Generic,
  59     String,
  60
  61     Undecided,
  62     Int32,
  63     Double,
  64     Contiguous,
  65     ArrayStorage,
  66     SlowPutArrayStorage,
  67
  68     DirectArguments,
  69     ScopedArguments,
  70
  71     Int8Array,
  72     Int16Array,
  73     Int32Array,
  74     Uint8Array,
  75     Uint8ClampedArray,
  76     Uint16Array,
  77     Uint32Array,
  78     Float32Array,
  79     Float64Array
  80 };
  81
  82 enum Class {
  83     NonArray, // Definitely some object that is not a JSArray.
  84     OriginalNonArray, // Definitely some object that is not a JSArray, but that object has the original structure.
  85     Array, // Definitely a JSArray, and may or may not have custom properties or have undergone some other bizarre transitions.
  86     OriginalArray, // Definitely a JSArray, and still has one of the primordial JSArray structures for the global object that this code block (possibly inlined code block) belongs to.
  87     PossiblyArray // Some object that may or may not be a JSArray.
  88 };
  89
  90 enum Speculation {
  91     SaneChain, // In bounds and the array prototype chain is still intact, i.e. loading a hole doesn't require special treatment.
  92
  93     InBounds, // In bounds and not loading a hole.
  94     ToHole, // Potentially storing to a hole.
  95     OutOfBounds // Out-of-bounds access and anything can happen.
  96 };
  97 enum Conversion {
  98     AsIs,
  99     Convert
 100 };
 101 } // namespace Array
 102
 103 const char* arrayTypeToString(Array::Type);
 104 const char* arrayClassToString(Array::Class);
 105 const char* arraySpeculationToString(Array::Speculation);
 106 const char* arrayConversionToString(Array::Conversion);
 107
 108 IndexingType toIndexingShape(Array::Type);
 109
 110 TypedArrayType toTypedArrayType(Array::Type);
 111 Array::Type toArrayType(TypedArrayType);
 112
 113 bool permitsBoundsCheckLowering(Array::Type);
 114
 115 class ArrayMode {
 116 public:
 117     ArrayMode()
 118     {
 119         u.asBytes.type = Array::SelectUsingPredictions;
 120         u.asBytes.arrayClass = Array::NonArray;
 121         u.asBytes.speculation = Array::InBounds;
 122         u.asBytes.conversion = Array::AsIs;
 123     }
 124
 125     explicit ArrayMode(Array::Type type)
 126     {
 127         u.asBytes.type = type;
 128         u.asBytes.arrayClass = Array::NonArray;
 129         u.asBytes.speculation = Array::InBounds;
 130         u.asBytes.conversion = Array::AsIs;
 131     }
 132
 133     ArrayMode(Array::Type type, Array::Class arrayClass)
 134     {
 135         u.asBytes.type = type;
 136         u.asBytes.arrayClass = arrayClass;
 137         u.asBytes.speculation = Array::InBounds;
 138         u.asBytes.conversion = Array::AsIs;
 139     }
 140
 141     ArrayMode(Array::Type type, Array::Class arrayClass, Array::Speculation speculation, Array::Conversion conversion)
 142     {
 143         u.asBytes.type = type;
 144         u.asBytes.arrayClass = arrayClass;
 145         u.asBytes.speculation = speculation;
 146         u.asBytes.conversion = conversion;
 147     }
 148
 149     ArrayMode(Array::Type type, Array::Class arrayClass, Array::Conversion conversion)
 150     {
 151         u.asBytes.type = type;
 152         u.asBytes.arrayClass = arrayClass;
 153         u.asBytes.speculation = Array::InBounds;
 154         u.asBytes.conversion = conversion;
 155     }
 156
 157     Array::Type type() const { return static_cast<Array::Type>(u.asBytes.type); }
 158     Array::Class arrayClass() const { return static_cast<Array::Class>(u.asBytes.arrayClass); }
 159     Array::Speculation speculation() const { return static_cast<Array::Speculation>(u.asBytes.speculation); }
 160     Array::Conversion conversion() const { return static_cast<Array::Conversion>(u.asBytes.conversion); }
 161
 162     unsigned asWord() const { return u.asWord; }
 163
 164     static ArrayMode fromWord(unsigned word)
 165     {
 166         return ArrayMode(word);
 167     }
 168
 169     static ArrayMode fromObserved(const ConcurrentJITLocker&, ArrayProfile*, Array::Action, bool makeSafe);
 170
 171     ArrayMode withSpeculation(Array::Speculation speculation) const
 172     {
 173         return ArrayMode(type(), arrayClass(), speculation, conversion());
 174     }
 175
 176     ArrayMode withArrayClass(Array::Class arrayClass) const
 177     {
 178         return ArrayMode(type(), arrayClass, speculation(), conversion());
 179     }
 180
 181     ArrayMode withSpeculationFromProfile(const ConcurrentJITLocker& locker, ArrayProfile* profile, bool makeSafe) const
 182     {
 183         Array::Speculation mySpeculation;
 184
 185         if (makeSafe)
 186             mySpeculation = Array::OutOfBounds;
 187         else if (profile->mayStoreToHole(locker))
 188             mySpeculation = Array::ToHole;
 189         else
 190             mySpeculation = Array::InBounds;
 191
 192         return withSpeculation(mySpeculation);
 193     }
 194
 195     ArrayMode withProfile(const ConcurrentJITLocker& locker, ArrayProfile* profile, bool makeSafe) const
 196     {
 197         Array::Class myArrayClass;
 198
 199         if (isJSArray()) {
 200             if (profile->usesOriginalArrayStructures(locker) && benefitsFromOriginalArray())
 201                 myArrayClass = Array::OriginalArray;
 202             else
 203                 myArrayClass = Array::Array;
 204         } else
 205             myArrayClass = arrayClass();
 206
 207         return withArrayClass(myArrayClass).withSpeculationFromProfile(locker, profile, makeSafe);
 208     }
 209
 210     ArrayMode withType(Array::Type type) const
 211     {
 212         return ArrayMode(type, arrayClass(), speculation(), conversion());
 213     }
 214
 215     ArrayMode withConversion(Array::Conversion conversion) const
 216     {
 217         return ArrayMode(type(), arrayClass(), speculation(), conversion);
 218     }
 219
 220     ArrayMode withTypeAndConversion(Array::Type type, Array::Conversion conversion) const
 221     {
 222         return ArrayMode(type, arrayClass(), speculation(), conversion);
 223     }
 224
 225     ArrayMode refine(Graph&, Node*, SpeculatedType base, SpeculatedType index, SpeculatedType value = SpecNone) const;
 226
 227     bool alreadyChecked(Graph&, Node*, const AbstractValue&) const;
 228
 229     void dump(PrintStream&) const;
 230
 231     bool usesButterfly() const
 232     {
 233         switch (type()) {
 234         case Array::Int32:
 235         case Array::Double:
 236         case Array::Contiguous:
 237         case Array::ArrayStorage:
 238         case Array::SlowPutArrayStorage:
 239             return true;
 240         default:
 241             return false;
 242         }
 243     }
 244
 245     bool isJSArray() const
 246     {
 247         switch (arrayClass()) {
 248         case Array::Array:
 249         case Array::OriginalArray:
 250             return true;
 251         default:
 252             return false;
 253         }
 254     }
 255
 256     bool isJSArrayWithOriginalStructure() const
 257     {
 258         return arrayClass() == Array::OriginalArray;
 259     }
 260
 261     bool isSaneChain() const
 262     {
 263         return speculation() == Array::SaneChain;
 264     }
 265
 266     bool isInBounds() const
 267     {
 268         switch (speculation()) {
 269         case Array::SaneChain:
 270         case Array::InBounds:
 271             return true;
 272         default:
 273             return false;
 274         }
 275     }
 276
 277     bool mayStoreToHole() const
 278     {
 279         return !isInBounds();
 280     }
 281
 282     bool isOutOfBounds() const
 283     {
 284         return speculation() == Array::OutOfBounds;
 285     }
 286
 287     bool isSlowPut() const
 288     {
 289         return type() == Array::SlowPutArrayStorage;
 290     }
 291
 292     bool canCSEStorage() const
 293     {
 294         switch (type()) {
 295         case Array::SelectUsingPredictions:
 296         case Array::Unprofiled:
 297         case Array::ForceExit:
 298         case Array::Generic:
 299         case Array::DirectArguments:
 300         case Array::ScopedArguments:
 301             return false;
 302         default:
 303             return true;
 304         }
 305     }
 306
 307     bool lengthNeedsStorage() const
 308     {
 309         switch (type()) {
 310         case Array::Undecided:
 311         case Array::Int32:
 312         case Array::Double:
 313         case Array::Contiguous:
 314         case Array::ArrayStorage:
 315         case Array::SlowPutArrayStorage:
 316             return true;
 317         default:
 318             return false;
 319         }
 320     }
 321
 322     ArrayMode modeForPut() const
 323     {
 324         switch (type()) {
 325         case Array::String:
 326         case Array::DirectArguments:
 327         case Array::ScopedArguments:
 328             return ArrayMode(Array::Generic);
 329         default:
 330             return *this;
 331         }
 332     }
 333
 334     bool isSpecific() const
 335     {
 336         switch (type()) {
 337         case Array::SelectUsingPredictions:
 338         case Array::Unprofiled:
 339         case Array::ForceExit:
 340         case Array::Generic:
 341         case Array::Undecided:
 342             return false;
 343         default:
 344             return true;
 345         }
 346     }
 347
 348     bool supportsLength() const
 349     {
 350         switch (type()) {
 351         case Array::SelectUsingPredictions:
 352         case Array::Unprofiled:
 353         case Array::ForceExit:
 354         case Array::Generic:
 355             return false;
 356         case Array::Int32:
 357         case Array::Double:
 358         case Array::Contiguous:
 359         case Array::ArrayStorage:
 360         case Array::SlowPutArrayStorage:
 361             return isJSArray();
 362         default:
 363             return true;
 364         }
 365     }
 366
 367     bool permitsBoundsCheckLowering() const;
 368
 369     bool benefitsFromOriginalArray() const
 370     {
 371         switch (type()) {
 372         case Array::Int32:
 373         case Array::Double:
 374         case Array::Contiguous:
 375         case Array::ArrayStorage:
 376             return true;
 377         default:
 378             return false;
 379         }
 380     }
 381
 382     // Returns 0 if this is not OriginalArray.
 383     Structure* originalArrayStructure(Graph&, const CodeOrigin&) const;
 384     Structure* originalArrayStructure(Graph&, Node*) const;
 385
 386     bool doesConversion() const
 387     {
 388         return conversion() != Array::AsIs;
 389     }
 390
 391     bool structureWouldPassArrayModeFiltering(Structure* structure)
 392     {
 393         return arrayModesAlreadyChecked(arrayModeFromStructure(structure), arrayModesThatPassFiltering());
 394     }
 395
 396     ArrayModes arrayModesThatPassFiltering() const
 397     {
 398         switch (type()) {
 399         case Array::Generic:
 400             return ALL_ARRAY_MODES;
 401         case Array::Int32:
 402             return arrayModesWithIndexingShape(Int32Shape);
 403         case Array::Double:
 404             return arrayModesWithIndexingShape(DoubleShape);
 405         case Array::Contiguous:
 406             return arrayModesWithIndexingShape(ContiguousShape);
 407         case Array::ArrayStorage:
 408             return arrayModesWithIndexingShape(ArrayStorageShape);
 409         case Array::SlowPutArrayStorage:
 410             return arrayModesWithIndexingShapes(SlowPutArrayStorageShape, ArrayStorageShape);
 411         default:
 412             return asArrayModes(NonArray);
 413         }
 414     }
 415
 416     bool getIndexedPropertyStorageMayTriggerGC() const
 417     {
 418         return type() == Array::String;
 419     }
 420
 421     IndexingType shapeMask() const
 422     {
 423         return toIndexingShape(type());
 424     }
 425
 426     TypedArrayType typedArrayType() const
 427     {
 428         return toTypedArrayType(type());
 429     }
 430
 431     bool operator==(const ArrayMode& other) const
 432     {
 433         return type() == other.type()
 434             && arrayClass() == other.arrayClass()
 435             && speculation() == other.speculation()
 436             && conversion() == other.conversion();
 437     }
 438
 439     bool operator!=(const ArrayMode& other) const
 440     {
 441         return !(*this == other);
 442     }
 443 private:
 444     explicit ArrayMode(unsigned word)
 445     {
 446         u.asWord = word;
 447     }
 448
 449     ArrayModes arrayModesWithIndexingShape(IndexingType shape) const
 450     {
 451         switch (arrayClass()) {
 452         case Array::NonArray:
 453         case Array::OriginalNonArray:
 454             return asArrayModes(shape);
 455         case Array::Array:
 456         case Array::OriginalArray:
 457             return asArrayModes(shape | IsArray);
 458         case Array::PossiblyArray:
 459             return asArrayModes(shape) | asArrayModes(shape | IsArray);
 460         default:
 461             // This is only necessary for C++ compilers that don't understand enums.
 462             return 0;
 463         }
 464     }
 465
 466     ArrayModes arrayModesWithIndexingShapes(IndexingType shape1, IndexingType shape2) const
 467     {
 468         ArrayModes arrayMode1 = arrayModesWithIndexingShape(shape1);
 469         ArrayModes arrayMode2 = arrayModesWithIndexingShape(shape2);
 470         return arrayMode1 | arrayMode2;
 471     }
 472
 473     bool alreadyChecked(Graph&, Node*, const AbstractValue&, IndexingType shape) const;
 474
 475     union {
 476         struct {
 477             uint8_t type;
 478             uint8_t arrayClass;
 479             uint8_t speculation;
 480             uint8_t conversion;
 481         } asBytes;
 482         unsigned asWord;
 483     } u;
 484 };
 485
 486 static inline bool canCSEStorage(const ArrayMode& arrayMode)
 487 {
 488     return arrayMode.canCSEStorage();
 489 }
 490
 491 static inline bool lengthNeedsStorage(const ArrayMode& arrayMode)
 492 {
 493     return arrayMode.lengthNeedsStorage();
 494 }
 495
 496 static inline bool neverNeedsStorage(const ArrayMode&)
 497 {
 498     return false;
 499 }
 500
 501 } } // namespace JSC::DFG
 502
 503 namespace WTF {
 504
 505 class PrintStream;
 506 void printInternal(PrintStream&, JSC::DFG::Array::Type);
 507 void printInternal(PrintStream&, JSC::DFG::Array::Class);
 508 void printInternal(PrintStream&, JSC::DFG::Array::Speculation);
 509 void printInternal(PrintStream&, JSC::DFG::Array::Conversion);
 510
 511 } // namespace WTF
 512
 513 #endif // ENABLE(DFG_JIT)
 514
 515 #endif // DFGArrayMode_h
 516