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