1/*
2 * Copyright (C) 2015-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. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "B3Procedure.h"
28
29#if ENABLE(B3_JIT)
30
31#include "AirCode.h"
32#include "B3BackwardsCFG.h"
33#include "B3BackwardsDominators.h"
34#include "B3BasicBlockInlines.h"
35#include "B3BasicBlockUtils.h"
36#include "B3BlockWorklist.h"
37#include "B3CFG.h"
38#include "B3DataSection.h"
39#include "B3Dominators.h"
40#include "B3NaturalLoops.h"
41#include "B3OpaqueByproducts.h"
42#include "B3PhiChildren.h"
43#include "B3StackSlot.h"
44#include "B3ValueInlines.h"
45#include "B3Variable.h"
46
47namespace JSC { namespace B3 {
48
49Procedure::Procedure()
50 : m_cfg(new CFG(*this))
51 , m_lastPhaseName("initial")
52 , m_byproducts(std::make_unique<OpaqueByproducts>())
53 , m_code(new Air::Code(*this))
54{
55 m_code->setNumEntrypoints(m_numEntrypoints);
56}
57
58Procedure::~Procedure()
59{
60}
61
62void Procedure::printOrigin(PrintStream& out, Origin origin) const
63{
64 if (m_originPrinter)
65 m_originPrinter->run(out, origin);
66 else
67 out.print(origin);
68}
69
70BasicBlock* Procedure::addBlock(double frequency)
71{
72 std::unique_ptr<BasicBlock> block(new BasicBlock(m_blocks.size(), frequency));
73 BasicBlock* result = block.get();
74 m_blocks.append(WTFMove(block));
75 return result;
76}
77
78StackSlot* Procedure::addStackSlot(unsigned byteSize)
79{
80 return m_stackSlots.addNew(byteSize);
81}
82
83Variable* Procedure::addVariable(Type type)
84{
85 return m_variables.addNew(type);
86}
87
88Value* Procedure::clone(Value* value)
89{
90 std::unique_ptr<Value> clone(value->cloneImpl());
91 clone->m_index = UINT_MAX;
92 clone->owner = nullptr;
93 return m_values.add(WTFMove(clone));
94}
95
96Value* Procedure::addIntConstant(Origin origin, Type type, int64_t value)
97{
98 switch (type) {
99 case Int32:
100 return add<Const32Value>(origin, static_cast<int32_t>(value));
101 case Int64:
102 return add<Const64Value>(origin, value);
103 case Double:
104 return add<ConstDoubleValue>(origin, static_cast<double>(value));
105 case Float:
106 return add<ConstFloatValue>(origin, static_cast<float>(value));
107 default:
108 RELEASE_ASSERT_NOT_REACHED();
109 return nullptr;
110 }
111}
112
113Value* Procedure::addIntConstant(Value* likeValue, int64_t value)
114{
115 return addIntConstant(likeValue->origin(), likeValue->type(), value);
116}
117
118Value* Procedure::addConstant(Origin origin, Type type, uint64_t bits)
119{
120 switch (type) {
121 case Int32:
122 return add<Const32Value>(origin, static_cast<int32_t>(bits));
123 case Int64:
124 return add<Const64Value>(origin, bits);
125 case Float:
126 return add<ConstFloatValue>(origin, bitwise_cast<float>(static_cast<int32_t>(bits)));
127 case Double:
128 return add<ConstDoubleValue>(origin, bitwise_cast<double>(bits));
129 default:
130 RELEASE_ASSERT_NOT_REACHED();
131 return nullptr;
132 }
133}
134
135Value* Procedure::addBottom(Origin origin, Type type)
136{
137 return addIntConstant(origin, type, 0);
138}
139
140Value* Procedure::addBottom(Value* value)
141{
142 return addBottom(value->origin(), value->type());
143}
144
145Value* Procedure::addBoolConstant(Origin origin, TriState triState)
146{
147 int32_t value = 0;
148 switch (triState) {
149 case FalseTriState:
150 value = 0;
151 break;
152 case TrueTriState:
153 value = 1;
154 break;
155 case MixedTriState:
156 return nullptr;
157 }
158
159 return addIntConstant(origin, Int32, value);
160}
161
162void Procedure::resetValueOwners()
163{
164 for (BasicBlock* block : *this) {
165 for (Value* value : *block)
166 value->owner = block;
167 }
168}
169
170void Procedure::resetReachability()
171{
172 recomputePredecessors(m_blocks);
173
174 // The common case is that this does not find any dead blocks.
175 bool foundDead = false;
176 for (auto& block : m_blocks) {
177 if (isBlockDead(block.get())) {
178 foundDead = true;
179 break;
180 }
181 }
182 if (!foundDead)
183 return;
184
185 resetValueOwners();
186
187 for (Value* value : values()) {
188 if (UpsilonValue* upsilon = value->as<UpsilonValue>()) {
189 if (isBlockDead(upsilon->phi()->owner))
190 upsilon->replaceWithNop();
191 }
192 }
193
194 for (auto& block : m_blocks) {
195 if (isBlockDead(block.get())) {
196 for (Value* value : *block)
197 deleteValue(value);
198 block = nullptr;
199 }
200 }
201}
202
203void Procedure::invalidateCFG()
204{
205 m_dominators = nullptr;
206 m_naturalLoops = nullptr;
207 m_backwardsCFG = nullptr;
208 m_backwardsDominators = nullptr;
209}
210
211void Procedure::dump(PrintStream& out) const
212{
213 IndexSet<Value*> valuesInBlocks;
214 for (BasicBlock* block : *this) {
215 out.print(deepDump(*this, block));
216 valuesInBlocks.addAll(*block);
217 }
218 bool didPrint = false;
219 for (Value* value : values()) {
220 if (valuesInBlocks.contains(value))
221 continue;
222
223 if (!didPrint) {
224 dataLog("Orphaned values:\n");
225 didPrint = true;
226 }
227 dataLog(" ", deepDump(*this, value), "\n");
228 }
229 if (hasQuirks())
230 out.print("Has Quirks: True\n");
231 if (variables().size()) {
232 out.print("Variables:\n");
233 for (Variable* variable : variables())
234 out.print(" ", deepDump(variable), "\n");
235 }
236 if (stackSlots().size()) {
237 out.print("Stack slots:\n");
238 for (StackSlot* slot : stackSlots())
239 out.print(" ", pointerDump(slot), ": ", deepDump(slot), "\n");
240 }
241 if (m_byproducts->count())
242 out.print(*m_byproducts);
243}
244
245Vector<BasicBlock*> Procedure::blocksInPreOrder()
246{
247 return B3::blocksInPreOrder(at(0));
248}
249
250Vector<BasicBlock*> Procedure::blocksInPostOrder()
251{
252 return B3::blocksInPostOrder(at(0));
253}
254
255void Procedure::deleteStackSlot(StackSlot* stackSlot)
256{
257 m_stackSlots.remove(stackSlot);
258}
259
260void Procedure::deleteVariable(Variable* variable)
261{
262 m_variables.remove(variable);
263}
264
265void Procedure::deleteValue(Value* value)
266{
267 m_values.remove(value);
268}
269
270void Procedure::deleteOrphans()
271{
272 IndexSet<Value*> valuesInBlocks;
273 for (BasicBlock* block : *this)
274 valuesInBlocks.addAll(*block);
275
276 // Since this method is not on any hot path, we do it conservatively: first a pass to
277 // identify the values to be removed, and then a second pass to remove them. This avoids any
278 // risk of the value iteration being broken by removals.
279 Vector<Value*, 16> toRemove;
280 for (Value* value : values()) {
281 if (!valuesInBlocks.contains(value))
282 toRemove.append(value);
283 else if (UpsilonValue* upsilon = value->as<UpsilonValue>()) {
284 if (!valuesInBlocks.contains(upsilon->phi()))
285 upsilon->replaceWithNop();
286 }
287 }
288
289 for (Value* value : toRemove)
290 deleteValue(value);
291}
292
293Dominators& Procedure::dominators()
294{
295 if (!m_dominators)
296 m_dominators = std::make_unique<Dominators>(*this);
297 return *m_dominators;
298}
299
300NaturalLoops& Procedure::naturalLoops()
301{
302 if (!m_naturalLoops)
303 m_naturalLoops = std::make_unique<NaturalLoops>(*this);
304 return *m_naturalLoops;
305}
306
307BackwardsCFG& Procedure::backwardsCFG()
308{
309 if (!m_backwardsCFG)
310 m_backwardsCFG = std::make_unique<BackwardsCFG>(*this);
311 return *m_backwardsCFG;
312}
313
314BackwardsDominators& Procedure::backwardsDominators()
315{
316 if (!m_backwardsDominators)
317 m_backwardsDominators = std::make_unique<BackwardsDominators>(*this);
318 return *m_backwardsDominators;
319}
320
321void Procedure::addFastConstant(const ValueKey& constant)
322{
323 RELEASE_ASSERT(constant.isConstant());
324 m_fastConstants.add(constant);
325}
326
327bool Procedure::isFastConstant(const ValueKey& constant)
328{
329 if (!constant)
330 return false;
331 return m_fastConstants.contains(constant);
332}
333
334CCallHelpers::Label Procedure::entrypointLabel(unsigned index) const
335{
336 return m_code->entrypointLabel(index);
337}
338
339void* Procedure::addDataSection(size_t size)
340{
341 if (!size)
342 return nullptr;
343 std::unique_ptr<DataSection> dataSection = std::make_unique<DataSection>(size);
344 void* result = dataSection->data();
345 m_byproducts->add(WTFMove(dataSection));
346 return result;
347}
348
349unsigned Procedure::callArgAreaSizeInBytes() const
350{
351 return code().callArgAreaSizeInBytes();
352}
353
354void Procedure::requestCallArgAreaSizeInBytes(unsigned size)
355{
356 code().requestCallArgAreaSizeInBytes(size);
357}
358
359void Procedure::pinRegister(Reg reg)
360{
361 code().pinRegister(reg);
362}
363
364void Procedure::setOptLevel(unsigned optLevel)
365{
366 m_optLevel = optLevel;
367 code().setOptLevel(optLevel);
368}
369
370unsigned Procedure::frameSize() const
371{
372 return code().frameSize();
373}
374
375RegisterAtOffsetList Procedure::calleeSaveRegisterAtOffsetList() const
376{
377 return code().calleeSaveRegisterAtOffsetList();
378}
379
380Value* Procedure::addValueImpl(Value* value)
381{
382 return m_values.add(std::unique_ptr<Value>(value));
383}
384
385void Procedure::setBlockOrderImpl(Vector<BasicBlock*>& blocks)
386{
387 IndexSet<BasicBlock*> blocksSet;
388 blocksSet.addAll(blocks);
389
390 for (BasicBlock* block : *this) {
391 if (!blocksSet.contains(block))
392 blocks.append(block);
393 }
394
395 // Place blocks into this's block list by first leaking all of the blocks and then readopting
396 // them.
397 for (auto& entry : m_blocks)
398 entry.release();
399
400 m_blocks.resize(blocks.size());
401 for (unsigned i = 0; i < blocks.size(); ++i) {
402 BasicBlock* block = blocks[i];
403 block->m_index = i;
404 m_blocks[i] = std::unique_ptr<BasicBlock>(block);
405 }
406}
407
408void Procedure::setWasmBoundsCheckGenerator(RefPtr<WasmBoundsCheckGenerator> generator)
409{
410 code().setWasmBoundsCheckGenerator(generator);
411}
412
413RegisterSet Procedure::mutableGPRs()
414{
415 return code().mutableGPRs();
416}
417
418RegisterSet Procedure::mutableFPRs()
419{
420 return code().mutableFPRs();
421}
422
423void Procedure::setNumEntrypoints(unsigned numEntrypoints)
424{
425 m_numEntrypoints = numEntrypoints;
426 m_code->setNumEntrypoints(numEntrypoints);
427}
428
429} } // namespace JSC::B3
430
431#endif // ENABLE(B3_JIT)
432