d7868a88baeedc412c93fbf733ddbb3fda04c454
[WebKit-https.git] / Source / JavaScriptCore / bytecode / BytecodeLivenessAnalysis.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 "BytecodeLivenessAnalysis.h"
28
29 #include "BytecodeKills.h"
30 #include "BytecodeLivenessAnalysisInlines.h"
31 #include "BytecodeUseDef.h"
32 #include "CodeBlock.h"
33 #include "FullBytecodeLiveness.h"
34 #include "InterpreterInlines.h"
35 #include "PreciseJumpTargets.h"
36
37 namespace JSC {
38
39 BytecodeLivenessAnalysis::BytecodeLivenessAnalysis(CodeBlock* codeBlock)
40     : m_graph(codeBlock, codeBlock->instructions())
41 {
42     compute();
43 }
44
45 template<typename Functor>
46 void BytecodeLivenessAnalysis::computeDefsForBytecodeOffset(CodeBlock* codeBlock, OpcodeID opcodeID, Instruction* instruction, FastBitVector&, const Functor& functor)
47 {
48     JSC::computeDefsForBytecodeOffset(codeBlock, opcodeID, instruction, functor);
49 }
50
51 template<typename Functor>
52 void BytecodeLivenessAnalysis::computeUsesForBytecodeOffset(CodeBlock* codeBlock, OpcodeID opcodeID, Instruction* instruction, FastBitVector&, const Functor& functor)
53 {
54     JSC::computeUsesForBytecodeOffset(codeBlock, opcodeID, instruction, functor);
55 }
56
57 void BytecodeLivenessAnalysis::getLivenessInfoAtBytecodeOffset(unsigned bytecodeOffset, FastBitVector& result)
58 {
59     BytecodeBasicBlock* block = m_graph.findBasicBlockForBytecodeOffset(bytecodeOffset);
60     ASSERT(block);
61     ASSERT(!block->isEntryBlock());
62     ASSERT(!block->isExitBlock());
63     result.resize(block->out().numBits());
64     computeLocalLivenessForBytecodeOffset(m_graph, block, bytecodeOffset, result);
65 }
66
67 bool BytecodeLivenessAnalysis::operandIsLiveAtBytecodeOffset(int operand, unsigned bytecodeOffset)
68 {
69     if (operandIsAlwaysLive(operand))
70         return true;
71     FastBitVector result;
72     getLivenessInfoAtBytecodeOffset(bytecodeOffset, result);
73     return operandThatIsNotAlwaysLiveIsLive(result, operand);
74 }
75
76 FastBitVector BytecodeLivenessAnalysis::getLivenessInfoAtBytecodeOffset(unsigned bytecodeOffset)
77 {
78     FastBitVector out;
79     getLivenessInfoAtBytecodeOffset(bytecodeOffset, out);
80     return out;
81 }
82
83 void BytecodeLivenessAnalysis::computeFullLiveness(FullBytecodeLiveness& result)
84 {
85     FastBitVector out;
86     CodeBlock* codeBlock = m_graph.codeBlock();
87     
88     result.m_map.resize(codeBlock->instructions().size());
89     
90     for (std::unique_ptr<BytecodeBasicBlock>& block : m_graph.basicBlocksInReverseOrder()) {
91         if (block->isEntryBlock() || block->isExitBlock())
92             continue;
93         
94         out = block->out();
95         
96         for (unsigned i = block->offsets().size(); i--;) {
97             unsigned bytecodeOffset = block->offsets()[i];
98             stepOverInstruction(m_graph, bytecodeOffset, out);
99             result.m_map[bytecodeOffset] = out;
100         }
101     }
102 }
103
104 void BytecodeLivenessAnalysis::computeKills(BytecodeKills& result)
105 {
106     FastBitVector out;
107     
108     CodeBlock* codeBlock = m_graph.codeBlock();
109     result.m_codeBlock = codeBlock;
110     result.m_killSets = std::make_unique<BytecodeKills::KillSet[]>(codeBlock->instructions().size());
111     
112     for (std::unique_ptr<BytecodeBasicBlock>& block : m_graph.basicBlocksInReverseOrder()) {
113         if (block->isEntryBlock() || block->isExitBlock())
114             continue;
115         
116         out = block->out();
117         
118         for (unsigned i = block->offsets().size(); i--;) {
119             unsigned bytecodeOffset = block->offsets()[i];
120             stepOverInstruction(
121                 m_graph, bytecodeOffset, out,
122                 [&] (unsigned index) {
123                     // This is for uses.
124                     if (out.get(index))
125                         return;
126                     result.m_killSets[bytecodeOffset].add(index);
127                     out.set(index);
128                 },
129                 [&] (unsigned index) {
130                     // This is for defs.
131                     out.clear(index);
132                 });
133         }
134     }
135 }
136
137 void BytecodeLivenessAnalysis::dumpResults()
138 {
139     CodeBlock* codeBlock = m_graph.codeBlock();
140     dataLog("\nDumping bytecode liveness for ", *codeBlock, ":\n");
141     Interpreter* interpreter = codeBlock->vm()->interpreter;
142     Instruction* instructionsBegin = codeBlock->instructions().begin();
143     unsigned i = 0;
144     for (BytecodeBasicBlock* block : m_graph) {
145         dataLogF("\nBytecode basic block %u: %p (offset: %u, length: %u)\n", i++, block, block->leaderOffset(), block->totalLength());
146         dataLogF("Successors: ");
147         for (unsigned j = 0; j < block->successors().size(); j++) {
148             BytecodeBasicBlock* successor = block->successors()[j];
149             dataLogF("%p ", successor);
150         }
151         dataLogF("\n");
152         if (block->isEntryBlock()) {
153             dataLogF("Entry block %p\n", block);
154             continue;
155         }
156         if (block->isExitBlock()) {
157             dataLogF("Exit block: %p\n", block);
158             continue;
159         }
160         for (unsigned bytecodeOffset = block->leaderOffset(); bytecodeOffset < block->leaderOffset() + block->totalLength();) {
161             const Instruction* currentInstruction = &instructionsBegin[bytecodeOffset];
162
163             dataLogF("Live variables: ");
164             FastBitVector liveBefore = getLivenessInfoAtBytecodeOffset(bytecodeOffset);
165             for (unsigned j = 0; j < liveBefore.numBits(); j++) {
166                 if (liveBefore.get(j))
167                     dataLogF("%u ", j);
168             }
169             dataLogF("\n");
170             codeBlock->dumpBytecode(WTF::dataFile(), codeBlock->globalObject()->globalExec(), instructionsBegin, currentInstruction);
171
172             OpcodeID opcodeID = interpreter->getOpcodeID(instructionsBegin[bytecodeOffset].u.opcode);
173             unsigned opcodeLength = opcodeLengths[opcodeID];
174             bytecodeOffset += opcodeLength;
175         }
176
177         dataLogF("Live variables: ");
178         FastBitVector liveAfter = block->out();
179         for (unsigned j = 0; j < liveAfter.numBits(); j++) {
180             if (liveAfter.get(j))
181                 dataLogF("%u ", j);
182         }
183         dataLogF("\n");
184     }
185 }
186
187 void BytecodeLivenessAnalysis::compute()
188 {
189     runLivenessFixpoint(m_graph);
190
191     if (Options::dumpBytecodeLivenessResults())
192         dumpResults();
193 }
194
195 } // namespace JSC