dfg/DFGConstantFoldingPhase.cpp

   1 /*
   2  * Copyright (C) 2012, 2013, 2014 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 "DFGConstantFoldingPhase.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGAbstractInterpreterInlines.h"
  32 #include "DFGBasicBlock.h"
  33 #include "DFGGraph.h"
  34 #include "DFGInPlaceAbstractState.h"
  35 #include "DFGInsertionSet.h"
  36 #include "DFGPhase.h"
  37 #include "GetByIdStatus.h"
  38 #include "JSCInlines.h"
  39 #include "PutByIdStatus.h"
  40
  41 namespace JSC { namespace DFG {
  42
  43 class ConstantFoldingPhase : public Phase {
  44 public:
  45     ConstantFoldingPhase(Graph& graph)
  46         : Phase(graph, "constant folding")
  47         , m_state(graph)
  48         , m_interpreter(graph, m_state)
  49         , m_insertionSet(graph)
  50     {
  51     }
  52
  53     bool run()
  54     {
  55         bool changed = false;
  56
  57         for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
  58             BasicBlock* block = m_graph.block(blockIndex);
  59             if (!block)
  60                 continue;
  61             if (block->cfaFoundConstants)
  62                 changed |= foldConstants(block);
  63         }
  64
  65         return changed;
  66     }
  67
  68 private:
  69     bool foldConstants(BasicBlock* block)
  70     {
  71         bool changed = false;
  72         m_state.beginBasicBlock(block);
  73         for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) {
  74             if (!m_state.isValid())
  75                 break;
  76
  77             Node* node = block->at(indexInBlock);
  78
  79             bool eliminated = false;
  80
  81             switch (node->op()) {
  82             case BooleanToNumber: {
  83                 if (node->child1().useKind() == UntypedUse
  84                     && !m_interpreter.needsTypeCheck(node->child1(), SpecBoolean))
  85                     node->child1().setUseKind(BooleanUse);
  86                 break;
  87             }
  88
  89             case CheckArgumentsNotCreated: {
  90                 if (!isEmptySpeculation(
  91                         m_state.variables().operand(
  92                             m_graph.argumentsRegisterFor(node->origin.semantic)).m_type))
  93                     break;
  94                 node->convertToPhantom();
  95                 eliminated = true;
  96                 break;
  97             }
  98
  99             case CheckStructure:
 100             case ArrayifyToStructure: {
 101                 AbstractValue& value = m_state.forNode(node->child1());
 102                 StructureSet set;
 103                 if (node->op() == ArrayifyToStructure)
 104                     set = node->structure();
 105                 else
 106                     set = node->structureSet();
 107                 if (value.m_currentKnownStructure.isSubsetOf(set)) {
 108                     m_interpreter.execute(indexInBlock); // Catch the fact that we may filter on cell.
 109                     node->convertToPhantom();
 110                     eliminated = true;
 111                     break;
 112                 }
 113                 StructureAbstractValue& structureValue = value.m_futurePossibleStructure;
 114                 if (structureValue.isSubsetOf(set)
 115                     && structureValue.hasSingleton()) {
 116                     Structure* structure = structureValue.singleton();
 117                     m_interpreter.execute(indexInBlock); // Catch the fact that we may filter on cell.
 118                     AdjacencyList children = node->children;
 119                     children.removeEdge(0);
 120                     if (!!children.child1())
 121                         m_insertionSet.insertNode(indexInBlock, SpecNone, Phantom, node->origin, children);
 122                     node->children.setChild2(Edge());
 123                     node->children.setChild3(Edge());
 124                     node->convertToStructureTransitionWatchpoint(structure);
 125                     eliminated = true;
 126                     break;
 127                 }
 128                 break;
 129             }
 130
 131             case CheckArray:
 132             case Arrayify: {
 133                 if (!node->arrayMode().alreadyChecked(m_graph, node, m_state.forNode(node->child1())))
 134                     break;
 135                 node->convertToPhantom();
 136                 eliminated = true;
 137                 break;
 138             }
 139
 140             case CheckFunction: {
 141                 if (m_state.forNode(node->child1()).value() != node->function())
 142                     break;
 143                 node->convertToPhantom();
 144                 eliminated = true;
 145                 break;
 146             }
 147
 148             case CheckInBounds: {
 149                 JSValue left = m_state.forNode(node->child1()).value();
 150                 JSValue right = m_state.forNode(node->child2()).value();
 151                 if (left && right && left.isInt32() && right.isInt32()
 152                     && static_cast<uint32_t>(left.asInt32()) < static_cast<uint32_t>(right.asInt32())) {
 153                     node->convertToPhantom();
 154                     eliminated = true;
 155                     break;
 156                 }
 157
 158                 break;
 159             }
 160
 161             case MultiGetByOffset: {
 162                 Edge childEdge = node->child1();
 163                 Node* child = childEdge.node();
 164                 MultiGetByOffsetData& data = node->multiGetByOffsetData();
 165
 166                 Structure* structure = m_state.forNode(child).bestProvenStructure();
 167                 if (!structure)
 168                     break;
 169
 170                 for (unsigned i = data.variants.size(); i--;) {
 171                     const GetByIdVariant& variant = data.variants[i];
 172                     if (!variant.structureSet().contains(structure))
 173                         continue;
 174
 175                     if (variant.chain())
 176                         break;
 177
 178                     emitGetByOffset(indexInBlock, node, structure, variant, data.identifierNumber);
 179                     eliminated = true;
 180                     break;
 181                 }
 182                 break;
 183             }
 184
 185             case MultiPutByOffset: {
 186                 Edge childEdge = node->child1();
 187                 Node* child = childEdge.node();
 188                 MultiPutByOffsetData& data = node->multiPutByOffsetData();
 189
 190                 Structure* structure = m_state.forNode(child).bestProvenStructure();
 191                 if (!structure)
 192                     break;
 193
 194                 for (unsigned i = data.variants.size(); i--;) {
 195                     const PutByIdVariant& variant = data.variants[i];
 196                     if (variant.oldStructure() != structure)
 197                         continue;
 198
 199                     emitPutByOffset(indexInBlock, node, structure, variant, data.identifierNumber);
 200                     eliminated = true;
 201                     break;
 202                 }
 203                 break;
 204             }
 205
 206             case GetById:
 207             case GetByIdFlush: {
 208                 Edge childEdge = node->child1();
 209                 Node* child = childEdge.node();
 210                 unsigned identifierNumber = node->identifierNumber();
 211
 212                 if (childEdge.useKind() != CellUse)
 213                     break;
 214
 215                 Structure* structure = m_state.forNode(child).bestProvenStructure();
 216                 if (!structure)
 217                     break;
 218
 219                 GetByIdStatus status = GetByIdStatus::computeFor(
 220                     vm(), structure, m_graph.identifiers()[identifierNumber]);
 221
 222                 if (!status.isSimple() || status.numVariants() != 1) {
 223                     // FIXME: We could handle prototype cases.
 224                     // https://bugs.webkit.org/show_bug.cgi?id=110386
 225                     break;
 226                 }
 227
 228                 emitGetByOffset(indexInBlock, node, structure, status[0], identifierNumber);
 229                 eliminated = true;
 230                 break;
 231             }
 232
 233             case PutById:
 234             case PutByIdDirect: {
 235                 NodeOrigin origin = node->origin;
 236                 Edge childEdge = node->child1();
 237                 Node* child = childEdge.node();
 238                 unsigned identifierNumber = node->identifierNumber();
 239
 240                 ASSERT(childEdge.useKind() == CellUse);
 241
 242                 Structure* structure = m_state.forNode(child).bestProvenStructure();
 243                 if (!structure)
 244                     break;
 245
 246                 PutByIdStatus status = PutByIdStatus::computeFor(
 247                     vm(),
 248                     m_graph.globalObjectFor(origin.semantic),
 249                     structure,
 250                     m_graph.identifiers()[identifierNumber],
 251                     node->op() == PutByIdDirect);
 252
 253                 if (!status.isSimple())
 254                     break;
 255                 if (status.numVariants() != 1)
 256                     break;
 257
 258                 emitPutByOffset(indexInBlock, node, structure, status[0], identifierNumber);
 259                 eliminated = true;
 260                 break;
 261             }
 262
 263             case ToPrimitive: {
 264                 if (m_state.forNode(node->child1()).m_type & ~(SpecFullNumber | SpecBoolean | SpecString))
 265                     break;
 266
 267                 node->convertToIdentity();
 268                 break;
 269             }
 270
 271             default:
 272                 break;
 273             }
 274
 275             if (eliminated) {
 276                 changed = true;
 277                 continue;
 278             }
 279
 280             m_interpreter.execute(indexInBlock);
 281             if (!m_state.isValid()) {
 282                 // If we invalidated then we shouldn't attempt to constant-fold. Here's an
 283                 // example:
 284                 //
 285                 //     c: JSConstant(4.2)
 286                 //     x: ValueToInt32(Check:Int32:@const)
 287                 //
 288                 // It would be correct for an analysis to assume that execution cannot
 289                 // proceed past @x. Therefore, constant-folding @x could be rather bad. But,
 290                 // the CFA may report that it found a constant even though it also reported
 291                 // that everything has been invalidated. This will only happen in a couple of
 292                 // the constant folding cases; most of them are also separately defensive
 293                 // about such things.
 294                 break;
 295             }
 296             if (!node->shouldGenerate() || m_state.didClobber() || node->hasConstant())
 297                 continue;
 298             JSValue value = m_state.forNode(node).value();
 299             if (!value)
 300                 continue;
 301
 302             // Check if merging the abstract value of the constant into the abstract value
 303             // we've proven for this node wouldn't widen the proof. If it widens the proof
 304             // (i.e. says that the set contains more things in it than it previously did)
 305             // then we refuse to fold.
 306             AbstractValue oldValue = m_state.forNode(node);
 307             AbstractValue constantValue;
 308             constantValue.set(m_graph, value);
 309             constantValue.fixTypeForRepresentation(node);
 310             if (oldValue.merge(constantValue))
 311                 continue;
 312
 313             NodeOrigin origin = node->origin;
 314             AdjacencyList children = node->children;
 315
 316             if (node->op() == GetLocal)
 317                 m_graph.dethread();
 318             else
 319                 ASSERT(!node->hasVariableAccessData(m_graph));
 320
 321             m_graph.convertToConstant(node, value);
 322             m_insertionSet.insertNode(
 323                 indexInBlock, SpecNone, Phantom, origin, children);
 324
 325             changed = true;
 326         }
 327         m_state.reset();
 328         m_insertionSet.execute(block);
 329
 330         return changed;
 331     }
 332
 333     void emitGetByOffset(unsigned indexInBlock, Node* node, Structure* structure, const GetByIdVariant& variant, unsigned identifierNumber)
 334     {
 335         NodeOrigin origin = node->origin;
 336         Edge childEdge = node->child1();
 337         Node* child = childEdge.node();
 338
 339         bool needsWatchpoint = !m_state.forNode(child).m_currentKnownStructure.hasSingleton();
 340         bool needsCellCheck = m_state.forNode(child).m_type & ~SpecCell;
 341
 342         ASSERT(!variant.chain());
 343         ASSERT(variant.structureSet().contains(structure));
 344
 345         // Now before we do anything else, push the CFA forward over the GetById
 346         // and make sure we signal to the loop that it should continue and not
 347         // do any eliminations.
 348         m_interpreter.execute(indexInBlock);
 349
 350         if (needsWatchpoint) {
 351             m_insertionSet.insertNode(
 352                 indexInBlock, SpecNone, StructureTransitionWatchpoint, origin,
 353                 OpInfo(structure), childEdge);
 354         } else if (needsCellCheck) {
 355             m_insertionSet.insertNode(
 356                 indexInBlock, SpecNone, Phantom, origin, childEdge);
 357         }
 358
 359         if (variant.specificValue()) {
 360             m_graph.convertToConstant(node, variant.specificValue());
 361             return;
 362         }
 363
 364         childEdge.setUseKind(KnownCellUse);
 365
 366         Edge propertyStorage;
 367
 368         if (isInlineOffset(variant.offset()))
 369             propertyStorage = childEdge;
 370         else {
 371             propertyStorage = Edge(m_insertionSet.insertNode(
 372                 indexInBlock, SpecNone, GetButterfly, origin, childEdge));
 373         }
 374
 375         node->convertToGetByOffset(m_graph.m_storageAccessData.size(), propertyStorage);
 376
 377         StorageAccessData storageAccessData;
 378         storageAccessData.offset = variant.offset();
 379         storageAccessData.identifierNumber = identifierNumber;
 380         m_graph.m_storageAccessData.append(storageAccessData);
 381     }
 382
 383     void emitPutByOffset(unsigned indexInBlock, Node* node, Structure* structure, const PutByIdVariant& variant, unsigned identifierNumber)
 384     {
 385         NodeOrigin origin = node->origin;
 386         Edge childEdge = node->child1();
 387         Node* child = childEdge.node();
 388
 389         ASSERT(variant.oldStructure() == structure);
 390
 391         bool needsWatchpoint = !m_state.forNode(child).m_currentKnownStructure.hasSingleton();
 392         bool needsCellCheck = m_state.forNode(child).m_type & ~SpecCell;
 393
 394         // Now before we do anything else, push the CFA forward over the PutById
 395         // and make sure we signal to the loop that it should continue and not
 396         // do any eliminations.
 397         m_interpreter.execute(indexInBlock);
 398
 399         if (needsWatchpoint) {
 400             m_insertionSet.insertNode(
 401                 indexInBlock, SpecNone, StructureTransitionWatchpoint, origin,
 402                 OpInfo(structure), childEdge);
 403         } else if (needsCellCheck) {
 404             m_insertionSet.insertNode(
 405                 indexInBlock, SpecNone, Phantom, origin, childEdge);
 406         }
 407
 408         childEdge.setUseKind(KnownCellUse);
 409
 410         StructureTransitionData* transitionData = 0;
 411         if (variant.kind() == PutByIdVariant::Transition) {
 412             transitionData = m_graph.addStructureTransitionData(
 413                 StructureTransitionData(structure, variant.newStructure()));
 414
 415             if (node->op() == PutById) {
 416                 if (!structure->storedPrototype().isNull()) {
 417                     addStructureTransitionCheck(
 418                         origin, indexInBlock,
 419                         structure->storedPrototype().asCell());
 420                 }
 421
 422                 m_graph.chains().addLazily(variant.structureChain());
 423
 424                 for (unsigned i = 0; i < variant.structureChain()->size(); ++i) {
 425                     JSValue prototype = variant.structureChain()->at(i)->storedPrototype();
 426                     if (prototype.isNull())
 427                         continue;
 428                     ASSERT(prototype.isCell());
 429                     addStructureTransitionCheck(
 430                         origin, indexInBlock, prototype.asCell());
 431                 }
 432             }
 433         }
 434
 435         Edge propertyStorage;
 436
 437         if (isInlineOffset(variant.offset()))
 438             propertyStorage = childEdge;
 439         else if (
 440             variant.kind() == PutByIdVariant::Replace
 441             || structure->outOfLineCapacity() == variant.newStructure()->outOfLineCapacity()) {
 442             propertyStorage = Edge(m_insertionSet.insertNode(
 443                 indexInBlock, SpecNone, GetButterfly, origin, childEdge));
 444         } else if (!structure->outOfLineCapacity()) {
 445             ASSERT(variant.newStructure()->outOfLineCapacity());
 446             ASSERT(!isInlineOffset(variant.offset()));
 447             Node* allocatePropertyStorage = m_insertionSet.insertNode(
 448                 indexInBlock, SpecNone, AllocatePropertyStorage,
 449                 origin, OpInfo(transitionData), childEdge);
 450             m_insertionSet.insertNode(indexInBlock, SpecNone, StoreBarrier, origin, Edge(node->child1().node(), KnownCellUse));
 451             propertyStorage = Edge(allocatePropertyStorage);
 452         } else {
 453             ASSERT(structure->outOfLineCapacity());
 454             ASSERT(variant.newStructure()->outOfLineCapacity() > structure->outOfLineCapacity());
 455             ASSERT(!isInlineOffset(variant.offset()));
 456
 457             Node* reallocatePropertyStorage = m_insertionSet.insertNode(
 458                 indexInBlock, SpecNone, ReallocatePropertyStorage, origin,
 459                 OpInfo(transitionData), childEdge,
 460                 Edge(m_insertionSet.insertNode(
 461                     indexInBlock, SpecNone, GetButterfly, origin, childEdge)));
 462             m_insertionSet.insertNode(indexInBlock, SpecNone, StoreBarrier, origin, Edge(node->child1().node(), KnownCellUse));
 463             propertyStorage = Edge(reallocatePropertyStorage);
 464         }
 465
 466         if (variant.kind() == PutByIdVariant::Transition) {
 467             Node* putStructure = m_graph.addNode(SpecNone, PutStructure, origin, OpInfo(transitionData), childEdge);
 468             m_insertionSet.insertNode(indexInBlock, SpecNone, StoreBarrier, origin, Edge(node->child1().node(), KnownCellUse));
 469             m_insertionSet.insert(indexInBlock, putStructure);
 470         }
 471
 472         node->convertToPutByOffset(m_graph.m_storageAccessData.size(), propertyStorage);
 473         m_insertionSet.insertNode(
 474             indexInBlock, SpecNone, StoreBarrier, origin,
 475             Edge(node->child2().node(), KnownCellUse));
 476
 477         StorageAccessData storageAccessData;
 478         storageAccessData.offset = variant.offset();
 479         storageAccessData.identifierNumber = identifierNumber;
 480         m_graph.m_storageAccessData.append(storageAccessData);
 481     }
 482
 483     void addStructureTransitionCheck(NodeOrigin origin, unsigned indexInBlock, JSCell* cell)
 484     {
 485         Node* weakConstant = m_insertionSet.insertNode(
 486             indexInBlock, speculationFromValue(cell), WeakJSConstant, origin, OpInfo(cell));
 487
 488         if (m_graph.watchpoints().isStillValid(cell->structure()->transitionWatchpointSet())) {
 489             m_insertionSet.insertNode(
 490                 indexInBlock, SpecNone, StructureTransitionWatchpoint, origin,
 491                 OpInfo(cell->structure()), Edge(weakConstant, CellUse));
 492             return;
 493         }
 494
 495         m_insertionSet.insertNode(
 496             indexInBlock, SpecNone, CheckStructure, origin,
 497             OpInfo(m_graph.addStructureSet(cell->structure())), Edge(weakConstant, CellUse));
 498     }
 499
 500     InPlaceAbstractState m_state;
 501     AbstractInterpreter<InPlaceAbstractState> m_interpreter;
 502     InsertionSet m_insertionSet;
 503 };
 504
 505 bool performConstantFolding(Graph& graph)
 506 {
 507     SamplingRegion samplingRegion("DFG Constant Folding Phase");
 508     return runPhase<ConstantFoldingPhase>(graph);
 509 }
 510
 511 } } // namespace JSC::DFG
 512
 513 #endif // ENABLE(DFG_JIT)
 514
 515