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         case NormalizeMapKey: {
 466             SpeculatedType prediction = node->child1()->prediction();
 467             if (prediction)
 468                 changed |= mergePrediction(prediction);
 469             break;
 470         }
 471
 472         default:
 473             break;
 474         }
 475
 476         m_changed |= changed;
 477     }
 478
 479     void propagateForward()
 480     {
 481         for (Node* node : m_dependentNodes) {
 482             m_currentNode = node;
 483             propagate(m_currentNode);
 484         }
 485     }
 486
 487     void propagateBackward()
 488     {
 489         for (unsigned i = m_dependentNodes.size(); i--;) {
 490             m_currentNode = m_dependentNodes[i];
 491             propagate(m_currentNode);
 492         }
 493     }
 494
 495     void doDoubleVoting(Node* node, float weight)
 496     {
 497         // Loop pre-headers created by OSR entrypoint creation may have NaN weight to indicate
 498         // that we actually don't know they weight. Assume that they execute once. This turns
 499         // out to be an OK assumption since the pre-header doesn't have any meaningful code.
 500         if (weight != weight)
 501             weight = 1;
 502
 503         switch (node->op()) {
 504         case ValueAdd:
 505         case ArithAdd:
 506         case ArithSub: {
 507             SpeculatedType left = node->child1()->prediction();
 508             SpeculatedType right = node->child2()->prediction();
 509
 510             DoubleBallot ballot;
 511
 512             if (isFullNumberSpeculation(left)
 513                 && isFullNumberSpeculation(right)
 514                 && !m_graph.addShouldSpeculateInt32(node, m_pass)
 515                 && !m_graph.addShouldSpeculateAnyInt(node))
 516                 ballot = VoteDouble;
 517             else
 518                 ballot = VoteValue;
 519
 520             m_graph.voteNode(node->child1(), ballot, weight);
 521             m_graph.voteNode(node->child2(), ballot, weight);
 522             break;
 523         }
 524
 525         case ArithMul: {
 526             SpeculatedType left = node->child1()->prediction();
 527             SpeculatedType right = node->child2()->prediction();
 528
 529             DoubleBallot ballot;
 530
 531             if (isFullNumberSpeculation(left)
 532                 && isFullNumberSpeculation(right)
 533                 && !m_graph.binaryArithShouldSpeculateInt32(node, m_pass)
 534                 && !m_graph.binaryArithShouldSpeculateAnyInt(node, m_pass))
 535                 ballot = VoteDouble;
 536             else
 537                 ballot = VoteValue;
 538
 539             m_graph.voteNode(node->child1(), ballot, weight);
 540             m_graph.voteNode(node->child2(), ballot, weight);
 541             break;
 542         }
 543
 544         case ArithMin:
 545         case ArithMax:
 546         case ArithMod:
 547         case ArithDiv: {
 548             SpeculatedType left = node->child1()->prediction();
 549             SpeculatedType right = node->child2()->prediction();
 550
 551             DoubleBallot ballot;
 552
 553             if (isFullNumberSpeculation(left)
 554                 && isFullNumberSpeculation(right)
 555                 && !m_graph.binaryArithShouldSpeculateInt32(node, m_pass))
 556                 ballot = VoteDouble;
 557             else
 558                 ballot = VoteValue;
 559
 560             m_graph.voteNode(node->child1(), ballot, weight);
 561             m_graph.voteNode(node->child2(), ballot, weight);
 562             break;
 563         }
 564
 565         case ArithAbs:
 566             DoubleBallot ballot;
 567             if (node->child1()->shouldSpeculateNumber()
 568                 && !m_graph.unaryArithShouldSpeculateInt32(node, m_pass))
 569                 ballot = VoteDouble;
 570             else
 571                 ballot = VoteValue;
 572
 573             m_graph.voteNode(node->child1(), ballot, weight);
 574             break;
 575
 576         case ArithSqrt:
 577         case ArithUnary:
 578             if (node->child1()->shouldSpeculateNumber())
 579                 m_graph.voteNode(node->child1(), VoteDouble, weight);
 580             else
 581                 m_graph.voteNode(node->child1(), VoteValue, weight);
 582             break;
 583
 584         case SetLocal: {
 585             SpeculatedType prediction = node->child1()->prediction();
 586             if (isDoubleSpeculation(prediction))
 587                 node->variableAccessData()->vote(VoteDouble, weight);
 588             else if (!isFullNumberSpeculation(prediction)
 589                 || isInt32Speculation(prediction) || isAnyIntSpeculation(prediction))
 590                 node->variableAccessData()->vote(VoteValue, weight);
 591             break;
 592         }
 593
 594         case PutByValDirect:
 595         case PutByVal:
 596         case PutByValAlias: {
 597             Edge child1 = m_graph.varArgChild(node, 0);
 598             Edge child2 = m_graph.varArgChild(node, 1);
 599             Edge child3 = m_graph.varArgChild(node, 2);
 600             m_graph.voteNode(child1, VoteValue, weight);
 601             m_graph.voteNode(child2, VoteValue, weight);
 602             switch (node->arrayMode().type()) {
 603             case Array::Double:
 604                 m_graph.voteNode(child3, VoteDouble, weight);
 605                 break;
 606             default:
 607                 m_graph.voteNode(child3, VoteValue, weight);
 608                 break;
 609             }
 610             break;
 611         }
 612
 613         case MovHint:
 614             // Ignore these since they have no effect on in-DFG execution.
 615             break;
 616
 617         default:
 618             m_graph.voteChildren(node, VoteValue, weight);
 619             break;
 620         }
 621     }
 622
 623     void doRoundOfDoubleVoting()
 624     {
 625         for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i)
 626             m_graph.m_variableAccessData[i].find()->clearVotes();
 627         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
 628             BasicBlock* block = m_graph.block(blockIndex);
 629             if (!block)
 630                 continue;
 631             ASSERT(block->isReachable);
 632             for (unsigned i = 0; i < block->size(); ++i) {
 633                 m_currentNode = block->at(i);
 634                 doDoubleVoting(m_currentNode, block->executionCount);
 635             }
 636         }
 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->tallyVotesForShouldUseDoubleFormat();
 642         }
 643         propagateThroughArgumentPositions();
 644         for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i) {
 645             VariableAccessData* variableAccessData = &m_graph.m_variableAccessData[i];
 646             if (!variableAccessData->isRoot())
 647                 continue;
 648             m_changed |= variableAccessData->makePredictionForDoubleFormat();
 649         }
 650     }
 651
 652     void propagateThroughArgumentPositions()
 653     {
 654         for (unsigned i = 0; i < m_graph.m_argumentPositions.size(); ++i)
 655             m_changed |= m_graph.m_argumentPositions[i].mergeArgumentPredictionAwareness();
 656     }
 657
 658     // Sets any predictions that do not depends on other nodes.
 659     void processInvariants()
 660     {
 661         for (BasicBlock* block : m_graph.blocksInNaturalOrder()) {
 662             for (Node* node : *block) {
 663                 m_currentNode = node;
 664                 processInvariantsForNode();
 665             }
 666         }
 667     }
 668
 669     void processInvariantsForNode()
 670     {
 671         switch (m_currentNode->op()) {
 672         case JSConstant: {
 673             SpeculatedType type = speculationFromValue(m_currentNode->asJSValue());
 674             if (type == SpecAnyIntAsDouble && enableInt52())
 675                 type = SpecInt52Only;
 676             setPrediction(type);
 677             break;
 678         }
 679         case DoubleConstant: {
 680             SpeculatedType type = speculationFromValue(m_currentNode->asJSValue());
 681             setPrediction(type);
 682             break;
 683         }
 684         case BitAnd:
 685         case BitOr:
 686         case BitXor:
 687         case BitRShift:
 688         case BitLShift:
 689         case BitURShift:
 690         case ArithIMul:
 691         case ArithClz32: {
 692             setPrediction(SpecInt32Only);
 693             break;
 694         }
 695
 696         case ArrayPop:
 697         case ArrayPush:
 698         case RegExpExec:
 699         case RegExpTest:
 700         case StringReplace:
 701         case StringReplaceRegExp:
 702         case GetById:
 703         case GetByIdFlush:
 704         case GetByIdWithThis:
 705         case TryGetById:
 706         case GetByValWithThis:
 707         case GetByOffset:
 708         case MultiGetByOffset:
 709         case GetDirectPname:
 710         case Call:
 711         case DirectCall:
 712         case TailCallInlinedCaller:
 713         case DirectTailCallInlinedCaller:
 714         case Construct:
 715         case DirectConstruct:
 716         case CallVarargs:
 717         case CallEval:
 718         case TailCallVarargsInlinedCaller:
 719         case ConstructVarargs:
 720         case CallForwardVarargs:
 721         case ConstructForwardVarargs:
 722         case TailCallForwardVarargsInlinedCaller:
 723         case GetGlobalVar:
 724         case GetGlobalLexicalVariable:
 725         case GetClosureVar:
 726         case GetFromArguments:
 727         case LoadKeyFromMapBucket:
 728         case LoadValueFromMapBucket:
 729         case ToNumber:
 730         case ToObject:
 731         case CallObjectConstructor:
 732         case GetArgument:
 733         case CallDOMGetter:
 734         case GetDynamicVar:
 735         case WeakMapGet:
 736         case GetPrototypeOf: {
 737             setPrediction(m_currentNode->getHeapPrediction());
 738             break;
 739         }
 740
 741         case ResolveScopeForHoistingFuncDeclInEval: {
 742             setPrediction(SpecBytecodeTop);
 743             break;
 744         }
 745
 746         case GetGetterSetterByOffset:
 747         case GetExecutable: {
 748             setPrediction(SpecCellOther);
 749             break;
 750         }
 751
 752         case GetGetter:
 753         case GetSetter:
 754         case GetCallee:
 755         case NewFunction:
 756         case NewGeneratorFunction:
 757         case NewAsyncGeneratorFunction:
 758         case NewAsyncFunction: {
 759             setPrediction(SpecFunction);
 760             break;
 761         }
 762
 763         case GetArgumentCountIncludingThis: {
 764             setPrediction(SpecInt32Only);
 765             break;
 766         }
 767
 768         case MapHash:
 769             setPrediction(SpecInt32Only);
 770             break;
 771
 772         case GetMapBucket:
 773         case GetMapBucketHead:
 774         case GetMapBucketNext:
 775             setPrediction(SpecCellOther);
 776             break;
 777
 778         case GetRestLength:
 779         case ArrayIndexOf: {
 780             setPrediction(SpecInt32Only);
 781             break;
 782         }
 783
 784         case GetTypedArrayByteOffset:
 785         case GetArrayLength:
 786         case GetVectorLength: {
 787             setPrediction(SpecInt32Only);
 788             break;
 789         }
 790
 791         case StringCharCodeAt: {
 792             setPrediction(SpecInt32Only);
 793             break;
 794         }
 795
 796         case StringSlice:
 797         case ToLowerCase:
 798             setPrediction(SpecString);
 799             break;
 800
 801         case ArithPow:
 802         case ArithSqrt:
 803         case ArithFRound:
 804         case ArithUnary: {
 805             setPrediction(SpecBytecodeDouble);
 806             break;
 807         }
 808
 809         case ArithRound:
 810         case ArithFloor:
 811         case ArithCeil:
 812         case ArithTrunc: {
 813             if (isInt32OrBooleanSpeculation(m_currentNode->getHeapPrediction())
 814                 && m_graph.roundShouldSpeculateInt32(m_currentNode, m_pass))
 815                 setPrediction(SpecInt32Only);
 816             else
 817                 setPrediction(SpecBytecodeDouble);
 818             break;
 819         }
 820
 821         case ArithRandom: {
 822             setPrediction(SpecDoubleReal);
 823             break;
 824         }
 825         case DeleteByVal:
 826         case DeleteById:
 827         case LogicalNot:
 828         case CompareLess:
 829         case CompareLessEq:
 830         case CompareGreater:
 831         case CompareGreaterEq:
 832         case CompareBelow:
 833         case CompareBelowEq:
 834         case CompareEq:
 835         case CompareStrictEq:
 836         case CompareEqPtr:
 837         case OverridesHasInstance:
 838         case InstanceOf:
 839         case InstanceOfCustom:
 840         case IsEmpty:
 841         case IsUndefined:
 842         case IsBoolean:
 843         case IsNumber:
 844         case IsObject:
 845         case IsObjectOrNull:
 846         case IsFunction:
 847         case IsCellWithType:
 848         case IsTypedArrayView: {
 849             setPrediction(SpecBoolean);
 850             break;
 851         }
 852
 853         case TypeOf: {
 854             setPrediction(SpecStringIdent);
 855             break;
 856         }
 857         case GetButterfly:
 858         case GetButterflyWithoutCaging:
 859         case GetIndexedPropertyStorage:
 860         case AllocatePropertyStorage:
 861         case ReallocatePropertyStorage: {
 862             setPrediction(SpecOther);
 863             break;
 864         }
 865
 866         case CheckSubClass:
 867             break;
 868
 869         case SkipScope:
 870         case GetGlobalObject: {
 871             setPrediction(SpecObjectOther);
 872             break;
 873         }
 874
 875         case GetGlobalThis:
 876             setPrediction(SpecObject);
 877             break;
 878
 879         case ResolveScope: {
 880             setPrediction(SpecObjectOther);
 881             break;
 882         }
 883
 884         case CreateThis:
 885         case NewObject: {
 886             setPrediction(SpecFinalObject);
 887             break;
 888         }
 889
 890         case ArraySlice:
 891         case NewArrayWithSpread:
 892         case NewArray:
 893         case NewArrayWithSize:
 894         case CreateRest:
 895         case NewArrayBuffer: {
 896             setPrediction(SpecArray);
 897             break;
 898         }
 899
 900         case Spread:
 901             setPrediction(SpecCellOther);
 902             break;
 903
 904         case NewTypedArray: {
 905             setPrediction(speculationFromTypedArrayType(m_currentNode->typedArrayType()));
 906             break;
 907         }
 908
 909         case NewRegexp: {
 910             setPrediction(SpecRegExpObject);
 911             break;
 912         }
 913
 914         case PushWithScope:
 915         case CreateActivation: {
 916             setPrediction(SpecObjectOther);
 917             break;
 918         }
 919
 920         case StringFromCharCode: {
 921             setPrediction(SpecString);
 922             m_currentNode->child1()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsInt);
 923             break;
 924         }
 925         case StringCharAt:
 926         case CallStringConstructor:
 927         case ToString:
 928         case NumberToStringWithRadix:
 929         case NumberToStringWithValidRadixConstant:
 930         case MakeRope:
 931         case StrCat: {
 932             setPrediction(SpecString);
 933             break;
 934         }
 935         case NewStringObject: {
 936             setPrediction(SpecStringObject);
 937             break;
 938         }
 939
 940         case CreateDirectArguments: {
 941             setPrediction(SpecDirectArguments);
 942             break;
 943         }
 944
 945         case CreateScopedArguments: {
 946             setPrediction(SpecScopedArguments);
 947             break;
 948         }
 949
 950         case CreateClonedArguments: {
 951             setPrediction(SpecObjectOther);
 952             break;
 953         }
 954
 955         case FiatInt52: {
 956             RELEASE_ASSERT(enableInt52());
 957             setPrediction(SpecAnyInt);
 958             break;
 959         }
 960
 961         case GetScope:
 962             setPrediction(SpecObjectOther);
 963             break;
 964
 965         case In:
 966             setPrediction(SpecBoolean);
 967             break;
 968
 969         case HasOwnProperty:
 970             setPrediction(SpecBoolean);
 971             break;
 972
 973         case GetEnumerableLength: {
 974             setPrediction(SpecInt32Only);
 975             break;
 976         }
 977         case HasGenericProperty:
 978         case HasStructureProperty:
 979         case HasIndexedProperty: {
 980             setPrediction(SpecBoolean);
 981             break;
 982         }
 983         case GetPropertyEnumerator: {
 984             setPrediction(SpecCell);
 985             break;
 986         }
 987         case GetEnumeratorStructurePname: {
 988             setPrediction(SpecCell | SpecOther);
 989             break;
 990         }
 991         case GetEnumeratorGenericPname: {
 992             setPrediction(SpecCell | SpecOther);
 993             break;
 994         }
 995         case ToIndexString: {
 996             setPrediction(SpecString);
 997             break;
 998         }
 999         case ParseInt: {
1000             // We expect this node to almost always produce an int32. However,
1001             // it's possible it produces NaN or integers out of int32 range. We
1002             // rely on the heap prediction since the parseInt() call profiled
1003             // its result.
1004             setPrediction(m_currentNode->getHeapPrediction());
1005             break;
1006         }
1007
1008         case IdentityWithProfile: {
1009             setPrediction(m_currentNode->getForcedPrediction());
1010             break;
1011         }
1012
1013         case ExtractCatchLocal: {
1014             setPrediction(m_currentNode->catchLocalPrediction());
1015             break;
1016         }
1017
1018         case GetLocal:
1019         case SetLocal:
1020         case UInt32ToNumber:
1021         case ValueAdd:
1022         case ArithAdd:
1023         case ArithSub:
1024         case ArithNegate:
1025         case ArithMin:
1026         case ArithMax:
1027         case ArithMul:
1028         case ArithDiv:
1029         case ArithMod:
1030         case ArithAbs:
1031         case GetByVal:
1032         case ToThis:
1033         case ToPrimitive:
1034         case NormalizeMapKey:
1035         case AtomicsAdd:
1036         case AtomicsAnd:
1037         case AtomicsCompareExchange:
1038         case AtomicsExchange:
1039         case AtomicsLoad:
1040         case AtomicsOr:
1041         case AtomicsStore:
1042         case AtomicsSub:
1043         case AtomicsXor: {
1044             m_dependentNodes.append(m_currentNode);
1045             break;
1046         }
1047
1048         case AtomicsIsLockFree: {
1049             setPrediction(SpecBoolean);
1050             break;
1051         }
1052
1053         case CPUIntrinsic: {
1054             if (m_currentNode->intrinsic() == CPURdtscIntrinsic)
1055                 setPrediction(SpecInt32Only);
1056             else
1057                 setPrediction(SpecOther);
1058             break;
1059         }
1060
1061         case PutByValAlias:
1062         case DoubleAsInt32:
1063         case CheckArray:
1064         case CheckTypeInfoFlags:
1065         case Arrayify:
1066         case ArrayifyToStructure:
1067         case CheckTierUpInLoop:
1068         case CheckTierUpAtReturn:
1069         case CheckTierUpAndOSREnter:
1070         case InvalidationPoint:
1071         case CheckInBounds:
1072         case ValueToInt32:
1073         case DoubleRep:
1074         case ValueRep:
1075         case Int52Rep:
1076         case Int52Constant:
1077         case Identity:
1078         case BooleanToNumber:
1079         case PhantomNewObject:
1080         case PhantomNewFunction:
1081         case PhantomNewGeneratorFunction:
1082         case PhantomNewAsyncGeneratorFunction:
1083         case PhantomNewAsyncFunction:
1084         case PhantomCreateActivation:
1085         case PhantomDirectArguments:
1086         case PhantomCreateRest:
1087         case PhantomSpread:
1088         case PhantomNewArrayWithSpread:
1089         case PhantomClonedArguments:
1090         case GetMyArgumentByVal:
1091         case GetMyArgumentByValOutOfBounds:
1092         case PutHint:
1093         case CheckStructureImmediate:
1094         case CheckStructureOrEmpty:
1095         case MaterializeNewObject:
1096         case MaterializeCreateActivation:
1097         case PutStack:
1098         case KillStack:
1099         case StoreBarrier:
1100         case FencedStoreBarrier:
1101         case GetStack:
1102         case GetRegExpObjectLastIndex:
1103         case SetRegExpObjectLastIndex:
1104         case RecordRegExpCachedResult:
1105         case LazyJSConstant:
1106         case CallDOM: {
1107             // This node should never be visible at this stage of compilation.
1108             DFG_CRASH(m_graph, m_currentNode, "Unexpected node during prediction propagation");
1109             break;
1110         }
1111
1112         case Phi:
1113             // Phis should not be visible here since we're iterating the all-but-Phi's
1114             // part of basic blocks.
1115             RELEASE_ASSERT_NOT_REACHED();
1116             break;
1117
1118         case EntrySwitch:
1119         case Upsilon:
1120             // These don't get inserted until we go into SSA.
1121             RELEASE_ASSERT_NOT_REACHED();
1122             break;
1123
1124 #ifndef NDEBUG
1125         // These get ignored because they don't return anything.
1126         case PutByValDirect:
1127         case PutByValWithThis:
1128         case PutByIdWithThis:
1129         case PutByVal:
1130         case PutClosureVar:
1131         case PutToArguments:
1132         case Return:
1133         case Throw:
1134         case ThrowStaticError:
1135         case TailCall:
1136         case DirectTailCall:
1137         case TailCallVarargs:
1138         case TailCallForwardVarargs:
1139         case PutById:
1140         case PutByIdFlush:
1141         case PutByIdDirect:
1142         case PutByOffset:
1143         case MultiPutByOffset:
1144         case PutGetterById:
1145         case PutSetterById:
1146         case PutGetterSetterById:
1147         case PutGetterByVal:
1148         case PutSetterByVal:
1149         case DefineDataProperty:
1150         case DefineAccessorProperty:
1151         case DFG::Jump:
1152         case Branch:
1153         case Switch:
1154         case ProfileType:
1155         case ProfileControlFlow:
1156         case ForceOSRExit:
1157         case SetArgument:
1158         case SetFunctionName:
1159         case CheckStructure:
1160         case CheckCell:
1161         case CheckNotEmpty:
1162         case CheckStringIdent:
1163         case CheckBadCell:
1164         case PutStructure:
1165         case Phantom:
1166         case Check:
1167         case PutGlobalVariable:
1168         case CheckTraps:
1169         case LogShadowChickenPrologue:
1170         case LogShadowChickenTail:
1171         case Unreachable:
1172         case LoopHint:
1173         case NotifyWrite:
1174         case ConstantStoragePointer:
1175         case MovHint:
1176         case ZombieHint:
1177         case ExitOK:
1178         case LoadVarargs:
1179         case ForwardVarargs:
1180         case PutDynamicVar:
1181         case NukeStructureAndSetButterfly:
1182         case InitializeEntrypointArguments:
1183         case SetAdd:
1184         case MapSet:
1185             break;
1186
1187         // This gets ignored because it only pretends to produce a value.
1188         case BottomValue:
1189             break;
1190
1191         // This gets ignored because it already has a prediction.
1192         case ExtractOSREntryLocal:
1193             break;
1194
1195         // These gets ignored because it doesn't do anything.
1196         case CountExecution:
1197         case SuperSamplerBegin:
1198         case SuperSamplerEnd:
1199         case PhantomLocal:
1200         case Flush:
1201             break;
1202
1203         case LastNodeType:
1204             RELEASE_ASSERT_NOT_REACHED();
1205             break;
1206 #else
1207         default:
1208             break;
1209 #endif
1210         }
1211     }
1212
1213     SpeculatedType resultOfToPrimitive(SpeculatedType type)
1214     {
1215         if (type & SpecObject) {
1216             // We try to be optimistic here about StringObjects since it's unlikely that
1217             // someone overrides the valueOf or toString methods.
1218             if (type & SpecStringObject && m_graph.canOptimizeStringObjectAccess(m_currentNode->origin.semantic))
1219                 return mergeSpeculations(type & ~SpecObject, SpecString);
1220
1221             return mergeSpeculations(type & ~SpecObject, SpecPrimitive);
1222         }
1223
1224         return type;
1225     }
1226
1227     Vector<Node*> m_dependentNodes;
1228     Node* m_currentNode;
1229     bool m_changed;
1230     PredictionPass m_pass; // We use different logic for considering predictions depending on how far along we are in propagation.
1231 };
1232
1233 } // Anonymous namespace.
1234
1235 bool performPredictionPropagation(Graph& graph)
1236 {
1237     return runPhase<PredictionPropagationPhase>(graph);
1238 }
1239
1240 } } // namespace JSC::DFG
1241
1242 #endif // ENABLE(DFG_JIT)
1243