dfg/DFGAbstractState.cpp

   1 /*
   2  * Copyright (C) 2011 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 "DFGAbstractState.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "CodeBlock.h"
  32 #include "DFGBasicBlock.h"
  33
  34 namespace JSC { namespace DFG {
  35
  36 #define CFA_PROFILING 0
  37
  38 #if CFA_PROFILING
  39 #define PROFILE(flag) SamplingFlags::ScopedFlag scopedFlag(flag)
  40 #else
  41 #define PROFILE(flag) do { } while (false)
  42 #endif
  43
  44 // Profiling flags
  45 #define FLAG_FOR_BLOCK_INITIALIZATION  17
  46 #define FLAG_FOR_BLOCK_END             18
  47 #define FLAG_FOR_EXECUTION             19
  48 #define FLAG_FOR_MERGE_TO_SUCCESSORS   20
  49 #define FLAG_FOR_STRUCTURE_CLOBBERING  21
  50
  51 AbstractState::AbstractState(Graph& graph)
  52     : m_codeBlock(graph.m_codeBlock)
  53     , m_graph(graph)
  54     , m_variables(m_codeBlock->numParameters(), graph.m_localVars)
  55     , m_block(0)
  56 {
  57     m_nodes.resize(graph.size());
  58 }
  59
  60 AbstractState::~AbstractState() { }
  61
  62 void AbstractState::beginBasicBlock(BasicBlock* basicBlock)
  63 {
  64     PROFILE(FLAG_FOR_BLOCK_INITIALIZATION);
  65
  66     ASSERT(!m_block);
  67
  68     ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->valuesAtHead.numberOfLocals());
  69     ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
  70     ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
  71
  72     for (size_t i = 0; i < basicBlock->size(); i++)
  73         m_nodes[basicBlock->at(i)].clear();
  74
  75     m_variables = basicBlock->valuesAtHead;
  76     m_haveStructures = false;
  77     for (size_t i = 0; i < m_variables.numberOfArguments(); ++i) {
  78         if (m_variables.argument(i).m_structure.isNeitherClearNorTop()) {
  79             m_haveStructures = true;
  80             break;
  81         }
  82     }
  83     for (size_t i = 0; i < m_variables.numberOfLocals(); ++i) {
  84         if (m_variables.local(i).m_structure.isNeitherClearNorTop()) {
  85             m_haveStructures = true;
  86             break;
  87         }
  88     }
  89
  90     basicBlock->cfaShouldRevisit = false;
  91     basicBlock->cfaHasVisited = true;
  92     m_block = basicBlock;
  93     m_isValid = true;
  94 }
  95
  96 void AbstractState::initialize(Graph& graph)
  97 {
  98     PROFILE(FLAG_FOR_BLOCK_INITIALIZATION);
  99     BasicBlock* root = graph.m_blocks[0].get();
 100     root->cfaShouldRevisit = true;
 101     for (size_t i = 0; i < root->valuesAtHead.numberOfArguments(); ++i) {
 102         Node& node = graph[root->variablesAtHead.argument(i)];
 103         ASSERT(node.op() == SetArgument);
 104         if (!node.shouldGenerate()) {
 105             // The argument is dead. We don't do any checks for such arguments, and so
 106             // for the purpose of the analysis, they contain no value.
 107             root->valuesAtHead.argument(i).clear();
 108             continue;
 109         }
 110
 111         if (graph.argumentIsCaptured(i)) {
 112             root->valuesAtHead.argument(i).makeTop();
 113             continue;
 114         }
 115
 116         PredictedType prediction = node.variableAccessData()->prediction();
 117         if (isInt32Prediction(prediction))
 118             root->valuesAtHead.argument(i).set(PredictInt32);
 119         else if (isArrayPrediction(prediction))
 120             root->valuesAtHead.argument(i).set(PredictArray);
 121         else if (isBooleanPrediction(prediction))
 122             root->valuesAtHead.argument(i).set(PredictBoolean);
 123         else if (isInt8ArrayPrediction(prediction))
 124             root->valuesAtHead.argument(i).set(PredictInt8Array);
 125         else if (isInt16ArrayPrediction(prediction))
 126             root->valuesAtHead.argument(i).set(PredictInt16Array);
 127         else if (isInt32ArrayPrediction(prediction))
 128             root->valuesAtHead.argument(i).set(PredictInt32Array);
 129         else if (isUint8ArrayPrediction(prediction))
 130             root->valuesAtHead.argument(i).set(PredictUint8Array);
 131         else if (isUint8ClampedArrayPrediction(prediction))
 132             root->valuesAtHead.argument(i).set(PredictUint8ClampedArray);
 133         else if (isUint16ArrayPrediction(prediction))
 134             root->valuesAtHead.argument(i).set(PredictUint16Array);
 135         else if (isUint32ArrayPrediction(prediction))
 136             root->valuesAtHead.argument(i).set(PredictUint32Array);
 137         else if (isFloat32ArrayPrediction(prediction))
 138             root->valuesAtHead.argument(i).set(PredictFloat32Array);
 139         else if (isFloat64ArrayPrediction(prediction))
 140             root->valuesAtHead.argument(i).set(PredictFloat64Array);
 141         else
 142             root->valuesAtHead.argument(i).makeTop();
 143     }
 144     for (size_t i = 0; i < root->valuesAtHead.numberOfLocals(); ++i) {
 145         if (!graph.localIsCaptured(i))
 146             continue;
 147         root->valuesAtHead.local(i).makeTop();
 148     }
 149 }
 150
 151 bool AbstractState::endBasicBlock(MergeMode mergeMode)
 152 {
 153     PROFILE(FLAG_FOR_BLOCK_END);
 154     ASSERT(m_block);
 155
 156     BasicBlock* block = m_block; // Save the block for successor merging.
 157
 158     if (!m_isValid) {
 159         reset();
 160         return false;
 161     }
 162
 163     bool changed = false;
 164
 165     if (mergeMode != DontMerge || !ASSERT_DISABLED) {
 166         for (size_t argument = 0; argument < block->variablesAtTail.numberOfArguments(); ++argument) {
 167 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 168             dataLog("        Merging state for argument %zu.\n", argument);
 169 #endif
 170             AbstractValue& destination = block->valuesAtTail.argument(argument);
 171             if (m_graph.argumentIsCaptured(argument)) {
 172                 if (!destination.isTop()) {
 173                     destination.makeTop();
 174                     changed = true;
 175                 }
 176             } else
 177                 changed |= mergeStateAtTail(destination, m_variables.argument(argument), block->variablesAtTail.argument(argument));
 178         }
 179
 180         for (size_t local = 0; local < block->variablesAtTail.numberOfLocals(); ++local) {
 181 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 182             dataLog("        Merging state for local %zu.\n", local);
 183 #endif
 184             AbstractValue& destination = block->valuesAtTail.local(local);
 185             if (m_graph.localIsCaptured(local)) {
 186                 if (!destination.isTop()) {
 187                     destination.makeTop();
 188                     changed = true;
 189                 }
 190             } else
 191                 changed |= mergeStateAtTail(destination, m_variables.local(local), block->variablesAtTail.local(local));
 192         }
 193     }
 194
 195     ASSERT(mergeMode != DontMerge || !changed);
 196
 197     reset();
 198
 199     if (mergeMode != MergeToSuccessors)
 200         return changed;
 201
 202     return mergeToSuccessors(m_graph, block);
 203 }
 204
 205 void AbstractState::reset()
 206 {
 207     m_block = 0;
 208     m_isValid = false;
 209 }
 210
 211 bool AbstractState::execute(unsigned indexInBlock)
 212 {
 213     PROFILE(FLAG_FOR_EXECUTION);
 214     ASSERT(m_block);
 215     ASSERT(m_isValid);
 216
 217     NodeIndex nodeIndex = m_block->at(indexInBlock);
 218     Node& node = m_graph[nodeIndex];
 219
 220     if (!node.shouldGenerate())
 221         return true;
 222
 223     switch (node.op()) {
 224     case JSConstant:
 225     case WeakJSConstant: {
 226         JSValue value = m_graph.valueOfJSConstant(nodeIndex);
 227         // Have to be careful here! It's tempting to call set(value), but
 228         // that would be wrong, since that would constitute a proof that this
 229         // value will always have the same structure. The whole point of a value
 230         // having a structure is that it may change in the future - for example
 231         // between when we compile the code and when we run it.
 232         forNode(nodeIndex).set(predictionFromValue(value));
 233         break;
 234     }
 235
 236     case GetLocal: {
 237         if (m_graph.isCaptured(node.local()))
 238             forNode(nodeIndex).makeTop();
 239         else
 240             forNode(nodeIndex) = m_variables.operand(node.local());
 241         break;
 242     }
 243
 244     case SetLocal: {
 245         if (m_graph.isCaptured(node.local()))
 246             break;
 247
 248         if (node.variableAccessData()->shouldUseDoubleFormat()) {
 249             forNode(node.child1()).filter(PredictNumber);
 250             m_variables.operand(node.local()).set(PredictDouble);
 251             break;
 252         }
 253
 254         PredictedType predictedType = node.variableAccessData()->argumentAwarePrediction();
 255         if (isInt32Prediction(predictedType))
 256             forNode(node.child1()).filter(PredictInt32);
 257         else if (isArrayPrediction(predictedType))
 258             forNode(node.child1()).filter(PredictArray);
 259         else if (isBooleanPrediction(predictedType))
 260             forNode(node.child1()).filter(PredictBoolean);
 261
 262         m_variables.operand(node.local()) = forNode(node.child1());
 263         break;
 264     }
 265
 266     case SetArgument:
 267         // Assert that the state of arguments has been set.
 268         ASSERT(!m_block->valuesAtHead.operand(node.local()).isClear());
 269         break;
 270
 271     case BitAnd:
 272     case BitOr:
 273     case BitXor:
 274     case BitRShift:
 275     case BitLShift:
 276     case BitURShift:
 277         forNode(node.child1()).filter(PredictInt32);
 278         forNode(node.child2()).filter(PredictInt32);
 279         forNode(nodeIndex).set(PredictInt32);
 280         break;
 281
 282     case UInt32ToNumber:
 283         if (!node.canSpeculateInteger())
 284             forNode(nodeIndex).set(PredictDouble);
 285         else
 286             forNode(nodeIndex).set(PredictInt32);
 287         break;
 288
 289     case DoubleAsInt32:
 290         forNode(node.child1()).filter(PredictNumber);
 291         forNode(nodeIndex).set(PredictInt32);
 292         break;
 293
 294     case ValueToInt32:
 295         if (m_graph[node.child1()].shouldSpeculateInteger())
 296             forNode(node.child1()).filter(PredictInt32);
 297         else if (m_graph[node.child1()].shouldSpeculateNumber())
 298             forNode(node.child1()).filter(PredictNumber);
 299         else if (m_graph[node.child1()].shouldSpeculateBoolean())
 300             forNode(node.child1()).filter(PredictBoolean);
 301
 302         forNode(nodeIndex).set(PredictInt32);
 303         break;
 304
 305     case Int32ToDouble:
 306         forNode(node.child1()).filter(PredictNumber);
 307         forNode(nodeIndex).set(PredictDouble);
 308         break;
 309
 310     case CheckNumber:
 311         forNode(node.child1()).filter(PredictNumber);
 312         break;
 313
 314     case ValueAdd:
 315     case ArithAdd: {
 316         if (m_graph.addShouldSpeculateInteger(node)) {
 317             forNode(node.child1()).filter(PredictInt32);
 318             forNode(node.child2()).filter(PredictInt32);
 319             forNode(nodeIndex).set(PredictInt32);
 320             break;
 321         }
 322         if (Node::shouldSpeculateNumber(m_graph[node.child1()], m_graph[node.child2()])) {
 323             forNode(node.child1()).filter(PredictNumber);
 324             forNode(node.child2()).filter(PredictNumber);
 325             forNode(nodeIndex).set(PredictDouble);
 326             break;
 327         }
 328         if (node.op() == ValueAdd) {
 329             clobberStructures(indexInBlock);
 330             forNode(nodeIndex).set(PredictString | PredictInt32 | PredictNumber);
 331             break;
 332         }
 333         // We don't handle this yet. :-(
 334         m_isValid = false;
 335         break;
 336     }
 337
 338     case ArithSub: {
 339         if (m_graph.addShouldSpeculateInteger(node)) {
 340             forNode(node.child1()).filter(PredictInt32);
 341             forNode(node.child2()).filter(PredictInt32);
 342             forNode(nodeIndex).set(PredictInt32);
 343             break;
 344         }
 345         forNode(node.child1()).filter(PredictNumber);
 346         forNode(node.child2()).filter(PredictNumber);
 347         forNode(nodeIndex).set(PredictDouble);
 348         break;
 349     }
 350
 351     case ArithNegate: {
 352         if (m_graph.negateShouldSpeculateInteger(node)) {
 353             forNode(node.child1()).filter(PredictInt32);
 354             forNode(nodeIndex).set(PredictInt32);
 355             break;
 356         }
 357         forNode(node.child1()).filter(PredictNumber);
 358         forNode(nodeIndex).set(PredictDouble);
 359         break;
 360     }
 361
 362     case ArithMul:
 363     case ArithDiv:
 364     case ArithMin:
 365     case ArithMax:
 366     case ArithMod: {
 367         if (Node::shouldSpeculateInteger(m_graph[node.child1()], m_graph[node.child2()]) && node.canSpeculateInteger()) {
 368             forNode(node.child1()).filter(PredictInt32);
 369             forNode(node.child2()).filter(PredictInt32);
 370             forNode(nodeIndex).set(PredictInt32);
 371             break;
 372         }
 373         forNode(node.child1()).filter(PredictNumber);
 374         forNode(node.child2()).filter(PredictNumber);
 375         forNode(nodeIndex).set(PredictDouble);
 376         break;
 377     }
 378
 379     case ArithAbs:
 380         if (m_graph[node.child1()].shouldSpeculateInteger() && node.canSpeculateInteger()) {
 381             forNode(node.child1()).filter(PredictInt32);
 382             forNode(nodeIndex).set(PredictInt32);
 383             break;
 384         }
 385         forNode(node.child1()).filter(PredictNumber);
 386         forNode(nodeIndex).set(PredictDouble);
 387         break;
 388
 389     case ArithSqrt:
 390         forNode(node.child1()).filter(PredictNumber);
 391         forNode(nodeIndex).set(PredictDouble);
 392         break;
 393
 394     case LogicalNot: {
 395         Node& child = m_graph[node.child1()];
 396         if (isBooleanPrediction(child.prediction()))
 397             forNode(node.child1()).filter(PredictBoolean);
 398         else if (child.shouldSpeculateFinalObjectOrOther())
 399             forNode(node.child1()).filter(PredictFinalObject | PredictOther);
 400         else if (child.shouldSpeculateArrayOrOther())
 401             forNode(node.child1()).filter(PredictArray | PredictOther);
 402         else if (child.shouldSpeculateInteger())
 403             forNode(node.child1()).filter(PredictInt32);
 404         else if (child.shouldSpeculateNumber())
 405             forNode(node.child1()).filter(PredictNumber);
 406         else
 407             clobberStructures(indexInBlock);
 408         forNode(nodeIndex).set(PredictBoolean);
 409         break;
 410     }
 411
 412     case IsUndefined:
 413     case IsBoolean:
 414     case IsNumber:
 415     case IsString:
 416     case IsObject:
 417     case IsFunction: {
 418         forNode(nodeIndex).set(PredictBoolean);
 419         break;
 420     }
 421
 422     case CompareLess:
 423     case CompareLessEq:
 424     case CompareGreater:
 425     case CompareGreaterEq:
 426     case CompareEq: {
 427         forNode(nodeIndex).set(PredictBoolean);
 428
 429         Node& left = m_graph[node.child1()];
 430         Node& right = m_graph[node.child2()];
 431         PredictedType filter;
 432         if (Node::shouldSpeculateInteger(left, right))
 433             filter = PredictInt32;
 434         else if (Node::shouldSpeculateNumber(left, right))
 435             filter = PredictNumber;
 436         else if (node.op() == CompareEq) {
 437             if ((m_graph.isConstant(node.child1().index())
 438                  && m_graph.valueOfJSConstant(node.child1().index()).isNull())
 439                 || (m_graph.isConstant(node.child2().index())
 440                     && m_graph.valueOfJSConstant(node.child2().index()).isNull())) {
 441                 // We know that this won't clobber the world. But that's all we know.
 442                 break;
 443             }
 444
 445             if (Node::shouldSpeculateFinalObject(left, right))
 446                 filter = PredictFinalObject;
 447             else if (Node::shouldSpeculateArray(left, right))
 448                 filter = PredictArray;
 449             else if (left.shouldSpeculateFinalObject() && right.shouldSpeculateFinalObjectOrOther()) {
 450                 forNode(node.child1()).filter(PredictFinalObject);
 451                 forNode(node.child2()).filter(PredictFinalObject | PredictOther);
 452                 break;
 453             } else if (right.shouldSpeculateFinalObject() && left.shouldSpeculateFinalObjectOrOther()) {
 454                 forNode(node.child1()).filter(PredictFinalObject | PredictOther);
 455                 forNode(node.child2()).filter(PredictFinalObject);
 456                 break;
 457             } else if (left.shouldSpeculateArray() && right.shouldSpeculateArrayOrOther()) {
 458                 forNode(node.child1()).filter(PredictFinalObject);
 459                 forNode(node.child2()).filter(PredictFinalObject | PredictOther);
 460                 break;
 461             } else if (right.shouldSpeculateArray() && left.shouldSpeculateArrayOrOther()) {
 462                 forNode(node.child1()).filter(PredictFinalObject | PredictOther);
 463                 forNode(node.child2()).filter(PredictFinalObject);
 464                 break;
 465             } else {
 466                 filter = PredictTop;
 467                 clobberStructures(indexInBlock);
 468             }
 469         } else {
 470             filter = PredictTop;
 471             clobberStructures(indexInBlock);
 472         }
 473         forNode(node.child1()).filter(filter);
 474         forNode(node.child2()).filter(filter);
 475         break;
 476     }
 477
 478     case CompareStrictEq:
 479         forNode(nodeIndex).set(PredictBoolean);
 480         break;
 481
 482     case StringCharCodeAt:
 483         forNode(node.child1()).filter(PredictString);
 484         forNode(node.child2()).filter(PredictInt32);
 485         forNode(nodeIndex).set(PredictInt32);
 486         break;
 487
 488     case StringCharAt:
 489         forNode(node.child1()).filter(PredictString);
 490         forNode(node.child2()).filter(PredictInt32);
 491         forNode(nodeIndex).set(PredictString);
 492         break;
 493
 494     case GetByVal: {
 495         if (!node.prediction() || !m_graph[node.child1()].prediction() || !m_graph[node.child2()].prediction()) {
 496             m_isValid = false;
 497             break;
 498         }
 499         if (!isActionableArrayPrediction(m_graph[node.child1()].prediction()) || !m_graph[node.child2()].shouldSpeculateInteger()) {
 500             clobberStructures(indexInBlock);
 501             forNode(nodeIndex).makeTop();
 502             break;
 503         }
 504         if (m_graph[node.child1()].prediction() == PredictString) {
 505             forNode(node.child1()).filter(PredictString);
 506             forNode(node.child2()).filter(PredictInt32);
 507             forNode(nodeIndex).set(PredictString);
 508             break;
 509         }
 510
 511         if (m_graph[node.child1()].shouldSpeculateInt8Array()) {
 512             forNode(node.child1()).filter(PredictInt8Array);
 513             forNode(node.child2()).filter(PredictInt32);
 514             forNode(nodeIndex).set(PredictInt32);
 515             break;
 516         }
 517         if (m_graph[node.child1()].shouldSpeculateInt16Array()) {
 518             forNode(node.child1()).filter(PredictInt16Array);
 519             forNode(node.child2()).filter(PredictInt32);
 520             forNode(nodeIndex).set(PredictInt32);
 521             break;
 522         }
 523         if (m_graph[node.child1()].shouldSpeculateInt32Array()) {
 524             forNode(node.child1()).filter(PredictInt32Array);
 525             forNode(node.child2()).filter(PredictInt32);
 526             forNode(nodeIndex).set(PredictInt32);
 527             break;
 528         }
 529         if (m_graph[node.child1()].shouldSpeculateUint8Array()) {
 530             forNode(node.child1()).filter(PredictUint8Array);
 531             forNode(node.child2()).filter(PredictInt32);
 532             forNode(nodeIndex).set(PredictInt32);
 533             break;
 534         }
 535         if (m_graph[node.child1()].shouldSpeculateUint8ClampedArray()) {
 536             forNode(node.child1()).filter(PredictUint8ClampedArray);
 537             forNode(node.child2()).filter(PredictInt32);
 538             forNode(nodeIndex).set(PredictInt32);
 539             break;
 540         }
 541         if (m_graph[node.child1()].shouldSpeculateUint16Array()) {
 542             forNode(node.child1()).filter(PredictUint16Array);
 543             forNode(node.child2()).filter(PredictInt32);
 544             forNode(nodeIndex).set(PredictInt32);
 545             break;
 546         }
 547         if (m_graph[node.child1()].shouldSpeculateUint32Array()) {
 548             forNode(node.child1()).filter(PredictUint32Array);
 549             forNode(node.child2()).filter(PredictInt32);
 550             if (node.shouldSpeculateInteger())
 551                 forNode(nodeIndex).set(PredictInt32);
 552             else
 553                 forNode(nodeIndex).set(PredictDouble);
 554             break;
 555         }
 556         if (m_graph[node.child1()].shouldSpeculateFloat32Array()) {
 557             forNode(node.child1()).filter(PredictFloat32Array);
 558             forNode(node.child2()).filter(PredictInt32);
 559             forNode(nodeIndex).set(PredictDouble);
 560             break;
 561         }
 562         if (m_graph[node.child1()].shouldSpeculateFloat64Array()) {
 563             forNode(node.child1()).filter(PredictFloat64Array);
 564             forNode(node.child2()).filter(PredictInt32);
 565             forNode(nodeIndex).set(PredictDouble);
 566             break;
 567         }
 568         ASSERT(m_graph[node.child1()].shouldSpeculateArray());
 569         forNode(node.child1()).filter(PredictArray);
 570         forNode(node.child2()).filter(PredictInt32);
 571         forNode(nodeIndex).makeTop();
 572         break;
 573     }
 574
 575     case PutByVal:
 576     case PutByValAlias: {
 577         if (!m_graph[node.child1()].prediction() || !m_graph[node.child2()].prediction()) {
 578             m_isValid = false;
 579             break;
 580         }
 581         if (!m_graph[node.child2()].shouldSpeculateInteger() || !isActionableMutableArrayPrediction(m_graph[node.child1()].prediction())) {
 582             ASSERT(node.op() == PutByVal);
 583             clobberStructures(indexInBlock);
 584             forNode(nodeIndex).makeTop();
 585             break;
 586         }
 587
 588         if (m_graph[node.child1()].shouldSpeculateInt8Array()) {
 589             forNode(node.child1()).filter(PredictInt8Array);
 590             forNode(node.child2()).filter(PredictInt32);
 591             if (m_graph[node.child3()].shouldSpeculateInteger())
 592                 forNode(node.child3()).filter(PredictInt32);
 593             else
 594                 forNode(node.child3()).filter(PredictNumber);
 595             break;
 596         }
 597         if (m_graph[node.child1()].shouldSpeculateInt16Array()) {
 598             forNode(node.child1()).filter(PredictInt16Array);
 599             forNode(node.child2()).filter(PredictInt32);
 600             if (m_graph[node.child3()].shouldSpeculateInteger())
 601                 forNode(node.child3()).filter(PredictInt32);
 602             else
 603                 forNode(node.child3()).filter(PredictNumber);
 604             break;
 605         }
 606         if (m_graph[node.child1()].shouldSpeculateInt32Array()) {
 607             forNode(node.child1()).filter(PredictInt32Array);
 608             forNode(node.child2()).filter(PredictInt32);
 609             if (m_graph[node.child3()].shouldSpeculateInteger())
 610                 forNode(node.child3()).filter(PredictInt32);
 611             else
 612                 forNode(node.child3()).filter(PredictNumber);
 613             break;
 614         }
 615         if (m_graph[node.child1()].shouldSpeculateUint8Array()) {
 616             forNode(node.child1()).filter(PredictUint8Array);
 617             forNode(node.child2()).filter(PredictInt32);
 618             if (m_graph[node.child3()].shouldSpeculateInteger())
 619                 forNode(node.child3()).filter(PredictInt32);
 620             else
 621                 forNode(node.child3()).filter(PredictNumber);
 622             break;
 623         }
 624         if (m_graph[node.child1()].shouldSpeculateUint8ClampedArray()) {
 625             forNode(node.child1()).filter(PredictUint8ClampedArray);
 626             forNode(node.child2()).filter(PredictInt32);
 627             if (m_graph[node.child3()].shouldSpeculateInteger())
 628                 forNode(node.child3()).filter(PredictInt32);
 629             else
 630                 forNode(node.child3()).filter(PredictNumber);
 631             break;
 632         }
 633         if (m_graph[node.child1()].shouldSpeculateUint16Array()) {
 634             forNode(node.child1()).filter(PredictUint16Array);
 635             forNode(node.child2()).filter(PredictInt32);
 636             if (m_graph[node.child3()].shouldSpeculateInteger())
 637                 forNode(node.child3()).filter(PredictInt32);
 638             else
 639                 forNode(node.child3()).filter(PredictNumber);
 640             break;
 641         }
 642         if (m_graph[node.child1()].shouldSpeculateUint32Array()) {
 643             forNode(node.child1()).filter(PredictUint32Array);
 644             forNode(node.child2()).filter(PredictInt32);
 645             if (m_graph[node.child3()].shouldSpeculateInteger())
 646                 forNode(node.child3()).filter(PredictInt32);
 647             else
 648                 forNode(node.child3()).filter(PredictNumber);
 649             break;
 650         }
 651         if (m_graph[node.child1()].shouldSpeculateFloat32Array()) {
 652             forNode(node.child1()).filter(PredictFloat32Array);
 653             forNode(node.child2()).filter(PredictInt32);
 654             forNode(node.child3()).filter(PredictNumber);
 655             break;
 656         }
 657         if (m_graph[node.child1()].shouldSpeculateFloat64Array()) {
 658             forNode(node.child1()).filter(PredictFloat64Array);
 659             forNode(node.child2()).filter(PredictInt32);
 660             forNode(node.child3()).filter(PredictNumber);
 661             break;
 662         }
 663         ASSERT(m_graph[node.child1()].shouldSpeculateArray());
 664         forNode(node.child1()).filter(PredictArray);
 665         forNode(node.child2()).filter(PredictInt32);
 666         break;
 667     }
 668
 669     case ArrayPush:
 670         forNode(node.child1()).filter(PredictArray);
 671         forNode(nodeIndex).set(PredictNumber);
 672         break;
 673
 674     case ArrayPop:
 675         forNode(node.child1()).filter(PredictArray);
 676         forNode(nodeIndex).makeTop();
 677         break;
 678
 679     case RegExpExec:
 680     case RegExpTest:
 681         forNode(node.child1()).filter(PredictCell);
 682         forNode(node.child2()).filter(PredictCell);
 683         forNode(nodeIndex).makeTop();
 684         break;
 685
 686     case Jump:
 687         break;
 688
 689     case Branch: {
 690         // There is probably profit to be found in doing sparse conditional constant
 691         // propagation, and to take it one step further, where a variable's value
 692         // is specialized on each direction of a branch. For now, we don't do this.
 693         Node& child = m_graph[node.child1()];
 694         if (child.shouldSpeculateBoolean())
 695             forNode(node.child1()).filter(PredictBoolean);
 696         else if (child.shouldSpeculateFinalObjectOrOther())
 697             forNode(node.child1()).filter(PredictFinalObject | PredictOther);
 698         else if (child.shouldSpeculateArrayOrOther())
 699             forNode(node.child1()).filter(PredictArray | PredictOther);
 700         else if (child.shouldSpeculateInteger())
 701             forNode(node.child1()).filter(PredictInt32);
 702         else if (child.shouldSpeculateNumber())
 703             forNode(node.child1()).filter(PredictNumber);
 704         break;
 705     }
 706
 707     case Return:
 708     case Throw:
 709     case ThrowReferenceError:
 710         m_isValid = false;
 711         break;
 712
 713     case ToPrimitive: {
 714         Node& child = m_graph[node.child1()];
 715         if (child.shouldSpeculateInteger()) {
 716             forNode(node.child1()).filter(PredictInt32);
 717             forNode(nodeIndex).set(PredictInt32);
 718             break;
 719         }
 720
 721         AbstractValue& source = forNode(node.child1());
 722         AbstractValue& destination = forNode(nodeIndex);
 723
 724         PredictedType type = source.m_type;
 725         if (type & ~(PredictNumber | PredictString | PredictBoolean)) {
 726             type &= (PredictNumber | PredictString | PredictBoolean);
 727             type |= PredictString;
 728         }
 729         destination.set(type);
 730         break;
 731     }
 732
 733     case StrCat:
 734         forNode(nodeIndex).set(PredictString);
 735         break;
 736
 737     case NewArray:
 738     case NewArrayBuffer:
 739         forNode(nodeIndex).set(m_codeBlock->globalObject()->arrayStructure());
 740         m_haveStructures = true;
 741         break;
 742
 743     case NewRegexp:
 744         forNode(nodeIndex).set(m_codeBlock->globalObject()->regExpStructure());
 745         m_haveStructures = true;
 746         break;
 747
 748     case ConvertThis: {
 749         Node& child = m_graph[node.child1()];
 750         AbstractValue& source = forNode(node.child1());
 751         AbstractValue& destination = forNode(nodeIndex);
 752
 753         if (isObjectPrediction(source.m_type)) {
 754             // This is the simple case. We already know that the source is an
 755             // object, so there's nothing to do. I don't think this case will
 756             // be hit, but then again, you never know.
 757             destination = source;
 758             break;
 759         }
 760
 761         if (isOtherPrediction(child.prediction())) {
 762             source.filter(PredictOther);
 763             destination.set(PredictObjectOther);
 764             break;
 765         }
 766
 767         if (isObjectPrediction(child.prediction())) {
 768             source.filter(PredictObjectMask);
 769             destination = source;
 770             break;
 771         }
 772
 773         destination = source;
 774         destination.merge(PredictObjectOther);
 775         break;
 776     }
 777
 778     case CreateThis: {
 779         Node& child = m_graph[node.child1()];
 780         AbstractValue& source = forNode(node.child1());
 781         AbstractValue& destination = forNode(nodeIndex);
 782
 783         if (child.shouldSpeculateFinalObject())
 784             source.filter(PredictFinalObject);
 785
 786         destination.set(PredictFinalObject);
 787         break;
 788     }
 789
 790     case NewObject:
 791         forNode(nodeIndex).set(m_codeBlock->globalObjectFor(node.codeOrigin)->emptyObjectStructure());
 792         m_haveStructures = true;
 793         break;
 794
 795     case CreateActivation:
 796         forNode(nodeIndex).set(m_graph.m_globalData.activationStructure.get());
 797         m_haveStructures = true;
 798         break;
 799
 800     case TearOffActivation:
 801         // Does nothing that is user-visible.
 802         break;
 803
 804     case NewFunction:
 805     case NewFunctionExpression:
 806     case NewFunctionNoCheck:
 807         forNode(nodeIndex).set(m_codeBlock->globalObjectFor(node.codeOrigin)->functionStructure());
 808         break;
 809
 810     case GetCallee:
 811         forNode(nodeIndex).set(PredictFunction);
 812         break;
 813
 814     case GetScopeChain:
 815         forNode(nodeIndex).set(PredictCellOther);
 816         break;
 817
 818     case GetScopedVar:
 819         forNode(nodeIndex).makeTop();
 820         break;
 821
 822     case PutScopedVar:
 823         clobberStructures(indexInBlock);
 824         break;
 825
 826     case GetById:
 827     case GetByIdFlush:
 828         if (!node.prediction()) {
 829             m_isValid = false;
 830             break;
 831         }
 832         if (isCellPrediction(m_graph[node.child1()].prediction()))
 833             forNode(node.child1()).filter(PredictCell);
 834         clobberStructures(indexInBlock);
 835         forNode(nodeIndex).makeTop();
 836         break;
 837
 838     case GetArrayLength:
 839         forNode(node.child1()).filter(PredictArray);
 840         forNode(nodeIndex).set(PredictInt32);
 841         break;
 842
 843     case GetStringLength:
 844         forNode(node.child1()).filter(PredictString);
 845         forNode(nodeIndex).set(PredictInt32);
 846         break;
 847
 848     case GetInt8ArrayLength:
 849         forNode(node.child1()).filter(PredictInt8Array);
 850         forNode(nodeIndex).set(PredictInt32);
 851         break;
 852     case GetInt16ArrayLength:
 853         forNode(node.child1()).filter(PredictInt16Array);
 854         forNode(nodeIndex).set(PredictInt32);
 855         break;
 856     case GetInt32ArrayLength:
 857         forNode(node.child1()).filter(PredictInt32Array);
 858         forNode(nodeIndex).set(PredictInt32);
 859         break;
 860     case GetUint8ArrayLength:
 861         forNode(node.child1()).filter(PredictUint8Array);
 862         forNode(nodeIndex).set(PredictInt32);
 863         break;
 864     case GetUint8ClampedArrayLength:
 865         forNode(node.child1()).filter(PredictUint8ClampedArray);
 866         forNode(nodeIndex).set(PredictInt32);
 867         break;
 868     case GetUint16ArrayLength:
 869         forNode(node.child1()).filter(PredictUint16Array);
 870         forNode(nodeIndex).set(PredictInt32);
 871         break;
 872     case GetUint32ArrayLength:
 873         forNode(node.child1()).filter(PredictUint32Array);
 874         forNode(nodeIndex).set(PredictInt32);
 875         break;
 876     case GetFloat32ArrayLength:
 877         forNode(node.child1()).filter(PredictFloat32Array);
 878         forNode(nodeIndex).set(PredictInt32);
 879         break;
 880     case GetFloat64ArrayLength:
 881         forNode(node.child1()).filter(PredictFloat64Array);
 882         forNode(nodeIndex).set(PredictInt32);
 883         break;
 884
 885     case CheckStructure:
 886         // FIXME: We should be able to propagate the structure sets of constants (i.e. prototypes).
 887         forNode(node.child1()).filter(node.structureSet());
 888         m_haveStructures = true;
 889         break;
 890
 891     case PutStructure:
 892         clobberStructures(indexInBlock);
 893         forNode(node.child1()).set(node.structureTransitionData().newStructure);
 894         m_haveStructures = true;
 895         break;
 896     case GetPropertyStorage:
 897         forNode(node.child1()).filter(PredictCell);
 898         forNode(nodeIndex).clear(); // The result is not a JS value.
 899         break;
 900     case GetIndexedPropertyStorage: {
 901         PredictedType basePrediction = m_graph[node.child2()].prediction();
 902         if (!(basePrediction & PredictInt32) && basePrediction) {
 903             forNode(nodeIndex).clear();
 904             break;
 905         }
 906         if (m_graph[node.child1()].prediction() == PredictString) {
 907             forNode(node.child1()).filter(PredictString);
 908             forNode(nodeIndex).clear();
 909             break;
 910         }
 911
 912         if (m_graph[node.child1()].shouldSpeculateInt8Array()) {
 913             forNode(node.child1()).filter(PredictInt8Array);
 914             forNode(nodeIndex).clear();
 915             break;
 916         }
 917         if (m_graph[node.child1()].shouldSpeculateInt16Array()) {
 918             forNode(node.child1()).filter(PredictInt16Array);
 919             forNode(nodeIndex).clear();
 920             break;
 921         }
 922         if (m_graph[node.child1()].shouldSpeculateInt32Array()) {
 923             forNode(node.child1()).filter(PredictInt32Array);
 924             forNode(nodeIndex).clear();
 925             break;
 926         }
 927         if (m_graph[node.child1()].shouldSpeculateUint8Array()) {
 928             forNode(node.child1()).filter(PredictUint8Array);
 929             forNode(nodeIndex).clear();
 930             break;
 931         }
 932         if (m_graph[node.child1()].shouldSpeculateUint8ClampedArray()) {
 933             forNode(node.child1()).filter(PredictUint8ClampedArray);
 934             forNode(nodeIndex).clear();
 935             break;
 936         }
 937         if (m_graph[node.child1()].shouldSpeculateUint16Array()) {
 938             forNode(node.child1()).filter(PredictUint16Array);
 939             forNode(nodeIndex).set(PredictOther);
 940             break;
 941         }
 942         if (m_graph[node.child1()].shouldSpeculateUint32Array()) {
 943             forNode(node.child1()).filter(PredictUint32Array);
 944             forNode(nodeIndex).clear();
 945             break;
 946         }
 947         if (m_graph[node.child1()].shouldSpeculateFloat32Array()) {
 948             forNode(node.child1()).filter(PredictFloat32Array);
 949             forNode(nodeIndex).clear();
 950             break;
 951         }
 952         if (m_graph[node.child1()].shouldSpeculateFloat64Array()) {
 953             forNode(node.child1()).filter(PredictFloat64Array);
 954             forNode(nodeIndex).clear();
 955             break;
 956         }
 957         forNode(node.child1()).filter(PredictArray);
 958         forNode(nodeIndex).clear();
 959         break;
 960     }
 961     case GetByOffset:
 962         forNode(node.child1()).filter(PredictCell);
 963         forNode(nodeIndex).makeTop();
 964         break;
 965
 966     case PutByOffset:
 967         forNode(node.child1()).filter(PredictCell);
 968         break;
 969
 970     case CheckFunction:
 971         forNode(node.child1()).filter(PredictFunction);
 972         // FIXME: Should be able to propagate the fact that we know what the function is.
 973         break;
 974
 975     case PutById:
 976     case PutByIdDirect:
 977         forNode(node.child1()).filter(PredictCell);
 978         clobberStructures(indexInBlock);
 979         break;
 980
 981     case GetGlobalVar:
 982         forNode(nodeIndex).makeTop();
 983         break;
 984
 985     case PutGlobalVar:
 986         break;
 987
 988     case CheckHasInstance:
 989         forNode(node.child1()).filter(PredictCell);
 990         // Sadly, we don't propagate the fact that we've done CheckHasInstance
 991         break;
 992
 993     case InstanceOf:
 994         // Again, sadly, we don't propagate the fact that we've done InstanceOf
 995         if (!(m_graph[node.child1()].prediction() & ~PredictCell) && !(forNode(node.child1()).m_type & ~PredictCell))
 996             forNode(node.child1()).filter(PredictCell);
 997         forNode(node.child3()).filter(PredictCell);
 998         forNode(nodeIndex).set(PredictBoolean);
 999         break;
1000
1001     case Phi:
1002     case Flush:
1003         break;
1004
1005     case Breakpoint:
1006         break;
1007
1008     case Call:
1009     case Construct:
1010     case Resolve:
1011     case ResolveBase:
1012     case ResolveBaseStrictPut:
1013     case ResolveGlobal:
1014         clobberStructures(indexInBlock);
1015         forNode(nodeIndex).makeTop();
1016         break;
1017
1018     case ForceOSRExit:
1019         m_isValid = false;
1020         break;
1021
1022     case Phantom:
1023     case InlineStart:
1024     case Nop:
1025         break;
1026
1027     case LastNodeType:
1028         ASSERT_NOT_REACHED();
1029         break;
1030     }
1031
1032     return m_isValid;
1033 }
1034
1035 inline void AbstractState::clobberStructures(unsigned indexInBlock)
1036 {
1037     PROFILE(FLAG_FOR_STRUCTURE_CLOBBERING);
1038     if (!m_haveStructures)
1039         return;
1040     for (size_t i = indexInBlock + 1; i--;)
1041         forNode(m_block->at(i)).clobberStructures();
1042     for (size_t i = 0; i < m_variables.numberOfArguments(); ++i)
1043         m_variables.argument(i).clobberStructures();
1044     for (size_t i = 0; i < m_variables.numberOfLocals(); ++i)
1045         m_variables.local(i).clobberStructures();
1046     m_haveStructures = false;
1047 }
1048
1049 inline bool AbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, NodeIndex nodeIndex)
1050 {
1051     if (nodeIndex == NoNode)
1052         return false;
1053
1054     AbstractValue source;
1055
1056     Node& node = m_graph[nodeIndex];
1057     if (!node.refCount())
1058         return false;
1059
1060 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1061     dataLog("          It's live, node @%u.\n", nodeIndex);
1062 #endif
1063
1064     switch (node.op()) {
1065     case Phi:
1066     case SetArgument:
1067     case Flush:
1068         // The block transfers the value from head to tail.
1069         source = inVariable;
1070 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1071         dataLog("          Transfering from head to tail.\n");
1072 #endif
1073         break;
1074
1075     case GetLocal:
1076         // The block refines the value with additional speculations.
1077         source = forNode(nodeIndex);
1078 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1079         dataLog("          Refining.\n");
1080 #endif
1081         break;
1082
1083     case SetLocal:
1084         // The block sets the variable, and potentially refines it, both
1085         // before and after setting it.
1086         if (node.variableAccessData()->shouldUseDoubleFormat())
1087             source.set(PredictDouble);
1088         else
1089             source = forNode(node.child1());
1090 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1091         dataLog("          Setting.\n");
1092 #endif
1093         break;
1094
1095     default:
1096         ASSERT_NOT_REACHED();
1097         break;
1098     }
1099
1100     if (destination == source) {
1101         // Abstract execution did not change the output value of the variable, for this
1102         // basic block, on this iteration.
1103 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1104         dataLog("          Not changed!\n");
1105 #endif
1106         return false;
1107     }
1108
1109     // Abstract execution reached a new conclusion about the speculations reached about
1110     // this variable after execution of this basic block. Update the state, and return
1111     // true to indicate that the fixpoint must go on!
1112     destination = source;
1113 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1114     dataLog("          Changed!\n");
1115 #endif
1116     return true;
1117 }
1118
1119 inline bool AbstractState::merge(BasicBlock* from, BasicBlock* to)
1120 {
1121     ASSERT(from->variablesAtTail.numberOfArguments() == to->variablesAtHead.numberOfArguments());
1122     ASSERT(from->variablesAtTail.numberOfLocals() == to->variablesAtHead.numberOfLocals());
1123
1124     bool changed = false;
1125
1126     for (size_t argument = 0; argument < from->variablesAtTail.numberOfArguments(); ++argument) {
1127         AbstractValue& destination = to->valuesAtHead.argument(argument);
1128         if (m_graph.argumentIsCaptured(argument)) {
1129             if (destination.isTop())
1130                 continue;
1131             destination.makeTop();
1132             changed = true;
1133             continue;
1134         }
1135         changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.argument(argument), to->variablesAtHead.argument(argument), from->variablesAtTail.argument(argument));
1136     }
1137
1138     for (size_t local = 0; local < from->variablesAtTail.numberOfLocals(); ++local) {
1139         AbstractValue& destination = to->valuesAtHead.local(local);
1140         if (m_graph.localIsCaptured(local)) {
1141             if (destination.isTop())
1142                 continue;
1143             destination.makeTop();
1144             changed = true;
1145             continue;
1146         }
1147         changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.local(local), to->variablesAtHead.local(local), from->variablesAtTail.local(local));
1148     }
1149
1150     if (!to->cfaHasVisited)
1151         changed = true;
1152
1153     to->cfaShouldRevisit |= changed;
1154
1155     return changed;
1156 }
1157
1158 inline bool AbstractState::mergeToSuccessors(Graph& graph, BasicBlock* basicBlock)
1159 {
1160     PROFILE(FLAG_FOR_MERGE_TO_SUCCESSORS);
1161
1162     Node& terminal = graph[basicBlock->last()];
1163
1164     ASSERT(terminal.isTerminal());
1165
1166     switch (terminal.op()) {
1167     case Jump:
1168         return merge(basicBlock, graph.m_blocks[terminal.takenBlockIndex()].get());
1169
1170     case Branch:
1171         return merge(basicBlock, graph.m_blocks[terminal.takenBlockIndex()].get())
1172             | merge(basicBlock, graph.m_blocks[terminal.notTakenBlockIndex()].get());
1173
1174     case Return:
1175     case Throw:
1176     case ThrowReferenceError:
1177         return false;
1178
1179     default:
1180         ASSERT_NOT_REACHED();
1181         return false;
1182     }
1183 }
1184
1185 inline bool AbstractState::mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, NodeIndex destinationNodeIndex, NodeIndex sourceNodeIndex)
1186 {
1187     if (destinationNodeIndex == NoNode)
1188         return false;
1189
1190     ASSERT_UNUSED(sourceNodeIndex, sourceNodeIndex != NoNode);
1191
1192     // FIXME: We could do some sparse conditional propagation here!
1193
1194     return destination.merge(source);
1195 }
1196
1197 #ifndef NDEBUG
1198 void AbstractState::dump(FILE* out)
1199 {
1200     bool first = true;
1201     for (size_t i = 0; i < m_block->size(); ++i) {
1202         NodeIndex index = m_block->at(i);
1203         AbstractValue& value = m_nodes[index];
1204         if (value.isClear())
1205             continue;
1206         if (first)
1207             first = false;
1208         else
1209             fprintf(out, " ");
1210         fprintf(out, "@%lu:", static_cast<unsigned long>(index));
1211         value.dump(out);
1212     }
1213 }
1214 #endif
1215
1216 } } // namespace JSC::DFG
1217
1218 #endif // ENABLE(DFG_JIT)
1219