dfg/DFGArrayMode.cpp

   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 #include "config.h"
  27 #include "DFGArrayMode.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGAbstractValue.h"
  32 #include "DFGGraph.h"
  33 #include "Operations.h"
  34
  35 namespace JSC { namespace DFG {
  36
  37 ArrayMode ArrayMode::fromObserved(ArrayProfile* profile, Array::Action action, bool makeSafe)
  38 {
  39     ArrayModes observed = profile->observedArrayModes();
  40     switch (observed) {
  41     case 0:
  42         return ArrayMode(Array::Unprofiled);
  43     case asArrayModes(NonArray):
  44         if (action == Array::Write && !profile->mayInterceptIndexedAccesses())
  45             return ArrayMode(Array::Undecided, Array::NonArray, Array::OutOfBounds, Array::Convert);
  46         return ArrayMode(Array::SelectUsingPredictions);
  47
  48     case asArrayModes(ArrayWithUndecided):
  49         if (action == Array::Write)
  50             return ArrayMode(Array::Undecided, Array::Array, Array::OutOfBounds, Array::Convert);
  51         return ArrayMode(Array::Generic);
  52
  53     case asArrayModes(NonArray) | asArrayModes(ArrayWithUndecided):
  54         if (action == Array::Write && !profile->mayInterceptIndexedAccesses())
  55             return ArrayMode(Array::Undecided, Array::PossiblyArray, Array::OutOfBounds, Array::Convert);
  56         return ArrayMode(Array::SelectUsingPredictions);
  57
  58     case asArrayModes(NonArrayWithInt32):
  59         return ArrayMode(Array::Int32, Array::NonArray, Array::AsIs).withProfile(profile, makeSafe);
  60     case asArrayModes(ArrayWithInt32):
  61         return ArrayMode(Array::Int32, Array::Array, Array::AsIs).withProfile(profile, makeSafe);
  62     case asArrayModes(NonArrayWithInt32) | asArrayModes(ArrayWithInt32):
  63         return ArrayMode(Array::Int32, Array::PossiblyArray, Array::AsIs).withProfile(profile, makeSafe);
  64
  65     case asArrayModes(NonArrayWithDouble):
  66         return ArrayMode(Array::Double, Array::NonArray, Array::AsIs).withProfile(profile, makeSafe);
  67     case asArrayModes(ArrayWithDouble):
  68         return ArrayMode(Array::Double, Array::Array, Array::AsIs).withProfile(profile, makeSafe);
  69     case asArrayModes(NonArrayWithDouble) | asArrayModes(ArrayWithDouble):
  70         return ArrayMode(Array::Double, Array::PossiblyArray, Array::AsIs).withProfile(profile, makeSafe);
  71
  72     case asArrayModes(NonArrayWithContiguous):
  73         return ArrayMode(Array::Contiguous, Array::NonArray, Array::AsIs).withProfile(profile, makeSafe);
  74     case asArrayModes(ArrayWithContiguous):
  75         return ArrayMode(Array::Contiguous, Array::Array, Array::AsIs).withProfile(profile, makeSafe);
  76     case asArrayModes(NonArrayWithContiguous) | asArrayModes(ArrayWithContiguous):
  77         return ArrayMode(Array::Contiguous, Array::PossiblyArray, Array::AsIs).withProfile(profile, makeSafe);
  78
  79     case asArrayModes(NonArrayWithArrayStorage):
  80         return ArrayMode(Array::ArrayStorage, Array::NonArray, Array::AsIs).withProfile(profile, makeSafe);
  81     case asArrayModes(NonArrayWithSlowPutArrayStorage):
  82     case asArrayModes(NonArrayWithArrayStorage) | asArrayModes(NonArrayWithSlowPutArrayStorage):
  83         return ArrayMode(Array::SlowPutArrayStorage, Array::NonArray, Array::AsIs).withProfile(profile, makeSafe);
  84     case asArrayModes(ArrayWithArrayStorage):
  85         return ArrayMode(Array::ArrayStorage, Array::Array, Array::AsIs).withProfile(profile, makeSafe);
  86     case asArrayModes(ArrayWithSlowPutArrayStorage):
  87     case asArrayModes(ArrayWithArrayStorage) | asArrayModes(ArrayWithSlowPutArrayStorage):
  88         return ArrayMode(Array::SlowPutArrayStorage, Array::Array, Array::AsIs).withProfile(profile, makeSafe);
  89     case asArrayModes(NonArrayWithArrayStorage) | asArrayModes(ArrayWithArrayStorage):
  90         return ArrayMode(Array::ArrayStorage, Array::PossiblyArray, Array::AsIs).withProfile(profile, makeSafe);
  91     case asArrayModes(NonArrayWithSlowPutArrayStorage) | asArrayModes(ArrayWithSlowPutArrayStorage):
  92     case asArrayModes(NonArrayWithArrayStorage) | asArrayModes(ArrayWithArrayStorage) | asArrayModes(NonArrayWithSlowPutArrayStorage) | asArrayModes(ArrayWithSlowPutArrayStorage):
  93         return ArrayMode(Array::SlowPutArrayStorage, Array::PossiblyArray, Array::AsIs).withProfile(profile, makeSafe);
  94
  95     default:
  96         if ((observed & asArrayModes(NonArray)) && profile->mayInterceptIndexedAccesses())
  97             return ArrayMode(Array::SelectUsingPredictions);
  98
  99         Array::Type type;
 100         Array::Class arrayClass;
 101
 102         if (shouldUseSlowPutArrayStorage(observed))
 103             type = Array::SlowPutArrayStorage;
 104         else if (shouldUseFastArrayStorage(observed))
 105             type = Array::ArrayStorage;
 106         else if (shouldUseContiguous(observed))
 107             type = Array::Contiguous;
 108         else if (shouldUseDouble(observed))
 109             type = Array::Double;
 110         else if (shouldUseInt32(observed))
 111             type = Array::Int32;
 112         else
 113             type = Array::Undecided;
 114
 115         if (hasSeenArray(observed) && hasSeenNonArray(observed))
 116             arrayClass = Array::PossiblyArray;
 117         else if (hasSeenArray(observed))
 118             arrayClass = Array::Array;
 119         else if (hasSeenNonArray(observed))
 120             arrayClass = Array::NonArray;
 121         else
 122             arrayClass = Array::PossiblyArray;
 123
 124         return ArrayMode(type, arrayClass, Array::Convert).withProfile(profile, makeSafe);
 125     }
 126 }
 127
 128 ArrayMode ArrayMode::refine(SpeculatedType base, SpeculatedType index, SpeculatedType value, NodeFlags flags) const
 129 {
 130     if (!base || !index) {
 131         // It can be that we had a legitimate arrayMode but no incoming predictions. That'll
 132         // happen if we inlined code based on, say, a global variable watchpoint, but later
 133         // realized that the callsite could not have possibly executed. It may be worthwhile
 134         // to fix that, but for now I'm leaving it as-is.
 135         return ArrayMode(Array::ForceExit);
 136     }
 137
 138     if (!isInt32Speculation(index))
 139         return ArrayMode(Array::Generic);
 140
 141     // Note: our profiling currently doesn't give us good information in case we have
 142     // an unlikely control flow path that sets the base to a non-cell value. Value
 143     // profiling and prediction propagation will probably tell us that the value is
 144     // either a cell or not, but that doesn't tell us which is more likely: that this
 145     // is an array access on a cell (what we want and can optimize) or that the user is
 146     // doing a crazy by-val access on a primitive (we can't easily optimize this and
 147     // don't want to). So, for now, we assume that if the base is not a cell according
 148     // to value profiling, but the array profile tells us something else, then we
 149     // should just trust the array profile.
 150
 151     switch (type()) {
 152     case Array::Unprofiled:
 153         return ArrayMode(Array::ForceExit);
 154
 155     case Array::Undecided:
 156         if (!value)
 157             return withType(Array::ForceExit);
 158         if (isInt32Speculation(value))
 159             return withTypeAndConversion(Array::Int32, Array::Convert);
 160         if (isNumberSpeculation(value))
 161             return withTypeAndConversion(Array::Double, Array::Convert);
 162         return withTypeAndConversion(Array::Contiguous, Array::Convert);
 163
 164     case Array::Int32:
 165         if (!value || isInt32Speculation(value))
 166             return *this;
 167         if (isNumberSpeculation(value))
 168             return withTypeAndConversion(Array::Double, Array::Convert);
 169         return withTypeAndConversion(Array::Contiguous, Array::Convert);
 170
 171     case Array::Double:
 172         if (flags & NodeUsedAsInt)
 173             return withTypeAndConversion(Array::Contiguous, Array::RageConvert);
 174         if (!value || isNumberSpeculation(value))
 175             return *this;
 176         return withTypeAndConversion(Array::Contiguous, Array::Convert);
 177
 178     case Array::Contiguous:
 179         if (doesConversion() && (flags & NodeUsedAsInt))
 180             return withConversion(Array::RageConvert);
 181         return *this;
 182
 183     case Array::SelectUsingPredictions:
 184         base &= ~SpecOther;
 185
 186         if (isStringSpeculation(base))
 187             return ArrayMode(Array::String);
 188
 189         if (isArgumentsSpeculation(base))
 190             return ArrayMode(Array::Arguments);
 191
 192         if (isInt8ArraySpeculation(base))
 193             return ArrayMode(Array::Int8Array);
 194
 195         if (isInt16ArraySpeculation(base))
 196             return ArrayMode(Array::Int16Array);
 197
 198         if (isInt32ArraySpeculation(base))
 199             return ArrayMode(Array::Int32Array);
 200
 201         if (isUint8ArraySpeculation(base))
 202             return ArrayMode(Array::Uint8Array);
 203
 204         if (isUint8ClampedArraySpeculation(base))
 205             return ArrayMode(Array::Uint8ClampedArray);
 206
 207         if (isUint16ArraySpeculation(base))
 208             return ArrayMode(Array::Uint16Array);
 209
 210         if (isUint32ArraySpeculation(base))
 211             return ArrayMode(Array::Uint32Array);
 212
 213         if (isFloat32ArraySpeculation(base))
 214             return ArrayMode(Array::Float32Array);
 215
 216         if (isFloat64ArraySpeculation(base))
 217             return ArrayMode(Array::Float64Array);
 218
 219         return ArrayMode(Array::Generic);
 220
 221     default:
 222         return *this;
 223     }
 224 }
 225
 226 Structure* ArrayMode::originalArrayStructure(Graph& graph, const CodeOrigin& codeOrigin) const
 227 {
 228     if (!isJSArrayWithOriginalStructure())
 229         return 0;
 230
 231     JSGlobalObject* globalObject = graph.globalObjectFor(codeOrigin);
 232
 233     switch (type()) {
 234     case Array::Int32:
 235         return globalObject->originalArrayStructureForIndexingType(ArrayWithInt32);
 236     case Array::Double:
 237         return globalObject->originalArrayStructureForIndexingType(ArrayWithDouble);
 238     case Array::Contiguous:
 239         return globalObject->originalArrayStructureForIndexingType(ArrayWithContiguous);
 240     case Array::ArrayStorage:
 241         return globalObject->originalArrayStructureForIndexingType(ArrayWithArrayStorage);
 242     default:
 243         CRASH();
 244         return 0;
 245     }
 246 }
 247
 248 Structure* ArrayMode::originalArrayStructure(Graph& graph, Node* node) const
 249 {
 250     return originalArrayStructure(graph, node->codeOrigin);
 251 }
 252
 253 bool ArrayMode::alreadyChecked(Graph& graph, Node* node, AbstractValue& value, IndexingType shape) const
 254 {
 255     switch (arrayClass()) {
 256     case Array::OriginalArray:
 257         return value.m_currentKnownStructure.hasSingleton()
 258             && (value.m_currentKnownStructure.singleton()->indexingType() & IndexingShapeMask) == shape
 259             && (value.m_currentKnownStructure.singleton()->indexingType() & IsArray)
 260             && graph.globalObjectFor(node->codeOrigin)->isOriginalArrayStructure(value.m_currentKnownStructure.singleton());
 261
 262     case Array::Array:
 263         if (arrayModesAlreadyChecked(value.m_arrayModes, asArrayModes(shape | IsArray)))
 264             return true;
 265         return value.m_currentKnownStructure.hasSingleton()
 266             && (value.m_currentKnownStructure.singleton()->indexingType() & IndexingShapeMask) == shape
 267             && (value.m_currentKnownStructure.singleton()->indexingType() & IsArray);
 268
 269     default:
 270         if (arrayModesAlreadyChecked(value.m_arrayModes, asArrayModes(shape) | asArrayModes(shape | IsArray)))
 271             return true;
 272         return value.m_currentKnownStructure.hasSingleton()
 273             && (value.m_currentKnownStructure.singleton()->indexingType() & IndexingShapeMask) == shape;
 274     }
 275 }
 276
 277 bool ArrayMode::alreadyChecked(Graph& graph, Node* node, AbstractValue& value) const
 278 {
 279     switch (type()) {
 280     case Array::Generic:
 281         return true;
 282
 283     case Array::ForceExit:
 284         return false;
 285
 286     case Array::String:
 287         return speculationChecked(value.m_type, SpecString);
 288
 289     case Array::Int32:
 290         return alreadyChecked(graph, node, value, Int32Shape);
 291
 292     case Array::Double:
 293         return alreadyChecked(graph, node, value, DoubleShape);
 294
 295     case Array::Contiguous:
 296         return alreadyChecked(graph, node, value, ContiguousShape);
 297
 298     case Array::ArrayStorage:
 299         return alreadyChecked(graph, node, value, ArrayStorageShape);
 300
 301     case Array::SlowPutArrayStorage:
 302         switch (arrayClass()) {
 303         case Array::OriginalArray:
 304             CRASH();
 305             return false;
 306
 307         case Array::Array:
 308             if (arrayModesAlreadyChecked(value.m_arrayModes, asArrayModes(ArrayWithArrayStorage) | asArrayModes(ArrayWithSlowPutArrayStorage)))
 309                 return true;
 310             return value.m_currentKnownStructure.hasSingleton()
 311                 && hasArrayStorage(value.m_currentKnownStructure.singleton()->indexingType())
 312                 && (value.m_currentKnownStructure.singleton()->indexingType() & IsArray);
 313
 314         default:
 315             if (arrayModesAlreadyChecked(value.m_arrayModes, asArrayModes(NonArrayWithArrayStorage) | asArrayModes(ArrayWithArrayStorage) | asArrayModes(NonArrayWithSlowPutArrayStorage) | asArrayModes(ArrayWithSlowPutArrayStorage)))
 316                 return true;
 317             return value.m_currentKnownStructure.hasSingleton()
 318                 && hasArrayStorage(value.m_currentKnownStructure.singleton()->indexingType());
 319         }
 320
 321     case Array::Arguments:
 322         return speculationChecked(value.m_type, SpecArguments);
 323
 324     case Array::Int8Array:
 325         return speculationChecked(value.m_type, SpecInt8Array);
 326
 327     case Array::Int16Array:
 328         return speculationChecked(value.m_type, SpecInt16Array);
 329
 330     case Array::Int32Array:
 331         return speculationChecked(value.m_type, SpecInt32Array);
 332
 333     case Array::Uint8Array:
 334         return speculationChecked(value.m_type, SpecUint8Array);
 335
 336     case Array::Uint8ClampedArray:
 337         return speculationChecked(value.m_type, SpecUint8ClampedArray);
 338
 339     case Array::Uint16Array:
 340         return speculationChecked(value.m_type, SpecUint16Array);
 341
 342     case Array::Uint32Array:
 343         return speculationChecked(value.m_type, SpecUint32Array);
 344
 345     case Array::Float32Array:
 346         return speculationChecked(value.m_type, SpecFloat32Array);
 347
 348     case Array::Float64Array:
 349         return speculationChecked(value.m_type, SpecFloat64Array);
 350
 351     case Array::SelectUsingPredictions:
 352     case Array::Unprofiled:
 353     case Array::Undecided:
 354         break;
 355     }
 356
 357     CRASH();
 358     return false;
 359 }
 360
 361 const char* arrayTypeToString(Array::Type type)
 362 {
 363     switch (type) {
 364     case Array::SelectUsingPredictions:
 365         return "SelectUsingPredictions";
 366     case Array::Unprofiled:
 367         return "Unprofiled";
 368     case Array::Generic:
 369         return "Generic";
 370     case Array::ForceExit:
 371         return "ForceExit";
 372     case Array::String:
 373         return "String";
 374     case Array::Undecided:
 375         return "Undecided";
 376     case Array::Int32:
 377         return "Int32";
 378     case Array::Double:
 379         return "Double";
 380     case Array::Contiguous:
 381         return "Contiguous";
 382     case Array::ArrayStorage:
 383         return "ArrayStorage";
 384     case Array::SlowPutArrayStorage:
 385         return "SlowPutArrayStorage";
 386     case Array::Arguments:
 387         return "Arguments";
 388     case Array::Int8Array:
 389         return "Int8Array";
 390     case Array::Int16Array:
 391         return "Int16Array";
 392     case Array::Int32Array:
 393         return "Int32Array";
 394     case Array::Uint8Array:
 395         return "Uint8Array";
 396     case Array::Uint8ClampedArray:
 397         return "Uint8ClampedArray";
 398     case Array::Uint16Array:
 399         return "Uint16Array";
 400     case Array::Uint32Array:
 401         return "Uint32Array";
 402     case Array::Float32Array:
 403         return "Float32Array";
 404     case Array::Float64Array:
 405         return "Float64Array";
 406     default:
 407         // Better to return something then it is to crash. Remember, this method
 408         // is being called from our main diagnostic tool, the IR dumper. It's like
 409         // a stack trace. So if we get here then probably something has already
 410         // gone wrong.
 411         return "Unknown!";
 412     }
 413 }
 414
 415 const char* arrayClassToString(Array::Class arrayClass)
 416 {
 417     switch (arrayClass) {
 418     case Array::Array:
 419         return "Array";
 420     case Array::OriginalArray:
 421         return "OriginalArray";
 422     case Array::NonArray:
 423         return "NonArray";
 424     case Array::PossiblyArray:
 425         return "PossiblyArray";
 426     default:
 427         return "Unknown!";
 428     }
 429 }
 430
 431 const char* arraySpeculationToString(Array::Speculation speculation)
 432 {
 433     switch (speculation) {
 434     case Array::SaneChain:
 435         return "SaneChain";
 436     case Array::InBounds:
 437         return "InBounds";
 438     case Array::ToHole:
 439         return "ToHole";
 440     case Array::OutOfBounds:
 441         return "OutOfBounds";
 442     default:
 443         return "Unknown!";
 444     }
 445 }
 446
 447 const char* arrayConversionToString(Array::Conversion conversion)
 448 {
 449     switch (conversion) {
 450     case Array::AsIs:
 451         return "AsIs";
 452     case Array::Convert:
 453         return "Convert";
 454     case Array::RageConvert:
 455         return "RageConvert";
 456     default:
 457         return "Unknown!";
 458     }
 459 }
 460
 461 void ArrayMode::dump(PrintStream& out) const
 462 {
 463     out.print(type(), arrayClass(), speculation(), conversion());
 464 }
 465
 466 } } // namespace JSC::DFG
 467
 468 namespace WTF {
 469
 470 void printInternal(PrintStream& out, JSC::DFG::Array::Type type)
 471 {
 472     out.print(JSC::DFG::arrayTypeToString(type));
 473 }
 474
 475 void printInternal(PrintStream& out, JSC::DFG::Array::Class arrayClass)
 476 {
 477     out.print(JSC::DFG::arrayClassToString(arrayClass));
 478 }
 479
 480 void printInternal(PrintStream& out, JSC::DFG::Array::Speculation speculation)
 481 {
 482     out.print(JSC::DFG::arraySpeculationToString(speculation));
 483 }
 484
 485 void printInternal(PrintStream& out, JSC::DFG::Array::Conversion conversion)
 486 {
 487     out.print(JSC::DFG::arrayConversionToString(conversion));
 488 }
 489
 490 } // namespace WTF
 491
 492 #endif // ENABLE(DFG_JIT)
 493