1/*
2 * Copyright (C) 2015-2019 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(makeUnique<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
88Type Procedure::addTuple(Vector<Type>&& types)
89{
90 Type result = Type::tupleFromIndex(m_tuples.size());
91 m_tuples.append(WTFMove(types));
92 ASSERT(result.isTuple());
93 return result;
94}
95
96bool Procedure::isValidTuple(Type tuple) const
97{
98 return tuple.tupleIndex() < m_tuples.size();
99}
100
101const Vector<Type>& Procedure::tupleForType(Type tuple) const
102{
103 return m_tuples[tuple.tupleIndex()];
104}
105
106Value* Procedure::clone(Value* value)
107{
108 std::unique_ptr<Value> clone(value->cloneImpl());
109 clone->m_index = UINT_MAX;
110 clone->owner = nullptr;
111 return m_values.add(WTFMove(clone));
112}
113
114Value* Procedure::addIntConstant(Origin origin, Type type, int64_t value)
115{
116 switch (type.kind()) {
117 case Int32:
118 return add<Const32Value>(origin, static_cast<int32_t>(value));
119 case Int64:
120 return add<Const64Value>(origin, value);
121 case Double:
122 return add<ConstDoubleValue>(origin, static_cast<double>(value));
123 case Float:
124 return add<ConstFloatValue>(origin, static_cast<float>(value));
125 default:
126 RELEASE_ASSERT_NOT_REACHED();
127 return nullptr;
128 }
129}
130
131Value* Procedure::addIntConstant(Value* likeValue, int64_t value)
132{
133 return addIntConstant(likeValue->origin(), likeValue->type(), value);
134}
135
136Value* Procedure::addConstant(Origin origin, Type type, uint64_t bits)
137{
138 switch (type.kind()) {
139 case Int32:
140 return add<Const32Value>(origin, static_cast<int32_t>(bits));
141 case Int64:
142 return add<Const64Value>(origin, bits);
143 case Float:
144 return add<ConstFloatValue>(origin, bitwise_cast<float>(static_cast<int32_t>(bits)));
145 case Double:
146 return add<ConstDoubleValue>(origin, bitwise_cast<double>(bits));
147 default:
148 RELEASE_ASSERT_NOT_REACHED();
149 return nullptr;
150 }
151}
152
153Value* Procedure::addBottom(Origin origin, Type type)
154{
155 return addIntConstant(origin, type, 0);
156}
157
158Value* Procedure::addBottom(Value* value)
159{
160 return addBottom(value->origin(), value->type());
161}
162
163Value* Procedure::addBoolConstant(Origin origin, TriState triState)
164{
165 int32_t value = 0;
166 switch (triState) {
167 case FalseTriState:
168 value = 0;
169 break;
170 case TrueTriState:
171 value = 1;
172 break;
173 case MixedTriState:
174 return nullptr;
175 }
176
177 return addIntConstant(origin, Int32, value);
178}
179
180void Procedure::resetValueOwners()
181{
182 for (BasicBlock* block : *this) {
183 for (Value* value : *block)
184 value->owner = block;
185 }
186}
187
188void Procedure::resetReachability()
189{
190 recomputePredecessors(m_blocks);
191
192 // The common case is that this does not find any dead blocks.
193 bool foundDead = false;
194 for (auto& block : m_blocks) {
195 if (isBlockDead(block.get())) {
196 foundDead = true;
197 break;
198 }
199 }
200 if (!foundDead)
201 return;
202
203 resetValueOwners();
204
205 for (Value* value : values()) {
206 if (UpsilonValue* upsilon = value->as<UpsilonValue>()) {
207 if (isBlockDead(upsilon->phi()->owner))
208 upsilon->replaceWithNop();
209 }
210 }
211
212 for (auto& block : m_blocks) {
213 if (isBlockDead(block.get())) {
214 for (Value* value : *block)
215 deleteValue(value);
216 block = nullptr;
217 }
218 }
219}
220
221void Procedure::invalidateCFG()
222{
223 m_dominators = nullptr;
224 m_naturalLoops = nullptr;
225 m_backwardsCFG = nullptr;
226 m_backwardsDominators = nullptr;
227}
228
229void Procedure::dump(PrintStream& out) const
230{
231 IndexSet<Value*> valuesInBlocks;
232 for (BasicBlock* block : *this) {
233 out.print(deepDump(*this, block));
234 valuesInBlocks.addAll(*block);
235 }
236 bool didPrint = false;
237 for (Value* value : values()) {
238 if (valuesInBlocks.contains(value))
239 continue;
240
241 if (!didPrint) {
242 dataLog("Orphaned values:\n");
243 didPrint = true;
244 }
245 dataLog(" ", deepDump(*this, value), "\n");
246 }
247 if (hasQuirks())
248 out.print("Has Quirks: True\n");
249 if (variables().size()) {
250 out.print("Variables:\n");
251 for (Variable* variable : variables())
252 out.print(" ", deepDump(variable), "\n");
253 }
254 if (stackSlots().size()) {
255 out.print("Stack slots:\n");
256 for (StackSlot* slot : stackSlots())
257 out.print(" ", pointerDump(slot), ": ", deepDump(slot), "\n");
258 }
259 if (m_byproducts->count())
260 out.print(*m_byproducts);
261}
262
263Vector<BasicBlock*> Procedure::blocksInPreOrder()
264{
265 return B3::blocksInPreOrder(at(0));
266}
267
268Vector<BasicBlock*> Procedure::blocksInPostOrder()
269{
270 return B3::blocksInPostOrder(at(0));
271}
272
273void Procedure::deleteStackSlot(StackSlot* stackSlot)
274{
275 m_stackSlots.remove(stackSlot);
276}
277
278void Procedure::deleteVariable(Variable* variable)
279{
280 m_variables.remove(variable);
281}
282
283void Procedure::deleteValue(Value* value)
284{
285 m_values.remove(value);
286}
287
288void Procedure::deleteOrphans()
289{
290 IndexSet<Value*> valuesInBlocks;
291 for (BasicBlock* block : *this)
292 valuesInBlocks.addAll(*block);
293
294 // Since this method is not on any hot path, we do it conservatively: first a pass to
295 // identify the values to be removed, and then a second pass to remove them. This avoids any
296 // risk of the value iteration being broken by removals.
297 Vector<Value*, 16> toRemove;
298 for (Value* value : values()) {
299 if (!valuesInBlocks.contains(value))
300 toRemove.append(value);
301 else if (UpsilonValue* upsilon = value->as<UpsilonValue>()) {
302 if (!valuesInBlocks.contains(upsilon->phi()))
303 upsilon->replaceWithNop();
304 }
305 }
306
307 for (Value* value : toRemove)
308 deleteValue(value);
309}
310
311Dominators& Procedure::dominators()
312{
313 if (!m_dominators)
314 m_dominators = makeUnique<Dominators>(*this);
315 return *m_dominators;
316}
317
318NaturalLoops& Procedure::naturalLoops()
319{
320 if (!m_naturalLoops)
321 m_naturalLoops = makeUnique<NaturalLoops>(*this);
322 return *m_naturalLoops;
323}
324
325BackwardsCFG& Procedure::backwardsCFG()
326{
327 if (!m_backwardsCFG)
328 m_backwardsCFG = makeUnique<BackwardsCFG>(*this);
329 return *m_backwardsCFG;
330}
331
332BackwardsDominators& Procedure::backwardsDominators()
333{
334 if (!m_backwardsDominators)
335 m_backwardsDominators = makeUnique<BackwardsDominators>(*this);
336 return *m_backwardsDominators;
337}
338
339void Procedure::addFastConstant(const ValueKey& constant)
340{
341 RELEASE_ASSERT(constant.isConstant());
342 m_fastConstants.add(constant);
343}
344
345bool Procedure::isFastConstant(const ValueKey& constant)
346{
347 if (!constant)
348 return false;
349 return m_fastConstants.contains(constant);
350}
351
352CCallHelpers::Label Procedure::entrypointLabel(unsigned index) const
353{
354 return m_code->entrypointLabel(index);
355}
356
357void* Procedure::addDataSection(size_t size)
358{
359 if (!size)
360 return nullptr;
361 std::unique_ptr<DataSection> dataSection = makeUnique<DataSection>(size);
362 void* result = dataSection->data();
363 m_byproducts->add(WTFMove(dataSection));
364 return result;
365}
366
367unsigned Procedure::callArgAreaSizeInBytes() const
368{
369 return code().callArgAreaSizeInBytes();
370}
371
372void Procedure::requestCallArgAreaSizeInBytes(unsigned size)
373{
374 code().requestCallArgAreaSizeInBytes(size);
375}
376
377void Procedure::pinRegister(Reg reg)
378{
379 code().pinRegister(reg);
380}
381
382void Procedure::setOptLevel(unsigned optLevel)
383{
384 m_optLevel = optLevel;
385 code().setOptLevel(optLevel);
386}
387
388unsigned Procedure::frameSize() const
389{
390 return code().frameSize();
391}
392
393RegisterAtOffsetList Procedure::calleeSaveRegisterAtOffsetList() const
394{
395 return code().calleeSaveRegisterAtOffsetList();
396}
397
398Value* Procedure::addValueImpl(Value* value)
399{
400 return m_values.add(std::unique_ptr<Value>(value));
401}
402
403void Procedure::setBlockOrderImpl(Vector<BasicBlock*>& blocks)
404{
405 IndexSet<BasicBlock*> blocksSet;
406 blocksSet.addAll(blocks);
407
408 for (BasicBlock* block : *this) {
409 if (!blocksSet.contains(block))
410 blocks.append(block);
411 }
412
413 // Place blocks into this's block list by first leaking all of the blocks and then readopting
414 // them.
415 for (auto& entry : m_blocks)
416 entry.release();
417
418 m_blocks.resize(blocks.size());
419 for (unsigned i = 0; i < blocks.size(); ++i) {
420 BasicBlock* block = blocks[i];
421 block->m_index = i;
422 m_blocks[i] = std::unique_ptr<BasicBlock>(block);
423 }
424}
425
426void Procedure::setWasmBoundsCheckGenerator(RefPtr<WasmBoundsCheckGenerator> generator)
427{
428 code().setWasmBoundsCheckGenerator(generator);
429}
430
431RegisterSet Procedure::mutableGPRs()
432{
433 return code().mutableGPRs();
434}
435
436RegisterSet Procedure::mutableFPRs()
437{
438 return code().mutableFPRs();
439}
440
441void Procedure::setNumEntrypoints(unsigned numEntrypoints)
442{
443 m_numEntrypoints = numEntrypoints;
444 m_code->setNumEntrypoints(numEntrypoints);
445}
446
447} } // namespace JSC::B3
448
449#endif // ENABLE(B3_JIT)
450