dfg/DFGArrayMode.h

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