1/* 2 * Copyright (C) 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. AND ITS CONTRIBUTORS ``AS IS'' 14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS 17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 23 * THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26#include "config.h" 27#include "BytecodeBasicBlock.h" 28 29#include "CodeBlock.h" 30#include "JSCInlines.h" 31#include "PreciseJumpTargets.h" 32 33namespace JSC { 34 35static bool isBranch(OpcodeID opcodeID) 36{ 37 switch (opcodeID) { 38 case op_jmp: 39 case op_jtrue: 40 case op_jfalse: 41 case op_jeq_null: 42 case op_jneq_null: 43 case op_jneq_ptr: 44 case op_jless: 45 case op_jlesseq: 46 case op_jgreater: 47 case op_jgreatereq: 48 case op_jnless: 49 case op_jnlesseq: 50 case op_jngreater: 51 case op_jngreatereq: 52 case op_switch_imm: 53 case op_switch_char: 54 case op_switch_string: 55 case op_get_pnames: 56 case op_next_pname: 57 case op_check_has_instance: 58 return true; 59 default: 60 return false; 61 } 62} 63 64static bool isUnconditionalBranch(OpcodeID opcodeID) 65{ 66 switch (opcodeID) { 67 case op_jmp: 68 return true; 69 default: 70 return false; 71 } 72} 73 74static bool isTerminal(OpcodeID opcodeID) 75{ 76 switch (opcodeID) { 77 case op_ret: 78 case op_ret_object_or_this: 79 case op_end: 80 return true; 81 default: 82 return false; 83 } 84} 85 86static bool isThrow(OpcodeID opcodeID) 87{ 88 switch (opcodeID) { 89 case op_throw: 90 case op_throw_static_error: 91 return true; 92 default: 93 return false; 94 } 95} 96 97static bool isJumpTarget(OpcodeID opcodeID, Vector<unsigned, 32>& jumpTargets, unsigned bytecodeOffset) 98{ 99 if (opcodeID == op_catch) 100 return true; 101 102 for (unsigned i = 0; i < jumpTargets.size(); i++) { 103 if (bytecodeOffset == jumpTargets[i]) 104 return true; 105 } 106 return false; 107} 108 109static void linkBlocks(BytecodeBasicBlock* predecessor, BytecodeBasicBlock* successor) 110{ 111 predecessor->addSuccessor(successor); 112 successor->addPredecessor(predecessor); 113} 114 115void computeBytecodeBasicBlocks(CodeBlock* codeBlock, Vector<RefPtr<BytecodeBasicBlock> >& basicBlocks) 116{ 117 Vector<unsigned, 32> jumpTargets; 118 computePreciseJumpTargets(codeBlock, jumpTargets); 119 120 // Create the entry and exit basic blocks. 121 BytecodeBasicBlock* entry = new BytecodeBasicBlock(BytecodeBasicBlock::EntryBlock); 122 basicBlocks.append(adoptRef(entry)); 123 BytecodeBasicBlock* exit = new BytecodeBasicBlock(BytecodeBasicBlock::ExitBlock); 124 125 // Find basic block boundaries. 126 BytecodeBasicBlock* current = new BytecodeBasicBlock(0, 0); 127 linkBlocks(entry, current); 128 basicBlocks.append(adoptRef(current)); 129 130 bool nextInstructionIsLeader = false; 131 132 Interpreter* interpreter = codeBlock->vm()->interpreter; 133 Instruction* instructionsBegin = codeBlock->instructions().begin(); 134 unsigned instructionCount = codeBlock->instructions().size(); 135 for (unsigned bytecodeOffset = 0; bytecodeOffset < instructionCount;) { 136 OpcodeID opcodeID = interpreter->getOpcodeID(instructionsBegin[bytecodeOffset].u.opcode); 137 unsigned opcodeLength = opcodeLengths[opcodeID]; 138 139 bool createdBlock = false; 140 // If the current bytecode is a jump target, then it's the leader of its own basic block. 141 if (isJumpTarget(opcodeID, jumpTargets, bytecodeOffset) || nextInstructionIsLeader) { 142 BytecodeBasicBlock* block = new BytecodeBasicBlock(bytecodeOffset, opcodeLength); 143 basicBlocks.append(adoptRef(block)); 144 current = block; 145 createdBlock = true; 146 nextInstructionIsLeader = false; 147 bytecodeOffset += opcodeLength; 148 } 149 150 // If the current bytecode is a branch or a return, then the next instruction is the leader of its own basic block. 151 if (isBranch(opcodeID) || isTerminal(opcodeID) || isThrow(opcodeID)) 152 nextInstructionIsLeader = true; 153 154 if (createdBlock) 155 continue; 156 157 // Otherwise, just add to the length of the current block. 158 current->addBytecodeLength(opcodeLength); 159 bytecodeOffset += opcodeLength; 160 } 161 162 // Link basic blocks together. 163 for (unsigned i = 0; i < basicBlocks.size(); i++) { 164 BytecodeBasicBlock* block = basicBlocks[i].get(); 165 166 if (block->isEntryBlock() || block->isExitBlock()) 167 continue; 168 169 bool fallsThrough = true; 170 for (unsigned bytecodeOffset = block->leaderBytecodeOffset(); bytecodeOffset < block->leaderBytecodeOffset() + block->totalBytecodeLength();) { 171 const Instruction& currentInstruction = instructionsBegin[bytecodeOffset]; 172 OpcodeID opcodeID = interpreter->getOpcodeID(currentInstruction.u.opcode); 173 unsigned opcodeLength = opcodeLengths[opcodeID]; 174 // If we found a terminal bytecode, link to the exit block. 175 if (isTerminal(opcodeID)) { 176 ASSERT(bytecodeOffset + opcodeLength == block->leaderBytecodeOffset() + block->totalBytecodeLength()); 177 linkBlocks(block, exit); 178 fallsThrough = false; 179 break; 180 } 181 182 // If we found a throw, get the HandlerInfo for this instruction to see where we will jump. 183 // If there isn't one, treat this throw as a terminal. This is true even if we have a finally 184 // block because the finally block will create its own catch, which will generate a HandlerInfo. 185 if (isThrow(opcodeID)) { 186 ASSERT(bytecodeOffset + opcodeLength == block->leaderBytecodeOffset() + block->totalBytecodeLength()); 187 HandlerInfo* handler = codeBlock->handlerForBytecodeOffset(bytecodeOffset); 188 fallsThrough = false; 189 if (!handler) { 190 linkBlocks(block, exit); 191 break; 192 } 193 for (unsigned i = 0; i < basicBlocks.size(); i++) { 194 BytecodeBasicBlock* otherBlock = basicBlocks[i].get(); 195 if (handler->target == otherBlock->leaderBytecodeOffset()) { 196 linkBlocks(block, otherBlock); 197 break; 198 } 199 } 200 break; 201 } 202 203 // If we found a branch, link to the block(s) that we jump to. 204 if (isBranch(opcodeID)) { 205 ASSERT(bytecodeOffset + opcodeLength == block->leaderBytecodeOffset() + block->totalBytecodeLength()); 206 Vector<unsigned, 1> bytecodeOffsetsJumpedTo; 207 findJumpTargetsForBytecodeOffset(codeBlock, bytecodeOffset, bytecodeOffsetsJumpedTo); 208 209 for (unsigned i = 0; i < basicBlocks.size(); i++) { 210 BytecodeBasicBlock* otherBlock = basicBlocks[i].get(); 211 if (bytecodeOffsetsJumpedTo.contains(otherBlock->leaderBytecodeOffset())) 212 linkBlocks(block, otherBlock); 213 } 214 215 if (isUnconditionalBranch(opcodeID)) 216 fallsThrough = false; 217 218 break; 219 } 220 bytecodeOffset += opcodeLength; 221 } 222 223 // If we fall through then link to the next block in program order. 224 if (fallsThrough) { 225 ASSERT(i + 1 < basicBlocks.size()); 226 BytecodeBasicBlock* nextBlock = basicBlocks[i + 1].get(); 227 linkBlocks(block, nextBlock); 228 } 229 } 230 231 basicBlocks.append(adoptRef(exit)); 232} 233 234} // namespace JSC 235