FastBitVector should have efficient and easy-to-use vector-vector operations
[WebKit-https.git] / Source / JavaScriptCore / bytecode / BytecodeLivenessAnalysisInlines.h
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 #pragma once
27
28 #include "BytecodeGraph.h"
29 #include "BytecodeLivenessAnalysis.h"
30 #include "CodeBlock.h"
31 #include "Interpreter.h"
32 #include "Operations.h"
33
34 namespace JSC {
35
36 inline bool operandIsAlwaysLive(int operand)
37 {
38     return !VirtualRegister(operand).isLocal();
39 }
40
41 inline bool operandThatIsNotAlwaysLiveIsLive(const FastBitVector& out, int operand)
42 {
43     unsigned local = VirtualRegister(operand).toLocal();
44     if (local >= out.numBits())
45         return false;
46     return out[local];
47 }
48
49 inline bool operandIsLive(const FastBitVector& out, int operand)
50 {
51     return operandIsAlwaysLive(operand) || operandThatIsNotAlwaysLiveIsLive(out, operand);
52 }
53
54 inline bool isValidRegisterForLiveness(int operand)
55 {
56     VirtualRegister virtualReg(operand);
57     if (virtualReg.isConstant())
58         return false;
59     return virtualReg.isLocal();
60 }
61
62 // Simplified interface to bytecode use/def, which determines defs first and then uses, and includes
63 // exception handlers in the uses.
64 template<typename DerivedAnalysis>
65 template<typename Graph, typename UseFunctor, typename DefFunctor>
66 inline void BytecodeLivenessPropagation<DerivedAnalysis>::stepOverInstruction(Graph& graph, unsigned bytecodeOffset, FastBitVector& out, const UseFunctor& use, const DefFunctor& def)
67 {
68     // This abstractly execute the instruction in reverse. Instructions logically first use operands and
69     // then define operands. This logical ordering is necessary for operations that use and def the same
70     // operand, like:
71     //
72     //     op_add loc1, loc1, loc2
73     //
74     // The use of loc1 happens before the def of loc1. That's a semantic requirement since the add
75     // operation cannot travel forward in time to read the value that it will produce after reading that
76     // value. Since we are executing in reverse, this means that we must do defs before uses (reverse of
77     // uses before defs).
78     //
79     // Since this is a liveness analysis, this ordering ends up being particularly important: if we did
80     // uses before defs, then the add operation above would appear to not have loc1 live, since we'd
81     // first add it to the out set (the use), and then we'd remove it (the def).
82
83     auto* codeBlock = graph.codeBlock();
84     Interpreter* interpreter = codeBlock->vm()->interpreter;
85     auto* instructionsBegin = graph.instructions().begin();
86     auto* instruction = &instructionsBegin[bytecodeOffset];
87     OpcodeID opcodeID = interpreter->getOpcodeID(*instruction);
88
89     static_cast<DerivedAnalysis*>(this)->computeDefsForBytecodeOffset(
90         codeBlock, opcodeID, instruction, out,
91         [&] (typename Graph::CodeBlock*, typename Graph::Instruction*, OpcodeID, int operand) {
92             if (isValidRegisterForLiveness(operand))
93                 def(VirtualRegister(operand).toLocal());
94         });
95
96     static_cast<DerivedAnalysis*>(this)->computeUsesForBytecodeOffset(
97         codeBlock, opcodeID, instruction, out,
98         [&] (typename Graph::CodeBlock*, typename Graph::Instruction*, OpcodeID, int operand) {
99             if (isValidRegisterForLiveness(operand))
100                 use(VirtualRegister(operand).toLocal());
101         });
102
103     // If we have an exception handler, we want the live-in variables of the 
104     // exception handler block to be included in the live-in of this particular bytecode.
105     if (auto* handler = codeBlock->handlerForBytecodeOffset(bytecodeOffset)) {
106         BytecodeBasicBlock* handlerBlock = graph.findBasicBlockWithLeaderOffset(handler->target);
107         ASSERT(handlerBlock);
108         handlerBlock->in().forEachSetBit(use);
109     }
110 }
111
112 template<typename DerivedAnalysis>
113 template<typename Graph>
114 inline void BytecodeLivenessPropagation<DerivedAnalysis>::stepOverInstruction(Graph& graph, unsigned bytecodeOffset, FastBitVector& out)
115 {
116     stepOverInstruction(
117         graph, bytecodeOffset, out,
118         [&] (unsigned bitIndex) {
119             // This is the use functor, so we set the bit.
120             out[bitIndex] = true;
121         },
122         [&] (unsigned bitIndex) {
123             // This is the def functor, so we clear the bit.
124             out[bitIndex] = false;
125         });
126 }
127
128 template<typename DerivedAnalysis>
129 template<typename Graph>
130 inline bool BytecodeLivenessPropagation<DerivedAnalysis>::computeLocalLivenessForBytecodeOffset(Graph& graph, BytecodeBasicBlock* block, unsigned targetOffset, FastBitVector& result)
131 {
132     ASSERT(!block->isExitBlock());
133     ASSERT(!block->isEntryBlock());
134
135     FastBitVector out = block->out();
136
137     for (int i = block->offsets().size() - 1; i >= 0; i--) {
138         unsigned bytecodeOffset = block->offsets()[i];
139         if (targetOffset > bytecodeOffset)
140             break;
141         stepOverInstruction(graph, bytecodeOffset, out);
142     }
143
144     return result.setAndCheck(out);
145 }
146
147 template<typename DerivedAnalysis>
148 template<typename Graph>
149 inline bool BytecodeLivenessPropagation<DerivedAnalysis>::computeLocalLivenessForBlock(Graph& graph, BytecodeBasicBlock* block)
150 {
151     if (block->isExitBlock() || block->isEntryBlock())
152         return false;
153     return computeLocalLivenessForBytecodeOffset(graph, block, block->leaderOffset(), block->in());
154 }
155
156 template<typename DerivedAnalysis>
157 template<typename Graph>
158 inline FastBitVector BytecodeLivenessPropagation<DerivedAnalysis>::getLivenessInfoAtBytecodeOffset(Graph& graph, unsigned bytecodeOffset)
159 {
160     BytecodeBasicBlock* block = graph.findBasicBlockForBytecodeOffset(bytecodeOffset);
161     ASSERT(block);
162     ASSERT(!block->isEntryBlock());
163     ASSERT(!block->isExitBlock());
164     FastBitVector out;
165     out.resize(block->out().numBits());
166     computeLocalLivenessForBytecodeOffset(graph, block, bytecodeOffset, out);
167     return out;
168 }
169
170 template<typename DerivedAnalysis>
171 template<typename Graph>
172 inline void BytecodeLivenessPropagation<DerivedAnalysis>::runLivenessFixpoint(Graph& graph)
173 {
174     auto* codeBlock = graph.codeBlock();
175     unsigned numberOfVariables = codeBlock->numCalleeLocals();
176     for (BytecodeBasicBlock* block : graph) {
177         block->in().resize(numberOfVariables);
178         block->out().resize(numberOfVariables);
179         block->in().clearAll();
180         block->out().clearAll();
181     }
182
183     bool changed;
184     BytecodeBasicBlock* lastBlock = graph.last();
185     lastBlock->in().clearAll();
186     lastBlock->out().clearAll();
187     FastBitVector newOut;
188     newOut.resize(lastBlock->out().numBits());
189     do {
190         changed = false;
191         for (std::unique_ptr<BytecodeBasicBlock>& block : graph.basicBlocksInReverseOrder()) {
192             newOut.clearAll();
193             for (BytecodeBasicBlock* successor : block->successors())
194                 newOut |= successor->in();
195             block->out() = newOut;
196             changed |= computeLocalLivenessForBlock(graph, block.get());
197         }
198     } while (changed);
199 }
200
201 } // namespace JSC