dfg/DFGArrayMode.h

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