Source/JavaScriptCore/dfg/DFGAbstractState.cpp

   1 /*
   2  * Copyright (C) 2011, 2012 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "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 AbstractState::AbstractState(Graph& graph)
  37     : m_codeBlock(graph.m_codeBlock)
  38     , m_graph(graph)
  39     , m_variables(m_codeBlock->numParameters(), graph.m_localVars)
  40     , m_block(0)
  41 {
  42     m_nodes.resize(graph.size());
  43 }
  44
  45 AbstractState::~AbstractState() { }
  46
  47 void AbstractState::beginBasicBlock(BasicBlock* basicBlock)
  48 {
  49     ASSERT(!m_block);
  50
  51     ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->valuesAtHead.numberOfLocals());
  52     ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals());
  53     ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals());
  54
  55     for (size_t i = 0; i < basicBlock->size(); i++)
  56         m_nodes[basicBlock->at(i)].clear();
  57
  58     m_variables = basicBlock->valuesAtHead;
  59     m_haveStructures = false;
  60     for (size_t i = 0; i < m_variables.numberOfArguments(); ++i) {
  61         if (m_variables.argument(i).m_structure.isNeitherClearNorTop()) {
  62             m_haveStructures = true;
  63             break;
  64         }
  65     }
  66     for (size_t i = 0; i < m_variables.numberOfLocals(); ++i) {
  67         if (m_variables.local(i).m_structure.isNeitherClearNorTop()) {
  68             m_haveStructures = true;
  69             break;
  70         }
  71     }
  72
  73     basicBlock->cfaShouldRevisit = false;
  74     basicBlock->cfaHasVisited = true;
  75     m_block = basicBlock;
  76     m_isValid = true;
  77     m_foundConstants = false;
  78     m_branchDirection = InvalidBranchDirection;
  79 }
  80
  81 void AbstractState::initialize(Graph& graph)
  82 {
  83     BasicBlock* root = graph.m_blocks[0].get();
  84     root->cfaShouldRevisit = true;
  85     root->cfaHasVisited = false;
  86     root->cfaFoundConstants = false;
  87     for (size_t i = 0; i < root->valuesAtHead.numberOfArguments(); ++i) {
  88         Node& node = graph[root->variablesAtHead.argument(i)];
  89         ASSERT(node.op() == SetArgument);
  90         if (!node.shouldGenerate()) {
  91             // The argument is dead. We don't do any checks for such arguments, and so
  92             // for the purpose of the analysis, they contain no value.
  93             root->valuesAtHead.argument(i).clear();
  94             continue;
  95         }
  96
  97         if (node.variableAccessData()->isCaptured()) {
  98             root->valuesAtHead.argument(i).makeTop();
  99             continue;
 100         }
 101
 102         SpeculatedType prediction = node.variableAccessData()->prediction();
 103         if (isInt32Speculation(prediction))
 104             root->valuesAtHead.argument(i).set(SpecInt32);
 105         else if (isArraySpeculation(prediction))
 106             root->valuesAtHead.argument(i).set(SpecArray);
 107         else if (isBooleanSpeculation(prediction))
 108             root->valuesAtHead.argument(i).set(SpecBoolean);
 109         else if (isInt8ArraySpeculation(prediction))
 110             root->valuesAtHead.argument(i).set(SpecInt8Array);
 111         else if (isInt16ArraySpeculation(prediction))
 112             root->valuesAtHead.argument(i).set(SpecInt16Array);
 113         else if (isInt32ArraySpeculation(prediction))
 114             root->valuesAtHead.argument(i).set(SpecInt32Array);
 115         else if (isUint8ArraySpeculation(prediction))
 116             root->valuesAtHead.argument(i).set(SpecUint8Array);
 117         else if (isUint8ClampedArraySpeculation(prediction))
 118             root->valuesAtHead.argument(i).set(SpecUint8ClampedArray);
 119         else if (isUint16ArraySpeculation(prediction))
 120             root->valuesAtHead.argument(i).set(SpecUint16Array);
 121         else if (isUint32ArraySpeculation(prediction))
 122             root->valuesAtHead.argument(i).set(SpecUint32Array);
 123         else if (isFloat32ArraySpeculation(prediction))
 124             root->valuesAtHead.argument(i).set(SpecFloat32Array);
 125         else if (isFloat64ArraySpeculation(prediction))
 126             root->valuesAtHead.argument(i).set(SpecFloat64Array);
 127         else
 128             root->valuesAtHead.argument(i).makeTop();
 129
 130         root->valuesAtTail.argument(i).clear();
 131     }
 132     for (size_t i = 0; i < root->valuesAtHead.numberOfLocals(); ++i) {
 133         NodeIndex nodeIndex = root->variablesAtHead.local(i);
 134         if (nodeIndex != NoNode && graph[nodeIndex].variableAccessData()->isCaptured())
 135             root->valuesAtHead.local(i).makeTop();
 136         else
 137             root->valuesAtHead.local(i).clear();
 138         root->valuesAtTail.local(i).clear();
 139     }
 140     for (BlockIndex blockIndex = 1 ; blockIndex < graph.m_blocks.size(); ++blockIndex) {
 141         BasicBlock* block = graph.m_blocks[blockIndex].get();
 142         if (!block)
 143             continue;
 144         if (!block->isReachable)
 145             continue;
 146         block->cfaShouldRevisit = false;
 147         block->cfaHasVisited = false;
 148         block->cfaFoundConstants = false;
 149         for (size_t i = 0; i < block->valuesAtHead.numberOfArguments(); ++i) {
 150             block->valuesAtHead.argument(i).clear();
 151             block->valuesAtTail.argument(i).clear();
 152         }
 153         for (size_t i = 0; i < block->valuesAtHead.numberOfLocals(); ++i) {
 154             block->valuesAtHead.local(i).clear();
 155             block->valuesAtTail.local(i).clear();
 156         }
 157     }
 158 }
 159
 160 bool AbstractState::endBasicBlock(MergeMode mergeMode, BranchDirection* branchDirectionPtr)
 161 {
 162     ASSERT(m_block);
 163
 164     BasicBlock* block = m_block; // Save the block for successor merging.
 165
 166     block->cfaFoundConstants = m_foundConstants;
 167
 168     if (!m_isValid) {
 169         reset();
 170         return false;
 171     }
 172
 173     bool changed = false;
 174
 175     if (mergeMode != DontMerge || !ASSERT_DISABLED) {
 176         for (size_t argument = 0; argument < block->variablesAtTail.numberOfArguments(); ++argument) {
 177 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 178             dataLog("        Merging state for argument %zu.\n", argument);
 179 #endif
 180             AbstractValue& destination = block->valuesAtTail.argument(argument);
 181             changed |= mergeStateAtTail(destination, m_variables.argument(argument), block->variablesAtTail.argument(argument));
 182         }
 183
 184         for (size_t local = 0; local < block->variablesAtTail.numberOfLocals(); ++local) {
 185 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 186             dataLog("        Merging state for local %zu.\n", local);
 187 #endif
 188             AbstractValue& destination = block->valuesAtTail.local(local);
 189             changed |= mergeStateAtTail(destination, m_variables.local(local), block->variablesAtTail.local(local));
 190         }
 191     }
 192
 193     ASSERT(mergeMode != DontMerge || !changed);
 194
 195     BranchDirection branchDirection = m_branchDirection;
 196     if (branchDirectionPtr)
 197         *branchDirectionPtr = branchDirection;
 198
 199 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 200     dataLog("        Branch direction = %s\n", branchDirectionToString(branchDirection));
 201 #endif
 202
 203     reset();
 204
 205     if (mergeMode != MergeToSuccessors)
 206         return changed;
 207
 208     return mergeToSuccessors(m_graph, block, branchDirection);
 209 }
 210
 211 void AbstractState::reset()
 212 {
 213     m_block = 0;
 214     m_isValid = false;
 215     m_branchDirection = InvalidBranchDirection;
 216 }
 217
 218 bool AbstractState::execute(unsigned indexInBlock)
 219 {
 220     ASSERT(m_block);
 221     ASSERT(m_isValid);
 222
 223     m_didClobber = false;
 224
 225     NodeIndex nodeIndex = m_block->at(indexInBlock);
 226     Node& node = m_graph[nodeIndex];
 227
 228     if (!node.shouldGenerate())
 229         return true;
 230
 231     switch (node.op()) {
 232     case JSConstant:
 233     case WeakJSConstant:
 234     case PhantomArguments: {
 235         forNode(nodeIndex).set(m_graph.valueOfJSConstant(nodeIndex));
 236         node.setCanExit(false);
 237         break;
 238     }
 239
 240     case GetLocal: {
 241         VariableAccessData* variableAccessData = node.variableAccessData();
 242         if (variableAccessData->prediction() == SpecNone) {
 243             m_isValid = false;
 244             node.setCanExit(true);
 245             break;
 246         }
 247         bool canExit = false;
 248         AbstractValue value = m_variables.operand(variableAccessData->local());
 249         if (!variableAccessData->isCaptured()) {
 250             if (value.isClear())
 251                 canExit |= true;
 252         }
 253         if (value.value())
 254             m_foundConstants = true;
 255         forNode(nodeIndex) = value;
 256         node.setCanExit(canExit);
 257         break;
 258     }
 259
 260     case GetLocalUnlinked: {
 261         AbstractValue value = m_variables.operand(node.unlinkedLocal());
 262         if (value.value())
 263             m_foundConstants = true;
 264         forNode(nodeIndex) = value;
 265         node.setCanExit(false);
 266         break;
 267     }
 268
 269     case SetLocal: {
 270         if (node.variableAccessData()->isCaptured()) {
 271             m_variables.operand(node.local()) = forNode(node.child1());
 272             node.setCanExit(false);
 273             break;
 274         }
 275
 276         if (node.variableAccessData()->shouldUseDoubleFormat()) {
 277             speculateNumberUnary(node);
 278             m_variables.operand(node.local()).set(SpecDouble);
 279             break;
 280         }
 281
 282         SpeculatedType predictedType = node.variableAccessData()->argumentAwarePrediction();
 283         if (isInt32Speculation(predictedType))
 284             speculateInt32Unary(node);
 285         else if (isArraySpeculation(predictedType)) {
 286             node.setCanExit(!isArraySpeculation(forNode(node.child1()).m_type));
 287             forNode(node.child1()).filter(SpecArray);
 288         } else if (isBooleanSpeculation(predictedType))
 289             speculateBooleanUnary(node);
 290         else
 291             node.setCanExit(false);
 292
 293         m_variables.operand(node.local()) = forNode(node.child1());
 294         break;
 295     }
 296
 297     case SetArgument:
 298         // Assert that the state of arguments has been set.
 299         ASSERT(!m_block->valuesAtHead.operand(node.local()).isClear());
 300         node.setCanExit(false);
 301         break;
 302
 303     case BitAnd:
 304     case BitOr:
 305     case BitXor:
 306     case BitRShift:
 307     case BitLShift:
 308     case BitURShift: {
 309         JSValue left = forNode(node.child1()).value();
 310         JSValue right = forNode(node.child2()).value();
 311         if (left && right && left.isInt32() && right.isInt32()) {
 312             int32_t a = left.asInt32();
 313             int32_t b = right.asInt32();
 314             switch (node.op()) {
 315             case BitAnd:
 316                 forNode(nodeIndex).set(JSValue(a & b));
 317                 break;
 318             case BitOr:
 319                 forNode(nodeIndex).set(JSValue(a | b));
 320                 break;
 321             case BitXor:
 322                 forNode(nodeIndex).set(JSValue(a ^ b));
 323                 break;
 324             case BitRShift:
 325                 forNode(nodeIndex).set(JSValue(a >> static_cast<uint32_t>(b)));
 326                 break;
 327             case BitLShift:
 328                 forNode(nodeIndex).set(JSValue(a << static_cast<uint32_t>(b)));
 329                 break;
 330             case BitURShift:
 331                 forNode(nodeIndex).set(JSValue(static_cast<uint32_t>(a) >> static_cast<uint32_t>(b)));
 332                 break;
 333             default:
 334                 ASSERT_NOT_REACHED();
 335             }
 336             m_foundConstants = true;
 337             node.setCanExit(false);
 338             break;
 339         }
 340         speculateInt32Binary(node);
 341         forNode(nodeIndex).set(SpecInt32);
 342         break;
 343     }
 344
 345     case UInt32ToNumber: {
 346         JSValue child = forNode(node.child1()).value();
 347         if (child && child.isNumber()) {
 348             ASSERT(child.isInt32());
 349             forNode(nodeIndex).set(JSValue(child.asUInt32()));
 350             m_foundConstants = true;
 351             node.setCanExit(false);
 352             break;
 353         }
 354         if (!node.canSpeculateInteger()) {
 355             forNode(nodeIndex).set(SpecDouble);
 356             node.setCanExit(false);
 357         } else {
 358             forNode(nodeIndex).set(SpecInt32);
 359             node.setCanExit(true);
 360         }
 361         break;
 362     }
 363
 364
 365     case DoubleAsInt32: {
 366         JSValue child = forNode(node.child1()).value();
 367         if (child && child.isNumber()) {
 368             double asDouble = child.asNumber();
 369             int32_t asInt = JSC::toInt32(asDouble);
 370             if (bitwise_cast<int64_t>(static_cast<double>(asInt)) == bitwise_cast<int64_t>(asDouble)) {
 371                 forNode(nodeIndex).set(JSValue(asInt));
 372                 m_foundConstants = true;
 373                 break;
 374             }
 375         }
 376         node.setCanExit(true);
 377         forNode(node.child1()).filter(SpecNumber);
 378         forNode(nodeIndex).set(SpecInt32);
 379         break;
 380     }
 381
 382     case ValueToInt32: {
 383         JSValue child = forNode(node.child1()).value();
 384         if (child && child.isNumber()) {
 385             if (child.isInt32())
 386                 forNode(nodeIndex).set(child);
 387             else
 388                 forNode(nodeIndex).set(JSValue(JSC::toInt32(child.asDouble())));
 389             m_foundConstants = true;
 390             node.setCanExit(false);
 391             break;
 392         }
 393         if (m_graph[node.child1()].shouldSpeculateInteger())
 394             speculateInt32Unary(node);
 395         else if (m_graph[node.child1()].shouldSpeculateNumber())
 396             speculateNumberUnary(node);
 397         else if (m_graph[node.child1()].shouldSpeculateBoolean())
 398             speculateBooleanUnary(node);
 399         else
 400             node.setCanExit(false);
 401
 402         forNode(nodeIndex).set(SpecInt32);
 403         break;
 404     }
 405
 406     case Int32ToDouble: {
 407         JSValue child = forNode(node.child1()).value();
 408         if (child && child.isNumber()) {
 409             forNode(nodeIndex).set(JSValue(JSValue::EncodeAsDouble, child.asNumber()));
 410             m_foundConstants = true;
 411             node.setCanExit(false);
 412             break;
 413         }
 414         speculateNumberUnary(node);
 415         forNode(nodeIndex).set(SpecDouble);
 416         break;
 417     }
 418
 419     case CheckNumber:
 420         forNode(node.child1()).filter(SpecNumber);
 421         break;
 422
 423     case ValueAdd:
 424     case ArithAdd: {
 425         JSValue left = forNode(node.child1()).value();
 426         JSValue right = forNode(node.child2()).value();
 427         if (left && right && left.isNumber() && right.isNumber()) {
 428             forNode(nodeIndex).set(JSValue(left.asNumber() + right.asNumber()));
 429             m_foundConstants = true;
 430             node.setCanExit(false);
 431             break;
 432         }
 433         if (m_graph.addShouldSpeculateInteger(node)) {
 434             speculateInt32Binary(
 435                 node, !nodeCanTruncateInteger(node.arithNodeFlags()));
 436             forNode(nodeIndex).set(SpecInt32);
 437             break;
 438         }
 439         if (Node::shouldSpeculateNumber(m_graph[node.child1()], m_graph[node.child2()])) {
 440             speculateNumberBinary(node);
 441             forNode(nodeIndex).set(SpecDouble);
 442             break;
 443         }
 444         if (node.op() == ValueAdd) {
 445             clobberWorld(node.codeOrigin, indexInBlock);
 446             forNode(nodeIndex).set(SpecString | SpecInt32 | SpecNumber);
 447             node.setCanExit(false);
 448             break;
 449         }
 450         // We don't handle this yet. :-(
 451         m_isValid = false;
 452         node.setCanExit(true);
 453         break;
 454     }
 455
 456     case ArithSub: {
 457         JSValue left = forNode(node.child1()).value();
 458         JSValue right = forNode(node.child2()).value();
 459         if (left && right && left.isNumber() && right.isNumber()) {
 460             forNode(nodeIndex).set(JSValue(left.asNumber() - right.asNumber()));
 461             m_foundConstants = true;
 462             node.setCanExit(false);
 463             break;
 464         }
 465         if (m_graph.addShouldSpeculateInteger(node)) {
 466             speculateInt32Binary(
 467                 node, !nodeCanTruncateInteger(node.arithNodeFlags()));
 468             forNode(nodeIndex).set(SpecInt32);
 469             break;
 470         }
 471         speculateNumberBinary(node);
 472         forNode(nodeIndex).set(SpecDouble);
 473         break;
 474     }
 475
 476     case ArithNegate: {
 477         JSValue child = forNode(node.child1()).value();
 478         if (child && child.isNumber()) {
 479             forNode(nodeIndex).set(JSValue(-child.asNumber()));
 480             m_foundConstants = true;
 481             node.setCanExit(false);
 482             break;
 483         }
 484         if (m_graph.negateShouldSpeculateInteger(node)) {
 485             speculateInt32Unary(
 486                 node, !nodeCanTruncateInteger(node.arithNodeFlags()));
 487             forNode(nodeIndex).set(SpecInt32);
 488             break;
 489         }
 490         speculateNumberUnary(node);
 491         forNode(nodeIndex).set(SpecDouble);
 492         break;
 493     }
 494
 495     case ArithMul: {
 496         JSValue left = forNode(node.child1()).value();
 497         JSValue right = forNode(node.child2()).value();
 498         if (left && right && left.isNumber() && right.isNumber()) {
 499             forNode(nodeIndex).set(JSValue(left.asNumber() * right.asNumber()));
 500             m_foundConstants = true;
 501             node.setCanExit(false);
 502             break;
 503         }
 504         if (m_graph.mulShouldSpeculateInteger(node)) {
 505             speculateInt32Binary(
 506                 node,
 507                 !nodeCanTruncateInteger(node.arithNodeFlags())
 508                 || !nodeCanIgnoreNegativeZero(node.arithNodeFlags()));
 509             forNode(nodeIndex).set(SpecInt32);
 510             break;
 511         }
 512         speculateNumberBinary(node);
 513         forNode(nodeIndex).set(SpecDouble);
 514         break;
 515     }
 516
 517     case ArithDiv:
 518     case ArithMin:
 519     case ArithMax:
 520     case ArithMod: {
 521         JSValue left = forNode(node.child1()).value();
 522         JSValue right = forNode(node.child2()).value();
 523         if (left && right && left.isNumber() && right.isNumber()) {
 524             double a = left.asNumber();
 525             double b = right.asNumber();
 526             switch (node.op()) {
 527             case ArithDiv:
 528                 forNode(nodeIndex).set(JSValue(a / b));
 529                 break;
 530             case ArithMin:
 531                 forNode(nodeIndex).set(JSValue(a < b ? a : (b <= a ? b : a + b)));
 532                 break;
 533             case ArithMax:
 534                 forNode(nodeIndex).set(JSValue(a > b ? a : (b >= a ? b : a + b)));
 535                 break;
 536             case ArithMod:
 537                 forNode(nodeIndex).set(JSValue(fmod(a, b)));
 538                 break;
 539             default:
 540                 ASSERT_NOT_REACHED();
 541                 break;
 542             }
 543             m_foundConstants = true;
 544             node.setCanExit(false);
 545             break;
 546         }
 547         if (Node::shouldSpeculateInteger(
 548                 m_graph[node.child1()], m_graph[node.child2()])
 549             && node.canSpeculateInteger()) {
 550             speculateInt32Binary(node, true); // forcing can-exit, which is a bit on the conservative side.
 551             forNode(nodeIndex).set(SpecInt32);
 552             break;
 553         }
 554         speculateNumberBinary(node);
 555         forNode(nodeIndex).set(SpecDouble);
 556         break;
 557     }
 558
 559     case ArithAbs: {
 560         JSValue child = forNode(node.child1()).value();
 561         if (child && child.isNumber()) {
 562             forNode(nodeIndex).set(JSValue(fabs(child.asNumber())));
 563             m_foundConstants = true;
 564             node.setCanExit(false);
 565             break;
 566         }
 567         if (m_graph[node.child1()].shouldSpeculateInteger()
 568             && node.canSpeculateInteger()) {
 569             speculateInt32Unary(node, true);
 570             forNode(nodeIndex).set(SpecInt32);
 571             break;
 572         }
 573         speculateNumberUnary(node);
 574         forNode(nodeIndex).set(SpecDouble);
 575         break;
 576     }
 577
 578     case ArithSqrt: {
 579         JSValue child = forNode(node.child1()).value();
 580         if (child && child.isNumber()) {
 581             forNode(nodeIndex).set(JSValue(sqrt(child.asNumber())));
 582             m_foundConstants = true;
 583             node.setCanExit(false);
 584             break;
 585         }
 586         speculateNumberUnary(node);
 587         forNode(nodeIndex).set(SpecDouble);
 588         break;
 589     }
 590
 591     case LogicalNot: {
 592         JSValue childConst = forNode(node.child1()).value();
 593         if (childConst) {
 594             forNode(nodeIndex).set(jsBoolean(!childConst.toBoolean()));
 595             node.setCanExit(false);
 596             break;
 597         }
 598         Node& child = m_graph[node.child1()];
 599         if (isBooleanSpeculation(child.prediction()))
 600             speculateBooleanUnary(node);
 601         else if (child.shouldSpeculateFinalObjectOrOther()) {
 602             node.setCanExit(
 603                 !isFinalObjectOrOtherSpeculation(forNode(node.child1()).m_type));
 604             forNode(node.child1()).filter(SpecFinalObject | SpecOther);
 605         } else if (child.shouldSpeculateArrayOrOther()) {
 606             node.setCanExit(
 607                 !isArrayOrOtherSpeculation(forNode(node.child1()).m_type));
 608             forNode(node.child1()).filter(SpecArray | SpecOther);
 609         } else if (child.shouldSpeculateInteger())
 610             speculateInt32Unary(node);
 611         else if (child.shouldSpeculateNumber())
 612             speculateNumberUnary(node);
 613         else
 614             node.setCanExit(false);
 615         forNode(nodeIndex).set(SpecBoolean);
 616         break;
 617     }
 618
 619     case IsUndefined:
 620     case IsBoolean:
 621     case IsNumber:
 622     case IsString:
 623     case IsObject:
 624     case IsFunction: {
 625         node.setCanExit(false);
 626         JSValue child = forNode(node.child1()).value();
 627         if (child) {
 628             bool foundConstant = true;
 629             switch (node.op()) {
 630             case IsUndefined:
 631                 forNode(nodeIndex).set(jsBoolean(
 632                     child.isCell()
 633                     ? child.asCell()->structure()->typeInfo().masqueradesAsUndefined()
 634                     : child.isUndefined()));
 635                 break;
 636             case IsBoolean:
 637                 forNode(nodeIndex).set(jsBoolean(child.isBoolean()));
 638                 break;
 639             case IsNumber:
 640                 forNode(nodeIndex).set(jsBoolean(child.isNumber()));
 641                 break;
 642             case IsString:
 643                 forNode(nodeIndex).set(jsBoolean(isJSString(child)));
 644                 break;
 645             default:
 646                 break;
 647             }
 648             if (foundConstant) {
 649                 m_foundConstants = true;
 650                 break;
 651             }
 652         }
 653         forNode(nodeIndex).set(SpecBoolean);
 654         break;
 655     }
 656
 657     case CompareLess:
 658     case CompareLessEq:
 659     case CompareGreater:
 660     case CompareGreaterEq:
 661     case CompareEq: {
 662         JSValue leftConst = forNode(node.child1()).value();
 663         JSValue rightConst = forNode(node.child2()).value();
 664         if (leftConst && rightConst && leftConst.isNumber() && rightConst.isNumber()) {
 665             double a = leftConst.asNumber();
 666             double b = rightConst.asNumber();
 667             switch (node.op()) {
 668             case CompareLess:
 669                 forNode(nodeIndex).set(jsBoolean(a < b));
 670                 break;
 671             case CompareLessEq:
 672                 forNode(nodeIndex).set(jsBoolean(a <= b));
 673                 break;
 674             case CompareGreater:
 675                 forNode(nodeIndex).set(jsBoolean(a > b));
 676                 break;
 677             case CompareGreaterEq:
 678                 forNode(nodeIndex).set(jsBoolean(a >= b));
 679                 break;
 680             case CompareEq:
 681                 forNode(nodeIndex).set(jsBoolean(a == b));
 682                 break;
 683             default:
 684                 ASSERT_NOT_REACHED();
 685                 break;
 686             }
 687             m_foundConstants = true;
 688             node.setCanExit(false);
 689             break;
 690         }
 691
 692         forNode(nodeIndex).set(SpecBoolean);
 693
 694         Node& left = m_graph[node.child1()];
 695         Node& right = m_graph[node.child2()];
 696         SpeculatedType filter;
 697         SpeculatedTypeChecker checker;
 698         if (Node::shouldSpeculateInteger(left, right)) {
 699             filter = SpecInt32;
 700             checker = isInt32Speculation;
 701         } else if (Node::shouldSpeculateNumber(left, right)) {
 702             filter = SpecNumber;
 703             checker = isNumberSpeculation;
 704         } else if (node.op() == CompareEq) {
 705             if ((m_graph.isConstant(node.child1().index())
 706                  && m_graph.valueOfJSConstant(node.child1().index()).isNull())
 707                 || (m_graph.isConstant(node.child2().index())
 708                     && m_graph.valueOfJSConstant(node.child2().index()).isNull())) {
 709                 // We know that this won't clobber the world. But that's all we know.
 710                 node.setCanExit(false);
 711                 break;
 712             }
 713
 714             if (Node::shouldSpeculateFinalObject(left, right)) {
 715                 filter = SpecFinalObject;
 716                 checker = isFinalObjectSpeculation;
 717             } else if (Node::shouldSpeculateArray(left, right)) {
 718                 filter = SpecArray;
 719                 checker = isArraySpeculation;
 720             } else if (left.shouldSpeculateFinalObject() && right.shouldSpeculateFinalObjectOrOther()) {
 721                 node.setCanExit(
 722                     !isFinalObjectSpeculation(forNode(node.child1()).m_type)
 723                     || !isFinalObjectOrOtherSpeculation(forNode(node.child2()).m_type));
 724                 forNode(node.child1()).filter(SpecFinalObject);
 725                 forNode(node.child2()).filter(SpecFinalObject | SpecOther);
 726                 break;
 727             } else if (right.shouldSpeculateFinalObject() && left.shouldSpeculateFinalObjectOrOther()) {
 728                 node.setCanExit(
 729                     !isFinalObjectOrOtherSpeculation(forNode(node.child1()).m_type)
 730                     || !isFinalObjectSpeculation(forNode(node.child2()).m_type));
 731                 forNode(node.child1()).filter(SpecFinalObject | SpecOther);
 732                 forNode(node.child2()).filter(SpecFinalObject);
 733                 break;
 734             } else if (left.shouldSpeculateArray() && right.shouldSpeculateArrayOrOther()) {
 735                 node.setCanExit(
 736                     !isArraySpeculation(forNode(node.child1()).m_type)
 737                     || !isArrayOrOtherSpeculation(forNode(node.child2()).m_type));
 738                 forNode(node.child1()).filter(SpecArray);
 739                 forNode(node.child2()).filter(SpecArray | SpecOther);
 740                 break;
 741             } else if (right.shouldSpeculateArray() && left.shouldSpeculateArrayOrOther()) {
 742                 node.setCanExit(
 743                     !isArrayOrOtherSpeculation(forNode(node.child1()).m_type)
 744                     || !isArraySpeculation(forNode(node.child2()).m_type));
 745                 forNode(node.child1()).filter(SpecArray | SpecOther);
 746                 forNode(node.child2()).filter(SpecArray);
 747                 break;
 748             } else {
 749                 filter = SpecTop;
 750                 checker = isAnySpeculation;
 751                 clobberWorld(node.codeOrigin, indexInBlock);
 752             }
 753         } else {
 754             filter = SpecTop;
 755             checker = isAnySpeculation;
 756             clobberWorld(node.codeOrigin, indexInBlock);
 757         }
 758         node.setCanExit(
 759             !checker(forNode(node.child1()).m_type)
 760             || !checker(forNode(node.child2()).m_type));
 761         forNode(node.child1()).filter(filter);
 762         forNode(node.child2()).filter(filter);
 763         break;
 764     }
 765
 766     case CompareStrictEq: {
 767         JSValue left = forNode(node.child1()).value();
 768         JSValue right = forNode(node.child2()).value();
 769         if (left && right && left.isNumber() && right.isNumber()) {
 770             forNode(nodeIndex).set(jsBoolean(left.asNumber() == right.asNumber()));
 771             m_foundConstants = true;
 772             node.setCanExit(false);
 773             break;
 774         }
 775         forNode(nodeIndex).set(SpecBoolean);
 776         if (m_graph.isJSConstant(node.child1().index())) {
 777             JSValue value = m_graph.valueOfJSConstant(node.child1().index());
 778             if (!value.isNumber() && !value.isString()) {
 779                 node.setCanExit(false);
 780                 break;
 781             }
 782         }
 783         if (m_graph.isJSConstant(node.child2().index())) {
 784             JSValue value = m_graph.valueOfJSConstant(node.child2().index());
 785             if (!value.isNumber() && !value.isString()) {
 786                 node.setCanExit(false);
 787                 break;
 788             }
 789         }
 790         if (Node::shouldSpeculateInteger(
 791                 m_graph[node.child1()], m_graph[node.child2()])) {
 792             speculateInt32Binary(node);
 793             break;
 794         }
 795         if (Node::shouldSpeculateNumber(
 796                 m_graph[node.child1()], m_graph[node.child2()])) {
 797             speculateNumberBinary(node);
 798             break;
 799         }
 800         if (Node::shouldSpeculateFinalObject(
 801                 m_graph[node.child1()], m_graph[node.child2()])) {
 802             node.setCanExit(
 803                 !isFinalObjectSpeculation(forNode(node.child1()).m_type)
 804                 || !isFinalObjectSpeculation(forNode(node.child2()).m_type));
 805             forNode(node.child1()).filter(SpecFinalObject);
 806             forNode(node.child2()).filter(SpecFinalObject);
 807             break;
 808         }
 809         if (Node::shouldSpeculateArray(
 810                 m_graph[node.child1()], m_graph[node.child2()])) {
 811             node.setCanExit(
 812                 !isArraySpeculation(forNode(node.child1()).m_type)
 813                 || !isArraySpeculation(forNode(node.child2()).m_type));
 814             forNode(node.child1()).filter(SpecArray);
 815             forNode(node.child2()).filter(SpecArray);
 816             break;
 817         }
 818         node.setCanExit(false);
 819         break;
 820     }
 821
 822     case StringCharCodeAt:
 823         node.setCanExit(true);
 824         forNode(node.child1()).filter(SpecString);
 825         forNode(node.child2()).filter(SpecInt32);
 826         forNode(nodeIndex).set(SpecInt32);
 827         break;
 828
 829     case StringCharAt:
 830         node.setCanExit(true);
 831         forNode(node.child1()).filter(SpecString);
 832         forNode(node.child2()).filter(SpecInt32);
 833         forNode(nodeIndex).set(SpecString);
 834         break;
 835
 836     case GetByVal: {
 837         node.setCanExit(true);
 838         if (!node.prediction() || !m_graph[node.child1()].prediction() || !m_graph[node.child2()].prediction()) {
 839             m_isValid = false;
 840             break;
 841         }
 842         if (!isActionableArraySpeculation(m_graph[node.child1()].prediction()) || !m_graph[node.child2()].shouldSpeculateInteger()) {
 843             clobberWorld(node.codeOrigin, indexInBlock);
 844             forNode(nodeIndex).makeTop();
 845             break;
 846         }
 847         if (m_graph[node.child1()].shouldSpeculateArguments()) {
 848             forNode(node.child1()).filter(SpecArguments);
 849             forNode(node.child2()).filter(SpecInt32);
 850             forNode(nodeIndex).makeTop();
 851             break;
 852         }
 853         if (m_graph[node.child1()].prediction() == SpecString) {
 854             forNode(node.child1()).filter(SpecString);
 855             forNode(node.child2()).filter(SpecInt32);
 856             forNode(nodeIndex).set(SpecString);
 857             break;
 858         }
 859
 860         if (m_graph[node.child1()].shouldSpeculateInt8Array()) {
 861             forNode(node.child1()).filter(SpecInt8Array);
 862             forNode(node.child2()).filter(SpecInt32);
 863             forNode(nodeIndex).set(SpecInt32);
 864             break;
 865         }
 866         if (m_graph[node.child1()].shouldSpeculateInt16Array()) {
 867             forNode(node.child1()).filter(SpecInt16Array);
 868             forNode(node.child2()).filter(SpecInt32);
 869             forNode(nodeIndex).set(SpecInt32);
 870             break;
 871         }
 872         if (m_graph[node.child1()].shouldSpeculateInt32Array()) {
 873             forNode(node.child1()).filter(SpecInt32Array);
 874             forNode(node.child2()).filter(SpecInt32);
 875             forNode(nodeIndex).set(SpecInt32);
 876             break;
 877         }
 878         if (m_graph[node.child1()].shouldSpeculateUint8Array()) {
 879             forNode(node.child1()).filter(SpecUint8Array);
 880             forNode(node.child2()).filter(SpecInt32);
 881             forNode(nodeIndex).set(SpecInt32);
 882             break;
 883         }
 884         if (m_graph[node.child1()].shouldSpeculateUint8ClampedArray()) {
 885             forNode(node.child1()).filter(SpecUint8ClampedArray);
 886             forNode(node.child2()).filter(SpecInt32);
 887             forNode(nodeIndex).set(SpecInt32);
 888             break;
 889         }
 890         if (m_graph[node.child1()].shouldSpeculateUint16Array()) {
 891             forNode(node.child1()).filter(SpecUint16Array);
 892             forNode(node.child2()).filter(SpecInt32);
 893             forNode(nodeIndex).set(SpecInt32);
 894             break;
 895         }
 896         if (m_graph[node.child1()].shouldSpeculateUint32Array()) {
 897             forNode(node.child1()).filter(SpecUint32Array);
 898             forNode(node.child2()).filter(SpecInt32);
 899             if (node.shouldSpeculateInteger())
 900                 forNode(nodeIndex).set(SpecInt32);
 901             else
 902                 forNode(nodeIndex).set(SpecDouble);
 903             break;
 904         }
 905         if (m_graph[node.child1()].shouldSpeculateFloat32Array()) {
 906             forNode(node.child1()).filter(SpecFloat32Array);
 907             forNode(node.child2()).filter(SpecInt32);
 908             forNode(nodeIndex).set(SpecDouble);
 909             break;
 910         }
 911         if (m_graph[node.child1()].shouldSpeculateFloat64Array()) {
 912             forNode(node.child1()).filter(SpecFloat64Array);
 913             forNode(node.child2()).filter(SpecInt32);
 914             forNode(nodeIndex).set(SpecDouble);
 915             break;
 916         }
 917         ASSERT(m_graph[node.child1()].shouldSpeculateArray());
 918         forNode(node.child1()).filter(SpecArray);
 919         forNode(node.child2()).filter(SpecInt32);
 920         forNode(nodeIndex).makeTop();
 921         break;
 922     }
 923
 924     case PutByVal:
 925     case PutByValAlias: {
 926         node.setCanExit(true);
 927         if (!m_graph[node.child1()].prediction() || !m_graph[node.child2()].prediction()) {
 928             m_isValid = false;
 929             break;
 930         }
 931         if (!m_graph[node.child2()].shouldSpeculateInteger() || !isActionableMutableArraySpeculation(m_graph[node.child1()].prediction())
 932 #if USE(JSVALUE32_64)
 933             || m_graph[node.child1()].shouldSpeculateArguments()
 934 #endif
 935             ) {
 936             ASSERT(node.op() == PutByVal);
 937             clobberWorld(node.codeOrigin, indexInBlock);
 938             forNode(nodeIndex).makeTop();
 939             break;
 940         }
 941
 942         if (m_graph[node.child1()].shouldSpeculateArguments()) {
 943             forNode(node.child1()).filter(SpecArguments);
 944             forNode(node.child2()).filter(SpecInt32);
 945             break;
 946         }
 947         if (m_graph[node.child1()].shouldSpeculateInt8Array()) {
 948             forNode(node.child1()).filter(SpecInt8Array);
 949             forNode(node.child2()).filter(SpecInt32);
 950             if (m_graph[node.child3()].shouldSpeculateInteger())
 951                 forNode(node.child3()).filter(SpecInt32);
 952             else
 953                 forNode(node.child3()).filter(SpecNumber);
 954             break;
 955         }
 956         if (m_graph[node.child1()].shouldSpeculateInt16Array()) {
 957             forNode(node.child1()).filter(SpecInt16Array);
 958             forNode(node.child2()).filter(SpecInt32);
 959             if (m_graph[node.child3()].shouldSpeculateInteger())
 960                 forNode(node.child3()).filter(SpecInt32);
 961             else
 962                 forNode(node.child3()).filter(SpecNumber);
 963             break;
 964         }
 965         if (m_graph[node.child1()].shouldSpeculateInt32Array()) {
 966             forNode(node.child1()).filter(SpecInt32Array);
 967             forNode(node.child2()).filter(SpecInt32);
 968             if (m_graph[node.child3()].shouldSpeculateInteger())
 969                 forNode(node.child3()).filter(SpecInt32);
 970             else
 971                 forNode(node.child3()).filter(SpecNumber);
 972             break;
 973         }
 974         if (m_graph[node.child1()].shouldSpeculateUint8Array()) {
 975             forNode(node.child1()).filter(SpecUint8Array);
 976             forNode(node.child2()).filter(SpecInt32);
 977             if (m_graph[node.child3()].shouldSpeculateInteger())
 978                 forNode(node.child3()).filter(SpecInt32);
 979             else
 980                 forNode(node.child3()).filter(SpecNumber);
 981             break;
 982         }
 983         if (m_graph[node.child1()].shouldSpeculateUint8ClampedArray()) {
 984             forNode(node.child1()).filter(SpecUint8ClampedArray);
 985             forNode(node.child2()).filter(SpecInt32);
 986             if (m_graph[node.child3()].shouldSpeculateInteger())
 987                 forNode(node.child3()).filter(SpecInt32);
 988             else
 989                 forNode(node.child3()).filter(SpecNumber);
 990             break;
 991         }
 992         if (m_graph[node.child1()].shouldSpeculateUint16Array()) {
 993             forNode(node.child1()).filter(SpecUint16Array);
 994             forNode(node.child2()).filter(SpecInt32);
 995             if (m_graph[node.child3()].shouldSpeculateInteger())
 996                 forNode(node.child3()).filter(SpecInt32);
 997             else
 998                 forNode(node.child3()).filter(SpecNumber);
 999             break;
1000         }
1001         if (m_graph[node.child1()].shouldSpeculateUint32Array()) {
1002             forNode(node.child1()).filter(SpecUint32Array);
1003             forNode(node.child2()).filter(SpecInt32);
1004             if (m_graph[node.child3()].shouldSpeculateInteger())
1005                 forNode(node.child3()).filter(SpecInt32);
1006             else
1007                 forNode(node.child3()).filter(SpecNumber);
1008             break;
1009         }
1010         if (m_graph[node.child1()].shouldSpeculateFloat32Array()) {
1011             forNode(node.child1()).filter(SpecFloat32Array);
1012             forNode(node.child2()).filter(SpecInt32);
1013             forNode(node.child3()).filter(SpecNumber);
1014             break;
1015         }
1016         if (m_graph[node.child1()].shouldSpeculateFloat64Array()) {
1017             forNode(node.child1()).filter(SpecFloat64Array);
1018             forNode(node.child2()).filter(SpecInt32);
1019             forNode(node.child3()).filter(SpecNumber);
1020             break;
1021         }
1022         ASSERT(m_graph[node.child1()].shouldSpeculateArray());
1023         forNode(node.child1()).filter(SpecArray);
1024         forNode(node.child2()).filter(SpecInt32);
1025         if (node.op() == PutByVal)
1026             clobberWorld(node.codeOrigin, indexInBlock);
1027         break;
1028     }
1029
1030     case ArrayPush:
1031         node.setCanExit(true);
1032         forNode(node.child1()).filter(SpecArray);
1033         forNode(nodeIndex).set(SpecNumber);
1034         break;
1035
1036     case ArrayPop:
1037         node.setCanExit(true);
1038         forNode(node.child1()).filter(SpecArray);
1039         forNode(nodeIndex).makeTop();
1040         break;
1041
1042     case RegExpExec:
1043     case RegExpTest:
1044         node.setCanExit(
1045             !isCellSpeculation(forNode(node.child1()).m_type)
1046             || !isCellSpeculation(forNode(node.child2()).m_type));
1047         forNode(node.child1()).filter(SpecCell);
1048         forNode(node.child2()).filter(SpecCell);
1049         forNode(nodeIndex).makeTop();
1050         break;
1051
1052     case Jump:
1053         node.setCanExit(false);
1054         break;
1055
1056     case Branch: {
1057         JSValue value = forNode(node.child1()).value();
1058         if (value) {
1059             bool booleanValue = value.toBoolean();
1060             if (booleanValue)
1061                 m_branchDirection = TakeTrue;
1062             else
1063                 m_branchDirection = TakeFalse;
1064             node.setCanExit(false);
1065             break;
1066         }
1067         // FIXME: The above handles the trivial cases of sparse conditional
1068         // constant propagation, but we can do better:
1069         // 1) If the abstract value does not have a concrete value but describes
1070         //    something that is known to evaluate true (or false) then we ought
1071         //    to sparse conditional that.
1072         // 2) We can specialize the source variable's value on each direction of
1073         //    the branch.
1074         Node& child = m_graph[node.child1()];
1075         if (child.shouldSpeculateBoolean())
1076             speculateBooleanUnary(node);
1077         else if (child.shouldSpeculateFinalObjectOrOther()) {
1078             node.setCanExit(
1079                 !isFinalObjectOrOtherSpeculation(forNode(node.child1()).m_type));
1080             forNode(node.child1()).filter(SpecFinalObject | SpecOther);
1081         } else if (child.shouldSpeculateArrayOrOther()) {
1082             node.setCanExit(
1083                 !isArrayOrOtherSpeculation(forNode(node.child1()).m_type));
1084             forNode(node.child1()).filter(SpecArray | SpecOther);
1085         } else if (child.shouldSpeculateInteger())
1086             speculateInt32Unary(node);
1087         else if (child.shouldSpeculateNumber())
1088             speculateNumberUnary(node);
1089         else
1090             node.setCanExit(false);
1091         m_branchDirection = TakeBoth;
1092         break;
1093     }
1094
1095     case Return:
1096         m_isValid = false;
1097         node.setCanExit(false);
1098         break;
1099
1100     case Throw:
1101     case ThrowReferenceError:
1102         m_isValid = false;
1103         node.setCanExit(true);
1104         break;
1105
1106     case ToPrimitive: {
1107         JSValue childConst = forNode(node.child1()).value();
1108         if (childConst && childConst.isNumber()) {
1109             forNode(nodeIndex).set(childConst);
1110             m_foundConstants = true;
1111             node.setCanExit(false);
1112             break;
1113         }
1114
1115         Node& child = m_graph[node.child1()];
1116         if (child.shouldSpeculateInteger()) {
1117             speculateInt32Unary(node);
1118             forNode(nodeIndex).set(SpecInt32);
1119             break;
1120         }
1121
1122         AbstractValue& source = forNode(node.child1());
1123         AbstractValue& destination = forNode(nodeIndex);
1124
1125         SpeculatedType type = source.m_type;
1126         if (type & ~(SpecNumber | SpecString | SpecBoolean)) {
1127             type &= (SpecNumber | SpecString | SpecBoolean);
1128             type |= SpecString;
1129         }
1130         destination.set(type);
1131         node.setCanExit(false);
1132         break;
1133     }
1134
1135     case StrCat:
1136         node.setCanExit(false);
1137         forNode(nodeIndex).set(SpecString);
1138         break;
1139
1140     case NewArray:
1141     case NewArrayBuffer:
1142         node.setCanExit(false);
1143         forNode(nodeIndex).set(m_codeBlock->globalObject()->arrayStructure());
1144         m_haveStructures = true;
1145         break;
1146
1147     case NewRegexp:
1148         node.setCanExit(false);
1149         forNode(nodeIndex).set(m_codeBlock->globalObject()->regExpStructure());
1150         m_haveStructures = true;
1151         break;
1152
1153     case ConvertThis: {
1154         Node& child = m_graph[node.child1()];
1155         AbstractValue& source = forNode(node.child1());
1156         AbstractValue& destination = forNode(nodeIndex);
1157
1158         if (isObjectSpeculation(source.m_type)) {
1159             // This is the simple case. We already know that the source is an
1160             // object, so there's nothing to do. I don't think this case will
1161             // be hit, but then again, you never know.
1162             destination = source;
1163             node.setCanExit(false);
1164             break;
1165         }
1166
1167         node.setCanExit(true);
1168
1169         if (isOtherSpeculation(child.prediction())) {
1170             source.filter(SpecOther);
1171             destination.set(SpecObjectOther);
1172             break;
1173         }
1174
1175         if (isObjectSpeculation(child.prediction())) {
1176             source.filter(SpecObjectMask);
1177             destination = source;
1178             break;
1179         }
1180
1181         destination = source;
1182         destination.merge(SpecObjectOther);
1183         break;
1184     }
1185
1186     case CreateThis: {
1187         AbstractValue& source = forNode(node.child1());
1188         AbstractValue& destination = forNode(nodeIndex);
1189
1190         node.setCanExit(!isCellSpeculation(source.m_type));
1191
1192         source.filter(SpecFunction);
1193         destination.set(SpecFinalObject);
1194         break;
1195     }
1196
1197     case NewObject:
1198         node.setCanExit(false);
1199         forNode(nodeIndex).set(m_codeBlock->globalObjectFor(node.codeOrigin)->emptyObjectStructure());
1200         m_haveStructures = true;
1201         break;
1202
1203     case CreateActivation:
1204         node.setCanExit(false);
1205         forNode(nodeIndex).set(m_graph.m_globalData.activationStructure.get());
1206         m_haveStructures = true;
1207         break;
1208
1209     case CreateArguments:
1210         node.setCanExit(false);
1211         forNode(nodeIndex).set(m_codeBlock->globalObjectFor(node.codeOrigin)->argumentsStructure());
1212         m_haveStructures = true;
1213         break;
1214
1215     case TearOffActivation:
1216     case TearOffArguments:
1217         node.setCanExit(false);
1218         // Does nothing that is user-visible.
1219         break;
1220
1221     case CheckArgumentsNotCreated:
1222         if (isEmptySpeculation(
1223                 m_variables.operand(
1224                     m_graph.argumentsRegisterFor(node.codeOrigin)).m_type)) {
1225             node.setCanExit(false);
1226             m_foundConstants = true;
1227         } else
1228             node.setCanExit(true);
1229         break;
1230
1231     case GetMyArgumentsLength:
1232         // We know that this executable does not escape its arguments, so we can optimize
1233         // the arguments a bit. Note that this is not sufficient to force constant folding
1234         // of GetMyArgumentsLength, because GetMyArgumentsLength is a clobbering operation.
1235         // We perform further optimizations on this later on.
1236         if (node.codeOrigin.inlineCallFrame)
1237             forNode(nodeIndex).set(jsNumber(node.codeOrigin.inlineCallFrame->arguments.size() - 1));
1238         else
1239             forNode(nodeIndex).set(SpecInt32);
1240         node.setCanExit(
1241             !isEmptySpeculation(
1242                 m_variables.operand(
1243                     m_graph.argumentsRegisterFor(node.codeOrigin)).m_type));
1244         break;
1245
1246     case GetMyArgumentsLengthSafe:
1247         node.setCanExit(false);
1248         // This potentially clobbers all structures if the arguments object had a getter
1249         // installed on the length property.
1250         clobberWorld(node.codeOrigin, indexInBlock);
1251         // We currently make no guarantee about what this returns because it does not
1252         // speculate that the length property is actually a length.
1253         forNode(nodeIndex).makeTop();
1254         break;
1255
1256     case GetMyArgumentByVal:
1257         node.setCanExit(true);
1258         // We know that this executable does not escape its arguments, so we can optimize
1259         // the arguments a bit. Note that this ends up being further optimized by the
1260         // ArgumentsSimplificationPhase.
1261         forNode(node.child1()).filter(SpecInt32);
1262         forNode(nodeIndex).makeTop();
1263         break;
1264
1265     case GetMyArgumentByValSafe:
1266         node.setCanExit(true);
1267         // This potentially clobbers all structures if the property we're accessing has
1268         // a getter. We don't speculate against this.
1269         clobberWorld(node.codeOrigin, indexInBlock);
1270         // But we do speculate that the index is an integer.
1271         forNode(node.child1()).filter(SpecInt32);
1272         // And the result is unknown.
1273         forNode(nodeIndex).makeTop();
1274         break;
1275
1276     case NewFunction:
1277     case NewFunctionExpression:
1278     case NewFunctionNoCheck:
1279         node.setCanExit(false);
1280         forNode(nodeIndex).set(m_codeBlock->globalObjectFor(node.codeOrigin)->functionStructure());
1281         break;
1282
1283     case GetCallee:
1284         node.setCanExit(false);
1285         forNode(nodeIndex).set(SpecFunction);
1286         break;
1287
1288     case GetScopeChain:
1289         node.setCanExit(false);
1290         forNode(nodeIndex).set(SpecCellOther);
1291         break;
1292
1293     case GetScopedVar:
1294         node.setCanExit(false);
1295         forNode(nodeIndex).makeTop();
1296         break;
1297
1298     case PutScopedVar:
1299         node.setCanExit(false);
1300         clobberStructures(indexInBlock);
1301         break;
1302
1303     case GetById:
1304     case GetByIdFlush:
1305         node.setCanExit(true);
1306         if (!node.prediction()) {
1307             m_isValid = false;
1308             break;
1309         }
1310         if (isCellSpeculation(m_graph[node.child1()].prediction()))
1311             forNode(node.child1()).filter(SpecCell);
1312         clobberWorld(node.codeOrigin, indexInBlock);
1313         forNode(nodeIndex).makeTop();
1314         break;
1315
1316     case GetArrayLength:
1317         node.setCanExit(true);
1318         forNode(node.child1()).filter(SpecArray);
1319         forNode(nodeIndex).set(SpecInt32);
1320         break;
1321
1322     case GetArgumentsLength:
1323         node.setCanExit(true);
1324         forNode(node.child1()).filter(SpecArguments);
1325         forNode(nodeIndex).set(SpecInt32);
1326         break;
1327
1328     case GetStringLength:
1329         node.setCanExit(!isStringSpeculation(forNode(node.child1()).m_type));
1330         forNode(node.child1()).filter(SpecString);
1331         forNode(nodeIndex).set(SpecInt32);
1332         break;
1333
1334     case GetInt8ArrayLength:
1335         node.setCanExit(!isInt8ArraySpeculation(forNode(node.child1()).m_type));
1336         forNode(node.child1()).filter(SpecInt8Array);
1337         forNode(nodeIndex).set(SpecInt32);
1338         break;
1339     case GetInt16ArrayLength:
1340         node.setCanExit(!isInt16ArraySpeculation(forNode(node.child1()).m_type));
1341         forNode(node.child1()).filter(SpecInt16Array);
1342         forNode(nodeIndex).set(SpecInt32);
1343         break;
1344     case GetInt32ArrayLength:
1345         node.setCanExit(!isInt32ArraySpeculation(forNode(node.child1()).m_type));
1346         forNode(node.child1()).filter(SpecInt32Array);
1347         forNode(nodeIndex).set(SpecInt32);
1348         break;
1349     case GetUint8ArrayLength:
1350         node.setCanExit(!isUint8ArraySpeculation(forNode(node.child1()).m_type));
1351         forNode(node.child1()).filter(SpecUint8Array);
1352         forNode(nodeIndex).set(SpecInt32);
1353         break;
1354     case GetUint8ClampedArrayLength:
1355         node.setCanExit(!isUint8ClampedArraySpeculation(forNode(node.child1()).m_type));
1356         forNode(node.child1()).filter(SpecUint8ClampedArray);
1357         forNode(nodeIndex).set(SpecInt32);
1358         break;
1359     case GetUint16ArrayLength:
1360         node.setCanExit(!isUint16ArraySpeculation(forNode(node.child1()).m_type));
1361         forNode(node.child1()).filter(SpecUint16Array);
1362         forNode(nodeIndex).set(SpecInt32);
1363         break;
1364     case GetUint32ArrayLength:
1365         node.setCanExit(!isUint32ArraySpeculation(forNode(node.child1()).m_type));
1366         forNode(node.child1()).filter(SpecUint32Array);
1367         forNode(nodeIndex).set(SpecInt32);
1368         break;
1369     case GetFloat32ArrayLength:
1370         node.setCanExit(!isFloat32ArraySpeculation(forNode(node.child1()).m_type));
1371         forNode(node.child1()).filter(SpecFloat32Array);
1372         forNode(nodeIndex).set(SpecInt32);
1373         break;
1374     case GetFloat64ArrayLength:
1375         node.setCanExit(!isFloat64ArraySpeculation(forNode(node.child1()).m_type));
1376         forNode(node.child1()).filter(SpecFloat64Array);
1377         forNode(nodeIndex).set(SpecInt32);
1378         break;
1379
1380     case CheckStructure: {
1381         // FIXME: We should be able to propagate the structure sets of constants (i.e. prototypes).
1382         AbstractValue& value = forNode(node.child1());
1383         node.setCanExit(
1384             !value.m_structure.isSubsetOf(node.structureSet())
1385             || !isCellSpeculation(value.m_type));
1386         value.filter(node.structureSet());
1387         m_haveStructures = true;
1388         break;
1389     }
1390
1391     case PutStructure:
1392     case PhantomPutStructure:
1393         node.setCanExit(false);
1394         clobberStructures(indexInBlock);
1395         forNode(node.child1()).set(node.structureTransitionData().newStructure);
1396         m_haveStructures = true;
1397         break;
1398     case GetPropertyStorage:
1399         node.setCanExit(false);
1400         forNode(node.child1()).filter(SpecCell);
1401         forNode(nodeIndex).clear(); // The result is not a JS value.
1402         break;
1403     case GetIndexedPropertyStorage: {
1404         node.setCanExit(true); // Lies, but this is (almost) always followed by GetByVal, which does exit. So no point in trying to be more precise.
1405         SpeculatedType basePrediction = m_graph[node.child2()].prediction();
1406         if (!(basePrediction & SpecInt32) && basePrediction) {
1407             forNode(nodeIndex).clear();
1408             break;
1409         }
1410         if (m_graph[node.child1()].shouldSpeculateArguments()) {
1411             ASSERT_NOT_REACHED();
1412             break;
1413         }
1414         if (m_graph[node.child1()].prediction() == SpecString) {
1415             forNode(node.child1()).filter(SpecString);
1416             forNode(nodeIndex).clear();
1417             break;
1418         }
1419
1420         if (m_graph[node.child1()].shouldSpeculateInt8Array()) {
1421             forNode(node.child1()).filter(SpecInt8Array);
1422             forNode(nodeIndex).clear();
1423             break;
1424         }
1425         if (m_graph[node.child1()].shouldSpeculateInt16Array()) {
1426             forNode(node.child1()).filter(SpecInt16Array);
1427             forNode(nodeIndex).clear();
1428             break;
1429         }
1430         if (m_graph[node.child1()].shouldSpeculateInt32Array()) {
1431             forNode(node.child1()).filter(SpecInt32Array);
1432             forNode(nodeIndex).clear();
1433             break;
1434         }
1435         if (m_graph[node.child1()].shouldSpeculateUint8Array()) {
1436             forNode(node.child1()).filter(SpecUint8Array);
1437             forNode(nodeIndex).clear();
1438             break;
1439         }
1440         if (m_graph[node.child1()].shouldSpeculateUint8ClampedArray()) {
1441             forNode(node.child1()).filter(SpecUint8ClampedArray);
1442             forNode(nodeIndex).clear();
1443             break;
1444         }
1445         if (m_graph[node.child1()].shouldSpeculateUint16Array()) {
1446             forNode(node.child1()).filter(SpecUint16Array);
1447             forNode(nodeIndex).set(SpecOther);
1448             break;
1449         }
1450         if (m_graph[node.child1()].shouldSpeculateUint32Array()) {
1451             forNode(node.child1()).filter(SpecUint32Array);
1452             forNode(nodeIndex).clear();
1453             break;
1454         }
1455         if (m_graph[node.child1()].shouldSpeculateFloat32Array()) {
1456             forNode(node.child1()).filter(SpecFloat32Array);
1457             forNode(nodeIndex).clear();
1458             break;
1459         }
1460         if (m_graph[node.child1()].shouldSpeculateFloat64Array()) {
1461             forNode(node.child1()).filter(SpecFloat64Array);
1462             forNode(nodeIndex).clear();
1463             break;
1464         }
1465         forNode(node.child1()).filter(SpecArray);
1466         forNode(nodeIndex).clear();
1467         break;
1468     }
1469     case GetByOffset:
1470         node.setCanExit(false);
1471         forNode(node.child1()).filter(SpecCell);
1472         forNode(nodeIndex).makeTop();
1473         break;
1474
1475     case PutByOffset:
1476         node.setCanExit(false);
1477         forNode(node.child1()).filter(SpecCell);
1478         break;
1479
1480     case CheckFunction:
1481         node.setCanExit(true); // Lies! We can do better.
1482         forNode(node.child1()).filter(SpecFunction);
1483         // FIXME: Should be able to propagate the fact that we know what the function is.
1484         break;
1485
1486     case PutById:
1487     case PutByIdDirect:
1488         node.setCanExit(true);
1489         forNode(node.child1()).filter(SpecCell);
1490         clobberWorld(node.codeOrigin, indexInBlock);
1491         break;
1492
1493     case GetGlobalVar:
1494         node.setCanExit(false);
1495         forNode(nodeIndex).makeTop();
1496         break;
1497
1498     case GlobalVarWatchpoint:
1499         node.setCanExit(true);
1500         break;
1501
1502     case PutGlobalVar:
1503     case PutGlobalVarCheck:
1504         node.setCanExit(false);
1505         break;
1506
1507     case CheckHasInstance:
1508         node.setCanExit(true);
1509         forNode(node.child1()).filter(SpecCell);
1510         // Sadly, we don't propagate the fact that we've done CheckHasInstance
1511         break;
1512
1513     case InstanceOf:
1514         node.setCanExit(true);
1515         // Again, sadly, we don't propagate the fact that we've done InstanceOf
1516         if (!(m_graph[node.child1()].prediction() & ~SpecCell) && !(forNode(node.child1()).m_type & ~SpecCell))
1517             forNode(node.child1()).filter(SpecCell);
1518         forNode(node.child3()).filter(SpecCell);
1519         forNode(nodeIndex).set(SpecBoolean);
1520         break;
1521
1522     case Phi:
1523     case Flush:
1524         node.setCanExit(false);
1525         break;
1526
1527     case Breakpoint:
1528         node.setCanExit(false);
1529         break;
1530
1531     case Call:
1532     case Construct:
1533     case Resolve:
1534     case ResolveBase:
1535     case ResolveBaseStrictPut:
1536     case ResolveGlobal:
1537         node.setCanExit(true);
1538         clobberWorld(node.codeOrigin, indexInBlock);
1539         forNode(nodeIndex).makeTop();
1540         break;
1541
1542     case ForceOSRExit:
1543         node.setCanExit(true);
1544         m_isValid = false;
1545         break;
1546
1547     case Phantom:
1548     case InlineStart:
1549     case Nop:
1550         node.setCanExit(false);
1551         break;
1552
1553     case LastNodeType:
1554         ASSERT_NOT_REACHED();
1555         break;
1556     }
1557
1558     return m_isValid;
1559 }
1560
1561 inline void AbstractState::clobberWorld(const CodeOrigin& codeOrigin, unsigned indexInBlock)
1562 {
1563     if (codeOrigin.inlineCallFrame) {
1564         const BitVector& capturedVars = codeOrigin.inlineCallFrame->capturedVars;
1565         for (size_t i = capturedVars.size(); i--;) {
1566             if (!capturedVars.quickGet(i))
1567                 continue;
1568             m_variables.local(i).makeTop();
1569         }
1570     } else {
1571         for (size_t i = m_codeBlock->m_numCapturedVars; i--;)
1572             m_variables.local(i).makeTop();
1573     }
1574     if (m_codeBlock->argumentsAreCaptured()) {
1575         for (size_t i = m_variables.numberOfArguments(); i--;)
1576             m_variables.argument(i).makeTop();
1577     }
1578     clobberStructures(indexInBlock);
1579 }
1580
1581 inline void AbstractState::clobberStructures(unsigned indexInBlock)
1582 {
1583     if (!m_haveStructures)
1584         return;
1585     for (size_t i = indexInBlock + 1; i--;)
1586         forNode(m_block->at(i)).clobberStructures();
1587     for (size_t i = m_variables.numberOfArguments(); i--;)
1588         m_variables.argument(i).clobberStructures();
1589     for (size_t i = m_variables.numberOfLocals(); i--;)
1590         m_variables.local(i).clobberStructures();
1591     m_haveStructures = false;
1592     m_didClobber = true;
1593 }
1594
1595 inline bool AbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, NodeIndex nodeIndex)
1596 {
1597     if (nodeIndex == NoNode)
1598         return false;
1599
1600     AbstractValue source;
1601
1602     Node& node = m_graph[nodeIndex];
1603     if (!node.refCount())
1604         return false;
1605
1606 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1607     dataLog("          It's live, node @%u.\n", nodeIndex);
1608 #endif
1609
1610     if (node.variableAccessData()->isCaptured()) {
1611         source = inVariable;
1612 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1613         dataLog("          Transfering ");
1614         source.dump(WTF::dataFile());
1615         dataLog(" from last access due to captured variable.\n");
1616 #endif
1617     } else {
1618         switch (node.op()) {
1619         case Phi:
1620         case SetArgument:
1621         case Flush:
1622             // The block transfers the value from head to tail.
1623             source = inVariable;
1624 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1625             dataLog("          Transfering ");
1626             source.dump(WTF::dataFile());
1627             dataLog(" from head to tail.\n");
1628 #endif
1629             break;
1630
1631         case GetLocal:
1632             // The block refines the value with additional speculations.
1633             source = forNode(nodeIndex);
1634 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1635             dataLog("          Refining to ");
1636             source.dump(WTF::dataFile());
1637             dataLog("\n");
1638 #endif
1639             break;
1640
1641         case SetLocal:
1642             // The block sets the variable, and potentially refines it, both
1643             // before and after setting it.
1644             if (node.variableAccessData()->shouldUseDoubleFormat()) {
1645                 // FIXME: This unnecessarily loses precision.
1646                 source.set(SpecDouble);
1647             } else
1648                 source = forNode(node.child1());
1649 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1650             dataLog("          Setting to ");
1651             source.dump(WTF::dataFile());
1652             dataLog("\n");
1653 #endif
1654             break;
1655
1656         default:
1657             ASSERT_NOT_REACHED();
1658             break;
1659         }
1660     }
1661
1662     if (destination == source) {
1663         // Abstract execution did not change the output value of the variable, for this
1664         // basic block, on this iteration.
1665 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1666         dataLog("          Not changed!\n");
1667 #endif
1668         return false;
1669     }
1670
1671     // Abstract execution reached a new conclusion about the speculations reached about
1672     // this variable after execution of this basic block. Update the state, and return
1673     // true to indicate that the fixpoint must go on!
1674     destination = source;
1675 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1676     dataLog("          Changed!\n");
1677 #endif
1678     return true;
1679 }
1680
1681 inline bool AbstractState::merge(BasicBlock* from, BasicBlock* to)
1682 {
1683     ASSERT(from->variablesAtTail.numberOfArguments() == to->variablesAtHead.numberOfArguments());
1684     ASSERT(from->variablesAtTail.numberOfLocals() == to->variablesAtHead.numberOfLocals());
1685
1686     bool changed = false;
1687
1688     for (size_t argument = 0; argument < from->variablesAtTail.numberOfArguments(); ++argument) {
1689         AbstractValue& destination = to->valuesAtHead.argument(argument);
1690         changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.argument(argument), to->variablesAtHead.argument(argument), from->variablesAtTail.argument(argument));
1691     }
1692
1693     for (size_t local = 0; local < from->variablesAtTail.numberOfLocals(); ++local) {
1694         AbstractValue& destination = to->valuesAtHead.local(local);
1695         changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.local(local), to->variablesAtHead.local(local), from->variablesAtTail.local(local));
1696     }
1697
1698     if (!to->cfaHasVisited)
1699         changed = true;
1700
1701     to->cfaShouldRevisit |= changed;
1702
1703     return changed;
1704 }
1705
1706 inline bool AbstractState::mergeToSuccessors(
1707     Graph& graph, BasicBlock* basicBlock, BranchDirection branchDirection)
1708 {
1709     Node& terminal = graph[basicBlock->last()];
1710
1711     ASSERT(terminal.isTerminal());
1712
1713     switch (terminal.op()) {
1714     case Jump: {
1715         ASSERT(branchDirection == InvalidBranchDirection);
1716 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1717         dataLog("        Merging to block #%u.\n", terminal.takenBlockIndex());
1718 #endif
1719         return merge(basicBlock, graph.m_blocks[terminal.takenBlockIndex()].get());
1720     }
1721
1722     case Branch: {
1723         ASSERT(branchDirection != InvalidBranchDirection);
1724         bool changed = false;
1725 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1726         dataLog("        Merging to block #%u.\n", terminal.takenBlockIndex());
1727 #endif
1728         if (branchDirection != TakeFalse)
1729             changed |= merge(basicBlock, graph.m_blocks[terminal.takenBlockIndex()].get());
1730 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
1731         dataLog("        Merging to block #%u.\n", terminal.notTakenBlockIndex());
1732 #endif
1733         if (branchDirection != TakeTrue)
1734             changed |= merge(basicBlock, graph.m_blocks[terminal.notTakenBlockIndex()].get());
1735         return changed;
1736     }
1737
1738     case Return:
1739     case Throw:
1740     case ThrowReferenceError:
1741         ASSERT(branchDirection == InvalidBranchDirection);
1742         return false;
1743
1744     default:
1745         ASSERT_NOT_REACHED();
1746         return false;
1747     }
1748 }
1749
1750 inline bool AbstractState::mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, NodeIndex destinationNodeIndex, NodeIndex sourceNodeIndex)
1751 {
1752     if (destinationNodeIndex == NoNode)
1753         return false;
1754
1755     ASSERT_UNUSED(sourceNodeIndex, sourceNodeIndex != NoNode);
1756
1757     // FIXME: We could do some sparse conditional propagation here!
1758
1759     return destination.merge(source);
1760 }
1761
1762 void AbstractState::dump(FILE* out)
1763 {
1764     bool first = true;
1765     for (size_t i = 0; i < m_block->size(); ++i) {
1766         NodeIndex index = m_block->at(i);
1767         AbstractValue& value = m_nodes[index];
1768         if (value.isClear())
1769             continue;
1770         if (first)
1771             first = false;
1772         else
1773             fprintf(out, " ");
1774         fprintf(out, "@%lu:", static_cast<unsigned long>(index));
1775         value.dump(out);
1776     }
1777 }
1778
1779 } } // namespace JSC::DFG
1780
1781 #endif // ENABLE(DFG_JIT)
1782