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 "DFGTypeCheckHoistingPhase.h" 28 29#if ENABLE(DFG_JIT) 30 31#include "DFGBasicBlock.h" 32#include "DFGGraph.h" 33#include "DFGInsertionSet.h" 34#include "DFGPhase.h" 35#include "DFGVariableAccessDataDump.h" 36#include "JSCInlines.h" 37#include <wtf/HashMap.h> 38 39namespace JSC { namespace DFG { 40 41enum CheckBallot { VoteOther, VoteStructureCheck = 1, VoteCheckArray = 1 }; 42 43struct ArrayTypeCheck; 44struct StructureTypeCheck; 45 46struct CheckData { 47 Structure* m_structure; 48 ArrayMode m_arrayMode; 49 bool m_arrayModeIsValid; 50 bool m_arrayModeHoistingOkay; 51 52 CheckData() 53 : m_structure(0) 54 , m_arrayModeIsValid(false) 55 , m_arrayModeHoistingOkay(false) 56 { 57 } 58 59 CheckData(Structure* structure) 60 : m_structure(structure) 61 , m_arrayModeIsValid(false) 62 , m_arrayModeHoistingOkay(true) 63 { 64 } 65 66 CheckData(ArrayMode arrayMode) 67 : m_structure(0) 68 , m_arrayMode(arrayMode) 69 , m_arrayModeIsValid(true) 70 , m_arrayModeHoistingOkay(true) 71 { 72 } 73 74 void disableCheckArrayHoisting() 75 { 76 m_arrayModeIsValid = false; 77 m_arrayModeHoistingOkay = false; 78 } 79}; 80 81class TypeCheckHoistingPhase : public Phase { 82public: 83 TypeCheckHoistingPhase(Graph& graph) 84 : Phase(graph, "structure check hoisting") 85 { 86 } 87 88 bool run() 89 { 90 ASSERT(m_graph.m_form == ThreadedCPS); 91 92 clearVariableVotes(); 93 identifyRedundantStructureChecks(); 94 disableHoistingForVariablesWithInsufficientVotes<StructureTypeCheck>(); 95 96 clearVariableVotes(); 97 identifyRedundantArrayChecks(); 98 disableHoistingForVariablesWithInsufficientVotes<ArrayTypeCheck>(); 99 100 disableHoistingAcrossOSREntries<StructureTypeCheck>(); 101 disableHoistingAcrossOSREntries<ArrayTypeCheck>(); 102 103 bool changed = false; 104 105 // Place CheckStructure's at SetLocal sites. 106 InsertionSet insertionSet(m_graph); 107 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) { 108 BasicBlock* block = m_graph.block(blockIndex); 109 if (!block) 110 continue; 111 for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) { 112 Node* node = block->at(indexInBlock); 113 // Be careful not to use 'node' after appending to the graph. In those switch 114 // cases where we need to append, we first carefully extract everything we need 115 // from the node, before doing any appending. 116 switch (node->op()) { 117 case SetArgument: { 118 ASSERT(!blockIndex); 119 // Insert a GetLocal and a CheckStructure immediately following this 120 // SetArgument, if the variable was a candidate for structure hoisting. 121 // If the basic block previously only had the SetArgument as its 122 // variable-at-tail, then replace it with this GetLocal. 123 VariableAccessData* variable = node->variableAccessData(); 124 HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable); 125 if (iter == m_map.end()) 126 break; 127 if (!iter->value.m_structure && !iter->value.m_arrayModeIsValid) 128 break; 129 130 NodeOrigin origin = node->origin; 131 132 Node* getLocal = insertionSet.insertNode( 133 indexInBlock + 1, variable->prediction(), GetLocal, origin, 134 OpInfo(variable), Edge(node)); 135 if (iter->value.m_structure) { 136 insertionSet.insertNode( 137 indexInBlock + 1, SpecNone, CheckStructure, origin, 138 OpInfo(m_graph.addStructureSet(iter->value.m_structure)), 139 Edge(getLocal, CellUse)); 140 } else if (iter->value.m_arrayModeIsValid) { 141 ASSERT(iter->value.m_arrayModeHoistingOkay); 142 insertionSet.insertNode( 143 indexInBlock + 1, SpecNone, CheckArray, origin, 144 OpInfo(iter->value.m_arrayMode.asWord()), 145 Edge(getLocal, CellUse)); 146 } else 147 RELEASE_ASSERT_NOT_REACHED(); 148 149 if (block->variablesAtTail.operand(variable->local()) == node) 150 block->variablesAtTail.operand(variable->local()) = getLocal; 151 152 m_graph.substituteGetLocal(*block, indexInBlock, variable, getLocal); 153 154 changed = true; 155 break; 156 } 157 158 case SetLocal: { 159 VariableAccessData* variable = node->variableAccessData(); 160 HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable); 161 if (iter == m_map.end()) 162 break; 163 if (!iter->value.m_structure && !iter->value.m_arrayModeIsValid) 164 break; 165 166 NodeOrigin origin = node->origin; 167 Edge child1 = node->child1(); 168 169 if (iter->value.m_structure) { 170 insertionSet.insertNode( 171 indexInBlock, SpecNone, CheckStructure, origin, 172 OpInfo(m_graph.addStructureSet(iter->value.m_structure)), 173 Edge(child1.node(), CellUse)); 174 } else if (iter->value.m_arrayModeIsValid) { 175 ASSERT(iter->value.m_arrayModeHoistingOkay); 176 insertionSet.insertNode( 177 indexInBlock, SpecNone, CheckArray, origin, 178 OpInfo(iter->value.m_arrayMode.asWord()), 179 Edge(child1.node(), CellUse)); 180 } else 181 RELEASE_ASSERT_NOT_REACHED(); 182 changed = true; 183 break; 184 } 185 186 default: 187 break; 188 } 189 } 190 insertionSet.execute(block); 191 } 192 193 return changed; 194 } 195 196private: 197 void clearVariableVotes() 198 { 199 for (unsigned i = m_graph.m_variableAccessData.size(); i--;) { 200 VariableAccessData* variable = &m_graph.m_variableAccessData[i]; 201 if (!variable->isRoot()) 202 continue; 203 variable->clearVotes(); 204 } 205 } 206 207 // Identify the set of variables that are always subject to the same structure 208 // checks. For now, only consider monomorphic structure checks (one structure). 209 void identifyRedundantStructureChecks() 210 { 211 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) { 212 BasicBlock* block = m_graph.block(blockIndex); 213 if (!block) 214 continue; 215 for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) { 216 Node* node = block->at(indexInBlock); 217 switch (node->op()) { 218 case CheckStructure: 219 case StructureTransitionWatchpoint: { 220 Node* child = node->child1().node(); 221 if (child->op() != GetLocal) 222 break; 223 VariableAccessData* variable = child->variableAccessData(); 224 variable->vote(VoteStructureCheck); 225 if (!shouldConsiderForHoisting<StructureTypeCheck>(variable)) 226 break; 227 noticeStructureCheck(variable, node->structureSet()); 228 break; 229 } 230 231 case GetByOffset: 232 case PutByOffset: 233 case PutStructure: 234 case AllocatePropertyStorage: 235 case ReallocatePropertyStorage: 236 case GetButterfly: 237 case GetByVal: 238 case PutByValDirect: 239 case PutByVal: 240 case PutByValAlias: 241 case GetArrayLength: 242 case CheckArray: 243 case GetIndexedPropertyStorage: 244 case GetTypedArrayByteOffset: 245 case Phantom: 246 case HardPhantom: 247 case MovHint: 248 case MultiGetByOffset: 249 case MultiPutByOffset: 250 // Don't count these uses. 251 break; 252 253 case ArrayifyToStructure: 254 case Arrayify: 255 if (node->arrayMode().conversion() == Array::RageConvert) { 256 // Rage conversion changes structures. We should avoid tying to do 257 // any kind of hoisting when rage conversion is in play. 258 Node* child = node->child1().node(); 259 if (child->op() != GetLocal) 260 break; 261 VariableAccessData* variable = child->variableAccessData(); 262 variable->vote(VoteOther); 263 if (!shouldConsiderForHoisting<StructureTypeCheck>(variable)) 264 break; 265 noticeStructureCheck(variable, 0); 266 } 267 break; 268 269 case SetLocal: { 270 // Find all uses of the source of the SetLocal. If any of them are a 271 // kind of CheckStructure, then we should notice them to ensure that 272 // we're not hoisting a check that would contravene checks that are 273 // already being performed. 274 VariableAccessData* variable = node->variableAccessData(); 275 if (!shouldConsiderForHoisting<StructureTypeCheck>(variable)) 276 break; 277 Node* source = node->child1().node(); 278 for (unsigned subIndexInBlock = 0; subIndexInBlock < block->size(); ++subIndexInBlock) { 279 Node* subNode = block->at(subIndexInBlock); 280 switch (subNode->op()) { 281 case CheckStructure: { 282 if (subNode->child1() != source) 283 break; 284 285 noticeStructureCheck(variable, subNode->structureSet()); 286 break; 287 } 288 case StructureTransitionWatchpoint: { 289 if (subNode->child1() != source) 290 break; 291 292 noticeStructureCheck(variable, subNode->structure()); 293 break; 294 } 295 default: 296 break; 297 } 298 } 299 300 m_graph.voteChildren(node, VoteOther); 301 break; 302 } 303 304 default: 305 m_graph.voteChildren(node, VoteOther); 306 break; 307 } 308 } 309 } 310 } 311 312 void identifyRedundantArrayChecks() 313 { 314 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) { 315 BasicBlock* block = m_graph.block(blockIndex); 316 if (!block) 317 continue; 318 for (unsigned indexInBlock = 0; indexInBlock < block->size(); ++indexInBlock) { 319 Node* node = block->at(indexInBlock); 320 switch (node->op()) { 321 case CheckArray: { 322 Node* child = node->child1().node(); 323 if (child->op() != GetLocal) 324 break; 325 VariableAccessData* variable = child->variableAccessData(); 326 variable->vote(VoteCheckArray); 327 if (!shouldConsiderForHoisting<ArrayTypeCheck>(variable)) 328 break; 329 noticeCheckArray(variable, node->arrayMode()); 330 break; 331 } 332 333 case CheckStructure: 334 case StructureTransitionWatchpoint: 335 case GetByOffset: 336 case PutByOffset: 337 case PutStructure: 338 case ReallocatePropertyStorage: 339 case GetButterfly: 340 case GetByVal: 341 case PutByValDirect: 342 case PutByVal: 343 case PutByValAlias: 344 case GetArrayLength: 345 case GetIndexedPropertyStorage: 346 case Phantom: 347 case HardPhantom: 348 case MovHint: 349 case MultiGetByOffset: 350 case MultiPutByOffset: 351 // Don't count these uses. 352 break; 353 354 case AllocatePropertyStorage: 355 case ArrayifyToStructure: 356 case Arrayify: { 357 // Any Arrayify could change our indexing type, so disable 358 // all CheckArray hoisting. 359 Node* child = node->child1().node(); 360 if (child->op() != GetLocal) 361 break; 362 VariableAccessData* variable = child->variableAccessData(); 363 variable->vote(VoteOther); 364 if (!shouldConsiderForHoisting<ArrayTypeCheck>(variable)) 365 break; 366 disableCheckArrayHoisting(variable); 367 break; 368 } 369 370 case SetLocal: { 371 // Find all uses of the source of the SetLocal. If any of them are a 372 // kind of CheckStructure, then we should notice them to ensure that 373 // we're not hoisting a check that would contravene checks that are 374 // already being performed. 375 VariableAccessData* variable = node->variableAccessData(); 376 if (!shouldConsiderForHoisting<ArrayTypeCheck>(variable)) 377 break; 378 Node* source = node->child1().node(); 379 for (unsigned subIndexInBlock = 0; subIndexInBlock < block->size(); ++subIndexInBlock) { 380 Node* subNode = block->at(subIndexInBlock); 381 switch (subNode->op()) { 382 case CheckStructure: { 383 if (subNode->child1() != source) 384 break; 385 386 noticeStructureCheckAccountingForArrayMode(variable, subNode->structureSet()); 387 break; 388 } 389 case StructureTransitionWatchpoint: { 390 if (subNode->child1() != source) 391 break; 392 393 noticeStructureCheckAccountingForArrayMode(variable, subNode->structure()); 394 break; 395 } 396 case CheckArray: { 397 if (subNode->child1() != source) 398 break; 399 noticeCheckArray(variable, subNode->arrayMode()); 400 break; 401 } 402 default: 403 break; 404 } 405 } 406 407 m_graph.voteChildren(node, VoteOther); 408 break; 409 } 410 411 default: 412 m_graph.voteChildren(node, VoteOther); 413 break; 414 } 415 } 416 } 417 } 418 419 // Disable hoisting on variables that appear to mostly be used in 420 // contexts where it doesn't make sense. 421 template <typename TypeCheck> 422 void disableHoistingForVariablesWithInsufficientVotes() 423 { 424 for (unsigned i = m_graph.m_variableAccessData.size(); i--;) { 425 VariableAccessData* variable = &m_graph.m_variableAccessData[i]; 426 if (!variable->isRoot()) 427 continue; 428 if (TypeCheck::hasEnoughVotesToHoist(variable)) 429 continue; 430 HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable); 431 if (iter == m_map.end()) 432 continue; 433 TypeCheck::disableHoisting(iter->value); 434 } 435 } 436 437 // Disable check hoisting for variables that cross the OSR entry that 438 // we're currently taking, and where the value currently does not have the 439 // particular form we want (e.g. a contradictory ArrayMode or Struture). 440 template <typename TypeCheck> 441 void disableHoistingAcrossOSREntries() 442 { 443 for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) { 444 BasicBlock* block = m_graph.block(blockIndex); 445 if (!block) 446 continue; 447 ASSERT(block->isReachable); 448 if (!block->isOSRTarget) 449 continue; 450 if (block->bytecodeBegin != m_graph.m_plan.osrEntryBytecodeIndex) 451 continue; 452 for (size_t i = 0; i < m_graph.m_plan.mustHandleValues.size(); ++i) { 453 int operand = m_graph.m_plan.mustHandleValues.operandForIndex(i); 454 Node* node = block->variablesAtHead.operand(operand); 455 if (!node) 456 continue; 457 VariableAccessData* variable = node->variableAccessData(); 458 HashMap<VariableAccessData*, CheckData>::iterator iter = m_map.find(variable); 459 if (iter == m_map.end()) 460 continue; 461 if (!TypeCheck::isValidToHoist(iter->value)) 462 continue; 463 JSValue value = m_graph.m_plan.mustHandleValues[i]; 464 if (!value || !value.isCell() || TypeCheck::isContravenedByValue(iter->value, value)) { 465 TypeCheck::disableHoisting(iter->value); 466 continue; 467 } 468 } 469 } 470 } 471 472 void disableCheckArrayHoisting(VariableAccessData* variable) 473 { 474 HashMap<VariableAccessData*, CheckData>::AddResult result = m_map.add(variable, CheckData()); 475 result.iterator->value.disableCheckArrayHoisting(); 476 } 477 478 template <typename TypeCheck> 479 bool shouldConsiderForHoisting(VariableAccessData* variable) 480 { 481 if (!variable->shouldUnboxIfPossible()) 482 return false; 483 if (TypeCheck::hoistingPreviouslyFailed(variable)) 484 return false; 485 if (!isCellSpeculation(variable->prediction())) 486 return false; 487 return true; 488 } 489 490 void noticeStructureCheck(VariableAccessData* variable, Structure* structure) 491 { 492 HashMap<VariableAccessData*, CheckData>::AddResult result = m_map.add(variable, CheckData(structure)); 493 if (result.isNewEntry) 494 return; 495 if (result.iterator->value.m_structure == structure) 496 return; 497 result.iterator->value.m_structure = 0; 498 } 499 500 void noticeStructureCheck(VariableAccessData* variable, const StructureSet& set) 501 { 502 if (set.size() != 1) { 503 noticeStructureCheck(variable, 0); 504 return; 505 } 506 noticeStructureCheck(variable, set.singletonStructure()); 507 } 508 509 void noticeCheckArray(VariableAccessData* variable, ArrayMode arrayMode) 510 { 511 HashMap<VariableAccessData*, CheckData>::AddResult result = m_map.add(variable, CheckData(arrayMode)); 512 if (result.isNewEntry) 513 return; 514 if (!result.iterator->value.m_arrayModeHoistingOkay) 515 return; 516 if (result.iterator->value.m_arrayMode == arrayMode) 517 return; 518 if (!result.iterator->value.m_arrayModeIsValid) { 519 result.iterator->value.m_arrayMode = arrayMode; 520 result.iterator->value.m_arrayModeIsValid = true; 521 return; 522 } 523 result.iterator->value.disableCheckArrayHoisting(); 524 } 525 526 void noticeStructureCheckAccountingForArrayMode(VariableAccessData* variable, Structure* structure) 527 { 528 HashMap<VariableAccessData*, CheckData>::iterator result = m_map.find(variable); 529 if (result == m_map.end()) 530 return; 531 if (!result->value.m_arrayModeHoistingOkay || !result->value.m_arrayModeIsValid) 532 return; 533 if (result->value.m_arrayMode.structureWouldPassArrayModeFiltering(structure)) 534 return; 535 result->value.disableCheckArrayHoisting(); 536 } 537 538 void noticeStructureCheckAccountingForArrayMode(VariableAccessData* variable, const StructureSet& set) 539 { 540 for (unsigned i = 0; i < set.size(); i++) 541 noticeStructureCheckAccountingForArrayMode(variable, set[i]); 542 } 543 544 HashMap<VariableAccessData*, CheckData> m_map; 545}; 546 547bool performTypeCheckHoisting(Graph& graph) 548{ 549 SamplingRegion samplingRegion("DFG Type Check Hoisting Phase"); 550 return runPhase<TypeCheckHoistingPhase>(graph); 551} 552 553struct ArrayTypeCheck { 554 static bool isValidToHoist(CheckData& checkData) 555 { 556 return checkData.m_arrayModeIsValid; 557 } 558 559 static void disableHoisting(CheckData& checkData) 560 { 561 checkData.disableCheckArrayHoisting(); 562 } 563 564 static bool isContravenedByValue(CheckData& checkData, JSValue value) 565 { 566 ASSERT(value.isCell()); 567 return !checkData.m_arrayMode.structureWouldPassArrayModeFiltering(value.asCell()->structure()); 568 } 569 570 static bool hasEnoughVotesToHoist(VariableAccessData* variable) 571 { 572 return variable->voteRatio() >= Options::checkArrayVoteRatioForHoisting(); 573 } 574 575 static bool hoistingPreviouslyFailed(VariableAccessData* variable) 576 { 577 return variable->checkArrayHoistingFailed(); 578 } 579}; 580 581struct StructureTypeCheck { 582 static bool isValidToHoist(CheckData& checkData) 583 { 584 return checkData.m_structure; 585 } 586 587 static void disableHoisting(CheckData& checkData) 588 { 589 checkData.m_structure = 0; 590 } 591 592 static bool isContravenedByValue(CheckData& checkData, JSValue value) 593 { 594 ASSERT(value.isCell()); 595 return checkData.m_structure != value.asCell()->structure(); 596 } 597 598 static bool hasEnoughVotesToHoist(VariableAccessData* variable) 599 { 600 return variable->voteRatio() >= Options::structureCheckVoteRatioForHoisting(); 601 } 602 603 static bool hoistingPreviouslyFailed(VariableAccessData* variable) 604 { 605 return variable->structureCheckHoistingFailed(); 606 } 607}; 608 609} } // namespace JSC::DFG 610 611#endif // ENABLE(DFG_JIT) 612 613 614