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 41namespace JSC { namespace DFG { 42 43class ConstantFoldingPhase : public Phase { 44public: 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 68private: 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 505bool 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 516