1/*
2 * Copyright (C) 2016-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 "AirFixObviousSpills.h"
28
29#if ENABLE(B3_JIT)
30
31#include "AirArgInlines.h"
32#include "AirCode.h"
33#include "AirInstInlines.h"
34#include "AirPhaseScope.h"
35#include <wtf/IndexMap.h>
36#include <wtf/ListDump.h>
37
38namespace JSC { namespace B3 { namespace Air {
39
40namespace {
41
42namespace AirFixObviousSpillsInternal {
43static const bool verbose = false;
44}
45
46class FixObviousSpills {
47public:
48 FixObviousSpills(Code& code)
49 : m_code(code)
50 , m_atHead(code.size())
51 {
52 }
53
54 void run()
55 {
56 if (AirFixObviousSpillsInternal::verbose)
57 dataLog("Code before fixObviousSpills:\n", m_code);
58
59 computeAliases();
60 fixCode();
61 }
62
63private:
64 void computeAliases()
65 {
66 m_atHead[m_code[0]].wasVisited = true;
67
68 bool changed = true;
69 while (changed) {
70 changed = false;
71
72 for (BasicBlock* block : m_code) {
73 m_block = block;
74 m_state = m_atHead[block];
75 if (!m_state.wasVisited)
76 continue;
77
78 if (AirFixObviousSpillsInternal::verbose)
79 dataLog("Executing block ", *m_block, ": ", m_state, "\n");
80
81 for (m_instIndex = 0; m_instIndex < block->size(); ++m_instIndex)
82 executeInst();
83
84 for (BasicBlock* successor : block->successorBlocks()) {
85 State& toState = m_atHead[successor];
86 if (toState.wasVisited)
87 changed |= toState.merge(m_state);
88 else {
89 toState = m_state;
90 changed = true;
91 }
92 }
93 }
94 }
95 }
96
97 void fixCode()
98 {
99 for (BasicBlock* block : m_code) {
100 m_block = block;
101 m_state = m_atHead[block];
102 RELEASE_ASSERT(m_state.wasVisited);
103
104 for (m_instIndex = 0; m_instIndex < block->size(); ++m_instIndex) {
105 fixInst();
106 executeInst();
107 }
108 }
109 }
110
111 template<typename Func>
112 void forAllAliases(const Func& func)
113 {
114 Inst& inst = m_block->at(m_instIndex);
115
116 switch (inst.kind.opcode) {
117 case Move:
118 if (inst.args[0].isSomeImm()) {
119 if (inst.args[1].isReg())
120 func(RegConst(inst.args[1].reg(), inst.args[0].value()));
121 else if (isSpillSlot(inst.args[1]))
122 func(SlotConst(inst.args[1].stackSlot(), inst.args[0].value()));
123 } else if (isSpillSlot(inst.args[0]) && inst.args[1].isReg()) {
124 if (Optional<int64_t> constant = m_state.constantFor(inst.args[0]))
125 func(RegConst(inst.args[1].reg(), *constant));
126 func(RegSlot(inst.args[1].reg(), inst.args[0].stackSlot(), RegSlot::AllBits));
127 } else if (inst.args[0].isReg() && isSpillSlot(inst.args[1])) {
128 if (Optional<int64_t> constant = m_state.constantFor(inst.args[0]))
129 func(SlotConst(inst.args[1].stackSlot(), *constant));
130 func(RegSlot(inst.args[0].reg(), inst.args[1].stackSlot(), RegSlot::AllBits));
131 }
132 break;
133
134 case Move32:
135 if (inst.args[0].isSomeImm()) {
136 if (inst.args[1].isReg())
137 func(RegConst(inst.args[1].reg(), static_cast<uint32_t>(inst.args[0].value())));
138 else if (isSpillSlot(inst.args[1]))
139 func(SlotConst(inst.args[1].stackSlot(), static_cast<uint32_t>(inst.args[0].value())));
140 } else if (isSpillSlot(inst.args[0]) && inst.args[1].isReg()) {
141 if (Optional<int64_t> constant = m_state.constantFor(inst.args[0]))
142 func(RegConst(inst.args[1].reg(), static_cast<uint32_t>(*constant)));
143 func(RegSlot(inst.args[1].reg(), inst.args[0].stackSlot(), RegSlot::ZExt32));
144 } else if (inst.args[0].isReg() && isSpillSlot(inst.args[1])) {
145 if (Optional<int64_t> constant = m_state.constantFor(inst.args[0]))
146 func(SlotConst(inst.args[1].stackSlot(), static_cast<int32_t>(*constant)));
147 func(RegSlot(inst.args[0].reg(), inst.args[1].stackSlot(), RegSlot::Match32));
148 }
149 break;
150
151 case MoveFloat:
152 if (isSpillSlot(inst.args[0]) && inst.args[1].isReg())
153 func(RegSlot(inst.args[1].reg(), inst.args[0].stackSlot(), RegSlot::Match32));
154 else if (inst.args[0].isReg() && isSpillSlot(inst.args[1]))
155 func(RegSlot(inst.args[0].reg(), inst.args[1].stackSlot(), RegSlot::Match32));
156 break;
157
158 case MoveDouble:
159 if (isSpillSlot(inst.args[0]) && inst.args[1].isReg())
160 func(RegSlot(inst.args[1].reg(), inst.args[0].stackSlot(), RegSlot::AllBits));
161 else if (inst.args[0].isReg() && isSpillSlot(inst.args[1]))
162 func(RegSlot(inst.args[0].reg(), inst.args[1].stackSlot(), RegSlot::AllBits));
163 break;
164
165 default:
166 break;
167 }
168 }
169
170 void executeInst()
171 {
172 Inst& inst = m_block->at(m_instIndex);
173
174 if (AirFixObviousSpillsInternal::verbose)
175 dataLog(" Executing ", inst, ": ", m_state, "\n");
176
177 Inst::forEachDefWithExtraClobberedRegs<Arg>(
178 &inst, &inst,
179 [&] (const Arg& arg, Arg::Role, Bank, Width) {
180 if (AirFixObviousSpillsInternal::verbose)
181 dataLog(" Clobbering ", arg, "\n");
182 m_state.clobber(arg);
183 });
184
185 forAllAliases(
186 [&] (const auto& alias) {
187 m_state.addAlias(alias);
188 });
189 }
190
191 void fixInst()
192 {
193 Inst& inst = m_block->at(m_instIndex);
194
195 if (AirFixObviousSpillsInternal::verbose)
196 dataLog("Fixing inst ", inst, ": ", m_state, "\n");
197
198 // Check if alias analysis says that this is unnecessary.
199 bool shouldLive = true;
200 forAllAliases(
201 [&] (const auto& alias) {
202 shouldLive &= !m_state.contains(alias);
203 });
204 if (!shouldLive) {
205 inst = Inst();
206 return;
207 }
208
209 // First handle some special instructions.
210 switch (inst.kind.opcode) {
211 case Move: {
212 if (inst.args[0].isBigImm() && inst.args[1].isReg()
213 && isValidForm(Add64, Arg::Imm, Arg::Tmp, Arg::Tmp)) {
214 // BigImm materializations are super expensive on both x86 and ARM. Let's try to
215 // materialize this bad boy using math instead. Note that we use unsigned math here
216 // since it's more deterministic.
217 uint64_t myValue = inst.args[0].value();
218 Reg myDest = inst.args[1].reg();
219 for (const RegConst& regConst : m_state.regConst) {
220 uint64_t otherValue = regConst.constant;
221
222 // Let's try add. That's the only thing that works on all platforms, since it's
223 // the only cheap arithmetic op that x86 does in three operands. Long term, we
224 // should add fancier materializations here for ARM if the BigImm is yuge.
225 uint64_t delta = myValue - otherValue;
226
227 if (Arg::isValidImmForm(delta)) {
228 inst.kind = Add64;
229 inst.args.resize(3);
230 inst.args[0] = Arg::imm(delta);
231 inst.args[1] = Tmp(regConst.reg);
232 inst.args[2] = Tmp(myDest);
233 return;
234 }
235 }
236 return;
237 }
238 break;
239 }
240
241 default:
242 break;
243 }
244
245 // FIXME: This code should be taught how to simplify the spill-to-spill move
246 // instruction. Basically it needs to know to remove the scratch arg.
247 // https://bugs.webkit.org/show_bug.cgi?id=171133
248
249 // Create a copy in case we invalidate the instruction. That doesn't happen often.
250 Inst instCopy = inst;
251
252 // The goal is to replace references to stack slots. We only care about early uses. We can't
253 // handle UseDefs. We could teach this to handle UseDefs if we inserted a store instruction
254 // after and we proved that the register aliased to the stack slot dies here. We can get that
255 // information from the liveness analysis. We also can't handle late uses, because we don't
256 // look at late clobbers when doing this.
257 bool didThings = false;
258 auto handleArg = [&] (Arg& arg, Arg::Role role, Bank, Width width) {
259 if (!isSpillSlot(arg))
260 return;
261 if (!Arg::isEarlyUse(role))
262 return;
263 if (Arg::isAnyDef(role))
264 return;
265
266 // Try to get a register if at all possible.
267 if (const RegSlot* alias = m_state.getRegSlot(arg.stackSlot())) {
268 switch (width) {
269 case Width64:
270 if (alias->mode != RegSlot::AllBits)
271 return;
272 if (AirFixObviousSpillsInternal::verbose)
273 dataLog(" Replacing ", arg, " with ", alias->reg, "\n");
274 arg = Tmp(alias->reg);
275 didThings = true;
276 return;
277 case Width32:
278 if (AirFixObviousSpillsInternal::verbose)
279 dataLog(" Replacing ", arg, " with ", alias->reg, " (subwidth case)\n");
280 arg = Tmp(alias->reg);
281 didThings = true;
282 return;
283 default:
284 return;
285 }
286 }
287
288 // Revert to immediate if that didn't work.
289 if (const SlotConst* alias = m_state.getSlotConst(arg.stackSlot())) {
290 if (AirFixObviousSpillsInternal::verbose)
291 dataLog(" Replacing ", arg, " with constant ", alias->constant, "\n");
292 if (Arg::isValidImmForm(alias->constant))
293 arg = Arg::imm(alias->constant);
294 else
295 arg = Arg::bigImm(alias->constant);
296 didThings = true;
297 return;
298 }
299 };
300
301 inst.forEachArg(handleArg);
302 if (!didThings || inst.isValidForm())
303 return;
304
305 // We introduced something invalid along the way. Back up and carefully handle each argument.
306 inst = instCopy;
307 ASSERT(inst.isValidForm());
308 inst.forEachArg(
309 [&] (Arg& arg, Arg::Role role, Bank bank, Width width) {
310 Arg argCopy = arg;
311 handleArg(arg, role, bank, width);
312 if (!inst.isValidForm())
313 arg = argCopy;
314 });
315 }
316
317 static bool isSpillSlot(const Arg& arg)
318 {
319 return arg.isStack() && arg.stackSlot()->isSpill();
320 }
321
322 struct RegConst {
323 RegConst()
324 {
325 }
326
327 RegConst(Reg reg, int64_t constant)
328 : reg(reg)
329 , constant(constant)
330 {
331 }
332
333 explicit operator bool() const
334 {
335 return !!reg;
336 }
337
338 bool operator==(const RegConst& other) const
339 {
340 return reg == other.reg
341 && constant == other.constant;
342 }
343
344 void dump(PrintStream& out) const
345 {
346 out.print(reg, "->", constant);
347 }
348
349 Reg reg;
350 int64_t constant { 0 };
351 };
352
353 struct RegSlot {
354 enum Mode : int8_t {
355 AllBits,
356 ZExt32, // Register contains zero-extended contents of stack slot.
357 Match32 // Low 32 bits of register match low 32 bits of stack slot.
358 };
359
360 RegSlot()
361 {
362 }
363
364 RegSlot(Reg reg, StackSlot* slot, Mode mode)
365 : slot(slot)
366 , reg(reg)
367 , mode(mode)
368 {
369 }
370
371 explicit operator bool() const
372 {
373 return slot && reg;
374 }
375
376 bool operator==(const RegSlot& other) const
377 {
378 return slot == other.slot
379 && reg == other.reg
380 && mode == other.mode;
381 }
382
383 void dump(PrintStream& out) const
384 {
385 out.print(pointerDump(slot), "->", reg);
386 switch (mode) {
387 case AllBits:
388 out.print("(AllBits)");
389 break;
390 case ZExt32:
391 out.print("(ZExt32)");
392 break;
393 case Match32:
394 out.print("(Match32)");
395 break;
396 }
397 }
398
399 StackSlot* slot { nullptr };
400 Reg reg;
401 Mode mode { AllBits };
402 };
403
404 struct SlotConst {
405 SlotConst()
406 {
407 }
408
409 SlotConst(StackSlot* slot, int64_t constant)
410 : slot(slot)
411 , constant(constant)
412 {
413 }
414
415 explicit operator bool() const
416 {
417 return slot;
418 }
419
420 bool operator==(const SlotConst& other) const
421 {
422 return slot == other.slot
423 && constant == other.constant;
424 }
425
426 void dump(PrintStream& out) const
427 {
428 out.print(pointerDump(slot), "->", constant);
429 }
430
431 StackSlot* slot { nullptr };
432 int64_t constant { 0 };
433 };
434
435 struct State {
436 void addAlias(const RegConst& newAlias)
437 {
438 return regConst.append(newAlias);
439 }
440 void addAlias(const RegSlot& newAlias)
441 {
442 return regSlot.append(newAlias);
443 }
444 void addAlias(const SlotConst& newAlias)
445 {
446 return slotConst.append(newAlias);
447 }
448
449 bool contains(const RegConst& alias)
450 {
451 return regConst.contains(alias);
452 }
453 bool contains(const RegSlot& alias)
454 {
455 return regSlot.contains(alias);
456 }
457 bool contains(const SlotConst& alias)
458 {
459 return slotConst.contains(alias);
460 }
461
462 const RegConst* getRegConst(Reg reg) const
463 {
464 for (const RegConst& alias : regConst) {
465 if (alias.reg == reg)
466 return &alias;
467 }
468 return nullptr;
469 }
470
471 const RegSlot* getRegSlot(Reg reg) const
472 {
473 for (const RegSlot& alias : regSlot) {
474 if (alias.reg == reg)
475 return &alias;
476 }
477 return nullptr;
478 }
479
480 const RegSlot* getRegSlot(StackSlot* slot) const
481 {
482 for (const RegSlot& alias : regSlot) {
483 if (alias.slot == slot)
484 return &alias;
485 }
486 return nullptr;
487 }
488
489 const RegSlot* getRegSlot(Reg reg, StackSlot* slot) const
490 {
491 for (const RegSlot& alias : regSlot) {
492 if (alias.reg == reg && alias.slot == slot)
493 return &alias;
494 }
495 return nullptr;
496 }
497
498 const SlotConst* getSlotConst(StackSlot* slot) const
499 {
500 for (const SlotConst& alias : slotConst) {
501 if (alias.slot == slot)
502 return &alias;
503 }
504 return nullptr;
505 }
506
507 Optional<int64_t> constantFor(const Arg& arg)
508 {
509 if (arg.isReg()) {
510 if (const RegConst* alias = getRegConst(arg.reg()))
511 return alias->constant;
512 return WTF::nullopt;
513 }
514 if (arg.isStack()) {
515 if (const SlotConst* alias = getSlotConst(arg.stackSlot()))
516 return alias->constant;
517 return WTF::nullopt;
518 }
519 return WTF::nullopt;
520 }
521
522 void clobber(const Arg& arg)
523 {
524 if (arg.isReg()) {
525 regConst.removeAllMatching(
526 [&] (const RegConst& alias) -> bool {
527 return alias.reg == arg.reg();
528 });
529 regSlot.removeAllMatching(
530 [&] (const RegSlot& alias) -> bool {
531 return alias.reg == arg.reg();
532 });
533 return;
534 }
535 if (arg.isStack()) {
536 slotConst.removeAllMatching(
537 [&] (const SlotConst& alias) -> bool {
538 return alias.slot == arg.stackSlot();
539 });
540 regSlot.removeAllMatching(
541 [&] (const RegSlot& alias) -> bool {
542 return alias.slot == arg.stackSlot();
543 });
544 }
545 }
546
547 bool merge(const State& other)
548 {
549 bool changed = false;
550
551 changed |= !!regConst.removeAllMatching(
552 [&] (RegConst& alias) -> bool {
553 const RegConst* otherAlias = other.getRegConst(alias.reg);
554 if (!otherAlias)
555 return true;
556 if (alias.constant != otherAlias->constant)
557 return true;
558 return false;
559 });
560
561 changed |= !!slotConst.removeAllMatching(
562 [&] (SlotConst& alias) -> bool {
563 const SlotConst* otherAlias = other.getSlotConst(alias.slot);
564 if (!otherAlias)
565 return true;
566 if (alias.constant != otherAlias->constant)
567 return true;
568 return false;
569 });
570
571 changed |= !!regSlot.removeAllMatching(
572 [&] (RegSlot& alias) -> bool {
573 const RegSlot* otherAlias = other.getRegSlot(alias.reg, alias.slot);
574 if (!otherAlias)
575 return true;
576 if (alias.mode != RegSlot::Match32 && alias.mode != otherAlias->mode) {
577 alias.mode = RegSlot::Match32;
578 changed = true;
579 }
580 return false;
581 });
582
583 return changed;
584 }
585
586 void dump(PrintStream& out) const
587 {
588 out.print(
589 "{regConst = [", listDump(regConst), "], slotConst = [", listDump(slotConst),
590 "], regSlot = [", listDump(regSlot), "], wasVisited = ", wasVisited, "}");
591 }
592
593 Vector<RegConst> regConst;
594 Vector<SlotConst> slotConst;
595 Vector<RegSlot> regSlot;
596 bool wasVisited { false };
597 };
598
599 Code& m_code;
600 IndexMap<BasicBlock*, State> m_atHead;
601 State m_state;
602 BasicBlock* m_block { nullptr };
603 unsigned m_instIndex { 0 };
604};
605
606} // anonymous namespace
607
608void fixObviousSpills(Code& code)
609{
610 PhaseScope phaseScope(code, "fixObviousSpills");
611
612 FixObviousSpills fixObviousSpills(code);
613 fixObviousSpills.run();
614}
615
616} } } // namespace JSC::B3::Air
617
618#endif // ENABLE(B3_JIT)
619
620