Source/JavaScriptCore/dfg/DFGPredictionPropagationPhase.cpp

   1 /*
   2  * Copyright (C) 2011-2017 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 "DFGPredictionPropagationPhase.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGGraph.h"
  32 #include "DFGPhase.h"
  33 #include "JSCInlines.h"
  34
  35 namespace JSC { namespace DFG {
  36
  37 namespace {
  38
  39 bool verboseFixPointLoops = false;
  40
  41 class PredictionPropagationPhase : public Phase {
  42 public:
  43     PredictionPropagationPhase(Graph& graph)
  44         : Phase(graph, "prediction propagation")
  45     {
  46     }
  47
  48     bool run()
  49     {
  50         ASSERT(m_graph.m_form == ThreadedCPS);
  51         ASSERT(m_graph.m_unificationState == GloballyUnified);
  52
  53         propagateThroughArgumentPositions();
  54
  55         processInvariants();
  56
  57         m_pass = PrimaryPass;
  58         propagateToFixpoint();
  59
  60         m_pass = RareCasePass;
  61         propagateToFixpoint();
  62
  63         m_pass = DoubleVotingPass;
  64         unsigned counter = 0;
  65         do {
  66             if (verboseFixPointLoops)
  67                 ++counter;
  68
  69             m_changed = false;
  70             doRoundOfDoubleVoting();
  71             if (!m_changed)
  72                 break;
  73             m_changed = false;
  74             propagateForward();
  75         } while (m_changed);
  76
  77         if (verboseFixPointLoops)
  78             dataLog("Iterated ", counter, " times in double voting fixpoint.\n");
  79
  80         return true;
  81     }
  82
  83 private:
  84     void propagateToFixpoint()
  85     {
  86         unsigned counter = 0;
  87         do {
  88             if (verboseFixPointLoops)
  89                 ++counter;
  90
  91             m_changed = false;
  92
  93             // Forward propagation is near-optimal for both topologically-sorted and
  94             // DFS-sorted code.
  95             propagateForward();
  96             if (!m_changed)
  97                 break;
  98
  99             // Backward propagation reduces the likelihood that pathological code will
 100             // cause slowness. Loops (especially nested ones) resemble backward flow.
 101             // This pass captures two cases: (1) it detects if the forward fixpoint
 102             // found a sound solution and (2) short-circuits backward flow.
 103             m_changed = false;
 104             propagateBackward();
 105         } while (m_changed);
 106
 107         if (verboseFixPointLoops)
 108             dataLog("Iterated ", counter, " times in propagateToFixpoint.\n");
 109     }
 110
 111     bool setPrediction(SpeculatedType prediction)
 112     {
 113         ASSERT(m_currentNode->hasResult());
 114
 115         // setPrediction() is used when we know that there is no way that we can change
 116         // our minds about what the prediction is going to be. There is no semantic
 117         // difference between setPrediction() and mergeSpeculation() other than the
 118         // increased checking to validate this property.
 119         ASSERT(m_currentNode->prediction() == SpecNone || m_currentNode->prediction() == prediction);
 120
 121         return m_currentNode->predict(prediction);
 122     }
 123
 124     bool mergePrediction(SpeculatedType prediction)
 125     {
 126         ASSERT(m_currentNode->hasResult());
 127
 128         return m_currentNode->predict(prediction);
 129     }
 130
 131     SpeculatedType speculatedDoubleTypeForPrediction(SpeculatedType value)
 132     {
 133         SpeculatedType result = SpecDoubleReal;
 134         if (value & SpecDoubleImpureNaN)
 135             result |= SpecDoubleImpureNaN;
 136         if (value & SpecDoublePureNaN)
 137             result |= SpecDoublePureNaN;
 138         if (!isFullNumberOrBooleanSpeculation(value))
 139             result |= SpecDoublePureNaN;
 140         return result;
 141     }
 142
 143     SpeculatedType speculatedDoubleTypeForPredictions(SpeculatedType left, SpeculatedType right)
 144     {
 145         return speculatedDoubleTypeForPrediction(mergeSpeculations(left, right));
 146     }
 147
 148     void propagate(Node* node)
 149     {
 150         NodeType op = node->op();
 151
 152         bool changed = false;
 153
 154         switch (op) {
 155         case GetLocal: {
 156             VariableAccessData* variable = node->variableAccessData();
 157             SpeculatedType prediction = variable->prediction();
 158             if (!variable->couldRepresentInt52() && (prediction & SpecInt52Only))
 159                 prediction = (prediction | SpecAnyIntAsDouble) & ~SpecInt52Only;
 160             if (prediction)
 161                 changed |= mergePrediction(prediction);
 162             break;
 163         }
 164
 165         case SetLocal: {
 166             VariableAccessData* variableAccessData = node->variableAccessData();
 167             changed |= variableAccessData->predict(node->child1()->prediction());
 168             break;
 169         }
 170
 171         case UInt32ToNumber: {
 172             if (node->canSpeculateInt32(m_pass))
 173                 changed |= mergePrediction(SpecInt32Only);
 174             else if (enableInt52())
 175                 changed |= mergePrediction(SpecAnyInt);
 176             else
 177                 changed |= mergePrediction(SpecBytecodeNumber);
 178             break;
 179         }
 180
 181         case ValueAdd: {
 182             SpeculatedType left = node->child1()->prediction();
 183             SpeculatedType right = node->child2()->prediction();
 184
 185             if (left && right) {
 186                 if (isFullNumberOrBooleanSpeculationExpectingDefined(left)
 187                     && isFullNumberOrBooleanSpeculationExpectingDefined(right)) {
 188                     if (m_graph.addSpeculationMode(node, m_pass) != DontSpeculateInt32)
 189                         changed |= mergePrediction(SpecInt32Only);
 190                     else if (m_graph.addShouldSpeculateAnyInt(node))
 191                         changed |= mergePrediction(SpecInt52Only);
 192                     else
 193                         changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
 194                 } else if (isStringOrStringObjectSpeculation(left) || isStringOrStringObjectSpeculation(right)) {
 195                     // left or right is definitely something other than a number.
 196                     changed |= mergePrediction(SpecString);
 197                 } else {
 198                     changed |= mergePrediction(SpecInt32Only);
 199                     if (node->mayHaveDoubleResult())
 200                         changed |= mergePrediction(SpecBytecodeDouble);
 201                     if (node->mayHaveNonNumberResult())
 202                         changed |= mergePrediction(SpecString);
 203                 }
 204             }
 205             break;
 206         }
 207
 208         case ArithAdd: {
 209             SpeculatedType left = node->child1()->prediction();
 210             SpeculatedType right = node->child2()->prediction();
 211
 212             if (left && right) {
 213                 if (m_graph.addSpeculationMode(node, m_pass) != DontSpeculateInt32)
 214                     changed |= mergePrediction(SpecInt32Only);
 215                 else if (m_graph.addShouldSpeculateAnyInt(node))
 216                     changed |= mergePrediction(SpecInt52Only);
 217                 else if (isFullNumberOrBooleanSpeculation(left) && isFullNumberOrBooleanSpeculation(right))
 218                     changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
 219                 else if (node->mayHaveNonIntResult() || (left & SpecBytecodeDouble) || (right & SpecBytecodeDouble))
 220                     changed |= mergePrediction(SpecInt32Only | SpecBytecodeDouble);
 221                 else
 222                     changed |= mergePrediction(SpecInt32Only);
 223             }
 224             break;
 225         }
 226
 227         case ArithSub: {
 228             SpeculatedType left = node->child1()->prediction();
 229             SpeculatedType right = node->child2()->prediction();
 230
 231             if (left && right) {
 232                 if (isFullNumberOrBooleanSpeculationExpectingDefined(left)
 233                     && isFullNumberOrBooleanSpeculationExpectingDefined(right)) {
 234                     if (m_graph.addSpeculationMode(node, m_pass) != DontSpeculateInt32)
 235                         changed |= mergePrediction(SpecInt32Only);
 236                     else if (m_graph.addShouldSpeculateAnyInt(node))
 237                         changed |= mergePrediction(SpecInt52Only);
 238                     else
 239                         changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
 240                 } else if (node->mayHaveNonIntResult() || (left & SpecBytecodeDouble) || (right & SpecBytecodeDouble))
 241                     changed |= mergePrediction(SpecInt32Only | SpecBytecodeDouble);
 242                 else
 243                     changed |= mergePrediction(SpecInt32Only);
 244             }
 245             break;
 246         }
 247
 248         case ArithNegate: {
 249             SpeculatedType prediction = node->child1()->prediction();
 250             if (prediction) {
 251                 if (isInt32OrBooleanSpeculation(prediction) && node->canSpeculateInt32(m_pass))
 252                     changed |= mergePrediction(SpecInt32Only);
 253                 else if (m_graph.unaryArithShouldSpeculateAnyInt(node, m_pass))
 254                     changed |= mergePrediction(SpecInt52Only);
 255                 else if (isBytecodeNumberSpeculation(prediction))
 256                     changed |= mergePrediction(speculatedDoubleTypeForPrediction(node->child1()->prediction()));
 257                 else {
 258                     changed |= mergePrediction(SpecInt32Only);
 259                     if (node->mayHaveDoubleResult())
 260                         changed |= mergePrediction(SpecBytecodeDouble);
 261                 }
 262             }
 263             break;
 264         }
 265         case ArithMin:
 266         case ArithMax: {
 267             SpeculatedType left = node->child1()->prediction();
 268             SpeculatedType right = node->child2()->prediction();
 269
 270             if (left && right) {
 271                 if (Node::shouldSpeculateInt32OrBooleanForArithmetic(node->child1().node(), node->child2().node())
 272                     && node->canSpeculateInt32(m_pass))
 273                     changed |= mergePrediction(SpecInt32Only);
 274                 else
 275                     changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
 276             }
 277             break;
 278         }
 279
 280         case ArithMul: {
 281             SpeculatedType left = node->child1()->prediction();
 282             SpeculatedType right = node->child2()->prediction();
 283
 284             if (left && right) {
 285                 // FIXME: We're currently relying on prediction propagation and backwards propagation
 286                 // whenever we can, and only falling back on result flags if that fails. And the result
 287                 // flags logic doesn't know how to use backwards propagation. We should get rid of the
 288                 // prediction propagation logic and rely solely on the result type.
 289                 if (isFullNumberOrBooleanSpeculationExpectingDefined(left)
 290                     && isFullNumberOrBooleanSpeculationExpectingDefined(right)) {
 291                     if (m_graph.binaryArithShouldSpeculateInt32(node, m_pass))
 292                         changed |= mergePrediction(SpecInt32Only);
 293                     else if (m_graph.binaryArithShouldSpeculateAnyInt(node, m_pass))
 294                         changed |= mergePrediction(SpecInt52Only);
 295                     else
 296                         changed |= mergePrediction(speculatedDoubleTypeForPredictions(left, right));
 297                 } else {
 298                     if (node->mayHaveNonIntResult()
 299                         || (left & SpecBytecodeDouble)
 300                         || (right & SpecBytecodeDouble))
 301                         changed |= mergePrediction(SpecInt32Only | SpecBytecodeDouble);
 302                     else
 303                         changed |= mergePrediction(SpecInt32Only);
 304                 }
 305             }
 306             break;
 307         }
 308
 309         case ArithDiv:
 310         case ArithMod: {
 311             SpeculatedType left = node->child1()->prediction();
 312             SpeculatedType right = node->child2()->prediction();
 313
 314             if (left && right) {
 315                 if (isFullNumberOrBooleanSpeculationExpectingDefined(left)
 316                     && isFullNumberOrBooleanSpeculationExpectingDefined(right)) {
 317                     if (m_graph.binaryArithShouldSpeculateInt32(node, m_pass))
 318                         changed |= mergePrediction(SpecInt32Only);
 319                     else
 320                         changed |= mergePrediction(SpecBytecodeDouble);
 321                 } else
 322                     changed |= mergePrediction(SpecInt32Only | SpecBytecodeDouble);
 323             }
 324             break;
 325         }
 326
 327         case ArithAbs: {
 328             SpeculatedType childPrediction = node->child1()->prediction();
 329             if (isInt32OrBooleanSpeculation(childPrediction)
 330                 && node->canSpeculateInt32(m_pass))
 331                 changed |= mergePrediction(SpecInt32Only);
 332             else
 333                 changed |= mergePrediction(SpecBytecodeDouble);
 334             break;
 335         }
 336
 337         case GetByVal:
 338         case AtomicsAdd:
 339         case AtomicsAnd:
 340         case AtomicsCompareExchange:
 341         case AtomicsExchange:
 342         case AtomicsLoad:
 343         case AtomicsOr:
 344         case AtomicsStore:
 345         case AtomicsSub:
 346         case AtomicsXor: {
 347             Edge child1 = m_graph.child(node, 0);
 348             if (!child1->prediction())
 349                 break;
 350
 351             Edge child2 = m_graph.child(node, 1);
 352             ArrayMode arrayMode = node->arrayMode().refine(
 353                 m_graph, node,
 354                 child1->prediction(),
 355                 child2->prediction(),
 356                 SpecNone);
 357
 358             switch (arrayMode.type()) {
 359             case Array::Int32:
 360                 if (arrayMode.isOutOfBounds())
 361                     changed |= mergePrediction(node->getHeapPrediction() | SpecInt32Only);
 362                 else
 363                     changed |= mergePrediction(SpecInt32Only);
 364                 break;
 365             case Array::Double:
 366                 if (arrayMode.isOutOfBounds())
 367                     changed |= mergePrediction(node->getHeapPrediction() | SpecDoubleReal);
 368                 else if (node->getHeapPrediction() & SpecNonIntAsDouble)
 369                     changed |= mergePrediction(SpecDoubleReal);
 370                 else
 371                     changed |= mergePrediction(SpecAnyIntAsDouble);
 372                 break;
 373             case Array::Float32Array:
 374             case Array::Float64Array:
 375                 changed |= mergePrediction(SpecFullDouble);
 376                 break;
 377             case Array::Uint32Array:
 378                 if (isInt32SpeculationForArithmetic(node->getHeapPrediction()) && node->op() == GetByVal)
 379                     changed |= mergePrediction(SpecInt32Only);
 380                 else if (enableInt52())
 381                     changed |= mergePrediction(SpecAnyInt);
 382                 else
 383                     changed |= mergePrediction(SpecInt32Only | SpecAnyIntAsDouble);
 384                 break;
 385             case Array::Int8Array:
 386             case Array::Uint8Array:
 387             case Array::Int16Array:
 388             case Array::Uint16Array:
 389             case Array::Int32Array:
 390                 changed |= mergePrediction(SpecInt32Only);
 391                 break;
 392             default:
 393                 changed |= mergePrediction(node->getHeapPrediction());
 394                 break;
 395             }
 396             break;
 397         }
 398
 399         case ToThis: {
 400             // ToThis in methods for primitive types should speculate primitive types in strict mode.
 401             ECMAMode ecmaMode = m_graph.executableFor(node->origin.semantic)->isStrictMode() ? StrictMode : NotStrictMode;
 402             if (ecmaMode == StrictMode) {
 403                 if (node->child1()->shouldSpeculateBoolean()) {
 404                     changed |= mergePrediction(SpecBoolean);
 405                     break;
 406                 }
 407
 408                 if (node->child1()->shouldSpeculateInt32()) {
 409                     changed |= mergePrediction(SpecInt32Only);
 410                     break;
 411                 }
 412
 413                 if (enableInt52() && node->child1()->shouldSpeculateAnyInt()) {
 414                     changed |= mergePrediction(SpecAnyInt);
 415                     break;
 416                 }
 417
 418                 if (node->child1()->shouldSpeculateNumber()) {
 419                     changed |= mergePrediction(SpecBytecodeNumber);
 420                     break;
 421                 }
 422
 423                 if (node->child1()->shouldSpeculateSymbol()) {
 424                     changed |= mergePrediction(SpecSymbol);
 425                     break;
 426                 }
 427
 428                 if (node->child1()->shouldSpeculateStringIdent()) {
 429                     changed |= mergePrediction(SpecStringIdent);
 430                     break;
 431                 }
 432
 433                 if (node->child1()->shouldSpeculateString()) {
 434                     changed |= mergePrediction(SpecString);
 435                     break;
 436                 }
 437             } else {
 438                 if (node->child1()->shouldSpeculateString()) {
 439                     changed |= mergePrediction(SpecStringObject);
 440                     break;
 441                 }
 442             }
 443
 444             SpeculatedType prediction = node->child1()->prediction();
 445             if (prediction) {
 446                 if (prediction & ~SpecObject) {
 447                     // Wrapper objects are created only in sloppy mode.
 448                     if (ecmaMode != StrictMode) {
 449                         prediction &= SpecObject;
 450                         prediction = mergeSpeculations(prediction, SpecObjectOther);
 451                     }
 452                 }
 453                 changed |= mergePrediction(prediction);
 454             }
 455             break;
 456         }
 457
 458         case ToPrimitive: {
 459             SpeculatedType child = node->child1()->prediction();
 460             if (child)
 461                 changed |= mergePrediction(resultOfToPrimitive(child));
 462             break;
 463         }
 464
 465         default:
 466             break;
 467         }
 468
 469         m_changed |= changed;
 470     }
 471
 472     void propagateForward()
 473     {
 474         for (Node* node : m_dependentNodes) {
 475             m_currentNode = node;
 476             propagate(m_currentNode);
 477         }
 478     }
 479
 480     void propagateBackward()
 481     {
 482         for (unsigned i = m_dependentNodes.size(); i--;) {
 483             m_currentNode = m_dependentNodes[i];
 484             propagate(m_currentNode);
 485         }
 486     }
 487
 488     void doDoubleVoting(Node* node, float weight)
 489     {
 490         // Loop pre-headers created by OSR entrypoint creation may have NaN weight to indicate
 491         // that we actually don't know they weight. Assume that they execute once. This turns
 492         // out to be an OK assumption since the pre-header doesn't have any meaningful code.
 493         if (weight != weight)
 494             weight = 1;
 495
 496         switch (node->op()) {
 497         case ValueAdd:
 498         case ArithAdd:
 499         case ArithSub: {
 500             SpeculatedType left = node->child1()->prediction();
 501             SpeculatedType right = node->child2()->prediction();
 502
 503             DoubleBallot ballot;
 504
 505             if (isFullNumberSpeculation(left)
 506                 && isFullNumberSpeculation(right)
 507                 && !m_graph.addShouldSpeculateInt32(node, m_pass)
 508                 && !m_graph.addShouldSpeculateAnyInt(node))
 509                 ballot = VoteDouble;
 510             else
 511                 ballot = VoteValue;
 512
 513             m_graph.voteNode(node->child1(), ballot, weight);
 514             m_graph.voteNode(node->child2(), ballot, weight);
 515             break;
 516         }
 517
 518         case ArithMul: {
 519             SpeculatedType left = node->child1()->prediction();
 520             SpeculatedType right = node->child2()->prediction();
 521
 522             DoubleBallot ballot;
 523
 524             if (isFullNumberSpeculation(left)
 525                 && isFullNumberSpeculation(right)
 526                 && !m_graph.binaryArithShouldSpeculateInt32(node, m_pass)
 527                 && !m_graph.binaryArithShouldSpeculateAnyInt(node, m_pass))
 528                 ballot = VoteDouble;
 529             else
 530                 ballot = VoteValue;
 531
 532             m_graph.voteNode(node->child1(), ballot, weight);
 533             m_graph.voteNode(node->child2(), ballot, weight);
 534             break;
 535         }
 536
 537         case ArithMin:
 538         case ArithMax:
 539         case ArithMod:
 540         case ArithDiv: {
 541             SpeculatedType left = node->child1()->prediction();
 542             SpeculatedType right = node->child2()->prediction();
 543
 544             DoubleBallot ballot;
 545
 546             if (isFullNumberSpeculation(left)
 547                 && isFullNumberSpeculation(right)
 548                 && !m_graph.binaryArithShouldSpeculateInt32(node, m_pass))
 549                 ballot = VoteDouble;
 550             else
 551                 ballot = VoteValue;
 552
 553             m_graph.voteNode(node->child1(), ballot, weight);
 554             m_graph.voteNode(node->child2(), ballot, weight);
 555             break;
 556         }
 557
 558         case ArithAbs:
 559             DoubleBallot ballot;
 560             if (node->child1()->shouldSpeculateNumber()
 561                 && !m_graph.unaryArithShouldSpeculateInt32(node, m_pass))
 562                 ballot = VoteDouble;
 563             else
 564                 ballot = VoteValue;
 565
 566             m_graph.voteNode(node->child1(), ballot, weight);
 567             break;
 568
 569         case ArithSqrt:
 570         case ArithUnary:
 571             if (node->child1()->shouldSpeculateNumber())
 572                 m_graph.voteNode(node->child1(), VoteDouble, weight);
 573             else
 574                 m_graph.voteNode(node->child1(), VoteValue, weight);
 575             break;
 576
 577         case SetLocal: {
 578             SpeculatedType prediction = node->child1()->prediction();
 579             if (isDoubleSpeculation(prediction))
 580                 node->variableAccessData()->vote(VoteDouble, weight);
 581             else if (!isFullNumberSpeculation(prediction)
 582                 || isInt32Speculation(prediction) || isAnyIntSpeculation(prediction))
 583                 node->variableAccessData()->vote(VoteValue, weight);
 584             break;
 585         }
 586
 587         case PutByValDirect:
 588         case PutByVal:
 589         case PutByValAlias: {
 590             Edge child1 = m_graph.varArgChild(node, 0);
 591             Edge child2 = m_graph.varArgChild(node, 1);
 592             Edge child3 = m_graph.varArgChild(node, 2);
 593             m_graph.voteNode(child1, VoteValue, weight);
 594             m_graph.voteNode(child2, VoteValue, weight);
 595             switch (node->arrayMode().type()) {
 596             case Array::Double:
 597                 m_graph.voteNode(child3, VoteDouble, weight);
 598                 break;
 599             default:
 600                 m_graph.voteNode(child3, VoteValue, weight);
 601                 break;
 602             }
 603             break;
 604         }
 605
 606         case MovHint:
 607             // Ignore these since they have no effect on in-DFG execution.
 608             break;
 609
 610         default:
 611             m_graph.voteChildren(node, VoteValue, weight);
 612             break;
 613         }
 614     }
 615
 616     void doRoundOfDoubleVoting()
 617     {
 618         for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i)
 619             m_graph.m_variableAccessData[i].find()->clearVotes();
 620         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
 621             BasicBlock* block = m_graph.block(blockIndex);
 622             if (!block)
 623                 continue;
 624             ASSERT(block->isReachable);
 625             for (unsigned i = 0; i < block->size(); ++i) {
 626                 m_currentNode = block->at(i);
 627                 doDoubleVoting(m_currentNode, block->executionCount);
 628             }
 629         }
 630         for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i) {
 631             VariableAccessData* variableAccessData = &m_graph.m_variableAccessData[i];
 632             if (!variableAccessData->isRoot())
 633                 continue;
 634             m_changed |= variableAccessData->tallyVotesForShouldUseDoubleFormat();
 635         }
 636         propagateThroughArgumentPositions();
 637         for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i) {
 638             VariableAccessData* variableAccessData = &m_graph.m_variableAccessData[i];
 639             if (!variableAccessData->isRoot())
 640                 continue;
 641             m_changed |= variableAccessData->makePredictionForDoubleFormat();
 642         }
 643     }
 644
 645     void propagateThroughArgumentPositions()
 646     {
 647         for (unsigned i = 0; i < m_graph.m_argumentPositions.size(); ++i)
 648             m_changed |= m_graph.m_argumentPositions[i].mergeArgumentPredictionAwareness();
 649     }
 650
 651     // Sets any predictions that do not depends on other nodes.
 652     void processInvariants()
 653     {
 654         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
 655             for (Node* node : *block) {
 656                 m_currentNode = node;
 657                 processInvariantsForNode();
 658             }
 659         }
 660     }
 661
 662     void processInvariantsForNode()
 663     {
 664         switch (m_currentNode->op()) {
 665         case JSConstant: {
 666             SpeculatedType type = speculationFromValue(m_currentNode->asJSValue());
 667             if (type == SpecAnyIntAsDouble && enableInt52())
 668                 type = SpecInt52Only;
 669             setPrediction(type);
 670             break;
 671         }
 672         case DoubleConstant: {
 673             SpeculatedType type = speculationFromValue(m_currentNode->asJSValue());
 674             setPrediction(type);
 675             break;
 676         }
 677         case BitAnd:
 678         case BitOr:
 679         case BitXor:
 680         case BitRShift:
 681         case BitLShift:
 682         case BitURShift:
 683         case ArithIMul:
 684         case ArithClz32: {
 685             setPrediction(SpecInt32Only);
 686             break;
 687         }
 688
 689         case ArrayPop:
 690         case ArrayPush:
 691         case RegExpExec:
 692         case RegExpTest:
 693         case StringReplace:
 694         case StringReplaceRegExp:
 695         case GetById:
 696         case GetByIdFlush:
 697         case GetByIdWithThis:
 698         case TryGetById:
 699         case GetByValWithThis:
 700         case GetByOffset:
 701         case MultiGetByOffset:
 702         case GetDirectPname:
 703         case Call:
 704         case DirectCall:
 705         case TailCallInlinedCaller:
 706         case DirectTailCallInlinedCaller:
 707         case Construct:
 708         case DirectConstruct:
 709         case CallVarargs:
 710         case CallEval:
 711         case TailCallVarargsInlinedCaller:
 712         case ConstructVarargs:
 713         case CallForwardVarargs:
 714         case ConstructForwardVarargs:
 715         case TailCallForwardVarargsInlinedCaller:
 716         case GetGlobalVar:
 717         case GetGlobalLexicalVariable:
 718         case GetClosureVar:
 719         case GetFromArguments:
 720         case LoadKeyFromMapBucket:
 721         case LoadValueFromMapBucket:
 722         case ToNumber:
 723         case ToObject:
 724         case CallObjectConstructor:
 725         case GetArgument:
 726         case CallDOMGetter:
 727         case GetDynamicVar:
 728         case WeakMapGet:
 729         case GetPrototypeOf: {
 730             setPrediction(m_currentNode->getHeapPrediction());
 731             break;
 732         }
 733
 734         case ResolveScopeForHoistingFuncDeclInEval: {
 735             setPrediction(SpecBytecodeTop);
 736             break;
 737         }
 738
 739         case GetGetterSetterByOffset:
 740         case GetExecutable: {
 741             setPrediction(SpecCellOther);
 742             break;
 743         }
 744
 745         case GetGetter:
 746         case GetSetter:
 747         case GetCallee:
 748         case NewFunction:
 749         case NewGeneratorFunction:
 750         case NewAsyncGeneratorFunction:
 751         case NewAsyncFunction: {
 752             setPrediction(SpecFunction);
 753             break;
 754         }
 755
 756         case GetArgumentCountIncludingThis: {
 757             setPrediction(SpecInt32Only);
 758             break;
 759         }
 760
 761         case MapHash:
 762             setPrediction(SpecInt32Only);
 763             break;
 764
 765         case GetMapBucket:
 766         case GetMapBucketHead:
 767         case GetMapBucketNext:
 768             setPrediction(SpecCellOther);
 769             break;
 770
 771         case GetRestLength:
 772         case ArrayIndexOf: {
 773             setPrediction(SpecInt32Only);
 774             break;
 775         }
 776
 777         case GetTypedArrayByteOffset:
 778         case GetArrayLength:
 779         case GetVectorLength: {
 780             setPrediction(SpecInt32Only);
 781             break;
 782         }
 783
 784         case StringCharCodeAt: {
 785             setPrediction(SpecInt32Only);
 786             break;
 787         }
 788
 789         case StringSlice:
 790         case ToLowerCase:
 791             setPrediction(SpecString);
 792             break;
 793
 794         case ArithPow:
 795         case ArithSqrt:
 796         case ArithFRound:
 797         case ArithUnary: {
 798             setPrediction(SpecBytecodeDouble);
 799             break;
 800         }
 801
 802         case ArithRound:
 803         case ArithFloor:
 804         case ArithCeil:
 805         case ArithTrunc: {
 806             if (isInt32OrBooleanSpeculation(m_currentNode->getHeapPrediction())
 807                 && m_graph.roundShouldSpeculateInt32(m_currentNode, m_pass))
 808                 setPrediction(SpecInt32Only);
 809             else
 810                 setPrediction(SpecBytecodeDouble);
 811             break;
 812         }
 813
 814         case ArithRandom: {
 815             setPrediction(SpecDoubleReal);
 816             break;
 817         }
 818         case DeleteByVal:
 819         case DeleteById:
 820         case LogicalNot:
 821         case CompareLess:
 822         case CompareLessEq:
 823         case CompareGreater:
 824         case CompareGreaterEq:
 825         case CompareBelow:
 826         case CompareBelowEq:
 827         case CompareEq:
 828         case CompareStrictEq:
 829         case CompareEqPtr:
 830         case OverridesHasInstance:
 831         case InstanceOf:
 832         case InstanceOfCustom:
 833         case IsEmpty:
 834         case IsUndefined:
 835         case IsBoolean:
 836         case IsNumber:
 837         case IsObject:
 838         case IsObjectOrNull:
 839         case IsFunction:
 840         case IsCellWithType:
 841         case IsTypedArrayView: {
 842             setPrediction(SpecBoolean);
 843             break;
 844         }
 845
 846         case TypeOf: {
 847             setPrediction(SpecStringIdent);
 848             break;
 849         }
 850         case GetButterfly:
 851         case GetButterflyWithoutCaging:
 852         case GetIndexedPropertyStorage:
 853         case AllocatePropertyStorage:
 854         case ReallocatePropertyStorage: {
 855             setPrediction(SpecOther);
 856             break;
 857         }
 858
 859         case CheckSubClass:
 860             break;
 861
 862         case SkipScope:
 863         case GetGlobalObject: {
 864             setPrediction(SpecObjectOther);
 865             break;
 866         }
 867
 868         case GetGlobalThis:
 869             setPrediction(SpecObject);
 870             break;
 871
 872         case ResolveScope: {
 873             setPrediction(SpecObjectOther);
 874             break;
 875         }
 876
 877         case CreateThis:
 878         case NewObject: {
 879             setPrediction(SpecFinalObject);
 880             break;
 881         }
 882
 883         case ArraySlice:
 884         case NewArrayWithSpread:
 885         case NewArray:
 886         case NewArrayWithSize:
 887         case CreateRest:
 888         case NewArrayBuffer: {
 889             setPrediction(SpecArray);
 890             break;
 891         }
 892
 893         case Spread:
 894             setPrediction(SpecCellOther);
 895             break;
 896
 897         case NewTypedArray: {
 898             setPrediction(speculationFromTypedArrayType(m_currentNode->typedArrayType()));
 899             break;
 900         }
 901
 902         case NewRegexp: {
 903             setPrediction(SpecRegExpObject);
 904             break;
 905         }
 906
 907         case PushWithScope:
 908         case CreateActivation: {
 909             setPrediction(SpecObjectOther);
 910             break;
 911         }
 912
 913         case StringFromCharCode: {
 914             setPrediction(SpecString);
 915             m_currentNode->child1()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsInt);
 916             break;
 917         }
 918         case StringCharAt:
 919         case CallStringConstructor:
 920         case ToString:
 921         case NumberToStringWithRadix:
 922         case NumberToStringWithValidRadixConstant:
 923         case MakeRope:
 924         case StrCat: {
 925             setPrediction(SpecString);
 926             break;
 927         }
 928         case NewStringObject: {
 929             setPrediction(SpecStringObject);
 930             break;
 931         }
 932
 933         case CreateDirectArguments: {
 934             setPrediction(SpecDirectArguments);
 935             break;
 936         }
 937
 938         case CreateScopedArguments: {
 939             setPrediction(SpecScopedArguments);
 940             break;
 941         }
 942
 943         case CreateClonedArguments: {
 944             setPrediction(SpecObjectOther);
 945             break;
 946         }
 947
 948         case FiatInt52: {
 949             RELEASE_ASSERT(enableInt52());
 950             setPrediction(SpecAnyInt);
 951             break;
 952         }
 953
 954         case GetScope:
 955             setPrediction(SpecObjectOther);
 956             break;
 957
 958         case In:
 959             setPrediction(SpecBoolean);
 960             break;
 961
 962         case HasOwnProperty:
 963             setPrediction(SpecBoolean);
 964             break;
 965
 966         case GetEnumerableLength: {
 967             setPrediction(SpecInt32Only);
 968             break;
 969         }
 970         case HasGenericProperty:
 971         case HasStructureProperty:
 972         case HasIndexedProperty: {
 973             setPrediction(SpecBoolean);
 974             break;
 975         }
 976         case GetPropertyEnumerator: {
 977             setPrediction(SpecCell);
 978             break;
 979         }
 980         case GetEnumeratorStructurePname: {
 981             setPrediction(SpecCell | SpecOther);
 982             break;
 983         }
 984         case GetEnumeratorGenericPname: {
 985             setPrediction(SpecCell | SpecOther);
 986             break;
 987         }
 988         case ToIndexString: {
 989             setPrediction(SpecString);
 990             break;
 991         }
 992         case ParseInt: {
 993             // We expect this node to almost always produce an int32. However,
 994             // it's possible it produces NaN or integers out of int32 range. We
 995             // rely on the heap prediction since the parseInt() call profiled
 996             // its result.
 997             setPrediction(m_currentNode->getHeapPrediction());
 998             break;
 999         }
1000
1001         case IdentityWithProfile: {
1002             setPrediction(m_currentNode->getForcedPrediction());
1003             break;
1004         }
1005
1006         case ExtractCatchLocal: {
1007             setPrediction(m_currentNode->catchLocalPrediction());
1008             break;
1009         }
1010
1011         case GetLocal:
1012         case SetLocal:
1013         case UInt32ToNumber:
1014         case ValueAdd:
1015         case ArithAdd:
1016         case ArithSub:
1017         case ArithNegate:
1018         case ArithMin:
1019         case ArithMax:
1020         case ArithMul:
1021         case ArithDiv:
1022         case ArithMod:
1023         case ArithAbs:
1024         case GetByVal:
1025         case ToThis:
1026         case ToPrimitive:
1027         case AtomicsAdd:
1028         case AtomicsAnd:
1029         case AtomicsCompareExchange:
1030         case AtomicsExchange:
1031         case AtomicsLoad:
1032         case AtomicsOr:
1033         case AtomicsStore:
1034         case AtomicsSub:
1035         case AtomicsXor: {
1036             m_dependentNodes.append(m_currentNode);
1037             break;
1038         }
1039
1040         case AtomicsIsLockFree: {
1041             setPrediction(SpecBoolean);
1042             break;
1043         }
1044
1045         case CPUIntrinsic: {
1046             if (m_currentNode->intrinsic() == CPURdtscIntrinsic)
1047                 setPrediction(SpecInt32Only);
1048             else
1049                 setPrediction(SpecOther);
1050             break;
1051         }
1052
1053         case PutByValAlias:
1054         case DoubleAsInt32:
1055         case CheckArray:
1056         case CheckTypeInfoFlags:
1057         case Arrayify:
1058         case ArrayifyToStructure:
1059         case CheckTierUpInLoop:
1060         case CheckTierUpAtReturn:
1061         case CheckTierUpAndOSREnter:
1062         case InvalidationPoint:
1063         case CheckInBounds:
1064         case ValueToInt32:
1065         case DoubleRep:
1066         case ValueRep:
1067         case Int52Rep:
1068         case Int52Constant:
1069         case Identity:
1070         case BooleanToNumber:
1071         case PhantomNewObject:
1072         case PhantomNewFunction:
1073         case PhantomNewGeneratorFunction:
1074         case PhantomNewAsyncGeneratorFunction:
1075         case PhantomNewAsyncFunction:
1076         case PhantomCreateActivation:
1077         case PhantomDirectArguments:
1078         case PhantomCreateRest:
1079         case PhantomSpread:
1080         case PhantomNewArrayWithSpread:
1081         case PhantomClonedArguments:
1082         case GetMyArgumentByVal:
1083         case GetMyArgumentByValOutOfBounds:
1084         case PutHint:
1085         case CheckStructureImmediate:
1086         case CheckStructureOrEmpty:
1087         case MaterializeNewObject:
1088         case MaterializeCreateActivation:
1089         case PutStack:
1090         case KillStack:
1091         case StoreBarrier:
1092         case FencedStoreBarrier:
1093         case GetStack:
1094         case GetRegExpObjectLastIndex:
1095         case SetRegExpObjectLastIndex:
1096         case RecordRegExpCachedResult:
1097         case LazyJSConstant:
1098         case CallDOM: {
1099             // This node should never be visible at this stage of compilation.
1100             DFG_CRASH(m_graph, m_currentNode, "Unexpected node during prediction propagation");
1101             break;
1102         }
1103
1104         case Phi:
1105             // Phis should not be visible here since we're iterating the all-but-Phi's
1106             // part of basic blocks.
1107             RELEASE_ASSERT_NOT_REACHED();
1108             break;
1109
1110         case EntrySwitch:
1111         case Upsilon:
1112             // These don't get inserted until we go into SSA.
1113             RELEASE_ASSERT_NOT_REACHED();
1114             break;
1115
1116 #ifndef NDEBUG
1117         // These get ignored because they don't return anything.
1118         case PutByValDirect:
1119         case PutByValWithThis:
1120         case PutByIdWithThis:
1121         case PutByVal:
1122         case PutClosureVar:
1123         case PutToArguments:
1124         case Return:
1125         case Throw:
1126         case ThrowStaticError:
1127         case TailCall:
1128         case DirectTailCall:
1129         case TailCallVarargs:
1130         case TailCallForwardVarargs:
1131         case PutById:
1132         case PutByIdFlush:
1133         case PutByIdDirect:
1134         case PutByOffset:
1135         case MultiPutByOffset:
1136         case PutGetterById:
1137         case PutSetterById:
1138         case PutGetterSetterById:
1139         case PutGetterByVal:
1140         case PutSetterByVal:
1141         case DefineDataProperty:
1142         case DefineAccessorProperty:
1143         case DFG::Jump:
1144         case Branch:
1145         case Switch:
1146         case ProfileType:
1147         case ProfileControlFlow:
1148         case ForceOSRExit:
1149         case SetArgument:
1150         case SetFunctionName:
1151         case CheckStructure:
1152         case CheckCell:
1153         case CheckNotEmpty:
1154         case CheckStringIdent:
1155         case CheckBadCell:
1156         case PutStructure:
1157         case Phantom:
1158         case Check:
1159         case PutGlobalVariable:
1160         case CheckTraps:
1161         case LogShadowChickenPrologue:
1162         case LogShadowChickenTail:
1163         case Unreachable:
1164         case LoopHint:
1165         case NotifyWrite:
1166         case ConstantStoragePointer:
1167         case MovHint:
1168         case ZombieHint:
1169         case ExitOK:
1170         case LoadVarargs:
1171         case ForwardVarargs:
1172         case PutDynamicVar:
1173         case NukeStructureAndSetButterfly:
1174         case InitializeEntrypointArguments:
1175         case SetAdd:
1176         case MapSet:
1177             break;
1178
1179         // This gets ignored because it only pretends to produce a value.
1180         case BottomValue:
1181             break;
1182
1183         // This gets ignored because it already has a prediction.
1184         case ExtractOSREntryLocal:
1185             break;
1186
1187         // These gets ignored because it doesn't do anything.
1188         case CountExecution:
1189         case SuperSamplerBegin:
1190         case SuperSamplerEnd:
1191         case PhantomLocal:
1192         case Flush:
1193             break;
1194
1195         case LastNodeType:
1196             RELEASE_ASSERT_NOT_REACHED();
1197             break;
1198 #else
1199         default:
1200             break;
1201 #endif
1202         }
1203     }
1204
1205     SpeculatedType resultOfToPrimitive(SpeculatedType type)
1206     {
1207         if (type & SpecObject) {
1208             // We try to be optimistic here about StringObjects since it's unlikely that
1209             // someone overrides the valueOf or toString methods.
1210             if (type & SpecStringObject && m_graph.canOptimizeStringObjectAccess(m_currentNode->origin.semantic))
1211                 return mergeSpeculations(type & ~SpecObject, SpecString);
1212
1213             return mergeSpeculations(type & ~SpecObject, SpecPrimitive);
1214         }
1215
1216         return type;
1217     }
1218
1219     Vector<Node*> m_dependentNodes;
1220     Node* m_currentNode;
1221     bool m_changed;
1222     PredictionPass m_pass; // We use different logic for considering predictions depending on how far along we are in propagation.
1223 };
1224
1225 } // Anonymous namespace.
1226
1227 bool performPredictionPropagation(Graph& graph)
1228 {
1229     return runPhase<PredictionPropagationPhase>(graph);
1230 }
1231
1232 } } // namespace JSC::DFG
1233
1234 #endif // ENABLE(DFG_JIT)
1235