1 /* 2 * Copyright (C) 2011 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 "DFGByteCodeParser.h" 28 29 #if ENABLE(DFG_JIT) 30 31 #include "DFGAliasTracker.h" 32 #include "DFGScoreBoard.h" 33 #include "CodeBlock.h" 34 35 namespace JSC { namespace DFG { 36 37 #if ENABLE(DFG_JIT_RESTRICTIONS) 38 // FIXME: Temporarily disable arithmetic, until we fix associated performance regressions. 39 #define ARITHMETIC_OP() m_parseFailed = true 40 #else 41 #define ARITHMETIC_OP() ((void)0) 42 #endif 43 44 // === ByteCodeParser === 45 // 46 // This class is used to compile the dataflow graph from a CodeBlock. 47 class ByteCodeParser { 48 public: 49 ByteCodeParser(JSGlobalData* globalData, CodeBlock* codeBlock, Graph& graph) 50 : m_globalData(globalData) 51 , m_codeBlock(codeBlock) 52 , m_graph(graph) 53 , m_currentIndex(0) 54 , m_parseFailed(false) 55 , m_constantUndefined(UINT_MAX) 56 , m_constantNull(UINT_MAX) 57 , m_constant1(UINT_MAX) 58 , m_constants(codeBlock->numberOfConstantRegisters()) 59 , m_arguments(codeBlock->m_numParameters) 60 , m_variables(codeBlock->m_numVars) 61 , m_temporaries(codeBlock->m_numCalleeRegisters - codeBlock->m_numVars) 62 { 63 for (unsigned i = 0; i < m_temporaries.size(); ++i) 64 m_temporaries[i] = NoNode; 65 } 66 67 // Parse a full CodeBlock of bytecode. 68 bool parse(); 69 70 private: 71 // Parse a single basic block of bytecode instructions. 72 bool parseBlock(unsigned limit); 73 74 // Get/Set the operands/result of a bytecode instruction. 75 NodeIndex get(int operand) 76 { 77 // Is this a constant? 78 if (operand >= FirstConstantRegisterIndex) { 79 unsigned constant = operand - FirstConstantRegisterIndex; 80 ASSERT(constant < m_constants.size()); 81 return getJSConstant(constant); 82 } 83 84 // Is this an argument? 85 if (operand < 0) 86 return getArgument(operand); 87 88 // Is this a variable? 89 unsigned numVariables = m_variables.size(); 90 if ((unsigned)operand < numVariables) 91 return getVariable((unsigned)operand); 92 93 // Must be a temporary. 94 unsigned temporary = (unsigned)operand - numVariables; 95 ASSERT(temporary < m_temporaries.size()); 96 return getTemporary(temporary); 97 } 98 void set(int operand, NodeIndex value) 99 { 100 // Is this an argument? 101 if (operand < 0) { 102 setArgument(operand, value); 103 return; 104 } 105 106 // Is this a variable? 107 unsigned numVariables = m_variables.size(); 108 if ((unsigned)operand < numVariables) { 109 setVariable((unsigned)operand, value); 110 return; 111 } 112 113 // Must be a temporary. 114 unsigned temporary = (unsigned)operand - numVariables; 115 ASSERT(temporary < m_temporaries.size()); 116 setTemporary(temporary, value); 117 } 118 119 // Used in implementing get/set, above, where the operand is a local variable. 120 NodeIndex getVariable(unsigned operand) 121 { 122 NodeIndex setNode = m_variables[operand].set; 123 if (setNode != NoNode) 124 return m_graph[setNode].child1; 125 126 NodeIndex getNode = m_variables[operand].get; 127 if (getNode != NoNode) 128 return getNode; 129 130 getNode = addToGraph(GetLocal, OpInfo(operand)); 131 m_variables[operand].get = getNode; 132 return getNode; 133 } 134 void setVariable(unsigned operand, NodeIndex value) 135 { 136 NodeIndex priorSet = m_variables[operand].set; 137 m_variables[operand].set = addToGraph(SetLocal, OpInfo(operand), value); 138 if (priorSet != NoNode) 139 m_graph.deref(priorSet); 140 } 141 142 // Used in implementing get/set, above, where the operand is a temporary. 143 NodeIndex getTemporary(unsigned operand) 144 { 145 NodeIndex index = m_temporaries[operand]; 146 if (index != NoNode) 147 return index; 148 149 // Detect a read of an temporary that is not a yet defined within this block (e.g. use of ?:). 150 m_parseFailed = true; 151 return constantUndefined(); 152 } 153 void setTemporary(unsigned operand, NodeIndex value) 154 { 155 m_temporaries[operand] = value; 156 } 157 158 // Used in implementing get/set, above, where the operand is an argument. 159 NodeIndex getArgument(unsigned operand) 160 { 161 unsigned argument = operand + m_codeBlock->m_numParameters + RegisterFile::CallFrameHeaderSize; 162 ASSERT(argument < m_arguments.size()); 163 164 NodeIndex setNode = m_arguments[argument].set; 165 if (setNode != NoNode) 166 return m_graph[setNode].child1; 167 168 NodeIndex getNode = m_arguments[argument].get; 169 if (getNode != NoNode) 170 return getNode; 171 172 getNode = addToGraph(GetLocal, OpInfo(operand)); 173 m_arguments[argument].get = getNode; 174 return getNode; 175 } 176 void setArgument(int operand, NodeIndex value) 177 { 178 unsigned argument = operand + m_codeBlock->m_numParameters + RegisterFile::CallFrameHeaderSize; 179 ASSERT(argument < m_arguments.size()); 180 181 NodeIndex priorSet = m_arguments[argument].set; 182 m_arguments[argument].set = addToGraph(SetLocal, OpInfo(operand), value); 183 if (priorSet != NoNode) 184 m_graph.deref(priorSet); 185 } 186 187 // Get an operand, and perform a ToInt32/ToNumber conversion on it. 188 NodeIndex getToInt32(int operand) 189 { 190 // Avoid wastefully adding a JSConstant node to the graph, only to 191 // replace it with a Int32Constant (which is what would happen if 192 // we called 'toInt32(get(operand))' in this case). 193 if (operand >= FirstConstantRegisterIndex) { 194 JSValue v = m_codeBlock->getConstant(operand); 195 if (v.isInt32()) 196 return getInt32Constant(v.asInt32(), operand - FirstConstantRegisterIndex); 197 } 198 return toInt32(get(operand)); 199 } 200 NodeIndex getToNumber(int operand) 201 { 202 // Avoid wastefully adding a JSConstant node to the graph, only to 203 // replace it with a DoubleConstant (which is what would happen if 204 // we called 'toNumber(get(operand))' in this case). 205 if (operand >= FirstConstantRegisterIndex) { 206 JSValue v = m_codeBlock->getConstant(operand); 207 if (v.isNumber()) 208 return getDoubleConstant(v.uncheckedGetNumber(), operand - FirstConstantRegisterIndex); 209 } 210 return toNumber(get(operand)); 211 } 212 213 // Perform an ES5 ToInt32 operation - returns a node of type NodeResultInt32. 214 NodeIndex toInt32(NodeIndex index) 215 { 216 Node& node = m_graph[index]; 217 218 if (node.hasInt32Result()) 219 return index; 220 221 if (node.hasDoubleResult()) { 222 if (node.op == DoubleConstant) 223 return getInt32Constant(JSC::toInt32(valueOfDoubleConstant(index)), node.constantNumber()); 224 // 'NumberToInt32(Int32ToNumber(X))' == X, and 'NumberToInt32(UInt32ToNumber(X)) == X' 225 if (node.op == Int32ToNumber || node.op == UInt32ToNumber) 226 return node.child1; 227 228 // We unique NumberToInt32 nodes in a map to prevent duplicate conversions. 229 pair<UnaryOpMap::iterator, bool> result = m_numberToInt32Nodes.add(index, NoNode); 230 // Either we added a new value, or the existing value in the map is non-zero. 231 ASSERT(result.second == (result.first->second == NoNode)); 232 if (result.second) 233 result.first->second = addToGraph(NumberToInt32, index); 234 return result.first->second; 235 } 236 237 // Check for numeric constants boxed as JSValues. 238 if (node.op == JSConstant) { 239 JSValue v = valueOfJSConstant(index); 240 if (v.isInt32()) 241 return getInt32Constant(v.asInt32(), node.constantNumber()); 242 if (v.isNumber()) 243 return getInt32Constant(JSC::toInt32(v.uncheckedGetNumber()), node.constantNumber()); 244 } 245 246 return addToGraph(ValueToInt32, index); 247 } 248 249 // Perform an ES5 ToNumber operation - returns a node of type NodeResultDouble. 250 NodeIndex toNumber(NodeIndex index) 251 { 252 Node& node = m_graph[index]; 253 254 if (node.hasDoubleResult()) 255 return index; 256 257 if (node.hasInt32Result()) { 258 if (node.op == Int32Constant) 259 return getDoubleConstant(valueOfInt32Constant(index), node.constantNumber()); 260 261 // We unique Int32ToNumber nodes in a map to prevent duplicate conversions. 262 pair<UnaryOpMap::iterator, bool> result = m_int32ToNumberNodes.add(index, NoNode); 263 // Either we added a new value, or the existing value in the map is non-zero. 264 ASSERT(result.second == (result.first->second == NoNode)); 265 if (result.second) 266 result.first->second = addToGraph(Int32ToNumber, index); 267 return result.first->second; 268 } 269 270 if (node.op == JSConstant) { 271 JSValue v = valueOfJSConstant(index); 272 if (v.isNumber()) 273 return getDoubleConstant(v.uncheckedGetNumber(), node.constantNumber()); 274 } 275 276 return addToGraph(ValueToNumber, index); 277 } 278 279 280 // Used in implementing get, above, where the operand is a constant. 281 NodeIndex getInt32Constant(int32_t value, unsigned constant) 282 { 283 NodeIndex index = m_constants[constant].asInt32; 284 if (index != NoNode) 285 return index; 286 NodeIndex resultIndex = addToGraph(Int32Constant, OpInfo(constant)); 287 m_graph[resultIndex].setInt32Constant(value); 288 m_constants[constant].asInt32 = resultIndex; 289 return resultIndex; 290 } 291 NodeIndex getDoubleConstant(double value, unsigned constant) 292 { 293 NodeIndex index = m_constants[constant].asNumeric; 294 if (index != NoNode) 295 return index; 296 NodeIndex resultIndex = addToGraph(DoubleConstant, OpInfo(constant)); 297 m_graph[resultIndex].setDoubleConstant(value); 298 m_constants[constant].asNumeric = resultIndex; 299 return resultIndex; 300 } 301 NodeIndex getJSConstant(unsigned constant) 302 { 303 NodeIndex index = m_constants[constant].asJSValue; 304 if (index != NoNode) 305 return index; 306 307 NodeIndex resultIndex = addToGraph(JSConstant, OpInfo(constant)); 308 m_constants[constant].asJSValue = resultIndex; 309 return resultIndex; 310 } 311 312 // Helper functions to get/set the this value. 313 NodeIndex getThis() 314 { 315 return getArgument(m_codeBlock->thisRegister()); 316 } 317 void setThis(NodeIndex value) 318 { 319 setArgument(m_codeBlock->thisRegister(), value); 320 } 321 322 // Convenience methods for checking nodes for constants. 323 bool isInt32Constant(NodeIndex index) 324 { 325 return m_graph[index].op == Int32Constant; 326 } 327 bool isDoubleConstant(NodeIndex index) 328 { 329 return m_graph[index].op == DoubleConstant; 330 } 331 bool isJSConstant(NodeIndex index) 332 { 333 return m_graph[index].op == JSConstant; 334 } 335 336 // Convenience methods for getting constant values. 337 int32_t valueOfInt32Constant(NodeIndex index) 338 { 339 ASSERT(isInt32Constant(index)); 340 return m_graph[index].int32Constant(); 341 } 342 double valueOfDoubleConstant(NodeIndex index) 343 { 344 ASSERT(isDoubleConstant(index)); 345 return m_graph[index].numericConstant(); 346 } 347 JSValue valueOfJSConstant(NodeIndex index) 348 { 349 ASSERT(isJSConstant(index)); 350 return m_codeBlock->getConstant(FirstConstantRegisterIndex + m_graph[index].constantNumber()); 351 } 352 353 // This method returns a JSConstant with the value 'undefined'. 354 NodeIndex constantUndefined() 355 { 356 // Has m_constantUndefined been set up yet? 357 if (m_constantUndefined == UINT_MAX) { 358 // Search the constant pool for undefined, if we find it, we can just reuse this! 359 unsigned numberOfConstants = m_codeBlock->numberOfConstantRegisters(); 360 for (m_constantUndefined = 0; m_constantUndefined < numberOfConstants; ++m_constantUndefined) { 361 JSValue testMe = m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constantUndefined); 362 if (testMe.isUndefined()) 363 return getJSConstant(m_constantUndefined); 364 } 365 366 // Add undefined to the CodeBlock's constants, and add a corresponding slot in m_constants. 367 ASSERT(m_constants.size() == numberOfConstants); 368 m_codeBlock->addConstant(jsUndefined()); 369 m_constants.append(ConstantRecord()); 370 ASSERT(m_constants.size() == m_codeBlock->numberOfConstantRegisters()); 371 } 372 373 // m_constantUndefined must refer to an entry in the CodeBlock's constant pool that has the value 'undefined'. 374 ASSERT(m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constantUndefined).isUndefined()); 375 return getJSConstant(m_constantUndefined); 376 } 377 378 // This method returns a JSConstant with the value 'null'. 379 NodeIndex constantNull() 380 { 381 // Has m_constantNull been set up yet? 382 if (m_constantNull == UINT_MAX) { 383 // Search the constant pool for null, if we find it, we can just reuse this! 384 unsigned numberOfConstants = m_codeBlock->numberOfConstantRegisters(); 385 for (m_constantNull = 0; m_constantNull < numberOfConstants; ++m_constantNull) { 386 JSValue testMe = m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constantNull); 387 if (testMe.isNull()) 388 return getJSConstant(m_constantNull); 389 } 390 391 // Add null to the CodeBlock's constants, and add a corresponding slot in m_constants. 392 ASSERT(m_constants.size() == numberOfConstants); 393 m_codeBlock->addConstant(jsNull()); 394 m_constants.append(ConstantRecord()); 395 ASSERT(m_constants.size() == m_codeBlock->numberOfConstantRegisters()); 396 } 397 398 // m_constantNull must refer to an entry in the CodeBlock's constant pool that has the value 'null'. 399 ASSERT(m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constantNull).isNull()); 400 return getJSConstant(m_constantNull); 401 } 402 403 // This method returns a DoubleConstant with the value 1. 404 NodeIndex one() 405 { 406 // Has m_constant1 been set up yet? 407 if (m_constant1 == UINT_MAX) { 408 // Search the constant pool for the value 1, if we find it, we can just reuse this! 409 unsigned numberOfConstants = m_codeBlock->numberOfConstantRegisters(); 410 for (m_constant1 = 0; m_constant1 < numberOfConstants; ++m_constant1) { 411 JSValue testMe = m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constant1); 412 if (testMe.isInt32() && testMe.asInt32() == 1) 413 return getDoubleConstant(1, m_constant1); 414 } 415 416 // Add the value 1 to the CodeBlock's constants, and add a corresponding slot in m_constants. 417 ASSERT(m_constants.size() == numberOfConstants); 418 m_codeBlock->addConstant(jsNumber(1)); 419 m_constants.append(ConstantRecord()); 420 ASSERT(m_constants.size() == m_codeBlock->numberOfConstantRegisters()); 421 } 422 423 // m_constant1 must refer to an entry in the CodeBlock's constant pool that has the integer value 1. 424 ASSERT(m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constant1).isInt32()); 425 ASSERT(m_codeBlock->getConstant(FirstConstantRegisterIndex + m_constant1).asInt32() == 1); 426 return getDoubleConstant(1, m_constant1); 427 } 428 429 430 // These methods create a node and add it to the graph. If nodes of this type are 431 // 'mustGenerate' then the node will implicitly be ref'ed to ensure generation. 432 NodeIndex addToGraph(NodeType op, NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode) 433 { 434 NodeIndex resultIndex = (NodeIndex)m_graph.size(); 435 m_graph.append(Node(op, m_currentIndex, child1, child2, child3)); 436 437 if (op & NodeMustGenerate) 438 m_graph.ref(resultIndex); 439 return resultIndex; 440 } 441 NodeIndex addToGraph(NodeType op, OpInfo info, NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode) 442 { 443 NodeIndex resultIndex = (NodeIndex)m_graph.size(); 444 m_graph.append(Node(op, m_currentIndex, info, child1, child2, child3)); 445 446 if (op & NodeMustGenerate) 447 m_graph.ref(resultIndex); 448 return resultIndex; 449 } 450 NodeIndex addToGraph(NodeType op, OpInfo info1, OpInfo info2, NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode) 451 { 452 NodeIndex resultIndex = (NodeIndex)m_graph.size(); 453 m_graph.append(Node(op, m_currentIndex, info1, info2, child1, child2, child3)); 454 455 if (op & NodeMustGenerate) 456 m_graph.ref(resultIndex); 457 return resultIndex; 458 } 459 460 JSGlobalData* m_globalData; 461 CodeBlock* m_codeBlock; 462 Graph& m_graph; 463 464 // The bytecode index of the current instruction being generated. 465 unsigned m_currentIndex; 466 467 // Record failures due to unimplemented functionality or regressions. 468 bool m_parseFailed; 469 470 // We use these values during code generation, and to avoid the need for 471 // special handling we make sure they are available as constants in the 472 // CodeBlock's constant pool. These variables are initialized to 473 // UINT_MAX, and lazily updated to hold an index into the CodeBlock's 474 // constant pool, as necessary. 475 unsigned m_constantUndefined; 476 unsigned m_constantNull; 477 unsigned m_constant1; 478 479 // A constant in the constant pool may be represented by more than one 480 // node in the graph, depending on the context in which it is being used. 481 struct ConstantRecord { 482 ConstantRecord() 483 : asInt32(NoNode) 484 , asNumeric(NoNode) 485 , asJSValue(NoNode) 486 { 487 } 488 489 NodeIndex asInt32; 490 NodeIndex asNumeric; 491 NodeIndex asJSValue; 492 }; 493 494 // For every local variable we track any existing get or set of the value. 495 // We track the get so that these may be shared, and we track the set to 496 // retrieve the current value, and to reference the final definition. 497 struct VariableRecord { 498 VariableRecord() 499 : get(NoNode) 500 , set(NoNode) 501 { 502 } 503 504 NodeIndex get; 505 NodeIndex set; 506 }; 507 508 // Track the index of the node whose result is the current value for every 509 // register value in the bytecode - argument, local, and temporary. 510 Vector <ConstantRecord, 32> m_constants; 511 Vector <VariableRecord, 32> m_arguments; 512 Vector <VariableRecord, 32> m_variables; 513 Vector <NodeIndex, 32> m_temporaries; 514 515 // These maps are used to unique ToNumber and ToInt32 operations. 516 typedef HashMap<NodeIndex, NodeIndex> UnaryOpMap; 517 UnaryOpMap m_int32ToNumberNodes; 518 UnaryOpMap m_numberToInt32Nodes; 519 }; 520 521 #define NEXT_OPCODE(name) \ 522 m_currentIndex += OPCODE_LENGTH(name); \ 523 continue 524 525 #define LAST_OPCODE(name) \ 526 m_currentIndex += OPCODE_LENGTH(name); \ 527 return !m_parseFailed 528 529 bool ByteCodeParser::parseBlock(unsigned limit) 530 { 531 // No need to reset state initially, since it has been set by the constructor. 532 if (m_currentIndex) { 533 for (unsigned i = 0; i < m_constants.size(); ++i) 534 m_constants[i] = ConstantRecord(); 535 for (unsigned i = 0; i < m_variables.size(); ++i) 536 m_variables[i] = VariableRecord(); 537 for (unsigned i = 0; i < m_arguments.size(); ++i) 538 m_arguments[i] = VariableRecord(); 539 for (unsigned i = 0; i < m_temporaries.size(); ++i) 540 m_temporaries[i] = NoNode; 541 } 542 543 AliasTracker aliases(m_graph); 544 545 Interpreter* interpreter = m_globalData->interpreter; 546 Instruction* instructionsBegin = m_codeBlock->instructions().begin(); 547 while (true) { 548 // Don't extend over jump destinations. 549 if (m_currentIndex == limit) { 550 addToGraph(Jump, OpInfo(m_currentIndex)); 551 return !m_parseFailed; 552 } 553 554 // Switch on the current bytecode opcode. 555 Instruction* currentInstruction = instructionsBegin + m_currentIndex; 556 switch (interpreter->getOpcodeID(currentInstruction->u.opcode)) { 557 558 // === Function entry opcodes === 559 560 case op_enter: 561 // Initialize all locals to undefined. 562 for (int i = 0; i < m_codeBlock->m_numVars; ++i) 563 set(i, constantUndefined()); 564 NEXT_OPCODE(op_enter); 565 566 case op_convert_this: { 567 NodeIndex op1 = getThis(); 568 setThis(addToGraph(ConvertThis, op1)); 569 NEXT_OPCODE(op_convert_this); 570 } 571 572 // === Bitwise operations === 573 574 case op_bitand: { 575 NodeIndex op1 = getToInt32(currentInstruction[2].u.operand); 576 NodeIndex op2 = getToInt32(currentInstruction[3].u.operand); 577 set(currentInstruction[1].u.operand, addToGraph(BitAnd, op1, op2)); 578 NEXT_OPCODE(op_bitand); 579 } 580 581 case op_bitor: { 582 NodeIndex op1 = getToInt32(currentInstruction[2].u.operand); 583 NodeIndex op2 = getToInt32(currentInstruction[3].u.operand); 584 set(currentInstruction[1].u.operand, addToGraph(BitOr, op1, op2)); 585 NEXT_OPCODE(op_bitor); 586 } 587 588 case op_bitxor: { 589 NodeIndex op1 = getToInt32(currentInstruction[2].u.operand); 590 NodeIndex op2 = getToInt32(currentInstruction[3].u.operand); 591 set(currentInstruction[1].u.operand, addToGraph(BitXor, op1, op2)); 592 NEXT_OPCODE(op_bitxor); 593 } 594 595 case op_rshift: { 596 NodeIndex op1 = getToInt32(currentInstruction[2].u.operand); 597 NodeIndex op2 = getToInt32(currentInstruction[3].u.operand); 598 NodeIndex result; 599 // Optimize out shifts by zero. 600 if (isInt32Constant(op2) && !(valueOfInt32Constant(op2) & 0x1f)) 601 result = op1; 602 else 603 result = addToGraph(BitRShift, op1, op2); 604 set(currentInstruction[1].u.operand, result); 605 NEXT_OPCODE(op_rshift); 606 } 607 608 case op_lshift: { 609 NodeIndex op1 = getToInt32(currentInstruction[2].u.operand); 610 NodeIndex op2 = getToInt32(currentInstruction[3].u.operand); 611 NodeIndex result; 612 // Optimize out shifts by zero. 613 if (isInt32Constant(op2) && !(valueOfInt32Constant(op2) & 0x1f)) 614 result = op1; 615 else 616 result = addToGraph(BitLShift, op1, op2); 617 set(currentInstruction[1].u.operand, result); 618 NEXT_OPCODE(op_lshift); 619 } 620 621 case op_urshift: { 622 NodeIndex op1 = getToInt32(currentInstruction[2].u.operand); 623 NodeIndex op2 = getToInt32(currentInstruction[3].u.operand); 624 NodeIndex result; 625 // The result of a zero-extending right shift is treated as an unsigned value. 626 // This means that if the top bit is set, the result is not in the int32 range, 627 // and as such must be stored as a double. If the shift amount is a constant, 628 // we may be able to optimize. 629 if (isInt32Constant(op2)) { 630 // If we know we are shifting by a non-zero amount, then since the operation 631 // zero fills we know the top bit of the result must be zero, and as such the 632 // result must be within the int32 range. Conversely, if this is a shift by 633 // zero, then the result may be changed by the conversion to unsigned, but it 634 // is not necessary to perform the shift! 635 if (valueOfInt32Constant(op2) & 0x1f) 636 result = addToGraph(BitURShift, op1, op2); 637 else 638 result = addToGraph(UInt32ToNumber, op1); 639 } else { 640 // Cannot optimize at this stage; shift & potentially rebox as a double. 641 result = addToGraph(BitURShift, op1, op2); 642 result = addToGraph(UInt32ToNumber, result); 643 } 644 set(currentInstruction[1].u.operand, result); 645 NEXT_OPCODE(op_urshift); 646 } 647 648 // === Increment/Decrement opcodes === 649 650 case op_pre_inc: { 651 unsigned srcDst = currentInstruction[1].u.operand; 652 NodeIndex op = getToNumber(srcDst); 653 set(srcDst, addToGraph(ArithAdd, op, one())); 654 NEXT_OPCODE(op_pre_inc); 655 } 656 657 case op_post_inc: { 658 unsigned result = currentInstruction[1].u.operand; 659 unsigned srcDst = currentInstruction[2].u.operand; 660 NodeIndex op = getToNumber(srcDst); 661 set(result, op); 662 set(srcDst, addToGraph(ArithAdd, op, one())); 663 NEXT_OPCODE(op_post_inc); 664 } 665 666 case op_pre_dec: { 667 unsigned srcDst = currentInstruction[1].u.operand; 668 NodeIndex op = getToNumber(srcDst); 669 set(srcDst, addToGraph(ArithSub, op, one())); 670 NEXT_OPCODE(op_pre_dec); 671 } 672 673 case op_post_dec: { 674 unsigned result = currentInstruction[1].u.operand; 675 unsigned srcDst = currentInstruction[2].u.operand; 676 NodeIndex op = getToNumber(srcDst); 677 set(result, op); 678 set(srcDst, addToGraph(ArithSub, op, one())); 679 NEXT_OPCODE(op_post_dec); 680 } 681 682 // === Arithmetic operations === 683 684 case op_add: { 685 ARITHMETIC_OP(); 686 NodeIndex op1 = get(currentInstruction[2].u.operand); 687 NodeIndex op2 = get(currentInstruction[3].u.operand); 688 // If both operands can statically be determined to the numbers, then this is an arithmetic add. 689 // Otherwise, we must assume this may be performing a concatenation to a string. 690 if (m_graph[op1].hasNumericResult() && m_graph[op2].hasNumericResult()) 691 set(currentInstruction[1].u.operand, addToGraph(ArithAdd, toNumber(op1), toNumber(op2))); 692 else 693 set(currentInstruction[1].u.operand, addToGraph(ValueAdd, op1, op2)); 694 NEXT_OPCODE(op_add); 695 } 696 697 case op_sub: { 698 ARITHMETIC_OP(); 699 NodeIndex op1 = getToNumber(currentInstruction[2].u.operand); 700 NodeIndex op2 = getToNumber(currentInstruction[3].u.operand); 701 set(currentInstruction[1].u.operand, addToGraph(ArithSub, op1, op2)); 702 NEXT_OPCODE(op_sub); 703 } 704 705 case op_mul: { 706 ARITHMETIC_OP(); 707 NodeIndex op1 = getToNumber(currentInstruction[2].u.operand); 708 NodeIndex op2 = getToNumber(currentInstruction[3].u.operand); 709 set(currentInstruction[1].u.operand, addToGraph(ArithMul, op1, op2)); 710 NEXT_OPCODE(op_mul); 711 } 712 713 case op_mod: { 714 ARITHMETIC_OP(); 715 NodeIndex op1 = getToNumber(currentInstruction[2].u.operand); 716 NodeIndex op2 = getToNumber(currentInstruction[3].u.operand); 717 set(currentInstruction[1].u.operand, addToGraph(ArithMod, op1, op2)); 718 NEXT_OPCODE(op_mod); 719 } 720 721 case op_div: { 722 ARITHMETIC_OP(); 723 NodeIndex op1 = getToNumber(currentInstruction[2].u.operand); 724 NodeIndex op2 = getToNumber(currentInstruction[3].u.operand); 725 set(currentInstruction[1].u.operand, addToGraph(ArithDiv, op1, op2)); 726 NEXT_OPCODE(op_div); 727 } 728 729 // === Misc operations === 730 731 case op_mov: { 732 NodeIndex op = get(currentInstruction[2].u.operand); 733 set(currentInstruction[1].u.operand, op); 734 NEXT_OPCODE(op_mov); 735 } 736 737 case op_not: { 738 ARITHMETIC_OP(); 739 NodeIndex value = get(currentInstruction[2].u.operand); 740 set(currentInstruction[1].u.operand, addToGraph(LogicalNot, value)); 741 NEXT_OPCODE(op_not); 742 } 743 744 case op_less: { 745 ARITHMETIC_OP(); 746 NodeIndex op1 = get(currentInstruction[2].u.operand); 747 NodeIndex op2 = get(currentInstruction[3].u.operand); 748 set(currentInstruction[1].u.operand, addToGraph(CompareLess, op1, op2)); 749 NEXT_OPCODE(op_less); 750 } 751 752 case op_lesseq: { 753 ARITHMETIC_OP(); 754 NodeIndex op1 = get(currentInstruction[2].u.operand); 755 NodeIndex op2 = get(currentInstruction[3].u.operand); 756 set(currentInstruction[1].u.operand, addToGraph(CompareLessEq, op1, op2)); 757 NEXT_OPCODE(op_lesseq); 758 } 759 760 case op_eq: { 761 ARITHMETIC_OP(); 762 NodeIndex op1 = get(currentInstruction[2].u.operand); 763 NodeIndex op2 = get(currentInstruction[3].u.operand); 764 set(currentInstruction[1].u.operand, addToGraph(CompareEq, op1, op2)); 765 NEXT_OPCODE(op_eq); 766 } 767 768 case op_eq_null: { 769 ARITHMETIC_OP(); 770 NodeIndex value = get(currentInstruction[2].u.operand); 771 set(currentInstruction[1].u.operand, addToGraph(CompareEq, value, constantNull())); 772 NEXT_OPCODE(op_eq_null); 773 } 774 775 case op_stricteq: { 776 ARITHMETIC_OP(); 777 NodeIndex op1 = get(currentInstruction[2].u.operand); 778 NodeIndex op2 = get(currentInstruction[3].u.operand); 779 set(currentInstruction[1].u.operand, addToGraph(CompareStrictEq, op1, op2)); 780 NEXT_OPCODE(op_stricteq); 781 } 782 783 case op_neq: { 784 ARITHMETIC_OP(); 785 NodeIndex op1 = get(currentInstruction[2].u.operand); 786 NodeIndex op2 = get(currentInstruction[3].u.operand); 787 set(currentInstruction[1].u.operand, addToGraph(LogicalNot, addToGraph(CompareEq, op1, op2))); 788 NEXT_OPCODE(op_neq); 789 } 790 791 case op_neq_null: { 792 ARITHMETIC_OP(); 793 NodeIndex value = get(currentInstruction[2].u.operand); 794 set(currentInstruction[1].u.operand, addToGraph(LogicalNot, addToGraph(CompareEq, value, constantNull()))); 795 NEXT_OPCODE(op_neq_null); 796 } 797 798 case op_nstricteq: { 799 ARITHMETIC_OP(); 800 NodeIndex op1 = get(currentInstruction[2].u.operand); 801 NodeIndex op2 = get(currentInstruction[3].u.operand); 802 set(currentInstruction[1].u.operand, addToGraph(LogicalNot, addToGraph(CompareStrictEq, op1, op2))); 803 NEXT_OPCODE(op_nstricteq); 804 } 805 806 // === Property access operations === 807 808 case op_get_by_val: { 809 NodeIndex base = get(currentInstruction[2].u.operand); 810 NodeIndex property = get(currentInstruction[3].u.operand); 811 812 NodeIndex getByVal = addToGraph(GetByVal, base, property, aliases.lookupGetByVal(base, property)); 813 set(currentInstruction[1].u.operand, getByVal); 814 aliases.recordGetByVal(getByVal); 815 816 NEXT_OPCODE(op_get_by_val); 817 } 818 819 case op_put_by_val: { 820 NodeIndex base = get(currentInstruction[1].u.operand); 821 NodeIndex property = get(currentInstruction[2].u.operand); 822 NodeIndex value = get(currentInstruction[3].u.operand); 823 824 NodeIndex aliasedGet = aliases.lookupGetByVal(base, property); 825 NodeIndex putByVal = addToGraph(aliasedGet != NoNode ? PutByValAlias : PutByVal, base, property, value); 826 aliases.recordPutByVal(putByVal); 827 828 NEXT_OPCODE(op_put_by_val); 829 } 830 831 case op_get_by_id: { 832 NodeIndex base = get(currentInstruction[2].u.operand); 833 unsigned identifier = currentInstruction[3].u.operand; 834 835 NodeIndex getById = addToGraph(GetById, OpInfo(identifier), base); 836 set(currentInstruction[1].u.operand, getById); 837 aliases.recordGetById(getById); 838 839 NEXT_OPCODE(op_get_by_id); 840 } 841 842 case op_put_by_id: { 843 NodeIndex value = get(currentInstruction[3].u.operand); 844 NodeIndex base = get(currentInstruction[1].u.operand); 845 unsigned identifier = currentInstruction[2].u.operand; 846 bool direct = currentInstruction[8].u.operand; 847 848 if (direct) { 849 NodeIndex putByIdDirect = addToGraph(PutByIdDirect, OpInfo(identifier), base, value); 850 aliases.recordPutByIdDirect(putByIdDirect); 851 } else { 852 NodeIndex putById = addToGraph(PutById, OpInfo(identifier), base, value); 853 aliases.recordPutById(putById); 854 } 855 856 NEXT_OPCODE(op_put_by_id); 857 } 858 859 case op_get_global_var: { 860 NodeIndex getGlobalVar = addToGraph(GetGlobalVar, OpInfo(currentInstruction[2].u.operand)); 861 set(currentInstruction[1].u.operand, getGlobalVar); 862 NEXT_OPCODE(op_get_global_var); 863 } 864 865 case op_put_global_var: { 866 NodeIndex value = get(currentInstruction[2].u.operand); 867 addToGraph(PutGlobalVar, OpInfo(currentInstruction[1].u.operand), value); 868 NEXT_OPCODE(op_put_global_var); 869 } 870 871 // === Block terminators. === 872 873 case op_jmp: { 874 unsigned relativeOffset = currentInstruction[1].u.operand; 875 addToGraph(Jump, OpInfo(m_currentIndex + relativeOffset)); 876 LAST_OPCODE(op_jmp); 877 } 878 879 case op_loop: { 880 unsigned relativeOffset = currentInstruction[1].u.operand; 881 addToGraph(Jump, OpInfo(m_currentIndex + relativeOffset)); 882 LAST_OPCODE(op_loop); 883 } 884 885 case op_jtrue: { 886 unsigned relativeOffset = currentInstruction[2].u.operand; 887 NodeIndex condition = get(currentInstruction[1].u.operand); 888 addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_jtrue)), condition); 889 LAST_OPCODE(op_jtrue); 890 } 891 892 case op_jfalse: { 893 unsigned relativeOffset = currentInstruction[2].u.operand; 894 NodeIndex condition = get(currentInstruction[1].u.operand); 895 addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_jfalse)), OpInfo(m_currentIndex + relativeOffset), condition); 896 LAST_OPCODE(op_jfalse); 897 } 898 899 case op_loop_if_true: { 900 unsigned relativeOffset = currentInstruction[2].u.operand; 901 NodeIndex condition = get(currentInstruction[1].u.operand); 902 addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_loop_if_true)), condition); 903 LAST_OPCODE(op_loop_if_true); 904 } 905 906 case op_loop_if_false: { 907 unsigned relativeOffset = currentInstruction[2].u.operand; 908 NodeIndex condition = get(currentInstruction[1].u.operand); 909 addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_loop_if_false)), OpInfo(m_currentIndex + relativeOffset), condition); 910 LAST_OPCODE(op_loop_if_false); 911 } 912 913 case op_jeq_null: { 914 unsigned relativeOffset = currentInstruction[2].u.operand; 915 NodeIndex value = get(currentInstruction[1].u.operand); 916 NodeIndex condition = addToGraph(CompareEq, value, constantNull()); 917 addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_jeq_null)), condition); 918 LAST_OPCODE(op_jeq_null); 919 } 920 921 case op_jneq_null: { 922 unsigned relativeOffset = currentInstruction[2].u.operand; 923 NodeIndex value = get(currentInstruction[1].u.operand); 924 NodeIndex condition = addToGraph(CompareEq, value, constantNull()); 925 addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_jneq_null)), OpInfo(m_currentIndex + relativeOffset), condition); 926 LAST_OPCODE(op_jneq_null); 927 } 928 929 case op_jnless: { 930 unsigned relativeOffset = currentInstruction[3].u.operand; 931 NodeIndex op1 = get(currentInstruction[1].u.operand); 932 NodeIndex op2 = get(currentInstruction[2].u.operand); 933 NodeIndex condition = addToGraph(CompareLess, op1, op2); 934 addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_jnless)), OpInfo(m_currentIndex + relativeOffset), condition); 935 LAST_OPCODE(op_jnless); 936 } 937 938 case op_jnlesseq: { 939 unsigned relativeOffset = currentInstruction[3].u.operand; 940 NodeIndex op1 = get(currentInstruction[1].u.operand); 941 NodeIndex op2 = get(currentInstruction[2].u.operand); 942 NodeIndex condition = addToGraph(CompareLessEq, op1, op2); 943 addToGraph(Branch, OpInfo(m_currentIndex + OPCODE_LENGTH(op_jnlesseq)), OpInfo(m_currentIndex + relativeOffset), condition); 944 LAST_OPCODE(op_jnlesseq); 945 } 946 947 case op_jless: { 948 unsigned relativeOffset = currentInstruction[3].u.operand; 949 NodeIndex op1 = get(currentInstruction[1].u.operand); 950 NodeIndex op2 = get(currentInstruction[2].u.operand); 951 NodeIndex condition = addToGraph(CompareLess, op1, op2); 952 addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_jless)), condition); 953 LAST_OPCODE(op_jless); 954 } 955 956 case op_jlesseq: { 957 unsigned relativeOffset = currentInstruction[3].u.operand; 958 NodeIndex op1 = get(currentInstruction[1].u.operand); 959 NodeIndex op2 = get(currentInstruction[2].u.operand); 960 NodeIndex condition = addToGraph(CompareLessEq, op1, op2); 961 addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_jlesseq)), condition); 962 LAST_OPCODE(op_jlesseq); 963 } 964 965 case op_loop_if_less: { 966 unsigned relativeOffset = currentInstruction[3].u.operand; 967 NodeIndex op1 = get(currentInstruction[1].u.operand); 968 NodeIndex op2 = get(currentInstruction[2].u.operand); 969 NodeIndex condition = addToGraph(CompareLess, op1, op2); 970 addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_loop_if_less)), condition); 971 LAST_OPCODE(op_loop_if_less); 972 } 973 974 case op_loop_if_lesseq: { 975 unsigned relativeOffset = currentInstruction[3].u.operand; 976 NodeIndex op1 = get(currentInstruction[1].u.operand); 977 NodeIndex op2 = get(currentInstruction[2].u.operand); 978 NodeIndex condition = addToGraph(CompareLessEq, op1, op2); 979 addToGraph(Branch, OpInfo(m_currentIndex + relativeOffset), OpInfo(m_currentIndex + OPCODE_LENGTH(op_loop_if_lesseq)), condition); 980 LAST_OPCODE(op_loop_if_lesseq); 981 } 982 983 case op_ret: { 984 addToGraph(Return, get(currentInstruction[1].u.operand)); 985 986 // FIXME: throw away terminal definitions of variables; 987 // should not be necessary once we have proper DCE! 988 for (unsigned i = 0; i < m_variables.size(); ++i) { 989 NodeIndex priorSet = m_variables[i].set; 990 if (priorSet != NoNode) 991 m_graph.deref(priorSet); 992 } 993 994 LAST_OPCODE(op_ret); 995 } 996 997 default: 998 // Parse failed! 999 return false; 1000 } 1001 } 1002 } 1003 1004 bool ByteCodeParser::parse() 1005 { 1006 // Set during construction. 1007 ASSERT(!m_currentIndex); 1008 1009 for (unsigned jumpTargetIndex = 0; jumpTargetIndex <= m_codeBlock->numberOfJumpTargets(); ++jumpTargetIndex) { 1010 // The maximum bytecode offset to go into the current basicblock is either the next jump target, or the end of the instructions. 1011 unsigned limit = jumpTargetIndex < m_codeBlock->numberOfJumpTargets() ? m_codeBlock->jumpTarget(jumpTargetIndex) : m_codeBlock->instructions().size(); 1012 ASSERT(m_currentIndex < limit); 1013 1014 // Loop until we reach the current limit (i.e. next jump target). 1015 do { 1016 unsigned bytecodeBegin = m_currentIndex; 1017 NodeIndex begin = m_graph.size(); 1018 1019 if (!parseBlock(limit)) 1020 return false; 1021 // We should not have gone beyond the limit. 1022 ASSERT(m_currentIndex <= limit); 1023 1024 NodeIndex end = m_graph.size(); 1025 m_graph.m_blocks.append(BasicBlock(bytecodeBegin, begin, end)); 1026 } while (m_currentIndex < limit); 1027 } 1028 1029 // Should have reached the end of the instructions. 1030 ASSERT(m_currentIndex == m_codeBlock->instructions().size()); 1031 1032 // Assign VirtualRegisters. 1033 ScoreBoard scoreBoard(m_graph, m_variables.size()); 1034 Node* nodes = m_graph.begin(); 1035 size_t size = m_graph.size(); 1036 for (size_t i = 0; i < size; ++i) { 1037 Node& node = nodes[i]; 1038 if (node.refCount) { 1039 // First, call use on all of the current node's children, then 1040 // allocate a VirtualRegister for this node. We do so in this 1041 // order so that if a child is on its last use, and a 1042 // VirtualRegister is freed, then it may be reused for node. 1043 scoreBoard.use(node.child1); 1044 scoreBoard.use(node.child2); 1045 scoreBoard.use(node.child3); 1046 node.virtualRegister = scoreBoard.allocate(); 1047 // 'mustGenerate' nodes have their useCount artificially elevated, 1048 // call use now to account for this. 1049 if (node.mustGenerate()) 1050 scoreBoard.use(i); 1051 } 1052 } 1053 1054 // 'm_numCalleeRegisters' is the number of locals and temporaries allocated 1055 // for the function (and checked for on entry). Since we perform a new and 1056 // different allocation of temporaries, more registers may now be required. 1057 unsigned calleeRegisters = scoreBoard.allocatedCount() + m_variables.size(); 1058 if ((unsigned)m_codeBlock->m_numCalleeRegisters < calleeRegisters) 1059 m_codeBlock->m_numCalleeRegisters = calleeRegisters; 1060 1061 #if DFG_DEBUG_VERBOSE 1062 m_graph.dump(m_codeBlock); 1063 #endif 1064 1065 return true; 1066 } 1067 1068 bool parse(Graph& graph, JSGlobalData* globalData, CodeBlock* codeBlock) 1069 { 1070 #if DFG_DEBUG_LOCAL_DISBALE 1071 UNUSED_PARAM(graph); 1072 UNUSED_PARAM(globalData); 1073 UNUSED_PARAM(codeBlock); 1074 return false; 1075 #else 1076 return ByteCodeParser(globalData, codeBlock, graph).parse(); 1077 #endif 1078 } 1079 1080 } } // namespace JSC::DFG 1081 1082 #endif 1083
