git.saurik.com Git - apple/javascriptcore.git/blob - bytecode/BytecodeBasicBlock.cpp

1 /*

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 */

26 #include "config.h"

27 #include "BytecodeBasicBlock.h"

29 #include "CodeBlock.h"

30 #include "JSCInlines.h"

31 #include "PreciseJumpTargets.h"

33 namespace JSC {

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_check_has_instance:

56 return true;

57 default:

58 return false;

59 }

60 }

62 static bool isUnconditionalBranch(OpcodeID opcodeID)

63 {

64 switch (opcodeID) {

65 case op_jmp:

66 return true;

67 default:

68 return false;

69 }

70 }

72 static bool isTerminal(OpcodeID opcodeID)

73 {

74 switch (opcodeID) {

75 case op_ret:

76 case op_end:

77 return true;

78 default:

79 return false;

80 }

81 }

83 static bool isThrow(OpcodeID opcodeID)

84 {

85 switch (opcodeID) {

86 case op_throw:

87 case op_throw_static_error:

88 return true;

89 default:

90 return false;

91 }

92 }

 static bool isJumpTarget(OpcodeID opcodeID, Vector<unsigned, 32>& jumpTargets, unsigned bytecodeOffset)

95 {

96 if (opcodeID == op_catch)

97 return true;

     for (unsigned i = 0; i < jumpTargets.size(); i++) {

         if (bytecodeOffset == jumpTargets[i])

101 return true;

102 }

103 return false;

104 }

105

 static void linkBlocks(BytecodeBasicBlock* predecessor, BytecodeBasicBlock* successor)

107 {

108 predecessor->addSuccessor(successor);

109 successor->addPredecessor(predecessor);

110 }

111

 void computeBytecodeBasicBlocks(CodeBlock* codeBlock, Vector<RefPtr<BytecodeBasicBlock> >& basicBlocks)

113 {

     Vector<unsigned, 32> jumpTargets;

115 computePreciseJumpTargets(codeBlock, jumpTargets);

116

117 // Create the entry and exit basic blocks.

     BytecodeBasicBlock* entry = new BytecodeBasicBlock(BytecodeBasicBlock::EntryBlock);

     basicBlocks.append(adoptRef(entry));

     BytecodeBasicBlock* exit = new BytecodeBasicBlock(BytecodeBasicBlock::ExitBlock);

121

122 // Find basic block boundaries.

     BytecodeBasicBlock* current = new BytecodeBasicBlock(0, 0);

124 linkBlocks(entry, current);

     basicBlocks.append(adoptRef(current));

126

127 bool nextInstructionIsLeader = false;

128

     Interpreter* interpreter = codeBlock->vm()->interpreter;

     Instruction* instructionsBegin = codeBlock->instructions().begin();

     unsigned instructionCount = codeBlock->instructions().size();

     for (unsigned bytecodeOffset = 0; bytecodeOffset < instructionCount;) {

         OpcodeID opcodeID = interpreter->getOpcodeID(instructionsBegin[bytecodeOffset].u.opcode);

134 unsigned opcodeLength = opcodeLengths[opcodeID];

135

136 bool createdBlock = false;

137 // If the current bytecode is a jump target, then it's the leader of its own basic block.

         if (isJumpTarget(opcodeID, jumpTargets, bytecodeOffset) || nextInstructionIsLeader) {

             BytecodeBasicBlock* block = new BytecodeBasicBlock(bytecodeOffset, opcodeLength);

             basicBlocks.append(adoptRef(block));

141 current = block;

142 createdBlock = true;

143 nextInstructionIsLeader = false;

144 bytecodeOffset += opcodeLength;

145 }

146

147 // If the current bytecode is a branch or a return, then the next instruction is the leader of its own basic block.

         if (isBranch(opcodeID) || isTerminal(opcodeID) || isThrow(opcodeID))

149 nextInstructionIsLeader = true;

150

151 if (createdBlock)

152 continue;

153

154 // Otherwise, just add to the length of the current block.

155 current->addBytecodeLength(opcodeLength);

156 bytecodeOffset += opcodeLength;

157 }

158

159 // Link basic blocks together.

     for (unsigned i = 0; i < basicBlocks.size(); i++) {

         BytecodeBasicBlock* block = basicBlocks[i].get();

162

         if (block->isEntryBlock() || block->isExitBlock())

164 continue;

165

166 bool fallsThrough = true;

         for (unsigned bytecodeOffset = block->leaderBytecodeOffset(); bytecodeOffset < block->leaderBytecodeOffset() + block->totalBytecodeLength();) {

             const Instruction& currentInstruction = instructionsBegin[bytecodeOffset];

             OpcodeID opcodeID = interpreter->getOpcodeID(currentInstruction.u.opcode);

170 unsigned opcodeLength = opcodeLengths[opcodeID];

171 // If we found a terminal bytecode, link to the exit block.

             if (isTerminal(opcodeID)) {

                 ASSERT(bytecodeOffset + opcodeLength == block->leaderBytecodeOffset() + block->totalBytecodeLength());

174 linkBlocks(block, exit);

175 fallsThrough = false;

176 break;

177 }

178

179 // If we found a throw, get the HandlerInfo for this instruction to see where we will jump.

180 // If there isn't one, treat this throw as a terminal. This is true even if we have a finally

181 // block because the finally block will create its own catch, which will generate a HandlerInfo.

             if (isThrow(opcodeID)) {

                 ASSERT(bytecodeOffset + opcodeLength == block->leaderBytecodeOffset() + block->totalBytecodeLength());

                 HandlerInfo* handler = codeBlock->handlerForBytecodeOffset(bytecodeOffset);

185 fallsThrough = false;

186 if (!handler) {

187 linkBlocks(block, exit);

188 break;

189 }

                 for (unsigned i = 0; i < basicBlocks.size(); i++) {

                     BytecodeBasicBlock* otherBlock = basicBlocks[i].get();

                     if (handler->target == otherBlock->leaderBytecodeOffset()) {

193 linkBlocks(block, otherBlock);

194 break;

195 }

196 }

197 break;

198 }

199

200 // If we found a branch, link to the block(s) that we jump to.

             if (isBranch(opcodeID)) {

                 ASSERT(bytecodeOffset + opcodeLength == block->leaderBytecodeOffset() + block->totalBytecodeLength());

                 Vector<unsigned, 1> bytecodeOffsetsJumpedTo;

                 findJumpTargetsForBytecodeOffset(codeBlock, bytecodeOffset, bytecodeOffsetsJumpedTo);

205

                 for (unsigned i = 0; i < basicBlocks.size(); i++) {

                     BytecodeBasicBlock* otherBlock = basicBlocks[i].get();

                     if (bytecodeOffsetsJumpedTo.contains(otherBlock->leaderBytecodeOffset()))

209 linkBlocks(block, otherBlock);

210 }

211

                 if (isUnconditionalBranch(opcodeID))

213 fallsThrough = false;

214

215 break;

216 }

217 bytecodeOffset += opcodeLength;

218 }

219

220 // If we fall through then link to the next block in program order.

221 if (fallsThrough) {

             ASSERT(i + 1 < basicBlocks.size());

             BytecodeBasicBlock* nextBlock = basicBlocks[i + 1].get();

224 linkBlocks(block, nextBlock);

225 }

226 }

227

     basicBlocks.append(adoptRef(exit));

229 }

230

231 } // namespace JSC