bytecode/BytecodeBasicBlock.cpp

   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
  33 namespace JSC {
  34
  35 static 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
  64 static bool isUnconditionalBranch(OpcodeID opcodeID)
  65 {
  66     switch (opcodeID) {
  67     case op_jmp:
  68         return true;
  69     default:
  70         return false;
  71     }
  72 }
  73
  74 static 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
  86 static 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
  97 static 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
 109 static void linkBlocks(BytecodeBasicBlock* predecessor, BytecodeBasicBlock* successor)
 110 {
 111     predecessor->addSuccessor(successor);
 112     successor->addPredecessor(predecessor);
 113 }
 114
 115 void 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