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