1/* 2 * Copyright (C) 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 "DFGConstantFoldingPhase.h" 28 29#if ENABLE(DFG_JIT) 30 31#include "DFGAbstractState.h" 32#include "DFGBasicBlock.h" 33#include "DFGGraph.h" 34#include "DFGInsertionSet.h" 35#include "DFGPhase.h" 36#include "GetByIdStatus.h" 37#include "Operations.h" 38#include "PutByIdStatus.h" 39 40namespace JSC { namespace DFG { 41 42class ConstantFoldingPhase : public Phase { 43public: 44 ConstantFoldingPhase(Graph& graph) 45 : Phase(graph, "constant folding") 46 , m_state(graph) 47 , m_insertionSet(graph) 48 { 49 } 50 51 bool run() 52 { 53 bool changed = false; 54 55 for (BlockIndex blockIndex = 0; blockIndex < m_graph.m_blocks.size(); ++blockIndex) { 56 BasicBlock* block = m_graph.m_blocks[blockIndex].get(); 57 if (!block) 58 continue; 59 if (!block->cfaDidFinish) 60 changed |= paintUnreachableCode(blockIndex); 61 if (block->cfaFoundConstants) 62 changed |= foldConstants(blockIndex); 63 } 64 65 return changed; 66 } 67 68private: 69 bool foldConstants(BlockIndex blockIndex) 70 { 71#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) 72 dataLogF("Constant folding considering Block #%u.\n", blockIndex); 73#endif 74 BasicBlock* block = m_graph.m_blocks[blockIndex].get(); 75 bool changed = false; 76 m_state.beginBasicBlock(block); 77 for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) { 78 if (!m_state.isValid()) 79 break; 80 81 Node* node = block->at(indexInBlock); 82 83 bool eliminated = false; 84 85 switch (node->op()) { 86 case CheckArgumentsNotCreated: { 87 if (!isEmptySpeculation( 88 m_state.variables().operand( 89 m_graph.argumentsRegisterFor(node->codeOrigin)).m_type)) 90 break; 91 node->convertToPhantom(); 92 eliminated = true; 93 break; 94 } 95 96 case CheckStructure: 97 case ForwardCheckStructure: 98 case ArrayifyToStructure: { 99 AbstractValue& value = m_state.forNode(node->child1()); 100 StructureSet set; 101 if (node->op() == ArrayifyToStructure) 102 set = node->structure(); 103 else 104 set = node->structureSet(); 105 if (value.m_currentKnownStructure.isSubsetOf(set)) { 106 m_state.execute(indexInBlock); // Catch the fact that we may filter on cell. 107 node->convertToPhantom(); 108 eliminated = true; 109 break; 110 } 111 StructureAbstractValue& structureValue = value.m_futurePossibleStructure; 112 if (structureValue.isSubsetOf(set) 113 && structureValue.hasSingleton()) { 114 Structure* structure = structureValue.singleton(); 115 m_state.execute(indexInBlock); // Catch the fact that we may filter on cell. 116 node->convertToStructureTransitionWatchpoint(structure); 117 eliminated = true; 118 break; 119 } 120 break; 121 } 122 123 case CheckArray: 124 case Arrayify: { 125 if (!node->arrayMode().alreadyChecked(m_graph, node, m_state.forNode(node->child1()))) 126 break; 127 node->convertToPhantom(); 128 eliminated = true; 129 break; 130 } 131 132 case CheckFunction: { 133 if (m_state.forNode(node->child1()).value() != node->function()) 134 break; 135 node->convertToPhantom(); 136 eliminated = true; 137 break; 138 } 139 140 case GetById: 141 case GetByIdFlush: { 142 CodeOrigin codeOrigin = node->codeOrigin; 143 Edge childEdge = node->child1(); 144 Node* child = childEdge.node(); 145 unsigned identifierNumber = node->identifierNumber(); 146 147 if (childEdge.useKind() != CellUse) 148 break; 149 150 Structure* structure = m_state.forNode(child).bestProvenStructure(); 151 if (!structure) 152 break; 153 154 bool needsWatchpoint = !m_state.forNode(child).m_currentKnownStructure.hasSingleton(); 155 bool needsCellCheck = m_state.forNode(child).m_type & ~SpecCell; 156 157 GetByIdStatus status = GetByIdStatus::computeFor( 158 vm(), structure, codeBlock()->identifier(identifierNumber)); 159 160 if (!status.isSimple()) { 161 // FIXME: We could handle prototype cases. 162 // https://bugs.webkit.org/show_bug.cgi?id=110386 163 break; 164 } 165 166 ASSERT(status.structureSet().size() == 1); 167 ASSERT(status.chain().isEmpty()); 168 ASSERT(status.structureSet().singletonStructure() == structure); 169 170 // Now before we do anything else, push the CFA forward over the GetById 171 // and make sure we signal to the loop that it should continue and not 172 // do any eliminations. 173 m_state.execute(indexInBlock); 174 eliminated = true; 175 176 if (needsWatchpoint) { 177 ASSERT(m_state.forNode(child).m_futurePossibleStructure.isSubsetOf(StructureSet(structure))); 178 m_insertionSet.insertNode( 179 indexInBlock, SpecNone, StructureTransitionWatchpoint, codeOrigin, 180 OpInfo(structure), childEdge); 181 } else if (needsCellCheck) { 182 m_insertionSet.insertNode( 183 indexInBlock, SpecNone, Phantom, codeOrigin, childEdge); 184 } 185 186 childEdge.setUseKind(KnownCellUse); 187 188 Edge propertyStorage; 189 190 if (isInlineOffset(status.offset())) 191 propertyStorage = childEdge; 192 else { 193 propertyStorage = Edge(m_insertionSet.insertNode( 194 indexInBlock, SpecNone, GetButterfly, codeOrigin, childEdge)); 195 } 196 197 node->convertToGetByOffset(m_graph.m_storageAccessData.size(), propertyStorage); 198 199 StorageAccessData storageAccessData; 200 storageAccessData.offset = indexRelativeToBase(status.offset()); 201 storageAccessData.identifierNumber = identifierNumber; 202 m_graph.m_storageAccessData.append(storageAccessData); 203 break; 204 } 205 206 case PutById: 207 case PutByIdDirect: { 208 CodeOrigin codeOrigin = node->codeOrigin; 209 Edge childEdge = node->child1(); 210 Node* child = childEdge.node(); 211 unsigned identifierNumber = node->identifierNumber(); 212 213 ASSERT(childEdge.useKind() == CellUse); 214 215 Structure* structure = m_state.forNode(child).bestProvenStructure(); 216 if (!structure) 217 break; 218 219 bool needsWatchpoint = !m_state.forNode(child).m_currentKnownStructure.hasSingleton(); 220 bool needsCellCheck = m_state.forNode(child).m_type & ~SpecCell; 221 222 PutByIdStatus status = PutByIdStatus::computeFor( 223 vm(), 224 m_graph.globalObjectFor(codeOrigin), 225 structure, 226 codeBlock()->identifier(identifierNumber), 227 node->op() == PutByIdDirect); 228 229 if (!status.isSimpleReplace() && !status.isSimpleTransition()) 230 break; 231 232 ASSERT(status.oldStructure() == structure); 233 234 // Now before we do anything else, push the CFA forward over the PutById 235 // and make sure we signal to the loop that it should continue and not 236 // do any eliminations. 237 m_state.execute(indexInBlock); 238 eliminated = true; 239 240 if (needsWatchpoint) { 241 ASSERT(m_state.forNode(child).m_futurePossibleStructure.isSubsetOf(StructureSet(structure))); 242 m_insertionSet.insertNode( 243 indexInBlock, SpecNone, StructureTransitionWatchpoint, codeOrigin, 244 OpInfo(structure), childEdge); 245 } else if (needsCellCheck) { 246 m_insertionSet.insertNode( 247 indexInBlock, SpecNone, Phantom, codeOrigin, childEdge); 248 } 249 250 childEdge.setUseKind(KnownCellUse); 251 252 StructureTransitionData* transitionData = 0; 253 if (status.isSimpleTransition()) { 254 transitionData = m_graph.addStructureTransitionData( 255 StructureTransitionData(structure, status.newStructure())); 256 257 if (node->op() == PutById) { 258 if (!structure->storedPrototype().isNull()) { 259 addStructureTransitionCheck( 260 codeOrigin, indexInBlock, 261 structure->storedPrototype().asCell()); 262 } 263 264 for (WriteBarrier<Structure>* it = status.structureChain()->head(); *it; ++it) { 265 JSValue prototype = (*it)->storedPrototype(); 266 if (prototype.isNull()) 267 continue; 268 ASSERT(prototype.isCell()); 269 addStructureTransitionCheck( 270 codeOrigin, indexInBlock, prototype.asCell()); 271 } 272 } 273 } 274 275 Edge propertyStorage; 276 277 if (isInlineOffset(status.offset())) 278 propertyStorage = childEdge; 279 else if (status.isSimpleReplace() || structure->outOfLineCapacity() == status.newStructure()->outOfLineCapacity()) { 280 propertyStorage = Edge(m_insertionSet.insertNode( 281 indexInBlock, SpecNone, GetButterfly, codeOrigin, childEdge)); 282 } else if (!structure->outOfLineCapacity()) { 283 ASSERT(status.newStructure()->outOfLineCapacity()); 284 ASSERT(!isInlineOffset(status.offset())); 285 propertyStorage = Edge(m_insertionSet.insertNode( 286 indexInBlock, SpecNone, AllocatePropertyStorage, 287 codeOrigin, OpInfo(transitionData), childEdge)); 288 } else { 289 ASSERT(structure->outOfLineCapacity()); 290 ASSERT(status.newStructure()->outOfLineCapacity() > structure->outOfLineCapacity()); 291 ASSERT(!isInlineOffset(status.offset())); 292 293 propertyStorage = Edge(m_insertionSet.insertNode( 294 indexInBlock, SpecNone, ReallocatePropertyStorage, codeOrigin, 295 OpInfo(transitionData), childEdge, 296 Edge(m_insertionSet.insertNode( 297 indexInBlock, SpecNone, GetButterfly, codeOrigin, childEdge)))); 298 } 299 300 if (status.isSimpleTransition()) { 301 m_insertionSet.insertNode( 302 indexInBlock, SpecNone, PutStructure, codeOrigin, 303 OpInfo(transitionData), childEdge); 304 } 305 306 node->convertToPutByOffset(m_graph.m_storageAccessData.size(), propertyStorage); 307 308 StorageAccessData storageAccessData; 309 storageAccessData.offset = indexRelativeToBase(status.offset()); 310 storageAccessData.identifierNumber = identifierNumber; 311 m_graph.m_storageAccessData.append(storageAccessData); 312 break; 313 } 314 315 default: 316 break; 317 } 318 319 if (eliminated) { 320 changed = true; 321 continue; 322 } 323 324 m_state.execute(indexInBlock); 325 if (!node->shouldGenerate() || m_state.didClobber() || node->hasConstant()) 326 continue; 327 JSValue value = m_state.forNode(node).value(); 328 if (!value) 329 continue; 330 331 CodeOrigin codeOrigin = node->codeOrigin; 332 AdjacencyList children = node->children; 333 334 if (node->op() == GetLocal) { 335 // GetLocals without a Phi child are guaranteed dead. We don't have to 336 // do anything about them. 337 if (!node->child1()) 338 continue; 339 340 if (m_graph.m_form != LoadStore) { 341 VariableAccessData* variable = node->variableAccessData(); 342 Node* phi = node->child1().node(); 343 if (phi->op() == Phi 344 && block->variablesAtHead.operand(variable->local()) == phi 345 && block->variablesAtTail.operand(variable->local()) == node) { 346 347 // Keep the graph threaded for easy cases. This is improves compile 348 // times. It would be correct to just dethread here. 349 350 m_graph.convertToConstant(node, value); 351 Node* phantom = m_insertionSet.insertNode( 352 indexInBlock, SpecNone, PhantomLocal, codeOrigin, 353 OpInfo(variable), Edge(phi)); 354 block->variablesAtHead.operand(variable->local()) = phantom; 355 block->variablesAtTail.operand(variable->local()) = phantom; 356 357 changed = true; 358 359 continue; 360 } 361 362 m_graph.dethread(); 363 } 364 } else 365 ASSERT(!node->hasVariableAccessData()); 366 367 m_graph.convertToConstant(node, value); 368 m_insertionSet.insertNode( 369 indexInBlock, SpecNone, Phantom, codeOrigin, children); 370 371 changed = true; 372 } 373 m_state.reset(); 374 m_insertionSet.execute(block); 375 376 return changed; 377 } 378 379#if !ASSERT_DISABLED 380 bool isCapturedAtOrAfter(BasicBlock* block, unsigned indexInBlock, int operand) 381 { 382 for (; indexInBlock < block->size(); ++indexInBlock) { 383 Node* node = block->at(indexInBlock); 384 if (!node->hasLocal()) 385 continue; 386 if (node->local() != operand) 387 continue; 388 if (node->variableAccessData()->isCaptured()) 389 return true; 390 } 391 return false; 392 } 393#endif // !ASSERT_DISABLED 394 395 void addStructureTransitionCheck(CodeOrigin codeOrigin, unsigned indexInBlock, JSCell* cell) 396 { 397 Node* weakConstant = m_insertionSet.insertNode( 398 indexInBlock, speculationFromValue(cell), WeakJSConstant, codeOrigin, OpInfo(cell)); 399 400 if (cell->structure()->transitionWatchpointSetIsStillValid()) { 401 m_insertionSet.insertNode( 402 indexInBlock, SpecNone, StructureTransitionWatchpoint, codeOrigin, 403 OpInfo(cell->structure()), Edge(weakConstant, CellUse)); 404 return; 405 } 406 407 m_insertionSet.insertNode( 408 indexInBlock, SpecNone, CheckStructure, codeOrigin, 409 OpInfo(m_graph.addStructureSet(cell->structure())), Edge(weakConstant, CellUse)); 410 } 411 412 // This is necessary because the CFA may reach conclusions about constants based on its 413 // assumption that certain code must exit, but then those constants may lead future 414 // reexecutions of the CFA to believe that the same code will now no longer exit. Thus 415 // to ensure soundness, we must paint unreachable code as such, by inserting an 416 // unconditional ForceOSRExit wherever we find that a node would have always exited. 417 // This will only happen in cases where we are making static speculations, or we're 418 // making totally wrong speculations due to imprecision on the prediction propagator. 419 bool paintUnreachableCode(BlockIndex blockIndex) 420 { 421 bool changed = false; 422 423#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) 424 dataLogF("Painting unreachable code in Block #%u.\n", blockIndex); 425#endif 426 BasicBlock* block = m_graph.m_blocks[blockIndex].get(); 427 m_state.beginBasicBlock(block); 428 429 for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) { 430 m_state.execute(indexInBlock); 431 if (m_state.isValid()) 432 continue; 433 434 Node* node = block->at(indexInBlock); 435 switch (node->op()) { 436 case Return: 437 case Unreachable: 438 case ForceOSRExit: 439 // Do nothing. These nodes will already do the right thing. 440 break; 441 442 default: 443 m_insertionSet.insertNode( 444 indexInBlock, SpecNone, ForceOSRExit, node->codeOrigin); 445 changed = true; 446 break; 447 } 448 break; 449 } 450 m_state.reset(); 451 m_insertionSet.execute(block); 452 453 return changed; 454 } 455 456 AbstractState m_state; 457 InsertionSet m_insertionSet; 458}; 459 460bool performConstantFolding(Graph& graph) 461{ 462 SamplingRegion samplingRegion("DFG Constant Folding Phase"); 463 return runPhase<ConstantFoldingPhase>(graph); 464} 465 466} } // namespace JSC::DFG 467 468#endif // ENABLE(DFG_JIT) 469 470 471