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 35namespace JSC { 36 37struct CodeOrigin; 38 39namespace DFG { 40 41class Graph; 42struct AbstractValue; 43struct 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. 48namespace Array { 49enum Action { 50 Read, 51 Write 52}; 53 54enum 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 80enum 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 88enum 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}; 94enum Conversion { 95 AsIs, 96 Convert, 97 RageConvert 98}; 99} // namespace Array 100 101const char* arrayTypeToString(Array::Type); 102const char* arrayClassToString(Array::Class); 103const char* arraySpeculationToString(Array::Speculation); 104const char* arrayConversionToString(Array::Conversion); 105 106IndexingType toIndexingShape(Array::Type); 107 108TypedArrayType toTypedArrayType(Array::Type); 109Array::Type toArrayType(TypedArrayType); 110 111bool permitsBoundsCheckLowering(Array::Type); 112 113class ArrayMode { 114public: 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 arrayModesWithIndexingShape(SlowPutArrayStorageShape); 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 } 442private: 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 bool alreadyChecked(Graph&, Node*, AbstractValue&, IndexingType shape) const; 466 467 union { 468 struct { 469 uint8_t type; 470 uint8_t arrayClass; 471 uint8_t speculation; 472 uint8_t conversion; 473 } asBytes; 474 unsigned asWord; 475 } u; 476}; 477 478static inline bool canCSEStorage(const ArrayMode& arrayMode) 479{ 480 return arrayMode.canCSEStorage(); 481} 482 483static inline bool lengthNeedsStorage(const ArrayMode& arrayMode) 484{ 485 return arrayMode.lengthNeedsStorage(); 486} 487 488static inline bool neverNeedsStorage(const ArrayMode&) 489{ 490 return false; 491} 492 493} } // namespace JSC::DFG 494 495namespace WTF { 496 497class PrintStream; 498void printInternal(PrintStream&, JSC::DFG::Array::Type); 499void printInternal(PrintStream&, JSC::DFG::Array::Class); 500void printInternal(PrintStream&, JSC::DFG::Array::Speculation); 501void printInternal(PrintStream&, JSC::DFG::Array::Conversion); 502 503} // namespace WTF 504 505#endif // ENABLE(DFG_JIT) 506 507#endif // DFGArrayMode_h 508 509