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 "B3LowerToAir.h"
28
29#if ENABLE(B3_JIT)
30
31#include "AirBlockInsertionSet.h"
32#include "AirCCallSpecial.h"
33#include "AirCode.h"
34#include "AirInsertionSet.h"
35#include "AirInstInlines.h"
36#include "AirPrintSpecial.h"
37#include "AirStackSlot.h"
38#include "B3ArgumentRegValue.h"
39#include "B3AtomicValue.h"
40#include "B3BasicBlockInlines.h"
41#include "B3BlockWorklist.h"
42#include "B3CCallValue.h"
43#include "B3CheckSpecial.h"
44#include "B3Commutativity.h"
45#include "B3Dominators.h"
46#include "B3FenceValue.h"
47#include "B3MemoryValueInlines.h"
48#include "B3PatchpointSpecial.h"
49#include "B3PatchpointValue.h"
50#include "B3PhaseScope.h"
51#include "B3PhiChildren.h"
52#include "B3Procedure.h"
53#include "B3SlotBaseValue.h"
54#include "B3StackSlot.h"
55#include "B3UpsilonValue.h"
56#include "B3UseCounts.h"
57#include "B3ValueInlines.h"
58#include "B3Variable.h"
59#include "B3VariableValue.h"
60#include "B3WasmAddressValue.h"
61#include <wtf/IndexMap.h>
62#include <wtf/IndexSet.h>
63#include <wtf/ListDump.h>
64
65#if ASSERT_DISABLED
66IGNORE_RETURN_TYPE_WARNINGS_BEGIN
67#endif
68
69namespace JSC { namespace B3 {
70
71namespace {
72
73namespace B3LowerToAirInternal {
74static const bool verbose = false;
75}
76
77using Arg = Air::Arg;
78using Inst = Air::Inst;
79using Code = Air::Code;
80using Tmp = Air::Tmp;
81
82// FIXME: We wouldn't need this if Air supported Width modifiers in Air::Kind.
83// https://bugs.webkit.org/show_bug.cgi?id=169247
84#define OPCODE_FOR_WIDTH(opcode, width) ( \
85 (width) == Width8 ? Air::opcode ## 8 : \
86 (width) == Width16 ? Air::opcode ## 16 : \
87 (width) == Width32 ? Air::opcode ## 32 : \
88 Air::opcode ## 64)
89#define OPCODE_FOR_CANONICAL_WIDTH(opcode, width) ( \
90 (width) == Width64 ? Air::opcode ## 64 : Air::opcode ## 32)
91
92class LowerToAir {
93public:
94 LowerToAir(Procedure& procedure)
95 : m_valueToTmp(procedure.values().size())
96 , m_phiToTmp(procedure.values().size())
97 , m_blockToBlock(procedure.size())
98 , m_useCounts(procedure)
99 , m_phiChildren(procedure)
100 , m_dominators(procedure.dominators())
101 , m_procedure(procedure)
102 , m_code(procedure.code())
103 , m_blockInsertionSet(m_code)
104#if CPU(X86) || CPU(X86_64)
105 , m_eax(X86Registers::eax)
106 , m_ecx(X86Registers::ecx)
107 , m_edx(X86Registers::edx)
108#endif
109 {
110 }
111
112 void run()
113 {
114 using namespace Air;
115 for (B3::BasicBlock* block : m_procedure)
116 m_blockToBlock[block] = m_code.addBlock(block->frequency());
117
118 for (Value* value : m_procedure.values()) {
119 switch (value->opcode()) {
120 case Phi: {
121 m_phiToTmp[value] = m_code.newTmp(value->resultBank());
122 if (B3LowerToAirInternal::verbose)
123 dataLog("Phi tmp for ", *value, ": ", m_phiToTmp[value], "\n");
124 break;
125 }
126 default:
127 break;
128 }
129 }
130
131 for (B3::StackSlot* stack : m_procedure.stackSlots())
132 m_stackToStack.add(stack, m_code.addStackSlot(stack));
133 for (Variable* variable : m_procedure.variables())
134 m_variableToTmp.add(variable, m_code.newTmp(variable->bank()));
135
136 // Figure out which blocks are not rare.
137 m_fastWorklist.push(m_procedure[0]);
138 while (B3::BasicBlock* block = m_fastWorklist.pop()) {
139 for (B3::FrequentedBlock& successor : block->successors()) {
140 if (!successor.isRare())
141 m_fastWorklist.push(successor.block());
142 }
143 }
144
145 m_procedure.resetValueOwners(); // Used by crossesInterference().
146
147 // Lower defs before uses on a global level. This is a good heuristic to lock down a
148 // hoisted address expression before we duplicate it back into the loop.
149 for (B3::BasicBlock* block : m_procedure.blocksInPreOrder()) {
150 m_block = block;
151
152 m_isRare = !m_fastWorklist.saw(block);
153
154 if (B3LowerToAirInternal::verbose)
155 dataLog("Lowering Block ", *block, ":\n");
156
157 // Make sure that the successors are set up correctly.
158 for (B3::FrequentedBlock successor : block->successors()) {
159 m_blockToBlock[block]->successors().append(
160 Air::FrequentedBlock(m_blockToBlock[successor.block()], successor.frequency()));
161 }
162
163 // Process blocks in reverse order so we see uses before defs. That's what allows us
164 // to match patterns effectively.
165 for (unsigned i = block->size(); i--;) {
166 m_index = i;
167 m_value = block->at(i);
168 if (m_locked.contains(m_value))
169 continue;
170 m_insts.append(Vector<Inst>());
171 if (B3LowerToAirInternal::verbose)
172 dataLog("Lowering ", deepDump(m_procedure, m_value), ":\n");
173 lower();
174 if (B3LowerToAirInternal::verbose) {
175 for (Inst& inst : m_insts.last())
176 dataLog(" ", inst, "\n");
177 }
178 }
179
180 finishAppendingInstructions(m_blockToBlock[block]);
181 }
182
183 m_blockInsertionSet.execute();
184
185 Air::InsertionSet insertionSet(m_code);
186 for (Inst& inst : m_prologue)
187 insertionSet.insertInst(0, WTFMove(inst));
188 insertionSet.execute(m_code[0]);
189 }
190
191private:
192 bool shouldCopyPropagate(Value* value)
193 {
194 switch (value->opcode()) {
195 case Trunc:
196 case Identity:
197 case Opaque:
198 return true;
199 default:
200 return false;
201 }
202 }
203
204 class ArgPromise {
205 WTF_MAKE_NONCOPYABLE(ArgPromise);
206 public:
207 ArgPromise() { }
208
209 ArgPromise(const Arg& arg, Value* valueToLock = nullptr)
210 : m_arg(arg)
211 , m_value(valueToLock)
212 {
213 }
214
215 void swap(ArgPromise& other)
216 {
217 std::swap(m_arg, other.m_arg);
218 std::swap(m_value, other.m_value);
219 std::swap(m_wasConsumed, other.m_wasConsumed);
220 std::swap(m_wasWrapped, other.m_wasWrapped);
221 std::swap(m_traps, other.m_traps);
222 }
223
224 ArgPromise(ArgPromise&& other)
225 {
226 swap(other);
227 }
228
229 ArgPromise& operator=(ArgPromise&& other)
230 {
231 swap(other);
232 return *this;
233 }
234
235 ~ArgPromise()
236 {
237 if (m_wasConsumed)
238 RELEASE_ASSERT(m_wasWrapped);
239 }
240
241 void setTraps(bool value)
242 {
243 m_traps = value;
244 }
245
246 static ArgPromise tmp(Value* value)
247 {
248 ArgPromise result;
249 result.m_value = value;
250 return result;
251 }
252
253 explicit operator bool() const { return m_arg || m_value; }
254
255 Arg::Kind kind() const
256 {
257 if (!m_arg && m_value)
258 return Arg::Tmp;
259 return m_arg.kind();
260 }
261
262 const Arg& peek() const
263 {
264 return m_arg;
265 }
266
267 Arg consume(LowerToAir& lower)
268 {
269 m_wasConsumed = true;
270 if (!m_arg && m_value)
271 return lower.tmp(m_value);
272 if (m_value)
273 lower.commitInternal(m_value);
274 return m_arg;
275 }
276
277 template<typename... Args>
278 Inst inst(Args&&... args)
279 {
280 Inst result(std::forward<Args>(args)...);
281 result.kind.effects |= m_traps;
282 m_wasWrapped = true;
283 return result;
284 }
285
286 private:
287 // Three forms:
288 // Everything null: invalid.
289 // Arg non-null, value null: just use the arg, nothing special.
290 // Arg null, value non-null: it's a tmp, pin it when necessary.
291 // Arg non-null, value non-null: use the arg, lock the value.
292 Arg m_arg;
293 Value* m_value { nullptr };
294 bool m_wasConsumed { false };
295 bool m_wasWrapped { false };
296 bool m_traps { false };
297 };
298
299 // Consider using tmpPromise() in cases where you aren't sure that you want to pin the value yet.
300 // Here are three canonical ways of using tmp() and tmpPromise():
301 //
302 // Idiom #1: You know that you want a tmp() and you know that it will be valid for the
303 // instruction you're emitting.
304 //
305 // append(Foo, tmp(bar));
306 //
307 // Idiom #2: You don't know if you want to use a tmp() because you haven't determined if the
308 // instruction will accept it, so you query first. Note that the call to tmp() happens only after
309 // you are sure that you will use it.
310 //
311 // if (isValidForm(Foo, Arg::Tmp))
312 // append(Foo, tmp(bar))
313 //
314 // Idiom #3: Same as Idiom #2, but using tmpPromise. Notice that this calls consume() only after
315 // it's sure it will use the tmp. That's deliberate. Also note that you're required to pass any
316 // Inst you create with consumed promises through that promise's inst() function.
317 //
318 // ArgPromise promise = tmpPromise(bar);
319 // if (isValidForm(Foo, promise.kind()))
320 // append(promise.inst(Foo, promise.consume(*this)))
321 //
322 // In both idiom #2 and idiom #3, we don't pin the value to a temporary except when we actually
323 // emit the instruction. Both tmp() and tmpPromise().consume(*this) will pin it. Pinning means
324 // that we will henceforth require that the value of 'bar' is generated as a separate
325 // instruction. We don't want to pin the value to a temporary if we might change our minds, and
326 // pass an address operand representing 'bar' to Foo instead.
327 //
328 // Because tmp() pins, the following is not an idiom you should use:
329 //
330 // Tmp tmp = this->tmp(bar);
331 // if (isValidForm(Foo, tmp.kind()))
332 // append(Foo, tmp);
333 //
334 // That's because if isValidForm() returns false, you will have already pinned the 'bar' to a
335 // temporary. You might later want to try to do something like loadPromise(), and that will fail.
336 // This arises in operations that have both a Addr,Tmp and Tmp,Addr forms. The following code
337 // seems right, but will actually fail to ever match the Tmp,Addr form because by then, the right
338 // value is already pinned.
339 //
340 // auto tryThings = [this] (const Arg& left, const Arg& right) {
341 // if (isValidForm(Foo, left.kind(), right.kind()))
342 // return Inst(Foo, m_value, left, right);
343 // return Inst();
344 // };
345 // if (Inst result = tryThings(loadAddr(left), tmp(right)))
346 // return result;
347 // if (Inst result = tryThings(tmp(left), loadAddr(right))) // this never succeeds.
348 // return result;
349 // return Inst(Foo, m_value, tmp(left), tmp(right));
350 //
351 // If you imagine that loadAddr(value) is just loadPromise(value).consume(*this), then this code
352 // will run correctly - it will generate OK code - but the second form is never matched.
353 // loadAddr(right) will never succeed because it will observe that 'right' is already pinned.
354 // Of course, it's exactly because of the risky nature of such code that we don't have a
355 // loadAddr() helper and require you to balance ArgPromise's in code like this. Such code will
356 // work fine if written as:
357 //
358 // auto tryThings = [this] (ArgPromise& left, ArgPromise& right) {
359 // if (isValidForm(Foo, left.kind(), right.kind()))
360 // return left.inst(right.inst(Foo, m_value, left.consume(*this), right.consume(*this)));
361 // return Inst();
362 // };
363 // if (Inst result = tryThings(loadPromise(left), tmpPromise(right)))
364 // return result;
365 // if (Inst result = tryThings(tmpPromise(left), loadPromise(right)))
366 // return result;
367 // return Inst(Foo, m_value, tmp(left), tmp(right));
368 //
369 // Notice that we did use tmp in the fall-back case at the end, because by then, we know for sure
370 // that we want a tmp. But using tmpPromise in the tryThings() calls ensures that doing so
371 // doesn't prevent us from trying loadPromise on the same value.
372 Tmp tmp(Value* value)
373 {
374 Tmp& tmp = m_valueToTmp[value];
375 if (!tmp) {
376 while (shouldCopyPropagate(value))
377 value = value->child(0);
378
379 if (value->opcode() == FramePointer)
380 return Tmp(GPRInfo::callFrameRegister);
381
382 Tmp& realTmp = m_valueToTmp[value];
383 if (!realTmp) {
384 realTmp = m_code.newTmp(value->resultBank());
385 if (m_procedure.isFastConstant(value->key()))
386 m_code.addFastTmp(realTmp);
387 if (B3LowerToAirInternal::verbose)
388 dataLog("Tmp for ", *value, ": ", realTmp, "\n");
389 }
390 tmp = realTmp;
391 }
392 return tmp;
393 }
394
395 ArgPromise tmpPromise(Value* value)
396 {
397 return ArgPromise::tmp(value);
398 }
399
400 bool canBeInternal(Value* value)
401 {
402 // If one of the internal things has already been computed, then we don't want to cause
403 // it to be recomputed again.
404 if (m_valueToTmp[value])
405 return false;
406
407 // We require internals to have only one use - us. It's not clear if this should be numUses() or
408 // numUsingInstructions(). Ideally, it would be numUsingInstructions(), except that it's not clear
409 // if we'd actually do the right thing when matching over such a DAG pattern. For now, it simply
410 // doesn't matter because we don't implement patterns that would trigger this.
411 if (m_useCounts.numUses(value) != 1)
412 return false;
413
414 return true;
415 }
416
417 // If you ask canBeInternal() and then construct something from that, and you commit to emitting
418 // that code, then you must commitInternal() on that value. This is tricky, and you only need to
419 // do it if you're pattern matching by hand rather than using the patterns language. Long story
420 // short, you should avoid this by using the pattern matcher to match patterns.
421 void commitInternal(Value* value)
422 {
423 if (value)
424 m_locked.add(value);
425 }
426
427 bool crossesInterference(Value* value)
428 {
429 // If it's in a foreign block, then be conservative. We could handle this if we were
430 // willing to do heavier analysis. For example, if we had liveness, then we could label
431 // values as "crossing interference" if they interfere with anything that they are live
432 // across. But, it's not clear how useful this would be.
433 if (value->owner != m_value->owner)
434 return true;
435
436 Effects effects = value->effects();
437
438 for (unsigned i = m_index; i--;) {
439 Value* otherValue = m_block->at(i);
440 if (otherValue == value)
441 return false;
442 if (effects.interferes(otherValue->effects()))
443 return true;
444 }
445
446 ASSERT_NOT_REACHED();
447 return true;
448 }
449
450 template<typename Int, typename = Value::IsLegalOffset<Int>>
451 Optional<unsigned> scaleForShl(Value* shl, Int offset, Optional<Width> width = WTF::nullopt)
452 {
453 if (shl->opcode() != Shl)
454 return WTF::nullopt;
455 if (!shl->child(1)->hasInt32())
456 return WTF::nullopt;
457 unsigned logScale = shl->child(1)->asInt32();
458 if (shl->type() == Int32)
459 logScale &= 31;
460 else
461 logScale &= 63;
462 // Use 64-bit math to perform the shift so that <<32 does the right thing, but then switch
463 // to signed since that's what all of our APIs want.
464 int64_t bigScale = static_cast<uint64_t>(1) << static_cast<uint64_t>(logScale);
465 if (!isRepresentableAs<int32_t>(bigScale))
466 return WTF::nullopt;
467 unsigned scale = static_cast<int32_t>(bigScale);
468 if (!Arg::isValidIndexForm(scale, offset, width))
469 return WTF::nullopt;
470 return scale;
471 }
472
473 // This turns the given operand into an address.
474 template<typename Int, typename = Value::IsLegalOffset<Int>>
475 Arg effectiveAddr(Value* address, Int offset, Width width)
476 {
477 ASSERT(Arg::isValidAddrForm(offset, width));
478
479 auto fallback = [&] () -> Arg {
480 return Arg::addr(tmp(address), offset);
481 };
482
483 static const unsigned lotsOfUses = 10; // This is arbitrary and we should tune it eventually.
484
485 // Only match if the address value isn't used in some large number of places.
486 if (m_useCounts.numUses(address) > lotsOfUses)
487 return fallback();
488
489 switch (address->opcode()) {
490 case Add: {
491 Value* left = address->child(0);
492 Value* right = address->child(1);
493
494 auto tryIndex = [&] (Value* index, Value* base) -> Arg {
495 Optional<unsigned> scale = scaleForShl(index, offset, width);
496 if (!scale)
497 return Arg();
498 if (m_locked.contains(index->child(0)) || m_locked.contains(base))
499 return Arg();
500 return Arg::index(tmp(base), tmp(index->child(0)), *scale, offset);
501 };
502
503 if (Arg result = tryIndex(left, right))
504 return result;
505 if (Arg result = tryIndex(right, left))
506 return result;
507
508 if (m_locked.contains(left) || m_locked.contains(right)
509 || !Arg::isValidIndexForm(1, offset, width))
510 return fallback();
511
512 return Arg::index(tmp(left), tmp(right), 1, offset);
513 }
514
515 case Shl: {
516 Value* left = address->child(0);
517
518 // We'll never see child(1)->isInt32(0), since that would have been reduced. If the shift
519 // amount is greater than 1, then there isn't really anything smart that we could do here.
520 // We avoid using baseless indexes because their encoding isn't particularly efficient.
521 if (m_locked.contains(left) || !address->child(1)->isInt32(1)
522 || !Arg::isValidIndexForm(1, offset, width))
523 return fallback();
524
525 return Arg::index(tmp(left), tmp(left), 1, offset);
526 }
527
528 case FramePointer:
529 return Arg::addr(Tmp(GPRInfo::callFrameRegister), offset);
530
531 case SlotBase:
532 return Arg::stack(m_stackToStack.get(address->as<SlotBaseValue>()->slot()), offset);
533
534 case WasmAddress: {
535 WasmAddressValue* wasmAddress = address->as<WasmAddressValue>();
536 Value* pointer = wasmAddress->child(0);
537 if (!Arg::isValidIndexForm(1, offset, width) || m_locked.contains(pointer))
538 return fallback();
539
540 // FIXME: We should support ARM64 LDR 32-bit addressing, which will
541 // allow us to fuse a Shl ptr, 2 into the address. Additionally, and
542 // perhaps more importantly, it would allow us to avoid a truncating
543 // move. See: https://bugs.webkit.org/show_bug.cgi?id=163465
544
545 return Arg::index(Tmp(wasmAddress->pinnedGPR()), tmp(pointer), 1, offset);
546 }
547
548 default:
549 return fallback();
550 }
551 }
552
553 // This gives you the address of the given Load or Store. If it's not a Load or Store, then
554 // it returns Arg().
555 Arg addr(Value* memoryValue)
556 {
557 MemoryValue* value = memoryValue->as<MemoryValue>();
558 if (!value)
559 return Arg();
560
561 if (value->requiresSimpleAddr())
562 return Arg::simpleAddr(tmp(value->lastChild()));
563
564 Value::OffsetType offset = value->offset();
565 Width width = value->accessWidth();
566
567 Arg result = effectiveAddr(value->lastChild(), offset, width);
568 RELEASE_ASSERT(result.isValidForm(width));
569
570 return result;
571 }
572
573 template<typename... Args>
574 Inst trappingInst(bool traps, Args&&... args)
575 {
576 Inst result(std::forward<Args>(args)...);
577 result.kind.effects |= traps;
578 return result;
579 }
580
581 template<typename... Args>
582 Inst trappingInst(Value* value, Args&&... args)
583 {
584 return trappingInst(value->traps(), std::forward<Args>(args)...);
585 }
586
587 ArgPromise loadPromiseAnyOpcode(Value* loadValue)
588 {
589 RELEASE_ASSERT(loadValue->as<MemoryValue>());
590 if (!canBeInternal(loadValue))
591 return Arg();
592 if (crossesInterference(loadValue))
593 return Arg();
594 // On x86, all loads have fences. Doing this kind of instruction selection will move the load,
595 // but that's fine because our interference analysis stops the motion of fences around other
596 // fences. So, any load motion we introduce here would not be observable.
597 if (!isX86() && loadValue->as<MemoryValue>()->hasFence())
598 return Arg();
599 Arg loadAddr = addr(loadValue);
600 RELEASE_ASSERT(loadAddr);
601 ArgPromise result(loadAddr, loadValue);
602 if (loadValue->traps())
603 result.setTraps(true);
604 return result;
605 }
606
607 ArgPromise loadPromise(Value* loadValue, B3::Opcode loadOpcode)
608 {
609 if (loadValue->opcode() != loadOpcode)
610 return Arg();
611 return loadPromiseAnyOpcode(loadValue);
612 }
613
614 ArgPromise loadPromise(Value* loadValue)
615 {
616 return loadPromise(loadValue, Load);
617 }
618
619 Arg imm(int64_t intValue)
620 {
621 if (Arg::isValidImmForm(intValue))
622 return Arg::imm(intValue);
623 return Arg();
624 }
625
626 Arg imm(Value* value)
627 {
628 if (value->hasInt())
629 return imm(value->asInt());
630 return Arg();
631 }
632
633 Arg bitImm(Value* value)
634 {
635 if (value->hasInt()) {
636 int64_t intValue = value->asInt();
637 if (Arg::isValidBitImmForm(intValue))
638 return Arg::bitImm(intValue);
639 }
640 return Arg();
641 }
642
643 Arg bitImm64(Value* value)
644 {
645 if (value->hasInt()) {
646 int64_t intValue = value->asInt();
647 if (Arg::isValidBitImm64Form(intValue))
648 return Arg::bitImm64(intValue);
649 }
650 return Arg();
651 }
652
653 Arg immOrTmp(Value* value)
654 {
655 if (Arg result = imm(value))
656 return result;
657 return tmp(value);
658 }
659
660 // By convention, we use Oops to mean "I don't know".
661 Air::Opcode tryOpcodeForType(
662 Air::Opcode opcode32, Air::Opcode opcode64, Air::Opcode opcodeDouble, Air::Opcode opcodeFloat, Type type)
663 {
664 Air::Opcode opcode;
665 switch (type) {
666 case Int32:
667 opcode = opcode32;
668 break;
669 case Int64:
670 opcode = opcode64;
671 break;
672 case Float:
673 opcode = opcodeFloat;
674 break;
675 case Double:
676 opcode = opcodeDouble;
677 break;
678 default:
679 opcode = Air::Oops;
680 break;
681 }
682
683 return opcode;
684 }
685
686 Air::Opcode tryOpcodeForType(Air::Opcode opcode32, Air::Opcode opcode64, Type type)
687 {
688 return tryOpcodeForType(opcode32, opcode64, Air::Oops, Air::Oops, type);
689 }
690
691 Air::Opcode opcodeForType(
692 Air::Opcode opcode32, Air::Opcode opcode64, Air::Opcode opcodeDouble, Air::Opcode opcodeFloat, Type type)
693 {
694 Air::Opcode opcode = tryOpcodeForType(opcode32, opcode64, opcodeDouble, opcodeFloat, type);
695 RELEASE_ASSERT(opcode != Air::Oops);
696 return opcode;
697 }
698
699 Air::Opcode opcodeForType(Air::Opcode opcode32, Air::Opcode opcode64, Type type)
700 {
701 return tryOpcodeForType(opcode32, opcode64, Air::Oops, Air::Oops, type);
702 }
703
704 template<Air::Opcode opcode32, Air::Opcode opcode64, Air::Opcode opcodeDouble = Air::Oops, Air::Opcode opcodeFloat = Air::Oops>
705 void appendUnOp(Value* value)
706 {
707 Air::Opcode opcode = opcodeForType(opcode32, opcode64, opcodeDouble, opcodeFloat, value->type());
708
709 Tmp result = tmp(m_value);
710
711 // Two operand forms like:
712 // Op a, b
713 // mean something like:
714 // b = Op a
715
716 ArgPromise addr = loadPromise(value);
717 if (isValidForm(opcode, addr.kind(), Arg::Tmp)) {
718 append(addr.inst(opcode, m_value, addr.consume(*this), result));
719 return;
720 }
721
722 if (isValidForm(opcode, Arg::Tmp, Arg::Tmp)) {
723 append(opcode, tmp(value), result);
724 return;
725 }
726
727 ASSERT(value->type() == m_value->type());
728 append(relaxedMoveForType(m_value->type()), tmp(value), result);
729 append(opcode, result);
730 }
731
732 // Call this method when doing two-operand lowering of a commutative operation. You have a choice of
733 // which incoming Value is moved into the result. This will select which one is likely to be most
734 // profitable to use as the result. Doing the right thing can have big performance consequences in tight
735 // kernels.
736 bool preferRightForResult(Value* left, Value* right)
737 {
738 // The default is to move left into result, because that's required for non-commutative instructions.
739 // The value that we want to move into result position is the one that dies here. So, if we're
740 // compiling a commutative operation and we know that actually right is the one that dies right here,
741 // then we can flip things around to help coalescing, which then kills the move instruction.
742 //
743 // But it's more complicated:
744 // - Used-once is a bad estimate of whether the variable dies here.
745 // - A child might be a candidate for coalescing with this value.
746 //
747 // Currently, we have machinery in place to recognize super obvious forms of the latter issue.
748
749 // We recognize when a child is a Phi that has this value as one of its children. We're very
750 // conservative about this; for example we don't even consider transitive Phi children.
751 bool leftIsPhiWithThis = m_phiChildren[left].transitivelyUses(m_value);
752 bool rightIsPhiWithThis = m_phiChildren[right].transitivelyUses(m_value);
753
754 if (leftIsPhiWithThis != rightIsPhiWithThis)
755 return rightIsPhiWithThis;
756
757 if (m_useCounts.numUsingInstructions(right) != 1)
758 return false;
759
760 if (m_useCounts.numUsingInstructions(left) != 1)
761 return true;
762
763 // The use count might be 1 if the variable is live around a loop. We can guarantee that we
764 // pick the variable that is least likely to suffer this problem if we pick the one that
765 // is closest to us in an idom walk. By convention, we slightly bias this in favor of
766 // returning true.
767
768 // We cannot prefer right if right is further away in an idom walk.
769 if (m_dominators.strictlyDominates(right->owner, left->owner))
770 return false;
771
772 return true;
773 }
774
775 template<Air::Opcode opcode32, Air::Opcode opcode64, Air::Opcode opcodeDouble, Air::Opcode opcodeFloat, Commutativity commutativity = NotCommutative>
776 void appendBinOp(Value* left, Value* right)
777 {
778 Air::Opcode opcode = opcodeForType(opcode32, opcode64, opcodeDouble, opcodeFloat, left->type());
779
780 Tmp result = tmp(m_value);
781
782 // Three-operand forms like:
783 // Op a, b, c
784 // mean something like:
785 // c = a Op b
786
787 if (isValidForm(opcode, Arg::Imm, Arg::Tmp, Arg::Tmp)) {
788 if (commutativity == Commutative) {
789 if (imm(right)) {
790 append(opcode, imm(right), tmp(left), result);
791 return;
792 }
793 } else {
794 // A non-commutative operation could have an immediate in left.
795 if (imm(left)) {
796 append(opcode, imm(left), tmp(right), result);
797 return;
798 }
799 }
800 }
801
802 if (isValidForm(opcode, Arg::BitImm, Arg::Tmp, Arg::Tmp)) {
803 if (commutativity == Commutative) {
804 if (Arg rightArg = bitImm(right)) {
805 append(opcode, rightArg, tmp(left), result);
806 return;
807 }
808 } else {
809 // A non-commutative operation could have an immediate in left.
810 if (Arg leftArg = bitImm(left)) {
811 append(opcode, leftArg, tmp(right), result);
812 return;
813 }
814 }
815 }
816
817 if (isValidForm(opcode, Arg::BitImm64, Arg::Tmp, Arg::Tmp)) {
818 if (commutativity == Commutative) {
819 if (Arg rightArg = bitImm64(right)) {
820 append(opcode, rightArg, tmp(left), result);
821 return;
822 }
823 } else {
824 // A non-commutative operation could have an immediate in left.
825 if (Arg leftArg = bitImm64(left)) {
826 append(opcode, leftArg, tmp(right), result);
827 return;
828 }
829 }
830 }
831
832 if (imm(right) && isValidForm(opcode, Arg::Tmp, Arg::Imm, Arg::Tmp)) {
833 append(opcode, tmp(left), imm(right), result);
834 return;
835 }
836
837 // Note that no extant architecture has a three-operand form of binary operations that also
838 // load from memory. If such an abomination did exist, we would handle it somewhere around
839 // here.
840
841 // Two-operand forms like:
842 // Op a, b
843 // mean something like:
844 // b = b Op a
845
846 // At this point, we prefer versions of the operation that have a fused load or an immediate
847 // over three operand forms.
848
849 if (left != right) {
850 ArgPromise leftAddr = loadPromise(left);
851 if (isValidForm(opcode, leftAddr.kind(), Arg::Tmp, Arg::Tmp)) {
852 append(leftAddr.inst(opcode, m_value, leftAddr.consume(*this), tmp(right), result));
853 return;
854 }
855
856 if (commutativity == Commutative) {
857 if (isValidForm(opcode, leftAddr.kind(), Arg::Tmp)) {
858 append(relaxedMoveForType(m_value->type()), tmp(right), result);
859 append(leftAddr.inst(opcode, m_value, leftAddr.consume(*this), result));
860 return;
861 }
862 }
863
864 ArgPromise rightAddr = loadPromise(right);
865 if (isValidForm(opcode, Arg::Tmp, rightAddr.kind(), Arg::Tmp)) {
866 append(rightAddr.inst(opcode, m_value, tmp(left), rightAddr.consume(*this), result));
867 return;
868 }
869
870 if (commutativity == Commutative) {
871 if (isValidForm(opcode, rightAddr.kind(), Arg::Tmp, Arg::Tmp)) {
872 append(rightAddr.inst(opcode, m_value, rightAddr.consume(*this), tmp(left), result));
873 return;
874 }
875 }
876
877 if (isValidForm(opcode, rightAddr.kind(), Arg::Tmp)) {
878 append(relaxedMoveForType(m_value->type()), tmp(left), result);
879 append(rightAddr.inst(opcode, m_value, rightAddr.consume(*this), result));
880 return;
881 }
882 }
883
884 if (imm(right) && isValidForm(opcode, Arg::Imm, Arg::Tmp)) {
885 append(relaxedMoveForType(m_value->type()), tmp(left), result);
886 append(opcode, imm(right), result);
887 return;
888 }
889
890 if (isValidForm(opcode, Arg::Tmp, Arg::Tmp, Arg::Tmp)) {
891 append(opcode, tmp(left), tmp(right), result);
892 return;
893 }
894
895 if (commutativity == Commutative && preferRightForResult(left, right)) {
896 append(relaxedMoveForType(m_value->type()), tmp(right), result);
897 append(opcode, tmp(left), result);
898 return;
899 }
900
901 append(relaxedMoveForType(m_value->type()), tmp(left), result);
902 append(opcode, tmp(right), result);
903 }
904
905 template<Air::Opcode opcode32, Air::Opcode opcode64, Commutativity commutativity = NotCommutative>
906 void appendBinOp(Value* left, Value* right)
907 {
908 appendBinOp<opcode32, opcode64, Air::Oops, Air::Oops, commutativity>(left, right);
909 }
910
911 template<Air::Opcode opcode32, Air::Opcode opcode64>
912 void appendShift(Value* value, Value* amount)
913 {
914 using namespace Air;
915 Air::Opcode opcode = opcodeForType(opcode32, opcode64, value->type());
916
917 if (imm(amount)) {
918 if (isValidForm(opcode, Arg::Tmp, Arg::Imm, Arg::Tmp)) {
919 append(opcode, tmp(value), imm(amount), tmp(m_value));
920 return;
921 }
922 if (isValidForm(opcode, Arg::Imm, Arg::Tmp)) {
923 append(Move, tmp(value), tmp(m_value));
924 append(opcode, imm(amount), tmp(m_value));
925 return;
926 }
927 }
928
929 if (isValidForm(opcode, Arg::Tmp, Arg::Tmp, Arg::Tmp)) {
930 append(opcode, tmp(value), tmp(amount), tmp(m_value));
931 return;
932 }
933
934 append(Move, tmp(value), tmp(m_value));
935 append(Move, tmp(amount), m_ecx);
936 append(opcode, m_ecx, tmp(m_value));
937 }
938
939 template<Air::Opcode opcode32, Air::Opcode opcode64>
940 bool tryAppendStoreUnOp(Value* value)
941 {
942 Air::Opcode opcode = tryOpcodeForType(opcode32, opcode64, value->type());
943 if (opcode == Air::Oops)
944 return false;
945
946 Arg storeAddr = addr(m_value);
947 ASSERT(storeAddr);
948
949 ArgPromise loadPromise = this->loadPromise(value);
950 if (loadPromise.peek() != storeAddr)
951 return false;
952
953 if (!isValidForm(opcode, storeAddr.kind()))
954 return false;
955
956 loadPromise.consume(*this);
957 append(trappingInst(m_value, loadPromise.inst(opcode, m_value, storeAddr)));
958 return true;
959 }
960
961 template<
962 Air::Opcode opcode32, Air::Opcode opcode64, Commutativity commutativity = NotCommutative>
963 bool tryAppendStoreBinOp(Value* left, Value* right)
964 {
965 RELEASE_ASSERT(m_value->as<MemoryValue>());
966
967 Air::Opcode opcode = tryOpcodeForType(opcode32, opcode64, left->type());
968 if (opcode == Air::Oops)
969 return false;
970
971 if (m_value->as<MemoryValue>()->hasFence())
972 return false;
973
974 Arg storeAddr = addr(m_value);
975 ASSERT(storeAddr);
976
977 auto getLoadPromise = [&] (Value* load) -> ArgPromise {
978 switch (m_value->opcode()) {
979 case B3::Store:
980 if (load->opcode() != B3::Load)
981 return ArgPromise();
982 break;
983 case B3::Store8:
984 if (load->opcode() != B3::Load8Z && load->opcode() != B3::Load8S)
985 return ArgPromise();
986 break;
987 case B3::Store16:
988 if (load->opcode() != B3::Load16Z && load->opcode() != B3::Load16S)
989 return ArgPromise();
990 break;
991 default:
992 return ArgPromise();
993 }
994 return loadPromiseAnyOpcode(load);
995 };
996
997 ArgPromise loadPromise;
998 Value* otherValue = nullptr;
999
1000 loadPromise = getLoadPromise(left);
1001 if (loadPromise.peek() == storeAddr)
1002 otherValue = right;
1003 else if (commutativity == Commutative) {
1004 loadPromise = getLoadPromise(right);
1005 if (loadPromise.peek() == storeAddr)
1006 otherValue = left;
1007 }
1008
1009 if (!otherValue)
1010 return false;
1011
1012 if (isValidForm(opcode, Arg::Imm, storeAddr.kind()) && imm(otherValue)) {
1013 loadPromise.consume(*this);
1014 append(trappingInst(m_value, loadPromise.inst(opcode, m_value, imm(otherValue), storeAddr)));
1015 return true;
1016 }
1017
1018 if (!isValidForm(opcode, Arg::Tmp, storeAddr.kind()))
1019 return false;
1020
1021 loadPromise.consume(*this);
1022 append(trappingInst(m_value, loadPromise.inst(opcode, m_value, tmp(otherValue), storeAddr)));
1023 return true;
1024 }
1025
1026 Inst createStore(Air::Kind move, Value* value, const Arg& dest)
1027 {
1028 using namespace Air;
1029 if (auto imm_value = imm(value)) {
1030 if (isARM64() && imm_value.value() == 0) {
1031 switch (move.opcode) {
1032 default:
1033 break;
1034 case Air::Move32:
1035 if (isValidForm(StoreZero32, dest.kind()) && dest.isValidForm(Width32))
1036 return Inst(StoreZero32, m_value, dest);
1037 break;
1038 case Air::Move:
1039 if (isValidForm(StoreZero64, dest.kind()) && dest.isValidForm(Width64))
1040 return Inst(StoreZero64, m_value, dest);
1041 break;
1042 }
1043 }
1044 if (isValidForm(move.opcode, Arg::Imm, dest.kind()))
1045 return Inst(move, m_value, imm_value, dest);
1046 }
1047
1048 return Inst(move, m_value, tmp(value), dest);
1049 }
1050
1051 Air::Opcode storeOpcode(Width width, Bank bank)
1052 {
1053 using namespace Air;
1054 switch (width) {
1055 case Width8:
1056 RELEASE_ASSERT(bank == GP);
1057 return Air::Store8;
1058 case Width16:
1059 RELEASE_ASSERT(bank == GP);
1060 return Air::Store16;
1061 case Width32:
1062 switch (bank) {
1063 case GP:
1064 return Move32;
1065 case FP:
1066 return MoveFloat;
1067 }
1068 break;
1069 case Width64:
1070 RELEASE_ASSERT(is64Bit());
1071 switch (bank) {
1072 case GP:
1073 return Move;
1074 case FP:
1075 return MoveDouble;
1076 }
1077 break;
1078 }
1079 RELEASE_ASSERT_NOT_REACHED();
1080 }
1081
1082 void appendStore(Value* value, const Arg& dest)
1083 {
1084 using namespace Air;
1085 MemoryValue* memory = value->as<MemoryValue>();
1086 RELEASE_ASSERT(memory->isStore());
1087
1088 Air::Kind kind;
1089 if (memory->hasFence()) {
1090 RELEASE_ASSERT(memory->accessBank() == GP);
1091
1092 if (isX86()) {
1093 kind = OPCODE_FOR_WIDTH(Xchg, memory->accessWidth());
1094 kind.effects = true;
1095 Tmp swapTmp = m_code.newTmp(GP);
1096 append(relaxedMoveForType(memory->accessType()), tmp(memory->child(0)), swapTmp);
1097 append(kind, swapTmp, dest);
1098 return;
1099 }
1100
1101 kind = OPCODE_FOR_WIDTH(StoreRel, memory->accessWidth());
1102 } else
1103 kind = storeOpcode(memory->accessWidth(), memory->accessBank());
1104
1105 kind.effects |= memory->traps();
1106
1107 append(createStore(kind, memory->child(0), dest));
1108 }
1109
1110 Air::Opcode moveForType(Type type)
1111 {
1112 using namespace Air;
1113 switch (type) {
1114 case Int32:
1115 return Move32;
1116 case Int64:
1117 RELEASE_ASSERT(is64Bit());
1118 return Move;
1119 case Float:
1120 return MoveFloat;
1121 case Double:
1122 return MoveDouble;
1123 case Void:
1124 break;
1125 }
1126 RELEASE_ASSERT_NOT_REACHED();
1127 return Air::Oops;
1128 }
1129
1130 Air::Opcode relaxedMoveForType(Type type)
1131 {
1132 using namespace Air;
1133 switch (type) {
1134 case Int32:
1135 case Int64:
1136 // For Int32, we could return Move or Move32. It's a trade-off.
1137 //
1138 // Move32: Using Move32 guarantees that we use the narrower move, but in cases where the
1139 // register allocator can't prove that the variables involved are 32-bit, this will
1140 // disable coalescing.
1141 //
1142 // Move: Using Move guarantees that the register allocator can coalesce normally, but in
1143 // cases where it can't prove that the variables are 32-bit and it doesn't coalesce,
1144 // this will force us to use a full 64-bit Move instead of the slightly cheaper
1145 // 32-bit Move32.
1146 //
1147 // Coalescing is a lot more profitable than turning Move into Move32. So, it's better to
1148 // use Move here because in cases where the register allocator cannot prove that
1149 // everything is 32-bit, we still get coalescing.
1150 return Move;
1151 case Float:
1152 // MoveFloat is always coalescable and we never convert MoveDouble to MoveFloat, so we
1153 // should use MoveFloat when we know that the temporaries involved are 32-bit.
1154 return MoveFloat;
1155 case Double:
1156 return MoveDouble;
1157 case Void:
1158 break;
1159 }
1160 RELEASE_ASSERT_NOT_REACHED();
1161 return Air::Oops;
1162 }
1163
1164#if ENABLE(MASM_PROBE)
1165 template<typename... Arguments>
1166 void print(Arguments&&... arguments)
1167 {
1168 Value* origin = m_value;
1169 print(origin, std::forward<Arguments>(arguments)...);
1170 }
1171
1172 template<typename... Arguments>
1173 void print(Value* origin, Arguments&&... arguments)
1174 {
1175 auto printList = Printer::makePrintRecordList(arguments...);
1176 auto printSpecial = static_cast<Air::PrintSpecial*>(m_code.addSpecial(std::make_unique<Air::PrintSpecial>(printList)));
1177 Inst inst(Air::Patch, origin, Arg::special(printSpecial));
1178 Printer::appendAirArgs(inst, std::forward<Arguments>(arguments)...);
1179 append(WTFMove(inst));
1180 }
1181#endif // ENABLE(MASM_PROBE)
1182
1183 template<typename... Arguments>
1184 void append(Air::Kind kind, Arguments&&... arguments)
1185 {
1186 m_insts.last().append(Inst(kind, m_value, std::forward<Arguments>(arguments)...));
1187 }
1188
1189 template<typename... Arguments>
1190 void appendTrapping(Air::Kind kind, Arguments&&... arguments)
1191 {
1192 m_insts.last().append(trappingInst(m_value, kind, m_value, std::forward<Arguments>(arguments)...));
1193 }
1194
1195 void append(Inst&& inst)
1196 {
1197 m_insts.last().append(WTFMove(inst));
1198 }
1199 void append(const Inst& inst)
1200 {
1201 m_insts.last().append(inst);
1202 }
1203
1204 void finishAppendingInstructions(Air::BasicBlock* target)
1205 {
1206 // Now append the instructions. m_insts contains them in reverse order, so we process
1207 // it in reverse.
1208 for (unsigned i = m_insts.size(); i--;) {
1209 for (Inst& inst : m_insts[i])
1210 target->appendInst(WTFMove(inst));
1211 }
1212 m_insts.shrink(0);
1213 }
1214
1215 Air::BasicBlock* newBlock()
1216 {
1217 return m_blockInsertionSet.insertAfter(m_blockToBlock[m_block]);
1218 }
1219
1220 // NOTE: This will create a continuation block (`nextBlock`) *after* any blocks you've created using
1221 // newBlock(). So, it's preferable to create all of your blocks upfront using newBlock(). Also note
1222 // that any code you emit before this will be prepended to the continuation, and any code you emit
1223 // after this will be appended to the previous block.
1224 void splitBlock(Air::BasicBlock*& previousBlock, Air::BasicBlock*& nextBlock)
1225 {
1226 Air::BasicBlock* block = m_blockToBlock[m_block];
1227
1228 previousBlock = block;
1229 nextBlock = m_blockInsertionSet.insertAfter(block);
1230
1231 finishAppendingInstructions(nextBlock);
1232 nextBlock->successors() = block->successors();
1233 block->successors().clear();
1234
1235 m_insts.append(Vector<Inst>());
1236 }
1237
1238 template<typename T, typename... Arguments>
1239 T* ensureSpecial(T*& field, Arguments&&... arguments)
1240 {
1241 if (!field) {
1242 field = static_cast<T*>(
1243 m_code.addSpecial(std::make_unique<T>(std::forward<Arguments>(arguments)...)));
1244 }
1245 return field;
1246 }
1247
1248 template<typename... Arguments>
1249 CheckSpecial* ensureCheckSpecial(Arguments&&... arguments)
1250 {
1251 CheckSpecial::Key key(std::forward<Arguments>(arguments)...);
1252 auto result = m_checkSpecials.add(key, nullptr);
1253 return ensureSpecial(result.iterator->value, key);
1254 }
1255
1256 void fillStackmap(Inst& inst, StackmapValue* stackmap, unsigned numSkipped)
1257 {
1258 for (unsigned i = numSkipped; i < stackmap->numChildren(); ++i) {
1259 ConstrainedValue value = stackmap->constrainedChild(i);
1260
1261 Arg arg;
1262 switch (value.rep().kind()) {
1263 case ValueRep::WarmAny:
1264 case ValueRep::ColdAny:
1265 case ValueRep::LateColdAny:
1266 if (imm(value.value()))
1267 arg = imm(value.value());
1268 else if (value.value()->hasInt64())
1269 arg = Arg::bigImm(value.value()->asInt64());
1270 else if (value.value()->hasDouble() && canBeInternal(value.value())) {
1271 commitInternal(value.value());
1272 arg = Arg::bigImm(bitwise_cast<int64_t>(value.value()->asDouble()));
1273 } else
1274 arg = tmp(value.value());
1275 break;
1276 case ValueRep::SomeRegister:
1277 arg = tmp(value.value());
1278 break;
1279 case ValueRep::SomeRegisterWithClobber: {
1280 Tmp dstTmp = m_code.newTmp(value.value()->resultBank());
1281 append(relaxedMoveForType(value.value()->type()), immOrTmp(value.value()), dstTmp);
1282 arg = dstTmp;
1283 break;
1284 }
1285 case ValueRep::LateRegister:
1286 case ValueRep::Register:
1287 stackmap->earlyClobbered().clear(value.rep().reg());
1288 arg = Tmp(value.rep().reg());
1289 append(relaxedMoveForType(value.value()->type()), immOrTmp(value.value()), arg);
1290 break;
1291 case ValueRep::StackArgument:
1292 arg = Arg::callArg(value.rep().offsetFromSP());
1293 append(trappingInst(m_value, createStore(moveForType(value.value()->type()), value.value(), arg)));
1294 break;
1295 default:
1296 RELEASE_ASSERT_NOT_REACHED();
1297 break;
1298 }
1299 inst.args.append(arg);
1300 }
1301 }
1302
1303 // Create an Inst to do the comparison specified by the given value.
1304 template<typename CompareFunctor, typename TestFunctor, typename CompareDoubleFunctor, typename CompareFloatFunctor>
1305 Inst createGenericCompare(
1306 Value* value,
1307 const CompareFunctor& compare, // Signature: (Width, Arg relCond, Arg, Arg) -> Inst
1308 const TestFunctor& test, // Signature: (Width, Arg resCond, Arg, Arg) -> Inst
1309 const CompareDoubleFunctor& compareDouble, // Signature: (Arg doubleCond, Arg, Arg) -> Inst
1310 const CompareFloatFunctor& compareFloat, // Signature: (Arg doubleCond, Arg, Arg) -> Inst
1311 bool inverted = false)
1312 {
1313 // NOTE: This is totally happy to match comparisons that have already been computed elsewhere
1314 // since on most architectures, the cost of branching on a previously computed comparison
1315 // result is almost always higher than just doing another fused compare/branch. The only time
1316 // it could be worse is if we have a binary comparison and both operands are variables (not
1317 // constants), and we encounter register pressure. Even in this case, duplicating the compare
1318 // so that we can fuse it to the branch will be more efficient most of the time, since
1319 // register pressure is not *that* common. For this reason, this algorithm will always
1320 // duplicate the comparison.
1321 //
1322 // However, we cannot duplicate loads. The canBeInternal() on a load will assume that we
1323 // already validated canBeInternal() on all of the values that got us to the load. So, even
1324 // if we are sharing a value, we still need to call canBeInternal() for the purpose of
1325 // tracking whether we are still in good shape to fuse loads.
1326 //
1327 // We could even have a chain of compare values that we fuse, and any member of the chain
1328 // could be shared. Once any of them are shared, then the shared one's transitive children
1329 // cannot be locked (i.e. commitInternal()). But if none of them are shared, then we want to
1330 // lock all of them because that's a prerequisite to fusing the loads so that the loads don't
1331 // get duplicated. For example, we might have:
1332 //
1333 // @tmp1 = LessThan(@a, @b)
1334 // @tmp2 = Equal(@tmp1, 0)
1335 // Branch(@tmp2)
1336 //
1337 // If either @a or @b are loads, then we want to have locked @tmp1 and @tmp2 so that they
1338 // don't emit the loads a second time. But if we had another use of @tmp2, then we cannot
1339 // lock @tmp1 (or @a or @b) because then we'll get into trouble when the other values that
1340 // try to share @tmp1 with us try to do their lowering.
1341 //
1342 // There's one more wrinkle. If we don't lock an internal value, then this internal value may
1343 // have already separately locked its children. So, if we're not locking a value then we need
1344 // to make sure that its children aren't locked. We encapsulate this in two ways:
1345 //
1346 // canCommitInternal: This variable tells us if the values that we've fused so far are
1347 // locked. This means that we're not sharing any of them with anyone. This permits us to fuse
1348 // loads. If it's false, then we cannot fuse loads and we also need to ensure that the
1349 // children of any values we try to fuse-by-sharing are not already locked. You don't have to
1350 // worry about the children locking thing if you use prepareToFuse() before trying to fuse a
1351 // sharable value. But, you do need to guard any load fusion by checking if canCommitInternal
1352 // is true.
1353 //
1354 // FusionResult prepareToFuse(value): Call this when you think that you would like to fuse
1355 // some value and that value is not a load. It will automatically handle the shared-or-locked
1356 // issues and it will clear canCommitInternal if necessary. This will return CannotFuse
1357 // (which acts like false) if the value cannot be locked and its children are locked. That's
1358 // rare, but you just need to make sure that you do smart things when this happens (i.e. just
1359 // use the value rather than trying to fuse it). After you call prepareToFuse(), you can
1360 // still change your mind about whether you will actually fuse the value. If you do fuse it,
1361 // you need to call commitFusion(value, fusionResult).
1362 //
1363 // commitFusion(value, fusionResult): Handles calling commitInternal(value) if fusionResult
1364 // is FuseAndCommit.
1365
1366 bool canCommitInternal = true;
1367
1368 enum FusionResult {
1369 CannotFuse,
1370 FuseAndCommit,
1371 Fuse
1372 };
1373 auto prepareToFuse = [&] (Value* value) -> FusionResult {
1374 if (value == m_value) {
1375 // It's not actually internal. It's the root value. We're good to go.
1376 return Fuse;
1377 }
1378
1379 if (canCommitInternal && canBeInternal(value)) {
1380 // We are the only users of this value. This also means that the value's children
1381 // could not have been locked, since we have now proved that m_value dominates value
1382 // in the data flow graph. To only other way to value is from a user of m_value. If
1383 // value's children are shared with others, then they could not have been locked
1384 // because their use count is greater than 1. If they are only used from value, then
1385 // in order for value's children to be locked, value would also have to be locked,
1386 // and we just proved that it wasn't.
1387 return FuseAndCommit;
1388 }
1389
1390 // We're going to try to share value with others. It's possible that some other basic
1391 // block had already emitted code for value and then matched over its children and then
1392 // locked them, in which case we just want to use value instead of duplicating it. So, we
1393 // validate the children. Note that this only arises in linear chains like:
1394 //
1395 // BB#1:
1396 // @1 = Foo(...)
1397 // @2 = Bar(@1)
1398 // Jump(#2)
1399 // BB#2:
1400 // @3 = Baz(@2)
1401 //
1402 // Notice how we could start by generating code for BB#1 and then decide to lock @1 when
1403 // generating code for @2, if we have some way of fusing Bar and Foo into a single
1404 // instruction. This is legal, since indeed @1 only has one user. The fact that @2 now
1405 // has a tmp (i.e. @2 is pinned), canBeInternal(@2) will return false, which brings us
1406 // here. In that case, we cannot match over @2 because then we'd hit a hazard if we end
1407 // up deciding not to fuse Foo into the fused Baz/Bar.
1408 //
1409 // Happily, there are only two places where this kind of child validation happens is in
1410 // rules that admit sharing, like this and effectiveAddress().
1411 //
1412 // N.B. We could probably avoid the need to do value locking if we committed to a well
1413 // chosen code generation order. For example, if we guaranteed that all of the users of
1414 // a value get generated before that value, then there's no way for the lowering of @3 to
1415 // see @1 locked. But we don't want to do that, since this is a greedy instruction
1416 // selector and so we want to be able to play with order.
1417 for (Value* child : value->children()) {
1418 if (m_locked.contains(child))
1419 return CannotFuse;
1420 }
1421
1422 // It's safe to share value, but since we're sharing, it means that we aren't locking it.
1423 // If we don't lock it, then fusing loads is off limits and all of value's children will
1424 // have to go through the sharing path as well. Fusing loads is off limits because the load
1425 // could already have been emitted elsehwere - so fusing it here would duplicate the load.
1426 // We don't consider that to be a legal optimization.
1427 canCommitInternal = false;
1428
1429 return Fuse;
1430 };
1431
1432 auto commitFusion = [&] (Value* value, FusionResult result) {
1433 if (result == FuseAndCommit)
1434 commitInternal(value);
1435 };
1436
1437 // Chew through any inversions. This loop isn't necessary for comparisons and branches, but
1438 // we do need at least one iteration of it for Check.
1439 for (;;) {
1440 bool shouldInvert =
1441 (value->opcode() == BitXor && value->child(1)->hasInt() && (value->child(1)->asInt() == 1) && value->child(0)->returnsBool())
1442 || (value->opcode() == Equal && value->child(1)->isInt(0));
1443 if (!shouldInvert)
1444 break;
1445
1446 FusionResult fusionResult = prepareToFuse(value);
1447 if (fusionResult == CannotFuse)
1448 break;
1449 commitFusion(value, fusionResult);
1450
1451 value = value->child(0);
1452 inverted = !inverted;
1453 }
1454
1455 auto createRelCond = [&] (
1456 MacroAssembler::RelationalCondition relationalCondition,
1457 MacroAssembler::DoubleCondition doubleCondition) {
1458 Arg relCond = Arg::relCond(relationalCondition).inverted(inverted);
1459 Arg doubleCond = Arg::doubleCond(doubleCondition).inverted(inverted);
1460 Value* left = value->child(0);
1461 Value* right = value->child(1);
1462
1463 if (isInt(value->child(0)->type())) {
1464 Arg rightImm = imm(right);
1465
1466 auto tryCompare = [&] (
1467 Width width, ArgPromise&& left, ArgPromise&& right) -> Inst {
1468 if (Inst result = compare(width, relCond, left, right))
1469 return result;
1470 if (Inst result = compare(width, relCond.flipped(), right, left))
1471 return result;
1472 return Inst();
1473 };
1474
1475 auto tryCompareLoadImm = [&] (
1476 Width width, B3::Opcode loadOpcode, Arg::Signedness signedness) -> Inst {
1477 if (rightImm && rightImm.isRepresentableAs(width, signedness)) {
1478 if (Inst result = tryCompare(width, loadPromise(left, loadOpcode), rightImm)) {
1479 commitInternal(left);
1480 return result;
1481 }
1482 }
1483 return Inst();
1484 };
1485
1486 Width width = value->child(0)->resultWidth();
1487
1488 if (canCommitInternal) {
1489 // First handle compares that involve fewer bits than B3's type system supports.
1490 // This is pretty important. For example, we want this to be a single
1491 // instruction:
1492 //
1493 // @1 = Load8S(...)
1494 // @2 = Const32(...)
1495 // @3 = LessThan(@1, @2)
1496 // Branch(@3)
1497
1498 if (relCond.isSignedCond()) {
1499 if (Inst result = tryCompareLoadImm(Width8, Load8S, Arg::Signed))
1500 return result;
1501 }
1502
1503 if (relCond.isUnsignedCond()) {
1504 if (Inst result = tryCompareLoadImm(Width8, Load8Z, Arg::Unsigned))
1505 return result;
1506 }
1507
1508 if (relCond.isSignedCond()) {
1509 if (Inst result = tryCompareLoadImm(Width16, Load16S, Arg::Signed))
1510 return result;
1511 }
1512
1513 if (relCond.isUnsignedCond()) {
1514 if (Inst result = tryCompareLoadImm(Width16, Load16Z, Arg::Unsigned))
1515 return result;
1516 }
1517
1518 // Now handle compares that involve a load and an immediate.
1519
1520 if (Inst result = tryCompareLoadImm(width, Load, Arg::Signed))
1521 return result;
1522
1523 // Now handle compares that involve a load. It's not obvious that it's better to
1524 // handle this before the immediate cases or not. Probably doesn't matter.
1525
1526 if (Inst result = tryCompare(width, loadPromise(left), tmpPromise(right))) {
1527 commitInternal(left);
1528 return result;
1529 }
1530
1531 if (Inst result = tryCompare(width, tmpPromise(left), loadPromise(right))) {
1532 commitInternal(right);
1533 return result;
1534 }
1535 }
1536
1537 // Now handle compares that involve an immediate and a tmp.
1538
1539 if (rightImm && rightImm.isRepresentableAs<int32_t>()) {
1540 if (Inst result = tryCompare(width, tmpPromise(left), rightImm))
1541 return result;
1542 }
1543
1544 // Finally, handle comparison between tmps.
1545 ArgPromise leftPromise = tmpPromise(left);
1546 ArgPromise rightPromise = tmpPromise(right);
1547 return compare(width, relCond, leftPromise, rightPromise);
1548 }
1549
1550 // Floating point comparisons can't really do anything smart.
1551 ArgPromise leftPromise = tmpPromise(left);
1552 ArgPromise rightPromise = tmpPromise(right);
1553 if (value->child(0)->type() == Float)
1554 return compareFloat(doubleCond, leftPromise, rightPromise);
1555 return compareDouble(doubleCond, leftPromise, rightPromise);
1556 };
1557
1558 Width width = value->resultWidth();
1559 Arg resCond = Arg::resCond(MacroAssembler::NonZero).inverted(inverted);
1560
1561 auto tryTest = [&] (
1562 Width width, ArgPromise&& left, ArgPromise&& right) -> Inst {
1563 if (Inst result = test(width, resCond, left, right))
1564 return result;
1565 if (Inst result = test(width, resCond, right, left))
1566 return result;
1567 return Inst();
1568 };
1569
1570 auto attemptFused = [&] () -> Inst {
1571 switch (value->opcode()) {
1572 case NotEqual:
1573 return createRelCond(MacroAssembler::NotEqual, MacroAssembler::DoubleNotEqualOrUnordered);
1574 case Equal:
1575 return createRelCond(MacroAssembler::Equal, MacroAssembler::DoubleEqual);
1576 case LessThan:
1577 return createRelCond(MacroAssembler::LessThan, MacroAssembler::DoubleLessThan);
1578 case GreaterThan:
1579 return createRelCond(MacroAssembler::GreaterThan, MacroAssembler::DoubleGreaterThan);
1580 case LessEqual:
1581 return createRelCond(MacroAssembler::LessThanOrEqual, MacroAssembler::DoubleLessThanOrEqual);
1582 case GreaterEqual:
1583 return createRelCond(MacroAssembler::GreaterThanOrEqual, MacroAssembler::DoubleGreaterThanOrEqual);
1584 case EqualOrUnordered:
1585 // The integer condition is never used in this case.
1586 return createRelCond(MacroAssembler::Equal, MacroAssembler::DoubleEqualOrUnordered);
1587 case Above:
1588 // We use a bogus double condition because these integer comparisons won't got down that
1589 // path anyway.
1590 return createRelCond(MacroAssembler::Above, MacroAssembler::DoubleEqual);
1591 case Below:
1592 return createRelCond(MacroAssembler::Below, MacroAssembler::DoubleEqual);
1593 case AboveEqual:
1594 return createRelCond(MacroAssembler::AboveOrEqual, MacroAssembler::DoubleEqual);
1595 case BelowEqual:
1596 return createRelCond(MacroAssembler::BelowOrEqual, MacroAssembler::DoubleEqual);
1597 case BitAnd: {
1598 Value* left = value->child(0);
1599 Value* right = value->child(1);
1600
1601 bool hasRightConst;
1602 int64_t rightConst;
1603 Arg rightImm;
1604 Arg rightImm64;
1605
1606 hasRightConst = right->hasInt();
1607 if (hasRightConst) {
1608 rightConst = right->asInt();
1609 rightImm = bitImm(right);
1610 rightImm64 = bitImm64(right);
1611 }
1612
1613 auto tryTestLoadImm = [&] (Width width, Arg::Signedness signedness, B3::Opcode loadOpcode) -> Inst {
1614 if (!hasRightConst)
1615 return Inst();
1616 // Signed loads will create high bits, so if the immediate has high bits
1617 // then we cannot proceed. Consider BitAnd(Load8S(ptr), 0x101). This cannot
1618 // be turned into testb (ptr), $1, since if the high bit within that byte
1619 // was set then it would be extended to include 0x100. The handling below
1620 // won't anticipate this, so we need to catch it here.
1621 if (signedness == Arg::Signed
1622 && !Arg::isRepresentableAs(width, Arg::Unsigned, rightConst))
1623 return Inst();
1624
1625 // FIXME: If this is unsigned then we can chop things off of the immediate.
1626 // This might make the immediate more legal. Perhaps that's a job for
1627 // strength reduction?
1628 // https://bugs.webkit.org/show_bug.cgi?id=169248
1629
1630 if (rightImm) {
1631 if (Inst result = tryTest(width, loadPromise(left, loadOpcode), rightImm)) {
1632 commitInternal(left);
1633 return result;
1634 }
1635 }
1636 if (rightImm64) {
1637 if (Inst result = tryTest(width, loadPromise(left, loadOpcode), rightImm64)) {
1638 commitInternal(left);
1639 return result;
1640 }
1641 }
1642 return Inst();
1643 };
1644
1645 if (canCommitInternal) {
1646 // First handle test's that involve fewer bits than B3's type system supports.
1647
1648 if (Inst result = tryTestLoadImm(Width8, Arg::Unsigned, Load8Z))
1649 return result;
1650
1651 if (Inst result = tryTestLoadImm(Width8, Arg::Signed, Load8S))
1652 return result;
1653
1654 if (Inst result = tryTestLoadImm(Width16, Arg::Unsigned, Load16Z))
1655 return result;
1656
1657 if (Inst result = tryTestLoadImm(Width16, Arg::Signed, Load16S))
1658 return result;
1659
1660 // This allows us to use a 32-bit test for 64-bit BitAnd if the immediate is
1661 // representable as an unsigned 32-bit value. The logic involved is the same
1662 // as if we were pondering using a 32-bit test for
1663 // BitAnd(SExt(Load(ptr)), const), in the sense that in both cases we have
1664 // to worry about high bits. So, we use the "Signed" version of this helper.
1665 if (Inst result = tryTestLoadImm(Width32, Arg::Signed, Load))
1666 return result;
1667
1668 // This is needed to handle 32-bit test for arbitrary 32-bit immediates.
1669 if (Inst result = tryTestLoadImm(width, Arg::Unsigned, Load))
1670 return result;
1671
1672 // Now handle test's that involve a load.
1673
1674 Width width = value->child(0)->resultWidth();
1675 if (Inst result = tryTest(width, loadPromise(left), tmpPromise(right))) {
1676 commitInternal(left);
1677 return result;
1678 }
1679
1680 if (Inst result = tryTest(width, tmpPromise(left), loadPromise(right))) {
1681 commitInternal(right);
1682 return result;
1683 }
1684 }
1685
1686 // Now handle test's that involve an immediate and a tmp.
1687
1688 if (hasRightConst) {
1689 if ((width == Width32 && rightConst == 0xffffffff)
1690 || (width == Width64 && rightConst == -1)) {
1691 if (Inst result = tryTest(width, tmpPromise(left), tmpPromise(left)))
1692 return result;
1693 }
1694 if (isRepresentableAs<uint32_t>(rightConst)) {
1695 if (Inst result = tryTest(Width32, tmpPromise(left), rightImm))
1696 return result;
1697 if (Inst result = tryTest(Width32, tmpPromise(left), rightImm64))
1698 return result;
1699 }
1700 if (Inst result = tryTest(width, tmpPromise(left), rightImm))
1701 return result;
1702 if (Inst result = tryTest(width, tmpPromise(left), rightImm64))
1703 return result;
1704 }
1705
1706 // Finally, just do tmp's.
1707 return tryTest(width, tmpPromise(left), tmpPromise(right));
1708 }
1709 default:
1710 return Inst();
1711 }
1712 };
1713
1714 if (FusionResult fusionResult = prepareToFuse(value)) {
1715 if (Inst result = attemptFused()) {
1716 commitFusion(value, fusionResult);
1717 return result;
1718 }
1719 }
1720
1721 if (Arg::isValidBitImmForm(-1)) {
1722 if (canCommitInternal && value->as<MemoryValue>()) {
1723 // Handle things like Branch(Load8Z(value))
1724
1725 if (Inst result = tryTest(Width8, loadPromise(value, Load8Z), Arg::bitImm(-1))) {
1726 commitInternal(value);
1727 return result;
1728 }
1729
1730 if (Inst result = tryTest(Width8, loadPromise(value, Load8S), Arg::bitImm(-1))) {
1731 commitInternal(value);
1732 return result;
1733 }
1734
1735 if (Inst result = tryTest(Width16, loadPromise(value, Load16Z), Arg::bitImm(-1))) {
1736 commitInternal(value);
1737 return result;
1738 }
1739
1740 if (Inst result = tryTest(Width16, loadPromise(value, Load16S), Arg::bitImm(-1))) {
1741 commitInternal(value);
1742 return result;
1743 }
1744
1745 if (Inst result = tryTest(width, loadPromise(value), Arg::bitImm(-1))) {
1746 commitInternal(value);
1747 return result;
1748 }
1749 }
1750
1751 ArgPromise leftPromise = tmpPromise(value);
1752 ArgPromise rightPromise = Arg::bitImm(-1);
1753 if (Inst result = test(width, resCond, leftPromise, rightPromise))
1754 return result;
1755 }
1756
1757 // Sometimes this is the only form of test available. We prefer not to use this because
1758 // it's less canonical.
1759 ArgPromise leftPromise = tmpPromise(value);
1760 ArgPromise rightPromise = tmpPromise(value);
1761 return test(width, resCond, leftPromise, rightPromise);
1762 }
1763
1764 Inst createBranch(Value* value, bool inverted = false)
1765 {
1766 using namespace Air;
1767 return createGenericCompare(
1768 value,
1769 [this] (
1770 Width width, const Arg& relCond,
1771 ArgPromise& left, ArgPromise& right) -> Inst {
1772 switch (width) {
1773 case Width8:
1774 if (isValidForm(Branch8, Arg::RelCond, left.kind(), right.kind())) {
1775 return left.inst(right.inst(
1776 Branch8, m_value, relCond,
1777 left.consume(*this), right.consume(*this)));
1778 }
1779 return Inst();
1780 case Width16:
1781 return Inst();
1782 case Width32:
1783 if (isValidForm(Branch32, Arg::RelCond, left.kind(), right.kind())) {
1784 return left.inst(right.inst(
1785 Branch32, m_value, relCond,
1786 left.consume(*this), right.consume(*this)));
1787 }
1788 return Inst();
1789 case Width64:
1790 if (isValidForm(Branch64, Arg::RelCond, left.kind(), right.kind())) {
1791 return left.inst(right.inst(
1792 Branch64, m_value, relCond,
1793 left.consume(*this), right.consume(*this)));
1794 }
1795 return Inst();
1796 }
1797 ASSERT_NOT_REACHED();
1798 },
1799 [this] (
1800 Width width, const Arg& resCond,
1801 ArgPromise& left, ArgPromise& right) -> Inst {
1802 switch (width) {
1803 case Width8:
1804 if (isValidForm(BranchTest8, Arg::ResCond, left.kind(), right.kind())) {
1805 return left.inst(right.inst(
1806 BranchTest8, m_value, resCond,
1807 left.consume(*this), right.consume(*this)));
1808 }
1809 return Inst();
1810 case Width16:
1811 return Inst();
1812 case Width32:
1813 if (isValidForm(BranchTest32, Arg::ResCond, left.kind(), right.kind())) {
1814 return left.inst(right.inst(
1815 BranchTest32, m_value, resCond,
1816 left.consume(*this), right.consume(*this)));
1817 }
1818 return Inst();
1819 case Width64:
1820 if (isValidForm(BranchTest64, Arg::ResCond, left.kind(), right.kind())) {
1821 return left.inst(right.inst(
1822 BranchTest64, m_value, resCond,
1823 left.consume(*this), right.consume(*this)));
1824 }
1825 return Inst();
1826 }
1827 ASSERT_NOT_REACHED();
1828 },
1829 [this] (Arg doubleCond, ArgPromise& left, ArgPromise& right) -> Inst {
1830 if (isValidForm(BranchDouble, Arg::DoubleCond, left.kind(), right.kind())) {
1831 return left.inst(right.inst(
1832 BranchDouble, m_value, doubleCond,
1833 left.consume(*this), right.consume(*this)));
1834 }
1835 return Inst();
1836 },
1837 [this] (Arg doubleCond, ArgPromise& left, ArgPromise& right) -> Inst {
1838 if (isValidForm(BranchFloat, Arg::DoubleCond, left.kind(), right.kind())) {
1839 return left.inst(right.inst(
1840 BranchFloat, m_value, doubleCond,
1841 left.consume(*this), right.consume(*this)));
1842 }
1843 return Inst();
1844 },
1845 inverted);
1846 }
1847
1848 Inst createCompare(Value* value, bool inverted = false)
1849 {
1850 using namespace Air;
1851 return createGenericCompare(
1852 value,
1853 [this] (
1854 Width width, const Arg& relCond,
1855 ArgPromise& left, ArgPromise& right) -> Inst {
1856 switch (width) {
1857 case Width8:
1858 case Width16:
1859 return Inst();
1860 case Width32:
1861 if (isValidForm(Compare32, Arg::RelCond, left.kind(), right.kind(), Arg::Tmp)) {
1862 return left.inst(right.inst(
1863 Compare32, m_value, relCond,
1864 left.consume(*this), right.consume(*this), tmp(m_value)));
1865 }
1866 return Inst();
1867 case Width64:
1868 if (isValidForm(Compare64, Arg::RelCond, left.kind(), right.kind(), Arg::Tmp)) {
1869 return left.inst(right.inst(
1870 Compare64, m_value, relCond,
1871 left.consume(*this), right.consume(*this), tmp(m_value)));
1872 }
1873 return Inst();
1874 }
1875 ASSERT_NOT_REACHED();
1876 },
1877 [this] (
1878 Width width, const Arg& resCond,
1879 ArgPromise& left, ArgPromise& right) -> Inst {
1880 switch (width) {
1881 case Width8:
1882 case Width16:
1883 return Inst();
1884 case Width32:
1885 if (isValidForm(Test32, Arg::ResCond, left.kind(), right.kind(), Arg::Tmp)) {
1886 return left.inst(right.inst(
1887 Test32, m_value, resCond,
1888 left.consume(*this), right.consume(*this), tmp(m_value)));
1889 }
1890 return Inst();
1891 case Width64:
1892 if (isValidForm(Test64, Arg::ResCond, left.kind(), right.kind(), Arg::Tmp)) {
1893 return left.inst(right.inst(
1894 Test64, m_value, resCond,
1895 left.consume(*this), right.consume(*this), tmp(m_value)));
1896 }
1897 return Inst();
1898 }
1899 ASSERT_NOT_REACHED();
1900 },
1901 [this] (const Arg& doubleCond, ArgPromise& left, ArgPromise& right) -> Inst {
1902 if (isValidForm(CompareDouble, Arg::DoubleCond, left.kind(), right.kind(), Arg::Tmp)) {
1903 return left.inst(right.inst(
1904 CompareDouble, m_value, doubleCond,
1905 left.consume(*this), right.consume(*this), tmp(m_value)));
1906 }
1907 return Inst();
1908 },
1909 [this] (const Arg& doubleCond, ArgPromise& left, ArgPromise& right) -> Inst {
1910 if (isValidForm(CompareFloat, Arg::DoubleCond, left.kind(), right.kind(), Arg::Tmp)) {
1911 return left.inst(right.inst(
1912 CompareFloat, m_value, doubleCond,
1913 left.consume(*this), right.consume(*this), tmp(m_value)));
1914 }
1915 return Inst();
1916 },
1917 inverted);
1918 }
1919
1920 struct MoveConditionallyConfig {
1921 Air::Opcode moveConditionally32;
1922 Air::Opcode moveConditionally64;
1923 Air::Opcode moveConditionallyTest32;
1924 Air::Opcode moveConditionallyTest64;
1925 Air::Opcode moveConditionallyDouble;
1926 Air::Opcode moveConditionallyFloat;
1927 };
1928 Inst createSelect(const MoveConditionallyConfig& config)
1929 {
1930 using namespace Air;
1931 auto createSelectInstruction = [&] (Air::Opcode opcode, const Arg& condition, ArgPromise& left, ArgPromise& right) -> Inst {
1932 if (isValidForm(opcode, condition.kind(), left.kind(), right.kind(), Arg::Tmp, Arg::Tmp, Arg::Tmp)) {
1933 Tmp result = tmp(m_value);
1934 Tmp thenCase = tmp(m_value->child(1));
1935 Tmp elseCase = tmp(m_value->child(2));
1936 return left.inst(right.inst(
1937 opcode, m_value, condition,
1938 left.consume(*this), right.consume(*this), thenCase, elseCase, result));
1939 }
1940 if (isValidForm(opcode, condition.kind(), left.kind(), right.kind(), Arg::Tmp, Arg::Tmp)) {
1941 Tmp result = tmp(m_value);
1942 Tmp source = tmp(m_value->child(1));
1943 append(relaxedMoveForType(m_value->type()), tmp(m_value->child(2)), result);
1944 return left.inst(right.inst(
1945 opcode, m_value, condition,
1946 left.consume(*this), right.consume(*this), source, result));
1947 }
1948 return Inst();
1949 };
1950
1951 return createGenericCompare(
1952 m_value->child(0),
1953 [&] (Width width, const Arg& relCond, ArgPromise& left, ArgPromise& right) -> Inst {
1954 switch (width) {
1955 case Width8:
1956 // FIXME: Support these things.
1957 // https://bugs.webkit.org/show_bug.cgi?id=151504
1958 return Inst();
1959 case Width16:
1960 return Inst();
1961 case Width32:
1962 return createSelectInstruction(config.moveConditionally32, relCond, left, right);
1963 case Width64:
1964 return createSelectInstruction(config.moveConditionally64, relCond, left, right);
1965 }
1966 ASSERT_NOT_REACHED();
1967 },
1968 [&] (Width width, const Arg& resCond, ArgPromise& left, ArgPromise& right) -> Inst {
1969 switch (width) {
1970 case Width8:
1971 // FIXME: Support more things.
1972 // https://bugs.webkit.org/show_bug.cgi?id=151504
1973 return Inst();
1974 case Width16:
1975 return Inst();
1976 case Width32:
1977 return createSelectInstruction(config.moveConditionallyTest32, resCond, left, right);
1978 case Width64:
1979 return createSelectInstruction(config.moveConditionallyTest64, resCond, left, right);
1980 }
1981 ASSERT_NOT_REACHED();
1982 },
1983 [&] (Arg doubleCond, ArgPromise& left, ArgPromise& right) -> Inst {
1984 return createSelectInstruction(config.moveConditionallyDouble, doubleCond, left, right);
1985 },
1986 [&] (Arg doubleCond, ArgPromise& left, ArgPromise& right) -> Inst {
1987 return createSelectInstruction(config.moveConditionallyFloat, doubleCond, left, right);
1988 },
1989 false);
1990 }
1991
1992 bool tryAppendLea()
1993 {
1994 using namespace Air;
1995 Air::Opcode leaOpcode = tryOpcodeForType(Lea32, Lea64, m_value->type());
1996 if (!isValidForm(leaOpcode, Arg::Index, Arg::Tmp))
1997 return false;
1998
1999 // This lets us turn things like this:
2000 //
2001 // Add(Add(@x, Shl(@y, $2)), $100)
2002 //
2003 // Into this:
2004 //
2005 // lea 100(%rdi,%rsi,4), %rax
2006 //
2007 // We have a choice here between committing the internal bits of an index or sharing
2008 // them. There are solid arguments for both.
2009 //
2010 // Sharing: The word on the street is that the cost of a lea is one cycle no matter
2011 // what it does. Every experiment I've ever seen seems to confirm this. So, sharing
2012 // helps us in situations where Wasm input did this:
2013 //
2014 // x = a[i].x;
2015 // y = a[i].y;
2016 //
2017 // With sharing we would do:
2018 //
2019 // leal (%a,%i,4), %tmp
2020 // cmp (%size, %tmp)
2021 // ja _fail
2022 // movl (%base, %tmp), %x
2023 // leal 4(%a,%i,4), %tmp
2024 // cmp (%size, %tmp)
2025 // ja _fail
2026 // movl (%base, %tmp), %y
2027 //
2028 // In the absence of sharing, we may find ourselves needing separate registers for
2029 // the innards of the index. That's relatively unlikely to be a thing due to other
2030 // optimizations that we already have, but it could happen
2031 //
2032 // Committing: The worst case is that there is a complicated graph of additions and
2033 // shifts, where each value has multiple uses. In that case, it's better to compute
2034 // each one separately from the others since that way, each calculation will use a
2035 // relatively nearby tmp as its input. That seems uncommon, but in those cases,
2036 // committing is a clear winner: it would result in a simple interference graph
2037 // while sharing would result in a complex one. Interference sucks because it means
2038 // more time in IRC and it means worse code.
2039 //
2040 // It's not super clear if any of these corner cases would ever arise. Committing
2041 // has the benefit that it's easier to reason about, and protects a much darker
2042 // corner case (more interference).
2043
2044 // Here are the things we want to match:
2045 // Add(Add(@x, @y), $c)
2046 // Add(Shl(@x, $c), @y)
2047 // Add(@x, Shl(@y, $c))
2048 // Add(Add(@x, Shl(@y, $c)), $d)
2049 // Add(Add(Shl(@x, $c), @y), $d)
2050 //
2051 // Note that if you do Add(Shl(@x, $c), $d) then we will treat $d as a non-constant and
2052 // force it to materialize. You'll get something like this:
2053 //
2054 // movl $d, %tmp
2055 // leal (%tmp,%x,1<<c), %result
2056 //
2057 // Which is pretty close to optimal and has the nice effect of being able to handle large
2058 // constants gracefully.
2059
2060 Value* innerAdd = nullptr;
2061
2062 Value* value = m_value;
2063
2064 // We're going to consume Add(Add(_), $c). If we succeed at consuming it then we have these
2065 // patterns left (i.e. in the Add(_)):
2066 //
2067 // Add(Add(@x, @y), $c)
2068 // Add(Add(@x, Shl(@y, $c)), $d)
2069 // Add(Add(Shl(@x, $c), @y), $d)
2070 //
2071 // Otherwise we are looking at these patterns:
2072 //
2073 // Add(Shl(@x, $c), @y)
2074 // Add(@x, Shl(@y, $c))
2075 //
2076 // This means that the subsequent code only has to worry about three patterns:
2077 //
2078 // Add(Shl(@x, $c), @y)
2079 // Add(@x, Shl(@y, $c))
2080 // Add(@x, @y) (only if offset != 0)
2081 Value::OffsetType offset = 0;
2082 if (value->child(1)->isRepresentableAs<Value::OffsetType>()
2083 && canBeInternal(value->child(0))
2084 && value->child(0)->opcode() == Add) {
2085 innerAdd = value->child(0);
2086 offset = static_cast<Value::OffsetType>(value->child(1)->asInt());
2087 value = value->child(0);
2088 }
2089
2090 auto tryShl = [&] (Value* shl, Value* other) -> bool {
2091 Optional<unsigned> scale = scaleForShl(shl, offset);
2092 if (!scale)
2093 return false;
2094 if (!canBeInternal(shl))
2095 return false;
2096
2097 ASSERT(!m_locked.contains(shl->child(0)));
2098 ASSERT(!m_locked.contains(other));
2099
2100 append(leaOpcode, Arg::index(tmp(other), tmp(shl->child(0)), *scale, offset), tmp(m_value));
2101 commitInternal(innerAdd);
2102 commitInternal(shl);
2103 return true;
2104 };
2105
2106 if (tryShl(value->child(0), value->child(1)))
2107 return true;
2108 if (tryShl(value->child(1), value->child(0)))
2109 return true;
2110
2111 // The remaining pattern is just:
2112 // Add(@x, @y) (only if offset != 0)
2113 if (!offset)
2114 return false;
2115 ASSERT(!m_locked.contains(value->child(0)));
2116 ASSERT(!m_locked.contains(value->child(1)));
2117 append(leaOpcode, Arg::index(tmp(value->child(0)), tmp(value->child(1)), 1, offset), tmp(m_value));
2118 commitInternal(innerAdd);
2119 return true;
2120 }
2121
2122 void appendX86Div(B3::Opcode op)
2123 {
2124 using namespace Air;
2125 Air::Opcode convertToDoubleWord;
2126 Air::Opcode div;
2127 switch (m_value->type()) {
2128 case Int32:
2129 convertToDoubleWord = X86ConvertToDoubleWord32;
2130 div = X86Div32;
2131 break;
2132 case Int64:
2133 convertToDoubleWord = X86ConvertToQuadWord64;
2134 div = X86Div64;
2135 break;
2136 default:
2137 RELEASE_ASSERT_NOT_REACHED();
2138 return;
2139 }
2140
2141 ASSERT(op == Div || op == Mod);
2142 Tmp result = op == Div ? m_eax : m_edx;
2143
2144 append(Move, tmp(m_value->child(0)), m_eax);
2145 append(convertToDoubleWord, m_eax, m_edx);
2146 append(div, m_eax, m_edx, tmp(m_value->child(1)));
2147 append(Move, result, tmp(m_value));
2148 }
2149
2150 void appendX86UDiv(B3::Opcode op)
2151 {
2152 using namespace Air;
2153 Air::Opcode div = m_value->type() == Int32 ? X86UDiv32 : X86UDiv64;
2154
2155 ASSERT(op == UDiv || op == UMod);
2156 Tmp result = op == UDiv ? m_eax : m_edx;
2157
2158 append(Move, tmp(m_value->child(0)), m_eax);
2159 append(Xor64, m_edx, m_edx);
2160 append(div, m_eax, m_edx, tmp(m_value->child(1)));
2161 append(Move, result, tmp(m_value));
2162 }
2163
2164 Air::Opcode loadLinkOpcode(Width width, bool fence)
2165 {
2166 return fence ? OPCODE_FOR_WIDTH(LoadLinkAcq, width) : OPCODE_FOR_WIDTH(LoadLink, width);
2167 }
2168
2169 Air::Opcode storeCondOpcode(Width width, bool fence)
2170 {
2171 return fence ? OPCODE_FOR_WIDTH(StoreCondRel, width) : OPCODE_FOR_WIDTH(StoreCond, width);
2172 }
2173
2174 // This can emit code for the following patterns:
2175 // AtomicWeakCAS
2176 // BitXor(AtomicWeakCAS, 1)
2177 // AtomicStrongCAS
2178 // Equal(AtomicStrongCAS, expected)
2179 // NotEqual(AtomicStrongCAS, expected)
2180 // Branch(AtomicWeakCAS)
2181 // Branch(Equal(AtomicStrongCAS, expected))
2182 // Branch(NotEqual(AtomicStrongCAS, expected))
2183 //
2184 // It assumes that atomicValue points to the CAS, and m_value points to the instruction being
2185 // generated. It assumes that you've consumed everything that needs to be consumed.
2186 void appendCAS(Value* atomicValue, bool invert)
2187 {
2188 using namespace Air;
2189 AtomicValue* atomic = atomicValue->as<AtomicValue>();
2190 RELEASE_ASSERT(atomic);
2191
2192 bool isBranch = m_value->opcode() == Branch;
2193 bool isStrong = atomic->opcode() == AtomicStrongCAS;
2194 bool returnsOldValue = m_value->opcode() == AtomicStrongCAS;
2195 bool hasFence = atomic->hasFence();
2196
2197 Width width = atomic->accessWidth();
2198 Arg address = addr(atomic);
2199
2200 Tmp valueResultTmp;
2201 Tmp boolResultTmp;
2202 if (returnsOldValue) {
2203 RELEASE_ASSERT(!invert);
2204 valueResultTmp = tmp(m_value);
2205 boolResultTmp = m_code.newTmp(GP);
2206 } else if (isBranch) {
2207 valueResultTmp = m_code.newTmp(GP);
2208 boolResultTmp = m_code.newTmp(GP);
2209 } else {
2210 valueResultTmp = m_code.newTmp(GP);
2211 boolResultTmp = tmp(m_value);
2212 }
2213
2214 Tmp successBoolResultTmp;
2215 if (isStrong && !isBranch)
2216 successBoolResultTmp = m_code.newTmp(GP);
2217 else
2218 successBoolResultTmp = boolResultTmp;
2219
2220 Tmp expectedValueTmp = tmp(atomic->child(0));
2221 Tmp newValueTmp = tmp(atomic->child(1));
2222
2223 Air::FrequentedBlock success;
2224 Air::FrequentedBlock failure;
2225 if (isBranch) {
2226 success = m_blockToBlock[m_block]->successor(invert);
2227 failure = m_blockToBlock[m_block]->successor(!invert);
2228 }
2229
2230 if (isX86()) {
2231 append(relaxedMoveForType(atomic->accessType()), immOrTmp(atomic->child(0)), m_eax);
2232 if (returnsOldValue) {
2233 appendTrapping(OPCODE_FOR_WIDTH(AtomicStrongCAS, width), m_eax, newValueTmp, address);
2234 append(relaxedMoveForType(atomic->accessType()), m_eax, valueResultTmp);
2235 } else if (isBranch) {
2236 appendTrapping(OPCODE_FOR_WIDTH(BranchAtomicStrongCAS, width), Arg::statusCond(MacroAssembler::Success), m_eax, newValueTmp, address);
2237 m_blockToBlock[m_block]->setSuccessors(success, failure);
2238 } else
2239 appendTrapping(OPCODE_FOR_WIDTH(AtomicStrongCAS, width), Arg::statusCond(invert ? MacroAssembler::Failure : MacroAssembler::Success), m_eax, tmp(atomic->child(1)), address, boolResultTmp);
2240 return;
2241 }
2242
2243 RELEASE_ASSERT(isARM64());
2244 // We wish to emit:
2245 //
2246 // Block #reloop:
2247 // LoadLink
2248 // Branch NotEqual
2249 // Successors: Then:#fail, Else: #store
2250 // Block #store:
2251 // StoreCond
2252 // Xor $1, %result <--- only if !invert
2253 // Jump
2254 // Successors: #done
2255 // Block #fail:
2256 // Move $invert, %result
2257 // Jump
2258 // Successors: #done
2259 // Block #done:
2260
2261 Air::BasicBlock* reloopBlock = newBlock();
2262 Air::BasicBlock* storeBlock = newBlock();
2263 Air::BasicBlock* successBlock = nullptr;
2264 if (!isBranch && isStrong)
2265 successBlock = newBlock();
2266 Air::BasicBlock* failBlock = nullptr;
2267 if (!isBranch) {
2268 failBlock = newBlock();
2269 failure = failBlock;
2270 }
2271 Air::BasicBlock* strongFailBlock;
2272 if (isStrong && hasFence)
2273 strongFailBlock = newBlock();
2274 Air::FrequentedBlock comparisonFail = failure;
2275 Air::FrequentedBlock weakFail;
2276 if (isStrong) {
2277 if (hasFence)
2278 comparisonFail = strongFailBlock;
2279 weakFail = reloopBlock;
2280 } else
2281 weakFail = failure;
2282 Air::BasicBlock* beginBlock;
2283 Air::BasicBlock* doneBlock;
2284 splitBlock(beginBlock, doneBlock);
2285
2286 append(Air::Jump);
2287 beginBlock->setSuccessors(reloopBlock);
2288
2289 reloopBlock->append(trappingInst(m_value, loadLinkOpcode(width, atomic->hasFence()), m_value, address, valueResultTmp));
2290 reloopBlock->append(OPCODE_FOR_CANONICAL_WIDTH(Branch, width), m_value, Arg::relCond(MacroAssembler::NotEqual), valueResultTmp, expectedValueTmp);
2291 reloopBlock->setSuccessors(comparisonFail, storeBlock);
2292
2293 storeBlock->append(trappingInst(m_value, storeCondOpcode(width, atomic->hasFence()), m_value, newValueTmp, address, successBoolResultTmp));
2294 if (isBranch) {
2295 storeBlock->append(BranchTest32, m_value, Arg::resCond(MacroAssembler::Zero), boolResultTmp, boolResultTmp);
2296 storeBlock->setSuccessors(success, weakFail);
2297 doneBlock->successors().clear();
2298 RELEASE_ASSERT(!doneBlock->size());
2299 doneBlock->append(Air::Oops, m_value);
2300 } else {
2301 if (isStrong) {
2302 storeBlock->append(BranchTest32, m_value, Arg::resCond(MacroAssembler::Zero), successBoolResultTmp, successBoolResultTmp);
2303 storeBlock->setSuccessors(successBlock, reloopBlock);
2304
2305 successBlock->append(Move, m_value, Arg::imm(!invert), boolResultTmp);
2306 successBlock->append(Air::Jump, m_value);
2307 successBlock->setSuccessors(doneBlock);
2308 } else {
2309 if (!invert)
2310 storeBlock->append(Xor32, m_value, Arg::bitImm(1), boolResultTmp, boolResultTmp);
2311
2312 storeBlock->append(Air::Jump, m_value);
2313 storeBlock->setSuccessors(doneBlock);
2314 }
2315
2316 failBlock->append(Move, m_value, Arg::imm(invert), boolResultTmp);
2317 failBlock->append(Air::Jump, m_value);
2318 failBlock->setSuccessors(doneBlock);
2319 }
2320
2321 if (isStrong && hasFence) {
2322 Tmp tmp = m_code.newTmp(GP);
2323 strongFailBlock->append(trappingInst(m_value, storeCondOpcode(width, atomic->hasFence()), m_value, valueResultTmp, address, tmp));
2324 strongFailBlock->append(BranchTest32, m_value, Arg::resCond(MacroAssembler::Zero), tmp, tmp);
2325 strongFailBlock->setSuccessors(failure, reloopBlock);
2326 }
2327 }
2328
2329 bool appendVoidAtomic(Air::Opcode atomicOpcode)
2330 {
2331 if (m_useCounts.numUses(m_value))
2332 return false;
2333
2334 Arg address = addr(m_value);
2335
2336 if (isValidForm(atomicOpcode, Arg::Imm, address.kind()) && imm(m_value->child(0))) {
2337 append(atomicOpcode, imm(m_value->child(0)), address);
2338 return true;
2339 }
2340
2341 if (isValidForm(atomicOpcode, Arg::Tmp, address.kind())) {
2342 append(atomicOpcode, tmp(m_value->child(0)), address);
2343 return true;
2344 }
2345
2346 return false;
2347 }
2348
2349 void appendGeneralAtomic(Air::Opcode opcode, Commutativity commutativity = NotCommutative)
2350 {
2351 using namespace Air;
2352 AtomicValue* atomic = m_value->as<AtomicValue>();
2353
2354 Arg address = addr(m_value);
2355 Tmp oldValue = m_code.newTmp(GP);
2356 Tmp newValue = opcode == Air::Nop ? tmp(atomic->child(0)) : m_code.newTmp(GP);
2357
2358 // We need a CAS loop or a LL/SC loop. Using prepare/attempt jargon, we want:
2359 //
2360 // Block #reloop:
2361 // Prepare
2362 // opcode
2363 // Attempt
2364 // Successors: Then:#done, Else:#reloop
2365 // Block #done:
2366 // Move oldValue, result
2367
2368 append(relaxedMoveForType(atomic->type()), oldValue, tmp(atomic));
2369
2370 Air::BasicBlock* reloopBlock = newBlock();
2371 Air::BasicBlock* beginBlock;
2372 Air::BasicBlock* doneBlock;
2373 splitBlock(beginBlock, doneBlock);
2374
2375 append(Air::Jump);
2376 beginBlock->setSuccessors(reloopBlock);
2377
2378 Air::Opcode prepareOpcode;
2379 if (isX86()) {
2380 switch (atomic->accessWidth()) {
2381 case Width8:
2382 prepareOpcode = Load8SignedExtendTo32;
2383 break;
2384 case Width16:
2385 prepareOpcode = Load16SignedExtendTo32;
2386 break;
2387 case Width32:
2388 prepareOpcode = Move32;
2389 break;
2390 case Width64:
2391 prepareOpcode = Move;
2392 break;
2393 }
2394 } else {
2395 RELEASE_ASSERT(isARM64());
2396 prepareOpcode = loadLinkOpcode(atomic->accessWidth(), atomic->hasFence());
2397 }
2398 reloopBlock->append(trappingInst(m_value, prepareOpcode, m_value, address, oldValue));
2399
2400 if (opcode != Air::Nop) {
2401 // FIXME: If we ever have to write this again, we need to find a way to share the code with
2402 // appendBinOp.
2403 // https://bugs.webkit.org/show_bug.cgi?id=169249
2404 if (commutativity == Commutative && imm(atomic->child(0)) && isValidForm(opcode, Arg::Imm, Arg::Tmp, Arg::Tmp))
2405 reloopBlock->append(opcode, m_value, imm(atomic->child(0)), oldValue, newValue);
2406 else if (imm(atomic->child(0)) && isValidForm(opcode, Arg::Tmp, Arg::Imm, Arg::Tmp))
2407 reloopBlock->append(opcode, m_value, oldValue, imm(atomic->child(0)), newValue);
2408 else if (commutativity == Commutative && bitImm(atomic->child(0)) && isValidForm(opcode, Arg::BitImm, Arg::Tmp, Arg::Tmp))
2409 reloopBlock->append(opcode, m_value, bitImm(atomic->child(0)), oldValue, newValue);
2410 else if (isValidForm(opcode, Arg::Tmp, Arg::Tmp, Arg::Tmp))
2411 reloopBlock->append(opcode, m_value, oldValue, tmp(atomic->child(0)), newValue);
2412 else {
2413 reloopBlock->append(relaxedMoveForType(atomic->type()), m_value, oldValue, newValue);
2414 if (imm(atomic->child(0)) && isValidForm(opcode, Arg::Imm, Arg::Tmp))
2415 reloopBlock->append(opcode, m_value, imm(atomic->child(0)), newValue);
2416 else
2417 reloopBlock->append(opcode, m_value, tmp(atomic->child(0)), newValue);
2418 }
2419 }
2420
2421 if (isX86()) {
2422 Air::Opcode casOpcode = OPCODE_FOR_WIDTH(BranchAtomicStrongCAS, atomic->accessWidth());
2423 reloopBlock->append(relaxedMoveForType(atomic->type()), m_value, oldValue, m_eax);
2424 reloopBlock->append(trappingInst(m_value, casOpcode, m_value, Arg::statusCond(MacroAssembler::Success), m_eax, newValue, address));
2425 } else {
2426 RELEASE_ASSERT(isARM64());
2427 Tmp boolResult = m_code.newTmp(GP);
2428 reloopBlock->append(trappingInst(m_value, storeCondOpcode(atomic->accessWidth(), atomic->hasFence()), m_value, newValue, address, boolResult));
2429 reloopBlock->append(BranchTest32, m_value, Arg::resCond(MacroAssembler::Zero), boolResult, boolResult);
2430 }
2431 reloopBlock->setSuccessors(doneBlock, reloopBlock);
2432 }
2433
2434 void lower()
2435 {
2436 using namespace Air;
2437 switch (m_value->opcode()) {
2438 case B3::Nop: {
2439 // Yes, we will totally see Nop's because some phases will replaceWithNop() instead of
2440 // properly removing things.
2441 return;
2442 }
2443
2444 case Load: {
2445 MemoryValue* memory = m_value->as<MemoryValue>();
2446 Air::Kind kind = moveForType(memory->type());
2447 if (memory->hasFence()) {
2448 if (isX86())
2449 kind.effects = true;
2450 else {
2451 switch (memory->type()) {
2452 case Int32:
2453 kind = LoadAcq32;
2454 break;
2455 case Int64:
2456 kind = LoadAcq64;
2457 break;
2458 default:
2459 RELEASE_ASSERT_NOT_REACHED();
2460 break;
2461 }
2462 }
2463 }
2464 append(trappingInst(m_value, kind, m_value, addr(m_value), tmp(m_value)));
2465 return;
2466 }
2467
2468 case Load8S: {
2469 Air::Kind kind = Load8SignedExtendTo32;
2470 if (m_value->as<MemoryValue>()->hasFence()) {
2471 if (isX86())
2472 kind.effects = true;
2473 else
2474 kind = LoadAcq8SignedExtendTo32;
2475 }
2476 append(trappingInst(m_value, kind, m_value, addr(m_value), tmp(m_value)));
2477 return;
2478 }
2479
2480 case Load8Z: {
2481 Air::Kind kind = Load8;
2482 if (m_value->as<MemoryValue>()->hasFence()) {
2483 if (isX86())
2484 kind.effects = true;
2485 else
2486 kind = LoadAcq8;
2487 }
2488 append(trappingInst(m_value, kind, m_value, addr(m_value), tmp(m_value)));
2489 return;
2490 }
2491
2492 case Load16S: {
2493 Air::Kind kind = Load16SignedExtendTo32;
2494 if (m_value->as<MemoryValue>()->hasFence()) {
2495 if (isX86())
2496 kind.effects = true;
2497 else
2498 kind = LoadAcq16SignedExtendTo32;
2499 }
2500 append(trappingInst(m_value, kind, m_value, addr(m_value), tmp(m_value)));
2501 return;
2502 }
2503
2504 case Load16Z: {
2505 Air::Kind kind = Load16;
2506 if (m_value->as<MemoryValue>()->hasFence()) {
2507 if (isX86())
2508 kind.effects = true;
2509 else
2510 kind = LoadAcq16;
2511 }
2512 append(trappingInst(m_value, kind, m_value, addr(m_value), tmp(m_value)));
2513 return;
2514 }
2515
2516 case Add: {
2517 if (tryAppendLea())
2518 return;
2519
2520 Air::Opcode multiplyAddOpcode = tryOpcodeForType(MultiplyAdd32, MultiplyAdd64, m_value->type());
2521 if (isValidForm(multiplyAddOpcode, Arg::Tmp, Arg::Tmp, Arg::Tmp, Arg::Tmp)) {
2522 Value* left = m_value->child(0);
2523 Value* right = m_value->child(1);
2524 if (!imm(right) || m_valueToTmp[right]) {
2525 auto tryAppendMultiplyAdd = [&] (Value* left, Value* right) -> bool {
2526 if (left->opcode() != Mul || !canBeInternal(left))
2527 return false;
2528
2529 Value* multiplyLeft = left->child(0);
2530 Value* multiplyRight = left->child(1);
2531 if (canBeInternal(multiplyLeft) || canBeInternal(multiplyRight))
2532 return false;
2533
2534 append(multiplyAddOpcode, tmp(multiplyLeft), tmp(multiplyRight), tmp(right), tmp(m_value));
2535 commitInternal(left);
2536
2537 return true;
2538 };
2539
2540 if (tryAppendMultiplyAdd(left, right))
2541 return;
2542 if (tryAppendMultiplyAdd(right, left))
2543 return;
2544 }
2545 }
2546
2547 appendBinOp<Add32, Add64, AddDouble, AddFloat, Commutative>(
2548 m_value->child(0), m_value->child(1));
2549 return;
2550 }
2551
2552 case Sub: {
2553 Air::Opcode multiplySubOpcode = tryOpcodeForType(MultiplySub32, MultiplySub64, m_value->type());
2554 if (multiplySubOpcode != Air::Oops
2555 && isValidForm(multiplySubOpcode, Arg::Tmp, Arg::Tmp, Arg::Tmp, Arg::Tmp)) {
2556 Value* left = m_value->child(0);
2557 Value* right = m_value->child(1);
2558 if (!imm(right) || m_valueToTmp[right]) {
2559 auto tryAppendMultiplySub = [&] () -> bool {
2560 if (right->opcode() != Mul || !canBeInternal(right))
2561 return false;
2562
2563 Value* multiplyLeft = right->child(0);
2564 Value* multiplyRight = right->child(1);
2565 if (m_locked.contains(multiplyLeft) || m_locked.contains(multiplyRight))
2566 return false;
2567
2568 append(multiplySubOpcode, tmp(multiplyLeft), tmp(multiplyRight), tmp(left), tmp(m_value));
2569 commitInternal(right);
2570
2571 return true;
2572 };
2573
2574 if (tryAppendMultiplySub())
2575 return;
2576 }
2577 }
2578
2579 appendBinOp<Sub32, Sub64, SubDouble, SubFloat>(m_value->child(0), m_value->child(1));
2580 return;
2581 }
2582
2583 case Neg: {
2584 Air::Opcode multiplyNegOpcode = tryOpcodeForType(MultiplyNeg32, MultiplyNeg64, m_value->type());
2585 if (multiplyNegOpcode != Air::Oops
2586 && isValidForm(multiplyNegOpcode, Arg::Tmp, Arg::Tmp, Arg::Tmp)
2587 && m_value->child(0)->opcode() == Mul
2588 && canBeInternal(m_value->child(0))) {
2589 Value* multiplyOperation = m_value->child(0);
2590 Value* multiplyLeft = multiplyOperation->child(0);
2591 Value* multiplyRight = multiplyOperation->child(1);
2592 if (!m_locked.contains(multiplyLeft) && !m_locked.contains(multiplyRight)) {
2593 append(multiplyNegOpcode, tmp(multiplyLeft), tmp(multiplyRight), tmp(m_value));
2594 commitInternal(multiplyOperation);
2595 return;
2596 }
2597 }
2598
2599 appendUnOp<Neg32, Neg64, NegateDouble, NegateFloat>(m_value->child(0));
2600 return;
2601 }
2602
2603 case Mul: {
2604 appendBinOp<Mul32, Mul64, MulDouble, MulFloat, Commutative>(
2605 m_value->child(0), m_value->child(1));
2606 return;
2607 }
2608
2609 case Div: {
2610 if (m_value->isChill())
2611 RELEASE_ASSERT(isARM64());
2612 if (isInt(m_value->type()) && isX86()) {
2613 appendX86Div(Div);
2614 return;
2615 }
2616 ASSERT(!isX86() || isFloat(m_value->type()));
2617
2618 appendBinOp<Div32, Div64, DivDouble, DivFloat>(m_value->child(0), m_value->child(1));
2619 return;
2620 }
2621
2622 case UDiv: {
2623 if (isInt(m_value->type()) && isX86()) {
2624 appendX86UDiv(UDiv);
2625 return;
2626 }
2627
2628 ASSERT(!isX86() && !isFloat(m_value->type()));
2629
2630 appendBinOp<UDiv32, UDiv64, Air::Oops, Air::Oops>(m_value->child(0), m_value->child(1));
2631 return;
2632
2633 }
2634
2635 case Mod: {
2636 RELEASE_ASSERT(isX86());
2637 RELEASE_ASSERT(!m_value->isChill());
2638 appendX86Div(Mod);
2639 return;
2640 }
2641
2642 case UMod: {
2643 RELEASE_ASSERT(isX86());
2644 appendX86UDiv(UMod);
2645 return;
2646 }
2647
2648 case BitAnd: {
2649 if (m_value->child(1)->isInt(0xff)) {
2650 appendUnOp<ZeroExtend8To32, ZeroExtend8To32>(m_value->child(0));
2651 return;
2652 }
2653
2654 if (m_value->child(1)->isInt(0xffff)) {
2655 appendUnOp<ZeroExtend16To32, ZeroExtend16To32>(m_value->child(0));
2656 return;
2657 }
2658
2659 if (m_value->child(1)->isInt(0xffffffff)) {
2660 appendUnOp<Move32, Move32>(m_value->child(0));
2661 return;
2662 }
2663
2664 appendBinOp<And32, And64, AndDouble, AndFloat, Commutative>(
2665 m_value->child(0), m_value->child(1));
2666 return;
2667 }
2668
2669 case BitOr: {
2670 appendBinOp<Or32, Or64, OrDouble, OrFloat, Commutative>(
2671 m_value->child(0), m_value->child(1));
2672 return;
2673 }
2674
2675 case BitXor: {
2676 // FIXME: If canBeInternal(child), we should generate this using the comparison path.
2677 // https://bugs.webkit.org/show_bug.cgi?id=152367
2678
2679 if (m_value->child(1)->isInt(-1)) {
2680 appendUnOp<Not32, Not64>(m_value->child(0));
2681 return;
2682 }
2683
2684 // This pattern is super useful on both x86 and ARM64, since the inversion of the CAS result
2685 // can be done with zero cost on x86 (just flip the set from E to NE) and it's a progression
2686 // on ARM64 (since STX returns 0 on success, so ordinarily we have to flip it).
2687 if (m_value->child(1)->isInt(1)
2688 && m_value->child(0)->opcode() == AtomicWeakCAS
2689 && canBeInternal(m_value->child(0))) {
2690 commitInternal(m_value->child(0));
2691 appendCAS(m_value->child(0), true);
2692 return;
2693 }
2694
2695 appendBinOp<Xor32, Xor64, XorDouble, XorFloat, Commutative>(
2696 m_value->child(0), m_value->child(1));
2697 return;
2698 }
2699
2700 case Depend: {
2701 RELEASE_ASSERT(isARM64());
2702 appendUnOp<Depend32, Depend64>(m_value->child(0));
2703 return;
2704 }
2705
2706 case Shl: {
2707 if (m_value->child(1)->isInt32(1)) {
2708 appendBinOp<Add32, Add64, AddDouble, AddFloat, Commutative>(m_value->child(0), m_value->child(0));
2709 return;
2710 }
2711
2712 appendShift<Lshift32, Lshift64>(m_value->child(0), m_value->child(1));
2713 return;
2714 }
2715
2716 case SShr: {
2717 appendShift<Rshift32, Rshift64>(m_value->child(0), m_value->child(1));
2718 return;
2719 }
2720
2721 case ZShr: {
2722 appendShift<Urshift32, Urshift64>(m_value->child(0), m_value->child(1));
2723 return;
2724 }
2725
2726 case RotR: {
2727 appendShift<RotateRight32, RotateRight64>(m_value->child(0), m_value->child(1));
2728 return;
2729 }
2730
2731 case RotL: {
2732 appendShift<RotateLeft32, RotateLeft64>(m_value->child(0), m_value->child(1));
2733 return;
2734 }
2735
2736 case Clz: {
2737 appendUnOp<CountLeadingZeros32, CountLeadingZeros64>(m_value->child(0));
2738 return;
2739 }
2740
2741 case Abs: {
2742 RELEASE_ASSERT_WITH_MESSAGE(!isX86(), "Abs is not supported natively on x86. It must be replaced before generation.");
2743 appendUnOp<Air::Oops, Air::Oops, AbsDouble, AbsFloat>(m_value->child(0));
2744 return;
2745 }
2746
2747 case Ceil: {
2748 appendUnOp<Air::Oops, Air::Oops, CeilDouble, CeilFloat>(m_value->child(0));
2749 return;
2750 }
2751
2752 case Floor: {
2753 appendUnOp<Air::Oops, Air::Oops, FloorDouble, FloorFloat>(m_value->child(0));
2754 return;
2755 }
2756
2757 case Sqrt: {
2758 appendUnOp<Air::Oops, Air::Oops, SqrtDouble, SqrtFloat>(m_value->child(0));
2759 return;
2760 }
2761
2762 case BitwiseCast: {
2763 appendUnOp<Move32ToFloat, Move64ToDouble, MoveDoubleTo64, MoveFloatTo32>(m_value->child(0));
2764 return;
2765 }
2766
2767 case Store: {
2768 Value* valueToStore = m_value->child(0);
2769 if (canBeInternal(valueToStore)) {
2770 bool matched = false;
2771 switch (valueToStore->opcode()) {
2772 case Add:
2773 matched = tryAppendStoreBinOp<Add32, Add64, Commutative>(
2774 valueToStore->child(0), valueToStore->child(1));
2775 break;
2776 case Sub:
2777 if (valueToStore->child(0)->isInt(0)) {
2778 matched = tryAppendStoreUnOp<Neg32, Neg64>(valueToStore->child(1));
2779 break;
2780 }
2781 matched = tryAppendStoreBinOp<Sub32, Sub64>(
2782 valueToStore->child(0), valueToStore->child(1));
2783 break;
2784 case BitAnd:
2785 matched = tryAppendStoreBinOp<And32, And64, Commutative>(
2786 valueToStore->child(0), valueToStore->child(1));
2787 break;
2788 case BitXor:
2789 if (valueToStore->child(1)->isInt(-1)) {
2790 matched = tryAppendStoreUnOp<Not32, Not64>(valueToStore->child(0));
2791 break;
2792 }
2793 matched = tryAppendStoreBinOp<Xor32, Xor64, Commutative>(
2794 valueToStore->child(0), valueToStore->child(1));
2795 break;
2796 default:
2797 break;
2798 }
2799 if (matched) {
2800 commitInternal(valueToStore);
2801 return;
2802 }
2803 }
2804
2805 appendStore(m_value, addr(m_value));
2806 return;
2807 }
2808
2809 case B3::Store8: {
2810 Value* valueToStore = m_value->child(0);
2811 if (canBeInternal(valueToStore)) {
2812 bool matched = false;
2813 switch (valueToStore->opcode()) {
2814 case Add:
2815 matched = tryAppendStoreBinOp<Add8, Air::Oops, Commutative>(
2816 valueToStore->child(0), valueToStore->child(1));
2817 break;
2818 default:
2819 break;
2820 }
2821 if (matched) {
2822 commitInternal(valueToStore);
2823 return;
2824 }
2825 }
2826 appendStore(m_value, addr(m_value));
2827 return;
2828 }
2829
2830 case B3::Store16: {
2831 Value* valueToStore = m_value->child(0);
2832 if (canBeInternal(valueToStore)) {
2833 bool matched = false;
2834 switch (valueToStore->opcode()) {
2835 case Add:
2836 matched = tryAppendStoreBinOp<Add16, Air::Oops, Commutative>(
2837 valueToStore->child(0), valueToStore->child(1));
2838 break;
2839 default:
2840 break;
2841 }
2842 if (matched) {
2843 commitInternal(valueToStore);
2844 return;
2845 }
2846 }
2847 appendStore(m_value, addr(m_value));
2848 return;
2849 }
2850
2851 case WasmAddress: {
2852 WasmAddressValue* address = m_value->as<WasmAddressValue>();
2853
2854 append(Add64, Arg(address->pinnedGPR()), tmp(m_value->child(0)), tmp(address));
2855 return;
2856 }
2857
2858 case Fence: {
2859 FenceValue* fence = m_value->as<FenceValue>();
2860 if (!fence->write && !fence->read)
2861 return;
2862 if (!fence->write) {
2863 // A fence that reads but does not write is for protecting motion of stores.
2864 append(StoreFence);
2865 return;
2866 }
2867 if (!fence->read) {
2868 // A fence that writes but does not read is for protecting motion of loads.
2869 append(LoadFence);
2870 return;
2871 }
2872 append(MemoryFence);
2873 return;
2874 }
2875
2876 case Trunc: {
2877 ASSERT(tmp(m_value->child(0)) == tmp(m_value));
2878 return;
2879 }
2880
2881 case SExt8: {
2882 appendUnOp<SignExtend8To32, Air::Oops>(m_value->child(0));
2883 return;
2884 }
2885
2886 case SExt16: {
2887 appendUnOp<SignExtend16To32, Air::Oops>(m_value->child(0));
2888 return;
2889 }
2890
2891 case ZExt32: {
2892 appendUnOp<Move32, Air::Oops>(m_value->child(0));
2893 return;
2894 }
2895
2896 case SExt32: {
2897 // FIXME: We should have support for movsbq/movswq
2898 // https://bugs.webkit.org/show_bug.cgi?id=152232
2899
2900 appendUnOp<SignExtend32ToPtr, Air::Oops>(m_value->child(0));
2901 return;
2902 }
2903
2904 case FloatToDouble: {
2905 appendUnOp<Air::Oops, Air::Oops, Air::Oops, ConvertFloatToDouble>(m_value->child(0));
2906 return;
2907 }
2908
2909 case DoubleToFloat: {
2910 appendUnOp<Air::Oops, Air::Oops, ConvertDoubleToFloat>(m_value->child(0));
2911 return;
2912 }
2913
2914 case ArgumentReg: {
2915 m_prologue.append(Inst(
2916 moveForType(m_value->type()), m_value,
2917 Tmp(m_value->as<ArgumentRegValue>()->argumentReg()),
2918 tmp(m_value)));
2919 return;
2920 }
2921
2922 case Const32:
2923 case Const64: {
2924 if (imm(m_value))
2925 append(Move, imm(m_value), tmp(m_value));
2926 else
2927 append(Move, Arg::bigImm(m_value->asInt()), tmp(m_value));
2928 return;
2929 }
2930
2931 case ConstDouble:
2932 case ConstFloat: {
2933 // We expect that the moveConstants() phase has run, and any doubles referenced from
2934 // stackmaps get fused.
2935 RELEASE_ASSERT(m_value->opcode() == ConstFloat || isIdentical(m_value->asDouble(), 0.0));
2936 RELEASE_ASSERT(m_value->opcode() == ConstDouble || isIdentical(m_value->asFloat(), 0.0f));
2937 append(MoveZeroToDouble, tmp(m_value));
2938 return;
2939 }
2940
2941 case FramePointer: {
2942 ASSERT(tmp(m_value) == Tmp(GPRInfo::callFrameRegister));
2943 return;
2944 }
2945
2946 case SlotBase: {
2947 append(
2948 pointerType() == Int64 ? Lea64 : Lea32,
2949 Arg::stack(m_stackToStack.get(m_value->as<SlotBaseValue>()->slot())),
2950 tmp(m_value));
2951 return;
2952 }
2953
2954 case Equal:
2955 case NotEqual: {
2956 // FIXME: Teach this to match patterns that arise from subwidth CAS. The CAS's result has to
2957 // be either zero- or sign-extended, and the value it's compared to should also be zero- or
2958 // sign-extended in a matching way. It's not super clear that this is very profitable.
2959 // https://bugs.webkit.org/show_bug.cgi?id=169250
2960 if (m_value->child(0)->opcode() == AtomicStrongCAS
2961 && m_value->child(0)->as<AtomicValue>()->isCanonicalWidth()
2962 && m_value->child(0)->child(0) == m_value->child(1)
2963 && canBeInternal(m_value->child(0))) {
2964 ASSERT(!m_locked.contains(m_value->child(0)->child(1)));
2965 ASSERT(!m_locked.contains(m_value->child(1)));
2966
2967 commitInternal(m_value->child(0));
2968 appendCAS(m_value->child(0), m_value->opcode() == NotEqual);
2969 return;
2970 }
2971
2972 m_insts.last().append(createCompare(m_value));
2973 return;
2974 }
2975
2976 case LessThan:
2977 case GreaterThan:
2978 case LessEqual:
2979 case GreaterEqual:
2980 case Above:
2981 case Below:
2982 case AboveEqual:
2983 case BelowEqual:
2984 case EqualOrUnordered: {
2985 m_insts.last().append(createCompare(m_value));
2986 return;
2987 }
2988
2989 case Select: {
2990 MoveConditionallyConfig config;
2991 if (isInt(m_value->type())) {
2992 config.moveConditionally32 = MoveConditionally32;
2993 config.moveConditionally64 = MoveConditionally64;
2994 config.moveConditionallyTest32 = MoveConditionallyTest32;
2995 config.moveConditionallyTest64 = MoveConditionallyTest64;
2996 config.moveConditionallyDouble = MoveConditionallyDouble;
2997 config.moveConditionallyFloat = MoveConditionallyFloat;
2998 } else {
2999 // FIXME: it's not obvious that these are particularly efficient.
3000 // https://bugs.webkit.org/show_bug.cgi?id=169251
3001 config.moveConditionally32 = MoveDoubleConditionally32;
3002 config.moveConditionally64 = MoveDoubleConditionally64;
3003 config.moveConditionallyTest32 = MoveDoubleConditionallyTest32;
3004 config.moveConditionallyTest64 = MoveDoubleConditionallyTest64;
3005 config.moveConditionallyDouble = MoveDoubleConditionallyDouble;
3006 config.moveConditionallyFloat = MoveDoubleConditionallyFloat;
3007 }
3008
3009 m_insts.last().append(createSelect(config));
3010 return;
3011 }
3012
3013 case IToD: {
3014 appendUnOp<ConvertInt32ToDouble, ConvertInt64ToDouble>(m_value->child(0));
3015 return;
3016 }
3017
3018 case IToF: {
3019 appendUnOp<ConvertInt32ToFloat, ConvertInt64ToFloat>(m_value->child(0));
3020 return;
3021 }
3022
3023 case B3::CCall: {
3024 CCallValue* cCall = m_value->as<CCallValue>();
3025
3026 Inst inst(m_isRare ? Air::ColdCCall : Air::CCall, cCall);
3027
3028 // We have a ton of flexibility regarding the callee argument, but currently, we don't
3029 // use it yet. It gets weird for reasons:
3030 // 1) We probably will never take advantage of this. We don't have C calls to locations
3031 // loaded from addresses. We have JS calls like that, but those use Patchpoints.
3032 // 2) On X86_64 we still don't support call with BaseIndex.
3033 // 3) On non-X86, we don't natively support any kind of loading from address.
3034 // 4) We don't have an isValidForm() for the CCallSpecial so we have no smart way to
3035 // decide.
3036 // FIXME: https://bugs.webkit.org/show_bug.cgi?id=151052
3037 inst.args.append(tmp(cCall->child(0)));
3038
3039 if (cCall->type() != Void)
3040 inst.args.append(tmp(cCall));
3041
3042 for (unsigned i = 1; i < cCall->numChildren(); ++i)
3043 inst.args.append(immOrTmp(cCall->child(i)));
3044
3045 m_insts.last().append(WTFMove(inst));
3046 return;
3047 }
3048
3049 case Patchpoint: {
3050 PatchpointValue* patchpointValue = m_value->as<PatchpointValue>();
3051 ensureSpecial(m_patchpointSpecial);
3052
3053 Inst inst(Patch, patchpointValue, Arg::special(m_patchpointSpecial));
3054
3055 Vector<Inst> after;
3056 if (patchpointValue->type() != Void) {
3057 switch (patchpointValue->resultConstraint.kind()) {
3058 case ValueRep::WarmAny:
3059 case ValueRep::ColdAny:
3060 case ValueRep::LateColdAny:
3061 case ValueRep::SomeRegister:
3062 case ValueRep::SomeEarlyRegister:
3063 inst.args.append(tmp(patchpointValue));
3064 break;
3065 case ValueRep::Register: {
3066 Tmp reg = Tmp(patchpointValue->resultConstraint.reg());
3067 inst.args.append(reg);
3068 after.append(Inst(
3069 relaxedMoveForType(patchpointValue->type()), m_value, reg, tmp(patchpointValue)));
3070 break;
3071 }
3072 case ValueRep::StackArgument: {
3073 Arg arg = Arg::callArg(patchpointValue->resultConstraint.offsetFromSP());
3074 inst.args.append(arg);
3075 after.append(Inst(
3076 moveForType(patchpointValue->type()), m_value, arg, tmp(patchpointValue)));
3077 break;
3078 }
3079 default:
3080 RELEASE_ASSERT_NOT_REACHED();
3081 break;
3082 }
3083 }
3084
3085 fillStackmap(inst, patchpointValue, 0);
3086
3087 if (patchpointValue->resultConstraint.isReg())
3088 patchpointValue->lateClobbered().clear(patchpointValue->resultConstraint.reg());
3089
3090 for (unsigned i = patchpointValue->numGPScratchRegisters; i--;)
3091 inst.args.append(m_code.newTmp(GP));
3092 for (unsigned i = patchpointValue->numFPScratchRegisters; i--;)
3093 inst.args.append(m_code.newTmp(FP));
3094
3095 m_insts.last().append(WTFMove(inst));
3096 m_insts.last().appendVector(after);
3097 return;
3098 }
3099
3100 case CheckAdd:
3101 case CheckSub:
3102 case CheckMul: {
3103 CheckValue* checkValue = m_value->as<CheckValue>();
3104
3105 Value* left = checkValue->child(0);
3106 Value* right = checkValue->child(1);
3107
3108 Tmp result = tmp(m_value);
3109
3110 // Handle checked negation.
3111 if (checkValue->opcode() == CheckSub && left->isInt(0)) {
3112 append(Move, tmp(right), result);
3113
3114 Air::Opcode opcode =
3115 opcodeForType(BranchNeg32, BranchNeg64, checkValue->type());
3116 CheckSpecial* special = ensureCheckSpecial(opcode, 2);
3117
3118 Inst inst(Patch, checkValue, Arg::special(special));
3119 inst.args.append(Arg::resCond(MacroAssembler::Overflow));
3120 inst.args.append(result);
3121
3122 fillStackmap(inst, checkValue, 2);
3123
3124 m_insts.last().append(WTFMove(inst));
3125 return;
3126 }
3127
3128 Air::Opcode opcode = Air::Oops;
3129 Commutativity commutativity = NotCommutative;
3130 StackmapSpecial::RoleMode stackmapRole = StackmapSpecial::SameAsRep;
3131 switch (m_value->opcode()) {
3132 case CheckAdd:
3133 opcode = opcodeForType(BranchAdd32, BranchAdd64, m_value->type());
3134 stackmapRole = StackmapSpecial::ForceLateUseUnlessRecoverable;
3135 commutativity = Commutative;
3136 break;
3137 case CheckSub:
3138 opcode = opcodeForType(BranchSub32, BranchSub64, m_value->type());
3139 break;
3140 case CheckMul:
3141 opcode = opcodeForType(BranchMul32, BranchMul64, checkValue->type());
3142 stackmapRole = StackmapSpecial::ForceLateUse;
3143 break;
3144 default:
3145 RELEASE_ASSERT_NOT_REACHED();
3146 break;
3147 }
3148
3149 // FIXME: It would be great to fuse Loads into these. We currently don't do it because the
3150 // rule for stackmaps is that all addresses are just stack addresses. Maybe we could relax
3151 // this rule here.
3152 // https://bugs.webkit.org/show_bug.cgi?id=151228
3153
3154 Vector<Arg, 2> sources;
3155 if (imm(right) && isValidForm(opcode, Arg::ResCond, Arg::Tmp, Arg::Imm, Arg::Tmp)) {
3156 sources.append(tmp(left));
3157 sources.append(imm(right));
3158 } else if (imm(right) && isValidForm(opcode, Arg::ResCond, Arg::Imm, Arg::Tmp)) {
3159 sources.append(imm(right));
3160 append(Move, tmp(left), result);
3161 } else if (isValidForm(opcode, Arg::ResCond, Arg::Tmp, Arg::Tmp, Arg::Tmp)) {
3162 sources.append(tmp(left));
3163 sources.append(tmp(right));
3164 } else if (isValidForm(opcode, Arg::ResCond, Arg::Tmp, Arg::Tmp)) {
3165 if (commutativity == Commutative && preferRightForResult(left, right)) {
3166 sources.append(tmp(left));
3167 append(Move, tmp(right), result);
3168 } else {
3169 sources.append(tmp(right));
3170 append(Move, tmp(left), result);
3171 }
3172 } else if (isValidForm(opcode, Arg::ResCond, Arg::Tmp, Arg::Tmp, Arg::Tmp, Arg::Tmp, Arg::Tmp)) {
3173 sources.append(tmp(left));
3174 sources.append(tmp(right));
3175 sources.append(m_code.newTmp(m_value->resultBank()));
3176 sources.append(m_code.newTmp(m_value->resultBank()));
3177 }
3178
3179 // There is a really hilarious case that arises when we do BranchAdd32(%x, %x). We won't emit
3180 // such code, but the coalescing in our register allocator also does copy propagation, so
3181 // although we emit:
3182 //
3183 // Move %tmp1, %tmp2
3184 // BranchAdd32 %tmp1, %tmp2
3185 //
3186 // The register allocator may turn this into:
3187 //
3188 // BranchAdd32 %rax, %rax
3189 //
3190 // Currently we handle this by ensuring that even this kind of addition can be undone. We can
3191 // undo it by using the carry flag. It's tempting to get rid of that code and just "fix" this
3192 // here by forcing LateUse on the stackmap. If we did that unconditionally, we'd lose a lot of
3193 // performance. So it's tempting to do it only if left == right. But that creates an awkward
3194 // constraint on Air: it means that Air would not be allowed to do any copy propagation.
3195 // Notice that the %rax,%rax situation happened after Air copy-propagated the Move we are
3196 // emitting. We know that copy-propagating over that Move causes add-to-self. But what if we
3197 // emit something like a Move - or even do other kinds of copy-propagation on tmp's -
3198 // somewhere else in this code. The add-to-self situation may only emerge after some other Air
3199 // optimizations remove other Move's or identity-like operations. That's why we don't use
3200 // LateUse here to take care of add-to-self.
3201
3202 CheckSpecial* special = ensureCheckSpecial(opcode, 2 + sources.size(), stackmapRole);
3203
3204 Inst inst(Patch, checkValue, Arg::special(special));
3205
3206 inst.args.append(Arg::resCond(MacroAssembler::Overflow));
3207
3208 inst.args.appendVector(sources);
3209 inst.args.append(result);
3210
3211 fillStackmap(inst, checkValue, 2);
3212
3213 m_insts.last().append(WTFMove(inst));
3214 return;
3215 }
3216
3217 case Check: {
3218 Inst branch = createBranch(m_value->child(0));
3219
3220 CheckSpecial* special = ensureCheckSpecial(branch);
3221
3222 CheckValue* checkValue = m_value->as<CheckValue>();
3223
3224 Inst inst(Patch, checkValue, Arg::special(special));
3225 inst.args.appendVector(branch.args);
3226
3227 fillStackmap(inst, checkValue, 1);
3228
3229 m_insts.last().append(WTFMove(inst));
3230 return;
3231 }
3232
3233 case B3::WasmBoundsCheck: {
3234 WasmBoundsCheckValue* value = m_value->as<WasmBoundsCheckValue>();
3235
3236 Value* ptr = value->child(0);
3237 Tmp pointer = tmp(ptr);
3238
3239 Arg ptrPlusImm = m_code.newTmp(GP);
3240 append(Inst(Move32, value, pointer, ptrPlusImm));
3241 if (value->offset()) {
3242 if (imm(value->offset()))
3243 append(Add64, imm(value->offset()), ptrPlusImm);
3244 else {
3245 Arg bigImm = m_code.newTmp(GP);
3246 append(Move, Arg::bigImm(value->offset()), bigImm);
3247 append(Add64, bigImm, ptrPlusImm);
3248 }
3249 }
3250
3251 Arg limit;
3252 switch (value->boundsType()) {
3253 case WasmBoundsCheckValue::Type::Pinned:
3254 limit = Arg(value->bounds().pinnedSize);
3255 break;
3256
3257 case WasmBoundsCheckValue::Type::Maximum:
3258 limit = m_code.newTmp(GP);
3259 if (imm(value->bounds().maximum))
3260 append(Move, imm(value->bounds().maximum), limit);
3261 else
3262 append(Move, Arg::bigImm(value->bounds().maximum), limit);
3263 break;
3264 }
3265
3266 append(Inst(Air::WasmBoundsCheck, value, ptrPlusImm, limit));
3267 return;
3268 }
3269
3270 case Upsilon: {
3271 Value* value = m_value->child(0);
3272 append(
3273 relaxedMoveForType(value->type()), immOrTmp(value),
3274 m_phiToTmp[m_value->as<UpsilonValue>()->phi()]);
3275 return;
3276 }
3277
3278 case Phi: {
3279 // Snapshot the value of the Phi. It may change under us because you could do:
3280 // a = Phi()
3281 // Upsilon(@x, ^a)
3282 // @a => this should get the value of the Phi before the Upsilon, i.e. not @x.
3283
3284 append(relaxedMoveForType(m_value->type()), m_phiToTmp[m_value], tmp(m_value));
3285 return;
3286 }
3287
3288 case Set: {
3289 Value* value = m_value->child(0);
3290 append(
3291 relaxedMoveForType(value->type()), immOrTmp(value),
3292 m_variableToTmp.get(m_value->as<VariableValue>()->variable()));
3293 return;
3294 }
3295
3296 case Get: {
3297 append(
3298 relaxedMoveForType(m_value->type()),
3299 m_variableToTmp.get(m_value->as<VariableValue>()->variable()), tmp(m_value));
3300 return;
3301 }
3302
3303 case Branch: {
3304 if (canBeInternal(m_value->child(0))) {
3305 Value* branchChild = m_value->child(0);
3306 switch (branchChild->opcode()) {
3307 case AtomicWeakCAS:
3308 commitInternal(branchChild);
3309 appendCAS(branchChild, false);
3310 return;
3311
3312 case AtomicStrongCAS:
3313 // A branch is a comparison to zero.
3314 // FIXME: Teach this to match patterns that arise from subwidth CAS.
3315 // https://bugs.webkit.org/show_bug.cgi?id=169250
3316 if (branchChild->child(0)->isInt(0)
3317 && branchChild->as<AtomicValue>()->isCanonicalWidth()) {
3318 commitInternal(branchChild);
3319 appendCAS(branchChild, true);
3320 return;
3321 }
3322 break;
3323
3324 case Equal:
3325 case NotEqual:
3326 // FIXME: Teach this to match patterns that arise from subwidth CAS.
3327 // https://bugs.webkit.org/show_bug.cgi?id=169250
3328 if (branchChild->child(0)->opcode() == AtomicStrongCAS
3329 && branchChild->child(0)->as<AtomicValue>()->isCanonicalWidth()
3330 && canBeInternal(branchChild->child(0))
3331 && branchChild->child(0)->child(0) == branchChild->child(1)) {
3332 commitInternal(branchChild);
3333 commitInternal(branchChild->child(0));
3334 appendCAS(branchChild->child(0), branchChild->opcode() == NotEqual);
3335 return;
3336 }
3337 break;
3338
3339 default:
3340 break;
3341 }
3342 }
3343
3344 m_insts.last().append(createBranch(m_value->child(0)));
3345 return;
3346 }
3347
3348 case B3::Jump: {
3349 append(Air::Jump);
3350 return;
3351 }
3352
3353 case Identity:
3354 case Opaque: {
3355 ASSERT(tmp(m_value->child(0)) == tmp(m_value));
3356 return;
3357 }
3358
3359 case Return: {
3360 if (!m_value->numChildren()) {
3361 append(RetVoid);
3362 return;
3363 }
3364 Value* value = m_value->child(0);
3365 Tmp returnValueGPR = Tmp(GPRInfo::returnValueGPR);
3366 Tmp returnValueFPR = Tmp(FPRInfo::returnValueFPR);
3367 switch (value->type()) {
3368 case Void:
3369 // It's impossible for a void value to be used as a child. We use RetVoid
3370 // for void returns.
3371 RELEASE_ASSERT_NOT_REACHED();
3372 break;
3373 case Int32:
3374 append(Move, immOrTmp(value), returnValueGPR);
3375 append(Ret32, returnValueGPR);
3376 break;
3377 case Int64:
3378 append(Move, immOrTmp(value), returnValueGPR);
3379 append(Ret64, returnValueGPR);
3380 break;
3381 case Float:
3382 append(MoveFloat, tmp(value), returnValueFPR);
3383 append(RetFloat, returnValueFPR);
3384 break;
3385 case Double:
3386 append(MoveDouble, tmp(value), returnValueFPR);
3387 append(RetDouble, returnValueFPR);
3388 break;
3389 }
3390 return;
3391 }
3392
3393 case B3::Oops: {
3394 append(Air::Oops);
3395 return;
3396 }
3397
3398 case B3::EntrySwitch: {
3399 append(Air::EntrySwitch);
3400 return;
3401 }
3402
3403 case AtomicWeakCAS:
3404 case AtomicStrongCAS: {
3405 appendCAS(m_value, false);
3406 return;
3407 }
3408
3409 case AtomicXchgAdd: {
3410 AtomicValue* atomic = m_value->as<AtomicValue>();
3411 if (appendVoidAtomic(OPCODE_FOR_WIDTH(AtomicAdd, atomic->accessWidth())))
3412 return;
3413
3414 Arg address = addr(atomic);
3415 Air::Opcode opcode = OPCODE_FOR_WIDTH(AtomicXchgAdd, atomic->accessWidth());
3416 if (isValidForm(opcode, Arg::Tmp, address.kind())) {
3417 append(relaxedMoveForType(atomic->type()), tmp(atomic->child(0)), tmp(atomic));
3418 append(opcode, tmp(atomic), address);
3419 return;
3420 }
3421
3422 appendGeneralAtomic(OPCODE_FOR_CANONICAL_WIDTH(Add, atomic->accessWidth()), Commutative);
3423 return;
3424 }
3425
3426 case AtomicXchgSub: {
3427 AtomicValue* atomic = m_value->as<AtomicValue>();
3428 if (appendVoidAtomic(OPCODE_FOR_WIDTH(AtomicSub, atomic->accessWidth())))
3429 return;
3430
3431 appendGeneralAtomic(OPCODE_FOR_CANONICAL_WIDTH(Sub, atomic->accessWidth()));
3432 return;
3433 }
3434
3435 case AtomicXchgAnd: {
3436 AtomicValue* atomic = m_value->as<AtomicValue>();
3437 if (appendVoidAtomic(OPCODE_FOR_WIDTH(AtomicAnd, atomic->accessWidth())))
3438 return;
3439
3440 appendGeneralAtomic(OPCODE_FOR_CANONICAL_WIDTH(And, atomic->accessWidth()), Commutative);
3441 return;
3442 }
3443
3444 case AtomicXchgOr: {
3445 AtomicValue* atomic = m_value->as<AtomicValue>();
3446 if (appendVoidAtomic(OPCODE_FOR_WIDTH(AtomicOr, atomic->accessWidth())))
3447 return;
3448
3449 appendGeneralAtomic(OPCODE_FOR_CANONICAL_WIDTH(Or, atomic->accessWidth()), Commutative);
3450 return;
3451 }
3452
3453 case AtomicXchgXor: {
3454 AtomicValue* atomic = m_value->as<AtomicValue>();
3455 if (appendVoidAtomic(OPCODE_FOR_WIDTH(AtomicXor, atomic->accessWidth())))
3456 return;
3457
3458 appendGeneralAtomic(OPCODE_FOR_CANONICAL_WIDTH(Xor, atomic->accessWidth()), Commutative);
3459 return;
3460 }
3461
3462 case AtomicXchg: {
3463 AtomicValue* atomic = m_value->as<AtomicValue>();
3464
3465 Arg address = addr(atomic);
3466 Air::Opcode opcode = OPCODE_FOR_WIDTH(AtomicXchg, atomic->accessWidth());
3467 if (isValidForm(opcode, Arg::Tmp, address.kind())) {
3468 append(relaxedMoveForType(atomic->type()), tmp(atomic->child(0)), tmp(atomic));
3469 append(opcode, tmp(atomic), address);
3470 return;
3471 }
3472
3473 appendGeneralAtomic(Air::Nop);
3474 return;
3475 }
3476
3477 default:
3478 break;
3479 }
3480
3481 dataLog("FATAL: could not lower ", deepDump(m_procedure, m_value), "\n");
3482 RELEASE_ASSERT_NOT_REACHED();
3483 }
3484
3485 IndexSet<Value*> m_locked; // These are values that will have no Tmp in Air.
3486 IndexMap<Value*, Tmp> m_valueToTmp; // These are values that must have a Tmp in Air. We say that a Value* with a non-null Tmp is "pinned".
3487 IndexMap<Value*, Tmp> m_phiToTmp; // Each Phi gets its own Tmp.
3488 IndexMap<B3::BasicBlock*, Air::BasicBlock*> m_blockToBlock;
3489 HashMap<B3::StackSlot*, Air::StackSlot*> m_stackToStack;
3490 HashMap<Variable*, Tmp> m_variableToTmp;
3491
3492 UseCounts m_useCounts;
3493 PhiChildren m_phiChildren;
3494 BlockWorklist m_fastWorklist;
3495 Dominators& m_dominators;
3496
3497 Vector<Vector<Inst, 4>> m_insts;
3498 Vector<Inst> m_prologue;
3499
3500 B3::BasicBlock* m_block;
3501 bool m_isRare;
3502 unsigned m_index;
3503 Value* m_value;
3504
3505 PatchpointSpecial* m_patchpointSpecial { nullptr };
3506 HashMap<CheckSpecial::Key, CheckSpecial*> m_checkSpecials;
3507
3508 Procedure& m_procedure;
3509 Code& m_code;
3510
3511 Air::BlockInsertionSet m_blockInsertionSet;
3512
3513 Tmp m_eax;
3514 Tmp m_ecx;
3515 Tmp m_edx;
3516};
3517
3518} // anonymous namespace
3519
3520void lowerToAir(Procedure& procedure)
3521{
3522 PhaseScope phaseScope(procedure, "lowerToAir");
3523 LowerToAir lowerToAir(procedure);
3524 lowerToAir.run();
3525}
3526
3527} } // namespace JSC::B3
3528
3529#if ASSERT_DISABLED
3530IGNORE_RETURN_TYPE_WARNINGS_END
3531#endif
3532
3533#endif // ENABLE(B3_JIT)
3534