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#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 "HeapInlines.h"
35#include "InterpreterInlines.h"
36#include "PreciseJumpTargets.h"
37
38namespace JSC {
39
40BytecodeLivenessAnalysis::BytecodeLivenessAnalysis(CodeBlock* codeBlock)
41 : m_graph(codeBlock, codeBlock->instructions())
42{
43 runLivenessFixpoint(codeBlock, codeBlock->instructions(), m_graph);
44
45 if (Options::dumpBytecodeLivenessResults())
46 dumpResults(codeBlock);
47}
48
49void BytecodeLivenessAnalysis::getLivenessInfoAtBytecodeOffset(CodeBlock* codeBlock, unsigned bytecodeOffset, FastBitVector& result)
50{
51 BytecodeBasicBlock* block = m_graph.findBasicBlockForBytecodeOffset(bytecodeOffset);
52 ASSERT(block);
53 ASSERT(!block->isEntryBlock());
54 ASSERT(!block->isExitBlock());
55 result.resize(block->out().numBits());
56 computeLocalLivenessForBytecodeOffset(codeBlock, codeBlock->instructions(), m_graph, block, bytecodeOffset, result);
57}
58
59FastBitVector BytecodeLivenessAnalysis::getLivenessInfoAtBytecodeOffset(CodeBlock* codeBlock, unsigned bytecodeOffset)
60{
61 FastBitVector out;
62 getLivenessInfoAtBytecodeOffset(codeBlock, bytecodeOffset, out);
63 return out;
64}
65
66void BytecodeLivenessAnalysis::computeFullLiveness(CodeBlock* codeBlock, FullBytecodeLiveness& result)
67{
68 FastBitVector out;
69
70 result.m_map.resize(codeBlock->instructions().size());
71
72 for (std::unique_ptr<BytecodeBasicBlock>& block : m_graph.basicBlocksInReverseOrder()) {
73 if (block->isEntryBlock() || block->isExitBlock())
74 continue;
75
76 out = block->out();
77
78 for (unsigned i = block->offsets().size(); i--;) {
79 unsigned bytecodeOffset = block->offsets()[i];
80 stepOverInstruction(codeBlock, codeBlock->instructions(), m_graph, bytecodeOffset, out);
81 result.m_map[bytecodeOffset] = out;
82 }
83 }
84}
85
86void BytecodeLivenessAnalysis::computeKills(CodeBlock* codeBlock, BytecodeKills& result)
87{
88 UNUSED_PARAM(result);
89 FastBitVector out;
90
91 result.m_codeBlock = codeBlock;
92 result.m_killSets = makeUniqueArray<BytecodeKills::KillSet>(codeBlock->instructions().size());
93
94 for (std::unique_ptr<BytecodeBasicBlock>& block : m_graph.basicBlocksInReverseOrder()) {
95 if (block->isEntryBlock() || block->isExitBlock())
96 continue;
97
98 out = block->out();
99
100 for (unsigned i = block->offsets().size(); i--;) {
101 unsigned bytecodeOffset = block->offsets()[i];
102 stepOverInstruction(
103 codeBlock, codeBlock->instructions(), m_graph, bytecodeOffset,
104 [&] (unsigned index) {
105 // This is for uses.
106 if (out[index])
107 return;
108 result.m_killSets[bytecodeOffset].add(index);
109 out[index] = true;
110 },
111 [&] (unsigned index) {
112 // This is for defs.
113 out[index] = false;
114 });
115 }
116 }
117}
118
119void BytecodeLivenessAnalysis::dumpResults(CodeBlock* codeBlock)
120{
121 dataLog("\nDumping bytecode liveness for ", *codeBlock, ":\n");
122 const auto& instructions = codeBlock->instructions();
123 unsigned i = 0;
124
125 unsigned numberOfBlocks = m_graph.size();
126 Vector<FastBitVector> predecessors(numberOfBlocks);
127 for (BytecodeBasicBlock* block : m_graph)
128 predecessors[block->index()].resize(numberOfBlocks);
129 for (BytecodeBasicBlock* block : m_graph) {
130 for (unsigned j = 0; j < block->successors().size(); j++) {
131 unsigned blockIndex = block->index();
132 unsigned successorIndex = block->successors()[j]->index();
133 predecessors[successorIndex][blockIndex] = true;
134 }
135 }
136
137 auto dumpBitVector = [] (FastBitVector& bits) {
138 for (unsigned j = 0; j < bits.numBits(); j++) {
139 if (bits[j])
140 dataLogF(" %u", j);
141 }
142 };
143
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
147 dataLogF("Predecessors:");
148 dumpBitVector(predecessors[block->index()]);
149 dataLogF("\n");
150
151 dataLogF("Successors:");
152 FastBitVector successors;
153 successors.resize(numberOfBlocks);
154 for (unsigned j = 0; j < block->successors().size(); j++) {
155 BytecodeBasicBlock* successor = block->successors()[j];
156 successors[successor->index()] = true;
157 }
158 dumpBitVector(successors); // Dump in sorted order.
159 dataLogF("\n");
160
161 if (block->isEntryBlock()) {
162 dataLogF("Entry block %p\n", block);
163 continue;
164 }
165 if (block->isExitBlock()) {
166 dataLogF("Exit block: %p\n", block);
167 continue;
168 }
169 for (unsigned bytecodeOffset = block->leaderOffset(); bytecodeOffset < block->leaderOffset() + block->totalLength();) {
170 const auto currentInstruction = instructions.at(bytecodeOffset);
171
172 dataLogF("Live variables:");
173 FastBitVector liveBefore = getLivenessInfoAtBytecodeOffset(codeBlock, bytecodeOffset);
174 dumpBitVector(liveBefore);
175 dataLogF("\n");
176 codeBlock->dumpBytecode(WTF::dataFile(), currentInstruction);
177
178 bytecodeOffset += currentInstruction->size();
179 }
180
181 dataLogF("Live variables:");
182 FastBitVector liveAfter = block->out();
183 dumpBitVector(liveAfter);
184 dataLogF("\n");
185 }
186}
187
188} // namespace JSC
189