dfg/DFGAbstractState.cpp

   1 /*
   2  * Copyright (C) 2011, 2012, 2013 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 #include "GetByIdStatus.h"
  34 #include "Operations.h"
  35 #include "PutByIdStatus.h"
  36 #include "StringObject.h"
  37
  38 namespace JSC { namespace DFG {
  39
  40 AbstractState::AbstractState(Graph& graph)
  41     : m_codeBlock(graph.m_codeBlock)
  42     , m_graph(graph)
  43     , m_variables(m_codeBlock->numParameters(), graph.m_localVars)
  44     , m_block(0)
  45 {
  46 }
  47
  48 AbstractState::~AbstractState() { }
  49
  50 void AbstractState::beginBasicBlock(BasicBlock* basicBlock)
  51 {
  52     ASSERT(!m_block);
  53
  54     ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->valuesAtHead.numberOfLocals());
  55     ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
  56     ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
  57
  58     for (size_t i = 0; i < basicBlock->size(); i++)
  59         forNode(basicBlock->at(i)).clear();
  60
  61     m_variables = basicBlock->valuesAtHead;
  62     m_haveStructures = false;
  63     for (size_t i = 0; i < m_variables.numberOfArguments(); ++i) {
  64         if (m_variables.argument(i).m_currentKnownStructure.isNeitherClearNorTop()) {
  65             m_haveStructures = true;
  66             break;
  67         }
  68     }
  69     for (size_t i = 0; i < m_variables.numberOfLocals(); ++i) {
  70         if (m_variables.local(i).m_currentKnownStructure.isNeitherClearNorTop()) {
  71             m_haveStructures = true;
  72             break;
  73         }
  74     }
  75
  76     basicBlock->cfaShouldRevisit = false;
  77     basicBlock->cfaHasVisited = true;
  78     m_block = basicBlock;
  79     m_isValid = true;
  80     m_foundConstants = false;
  81     m_branchDirection = InvalidBranchDirection;
  82 }
  83
  84 void AbstractState::initialize(Graph& graph)
  85 {
  86     BasicBlock* root = graph.m_blocks[0].get();
  87     root->cfaShouldRevisit = true;
  88     root->cfaHasVisited = false;
  89     root->cfaFoundConstants = false;
  90     for (size_t i = 0; i < root->valuesAtHead.numberOfArguments(); ++i) {
  91         Node* node = root->variablesAtHead.argument(i);
  92         ASSERT(node->op() == SetArgument);
  93         if (!node->variableAccessData()->shouldUnboxIfPossible()) {
  94             root->valuesAtHead.argument(i).makeTop();
  95             continue;
  96         }
  97
  98         SpeculatedType prediction = node->variableAccessData()->prediction();
  99         if (isInt32Speculation(prediction))
 100             root->valuesAtHead.argument(i).set(SpecInt32);
 101         else if (isBooleanSpeculation(prediction))
 102             root->valuesAtHead.argument(i).set(SpecBoolean);
 103         else if (isCellSpeculation(prediction))
 104             root->valuesAtHead.argument(i).set(SpecCell);
 105         else
 106             root->valuesAtHead.argument(i).makeTop();
 107
 108         root->valuesAtTail.argument(i).clear();
 109     }
 110     for (size_t i = 0; i < root->valuesAtHead.numberOfLocals(); ++i) {
 111         Node* node = root->variablesAtHead.local(i);
 112         if (node && node->variableAccessData()->isCaptured())
 113             root->valuesAtHead.local(i).makeTop();
 114         else
 115             root->valuesAtHead.local(i).clear();
 116         root->valuesAtTail.local(i).clear();
 117     }
 118     for (BlockIndex blockIndex = 1 ; blockIndex < graph.m_blocks.size(); ++blockIndex) {
 119         BasicBlock* block = graph.m_blocks[blockIndex].get();
 120         if (!block)
 121             continue;
 122         if (!block->isReachable)
 123             continue;
 124         block->cfaShouldRevisit = false;
 125         block->cfaHasVisited = false;
 126         block->cfaFoundConstants = false;
 127         for (size_t i = 0; i < block->valuesAtHead.numberOfArguments(); ++i) {
 128             block->valuesAtHead.argument(i).clear();
 129             block->valuesAtTail.argument(i).clear();
 130         }
 131         for (size_t i = 0; i < block->valuesAtHead.numberOfLocals(); ++i) {
 132             block->valuesAtHead.local(i).clear();
 133             block->valuesAtTail.local(i).clear();
 134         }
 135         if (!block->isOSRTarget)
 136             continue;
 137         if (block->bytecodeBegin != graph.m_osrEntryBytecodeIndex)
 138             continue;
 139         for (size_t i = 0; i < graph.m_mustHandleValues.size(); ++i) {
 140             AbstractValue value;
 141             value.setMostSpecific(graph.m_mustHandleValues[i]);
 142             int operand = graph.m_mustHandleValues.operandForIndex(i);
 143             block->valuesAtHead.operand(operand).merge(value);
 144 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 145             dataLogF("    Initializing Block #%u, operand r%d, to ", blockIndex, operand);
 146             block->valuesAtHead.operand(operand).dump(WTF::dataFile());
 147             dataLogF("\n");
 148 #endif
 149         }
 150         block->cfaShouldRevisit = true;
 151     }
 152 }
 153
 154 bool AbstractState::endBasicBlock(MergeMode mergeMode)
 155 {
 156     ASSERT(m_block);
 157
 158     BasicBlock* block = m_block; // Save the block for successor merging.
 159
 160     block->cfaFoundConstants = m_foundConstants;
 161     block->cfaDidFinish = m_isValid;
 162     block->cfaBranchDirection = m_branchDirection;
 163
 164     if (!m_isValid) {
 165         reset();
 166         return false;
 167     }
 168
 169     bool changed = false;
 170
 171     if (mergeMode != DontMerge || !ASSERT_DISABLED) {
 172         for (size_t argument = 0; argument < block->variablesAtTail.numberOfArguments(); ++argument) {
 173 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 174             dataLogF("        Merging state for argument %zu.\n", argument);
 175 #endif
 176             AbstractValue& destination = block->valuesAtTail.argument(argument);
 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             dataLogF("        Merging state for local %zu.\n", local);
 183 #endif
 184             AbstractValue& destination = block->valuesAtTail.local(local);
 185             changed |= mergeStateAtTail(destination, m_variables.local(local), block->variablesAtTail.local(local));
 186         }
 187     }
 188
 189     ASSERT(mergeMode != DontMerge || !changed);
 190
 191 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 192     dataLogF("        Branch direction = %s\n", branchDirectionToString(m_branchDirection));
 193 #endif
 194
 195     reset();
 196
 197     if (mergeMode != MergeToSuccessors)
 198         return changed;
 199
 200     return mergeToSuccessors(m_graph, block);
 201 }
 202
 203 void AbstractState::reset()
 204 {
 205     m_block = 0;
 206     m_isValid = false;
 207     m_branchDirection = InvalidBranchDirection;
 208 }
 209
 210 AbstractState::BooleanResult AbstractState::booleanResult(Node* node, AbstractValue& value)
 211 {
 212     JSValue childConst = value.value();
 213     if (childConst) {
 214         if (childConst.toBoolean(m_codeBlock->globalObjectFor(node->codeOrigin)->globalExec()))
 215             return DefinitelyTrue;
 216         return DefinitelyFalse;
 217     }
 218
 219     // Next check if we can fold because we know that the source is an object or string and does not equal undefined.
 220     if (isCellSpeculation(value.m_type)
 221         && value.m_currentKnownStructure.hasSingleton()) {
 222         Structure* structure = value.m_currentKnownStructure.singleton();
 223         if (!structure->masqueradesAsUndefined(m_codeBlock->globalObjectFor(node->codeOrigin))
 224             && structure->typeInfo().type() != StringType)
 225             return DefinitelyTrue;
 226     }
 227
 228     return UnknownBooleanResult;
 229 }
 230
 231 bool AbstractState::startExecuting(Node* node)
 232 {
 233     ASSERT(m_block);
 234     ASSERT(m_isValid);
 235
 236     m_didClobber = false;
 237
 238     node->setCanExit(false);
 239
 240     if (!node->shouldGenerate())
 241         return false;
 242
 243     return true;
 244 }
 245
 246 bool AbstractState::startExecuting(unsigned indexInBlock)
 247 {
 248     return startExecuting(m_block->at(indexInBlock));
 249 }
 250
 251 void AbstractState::executeEdges(Node* node)
 252 {
 253     DFG_NODE_DO_TO_CHILDREN(m_graph, node, filterEdgeByUse);
 254 }
 255
 256 void AbstractState::executeEdges(unsigned indexInBlock)
 257 {
 258     executeEdges(m_block->at(indexInBlock));
 259 }
 260
 261 void AbstractState::verifyEdge(Node*, Edge edge)
 262 {
 263     RELEASE_ASSERT(!(forNode(edge).m_type & ~typeFilterFor(edge.useKind())));
 264 }
 265
 266 void AbstractState::verifyEdges(Node* node)
 267 {
 268     DFG_NODE_DO_TO_CHILDREN(m_graph, node, verifyEdge);
 269 }
 270
 271 bool AbstractState::executeEffects(unsigned indexInBlock, Node* node)
 272 {
 273     if (!ASSERT_DISABLED)
 274         verifyEdges(node);
 275
 276     switch (node->op()) {
 277     case JSConstant:
 278     case WeakJSConstant:
 279     case PhantomArguments: {
 280         forNode(node).set(m_graph.valueOfJSConstant(node));
 281         break;
 282     }
 283
 284     case Identity: {
 285         forNode(node) = forNode(node->child1());
 286         break;
 287     }
 288
 289     case GetLocal: {
 290         VariableAccessData* variableAccessData = node->variableAccessData();
 291         if (variableAccessData->prediction() == SpecNone) {
 292             m_isValid = false;
 293             break;
 294         }
 295         AbstractValue value = m_variables.operand(variableAccessData->local());
 296         if (!variableAccessData->isCaptured()) {
 297             if (value.isClear())
 298                 node->setCanExit(true);
 299         }
 300         if (value.value())
 301             m_foundConstants = true;
 302         forNode(node) = value;
 303         break;
 304     }
 305
 306     case GetLocalUnlinked: {
 307         AbstractValue value = m_variables.operand(node->unlinkedLocal());
 308         if (value.value())
 309             m_foundConstants = true;
 310         forNode(node) = value;
 311         break;
 312     }
 313
 314     case SetLocal: {
 315         m_variables.operand(node->local()) = forNode(node->child1());
 316         break;
 317     }
 318
 319     case MovHintAndCheck: {
 320         // Don't need to do anything. A MovHint is effectively a promise that the SetLocal
 321         // was dead.
 322         break;
 323     }
 324
 325     case MovHint:
 326     case ZombieHint: {
 327         RELEASE_ASSERT_NOT_REACHED();
 328         break;
 329     }
 330
 331     case SetArgument:
 332         // Assert that the state of arguments has been set.
 333         ASSERT(!m_block->valuesAtHead.operand(node->local()).isClear());
 334         break;
 335
 336     case BitAnd:
 337     case BitOr:
 338     case BitXor:
 339     case BitRShift:
 340     case BitLShift:
 341     case BitURShift: {
 342         JSValue left = forNode(node->child1()).value();
 343         JSValue right = forNode(node->child2()).value();
 344         if (left && right && left.isInt32() && right.isInt32()) {
 345             int32_t a = left.asInt32();
 346             int32_t b = right.asInt32();
 347             bool constantWasSet;
 348             switch (node->op()) {
 349             case BitAnd:
 350                 constantWasSet = trySetConstant(node, JSValue(a & b));
 351                 break;
 352             case BitOr:
 353                 constantWasSet = trySetConstant(node, JSValue(a | b));
 354                 break;
 355             case BitXor:
 356                 constantWasSet = trySetConstant(node, JSValue(a ^ b));
 357                 break;
 358             case BitRShift:
 359                 constantWasSet = trySetConstant(node, JSValue(a >> static_cast<uint32_t>(b)));
 360                 break;
 361             case BitLShift:
 362                 constantWasSet = trySetConstant(node, JSValue(a << static_cast<uint32_t>(b)));
 363                 break;
 364             case BitURShift:
 365                 constantWasSet = trySetConstant(node, JSValue(static_cast<uint32_t>(a) >> static_cast<uint32_t>(b)));
 366                 break;
 367             default:
 368                 RELEASE_ASSERT_NOT_REACHED();
 369                 constantWasSet = false;
 370             }
 371             if (constantWasSet) {
 372                 m_foundConstants = true;
 373                 break;
 374             }
 375         }
 376         forNode(node).set(SpecInt32);
 377         break;
 378     }
 379
 380     case UInt32ToNumber: {
 381         JSValue child = forNode(node->child1()).value();
 382         if (child && child.isNumber()) {
 383             ASSERT(child.isInt32());
 384             if (trySetConstant(node, JSValue(child.asUInt32()))) {
 385                 m_foundConstants = true;
 386                 break;
 387             }
 388         }
 389         if (!node->canSpeculateInteger())
 390             forNode(node).set(SpecDouble);
 391         else {
 392             forNode(node).set(SpecInt32);
 393             node->setCanExit(true);
 394         }
 395         break;
 396     }
 397
 398     case DoubleAsInt32: {
 399         JSValue child = forNode(node->child1()).value();
 400         if (child && child.isNumber()) {
 401             double asDouble = child.asNumber();
 402             int32_t asInt = JSC::toInt32(asDouble);
 403             if (bitwise_cast<int64_t>(static_cast<double>(asInt)) == bitwise_cast<int64_t>(asDouble)
 404                 && trySetConstant(node, JSValue(asInt))) {
 405                 m_foundConstants = true;
 406                 break;
 407             }
 408         }
 409         node->setCanExit(true);
 410         forNode(node).set(SpecInt32);
 411         break;
 412     }
 413
 414     case ValueToInt32: {
 415         JSValue child = forNode(node->child1()).value();
 416         if (child && child.isNumber()) {
 417             bool constantWasSet;
 418             if (child.isInt32())
 419                 constantWasSet = trySetConstant(node, child);
 420             else
 421                 constantWasSet = trySetConstant(node, JSValue(JSC::toInt32(child.asDouble())));
 422             if (constantWasSet) {
 423                 m_foundConstants = true;
 424                 break;
 425             }
 426         }
 427
 428         forNode(node).set(SpecInt32);
 429         break;
 430     }
 431
 432     case Int32ToDouble:
 433     case ForwardInt32ToDouble: {
 434         JSValue child = forNode(node->child1()).value();
 435         if (child && child.isNumber()
 436             && trySetConstant(node, JSValue(JSValue::EncodeAsDouble, child.asNumber()))) {
 437             m_foundConstants = true;
 438             break;
 439         }
 440         if (isInt32Speculation(forNode(node->child1()).m_type))
 441             forNode(node).set(SpecDoubleReal);
 442         else
 443             forNode(node).set(SpecDouble);
 444         break;
 445     }
 446
 447     case ValueAdd:
 448     case ArithAdd: {
 449         JSValue left = forNode(node->child1()).value();
 450         JSValue right = forNode(node->child2()).value();
 451         if (left && right && left.isNumber() && right.isNumber()
 452             && trySetConstant(node, JSValue(left.asNumber() + right.asNumber()))) {
 453             m_foundConstants = true;
 454             break;
 455         }
 456         switch (node->binaryUseKind()) {
 457         case Int32Use:
 458             forNode(node).set(SpecInt32);
 459             if (!nodeCanTruncateInteger(node->arithNodeFlags()))
 460                 node->setCanExit(true);
 461             break;
 462         case NumberUse:
 463             if (isRealNumberSpeculation(forNode(node->child1()).m_type)
 464                 && isRealNumberSpeculation(forNode(node->child2()).m_type))
 465                 forNode(node).set(SpecDoubleReal);
 466             else
 467                 forNode(node).set(SpecDouble);
 468             break;
 469         default:
 470             RELEASE_ASSERT(node->op() == ValueAdd);
 471             clobberWorld(node->codeOrigin, indexInBlock);
 472             forNode(node).set(SpecString | SpecInt32 | SpecNumber);
 473             break;
 474         }
 475         break;
 476     }
 477
 478     case MakeRope: {
 479         forNode(node).set(m_graph.m_vm.stringStructure.get());
 480         break;
 481     }
 482
 483     case ArithSub: {
 484         JSValue left = forNode(node->child1()).value();
 485         JSValue right = forNode(node->child2()).value();
 486         if (left && right && left.isNumber() && right.isNumber()
 487             && trySetConstant(node, JSValue(left.asNumber() - right.asNumber()))) {
 488             m_foundConstants = true;
 489             break;
 490         }
 491         switch (node->binaryUseKind()) {
 492         case Int32Use:
 493             forNode(node).set(SpecInt32);
 494             if (!nodeCanTruncateInteger(node->arithNodeFlags()))
 495                 node->setCanExit(true);
 496             break;
 497         case NumberUse:
 498             forNode(node).set(SpecDouble);
 499             break;
 500         default:
 501             RELEASE_ASSERT_NOT_REACHED();
 502             break;
 503         }
 504         break;
 505     }
 506
 507     case ArithNegate: {
 508         JSValue child = forNode(node->child1()).value();
 509         if (child && child.isNumber()
 510             && trySetConstant(node, JSValue(-child.asNumber()))) {
 511             m_foundConstants = true;
 512             break;
 513         }
 514         switch (node->child1().useKind()) {
 515         case Int32Use:
 516             forNode(node).set(SpecInt32);
 517             if (!nodeCanTruncateInteger(node->arithNodeFlags()))
 518                 node->setCanExit(true);
 519             break;
 520         case NumberUse:
 521             forNode(node).set(SpecDouble);
 522             break;
 523         default:
 524             RELEASE_ASSERT_NOT_REACHED();
 525             break;
 526         }
 527         break;
 528     }
 529
 530     case ArithMul: {
 531         JSValue left = forNode(node->child1()).value();
 532         JSValue right = forNode(node->child2()).value();
 533         if (left && right && left.isNumber() && right.isNumber()
 534             && trySetConstant(node, JSValue(left.asNumber() * right.asNumber()))) {
 535             m_foundConstants = true;
 536             break;
 537         }
 538         switch (node->binaryUseKind()) {
 539         case Int32Use:
 540             forNode(node).set(SpecInt32);
 541             if (!nodeCanTruncateInteger(node->arithNodeFlags())
 542                 || !nodeCanIgnoreNegativeZero(node->arithNodeFlags()))
 543                 node->setCanExit(true);
 544             break;
 545         case NumberUse:
 546             if (isRealNumberSpeculation(forNode(node->child1()).m_type)
 547                 || isRealNumberSpeculation(forNode(node->child2()).m_type))
 548                 forNode(node).set(SpecDoubleReal);
 549             else
 550                 forNode(node).set(SpecDouble);
 551             break;
 552         default:
 553             RELEASE_ASSERT_NOT_REACHED();
 554             break;
 555         }
 556         break;
 557     }
 558
 559     case ArithIMul: {
 560         forNode(node).set(SpecInt32);
 561         break;
 562     }
 563
 564     case ArithDiv:
 565     case ArithMin:
 566     case ArithMax:
 567     case ArithMod: {
 568         JSValue left = forNode(node->child1()).value();
 569         JSValue right = forNode(node->child2()).value();
 570         if (left && right && left.isNumber() && right.isNumber()) {
 571             double a = left.asNumber();
 572             double b = right.asNumber();
 573             bool constantWasSet;
 574             switch (node->op()) {
 575             case ArithDiv:
 576                 constantWasSet = trySetConstant(node, JSValue(a / b));
 577                 break;
 578             case ArithMin:
 579                 constantWasSet = trySetConstant(node, JSValue(a < b ? a : (b <= a ? b : a + b)));
 580                 break;
 581             case ArithMax:
 582                 constantWasSet = trySetConstant(node, JSValue(a > b ? a : (b >= a ? b : a + b)));
 583                 break;
 584             case ArithMod:
 585                 constantWasSet = trySetConstant(node, JSValue(fmod(a, b)));
 586                 break;
 587             default:
 588                 RELEASE_ASSERT_NOT_REACHED();
 589                 constantWasSet = false;
 590                 break;
 591             }
 592             if (constantWasSet) {
 593                 m_foundConstants = true;
 594                 break;
 595             }
 596         }
 597         switch (node->binaryUseKind()) {
 598         case Int32Use:
 599             forNode(node).set(SpecInt32);
 600             node->setCanExit(true);
 601             break;
 602         case NumberUse:
 603             forNode(node).set(SpecDouble);
 604             break;
 605         default:
 606             RELEASE_ASSERT_NOT_REACHED();
 607             break;
 608         }
 609         break;
 610     }
 611
 612     case ArithAbs: {
 613         JSValue child = forNode(node->child1()).value();
 614         if (child && child.isNumber()
 615             && trySetConstant(node, JSValue(fabs(child.asNumber())))) {
 616             m_foundConstants = true;
 617             break;
 618         }
 619         switch (node->child1().useKind()) {
 620         case Int32Use:
 621             forNode(node).set(SpecInt32);
 622             node->setCanExit(true);
 623             break;
 624         case NumberUse:
 625             forNode(node).set(SpecDouble);
 626             break;
 627         default:
 628             RELEASE_ASSERT_NOT_REACHED();
 629             break;
 630         }
 631         break;
 632     }
 633
 634     case ArithSqrt: {
 635         JSValue child = forNode(node->child1()).value();
 636         if (child && child.isNumber()
 637             && trySetConstant(node, JSValue(sqrt(child.asNumber())))) {
 638             m_foundConstants = true;
 639             break;
 640         }
 641         forNode(node).set(SpecDouble);
 642         break;
 643     }
 644
 645     case LogicalNot: {
 646         bool didSetConstant = false;
 647         switch (booleanResult(node, forNode(node->child1()))) {
 648         case DefinitelyTrue:
 649             didSetConstant = trySetConstant(node, jsBoolean(false));
 650             break;
 651         case DefinitelyFalse:
 652             didSetConstant = trySetConstant(node, jsBoolean(true));
 653             break;
 654         default:
 655             break;
 656         }
 657         if (didSetConstant) {
 658             m_foundConstants = true;
 659             break;
 660         }
 661         switch (node->child1().useKind()) {
 662         case BooleanUse:
 663         case Int32Use:
 664         case NumberUse:
 665         case UntypedUse:
 666             break;
 667         case ObjectOrOtherUse:
 668             node->setCanExit(true);
 669             break;
 670         default:
 671             RELEASE_ASSERT_NOT_REACHED();
 672             break;
 673         }
 674         forNode(node).set(SpecBoolean);
 675         break;
 676     }
 677
 678     case IsUndefined:
 679     case IsBoolean:
 680     case IsNumber:
 681     case IsString:
 682     case IsObject:
 683     case IsFunction: {
 684         node->setCanExit(node->op() == IsUndefined && m_codeBlock->globalObjectFor(node->codeOrigin)->masqueradesAsUndefinedWatchpoint()->isStillValid());
 685         JSValue child = forNode(node->child1()).value();
 686         if (child) {
 687             bool constantWasSet;
 688             switch (node->op()) {
 689             case IsUndefined:
 690                 if (m_codeBlock->globalObjectFor(node->codeOrigin)->masqueradesAsUndefinedWatchpoint()->isStillValid()) {
 691                     constantWasSet = trySetConstant(node, jsBoolean(
 692                         child.isCell()
 693                         ? false
 694                         : child.isUndefined()));
 695                 } else {
 696                     constantWasSet = trySetConstant(node, jsBoolean(
 697                         child.isCell()
 698                         ? child.asCell()->structure()->masqueradesAsUndefined(m_codeBlock->globalObjectFor(node->codeOrigin))
 699                         : child.isUndefined()));
 700                 }
 701                 break;
 702             case IsBoolean:
 703                 constantWasSet = trySetConstant(node, jsBoolean(child.isBoolean()));
 704                 break;
 705             case IsNumber:
 706                 constantWasSet = trySetConstant(node, jsBoolean(child.isNumber()));
 707                 break;
 708             case IsString:
 709                 constantWasSet = trySetConstant(node, jsBoolean(isJSString(child)));
 710                 break;
 711             case IsObject:
 712                 if (child.isNull() || !child.isObject()) {
 713                     constantWasSet = trySetConstant(node, jsBoolean(child.isNull()));
 714                     break;
 715                 }
 716             default:
 717                 constantWasSet = false;
 718                 break;
 719             }
 720             if (constantWasSet) {
 721                 m_foundConstants = true;
 722                 break;
 723             }
 724         }
 725
 726         forNode(node).set(SpecBoolean);
 727         break;
 728     }
 729
 730     case TypeOf: {
 731         VM* vm = m_codeBlock->vm();
 732         JSValue child = forNode(node->child1()).value();
 733         AbstractValue& abstractChild = forNode(node->child1());
 734         if (child) {
 735             JSValue typeString = jsTypeStringForValue(*vm, m_codeBlock->globalObjectFor(node->codeOrigin), child);
 736             if (trySetConstant(node, typeString)) {
 737                 m_foundConstants = true;
 738                 break;
 739             }
 740         } else if (isNumberSpeculation(abstractChild.m_type)) {
 741             if (trySetConstant(node, vm->smallStrings.numberString())) {
 742                 forNode(node->child1()).filter(SpecNumber);
 743                 m_foundConstants = true;
 744                 break;
 745             }
 746         } else if (isStringSpeculation(abstractChild.m_type)) {
 747             if (trySetConstant(node, vm->smallStrings.stringString())) {
 748                 forNode(node->child1()).filter(SpecString);
 749                 m_foundConstants = true;
 750                 break;
 751             }
 752         } else if (isFinalObjectSpeculation(abstractChild.m_type) || isArraySpeculation(abstractChild.m_type) || isArgumentsSpeculation(abstractChild.m_type)) {
 753             if (trySetConstant(node, vm->smallStrings.objectString())) {
 754                 forNode(node->child1()).filter(SpecFinalObject | SpecArray | SpecArguments);
 755                 m_foundConstants = true;
 756                 break;
 757             }
 758         } else if (isFunctionSpeculation(abstractChild.m_type)) {
 759             if (trySetConstant(node, vm->smallStrings.functionString())) {
 760                 forNode(node->child1()).filter(SpecFunction);
 761                 m_foundConstants = true;
 762                 break;
 763             }
 764         } else if (isBooleanSpeculation(abstractChild.m_type)) {
 765             if (trySetConstant(node, vm->smallStrings.booleanString())) {
 766                 forNode(node->child1()).filter(SpecBoolean);
 767                 m_foundConstants = true;
 768                 break;
 769             }
 770         }
 771
 772         switch (node->child1().useKind()) {
 773         case StringUse:
 774         case CellUse:
 775             node->setCanExit(true);
 776             break;
 777         case UntypedUse:
 778             break;
 779         default:
 780             RELEASE_ASSERT_NOT_REACHED();
 781             break;
 782         }
 783         forNode(node).set(m_graph.m_vm.stringStructure.get());
 784         break;
 785     }
 786
 787     case CompareLess:
 788     case CompareLessEq:
 789     case CompareGreater:
 790     case CompareGreaterEq:
 791     case CompareEq:
 792     case CompareEqConstant: {
 793         bool constantWasSet = false;
 794
 795         JSValue leftConst = forNode(node->child1()).value();
 796         JSValue rightConst = forNode(node->child2()).value();
 797         if (leftConst && rightConst && leftConst.isNumber() && rightConst.isNumber()) {
 798             double a = leftConst.asNumber();
 799             double b = rightConst.asNumber();
 800             switch (node->op()) {
 801             case CompareLess:
 802                 constantWasSet = trySetConstant(node, jsBoolean(a < b));
 803                 break;
 804             case CompareLessEq:
 805                 constantWasSet = trySetConstant(node, jsBoolean(a <= b));
 806                 break;
 807             case CompareGreater:
 808                 constantWasSet = trySetConstant(node, jsBoolean(a > b));
 809                 break;
 810             case CompareGreaterEq:
 811                 constantWasSet = trySetConstant(node, jsBoolean(a >= b));
 812                 break;
 813             case CompareEq:
 814                 constantWasSet = trySetConstant(node, jsBoolean(a == b));
 815                 break;
 816             default:
 817                 RELEASE_ASSERT_NOT_REACHED();
 818                 constantWasSet = false;
 819                 break;
 820             }
 821         }
 822
 823         if (!constantWasSet && (node->op() == CompareEqConstant || node->op() == CompareEq)) {
 824             SpeculatedType leftType = forNode(node->child1()).m_type;
 825             SpeculatedType rightType = forNode(node->child2()).m_type;
 826             if ((isInt32Speculation(leftType) && isOtherSpeculation(rightType))
 827                 || (isOtherSpeculation(leftType) && isInt32Speculation(rightType)))
 828                 constantWasSet = trySetConstant(node, jsBoolean(false));
 829         }
 830
 831         if (constantWasSet) {
 832             m_foundConstants = true;
 833             break;
 834         }
 835
 836         forNode(node).set(SpecBoolean);
 837
 838         // This is overly conservative. But the only thing this prevents is store elimination,
 839         // and how likely is it, really, that you'll have redundant stores across a comparison
 840         // operation? Comparison operations are typically at the end of basic blocks, so
 841         // unless we have global store elimination (super unlikely given how unprofitable that
 842         // optimization is to begin with), you aren't going to be wanting to store eliminate
 843         // across an equality op.
 844         node->setCanExit(true);
 845         break;
 846     }
 847
 848     case CompareStrictEq:
 849     case CompareStrictEqConstant: {
 850         Node* leftNode = node->child1().node();
 851         Node* rightNode = node->child2().node();
 852         JSValue left = forNode(leftNode).value();
 853         JSValue right = forNode(rightNode).value();
 854         if (left && right && left.isNumber() && right.isNumber()
 855             && trySetConstant(node, jsBoolean(left.asNumber() == right.asNumber()))) {
 856             m_foundConstants = true;
 857             break;
 858         }
 859         forNode(node).set(SpecBoolean);
 860         node->setCanExit(true); // This is overly conservative.
 861         break;
 862     }
 863
 864     case StringCharCodeAt:
 865         node->setCanExit(true);
 866         forNode(node).set(SpecInt32);
 867         break;
 868
 869     case StringFromCharCode:
 870         forNode(node).set(SpecString);
 871         break;
 872
 873     case StringCharAt:
 874         node->setCanExit(true);
 875         forNode(node).set(m_graph.m_vm.stringStructure.get());
 876         break;
 877
 878     case GetByVal: {
 879         node->setCanExit(true);
 880         switch (node->arrayMode().type()) {
 881         case Array::SelectUsingPredictions:
 882         case Array::Unprofiled:
 883         case Array::Undecided:
 884             RELEASE_ASSERT_NOT_REACHED();
 885             break;
 886         case Array::ForceExit:
 887             m_isValid = false;
 888             break;
 889         case Array::Generic:
 890             clobberWorld(node->codeOrigin, indexInBlock);
 891             forNode(node).makeTop();
 892             break;
 893         case Array::String:
 894             forNode(node).set(m_graph.m_vm.stringStructure.get());
 895             break;
 896         case Array::Arguments:
 897             forNode(node).makeTop();
 898             break;
 899         case Array::Int32:
 900             if (node->arrayMode().isOutOfBounds()) {
 901                 clobberWorld(node->codeOrigin, indexInBlock);
 902                 forNode(node).makeTop();
 903             } else
 904                 forNode(node).set(SpecInt32);
 905             break;
 906         case Array::Double:
 907             if (node->arrayMode().isOutOfBounds()) {
 908                 clobberWorld(node->codeOrigin, indexInBlock);
 909                 forNode(node).makeTop();
 910             } else if (node->arrayMode().isSaneChain())
 911                 forNode(node).set(SpecDouble);
 912             else
 913                 forNode(node).set(SpecDoubleReal);
 914             break;
 915         case Array::Contiguous:
 916         case Array::ArrayStorage:
 917         case Array::SlowPutArrayStorage:
 918             if (node->arrayMode().isOutOfBounds())
 919                 clobberWorld(node->codeOrigin, indexInBlock);
 920             forNode(node).makeTop();
 921             break;
 922         case Array::Int8Array:
 923             forNode(node).set(SpecInt32);
 924             break;
 925         case Array::Int16Array:
 926             forNode(node).set(SpecInt32);
 927             break;
 928         case Array::Int32Array:
 929             forNode(node).set(SpecInt32);
 930             break;
 931         case Array::Uint8Array:
 932             forNode(node).set(SpecInt32);
 933             break;
 934         case Array::Uint8ClampedArray:
 935             forNode(node).set(SpecInt32);
 936             break;
 937         case Array::Uint16Array:
 938             forNode(node).set(SpecInt32);
 939             break;
 940         case Array::Uint32Array:
 941             if (node->shouldSpeculateInteger())
 942                 forNode(node).set(SpecInt32);
 943             else
 944                 forNode(node).set(SpecDouble);
 945             break;
 946         case Array::Float32Array:
 947             forNode(node).set(SpecDouble);
 948             break;
 949         case Array::Float64Array:
 950             forNode(node).set(SpecDouble);
 951             break;
 952         default:
 953             RELEASE_ASSERT_NOT_REACHED();
 954             break;
 955         }
 956         break;
 957     }
 958
 959     case PutByVal:
 960     case PutByValAlias: {
 961         node->setCanExit(true);
 962         switch (node->arrayMode().modeForPut().type()) {
 963         case Array::ForceExit:
 964             m_isValid = false;
 965             break;
 966         case Array::Generic:
 967             clobberWorld(node->codeOrigin, indexInBlock);
 968             break;
 969         case Array::Int32:
 970             if (node->arrayMode().isOutOfBounds())
 971                 clobberWorld(node->codeOrigin, indexInBlock);
 972             break;
 973         case Array::Double:
 974             if (node->arrayMode().isOutOfBounds())
 975                 clobberWorld(node->codeOrigin, indexInBlock);
 976             break;
 977         case Array::Contiguous:
 978         case Array::ArrayStorage:
 979             if (node->arrayMode().isOutOfBounds())
 980                 clobberWorld(node->codeOrigin, indexInBlock);
 981             break;
 982         case Array::SlowPutArrayStorage:
 983             if (node->arrayMode().mayStoreToHole())
 984                 clobberWorld(node->codeOrigin, indexInBlock);
 985             break;
 986         default:
 987             break;
 988         }
 989         break;
 990     }
 991
 992     case ArrayPush:
 993         node->setCanExit(true);
 994         clobberWorld(node->codeOrigin, indexInBlock);
 995         forNode(node).set(SpecNumber);
 996         break;
 997
 998     case ArrayPop:
 999         node->setCanExit(true);
1000         clobberWorld(node->codeOrigin, indexInBlock);
1001         forNode(node).makeTop();
1002         break;
1003
1004     case RegExpExec:
1005         forNode(node).makeTop();
1006         break;
1007
1008     case RegExpTest:
1009         forNode(node).set(SpecBoolean);
1010         break;
1011
1012     case Jump:
1013         break;
1014
1015     case Branch: {
1016         Node* child = node->child1().node();
1017         BooleanResult result = booleanResult(node, forNode(child));
1018         if (result == DefinitelyTrue) {
1019             m_branchDirection = TakeTrue;
1020             break;
1021         }
1022         if (result == DefinitelyFalse) {
1023             m_branchDirection = TakeFalse;
1024             break;
1025         }
1026         // FIXME: The above handles the trivial cases of sparse conditional
1027         // constant propagation, but we can do better:
1028         // We can specialize the source variable's value on each direction of
1029         // the branch.
1030         node->setCanExit(true); // This is overly conservative.
1031         m_branchDirection = TakeBoth;
1032         break;
1033     }
1034
1035     case Return:
1036         m_isValid = false;
1037         break;
1038
1039     case Throw:
1040     case ThrowReferenceError:
1041         m_isValid = false;
1042         node->setCanExit(true);
1043         break;
1044
1045     case ToPrimitive: {
1046         JSValue childConst = forNode(node->child1()).value();
1047         if (childConst && childConst.isNumber() && trySetConstant(node, childConst)) {
1048             m_foundConstants = true;
1049             break;
1050         }
1051
1052         ASSERT(node->child1().useKind() == UntypedUse);
1053
1054         AbstractValue& source = forNode(node->child1());
1055         AbstractValue& destination = forNode(node);
1056
1057         // NB. The more canonical way of writing this would have been:
1058         //
1059         // destination = source;
1060         // if (destination.m_type & !(SpecNumber | SpecString | SpecBoolean)) {
1061         //     destination.filter(SpecNumber | SpecString | SpecBoolean);
1062         //     AbstractValue string;
1063         //     string.set(vm->stringStructure);
1064         //     destination.merge(string);
1065         // }
1066         //
1067         // The reason why this would, in most other cases, have been better is that
1068         // then destination would preserve any non-SpeculatedType knowledge of source.
1069         // As it stands, the code below forgets any non-SpeculatedType knowledge that
1070         // source would have had. Fortunately, though, for things like strings and
1071         // numbers and booleans, we don't care about the non-SpeculatedType knowedge:
1072         // the structure won't tell us anything we don't already know, and neither
1073         // will ArrayModes. And if the source was a meaningful constant then we
1074         // would have handled that above. Unfortunately, this does mean that
1075         // ToPrimitive will currently forget string constants. But that's not a big
1076         // deal since we don't do any optimization on those currently.
1077
1078         clobberWorld(node->codeOrigin, indexInBlock);
1079
1080         SpeculatedType type = source.m_type;
1081         if (type & ~(SpecNumber | SpecString | SpecBoolean))
1082             type = (SpecTop & ~SpecCell) | SpecString;
1083
1084         destination.set(type);
1085         break;
1086     }
1087
1088     case ToString: {
1089         switch (node->child1().useKind()) {
1090         case StringObjectUse:
1091             // This also filters that the StringObject has the primordial StringObject
1092             // structure.
1093             forNode(node->child1()).filter(m_graph.globalObjectFor(node->codeOrigin)->stringObjectStructure());
1094             node->setCanExit(true); // We could be more precise but it's likely not worth it.
1095             break;
1096         case StringOrStringObjectUse:
1097             node->setCanExit(true); // We could be more precise but it's likely not worth it.
1098             break;
1099         case CellUse:
1100         case UntypedUse:
1101             clobberWorld(node->codeOrigin, indexInBlock);
1102             break;
1103         default:
1104             RELEASE_ASSERT_NOT_REACHED();
1105             break;
1106         }
1107         forNode(node).set(m_graph.m_vm.stringStructure.get());
1108         break;
1109     }
1110
1111     case NewStringObject: {
1112         ASSERT(node->structure()->classInfo() == &StringObject::s_info);
1113         forNode(node).set(node->structure());
1114         break;
1115     }
1116
1117     case NewArray:
1118         node->setCanExit(true);
1119         forNode(node).set(m_graph.globalObjectFor(node->codeOrigin)->arrayStructureForIndexingTypeDuringAllocation(node->indexingType()));
1120         m_haveStructures = true;
1121         break;
1122
1123     case NewArrayBuffer:
1124         node->setCanExit(true);
1125         forNode(node).set(m_graph.globalObjectFor(node->codeOrigin)->arrayStructureForIndexingTypeDuringAllocation(node->indexingType()));
1126         m_haveStructures = true;
1127         break;
1128
1129     case NewArrayWithSize:
1130         node->setCanExit(true);
1131         forNode(node).set(SpecArray);
1132         m_haveStructures = true;
1133         break;
1134
1135     case NewRegexp:
1136         forNode(node).set(m_graph.globalObjectFor(node->codeOrigin)->regExpStructure());
1137         m_haveStructures = true;
1138         break;
1139
1140     case ConvertThis: {
1141         AbstractValue& source = forNode(node->child1());
1142         AbstractValue& destination = forNode(node);
1143
1144         destination = source;
1145         destination.merge(SpecObjectOther);
1146         break;
1147     }
1148
1149     case CreateThis: {
1150         forNode(node).set(SpecFinalObject);
1151         break;
1152     }
1153
1154     case AllocationProfileWatchpoint:
1155         node->setCanExit(true);
1156         break;
1157
1158     case NewObject:
1159         forNode(node).set(node->structure());
1160         m_haveStructures = true;
1161         break;
1162
1163     case CreateActivation:
1164         forNode(node).set(m_codeBlock->globalObjectFor(node->codeOrigin)->activationStructure());
1165         m_haveStructures = true;
1166         break;
1167
1168     case CreateArguments:
1169         forNode(node).set(m_codeBlock->globalObjectFor(node->codeOrigin)->argumentsStructure());
1170         m_haveStructures = true;
1171         break;
1172
1173     case TearOffActivation:
1174     case TearOffArguments:
1175         // Does nothing that is user-visible.
1176         break;
1177
1178     case CheckArgumentsNotCreated:
1179         if (isEmptySpeculation(
1180                 m_variables.operand(
1181                     m_graph.argumentsRegisterFor(node->codeOrigin)).m_type))
1182             m_foundConstants = true;
1183         else
1184             node->setCanExit(true);
1185         break;
1186
1187     case GetMyArgumentsLength:
1188         // We know that this executable does not escape its arguments, so we can optimize
1189         // the arguments a bit. Note that this is not sufficient to force constant folding
1190         // of GetMyArgumentsLength, because GetMyArgumentsLength is a clobbering operation.
1191         // We perform further optimizations on this later on.
1192         if (node->codeOrigin.inlineCallFrame)
1193             forNode(node).set(jsNumber(node->codeOrigin.inlineCallFrame->arguments.size() - 1));
1194         else
1195             forNode(node).set(SpecInt32);
1196         node->setCanExit(
1197             !isEmptySpeculation(
1198                 m_variables.operand(
1199                     m_graph.argumentsRegisterFor(node->codeOrigin)).m_type));
1200         break;
1201
1202     case GetMyArgumentsLengthSafe:
1203         // This potentially clobbers all structures if the arguments object had a getter
1204         // installed on the length property.
1205         clobberWorld(node->codeOrigin, indexInBlock);
1206         // We currently make no guarantee about what this returns because it does not
1207         // speculate that the length property is actually a length.
1208         forNode(node).makeTop();
1209         break;
1210
1211     case GetMyArgumentByVal:
1212         node->setCanExit(true);
1213         // We know that this executable does not escape its arguments, so we can optimize
1214         // the arguments a bit. Note that this ends up being further optimized by the
1215         // ArgumentsSimplificationPhase.
1216         forNode(node).makeTop();
1217         break;
1218
1219     case GetMyArgumentByValSafe:
1220         node->setCanExit(true);
1221         // This potentially clobbers all structures if the property we're accessing has
1222         // a getter. We don't speculate against this.
1223         clobberWorld(node->codeOrigin, indexInBlock);
1224         // And the result is unknown.
1225         forNode(node).makeTop();
1226         break;
1227
1228     case NewFunction: {
1229         AbstractValue& value = forNode(node);
1230         value = forNode(node->child1());
1231
1232         if (!(value.m_type & SpecEmpty)) {
1233             m_foundConstants = true;
1234             break;
1235         }
1236
1237         value.set((value.m_type & ~SpecEmpty) | SpecFunction);
1238         break;
1239     }
1240
1241     case NewFunctionExpression:
1242     case NewFunctionNoCheck:
1243         forNode(node).set(m_codeBlock->globalObjectFor(node->codeOrigin)->functionStructure());
1244         break;
1245
1246     case GetCallee:
1247         forNode(node).set(SpecFunction);
1248         break;
1249
1250     case SetCallee:
1251     case SetMyScope:
1252         break;
1253
1254     case GetScope: // FIXME: We could get rid of these if we know that the JSFunction is a constant. https://bugs.webkit.org/show_bug.cgi?id=106202
1255     case GetMyScope:
1256     case SkipTopScope:
1257         forNode(node).set(SpecObjectOther);
1258         break;
1259
1260     case SkipScope: {
1261         JSValue child = forNode(node->child1()).value();
1262         if (child && trySetConstant(node, JSValue(jsCast<JSScope*>(child.asCell())->next()))) {
1263             m_foundConstants = true;
1264             break;
1265         }
1266         forNode(node).set(SpecObjectOther);
1267         break;
1268     }
1269
1270     case GetScopeRegisters:
1271         forNode(node).clear(); // The result is not a JS value.
1272         break;
1273
1274     case GetScopedVar:
1275         forNode(node).makeTop();
1276         break;
1277
1278     case PutScopedVar:
1279         clobberCapturedVars(node->codeOrigin);
1280         break;
1281
1282     case GetById:
1283     case GetByIdFlush:
1284         node->setCanExit(true);
1285         if (!node->prediction()) {
1286             m_isValid = false;
1287             break;
1288         }
1289         if (isCellSpeculation(node->child1()->prediction())) {
1290             if (Structure* structure = forNode(node->child1()).bestProvenStructure()) {
1291                 GetByIdStatus status = GetByIdStatus::computeFor(
1292                     m_graph.m_vm, structure,
1293                     m_graph.m_codeBlock->identifier(node->identifierNumber()));
1294                 if (status.isSimple()) {
1295                     // Assert things that we can't handle and that the computeFor() method
1296                     // above won't be able to return.
1297                     ASSERT(status.structureSet().size() == 1);
1298                     ASSERT(status.chain().isEmpty());
1299
1300                     if (status.specificValue())
1301                         forNode(node).set(status.specificValue());
1302                     else
1303                         forNode(node).makeTop();
1304                     forNode(node->child1()).filter(status.structureSet());
1305
1306                     m_foundConstants = true;
1307                     break;
1308                 }
1309             }
1310         }
1311         clobberWorld(node->codeOrigin, indexInBlock);
1312         forNode(node).makeTop();
1313         break;
1314
1315     case GetArrayLength:
1316         node->setCanExit(true); // Lies, but it's true for the common case of JSArray, so it's good enough.
1317         forNode(node).set(SpecInt32);
1318         break;
1319
1320     case CheckExecutable: {
1321         // FIXME: We could track executables in AbstractValue, which would allow us to get rid of these checks
1322         // more thoroughly. https://bugs.webkit.org/show_bug.cgi?id=106200
1323         // FIXME: We could eliminate these entirely if we know the exact value that flows into this.
1324         // https://bugs.webkit.org/show_bug.cgi?id=106201
1325         node->setCanExit(true);
1326         break;
1327     }
1328
1329     case CheckStructure:
1330     case ForwardCheckStructure: {
1331         // FIXME: We should be able to propagate the structure sets of constants (i.e. prototypes).
1332         AbstractValue& value = forNode(node->child1());
1333         ASSERT(!(value.m_type & ~SpecCell)); // Edge filtering should have already ensured this.
1334         // If this structure check is attempting to prove knowledge already held in
1335         // the futurePossibleStructure set then the constant folding phase should
1336         // turn this into a watchpoint instead.
1337         StructureSet& set = node->structureSet();
1338         if (value.m_futurePossibleStructure.isSubsetOf(set)
1339             || value.m_currentKnownStructure.isSubsetOf(set))
1340             m_foundConstants = true;
1341         if (!value.m_currentKnownStructure.isSubsetOf(set))
1342             node->setCanExit(true);
1343         value.filter(set);
1344         m_haveStructures = true;
1345         break;
1346     }
1347
1348     case StructureTransitionWatchpoint:
1349     case ForwardStructureTransitionWatchpoint: {
1350         AbstractValue& value = forNode(node->child1());
1351
1352         // It's only valid to issue a structure transition watchpoint if we already
1353         // know that the watchpoint covers a superset of the structures known to
1354         // belong to the set of future structures that this value may have.
1355         // Currently, we only issue singleton watchpoints (that check one structure)
1356         // and our futurePossibleStructure set can only contain zero, one, or an
1357         // infinity of structures.
1358         ASSERT(value.m_futurePossibleStructure.isSubsetOf(StructureSet(node->structure())));
1359
1360         value.filter(node->structure());
1361         m_haveStructures = true;
1362         node->setCanExit(true);
1363         break;
1364     }
1365
1366     case PutStructure:
1367     case PhantomPutStructure:
1368         if (!forNode(node->child1()).m_currentKnownStructure.isClear()) {
1369             clobberStructures(indexInBlock);
1370             forNode(node->child1()).set(node->structureTransitionData().newStructure);
1371             m_haveStructures = true;
1372         }
1373         break;
1374     case GetButterfly:
1375     case AllocatePropertyStorage:
1376     case ReallocatePropertyStorage:
1377         forNode(node).clear(); // The result is not a JS value.
1378         break;
1379     case CheckArray: {
1380         if (node->arrayMode().alreadyChecked(m_graph, node, forNode(node->child1()))) {
1381             m_foundConstants = true;
1382             break;
1383         }
1384         node->setCanExit(true); // Lies, but this is followed by operations (like GetByVal) that always exit, so there is no point in us trying to be clever here.
1385         switch (node->arrayMode().type()) {
1386         case Array::String:
1387             forNode(node->child1()).filter(SpecString);
1388             break;
1389         case Array::Int32:
1390         case Array::Double:
1391         case Array::Contiguous:
1392         case Array::ArrayStorage:
1393         case Array::SlowPutArrayStorage:
1394             break;
1395         case Array::Arguments:
1396             forNode(node->child1()).filter(SpecArguments);
1397             break;
1398         case Array::Int8Array:
1399             forNode(node->child1()).filter(SpecInt8Array);
1400             break;
1401         case Array::Int16Array:
1402             forNode(node->child1()).filter(SpecInt16Array);
1403             break;
1404         case Array::Int32Array:
1405             forNode(node->child1()).filter(SpecInt32Array);
1406             break;
1407         case Array::Uint8Array:
1408             forNode(node->child1()).filter(SpecUint8Array);
1409             break;
1410         case Array::Uint8ClampedArray:
1411             forNode(node->child1()).filter(SpecUint8ClampedArray);
1412             break;
1413         case Array::Uint16Array:
1414             forNode(node->child1()).filter(SpecUint16Array);
1415             break;
1416         case Array::Uint32Array:
1417             forNode(node->child1()).filter(SpecUint32Array);
1418             break;
1419         case Array::Float32Array:
1420             forNode(node->child1()).filter(SpecFloat32Array);
1421             break;
1422         case Array::Float64Array:
1423             forNode(node->child1()).filter(SpecFloat64Array);
1424             break;
1425         default:
1426             RELEASE_ASSERT_NOT_REACHED();
1427             break;
1428         }
1429         forNode(node->child1()).filterArrayModes(node->arrayMode().arrayModesThatPassFiltering());
1430         m_haveStructures = true;
1431         break;
1432     }
1433     case Arrayify: {
1434         if (node->arrayMode().alreadyChecked(m_graph, node, forNode(node->child1()))) {
1435             m_foundConstants = true;
1436             break;
1437         }
1438         ASSERT(node->arrayMode().conversion() == Array::Convert
1439             || node->arrayMode().conversion() == Array::RageConvert);
1440         node->setCanExit(true);
1441         clobberStructures(indexInBlock);
1442         forNode(node->child1()).filterArrayModes(node->arrayMode().arrayModesThatPassFiltering());
1443         m_haveStructures = true;
1444         break;
1445     }
1446     case ArrayifyToStructure: {
1447         AbstractValue& value = forNode(node->child1());
1448         StructureSet set = node->structure();
1449         if (value.m_futurePossibleStructure.isSubsetOf(set)
1450             || value.m_currentKnownStructure.isSubsetOf(set))
1451             m_foundConstants = true;
1452         node->setCanExit(true);
1453         clobberStructures(indexInBlock);
1454         value.filter(set);
1455         m_haveStructures = true;
1456         break;
1457     }
1458     case GetIndexedPropertyStorage: {
1459         forNode(node).clear();
1460         break;
1461     }
1462     case GetByOffset: {
1463         forNode(node).makeTop();
1464         break;
1465     }
1466
1467     case PutByOffset: {
1468         break;
1469     }
1470
1471     case CheckFunction: {
1472         JSValue value = forNode(node->child1()).value();
1473         if (value == node->function()) {
1474             m_foundConstants = true;
1475             ASSERT(value);
1476             break;
1477         }
1478
1479         node->setCanExit(true); // Lies! We can do better.
1480         forNode(node->child1()).filterByValue(node->function());
1481         break;
1482     }
1483
1484     case PutById:
1485     case PutByIdDirect:
1486         node->setCanExit(true);
1487         if (Structure* structure = forNode(node->child1()).bestProvenStructure()) {
1488             PutByIdStatus status = PutByIdStatus::computeFor(
1489                 m_graph.m_vm,
1490                 m_graph.globalObjectFor(node->codeOrigin),
1491                 structure,
1492                 m_graph.m_codeBlock->identifier(node->identifierNumber()),
1493                 node->op() == PutByIdDirect);
1494             if (status.isSimpleReplace()) {
1495                 forNode(node->child1()).filter(structure);
1496                 m_foundConstants = true;
1497                 break;
1498             }
1499             if (status.isSimpleTransition()) {
1500                 clobberStructures(indexInBlock);
1501                 forNode(node->child1()).set(status.newStructure());
1502                 m_haveStructures = true;
1503                 m_foundConstants = true;
1504                 break;
1505             }
1506         }
1507         clobberWorld(node->codeOrigin, indexInBlock);
1508         break;
1509
1510     case GetGlobalVar:
1511         forNode(node).makeTop();
1512         break;
1513
1514     case GlobalVarWatchpoint:
1515         node->setCanExit(true);
1516         break;
1517
1518     case PutGlobalVar:
1519     case PutGlobalVarCheck:
1520         break;
1521
1522     case CheckHasInstance:
1523         node->setCanExit(true);
1524         // Sadly, we don't propagate the fact that we've done CheckHasInstance
1525         break;
1526
1527     case InstanceOf:
1528         node->setCanExit(true);
1529         // Again, sadly, we don't propagate the fact that we've done InstanceOf
1530         forNode(node).set(SpecBoolean);
1531         break;
1532
1533     case Phi:
1534     case Flush:
1535     case PhantomLocal:
1536     case Breakpoint:
1537         break;
1538
1539     case Call:
1540     case Construct:
1541     case Resolve:
1542     case ResolveBase:
1543     case ResolveBaseStrictPut:
1544     case ResolveGlobal:
1545         node->setCanExit(true);
1546         clobberWorld(node->codeOrigin, indexInBlock);
1547         forNode(node).makeTop();
1548         break;
1549
1550     case GarbageValue:
1551         clobberWorld(node->codeOrigin, indexInBlock);
1552         forNode(node).makeTop();
1553         break;
1554
1555     case ForceOSRExit:
1556         node->setCanExit(true);
1557         m_isValid = false;
1558         break;
1559
1560     case CheckWatchdogTimer:
1561         node->setCanExit(true);
1562         break;
1563
1564     case Phantom:
1565     case InlineStart:
1566     case Nop:
1567     case CountExecution:
1568         break;
1569
1570     case LastNodeType:
1571         RELEASE_ASSERT_NOT_REACHED();
1572         break;
1573     }
1574
1575     return m_isValid;
1576 }
1577
1578 bool AbstractState::executeEffects(unsigned indexInBlock)
1579 {
1580     return executeEffects(indexInBlock, m_block->at(indexInBlock));
1581 }
1582
1583 bool AbstractState::execute(unsigned indexInBlock)
1584 {
1585     Node* node = m_block->at(indexInBlock);
1586     if (!startExecuting(node))
1587         return true;
1588
1589     executeEdges(node);
1590     return executeEffects(indexInBlock, node);
1591 }
1592
1593 inline void AbstractState::clobberWorld(const CodeOrigin& codeOrigin, unsigned indexInBlock)
1594 {
1595     clobberCapturedVars(codeOrigin);
1596     clobberStructures(indexInBlock);
1597 }
1598
1599 inline void AbstractState::clobberCapturedVars(const CodeOrigin& codeOrigin)
1600 {
1601     if (codeOrigin.inlineCallFrame) {
1602         const BitVector& capturedVars = codeOrigin.inlineCallFrame->capturedVars;
1603         for (size_t i = capturedVars.size(); i--;) {
1604             if (!capturedVars.quickGet(i))
1605                 continue;
1606             m_variables.local(i).makeTop();
1607         }
1608     } else {
1609         for (size_t i = m_codeBlock->m_numVars; i--;) {
1610             if (m_codeBlock->isCaptured(i))
1611                 m_variables.local(i).makeTop();
1612         }
1613     }
1614
1615     for (size_t i = m_variables.numberOfArguments(); i--;) {
1616         if (m_codeBlock->isCaptured(argumentToOperand(i)))
1617             m_variables.argument(i).makeTop();
1618     }
1619 }
1620
1621 inline void AbstractState::clobberStructures(unsigned indexInBlock)
1622 {
1623     if (!m_haveStructures)
1624         return;
1625     for (size_t i = indexInBlock + 1; i--;)
1626         forNode(m_block->at(i)).clobberStructures();
1627     for (size_t i = m_variables.numberOfArguments(); i--;)
1628         m_variables.argument(i).clobberStructures();
1629     for (size_t i = m_variables.numberOfLocals(); i--;)
1630         m_variables.local(i).clobberStructures();
1631     m_haveStructures = false;
1632     m_didClobber = true;
1633 }
1634
1635 inline bool AbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, Node* node)
1636 {
1637     if (!node)
1638         return false;
1639
1640     AbstractValue source;
1641
1642     if (node->variableAccessData()->isCaptured()) {
1643         // If it's captured then we know that whatever value was stored into the variable last is the
1644         // one we care about. This is true even if the variable at tail is dead, which might happen if
1645         // the last thing we did to the variable was a GetLocal and then ended up now using the
1646         // GetLocal's result.
1647
1648         source = inVariable;
1649 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1650         dataLogF("          Transfering ");
1651         source.dump(WTF::dataFile());
1652         dataLogF(" from last access due to captured variable.\n");
1653 #endif
1654     } else {
1655 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1656         dataLogF("          It's live, node @%u.\n", node->index());
1657 #endif
1658
1659         switch (node->op()) {
1660         case Phi:
1661         case SetArgument:
1662         case PhantomLocal:
1663         case Flush:
1664             // The block transfers the value from head to tail.
1665             source = inVariable;
1666 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1667             dataLogF("          Transfering ");
1668             source.dump(WTF::dataFile());
1669             dataLogF(" from head to tail.\n");
1670 #endif
1671             break;
1672
1673         case GetLocal:
1674             // The block refines the value with additional speculations.
1675             source = forNode(node);
1676 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1677             dataLogF("          Refining to ");
1678             source.dump(WTF::dataFile());
1679             dataLogF("\n");
1680 #endif
1681             break;
1682
1683         case SetLocal:
1684             // The block sets the variable, and potentially refines it, both
1685             // before and after setting it.
1686             if (node->variableAccessData()->shouldUseDoubleFormat()) {
1687                 // FIXME: This unnecessarily loses precision.
1688                 source.set(SpecDouble);
1689             } else
1690                 source = forNode(node->child1());
1691 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1692             dataLogF("          Setting to ");
1693             source.dump(WTF::dataFile());
1694             dataLogF("\n");
1695 #endif
1696             break;
1697
1698         default:
1699             RELEASE_ASSERT_NOT_REACHED();
1700             break;
1701         }
1702     }
1703
1704     if (destination == source) {
1705         // Abstract execution did not change the output value of the variable, for this
1706         // basic block, on this iteration.
1707 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1708         dataLogF("          Not changed!\n");
1709 #endif
1710         return false;
1711     }
1712
1713     // Abstract execution reached a new conclusion about the speculations reached about
1714     // this variable after execution of this basic block. Update the state, and return
1715     // true to indicate that the fixpoint must go on!
1716     destination = source;
1717 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1718     dataLogF("          Changed!\n");
1719 #endif
1720     return true;
1721 }
1722
1723 inline bool AbstractState::merge(BasicBlock* from, BasicBlock* to)
1724 {
1725     ASSERT(from->variablesAtTail.numberOfArguments() == to->variablesAtHead.numberOfArguments());
1726     ASSERT(from->variablesAtTail.numberOfLocals() == to->variablesAtHead.numberOfLocals());
1727
1728     bool changed = false;
1729
1730     for (size_t argument = 0; argument < from->variablesAtTail.numberOfArguments(); ++argument) {
1731         AbstractValue& destination = to->valuesAtHead.argument(argument);
1732         changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.argument(argument), to->variablesAtHead.argument(argument), from->variablesAtTail.argument(argument));
1733     }
1734
1735     for (size_t local = 0; local < from->variablesAtTail.numberOfLocals(); ++local) {
1736         AbstractValue& destination = to->valuesAtHead.local(local);
1737         changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.local(local), to->variablesAtHead.local(local), from->variablesAtTail.local(local));
1738     }
1739
1740     if (!to->cfaHasVisited)
1741         changed = true;
1742
1743     to->cfaShouldRevisit |= changed;
1744
1745     return changed;
1746 }
1747
1748 inline bool AbstractState::mergeToSuccessors(Graph& graph, BasicBlock* basicBlock)
1749 {
1750     Node* terminal = basicBlock->last();
1751
1752     ASSERT(terminal->isTerminal());
1753
1754     switch (terminal->op()) {
1755     case Jump: {
1756         ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
1757 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1758         dataLogF("        Merging to block #%u.\n", terminal->takenBlockIndex());
1759 #endif
1760         return merge(basicBlock, graph.m_blocks[terminal->takenBlockIndex()].get());
1761     }
1762
1763     case Branch: {
1764         ASSERT(basicBlock->cfaBranchDirection != InvalidBranchDirection);
1765         bool changed = false;
1766 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1767         dataLogF("        Merging to block #%u.\n", terminal->takenBlockIndex());
1768 #endif
1769         if (basicBlock->cfaBranchDirection != TakeFalse)
1770             changed |= merge(basicBlock, graph.m_blocks[terminal->takenBlockIndex()].get());
1771 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1772         dataLogF("        Merging to block #%u.\n", terminal->notTakenBlockIndex());
1773 #endif
1774         if (basicBlock->cfaBranchDirection != TakeTrue)
1775             changed |= merge(basicBlock, graph.m_blocks[terminal->notTakenBlockIndex()].get());
1776         return changed;
1777     }
1778
1779     case Return:
1780     case Throw:
1781     case ThrowReferenceError:
1782         ASSERT(basicBlock->cfaBranchDirection == InvalidBranchDirection);
1783         return false;
1784
1785     default:
1786         RELEASE_ASSERT_NOT_REACHED();
1787         return false;
1788     }
1789 }
1790
1791 inline bool AbstractState::mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, Node* destinationNode, Node* sourceNode)
1792 {
1793     if (!destinationNode)
1794         return false;
1795
1796     ASSERT_UNUSED(sourceNode, sourceNode);
1797
1798     // FIXME: We could do some sparse conditional propagation here!
1799
1800     return destination.merge(source);
1801 }
1802
1803 void AbstractState::dump(PrintStream& out)
1804 {
1805     bool first = true;
1806     for (size_t i = 0; i < m_block->size(); ++i) {
1807         Node* node = m_block->at(i);
1808         AbstractValue& value = forNode(node);
1809         if (value.isClear())
1810             continue;
1811         if (first)
1812             first = false;
1813         else
1814             out.printf(" ");
1815         out.printf("@%lu:", static_cast<unsigned long>(node->index()));
1816         value.dump(out);
1817     }
1818 }
1819
1820 } } // namespace JSC::DFG
1821
1822 #endif // ENABLE(DFG_JIT)
1823