Replace WTF::move with WTFMove
[WebKit-https.git] / Source / JavaScriptCore / bytecode / BytecodeBasicBlock.cpp
1 /*
2  * Copyright (C) 2013, 2015 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 void BytecodeBasicBlock::shrinkToFit()
36 {
37     m_bytecodeOffsets.shrinkToFit();
38     m_successors.shrinkToFit();
39 }
40
41 static bool isBranch(OpcodeID opcodeID)
42 {
43     switch (opcodeID) {
44     case op_jmp:
45     case op_jtrue:
46     case op_jfalse:
47     case op_jeq_null:
48     case op_jneq_null:
49     case op_jneq_ptr:
50     case op_jless:
51     case op_jlesseq:
52     case op_jgreater:
53     case op_jgreatereq:
54     case op_jnless:
55     case op_jnlesseq:
56     case op_jngreater:
57     case op_jngreatereq:
58     case op_switch_imm:
59     case op_switch_char:
60     case op_switch_string:
61     case op_save:
62         return true;
63     default:
64         return false;
65     }
66 }
67
68 static bool isUnconditionalBranch(OpcodeID opcodeID)
69 {
70     switch (opcodeID) {
71     case op_jmp:
72         return true;
73     default:
74         return false;
75     }
76 }
77
78 static bool isTerminal(OpcodeID opcodeID)
79 {
80     switch (opcodeID) {
81     case op_ret:
82     case op_end:
83         return true;
84     default:
85         return false;
86     }
87 }
88
89 static bool isThrow(OpcodeID opcodeID)
90 {
91     switch (opcodeID) {
92     case op_throw:
93     case op_throw_static_error:
94         return true;
95     default:
96         return false;
97     }
98 }
99
100 static bool isJumpTarget(OpcodeID opcodeID, const Vector<unsigned, 32>& jumpTargets, unsigned bytecodeOffset)
101 {
102     if (opcodeID == op_catch)
103         return true;
104
105     return std::binary_search(jumpTargets.begin(), jumpTargets.end(), bytecodeOffset);
106 }
107
108 static void linkBlocks(BytecodeBasicBlock* predecessor, BytecodeBasicBlock* successor)
109 {
110     predecessor->addSuccessor(successor);
111 }
112
113 void computeBytecodeBasicBlocks(CodeBlock* codeBlock, Vector<std::unique_ptr<BytecodeBasicBlock>>& basicBlocks)
114 {
115     Vector<unsigned, 32> jumpTargets;
116     computePreciseJumpTargets(codeBlock, jumpTargets);
117
118     // Create the entry and exit basic blocks.
119     basicBlocks.reserveCapacity(jumpTargets.size() + 2);
120
121     auto entry = std::make_unique<BytecodeBasicBlock>(BytecodeBasicBlock::EntryBlock);
122     auto firstBlock = std::make_unique<BytecodeBasicBlock>(0, 0);
123     linkBlocks(entry.get(), firstBlock.get());
124
125     basicBlocks.append(WTFMove(entry));
126     BytecodeBasicBlock* current = firstBlock.get();
127     basicBlocks.append(WTFMove(firstBlock));
128
129     auto exit = std::make_unique<BytecodeBasicBlock>(BytecodeBasicBlock::ExitBlock);
130
131     bool nextInstructionIsLeader = false;
132
133     Interpreter* interpreter = codeBlock->vm()->interpreter;
134     Instruction* instructionsBegin = codeBlock->instructions().begin();
135     unsigned instructionCount = codeBlock->instructions().size();
136     for (unsigned bytecodeOffset = 0; bytecodeOffset < instructionCount;) {
137         OpcodeID opcodeID = interpreter->getOpcodeID(instructionsBegin[bytecodeOffset].u.opcode);
138         unsigned opcodeLength = opcodeLengths[opcodeID];
139
140         bool createdBlock = false;
141         // If the current bytecode is a jump target, then it's the leader of its own basic block.
142         if (isJumpTarget(opcodeID, jumpTargets, bytecodeOffset) || nextInstructionIsLeader) {
143             auto newBlock = std::make_unique<BytecodeBasicBlock>(bytecodeOffset, opcodeLength);
144             current = newBlock.get();
145             basicBlocks.append(WTFMove(newBlock));
146             createdBlock = true;
147             nextInstructionIsLeader = false;
148             bytecodeOffset += opcodeLength;
149         }
150
151         // If the current bytecode is a branch or a return, then the next instruction is the leader of its own basic block.
152         if (isBranch(opcodeID) || isTerminal(opcodeID) || isThrow(opcodeID))
153             nextInstructionIsLeader = true;
154
155         if (createdBlock)
156             continue;
157
158         // Otherwise, just add to the length of the current block.
159         current->addBytecodeLength(opcodeLength);
160         bytecodeOffset += opcodeLength;
161     }
162
163     // Link basic blocks together.
164     for (unsigned i = 0; i < basicBlocks.size(); i++) {
165         BytecodeBasicBlock* block = basicBlocks[i].get();
166
167         if (block->isEntryBlock() || block->isExitBlock())
168             continue;
169
170         bool fallsThrough = true; 
171         for (unsigned bytecodeOffset = block->leaderBytecodeOffset(); bytecodeOffset < block->leaderBytecodeOffset() + block->totalBytecodeLength();) {
172             const Instruction& currentInstruction = instructionsBegin[bytecodeOffset];
173             OpcodeID opcodeID = interpreter->getOpcodeID(currentInstruction.u.opcode);
174             unsigned opcodeLength = opcodeLengths[opcodeID];
175             // If we found a terminal bytecode, link to the exit block.
176             if (isTerminal(opcodeID)) {
177                 ASSERT(bytecodeOffset + opcodeLength == block->leaderBytecodeOffset() + block->totalBytecodeLength());
178                 linkBlocks(block, exit.get());
179                 fallsThrough = false;
180                 break;
181             }
182
183             // If we found a throw, get the HandlerInfo for this instruction to see where we will jump. 
184             // If there isn't one, treat this throw as a terminal. This is true even if we have a finally
185             // block because the finally block will create its own catch, which will generate a HandlerInfo.
186             if (isThrow(opcodeID)) {
187                 ASSERT(bytecodeOffset + opcodeLength == block->leaderBytecodeOffset() + block->totalBytecodeLength());
188                 HandlerInfo* handler = codeBlock->handlerForBytecodeOffset(bytecodeOffset);
189                 fallsThrough = false;
190                 if (!handler) {
191                     linkBlocks(block, exit.get());
192                     break;
193                 }
194                 for (unsigned i = 0; i < basicBlocks.size(); i++) {
195                     BytecodeBasicBlock* otherBlock = basicBlocks[i].get();
196                     if (handler->target == otherBlock->leaderBytecodeOffset()) {
197                         linkBlocks(block, otherBlock);
198                         break;
199                     }
200                 }
201                 break;
202             }
203
204             // If we found a branch, link to the block(s) that we jump to.
205             if (isBranch(opcodeID)) {
206                 ASSERT(bytecodeOffset + opcodeLength == block->leaderBytecodeOffset() + block->totalBytecodeLength());
207                 Vector<unsigned, 1> bytecodeOffsetsJumpedTo;
208                 findJumpTargetsForBytecodeOffset(codeBlock, bytecodeOffset, bytecodeOffsetsJumpedTo);
209
210                 for (unsigned i = 0; i < basicBlocks.size(); i++) {
211                     BytecodeBasicBlock* otherBlock = basicBlocks[i].get();
212                     if (bytecodeOffsetsJumpedTo.contains(otherBlock->leaderBytecodeOffset()))
213                         linkBlocks(block, otherBlock);
214                 }
215
216                 if (isUnconditionalBranch(opcodeID))
217                     fallsThrough = false;
218
219                 break;
220             }
221             bytecodeOffset += opcodeLength;
222         }
223
224         // If we fall through then link to the next block in program order.
225         if (fallsThrough) {
226             ASSERT(i + 1 < basicBlocks.size());
227             BytecodeBasicBlock* nextBlock = basicBlocks[i + 1].get();
228             linkBlocks(block, nextBlock);
229         }
230     }
231
232     basicBlocks.append(WTFMove(exit));
233     
234     for (auto& basicBlock : basicBlocks)
235         basicBlock->shrinkToFit();
236 }
237
238 } // namespace JSC