Source/JavaScriptCore/dfg/DFGFixupPhase.cpp

   1 /*
   2  * Copyright (C) 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 "DFGFixupPhase.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGGraph.h"
  32 #include "DFGInsertionSet.h"
  33 #include "DFGPhase.h"
  34
  35 namespace JSC { namespace DFG {
  36
  37 class FixupPhase : public Phase {
  38 public:
  39     FixupPhase(Graph& graph)
  40         : Phase(graph, "fixup")
  41     {
  42     }
  43
  44     bool run()
  45     {
  46         for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex)
  47             fixupBlock(m_graph.m_blocks[blockIndex].get());
  48         return true;
  49     }
  50
  51 private:
  52     void fixupBlock(BasicBlock* block)
  53     {
  54         if (!block)
  55             return;
  56         ASSERT(block->isReachable);
  57         for (m_indexInBlock = 0; m_indexInBlock < block->size(); ++m_indexInBlock) {
  58             m_compileIndex = block->at(m_indexInBlock);
  59             fixupNode(m_graph[m_compileIndex]);
  60         }
  61         m_insertionSet.execute(*block);
  62     }
  63
  64     void fixupNode(Node& node)
  65     {
  66         if (!node.shouldGenerate())
  67             return;
  68
  69         NodeType op = node.op();
  70
  71 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
  72         dataLogF("   %s @%u: ", Graph::opName(op), m_compileIndex);
  73 #endif
  74
  75         switch (op) {
  76         case GetById: {
  77             if (m_graph.m_fixpointState > BeforeFixpoint)
  78                 break;
  79
  80             Node* nodePtr = &node;
  81
  82             if (!isInt32Speculation(m_graph[m_compileIndex].prediction()))
  83                 break;
  84             if (codeBlock()->identifier(nodePtr->identifierNumber()) != globalData().propertyNames->length)
  85                 break;
  86             ArrayProfile* arrayProfile =
  87                 m_graph.baselineCodeBlockFor(nodePtr->codeOrigin)->getArrayProfile(
  88                     nodePtr->codeOrigin.bytecodeIndex);
  89             ArrayMode arrayMode = ArrayMode(Array::SelectUsingPredictions);
  90             if (arrayProfile) {
  91                 arrayProfile->computeUpdatedPrediction(m_graph.baselineCodeBlockFor(node.codeOrigin));
  92                 arrayMode = ArrayMode::fromObserved(arrayProfile, Array::Read, false);
  93                 arrayMode = arrayMode.refine(
  94                     m_graph[node.child1()].prediction(),
  95                     m_graph[m_compileIndex].prediction());
  96                 if (arrayMode.supportsLength() && arrayProfile->hasDefiniteStructure()) {
  97                     m_graph.ref(nodePtr->child1());
  98                     Node checkStructure(CheckStructure, nodePtr->codeOrigin, OpInfo(m_graph.addStructureSet(arrayProfile->expectedStructure())), nodePtr->child1().index());
  99                     checkStructure.ref();
 100                     NodeIndex checkStructureIndex = m_graph.size();
 101                     m_graph.append(checkStructure);
 102                     m_insertionSet.append(m_indexInBlock, checkStructureIndex);
 103                     nodePtr = &m_graph[m_compileIndex];
 104                 }
 105             } else {
 106                 arrayMode = arrayMode.refine(
 107                     m_graph[node.child1()].prediction(),
 108                     m_graph[m_compileIndex].prediction());
 109             }
 110             if (!arrayMode.supportsLength())
 111                 break;
 112             nodePtr->setOp(GetArrayLength);
 113             ASSERT(nodePtr->flags() & NodeMustGenerate);
 114             nodePtr->clearFlags(NodeMustGenerate | NodeClobbersWorld);
 115             m_graph.deref(m_compileIndex);
 116             nodePtr->setArrayMode(arrayMode);
 117
 118             NodeIndex storage = checkArray(arrayMode, nodePtr->codeOrigin, nodePtr->child1().index(), NoNode, lengthNeedsStorage, nodePtr->shouldGenerate());
 119             if (storage == NoNode)
 120                 break;
 121
 122             nodePtr = &m_graph[m_compileIndex];
 123             nodePtr->children.child2() = Edge(storage);
 124             break;
 125         }
 126         case GetIndexedPropertyStorage: {
 127             ASSERT(node.arrayMode().canCSEStorage());
 128             break;
 129         }
 130         case GetByVal: {
 131             node.setArrayMode(
 132                 node.arrayMode().refine(
 133                     m_graph[node.child1()].prediction(),
 134                     m_graph[node.child2()].prediction()));
 135
 136             blessArrayOperation(node.child1(), node.child2(), 2);
 137
 138             Node* nodePtr = &m_graph[m_compileIndex];
 139             ArrayMode arrayMode = nodePtr->arrayMode();
 140             if (arrayMode.type() == Array::Double
 141                 && arrayMode.arrayClass() == Array::OriginalArray
 142                 && arrayMode.speculation() == Array::InBounds
 143                 && arrayMode.conversion() == Array::AsIs
 144                 && m_graph.globalObjectFor(nodePtr->codeOrigin)->arrayPrototypeChainIsSane()
 145                 && !(nodePtr->flags() & NodeUsedAsOther))
 146                 nodePtr->setArrayMode(arrayMode.withSpeculation(Array::SaneChain));
 147
 148             break;
 149         }
 150         case StringCharAt:
 151         case StringCharCodeAt: {
 152             // Currently we have no good way of refining these.
 153             ASSERT(node.arrayMode() == ArrayMode(Array::String));
 154             blessArrayOperation(node.child1(), node.child2(), 2);
 155             break;
 156         }
 157
 158         case ArrayPush: {
 159             // May need to refine the array mode in case the value prediction contravenes
 160             // the array prediction. For example, we may have evidence showing that the
 161             // array is in Int32 mode, but the value we're storing is likely to be a double.
 162             // Then we should turn this into a conversion to Double array followed by the
 163             // push. On the other hand, we absolutely don't want to refine based on the
 164             // base prediction. If it has non-cell garbage in it, then we want that to be
 165             // ignored. That's because ArrayPush can't handle any array modes that aren't
 166             // array-related - so if refine() turned this into a "Generic" ArrayPush then
 167             // that would break things.
 168             node.setArrayMode(
 169                 node.arrayMode().refine(
 170                     m_graph[node.child1()].prediction() & SpecCell,
 171                     SpecInt32,
 172                     m_graph[node.child2()].prediction()));
 173             blessArrayOperation(node.child1(), node.child2(), 2);
 174
 175             Node* nodePtr = &m_graph[m_compileIndex];
 176             switch (nodePtr->arrayMode().type()) {
 177             case Array::Double:
 178                 fixDoubleEdge(1);
 179                 break;
 180             default:
 181                 break;
 182             }
 183             break;
 184         }
 185
 186         case ArrayPop: {
 187             blessArrayOperation(node.child1(), node.child2(), 1);
 188             break;
 189         }
 190
 191         case ValueToInt32: {
 192             if (m_graph[node.child1()].shouldSpeculateNumber()
 193                 && node.mustGenerate()) {
 194                 node.clearFlags(NodeMustGenerate);
 195                 m_graph.deref(m_compileIndex);
 196             }
 197             break;
 198         }
 199
 200         case BitAnd:
 201         case BitOr:
 202         case BitXor:
 203         case BitRShift:
 204         case BitLShift:
 205         case BitURShift: {
 206             fixIntEdge(node.children.child1());
 207             fixIntEdge(node.children.child2());
 208             break;
 209         }
 210
 211         case CompareEq:
 212         case CompareLess:
 213         case CompareLessEq:
 214         case CompareGreater:
 215         case CompareGreaterEq:
 216         case CompareStrictEq: {
 217             if (Node::shouldSpeculateInteger(m_graph[node.child1()], m_graph[node.child2()]))
 218                 break;
 219             if (!Node::shouldSpeculateNumber(m_graph[node.child1()], m_graph[node.child2()]))
 220                 break;
 221             fixDoubleEdge(0);
 222             fixDoubleEdge(1);
 223             break;
 224         }
 225
 226         case LogicalNot: {
 227             if (m_graph[node.child1()].shouldSpeculateInteger())
 228                 break;
 229             if (!m_graph[node.child1()].shouldSpeculateNumber())
 230                 break;
 231             fixDoubleEdge(0);
 232             break;
 233         }
 234
 235         case Branch: {
 236             if (!m_graph[node.child1()].shouldSpeculateInteger()
 237                 && m_graph[node.child1()].shouldSpeculateNumber())
 238                 fixDoubleEdge(0);
 239
 240             Node& myNode = m_graph[m_compileIndex]; // reload because the graph may have changed
 241             Edge logicalNotEdge = myNode.child1();
 242             Node& logicalNot = m_graph[logicalNotEdge];
 243             if (logicalNot.op() == LogicalNot
 244                 && logicalNot.adjustedRefCount() == 1) {
 245                 Edge newChildEdge = logicalNot.child1();
 246                 if (m_graph[newChildEdge].hasBooleanResult()) {
 247                     m_graph.ref(newChildEdge);
 248                     m_graph.deref(logicalNotEdge);
 249                     myNode.children.setChild1(newChildEdge);
 250
 251                     BlockIndex toBeTaken = myNode.notTakenBlockIndex();
 252                     BlockIndex toBeNotTaken = myNode.takenBlockIndex();
 253                     myNode.setTakenBlockIndex(toBeTaken);
 254                     myNode.setNotTakenBlockIndex(toBeNotTaken);
 255                 }
 256             }
 257             break;
 258         }
 259
 260         case SetLocal: {
 261             if (node.variableAccessData()->isCaptured())
 262                 break;
 263             if (!node.variableAccessData()->shouldUseDoubleFormat())
 264                 break;
 265             fixDoubleEdge(0);
 266             break;
 267         }
 268
 269         case ArithAdd:
 270         case ValueAdd: {
 271             if (m_graph.addShouldSpeculateInteger(node))
 272                 break;
 273             if (!Node::shouldSpeculateNumberExpectingDefined(m_graph[node.child1()], m_graph[node.child2()]))
 274                 break;
 275             fixDoubleEdge(0);
 276             fixDoubleEdge(1);
 277             break;
 278         }
 279
 280         case ArithSub: {
 281             if (m_graph.addShouldSpeculateInteger(node)
 282                 && node.canSpeculateInteger())
 283                 break;
 284             fixDoubleEdge(0);
 285             fixDoubleEdge(1);
 286             break;
 287         }
 288
 289         case ArithNegate: {
 290             if (m_graph.negateShouldSpeculateInteger(node))
 291                 break;
 292             fixDoubleEdge(0);
 293             break;
 294         }
 295
 296         case ArithMin:
 297         case ArithMax:
 298         case ArithMod: {
 299             if (Node::shouldSpeculateIntegerForArithmetic(m_graph[node.child1()], m_graph[node.child2()])
 300                 && node.canSpeculateInteger())
 301                 break;
 302             fixDoubleEdge(0);
 303             fixDoubleEdge(1);
 304             break;
 305         }
 306
 307         case ArithMul: {
 308             if (m_graph.mulShouldSpeculateInteger(node))
 309                 break;
 310             fixDoubleEdge(0);
 311             fixDoubleEdge(1);
 312             break;
 313         }
 314
 315         case ArithDiv: {
 316             if (Node::shouldSpeculateIntegerForArithmetic(m_graph[node.child1()], m_graph[node.child2()])
 317                 && node.canSpeculateInteger()) {
 318                 if (isX86())
 319                     break;
 320                 fixDoubleEdge(0);
 321                 fixDoubleEdge(1);
 322
 323                 Node& oldDivision = m_graph[m_compileIndex];
 324
 325                 Node newDivision = oldDivision;
 326                 newDivision.setRefCount(2);
 327                 newDivision.predict(SpecDouble);
 328                 NodeIndex newDivisionIndex = m_graph.size();
 329
 330                 oldDivision.setOp(DoubleAsInt32);
 331                 oldDivision.children.initialize(Edge(newDivisionIndex, DoubleUse), Edge(), Edge());
 332
 333                 m_graph.append(newDivision);
 334                 m_insertionSet.append(m_indexInBlock, newDivisionIndex);
 335
 336                 break;
 337             }
 338             fixDoubleEdge(0);
 339             fixDoubleEdge(1);
 340             break;
 341         }
 342
 343         case ArithAbs: {
 344             if (m_graph[node.child1()].shouldSpeculateIntegerForArithmetic()
 345                 && node.canSpeculateInteger())
 346                 break;
 347             fixDoubleEdge(0);
 348             break;
 349         }
 350
 351         case ArithSqrt: {
 352             fixDoubleEdge(0);
 353             break;
 354         }
 355
 356         case PutByVal:
 357         case PutByValAlias: {
 358             Edge child1 = m_graph.varArgChild(node, 0);
 359             Edge child2 = m_graph.varArgChild(node, 1);
 360             Edge child3 = m_graph.varArgChild(node, 2);
 361
 362             node.setArrayMode(
 363                 node.arrayMode().refine(
 364                     m_graph[child1].prediction(),
 365                     m_graph[child2].prediction(),
 366                     m_graph[child3].prediction()));
 367
 368             blessArrayOperation(child1, child2, 3);
 369
 370             Node* nodePtr = &m_graph[m_compileIndex];
 371
 372             switch (nodePtr->arrayMode().modeForPut().type()) {
 373             case Array::Double:
 374                 fixDoubleEdge(2);
 375                 break;
 376             case Array::Int8Array:
 377             case Array::Int16Array:
 378             case Array::Int32Array:
 379             case Array::Uint8Array:
 380             case Array::Uint8ClampedArray:
 381             case Array::Uint16Array:
 382             case Array::Uint32Array:
 383                 if (!m_graph[child3].shouldSpeculateInteger())
 384                     fixDoubleEdge(2);
 385                 break;
 386             case Array::Float32Array:
 387             case Array::Float64Array:
 388                 fixDoubleEdge(2);
 389                 break;
 390             default:
 391                 break;
 392             }
 393             break;
 394         }
 395
 396         case NewArray: {
 397             for (unsigned i = m_graph.varArgNumChildren(node); i--;) {
 398                 node.setIndexingType(
 399                     leastUpperBoundOfIndexingTypeAndType(
 400                         node.indexingType(), m_graph[m_graph.varArgChild(node, i)].prediction()));
 401             }
 402             if (node.indexingType() == ArrayWithDouble) {
 403                 for (unsigned i = m_graph.varArgNumChildren(node); i--;)
 404                     fixDoubleEdge(i);
 405             }
 406             break;
 407         }
 408
 409         default:
 410             break;
 411         }
 412
 413 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 414         if (!(node.flags() & NodeHasVarArgs)) {
 415             dataLogF("new children: ");
 416             node.dumpChildren(WTF::dataFile());
 417         }
 418         dataLogF("\n");
 419 #endif
 420     }
 421
 422     NodeIndex addNode(const Node& node, bool shouldGenerate)
 423     {
 424         NodeIndex nodeIndex = m_graph.size();
 425         m_graph.append(node);
 426         m_insertionSet.append(m_indexInBlock, nodeIndex);
 427         if (shouldGenerate)
 428             m_graph[nodeIndex].ref();
 429         return nodeIndex;
 430     }
 431
 432     NodeIndex checkArray(ArrayMode arrayMode, CodeOrigin codeOrigin, NodeIndex array, NodeIndex index, bool (*storageCheck)(const ArrayMode&) = canCSEStorage, bool shouldGenerate = true)
 433     {
 434         ASSERT(arrayMode.isSpecific());
 435
 436         m_graph.ref(array);
 437
 438         Structure* structure = arrayMode.originalArrayStructure(m_graph, codeOrigin);
 439
 440         if (arrayMode.doesConversion()) {
 441             if (index != NoNode)
 442                 m_graph.ref(index);
 443
 444             if (structure) {
 445                 Node arrayify(ArrayifyToStructure, codeOrigin, OpInfo(structure), OpInfo(arrayMode.asWord()), array, index);
 446                 arrayify.ref();
 447                 NodeIndex arrayifyIndex = m_graph.size();
 448                 m_graph.append(arrayify);
 449                 m_insertionSet.append(m_indexInBlock, arrayifyIndex);
 450             } else {
 451                 Node arrayify(Arrayify, codeOrigin, OpInfo(arrayMode.asWord()), array, index);
 452                 arrayify.ref();
 453                 NodeIndex arrayifyIndex = m_graph.size();
 454                 m_graph.append(arrayify);
 455                 m_insertionSet.append(m_indexInBlock, arrayifyIndex);
 456             }
 457         } else {
 458             if (structure) {
 459                 Node checkStructure(CheckStructure, codeOrigin, OpInfo(m_graph.addStructureSet(structure)), array);
 460                 checkStructure.ref();
 461                 NodeIndex checkStructureIndex = m_graph.size();
 462                 m_graph.append(checkStructure);
 463                 m_insertionSet.append(m_indexInBlock, checkStructureIndex);
 464             } else {
 465                 Node checkArray(CheckArray, codeOrigin, OpInfo(arrayMode.asWord()), array);
 466                 checkArray.ref();
 467                 NodeIndex checkArrayIndex = m_graph.size();
 468                 m_graph.append(checkArray);
 469                 m_insertionSet.append(m_indexInBlock, checkArrayIndex);
 470             }
 471         }
 472
 473         if (!storageCheck(arrayMode))
 474             return NoNode;
 475
 476         if (shouldGenerate)
 477             m_graph.ref(array);
 478
 479         if (arrayMode.usesButterfly())
 480             return addNode(Node(GetButterfly, codeOrigin, array), shouldGenerate);
 481
 482         return addNode(Node(GetIndexedPropertyStorage, codeOrigin, OpInfo(arrayMode.asWord()), array), shouldGenerate);
 483     }
 484
 485     void blessArrayOperation(Edge base, Edge index, unsigned storageChildIdx)
 486     {
 487         if (m_graph.m_fixpointState > BeforeFixpoint)
 488             return;
 489
 490         Node* nodePtr = &m_graph[m_compileIndex];
 491
 492         switch (nodePtr->arrayMode().type()) {
 493         case Array::ForceExit: {
 494             Node forceExit(ForceOSRExit, nodePtr->codeOrigin);
 495             forceExit.ref();
 496             NodeIndex forceExitIndex = m_graph.size();
 497             m_graph.append(forceExit);
 498             m_insertionSet.append(m_indexInBlock, forceExitIndex);
 499             return;
 500         }
 501
 502         case Array::SelectUsingPredictions:
 503         case Array::Unprofiled:
 504             ASSERT_NOT_REACHED();
 505             return;
 506
 507         case Array::Generic:
 508             return;
 509
 510         default: {
 511             NodeIndex storage = checkArray(nodePtr->arrayMode(), nodePtr->codeOrigin, base.index(), index.indexUnchecked());
 512             if (storage == NoNode)
 513                 return;
 514
 515             m_graph.child(m_graph[m_compileIndex], storageChildIdx) = Edge(storage);
 516             return;
 517         } }
 518     }
 519
 520     void fixIntEdge(Edge& edge)
 521     {
 522         Node& node = m_graph[edge];
 523         if (node.op() != ValueToInt32)
 524             return;
 525
 526         if (!m_graph[node.child1()].shouldSpeculateInteger())
 527             return;
 528
 529         Edge oldEdge = edge;
 530         Edge newEdge = node.child1();
 531
 532         m_graph.ref(newEdge);
 533         m_graph.deref(oldEdge);
 534
 535         edge = newEdge;
 536     }
 537
 538     void fixDoubleEdge(unsigned childIndex)
 539     {
 540         Node& source = m_graph[m_compileIndex];
 541         Edge& edge = m_graph.child(source, childIndex);
 542
 543         if (!m_graph[edge].shouldSpeculateInteger()) {
 544             edge.setUseKind(DoubleUse);
 545             return;
 546         }
 547
 548         NodeIndex resultIndex = (NodeIndex)m_graph.size();
 549
 550 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 551         dataLogF("(replacing @%u->@%u with @%u->@%u) ",
 552                 m_compileIndex, edge.index(), m_compileIndex, resultIndex);
 553 #endif
 554
 555         // Fix the edge up here because it's a reference that will be clobbered by
 556         // the append() below.
 557         NodeIndex oldIndex = edge.index();
 558         edge = Edge(resultIndex, DoubleUse);
 559
 560         m_graph.append(Node(Int32ToDouble, source.codeOrigin, oldIndex));
 561         m_insertionSet.append(m_indexInBlock, resultIndex);
 562
 563         Node& int32ToDouble = m_graph[resultIndex];
 564         int32ToDouble.predict(SpecDouble);
 565         int32ToDouble.ref();
 566     }
 567
 568     unsigned m_indexInBlock;
 569     NodeIndex m_compileIndex;
 570     InsertionSet<NodeIndex> m_insertionSet;
 571 };
 572
 573 bool performFixup(Graph& graph)
 574 {
 575     SamplingRegion samplingRegion("DFG Fixup Phase");
 576     return runPhase<FixupPhase>(graph);
 577 }
 578
 579 } } // namespace JSC::DFG
 580
 581 #endif // ENABLE(DFG_JIT)
 582