Make sure that the address matcher correctly handles Shl(x, 1)
[WebKit-https.git] / Source / JavaScriptCore / b3 / B3LowerToAir.cpp
1 /*
2  * Copyright (C) 2015 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 "AirCCallSpecial.h"
32 #include "AirCode.h"
33 #include "AirInsertionSet.h"
34 #include "AirInstInlines.h"
35 #include "AirStackSlot.h"
36 #include "B3ArgumentRegValue.h"
37 #include "B3BasicBlockInlines.h"
38 #include "B3CCallValue.h"
39 #include "B3CheckSpecial.h"
40 #include "B3Commutativity.h"
41 #include "B3IndexMap.h"
42 #include "B3IndexSet.h"
43 #include "B3MemoryValue.h"
44 #include "B3PatchpointSpecial.h"
45 #include "B3PatchpointValue.h"
46 #include "B3PhaseScope.h"
47 #include "B3Procedure.h"
48 #include "B3StackSlotValue.h"
49 #include "B3UpsilonValue.h"
50 #include "B3UseCounts.h"
51 #include "B3ValueInlines.h"
52 #include <wtf/ListDump.h>
53
54 namespace JSC { namespace B3 {
55
56 using namespace Air;
57
58 namespace {
59
60 const bool verbose = false;
61
62 class LowerToAir {
63 public:
64     LowerToAir(Procedure& procedure, Code& code)
65         : m_valueToTmp(procedure.values().size())
66         , m_blockToBlock(procedure.size())
67         , m_useCounts(procedure)
68         , m_procedure(procedure)
69         , m_code(code)
70     {
71     }
72
73     void run()
74     {
75         for (B3::BasicBlock* block : m_procedure)
76             m_blockToBlock[block] = m_code.addBlock(block->frequency());
77         for (Value* value : m_procedure.values()) {
78             if (StackSlotValue* stackSlotValue = value->as<StackSlotValue>())
79                 m_stackToStack.add(stackSlotValue, m_code.addStackSlot(stackSlotValue));
80         }
81
82         m_procedure.resetValueOwners(); // Used by crossesInterference().
83
84         // Lower defs before uses on a global level. This is a good heuristic to lock down a
85         // hoisted address expression before we duplicate it back into the loop.
86         for (B3::BasicBlock* block : m_procedure.blocksInPreOrder()) {
87             m_block = block;
88             // Reset some state.
89             m_insts.resize(0);
90
91             if (verbose)
92                 dataLog("Lowering Block ", *block, ":\n");
93             
94             // Process blocks in reverse order so we see uses before defs. That's what allows us
95             // to match patterns effectively.
96             for (unsigned i = block->size(); i--;) {
97                 m_index = i;
98                 m_value = block->at(i);
99                 if (m_locked.contains(m_value))
100                     continue;
101                 m_insts.append(Vector<Inst>());
102                 if (verbose)
103                     dataLog("Lowering ", deepDump(m_value), ":\n");
104                 lower();
105                 if (verbose) {
106                     for (Inst& inst : m_insts.last())
107                         dataLog("    ", inst, "\n");
108                 }
109             }
110
111             // Now append the instructions. m_insts contains them in reverse order, so we process
112             // it in reverse.
113             for (unsigned i = m_insts.size(); i--;) {
114                 for (Inst& inst : m_insts[i])
115                     m_blockToBlock[block]->appendInst(WTF::move(inst));
116             }
117
118             // Make sure that the successors are set up correctly.
119             ASSERT(block->successors().size() <= 2);
120             for (B3::BasicBlock* successor : block->successorBlocks())
121                 m_blockToBlock[block]->successors().append(m_blockToBlock[successor]);
122         }
123
124         Air::InsertionSet insertionSet(m_code);
125         for (Inst& inst : m_prologue)
126             insertionSet.insertInst(0, WTF::move(inst));
127         insertionSet.execute(m_code[0]);
128     }
129
130 private:
131     bool highBitsAreZero(Value* value)
132     {
133         switch (value->opcode()) {
134         case Const32:
135             // We will use a Move immediate instruction, which may sign extend.
136             return value->asInt32() >= 0;
137         case Trunc:
138             // Trunc is copy-propagated, so the value may have garbage in the high bits.
139             return false;
140         case CCall:
141             // Calls are allowed to have garbage in their high bits.
142             return false;
143         case Patchpoint:
144             // For now, we assume that patchpoints may return garbage in the high bits. This simplifies
145             // the interface. We may revisit for performance reasons later.
146             return false;
147         case Phi:
148             // FIXME: We could do this right.
149             // https://bugs.webkit.org/show_bug.cgi?id=150845
150             return false;
151         default:
152             // All other operations that return Int32 should lower to something that zero extends.
153             return value->type() == Int32;
154         }
155     }
156
157     // NOTE: This entire mechanism could be done over Air, if we felt that this would be fast enough.
158     // For now we're assuming that it's faster to do this here, since analyzing B3 is so cheap.
159     bool shouldCopyPropagate(Value* value)
160     {
161         switch (value->opcode()) {
162         case Trunc:
163         case Identity:
164             return true;
165         case ZExt32:
166             return highBitsAreZero(value->child(0));
167         default:
168             return false;
169         }
170     }
171
172     class ArgPromise {
173     public:
174         ArgPromise() { }
175
176         ArgPromise(const Arg& arg, Value* valueToLock = nullptr)
177             : m_arg(arg)
178             , m_value(valueToLock)
179         {
180         }
181
182         static ArgPromise tmp(Value* value)
183         {
184             ArgPromise result;
185             result.m_value = value;
186             return result;
187         }
188
189         explicit operator bool() const { return m_arg || m_value; }
190
191         Arg::Kind kind() const
192         {
193             if (!m_arg && m_value)
194                 return Arg::Tmp;
195             return m_arg.kind();
196         }
197
198         const Arg& peek() const
199         {
200             return m_arg;
201         }
202
203         Arg consume(LowerToAir& lower) const
204         {
205             if (!m_arg && m_value)
206                 return lower.tmp(m_value);
207             if (m_value)
208                 lower.commitInternal(m_value);
209             return m_arg;
210         }
211         
212     private:
213         // Three forms:
214         // Everything null: invalid.
215         // Arg non-null, value null: just use the arg, nothing special.
216         // Arg null, value non-null: it's a tmp, pin it when necessary.
217         // Arg non-null, value non-null: use the arg, lock the value.
218         Arg m_arg;
219         Value* m_value;
220     };
221
222     // Consider using tmpPromise() in cases where you aren't sure that you want to pin the value yet.
223     // Here are three canonical ways of using tmp() and tmpPromise():
224     //
225     // Idiom #1: You know that you want a tmp() and you know that it will be valid for the
226     // instruction you're emitting.
227     //
228     //     append(Foo, tmp(bar));
229     //
230     // Idiom #2: You don't know if you want to use a tmp() because you haven't determined if the
231     // instruction will accept it, so you query first. Note that the call to tmp() happens only after
232     // you are sure that you will use it.
233     //
234     //     if (isValidForm(Foo, Arg::Tmp))
235     //         append(Foo, tmp(bar))
236     //
237     // Idiom #3: Same as Idiom #2, but using tmpPromise. Notice that this calls consume() only after
238     // it's sure it will use the tmp. That's deliberate.
239     //
240     //     ArgPromise promise = tmpPromise(bar);
241     //     if (isValidForm(Foo, promise.kind()))
242     //         append(Foo, promise.consume(*this))
243     //
244     // In both idiom #2 and idiom #3, we don't pin the value to a temporary except when we actually
245     // emit the instruction. Both tmp() and tmpPromise().consume(*this) will pin it. Pinning means
246     // that we will henceforth require that the value of 'bar' is generated as a separate
247     // instruction. We don't want to pin the value to a temporary if we might change our minds, and
248     // pass an address operand representing 'bar' to Foo instead.
249     //
250     // Because tmp() pins, the following is not an idiom you should use:
251     //
252     //     Tmp tmp = this->tmp(bar);
253     //     if (isValidForm(Foo, tmp.kind()))
254     //         append(Foo, tmp);
255     //
256     // That's because if isValidForm() returns false, you will have already pinned the 'bar' to a
257     // temporary. You might later want to try to do something like loadPromise(), and that will fail.
258     // This arises in operations that have both a Addr,Tmp and Tmp,Addr forms. The following code
259     // seems right, but will actually fail to ever match the Tmp,Addr form because by then, the right
260     // value is already pinned.
261     //
262     //     auto tryThings = [this] (const Arg& left, const Arg& right) {
263     //         if (isValidForm(Foo, left.kind(), right.kind()))
264     //             return Inst(Foo, m_value, left, right);
265     //         return Inst();
266     //     };
267     //     if (Inst result = tryThings(loadAddr(left), tmp(right)))
268     //         return result;
269     //     if (Inst result = tryThings(tmp(left), loadAddr(right))) // this never succeeds.
270     //         return result;
271     //     return Inst(Foo, m_value, tmp(left), tmp(right));
272     //
273     // If you imagine that loadAddr(value) is just loadPromise(value).consume(*this), then this code
274     // will run correctly - it will generate OK code - but the second form is never matched.
275     // loadAddr(right) will never succeed because it will observe that 'right' is already pinned.
276     // Of course, it's exactly because of the risky nature of such code that we don't have a
277     // loadAddr() helper and require you to balance ArgPromise's in code like this. Such code will
278     // work fine if written as:
279     //
280     //     auto tryThings = [this] (const ArgPromise& left, const ArgPromise& right) {
281     //         if (isValidForm(Foo, left.kind(), right.kind()))
282     //             return Inst(Foo, m_value, left.consume(*this), right.consume(*this));
283     //         return Inst();
284     //     };
285     //     if (Inst result = tryThings(loadPromise(left), tmpPromise(right)))
286     //         return result;
287     //     if (Inst result = tryThings(tmpPromise(left), loadPromise(right)))
288     //         return result;
289     //     return Inst(Foo, m_value, tmp(left), tmp(right));
290     //
291     // Notice that we did use tmp in the fall-back case at the end, because by then, we know for sure
292     // that we want a tmp. But using tmpPromise in the tryThings() calls ensures that doing so
293     // doesn't prevent us from trying loadPromise on the same value.
294     Tmp tmp(Value* value)
295     {
296         Tmp& tmp = m_valueToTmp[value];
297         if (!tmp) {
298             while (shouldCopyPropagate(value))
299                 value = value->child(0);
300             Tmp& realTmp = m_valueToTmp[value];
301             if (!realTmp)
302                 realTmp = m_code.newTmp(Arg::typeForB3Type(value->type()));
303             tmp = realTmp;
304         }
305         return tmp;
306     }
307
308     ArgPromise tmpPromise(Value* value)
309     {
310         return ArgPromise::tmp(value);
311     }
312
313     bool canBeInternal(Value* value)
314     {
315         // If one of the internal things has already been computed, then we don't want to cause
316         // it to be recomputed again.
317         if (m_valueToTmp[value])
318             return false;
319         
320         // We require internals to have only one use - us.
321         if (m_useCounts[value] != 1)
322             return false;
323
324         return true;
325     }
326
327     // If you ask canBeInternal() and then construct something from that, and you commit to emitting
328     // that code, then you must commitInternal() on that value. This is tricky, and you only need to
329     // do it if you're pattern matching by hand rather than using the patterns language. Long story
330     // short, you should avoid this by using the pattern matcher to match patterns.
331     void commitInternal(Value* value)
332     {
333         m_locked.add(value);
334     }
335
336     bool crossesInterference(Value* value)
337     {
338         // If it's in a foreign block, then be conservative. We could handle this if we were
339         // willing to do heavier analysis. For example, if we had liveness, then we could label
340         // values as "crossing interference" if they interfere with anything that they are live
341         // across. But, it's not clear how useful this would be.
342         if (value->owner != m_value->owner)
343             return true;
344
345         Effects effects = value->effects();
346
347         for (unsigned i = m_index; i--;) {
348             Value* otherValue = m_block->at(i);
349             if (otherValue == value)
350                 return false;
351             if (effects.interferes(otherValue->effects()))
352                 return true;
353         }
354
355         ASSERT_NOT_REACHED();
356         return true;
357     }
358
359     // This turns the given operand into an address.
360     Arg effectiveAddr(Value* address)
361     {
362         // FIXME: Consider matching an address expression even if we've already assigned a
363         // Tmp to it. https://bugs.webkit.org/show_bug.cgi?id=150777
364         if (m_valueToTmp[address])
365             return Arg::addr(tmp(address));
366         
367         switch (address->opcode()) {
368         case Add: {
369             Value* left = address->child(0);
370             Value* right = address->child(1);
371
372             auto tryIndex = [&] (Value* index, Value* offset) -> Arg {
373                 if (index->opcode() != Shl)
374                     return Arg();
375                 if (m_locked.contains(index->child(0)) || m_locked.contains(offset))
376                     return Arg();
377                 if (!index->child(1)->hasInt32())
378                     return Arg();
379                 
380                 unsigned scale = 1 << (index->child(1)->asInt32() & 31);
381                 if (!Arg::isValidScale(scale))
382                     return Arg();
383
384                 return Arg::index(tmp(offset), tmp(index->child(0)), scale);
385             };
386
387             if (Arg result = tryIndex(left, right))
388                 return result;
389             if (Arg result = tryIndex(right, left))
390                 return result;
391
392             if (m_locked.contains(left) || m_locked.contains(right))
393                 return Arg::addr(tmp(address));
394             
395             return Arg::index(tmp(left), tmp(right));
396         }
397
398         case Shl: {
399             Value* left = address->child(0);
400
401             // We'll never see child(1)->isInt32(0), since that would have been reduced. If the shift
402             // amount is greater than 1, then there isn't really anything smart that we could do here.
403             // We avoid using baseless indexes because their encoding isn't particularly efficient.
404             if (m_locked.contains(left) || !address->child(1)->isInt32(1))
405                 return Arg::addr(tmp(address));
406
407             return Arg::index(tmp(left), tmp(left));
408         }
409
410         case FramePointer:
411             return Arg::addr(Tmp(GPRInfo::callFrameRegister));
412
413         case B3::StackSlot:
414             return Arg::stack(m_stackToStack.get(address->as<StackSlotValue>()));
415
416         default:
417             return Arg::addr(tmp(address));
418         }
419     }
420
421     // This gives you the address of the given Load or Store. If it's not a Load or Store, then
422     // it returns Arg().
423     Arg addr(Value* memoryValue)
424     {
425         MemoryValue* value = memoryValue->as<MemoryValue>();
426         if (!value)
427             return Arg();
428
429         Arg result = effectiveAddr(value->lastChild());
430         ASSERT(result);
431         
432         int32_t offset = memoryValue->as<MemoryValue>()->offset();
433         Arg offsetResult = result.withOffset(offset);
434         if (!offsetResult)
435             return Arg::addr(tmp(value->lastChild()), offset);
436         return offsetResult;
437     }
438
439     ArgPromise loadPromise(Value* loadValue, B3::Opcode loadOpcode)
440     {
441         if (loadValue->opcode() != loadOpcode)
442             return Arg();
443         if (!canBeInternal(loadValue))
444             return Arg();
445         if (crossesInterference(loadValue))
446             return Arg();
447         return ArgPromise(addr(loadValue), loadValue);
448     }
449
450     ArgPromise loadPromise(Value* loadValue)
451     {
452         return loadPromise(loadValue, Load);
453     }
454
455     Arg imm(Value* value)
456     {
457         if (value->hasInt() && value->representableAs<int32_t>())
458             return Arg::imm(value->asNumber<int32_t>());
459         return Arg();
460     }
461
462     Arg immOrTmp(Value* value)
463     {
464         if (Arg result = imm(value))
465             return result;
466         return tmp(value);
467     }
468
469     // By convention, we use Oops to mean "I don't know".
470     Air::Opcode tryOpcodeForType(
471         Air::Opcode opcode32, Air::Opcode opcode64, Air::Opcode opcodeDouble, Type type)
472     {
473         Air::Opcode opcode;
474         switch (type) {
475         case Int32:
476             opcode = opcode32;
477             break;
478         case Int64:
479             opcode = opcode64;
480             break;
481         case Double:
482             opcode = opcodeDouble;
483             break;
484         default:
485             opcode = Air::Oops;
486             break;
487         }
488
489         return opcode;
490     }
491
492     Air::Opcode opcodeForType(
493         Air::Opcode opcode32, Air::Opcode opcode64, Air::Opcode opcodeDouble, Type type)
494     {
495         Air::Opcode opcode = tryOpcodeForType(opcode32, opcode64, opcodeDouble, type);
496         RELEASE_ASSERT(opcode != Air::Oops);
497         return opcode;
498     }
499
500     template<Air::Opcode opcode32, Air::Opcode opcode64, Air::Opcode opcodeDouble>
501     void appendUnOp(Value* value)
502     {
503         Air::Opcode opcode = opcodeForType(opcode32, opcode64, opcodeDouble, value->type());
504         
505         Tmp result = tmp(m_value);
506
507         // Two operand forms like:
508         //     Op a, b
509         // mean something like:
510         //     b = Op a
511
512         ArgPromise addr = loadPromise(value);
513         if (isValidForm(opcode, addr.kind(), Arg::Tmp)) {
514             append(opcode, addr.consume(*this), result);
515             return;
516         }
517
518         if (isValidForm(opcode, Arg::Tmp, Arg::Tmp)) {
519             append(opcode, tmp(value), result);
520             return;
521         }
522
523         ASSERT(value->type() == m_value->type());
524         append(relaxedMoveForType(m_value->type()), tmp(value), result);
525         append(opcode, result);
526     }
527
528     template<
529         Air::Opcode opcode32, Air::Opcode opcode64, Air::Opcode opcodeDouble,
530         Commutativity commutativity = NotCommutative>
531     void appendBinOp(Value* left, Value* right)
532     {
533         Air::Opcode opcode = opcodeForType(opcode32, opcode64, opcodeDouble, left->type());
534         
535         Tmp result = tmp(m_value);
536         
537         // Three-operand forms like:
538         //     Op a, b, c
539         // mean something like:
540         //     c = a Op b
541
542         if (isValidForm(opcode, Arg::Imm, Arg::Tmp, Arg::Tmp)) {
543             if (commutativity == Commutative) {
544                 if (imm(right)) {
545                     append(opcode, imm(right), tmp(left), result);
546                     return;
547                 }
548             } else {
549                 // A non-commutative operation could have an immediate in left.
550                 if (imm(left)) {
551                     append(opcode, imm(left), tmp(right), result);
552                     return;
553                 }
554             }
555         }
556
557         if (imm(right) && isValidForm(opcode, Arg::Tmp, Arg::Imm, Arg::Tmp)) {
558             append(opcode, tmp(left), imm(right), result);
559             return;
560         }
561
562         // Note that no extant architecture has a three-operand form of binary operations that also
563         // load from memory. If such an abomination did exist, we would handle it somewhere around
564         // here.
565
566         // Two-operand forms like:
567         //     Op a, b
568         // mean something like:
569         //     b = b Op a
570
571         // At this point, we prefer versions of the operation that have a fused load or an immediate
572         // over three operand forms.
573         
574         if (commutativity == Commutative) {
575             ArgPromise leftAddr = loadPromise(left);
576             if (isValidForm(opcode, leftAddr.kind(), Arg::Tmp)) {
577                 append(relaxedMoveForType(m_value->type()), tmp(right), result);
578                 append(opcode, leftAddr.consume(*this), result);
579                 return;
580             }
581         }
582
583         ArgPromise rightAddr = loadPromise(right);
584         if (isValidForm(opcode, rightAddr.kind(), Arg::Tmp)) {
585             append(relaxedMoveForType(m_value->type()), tmp(left), result);
586             append(opcode, rightAddr.consume(*this), result);
587             return;
588         }
589
590         if (imm(right) && isValidForm(opcode, Arg::Imm, Arg::Tmp)) {
591             append(relaxedMoveForType(m_value->type()), tmp(left), result);
592             append(opcode, imm(right), result);
593             return;
594         }
595
596         if (isValidForm(opcode, Arg::Tmp, Arg::Tmp, Arg::Tmp)) {
597             append(opcode, tmp(left), tmp(right), result);
598             return;
599         }
600
601         append(relaxedMoveForType(m_value->type()), tmp(left), result);
602         append(opcode, tmp(right), result);
603     }
604
605     template<Air::Opcode opcode32, Air::Opcode opcode64>
606     void appendShift(Value* value, Value* amount)
607     {
608         Air::Opcode opcode = opcodeForType(opcode32, opcode64, Air::Oops, value->type());
609         
610         if (imm(amount)) {
611             append(Move, tmp(value), tmp(m_value));
612             append(opcode, imm(amount), tmp(m_value));
613             return;
614         }
615
616         append(Move, tmp(value), tmp(m_value));
617         append(Move, tmp(amount), Tmp(X86Registers::ecx));
618         append(opcode, Tmp(X86Registers::ecx), tmp(m_value));
619     }
620
621     template<Air::Opcode opcode32, Air::Opcode opcode64>
622     bool tryAppendStoreUnOp(Value* value)
623     {
624         Air::Opcode opcode = tryOpcodeForType(opcode32, opcode64, Air::Oops, value->type());
625         if (opcode == Air::Oops)
626             return false;
627         
628         Arg storeAddr = addr(m_value);
629         ASSERT(storeAddr);
630
631         ArgPromise loadPromise = this->loadPromise(value);
632         if (loadPromise.peek() != storeAddr)
633             return false;
634
635         if (!isValidForm(opcode, storeAddr.kind()))
636             return false;
637         
638         loadPromise.consume(*this);
639         append(opcode, storeAddr);
640         return true;
641     }
642
643     template<
644         Air::Opcode opcode32, Air::Opcode opcode64, Commutativity commutativity = NotCommutative>
645     bool tryAppendStoreBinOp(Value* left, Value* right)
646     {
647         Air::Opcode opcode = tryOpcodeForType(opcode32, opcode64, Air::Oops, left->type());
648         if (opcode == Air::Oops)
649             return false;
650         
651         Arg storeAddr = addr(m_value);
652         ASSERT(storeAddr);
653
654         ArgPromise loadPromise;
655         Value* otherValue = nullptr;
656         
657         loadPromise = this->loadPromise(left);
658         if (loadPromise.peek() == storeAddr)
659             otherValue = right;
660         else if (commutativity == Commutative) {
661             loadPromise = this->loadPromise(right);
662             if (loadPromise.peek() == storeAddr)
663                 otherValue = left;
664         }
665
666         if (!otherValue)
667             return false;
668
669         if (isValidForm(opcode, Arg::Imm, storeAddr.kind()) && imm(otherValue)) {
670             loadPromise.consume(*this);
671             append(opcode, imm(otherValue), storeAddr);
672             return true;
673         }
674
675         if (!isValidForm(opcode, Arg::Tmp, storeAddr.kind()))
676             return false;
677
678         loadPromise.consume(*this);
679         append(opcode, tmp(otherValue), storeAddr);
680         return true;
681     }
682
683     Inst createStore(Value* value, const Arg& dest)
684     {
685         Air::Opcode move = moveForType(value->type());
686
687         if (imm(value) && isValidForm(move, Arg::Imm, dest.kind()))
688             return Inst(move, m_value, imm(value), dest);
689
690         return Inst(move, m_value, tmp(value), dest);
691     }
692
693     void appendStore(Value* value, const Arg& dest)
694     {
695         m_insts.last().append(createStore(value, dest));
696     }
697
698     Air::Opcode moveForType(Type type)
699     {
700         switch (type) {
701         case Int32:
702             return Move32;
703         case Int64:
704             RELEASE_ASSERT(is64Bit());
705             return Move;
706         case Double:
707             return MoveDouble;
708         default:
709             RELEASE_ASSERT_NOT_REACHED();
710         }
711     }
712
713     Air::Opcode relaxedMoveForType(Type type)
714     {
715         switch (type) {
716         case Int32:
717         case Int64:
718             return Move;
719         case Double:
720             return MoveDouble;
721         default:
722             RELEASE_ASSERT_NOT_REACHED();
723         }
724     }
725
726     template<typename... Arguments>
727     void append(Air::Opcode opcode, Arguments&&... arguments)
728     {
729         m_insts.last().append(Inst(opcode, m_value, std::forward<Arguments>(arguments)...));
730     }
731
732     template<typename T, typename... Arguments>
733     T* ensureSpecial(T*& field, Arguments&&... arguments)
734     {
735         if (!field) {
736             field = static_cast<T*>(
737                 m_code.addSpecial(std::make_unique<T>(std::forward<Arguments>(arguments)...)));
738         }
739         return field;
740     }
741
742     template<typename... Arguments>
743     CheckSpecial* ensureCheckSpecial(Arguments&&... arguments)
744     {
745         CheckSpecial::Key key(std::forward<Arguments>(arguments)...);
746         auto result = m_checkSpecials.add(key, nullptr);
747         return ensureSpecial(result.iterator->value, key);
748     }
749
750     void fillStackmap(Inst& inst, StackmapValue* stackmap, unsigned numSkipped)
751     {
752         for (unsigned i = numSkipped; i < stackmap->numChildren(); ++i) {
753             ConstrainedValue value = stackmap->constrainedChild(i);
754
755             Arg arg;
756             switch (value.rep().kind()) {
757             case ValueRep::Any:
758                 if (imm(value.value()))
759                     arg = imm(value.value());
760                 else if (value.value()->hasInt64())
761                     arg = Arg::imm64(value.value()->asInt64());
762                 else if (value.value()->hasDouble() && canBeInternal(value.value())) {
763                     commitInternal(value.value());
764                     arg = Arg::imm64(bitwise_cast<int64_t>(value.value()->asDouble()));
765                 } else
766                     arg = tmp(value.value());
767                 break;
768             case ValueRep::SomeRegister:
769                 arg = tmp(value.value());
770                 break;
771             case ValueRep::Register:
772                 arg = Tmp(value.rep().reg());
773                 append(Move, immOrTmp(value.value()), arg);
774                 break;
775             case ValueRep::StackArgument:
776                 arg = Arg::callArg(value.rep().offsetFromSP());
777                 appendStore(value.value(), arg);
778                 break;
779             default:
780                 RELEASE_ASSERT_NOT_REACHED();
781                 break;
782             }
783             inst.args.append(arg);
784         }
785     }
786     
787     // Create an Inst to do the comparison specified by the given value.
788     template<typename CompareFunctor, typename TestFunctor, typename CompareDoubleFunctor>
789     Inst createGenericCompare(
790         Value* value,
791         const CompareFunctor& compare, // Signature: (Arg::Width, Arg relCond, Arg, Arg) -> Inst
792         const TestFunctor& test, // Signature: (Arg::Width, Arg resCond, Arg, Arg) -> Inst
793         const CompareDoubleFunctor& compareDouble, // Signature: (Arg doubleCond, Arg, Arg) -> Inst
794         bool inverted = false)
795     {
796         // Chew through any negations. It's not strictly necessary for this to be a loop, but we like
797         // to follow the rule that the instruction selector reduces strength whenever it doesn't
798         // require making things more complicated.
799         for (;;) {
800             if (!canBeInternal(value) && value != m_value)
801                 break;
802             bool shouldInvert =
803                 (value->opcode() == BitXor && value->child(1)->isInt(1) && value->child(0)->returnsBool())
804                 || (value->opcode() == Equal && value->child(1)->isInt(0));
805             if (!shouldInvert)
806                 break;
807             value = value->child(0);
808             inverted = !inverted;
809             commitInternal(value);
810         }
811
812         auto createRelCond = [&] (
813             MacroAssembler::RelationalCondition relationalCondition,
814             MacroAssembler::DoubleCondition doubleCondition) {
815             Arg relCond = Arg::relCond(relationalCondition).inverted(inverted);
816             Arg doubleCond = Arg::doubleCond(doubleCondition).inverted(inverted);
817             Value* left = value->child(0);
818             Value* right = value->child(1);
819
820             if (isInt(value->child(0)->type())) {
821                 // FIXME: We wouldn't have to worry about leftImm if we canonicalized integer
822                 // comparisons.
823                 // https://bugs.webkit.org/show_bug.cgi?id=150958
824                 
825                 Arg leftImm = imm(left);
826                 Arg rightImm = imm(right);
827
828                 auto tryCompare = [&] (
829                     Arg::Width width, const ArgPromise& left, const ArgPromise& right) -> Inst {
830                     if (Inst result = compare(width, relCond, left, right))
831                         return result;
832                     if (Inst result = compare(width, relCond.flipped(), right, left))
833                         return result;
834                     return Inst();
835                 };
836
837                 auto tryCompareLoadImm = [&] (
838                     Arg::Width width, B3::Opcode loadOpcode, Arg::Signedness signedness) -> Inst {
839                     if (rightImm && rightImm.isRepresentableAs(width, signedness)) {
840                         if (Inst result = tryCompare(width, loadPromise(left, loadOpcode), rightImm)) {
841                             commitInternal(left);
842                             return result;
843                         }
844                     }
845                     if (leftImm && leftImm.isRepresentableAs(width, signedness)) {
846                         if (Inst result = tryCompare(width, leftImm, loadPromise(right, loadOpcode))) {
847                             commitInternal(right);
848                             return result;
849                         }
850                     }
851                     return Inst();
852                 };
853
854                 // First handle compares that involve fewer bits than B3's type system supports.
855                 // This is pretty important. For example, we want this to be a single instruction:
856                 //
857                 //     @1 = Load8S(...)
858                 //     @2 = Const32(...)
859                 //     @3 = LessThan(@1, @2)
860                 //     Branch(@3)
861                 
862                 if (relCond.isSignedCond()) {
863                     if (Inst result = tryCompareLoadImm(Arg::Width8, Load8S, Arg::Signed))
864                         return result;
865                 }
866                 
867                 if (relCond.isUnsignedCond()) {
868                     if (Inst result = tryCompareLoadImm(Arg::Width8, Load8Z, Arg::Unsigned))
869                         return result;
870                 }
871
872                 if (relCond.isSignedCond()) {
873                     if (Inst result = tryCompareLoadImm(Arg::Width16, Load16S, Arg::Signed))
874                         return result;
875                 }
876                 
877                 if (relCond.isUnsignedCond()) {
878                     if (Inst result = tryCompareLoadImm(Arg::Width16, Load16Z, Arg::Unsigned))
879                         return result;
880                 }
881
882                 // Now handle compares that involve a load and an immediate.
883
884                 Arg::Width width = Arg::widthForB3Type(value->child(0)->type());
885                 if (Inst result = tryCompareLoadImm(width, Load, Arg::Signed))
886                     return result;
887
888                 // Now handle compares that involve a load. It's not obvious that it's better to
889                 // handle this before the immediate cases or not. Probably doesn't matter.
890
891                 if (Inst result = tryCompare(width, loadPromise(left), tmpPromise(right))) {
892                     commitInternal(left);
893                     return result;
894                 }
895                 
896                 if (Inst result = tryCompare(width, tmpPromise(left), loadPromise(right))) {
897                     commitInternal(right);
898                     return result;
899                 }
900
901                 // Now handle compares that involve an immediate and a tmp.
902                 
903                 if (leftImm && leftImm.isRepresentableAs<int32_t>()) {
904                     if (Inst result = tryCompare(width, leftImm, tmpPromise(right)))
905                         return result;
906                 }
907                 
908                 if (rightImm && rightImm.isRepresentableAs<int32_t>()) {
909                     if (Inst result = tryCompare(width, tmpPromise(left), rightImm))
910                         return result;
911                 }
912
913                 // Finally, handle comparison between tmps.
914                 return compare(width, relCond, tmpPromise(left), tmpPromise(right));
915             }
916
917             // Double comparisons can't really do anything smart.
918             return compareDouble(doubleCond, tmpPromise(left), tmpPromise(right));
919         };
920
921         Arg::Width width = Arg::widthForB3Type(value->type());
922         Arg resCond = Arg::resCond(MacroAssembler::NonZero).inverted(inverted);
923         
924         auto attemptFused = [&] () -> Inst {
925             switch (value->opcode()) {
926             case NotEqual:
927                 return createRelCond(MacroAssembler::NotEqual, MacroAssembler::DoubleNotEqualOrUnordered);
928             case Equal:
929                 return createRelCond(MacroAssembler::Equal, MacroAssembler::DoubleEqual);
930             case LessThan:
931                 return createRelCond(MacroAssembler::LessThan, MacroAssembler::DoubleLessThan);
932             case GreaterThan:
933                 return createRelCond(MacroAssembler::GreaterThan, MacroAssembler::DoubleGreaterThan);
934             case LessEqual:
935                 return createRelCond(MacroAssembler::LessThanOrEqual, MacroAssembler::DoubleLessThanOrEqual);
936             case GreaterEqual:
937                 return createRelCond(MacroAssembler::GreaterThanOrEqual, MacroAssembler::DoubleGreaterThanOrEqual);
938             case Above:
939                 // We use a bogus double condition because these integer comparisons won't got down that
940                 // path anyway.
941                 return createRelCond(MacroAssembler::Above, MacroAssembler::DoubleEqual);
942             case Below:
943                 return createRelCond(MacroAssembler::Below, MacroAssembler::DoubleEqual);
944             case AboveEqual:
945                 return createRelCond(MacroAssembler::AboveOrEqual, MacroAssembler::DoubleEqual);
946             case BelowEqual:
947                 return createRelCond(MacroAssembler::BelowOrEqual, MacroAssembler::DoubleEqual);
948             case BitAnd: {
949                 Value* left = value->child(0);
950                 Value* right = value->child(1);
951
952                 // FIXME: We don't actually have to worry about leftImm.
953                 // https://bugs.webkit.org/show_bug.cgi?id=150954
954
955                 Arg leftImm = imm(left);
956                 Arg rightImm = imm(right);
957                 
958                 auto tryTest = [&] (
959                     Arg::Width width, const ArgPromise& left, const ArgPromise& right) -> Inst {
960                     if (Inst result = test(width, resCond, left, right))
961                         return result;
962                     if (Inst result = test(width, resCond, right, left))
963                         return result;
964                     return Inst();
965                 };
966
967                 auto tryTestLoadImm = [&] (Arg::Width width, B3::Opcode loadOpcode) -> Inst {
968                     if (rightImm && rightImm.isRepresentableAs(width, Arg::Unsigned)) {
969                         if (Inst result = tryTest(width, loadPromise(left, loadOpcode), rightImm)) {
970                             commitInternal(left);
971                             return result;
972                         }
973                     }
974                     if (leftImm && leftImm.isRepresentableAs(width, Arg::Unsigned)) {
975                         if (Inst result = tryTest(width, leftImm, loadPromise(right, loadOpcode))) {
976                             commitInternal(right);
977                             return result;
978                         }
979                     }
980                     return Inst();
981                 };
982
983                 // First handle test's that involve fewer bits than B3's type system supports.
984
985                 if (Inst result = tryTestLoadImm(Arg::Width8, Load8Z))
986                     return result;
987
988                 if (Inst result = tryTestLoadImm(Arg::Width8, Load8S))
989                     return result;
990
991                 if (Inst result = tryTestLoadImm(Arg::Width16, Load16Z))
992                     return result;
993
994                 if (Inst result = tryTestLoadImm(Arg::Width16, Load16S))
995                     return result;
996
997                 // Now handle test's that involve a load and an immediate. Note that immediates are
998                 // 32-bit, and we want zero-extension. Hence, the immediate form is compiled as a
999                 // 32-bit test. Note that this spits on the grave of inferior endians, such as the
1000                 // big one.
1001                 
1002                 if (Inst result = tryTestLoadImm(Arg::Width32, Load))
1003                     return result;
1004
1005                 // Now handle test's that involve a load.
1006
1007                 Arg::Width width = Arg::widthForB3Type(value->child(0)->type());
1008                 if (Inst result = tryTest(width, loadPromise(left), tmpPromise(right))) {
1009                     commitInternal(left);
1010                     return result;
1011                 }
1012
1013                 if (Inst result = tryTest(width, tmpPromise(left), loadPromise(right))) {
1014                     commitInternal(right);
1015                     return result;
1016                 }
1017
1018                 // Now handle test's that involve an immediate and a tmp.
1019
1020                 if (leftImm && leftImm.isRepresentableAs<uint32_t>()) {
1021                     if (Inst result = tryTest(Arg::Width32, leftImm, tmpPromise(right)))
1022                         return result;
1023                 }
1024
1025                 if (rightImm && rightImm.isRepresentableAs<uint32_t>()) {
1026                     if (Inst result = tryTest(Arg::Width32, tmpPromise(left), rightImm))
1027                         return result;
1028                 }
1029
1030                 // Finally, just do tmp's.
1031                 return tryTest(width, tmpPromise(left), tmpPromise(right));
1032             }
1033             default:
1034                 return Inst();
1035             }
1036         };
1037
1038         if (canBeInternal(value) || value == m_value) {
1039             if (Inst result = attemptFused()) {
1040                 commitInternal(value);
1041                 return result;
1042             }
1043         }
1044
1045         if (Inst result = test(width, resCond, tmpPromise(value), Arg::imm(-1)))
1046             return result;
1047         
1048         // Sometimes this is the only form of test available. We prefer not to use this because
1049         // it's less canonical.
1050         return test(width, resCond, tmpPromise(value), tmpPromise(value));
1051     }
1052
1053     Inst createBranch(Value* value, bool inverted = false)
1054     {
1055         return createGenericCompare(
1056             value,
1057             [this] (
1058                 Arg::Width width, const Arg& relCond,
1059                 const ArgPromise& left, const ArgPromise& right) -> Inst {
1060                 switch (width) {
1061                 case Arg::Width8:
1062                     if (isValidForm(Branch8, Arg::RelCond, left.kind(), right.kind())) {
1063                         return Inst(
1064                             Branch8, m_value, relCond,
1065                             left.consume(*this), right.consume(*this));
1066                     }
1067                     return Inst();
1068                 case Arg::Width16:
1069                     return Inst();
1070                 case Arg::Width32:
1071                     if (isValidForm(Branch32, Arg::RelCond, left.kind(), right.kind())) {
1072                         return Inst(
1073                             Branch32, m_value, relCond,
1074                             left.consume(*this), right.consume(*this));
1075                     }
1076                     return Inst();
1077                 case Arg::Width64:
1078                     if (isValidForm(Branch64, Arg::RelCond, left.kind(), right.kind())) {
1079                         return Inst(
1080                             Branch64, m_value, relCond,
1081                             left.consume(*this), right.consume(*this));
1082                     }
1083                     return Inst();
1084                 }
1085             },
1086             [this] (
1087                 Arg::Width width, const Arg& resCond,
1088                 const ArgPromise& left, const ArgPromise& right) -> Inst {
1089                 switch (width) {
1090                 case Arg::Width8:
1091                     if (isValidForm(BranchTest8, Arg::ResCond, left.kind(), right.kind())) {
1092                         return Inst(
1093                             BranchTest8, m_value, resCond,
1094                             left.consume(*this), right.consume(*this));
1095                     }
1096                     return Inst();
1097                 case Arg::Width16:
1098                     return Inst();
1099                 case Arg::Width32:
1100                     if (isValidForm(BranchTest32, Arg::ResCond, left.kind(), right.kind())) {
1101                         return Inst(
1102                             BranchTest32, m_value, resCond,
1103                             left.consume(*this), right.consume(*this));
1104                     }
1105                     return Inst();
1106                 case Arg::Width64:
1107                     if (isValidForm(BranchTest64, Arg::ResCond, left.kind(), right.kind())) {
1108                         return Inst(
1109                             BranchTest64, m_value, resCond,
1110                             left.consume(*this), right.consume(*this));
1111                     }
1112                     return Inst();
1113                 }
1114             },
1115             [this] (Arg doubleCond, const ArgPromise& left, const ArgPromise& right) -> Inst {
1116                 if (isValidForm(BranchDouble, Arg::DoubleCond, left.kind(), right.kind())) {
1117                     return Inst(
1118                         BranchDouble, m_value, doubleCond,
1119                         left.consume(*this), right.consume(*this));
1120                 }
1121                 return Inst();
1122             },
1123             inverted);
1124     }
1125
1126     Inst createCompare(Value* value, bool inverted = false)
1127     {
1128         return createGenericCompare(
1129             value,
1130             [this] (
1131                 Arg::Width width, const Arg& relCond,
1132                 const ArgPromise& left, const ArgPromise& right) -> Inst {
1133                 switch (width) {
1134                 case Arg::Width8:
1135                 case Arg::Width16:
1136                     return Inst();
1137                 case Arg::Width32:
1138                     if (isValidForm(Compare32, Arg::RelCond, left.kind(), right.kind(), Arg::Tmp)) {
1139                         return Inst(
1140                             Compare32, m_value, relCond,
1141                             left.consume(*this), right.consume(*this), tmp(m_value));
1142                     }
1143                     return Inst();
1144                 case Arg::Width64:
1145                     if (isValidForm(Compare64, Arg::RelCond, left.kind(), right.kind(), Arg::Tmp)) {
1146                         return Inst(
1147                             Compare64, m_value, relCond,
1148                             left.consume(*this), right.consume(*this), tmp(m_value));
1149                     }
1150                     return Inst();
1151                 }
1152             },
1153             [this] (
1154                 Arg::Width width, const Arg& resCond,
1155                 const ArgPromise& left, const ArgPromise& right) -> Inst {
1156                 switch (width) {
1157                 case Arg::Width8:
1158                 case Arg::Width16:
1159                     return Inst();
1160                 case Arg::Width32:
1161                     if (isValidForm(Test32, Arg::ResCond, left.kind(), right.kind(), Arg::Tmp)) {
1162                         return Inst(
1163                             Test32, m_value, resCond,
1164                             left.consume(*this), right.consume(*this), tmp(m_value));
1165                     }
1166                     return Inst();
1167                 case Arg::Width64:
1168                     if (isValidForm(Test64, Arg::ResCond, left.kind(), right.kind(), Arg::Tmp)) {
1169                         return Inst(
1170                             Test64, m_value, resCond,
1171                             left.consume(*this), right.consume(*this), tmp(m_value));
1172                     }
1173                     return Inst();
1174                 }
1175             },
1176             [this] (const Arg&, const ArgPromise&, const ArgPromise&) -> Inst {
1177                 // FIXME: Implement this.
1178                 // https://bugs.webkit.org/show_bug.cgi?id=150903
1179                 return Inst();
1180             },
1181             inverted);
1182     }
1183
1184     template<typename BankInfo>
1185     Arg marshallCCallArgument(unsigned& argumentCount, unsigned& stackCount, Value* child)
1186     {
1187         unsigned argumentIndex = argumentCount++;
1188         if (argumentIndex < BankInfo::numberOfArgumentRegisters) {
1189             Tmp result = Tmp(BankInfo::toArgumentRegister(argumentIndex));
1190             append(relaxedMoveForType(child->type()), immOrTmp(child), result);
1191             return result;
1192         }
1193
1194         // Compute the place that this goes onto the stack. On X86_64 and probably other calling
1195         // conventions that don't involve obsolete computers and operating systems, sub-pointer-size
1196         // arguments are still given a full pointer-sized stack slot. Hence we don't have to consider
1197         // the type of the argument when deducing the stack index.
1198         unsigned stackIndex = stackCount++;
1199
1200         Arg result = Arg::callArg(stackIndex * sizeof(void*));
1201         
1202         // Put the code for storing the argument before anything else. This significantly eases the
1203         // burden on the register allocator. If we could, we'd hoist these stores as far as
1204         // possible.
1205         // FIXME: Add a phase to hoist stores as high as possible to relieve register pressure.
1206         // https://bugs.webkit.org/show_bug.cgi?id=151063
1207         m_insts.last().insert(0, createStore(child, result));
1208         
1209         return result;
1210     }
1211
1212     void lower()
1213     {
1214         switch (m_value->opcode()) {
1215         case B3::Nop: {
1216             // Yes, we will totally see Nop's because some phases will replaceWithNop() instead of
1217             // properly removing things.
1218             return;
1219         }
1220             
1221         case Load: {
1222             append(
1223                 moveForType(m_value->type()),
1224                 addr(m_value), tmp(m_value));
1225             return;
1226         }
1227             
1228         case Load8S: {
1229             append(Load8SignedExtendTo32, addr(m_value), tmp(m_value));
1230             return;
1231         }
1232
1233         case Load8Z: {
1234             append(Load8, addr(m_value), tmp(m_value));
1235             return;
1236         }
1237
1238         case Load16S: {
1239             append(Load16SignedExtendTo32, addr(m_value), tmp(m_value));
1240             return;
1241         }
1242
1243         case Load16Z: {
1244             append(Load16, addr(m_value), tmp(m_value));
1245             return;
1246         }
1247
1248         case Add: {
1249             appendBinOp<Add32, Add64, AddDouble, Commutative>(
1250                 m_value->child(0), m_value->child(1));
1251             return;
1252         }
1253
1254         case Sub: {
1255             if (m_value->child(0)->isInt(0))
1256                 appendUnOp<Neg32, Neg64, Air::Oops>(m_value->child(1));
1257             else
1258                 appendBinOp<Sub32, Sub64, Air::Oops>(m_value->child(0), m_value->child(1));
1259             return;
1260         }
1261
1262         case Mul: {
1263             appendBinOp<Mul32, Mul64, Air::Oops, Commutative>(
1264                 m_value->child(0), m_value->child(1));
1265             return;
1266         }
1267
1268         case Div: {
1269             if (isInt(m_value->type())) {
1270                 Tmp eax = Tmp(X86Registers::eax);
1271                 Tmp edx = Tmp(X86Registers::edx);
1272
1273                 Air::Opcode convertToDoubleWord;
1274                 Air::Opcode div;
1275                 switch (m_value->type()) {
1276                 case Int32:
1277                     convertToDoubleWord = X86ConvertToDoubleWord32;
1278                     div = X86Div32;
1279                     break;
1280                 case Int64:
1281                     convertToDoubleWord = X86ConvertToQuadWord64;
1282                     div = X86Div64;
1283                     break;
1284                 default:
1285                     RELEASE_ASSERT_NOT_REACHED();
1286                     return;
1287                 }
1288                 
1289                 append(Move, tmp(m_value->child(0)), eax);
1290                 append(convertToDoubleWord, eax, edx);
1291                 append(div, eax, edx, tmp(m_value->child(1)));
1292                 append(Move, eax, tmp(m_value));
1293                 return;
1294             }
1295
1296             // FIXME: Support doubles.
1297             // https://bugs.webkit.org/show_bug.cgi?id=150991
1298             RELEASE_ASSERT_NOT_REACHED();
1299             return;
1300         }
1301
1302         case BitAnd: {
1303             appendBinOp<And32, And64, Air::Oops, Commutative>(
1304                 m_value->child(0), m_value->child(1));
1305             return;
1306         }
1307
1308         case BitOr: {
1309             appendBinOp<Or32, Or64, Air::Oops, Commutative>(
1310                 m_value->child(0), m_value->child(1));
1311             return;
1312         }
1313
1314         case BitXor: {
1315             appendBinOp<Xor32, Xor64, Air::Oops, Commutative>(
1316                 m_value->child(0), m_value->child(1));
1317             return;
1318         }
1319
1320         case Shl: {
1321             if (m_value->child(1)->isInt32(1)) {
1322                 // This optimization makes sense on X86. I don't know if it makes sense anywhere else.
1323                 append(Move, tmp(m_value->child(0)), tmp(m_value));
1324                 append(
1325                     opcodeForType(Add32, Add64, Air::Oops, m_value->child(0)->type()),
1326                     tmp(m_value), tmp(m_value));
1327                 return;
1328             }
1329             
1330             appendShift<Lshift32, Lshift64>(m_value->child(0), m_value->child(1));
1331             return;
1332         }
1333
1334         case SShr: {
1335             appendShift<Rshift32, Rshift64>(m_value->child(0), m_value->child(1));
1336             return;
1337         }
1338
1339         case ZShr: {
1340             appendShift<Urshift32, Urshift64>(m_value->child(0), m_value->child(1));
1341             return;
1342         }
1343
1344         case Store: {
1345             Value* valueToStore = m_value->child(0);
1346             if (canBeInternal(valueToStore)) {
1347                 bool matched = false;
1348                 switch (valueToStore->opcode()) {
1349                 case Add:
1350                     matched = tryAppendStoreBinOp<Add32, Add64, Commutative>(
1351                         valueToStore->child(0), valueToStore->child(1));
1352                     break;
1353                 case Sub:
1354                     if (valueToStore->child(0)->isInt(0)) {
1355                         matched = tryAppendStoreUnOp<Neg32, Neg64>(valueToStore->child(1));
1356                         break;
1357                     }
1358                     matched = tryAppendStoreBinOp<Sub32, Sub64>(
1359                         valueToStore->child(0), valueToStore->child(1));
1360                     break;
1361                 case BitAnd:
1362                     matched = tryAppendStoreBinOp<And32, And64, Commutative>(
1363                         valueToStore->child(0), valueToStore->child(1));
1364                     break;
1365                 default:
1366                     break;
1367                 }
1368                 if (matched) {
1369                     commitInternal(valueToStore);
1370                     return;
1371                 }
1372             }
1373
1374             appendStore(valueToStore, addr(m_value));
1375             return;
1376         }
1377
1378         case Trunc: {
1379             ASSERT(tmp(m_value->child(0)) == tmp(m_value));
1380             return;
1381         }
1382
1383         case ZExt32: {
1384             if (highBitsAreZero(m_value->child(0))) {
1385                 ASSERT(tmp(m_value->child(0)) == tmp(m_value));
1386                 return;
1387             }
1388
1389             append(Move32, tmp(m_value->child(0)), tmp(m_value));
1390             return;
1391         }
1392
1393         case ArgumentReg: {
1394             m_prologue.append(Inst(
1395                 moveForType(m_value->type()), m_value,
1396                 Tmp(m_value->as<ArgumentRegValue>()->argumentReg()),
1397                 tmp(m_value)));
1398             return;
1399         }
1400
1401         case Const32: {
1402             append(Move, imm(m_value), tmp(m_value));
1403             return;
1404         }
1405         case Const64: {
1406             if (imm(m_value))
1407                 append(Move, imm(m_value), tmp(m_value));
1408             else
1409                 append(Move, Arg::imm64(m_value->asInt64()), tmp(m_value));
1410             return;
1411         }
1412
1413         case ConstDouble: {
1414             // We expect that the moveConstants() phase has run, and any doubles referenced from
1415             // stackmaps get fused.
1416             RELEASE_ASSERT(isIdentical(m_value->asDouble(), 0.0));
1417             append(MoveZeroToDouble, tmp(m_value));
1418             return;
1419         }
1420
1421         case FramePointer: {
1422             append(Move, Tmp(GPRInfo::callFrameRegister), tmp(m_value));
1423             return;
1424         }
1425
1426         case B3::StackSlot: {
1427             append(
1428                 Lea,
1429                 Arg::stack(m_stackToStack.get(m_value->as<StackSlotValue>())),
1430                 tmp(m_value));
1431             return;
1432         }
1433
1434         case Equal:
1435         case NotEqual:
1436         case LessThan:
1437         case GreaterThan:
1438         case LessEqual:
1439         case GreaterEqual:
1440         case Above:
1441         case Below:
1442         case AboveEqual:
1443         case BelowEqual: {
1444             m_insts.last().append(createCompare(m_value));
1445             return;
1446         }
1447
1448         case IToD: {
1449             appendUnOp<ConvertInt32ToDouble, ConvertInt64ToDouble, Air::Oops>(m_value->child(0));
1450             return;
1451         }
1452
1453         case CCall: {
1454             CCallValue* cCall = m_value->as<CCallValue>();
1455             Inst inst(Patch, cCall, Arg::special(m_code.cCallSpecial()));
1456
1457             // This is a bit weird - we have a super intense contract with Arg::CCallSpecial. It might
1458             // be better if we factored Air::CCallSpecial out of the Air namespace and made it a B3
1459             // thing.
1460             // FIXME: https://bugs.webkit.org/show_bug.cgi?id=151045
1461
1462             // We have a ton of flexibility regarding the callee argument, but currently, we don't
1463             // use it yet. It gets weird for reasons:
1464             // 1) We probably will never take advantage of this. We don't have C calls to locations
1465             //    loaded from addresses. We have JS calls like that, but those use Patchpoints.
1466             // 2) On X86_64 we still don't support call with BaseIndex.
1467             // 3) On non-X86, we don't natively support any kind of loading from address.
1468             // 4) We don't have an isValidForm() for the CCallSpecial so we have no smart way to
1469             //    decide.
1470             // FIXME: https://bugs.webkit.org/show_bug.cgi?id=151052
1471             inst.args.append(tmp(cCall->child(0)));
1472
1473             // We need to tell Air what registers this defines.
1474             inst.args.append(Tmp(GPRInfo::returnValueGPR));
1475             inst.args.append(Tmp(GPRInfo::returnValueGPR2));
1476             inst.args.append(Tmp(FPRInfo::returnValueFPR));
1477
1478             // Now marshall the arguments. This is where we implement the C calling convention. After
1479             // this, Air does not know what the convention is; it just takes our word for it.
1480             unsigned gpArgumentCount = 0;
1481             unsigned fpArgumentCount = 0;
1482             unsigned stackCount = 0;
1483             for (unsigned i = 1; i < cCall->numChildren(); ++i) {
1484                 Value* argChild = cCall->child(i);
1485                 Arg arg;
1486                 
1487                 switch (Arg::typeForB3Type(argChild->type())) {
1488                 case Arg::GP:
1489                     arg = marshallCCallArgument<GPRInfo>(gpArgumentCount, stackCount, argChild);
1490                     break;
1491
1492                 case Arg::FP:
1493                     arg = marshallCCallArgument<FPRInfo>(fpArgumentCount, stackCount, argChild);
1494                     break;
1495                 }
1496
1497                 if (arg.isTmp())
1498                     inst.args.append(arg);
1499             }
1500             
1501             m_insts.last().append(WTF::move(inst));
1502
1503             switch (cCall->type()) {
1504             case Void:
1505                 break;
1506             case Int32:
1507             case Int64:
1508                 append(Move, Tmp(GPRInfo::returnValueGPR), tmp(cCall));
1509                 break;
1510             case Double:
1511                 append(MoveDouble, Tmp(FPRInfo::returnValueFPR), tmp(cCall));
1512                 break;
1513             }
1514             return;
1515         }
1516
1517         case Patchpoint: {
1518             PatchpointValue* patchpointValue = m_value->as<PatchpointValue>();
1519             ensureSpecial(m_patchpointSpecial);
1520             
1521             Inst inst(Patch, patchpointValue, Arg::special(m_patchpointSpecial));
1522             
1523             if (patchpointValue->type() != Void)
1524                 inst.args.append(tmp(patchpointValue));
1525             
1526             fillStackmap(inst, patchpointValue, 0);
1527             
1528             m_insts.last().append(WTF::move(inst));
1529             return;
1530         }
1531
1532         case CheckAdd:
1533         case CheckSub: {
1534             // FIXME: Make this support commutativity. That will let us leverage more instruction forms
1535             // and it let us commute to maximize coalescing.
1536             // https://bugs.webkit.org/show_bug.cgi?id=151214
1537
1538             CheckValue* checkValue = m_value->as<CheckValue>();
1539
1540             Value* left = checkValue->child(0);
1541             Value* right = checkValue->child(1);
1542
1543             Tmp result = tmp(m_value);
1544
1545             // Handle checked negation.
1546             if (checkValue->opcode() == CheckSub && left->isInt(0)) {
1547                 append(relaxedMoveForType(checkValue->type()), tmp(right), result);
1548
1549                 Air::Opcode opcode =
1550                     opcodeForType(BranchNeg32, BranchNeg64, Air::Oops, checkValue->type());
1551                 CheckSpecial* special = ensureCheckSpecial(opcode, 2);
1552
1553                 Inst inst(Patch, checkValue, Arg::special(special));
1554                 inst.args.append(Arg::resCond(MacroAssembler::Overflow));
1555                 inst.args.append(result);
1556
1557                 fillStackmap(inst, checkValue, 2);
1558
1559                 m_insts.last().append(WTF::move(inst));
1560                 return;
1561             }
1562
1563             append(relaxedMoveForType(m_value->type()), tmp(left), result);
1564             
1565             Air::Opcode opcode = Air::Oops;
1566             CheckSpecial* special = nullptr;
1567             switch (m_value->opcode()) {
1568             case CheckAdd:
1569                 opcode = opcodeForType(BranchAdd32, BranchAdd64, Air::Oops, m_value->type());
1570                 special = ensureCheckSpecial(opcode, 3);
1571                 break;
1572             case CheckSub:
1573                 opcode = opcodeForType(BranchSub32, BranchSub64, Air::Oops, m_value->type());
1574                 special = ensureCheckSpecial(opcode, 3);
1575                 break;
1576             default:
1577                 RELEASE_ASSERT_NOT_REACHED();
1578                 break;
1579             }
1580
1581             Inst inst(Patch, checkValue, Arg::special(special));
1582
1583             inst.args.append(Arg::resCond(MacroAssembler::Overflow));
1584
1585             // FIXME: It would be great to fuse Loads into these. We currently don't do it because the
1586             // rule for stackmaps is that all addresses are just stack addresses. Maybe we could relax
1587             // this rule here.
1588             // https://bugs.webkit.org/show_bug.cgi?id=151228
1589             
1590             if (imm(right) && isValidForm(opcode, Arg::ResCond, Arg::Imm, Arg::Tmp))
1591                 inst.args.append(imm(right));
1592             else
1593                 inst.args.append(tmp(right));
1594             inst.args.append(result);
1595             
1596             fillStackmap(inst, checkValue, 2);
1597
1598             m_insts.last().append(WTF::move(inst));
1599             return;
1600         }
1601
1602         case CheckMul: {
1603             // Handle multiplication separately. Multiplication is hard because we have to preserve
1604             // both inputs. This requires using three-operand multiplication, even on platforms where
1605             // this requires an additional Move.
1606
1607             CheckValue* checkValue = m_value->as<CheckValue>();
1608
1609             Value* left = checkValue->child(0);
1610             Value* right = checkValue->child(1);
1611
1612             Tmp result = tmp(m_value);
1613
1614             Air::Opcode opcode =
1615                 opcodeForType(BranchMul32, BranchMul64, Air::Oops, checkValue->type());
1616             CheckSpecial* special = ensureCheckSpecial(opcode, 4);
1617
1618             // FIXME: Handle immediates.
1619             // https://bugs.webkit.org/show_bug.cgi?id=151230
1620
1621             Inst inst(Patch, checkValue, Arg::special(special));
1622             inst.args.append(Arg::resCond(MacroAssembler::Overflow));
1623             inst.args.append(tmp(left));
1624             inst.args.append(tmp(right));
1625             inst.args.append(result);
1626
1627             fillStackmap(inst, checkValue, 2);
1628             
1629             m_insts.last().append(WTF::move(inst));
1630             return;
1631         }
1632
1633         case Check: {
1634             Inst branch = createBranch(m_value->child(0));
1635
1636             CheckSpecial* special = ensureCheckSpecial(branch);
1637             
1638             CheckValue* checkValue = m_value->as<CheckValue>();
1639             
1640             Inst inst(Patch, checkValue, Arg::special(special));
1641             inst.args.appendVector(branch.args);
1642             
1643             fillStackmap(inst, checkValue, 1);
1644             
1645             m_insts.last().append(WTF::move(inst));
1646             return;
1647         }
1648
1649         case Upsilon: {
1650             Value* value = m_value->child(0);
1651             append(
1652                 relaxedMoveForType(value->type()), immOrTmp(value),
1653                 tmp(m_value->as<UpsilonValue>()->phi()));
1654             return;
1655         }
1656
1657         case Phi: {
1658             // Our semantics are determined by Upsilons, so we have nothing to do here.
1659             return;
1660         }
1661
1662         case Branch: {
1663             m_insts.last().append(createBranch(m_value->child(0)));
1664             return;
1665         }
1666
1667         case B3::Jump: {
1668             append(Air::Jump);
1669             return;
1670         }
1671             
1672         case Identity: {
1673             ASSERT(tmp(m_value->child(0)) == tmp(m_value));
1674             return;
1675         }
1676
1677         case Return: {
1678             Value* value = m_value->child(0);
1679             Air::Opcode move;
1680             Tmp dest;
1681             if (isInt(value->type())) {
1682                 move = Move;
1683                 dest = Tmp(GPRInfo::returnValueGPR);
1684             } else {
1685                 move = MoveDouble;
1686                 dest = Tmp(FPRInfo::returnValueFPR);
1687             }
1688             append(move, immOrTmp(value), dest);
1689             append(Ret);
1690             return;
1691         }
1692
1693         default:
1694             break;
1695         }
1696
1697         dataLog("FATAL: could not lower ", deepDump(m_value), "\n");
1698         RELEASE_ASSERT_NOT_REACHED();
1699     }
1700     
1701     IndexSet<Value> m_locked; // These are values that will have no Tmp in Air.
1702     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".
1703     IndexMap<B3::BasicBlock, Air::BasicBlock*> m_blockToBlock;
1704     HashMap<StackSlotValue*, Air::StackSlot*> m_stackToStack;
1705
1706     UseCounts m_useCounts;
1707
1708     Vector<Vector<Inst, 4>> m_insts;
1709     Vector<Inst> m_prologue;
1710
1711     B3::BasicBlock* m_block;
1712     unsigned m_index;
1713     Value* m_value;
1714
1715     PatchpointSpecial* m_patchpointSpecial { nullptr };
1716     HashMap<CheckSpecial::Key, CheckSpecial*> m_checkSpecials;
1717
1718     Procedure& m_procedure;
1719     Code& m_code;
1720 };
1721
1722 } // anonymous namespace
1723
1724 void lowerToAir(Procedure& procedure, Code& code)
1725 {
1726     PhaseScope phaseScope(procedure, "lowerToAir");
1727     LowerToAir lowerToAir(procedure, code);
1728     lowerToAir.run();
1729 }
1730
1731 } } // namespace JSC::B3
1732
1733 #endif // ENABLE(B3_JIT)
1734