1 /*
2  * Copyright 2017 WebAssembly Community Group participants
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *     http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 //
18 // Lowers i64s to i32s by splitting variables and arguments
19 // into pairs of i32s. i64 return values are lowered by
20 // returning the low half and storing the high half into a
21 // global.
22 //
23 
24 #include "abi/js.h"
25 #include "asmjs/shared-constants.h"
26 #include "emscripten-optimizer/istring.h"
27 #include "ir/flat.h"
28 #include "ir/iteration.h"
29 #include "ir/memory-utils.h"
30 #include "ir/module-utils.h"
31 #include "ir/names.h"
32 #include "pass.h"
33 #include "support/name.h"
34 #include "wasm-builder.h"
35 #include "wasm.h"
36 #include <algorithm>
37 
38 namespace wasm {
39 
makeHighName(Name n)40 static Name makeHighName(Name n) { return std::string(n.c_str()) + "$hi"; }
41 
42 struct I64ToI32Lowering : public WalkerPass<PostWalker<I64ToI32Lowering>> {
43   struct TempVar {
TempVarwasm::I64ToI32Lowering::TempVar44     TempVar(Index idx, Type ty, I64ToI32Lowering& pass)
45       : idx(idx), pass(pass), moved(false), ty(ty) {}
46 
TempVarwasm::I64ToI32Lowering::TempVar47     TempVar(TempVar&& other)
48       : idx(other), pass(other.pass), moved(false), ty(other.ty) {
49       assert(!other.moved);
50       other.moved = true;
51     }
52 
operator =wasm::I64ToI32Lowering::TempVar53     TempVar& operator=(TempVar&& rhs) {
54       assert(!rhs.moved);
55       // free overwritten idx
56       if (!moved) {
57         freeIdx();
58       }
59       idx = rhs.idx;
60       rhs.moved = true;
61       moved = false;
62       return *this;
63     }
64 
~TempVarwasm::I64ToI32Lowering::TempVar65     ~TempVar() {
66       if (!moved) {
67         freeIdx();
68       }
69     }
70 
operator ==wasm::I64ToI32Lowering::TempVar71     bool operator==(const TempVar& rhs) {
72       assert(!moved && !rhs.moved);
73       return idx == rhs.idx;
74     }
75 
operator Indexwasm::I64ToI32Lowering::TempVar76     operator Index() {
77       assert(!moved);
78       return idx;
79     }
80 
81     // disallow copying
82     TempVar(const TempVar&) = delete;
83     TempVar& operator=(const TempVar&) = delete;
84 
85   private:
freeIdxwasm::I64ToI32Lowering::TempVar86     void freeIdx() {
87       auto& freeList = pass.freeTemps[ty.getBasic()];
88       assert(std::find(freeList.begin(), freeList.end(), idx) ==
89              freeList.end());
90       freeList.push_back(idx);
91     }
92 
93     Index idx;
94     I64ToI32Lowering& pass;
95     bool moved; // since C++ will still destruct moved-from values
96     Type ty;
97   };
98 
99   // false since function types need to be lowered
100   // TODO: allow module-level transformations in parallel passes
isFunctionParallelwasm::I64ToI32Lowering101   bool isFunctionParallel() override { return false; }
102 
createwasm::I64ToI32Lowering103   Pass* create() override { return new I64ToI32Lowering; }
104 
doWalkModulewasm::I64ToI32Lowering105   void doWalkModule(Module* module) {
106     if (!builder) {
107       builder = make_unique<Builder>(*module);
108     }
109     // add new globals for high bits
110     for (size_t i = 0, globals = module->globals.size(); i < globals; ++i) {
111       auto* curr = module->globals[i].get();
112       if (curr->type != Type::i64) {
113         continue;
114       }
115       originallyI64Globals.insert(curr->name);
116       curr->type = Type::i32;
117       auto* high = builder->makeGlobal(makeHighName(curr->name),
118                                        Type::i32,
119                                        builder->makeConst(int32_t(0)),
120                                        Builder::Mutable);
121       module->addGlobal(high);
122       if (curr->imported()) {
123         Fatal() << "TODO: imported i64 globals";
124       } else {
125         if (auto* c = curr->init->dynCast<Const>()) {
126           uint64_t value = c->value.geti64();
127           c->value = Literal(uint32_t(value));
128           c->type = Type::i32;
129           high->init = builder->makeConst(uint32_t(value >> 32));
130         } else if (auto* get = curr->init->dynCast<GlobalGet>()) {
131           high->init =
132             builder->makeGlobalGet(makeHighName(get->name), Type::i32);
133         } else {
134           WASM_UNREACHABLE("unexpected expression type");
135         }
136         curr->init->type = Type::i32;
137       }
138     }
139 
140     // For functions that return 64-bit values, we use this global variable
141     // to return the high 32 bits.
142     auto* highBits = new Global();
143     highBits->type = Type::i32;
144     highBits->name = INT64_TO_32_HIGH_BITS;
145     highBits->init = builder->makeConst(int32_t(0));
146     highBits->mutable_ = true;
147     module->addGlobal(highBits);
148     PostWalker<I64ToI32Lowering>::doWalkModule(module);
149   }
150 
doWalkFunctionwasm::I64ToI32Lowering151   void doWalkFunction(Function* func) {
152     Flat::verifyFlatness(func);
153     // create builder here if this is first entry to module for this object
154     if (!builder) {
155       builder = make_unique<Builder>(*getModule());
156     }
157     indexMap.clear();
158     highBitVars.clear();
159     freeTemps.clear();
160     Module temp;
161     auto* oldFunc = ModuleUtils::copyFunction(func, temp);
162     func->sig.params = Type::none;
163     func->vars.clear();
164     func->localNames.clear();
165     func->localIndices.clear();
166     Index newIdx = 0;
167     Names::ensureNames(oldFunc);
168     for (Index i = 0; i < oldFunc->getNumLocals(); ++i) {
169       assert(oldFunc->hasLocalName(i));
170       Name lowName = oldFunc->getLocalName(i);
171       Name highName = makeHighName(lowName);
172       Type paramType = oldFunc->getLocalType(i);
173       auto builderFunc =
174         (i < oldFunc->getVarIndexBase())
175           ? Builder::addParam
176           : static_cast<Index (*)(Function*, Name, Type)>(Builder::addVar);
177       if (paramType == Type::i64) {
178         builderFunc(func, lowName, Type::i32);
179         builderFunc(func, highName, Type::i32);
180         indexMap[i] = newIdx;
181         newIdx += 2;
182       } else {
183         builderFunc(func, lowName, paramType);
184         indexMap[i] = newIdx++;
185       }
186     }
187     nextTemp = func->getNumLocals();
188     PostWalker<I64ToI32Lowering>::doWalkFunction(func);
189   }
190 
visitFunctionwasm::I64ToI32Lowering191   void visitFunction(Function* func) {
192     if (func->imported()) {
193       return;
194     }
195     if (func->sig.results == Type::i64) {
196       func->sig.results = Type::i32;
197       // body may not have out param if it ends with control flow
198       if (hasOutParam(func->body)) {
199         TempVar highBits = fetchOutParam(func->body);
200         TempVar lowBits = getTemp();
201         LocalSet* setLow = builder->makeLocalSet(lowBits, func->body);
202         GlobalSet* setHigh = builder->makeGlobalSet(
203           INT64_TO_32_HIGH_BITS, builder->makeLocalGet(highBits, Type::i32));
204         LocalGet* getLow = builder->makeLocalGet(lowBits, Type::i32);
205         func->body = builder->blockify(setLow, setHigh, getLow);
206       }
207     }
208     int idx = 0;
209     for (size_t i = func->getNumLocals(); i < nextTemp; i++) {
210       Name tmpName("i64toi32_i32$" + std::to_string(idx++));
211       builder->addVar(func, tmpName, tempTypes[i]);
212     }
213   }
214 
215   template<typename T>
216   using BuilderFunc = std::function<T*(std::vector<Expression*>&, Type)>;
217 
218   // Fixes up a call. If we performed fixups, returns the call; otherwise
219   // returns nullptr;
220   template<typename T>
visitGenericCallwasm::I64ToI32Lowering221   T* visitGenericCall(T* curr, BuilderFunc<T> callBuilder) {
222     bool fixed = false;
223     std::vector<Expression*> args;
224     for (auto* e : curr->operands) {
225       args.push_back(e);
226       if (hasOutParam(e)) {
227         TempVar argHighBits = fetchOutParam(e);
228         args.push_back(builder->makeLocalGet(argHighBits, Type::i32));
229         fixed = true;
230       }
231     }
232     if (curr->type != Type::i64) {
233       auto* ret = callBuilder(args, curr->type);
234       replaceCurrent(ret);
235       return fixed ? ret : nullptr;
236     }
237     TempVar lowBits = getTemp();
238     TempVar highBits = getTemp();
239     auto* call = callBuilder(args, Type::i32);
240     LocalSet* doCall = builder->makeLocalSet(lowBits, call);
241     LocalSet* setHigh = builder->makeLocalSet(
242       highBits, builder->makeGlobalGet(INT64_TO_32_HIGH_BITS, Type::i32));
243     LocalGet* getLow = builder->makeLocalGet(lowBits, Type::i32);
244     Block* result = builder->blockify(doCall, setHigh, getLow);
245     setOutParam(result, std::move(highBits));
246     replaceCurrent(result);
247     return call;
248   }
visitCallwasm::I64ToI32Lowering249   void visitCall(Call* curr) {
250     if (curr->isReturn &&
251         getModule()->getFunction(curr->target)->sig.results == Type::i64) {
252       Fatal()
253         << "i64 to i32 lowering of return_call values not yet implemented";
254     }
255     auto* fixedCall = visitGenericCall<Call>(
256       curr, [&](std::vector<Expression*>& args, Type results) {
257         return builder->makeCall(curr->target, args, results, curr->isReturn);
258       });
259     // If this was to an import, we need to call the legal version. This assumes
260     // that legalize-js-interface has been run before.
261     if (fixedCall && getModule()->getFunction(fixedCall->target)->imported()) {
262       fixedCall->target = std::string("legalfunc$") + fixedCall->target.str;
263       return;
264     }
265   }
266 
visitCallIndirectwasm::I64ToI32Lowering267   void visitCallIndirect(CallIndirect* curr) {
268     if (curr->isReturn && curr->sig.results == Type::i64) {
269       Fatal()
270         << "i64 to i32 lowering of return_call values not yet implemented";
271     }
272     visitGenericCall<CallIndirect>(
273       curr, [&](std::vector<Expression*>& args, Type results) {
274         std::vector<Type> params;
275         for (const auto& param : curr->sig.params) {
276           if (param == Type::i64) {
277             params.push_back(Type::i32);
278             params.push_back(Type::i32);
279           } else {
280             params.push_back(param);
281           }
282         }
283         return builder->makeCallIndirect(
284           curr->target, args, Signature(Type(params), results), curr->isReturn);
285       });
286   }
287 
visitLocalGetwasm::I64ToI32Lowering288   void visitLocalGet(LocalGet* curr) {
289     const auto mappedIndex = indexMap[curr->index];
290     // Need to remap the local into the new naming scheme, regardless of
291     // the type of the local.
292     curr->index = mappedIndex;
293     if (curr->type != Type::i64) {
294       return;
295     }
296     curr->type = Type::i32;
297     TempVar highBits = getTemp();
298     LocalSet* setHighBits = builder->makeLocalSet(
299       highBits, builder->makeLocalGet(mappedIndex + 1, Type::i32));
300     Block* result = builder->blockify(setHighBits, curr);
301     replaceCurrent(result);
302     setOutParam(result, std::move(highBits));
303   }
304 
lowerTeewasm::I64ToI32Lowering305   void lowerTee(LocalSet* curr) {
306     TempVar highBits = fetchOutParam(curr->value);
307     TempVar tmp = getTemp();
308     curr->type = Type::i32;
309     LocalSet* setLow = builder->makeLocalSet(tmp, curr);
310     LocalSet* setHigh = builder->makeLocalSet(
311       curr->index + 1, builder->makeLocalGet(highBits, Type::i32));
312     LocalGet* getLow = builder->makeLocalGet(tmp, Type::i32);
313     Block* result = builder->blockify(setLow, setHigh, getLow);
314     replaceCurrent(result);
315     setOutParam(result, std::move(highBits));
316   }
317 
visitLocalSetwasm::I64ToI32Lowering318   void visitLocalSet(LocalSet* curr) {
319     const auto mappedIndex = indexMap[curr->index];
320     // Need to remap the local into the new naming scheme, regardless of
321     // the type of the local.  Note that lowerTee depends on this happening.
322     curr->index = mappedIndex;
323     if (!hasOutParam(curr->value)) {
324       return;
325     }
326     if (curr->isTee()) {
327       lowerTee(curr);
328       return;
329     }
330     TempVar highBits = fetchOutParam(curr->value);
331     auto* setHigh = builder->makeLocalSet(
332       mappedIndex + 1, builder->makeLocalGet(highBits, Type::i32));
333     Block* result = builder->blockify(curr, setHigh);
334     replaceCurrent(result);
335   }
336 
visitGlobalGetwasm::I64ToI32Lowering337   void visitGlobalGet(GlobalGet* curr) {
338     if (!getFunction()) {
339       return; // if in a global init, skip - we already handled that.
340     }
341     if (!originallyI64Globals.count(curr->name)) {
342       return;
343     }
344     curr->type = Type::i32;
345     TempVar highBits = getTemp();
346     LocalSet* setHighBits = builder->makeLocalSet(
347       highBits, builder->makeGlobalGet(makeHighName(curr->name), Type::i32));
348     Block* result = builder->blockify(setHighBits, curr);
349     replaceCurrent(result);
350     setOutParam(result, std::move(highBits));
351   }
352 
visitGlobalSetwasm::I64ToI32Lowering353   void visitGlobalSet(GlobalSet* curr) {
354     if (!originallyI64Globals.count(curr->name)) {
355       return;
356     }
357     if (handleUnreachable(curr)) {
358       return;
359     }
360     TempVar highBits = fetchOutParam(curr->value);
361     auto* setHigh = builder->makeGlobalSet(
362       makeHighName(curr->name), builder->makeLocalGet(highBits, Type::i32));
363     replaceCurrent(builder->makeSequence(curr, setHigh));
364   }
365 
visitLoadwasm::I64ToI32Lowering366   void visitLoad(Load* curr) {
367     if (curr->type != Type::i64) {
368       return;
369     }
370     assert(!curr->isAtomic && "64-bit atomic load not implemented");
371     TempVar lowBits = getTemp();
372     TempVar highBits = getTemp();
373     TempVar ptrTemp = getTemp();
374     LocalSet* setPtr = builder->makeLocalSet(ptrTemp, curr->ptr);
375     LocalSet* loadHigh;
376     if (curr->bytes == 8) {
377       loadHigh = builder->makeLocalSet(
378         highBits,
379         builder->makeLoad(4,
380                           curr->signed_,
381                           curr->offset + 4,
382                           std::min(uint32_t(curr->align), uint32_t(4)),
383                           builder->makeLocalGet(ptrTemp, Type::i32),
384                           Type::i32));
385     } else if (curr->signed_) {
386       loadHigh = builder->makeLocalSet(
387         highBits,
388         builder->makeBinary(ShrSInt32,
389                             builder->makeLocalGet(lowBits, Type::i32),
390                             builder->makeConst(int32_t(31))));
391     } else {
392       loadHigh =
393         builder->makeLocalSet(highBits, builder->makeConst(int32_t(0)));
394     }
395     curr->type = Type::i32;
396     curr->bytes = std::min(curr->bytes, uint8_t(4));
397     curr->align = std::min(uint32_t(curr->align), uint32_t(4));
398     curr->ptr = builder->makeLocalGet(ptrTemp, Type::i32);
399     Block* result =
400       builder->blockify(setPtr,
401                         builder->makeLocalSet(lowBits, curr),
402                         loadHigh,
403                         builder->makeLocalGet(lowBits, Type::i32));
404     replaceCurrent(result);
405     setOutParam(result, std::move(highBits));
406   }
407 
visitStorewasm::I64ToI32Lowering408   void visitStore(Store* curr) {
409     if (!hasOutParam(curr->value)) {
410       return;
411     }
412     assert(curr->offset + 4 > curr->offset);
413     assert(!curr->isAtomic && "atomic store not implemented");
414     TempVar highBits = fetchOutParam(curr->value);
415     uint8_t bytes = curr->bytes;
416     curr->bytes = std::min(curr->bytes, uint8_t(4));
417     curr->align = std::min(uint32_t(curr->align), uint32_t(4));
418     curr->valueType = Type::i32;
419     if (bytes == 8) {
420       TempVar ptrTemp = getTemp();
421       LocalSet* setPtr = builder->makeLocalSet(ptrTemp, curr->ptr);
422       curr->ptr = builder->makeLocalGet(ptrTemp, Type::i32);
423       curr->finalize();
424       Store* storeHigh =
425         builder->makeStore(4,
426                            curr->offset + 4,
427                            std::min(uint32_t(curr->align), uint32_t(4)),
428                            builder->makeLocalGet(ptrTemp, Type::i32),
429                            builder->makeLocalGet(highBits, Type::i32),
430                            Type::i32);
431       replaceCurrent(builder->blockify(setPtr, curr, storeHigh));
432     }
433   }
434 
visitAtomicRMWwasm::I64ToI32Lowering435   void visitAtomicRMW(AtomicRMW* curr) {
436     if (handleUnreachable(curr)) {
437       return;
438     }
439     if (curr->type != Type::i64) {
440       return;
441     }
442     // We cannot break this up into smaller operations as it must be atomic.
443     // Lower to an instrinsic function that wasm2js will implement.
444     TempVar lowBits = getTemp();
445     TempVar highBits = getTemp();
446     auto* getLow = builder->makeCall(
447       ABI::wasm2js::ATOMIC_RMW_I64,
448       {builder->makeConst(int32_t(curr->op)),
449        builder->makeConst(int32_t(curr->bytes)),
450        builder->makeConst(int32_t(curr->offset)),
451        curr->ptr,
452        curr->value,
453        builder->makeLocalGet(fetchOutParam(curr->value), Type::i32)},
454       Type::i32);
455     auto* getHigh =
456       builder->makeCall(ABI::wasm2js::GET_STASHED_BITS, {}, Type::i32);
457     auto* setLow = builder->makeLocalSet(lowBits, getLow);
458     auto* setHigh = builder->makeLocalSet(highBits, getHigh);
459     auto* finalGet = builder->makeLocalGet(lowBits, Type::i32);
460     auto* result = builder->makeBlock({setLow, setHigh, finalGet});
461     setOutParam(result, std::move(highBits));
462     replaceCurrent(result);
463   }
464 
visitAtomicCmpxchgwasm::I64ToI32Lowering465   void visitAtomicCmpxchg(AtomicCmpxchg* curr) {
466     assert(curr->type != Type::i64 && "64-bit AtomicCmpxchg not implemented");
467   }
468 
visitAtomicWaitwasm::I64ToI32Lowering469   void visitAtomicWait(AtomicWait* curr) {
470     // The last parameter is an i64, so we cannot leave it as it is
471     assert(curr->offset == 0);
472     replaceCurrent(builder->makeCall(
473       ABI::wasm2js::ATOMIC_WAIT_I32,
474       {curr->ptr,
475        curr->expected,
476        curr->timeout,
477        builder->makeLocalGet(fetchOutParam(curr->timeout), Type::i32)},
478       Type::i32));
479   }
480 
visitConstwasm::I64ToI32Lowering481   void visitConst(Const* curr) {
482     if (!getFunction()) {
483       return; // if in a global init, skip - we already handled that.
484     }
485     if (curr->type != Type::i64) {
486       return;
487     }
488     TempVar highBits = getTemp();
489     Const* lowVal =
490       builder->makeConst(int32_t(curr->value.geti64() & 0xffffffff));
491     LocalSet* setHigh = builder->makeLocalSet(
492       highBits,
493       builder->makeConst(int32_t(uint64_t(curr->value.geti64()) >> 32)));
494     Block* result = builder->blockify(setHigh, lowVal);
495     setOutParam(result, std::move(highBits));
496     replaceCurrent(result);
497   }
498 
lowerEqZInt64wasm::I64ToI32Lowering499   void lowerEqZInt64(Unary* curr) {
500     TempVar highBits = fetchOutParam(curr->value);
501 
502     auto* result = builder->makeUnary(
503       EqZInt32,
504       builder->makeBinary(
505         OrInt32, curr->value, builder->makeLocalGet(highBits, Type::i32)));
506 
507     replaceCurrent(result);
508   }
509 
lowerExtendUInt32wasm::I64ToI32Lowering510   void lowerExtendUInt32(Unary* curr) {
511     TempVar highBits = getTemp();
512     Block* result = builder->blockify(
513       builder->makeLocalSet(highBits, builder->makeConst(int32_t(0))),
514       curr->value);
515     setOutParam(result, std::move(highBits));
516     replaceCurrent(result);
517   }
518 
lowerExtendSInt32wasm::I64ToI32Lowering519   void lowerExtendSInt32(Unary* curr) {
520     TempVar highBits = getTemp();
521     TempVar lowBits = getTemp();
522 
523     LocalSet* setLow = builder->makeLocalSet(lowBits, curr->value);
524     LocalSet* setHigh = builder->makeLocalSet(
525       highBits,
526       builder->makeBinary(ShrSInt32,
527                           builder->makeLocalGet(lowBits, Type::i32),
528                           builder->makeConst(int32_t(31))));
529 
530     Block* result = builder->blockify(
531       setLow, setHigh, builder->makeLocalGet(lowBits, Type::i32));
532 
533     setOutParam(result, std::move(highBits));
534     replaceCurrent(result);
535   }
536 
lowerWrapInt64wasm::I64ToI32Lowering537   void lowerWrapInt64(Unary* curr) {
538     // free the temp var
539     fetchOutParam(curr->value);
540     replaceCurrent(curr->value);
541   }
542 
lowerReinterpretFloat64wasm::I64ToI32Lowering543   void lowerReinterpretFloat64(Unary* curr) {
544     // Assume that the wasm file assumes the address 0 is invalid and roundtrip
545     // our f64 through memory at address 0
546     TempVar highBits = getTemp();
547     Block* result = builder->blockify(
548       builder->makeCall(
549         ABI::wasm2js::SCRATCH_STORE_F64, {curr->value}, Type::none),
550       builder->makeLocalSet(highBits,
551                             builder->makeCall(ABI::wasm2js::SCRATCH_LOAD_I32,
552                                               {builder->makeConst(int32_t(1))},
553                                               Type::i32)),
554       builder->makeCall(ABI::wasm2js::SCRATCH_LOAD_I32,
555                         {builder->makeConst(int32_t(0))},
556                         Type::i32));
557     setOutParam(result, std::move(highBits));
558     replaceCurrent(result);
559     MemoryUtils::ensureExists(getModule()->memory);
560     ABI::wasm2js::ensureHelpers(getModule());
561   }
562 
lowerReinterpretInt64wasm::I64ToI32Lowering563   void lowerReinterpretInt64(Unary* curr) {
564     // Assume that the wasm file assumes the address 0 is invalid and roundtrip
565     // our i64 through memory at address 0
566     TempVar highBits = fetchOutParam(curr->value);
567     Block* result = builder->blockify(
568       builder->makeCall(ABI::wasm2js::SCRATCH_STORE_I32,
569                         {builder->makeConst(int32_t(0)), curr->value},
570                         Type::none),
571       builder->makeCall(ABI::wasm2js::SCRATCH_STORE_I32,
572                         {builder->makeConst(int32_t(1)),
573                          builder->makeLocalGet(highBits, Type::i32)},
574                         Type::none),
575       builder->makeCall(ABI::wasm2js::SCRATCH_LOAD_F64, {}, Type::f64));
576     replaceCurrent(result);
577     MemoryUtils::ensureExists(getModule()->memory);
578     ABI::wasm2js::ensureHelpers(getModule());
579   }
580 
lowerTruncFloatToIntwasm::I64ToI32Lowering581   void lowerTruncFloatToInt(Unary* curr) {
582     // hiBits = if abs(f) >= 1.0 {
583     //    if f > 0.0 {
584     //        (unsigned) min(
585     //          floor(f / (float) U32_MAX),
586     //          (float) U32_MAX - 1,
587     //        )
588     //    } else {
589     //        (unsigned) ceil((f - (float) (unsigned) f) / ((float) U32_MAX))
590     //    }
591     // } else {
592     //    0
593     // }
594     //
595     // loBits = (unsigned) f;
596 
597     Literal litZero, litOne, u32Max;
598     UnaryOp trunc, convert, abs, floor, ceil;
599     Type localType;
600     BinaryOp ge, gt, min, div, sub;
601     switch (curr->op) {
602       case TruncSFloat32ToInt64:
603       case TruncUFloat32ToInt64: {
604         litZero = Literal((float)0);
605         litOne = Literal((float)1);
606         u32Max = Literal(((float)UINT_MAX) + 1);
607         trunc = TruncUFloat32ToInt32;
608         convert = ConvertUInt32ToFloat32;
609         localType = Type::f32;
610         abs = AbsFloat32;
611         ge = GeFloat32;
612         gt = GtFloat32;
613         min = MinFloat32;
614         floor = FloorFloat32;
615         ceil = CeilFloat32;
616         div = DivFloat32;
617         sub = SubFloat32;
618         break;
619       }
620       case TruncSFloat64ToInt64:
621       case TruncUFloat64ToInt64: {
622         litZero = Literal((double)0);
623         litOne = Literal((double)1);
624         u32Max = Literal(((double)UINT_MAX) + 1);
625         trunc = TruncUFloat64ToInt32;
626         convert = ConvertUInt32ToFloat64;
627         localType = Type::f64;
628         abs = AbsFloat64;
629         ge = GeFloat64;
630         gt = GtFloat64;
631         min = MinFloat64;
632         floor = FloorFloat64;
633         ceil = CeilFloat64;
634         div = DivFloat64;
635         sub = SubFloat64;
636         break;
637       }
638       default:
639         abort();
640     }
641 
642     TempVar f = getTemp(localType);
643     TempVar highBits = getTemp();
644 
645     Expression* gtZeroBranch = builder->makeBinary(
646       min,
647       builder->makeUnary(
648         floor,
649         builder->makeBinary(div,
650                             builder->makeLocalGet(f, localType),
651                             builder->makeConst(u32Max))),
652       builder->makeBinary(
653         sub, builder->makeConst(u32Max), builder->makeConst(litOne)));
654     Expression* ltZeroBranch = builder->makeUnary(
655       ceil,
656       builder->makeBinary(
657         div,
658         builder->makeBinary(
659           sub,
660           builder->makeLocalGet(f, localType),
661           builder->makeUnary(
662             convert,
663             builder->makeUnary(trunc, builder->makeLocalGet(f, localType)))),
664         builder->makeConst(u32Max)));
665 
666     If* highBitsCalc = builder->makeIf(
667       builder->makeBinary(
668         gt, builder->makeLocalGet(f, localType), builder->makeConst(litZero)),
669       builder->makeUnary(trunc, gtZeroBranch),
670       builder->makeUnary(trunc, ltZeroBranch));
671     If* highBitsVal = builder->makeIf(
672       builder->makeBinary(
673         ge,
674         builder->makeUnary(abs, builder->makeLocalGet(f, localType)),
675         builder->makeConst(litOne)),
676       highBitsCalc,
677       builder->makeConst(int32_t(0)));
678     Block* result = builder->blockify(
679       builder->makeLocalSet(f, curr->value),
680       builder->makeLocalSet(highBits, highBitsVal),
681       builder->makeUnary(trunc, builder->makeLocalGet(f, localType)));
682     setOutParam(result, std::move(highBits));
683     replaceCurrent(result);
684   }
685 
lowerConvertIntToFloatwasm::I64ToI32Lowering686   void lowerConvertIntToFloat(Unary* curr) {
687     // Here the same strategy as `emcc` is taken which takes the two halves of
688     // the 64-bit integer and creates a mathematical expression using float
689     // arithmetic to reassemble the final floating point value.
690     //
691     // For example for i64 -> f32 we generate:
692     //
693     //  ((double) (unsigned) lowBits) +
694     //      ((double) U32_MAX) * ((double) (int) highBits)
695     //
696     // Mostly just shuffling things around here with coercions and whatnot!
697     // Note though that all arithmetic is done with f64 to have as much
698     // precision as we can.
699     //
700     // NB: this is *not* accurate for i64 -> f32. Using f64s for intermediate
701     // operations can give slightly inaccurate results in some cases, as we
702     // round to an f64, then round again to an f32, which is not always the
703     // same as a single rounding of i64 to f32 directly. Example:
704     //
705     //   #include <stdio.h>
706     //   int main() {
707     //     unsigned long long x = 18446743523953737727ULL;
708     //     float y = x;
709     //     double z = x;
710     //     float w = z;
711     //     printf("i64          : %llu\n"
712     //            "i64->f32     : %f\n"
713     //            "i64->f64     : %f\n"
714     //            "i64->f64->f32: %f\n", x, y, z, w);
715     //   }
716     //
717     //   i64          : 18446743523953737727
718     //   i64->f32     : 18446742974197923840.000000 ;; correct rounding to f32
719     //   i64->f64     : 18446743523953737728.000000 ;; correct rounding to f64
720     //   i64->f64->f32: 18446744073709551616.000000 ;; incorrect rounding to f32
721     //
722     // This is even a problem if we use BigInts in JavaScript to represent
723     // i64s, as Math.fround(BigInt) is not supported - the BigInt must be
724     // converted to a Number first, so we again have that extra rounding.
725     //
726     // A more precise approach could use compiled floatdisf/floatundisf from
727     // compiler-rt, but that is much larger and slower. (Note that we are in the
728     // interesting situation of having f32 and f64 operations and only missing
729     // i64 ones, so we have a different problem to solve than compiler-rt, and
730     // maybe there is a better solution we haven't found yet.)
731     TempVar highBits = fetchOutParam(curr->value);
732     TempVar lowBits = getTemp();
733     TempVar highResult = getTemp();
734 
735     UnaryOp convertHigh;
736     switch (curr->op) {
737       case ConvertSInt64ToFloat32:
738       case ConvertSInt64ToFloat64:
739         convertHigh = ConvertSInt32ToFloat64;
740         break;
741       case ConvertUInt64ToFloat32:
742       case ConvertUInt64ToFloat64:
743         convertHigh = ConvertUInt32ToFloat64;
744         break;
745       default:
746         abort();
747     }
748 
749     Expression* result = builder->blockify(
750       builder->makeLocalSet(lowBits, curr->value),
751       builder->makeLocalSet(highResult, builder->makeConst(int32_t(0))),
752       builder->makeBinary(
753         AddFloat64,
754         builder->makeUnary(ConvertUInt32ToFloat64,
755                            builder->makeLocalGet(lowBits, Type::i32)),
756         builder->makeBinary(
757           MulFloat64,
758           builder->makeConst((double)UINT_MAX + 1),
759           builder->makeUnary(convertHigh,
760                              builder->makeLocalGet(highBits, Type::i32)))));
761 
762     switch (curr->op) {
763       case ConvertSInt64ToFloat32:
764       case ConvertUInt64ToFloat32: {
765         result = builder->makeUnary(DemoteFloat64, result);
766         break;
767       }
768       default:
769         break;
770     }
771 
772     replaceCurrent(result);
773   }
774 
lowerCountZeroswasm::I64ToI32Lowering775   void lowerCountZeros(Unary* curr) {
776     auto lower = [&](Block* result,
777                      UnaryOp op32,
778                      TempVar&& first,
779                      TempVar&& second) {
780       TempVar highResult = getTemp();
781       TempVar firstResult = getTemp();
782       LocalSet* setFirst = builder->makeLocalSet(
783         firstResult,
784         builder->makeUnary(op32, builder->makeLocalGet(first, Type::i32)));
785 
786       Binary* check =
787         builder->makeBinary(EqInt32,
788                             builder->makeLocalGet(firstResult, Type::i32),
789                             builder->makeConst(int32_t(32)));
790 
791       If* conditional = builder->makeIf(
792         check,
793         builder->makeBinary(
794           AddInt32,
795           builder->makeUnary(op32, builder->makeLocalGet(second, Type::i32)),
796           builder->makeConst(int32_t(32))),
797         builder->makeLocalGet(firstResult, Type::i32));
798 
799       LocalSet* setHigh =
800         builder->makeLocalSet(highResult, builder->makeConst(int32_t(0)));
801 
802       setOutParam(result, std::move(highResult));
803 
804       replaceCurrent(builder->blockify(result, setFirst, setHigh, conditional));
805     };
806 
807     TempVar highBits = fetchOutParam(curr->value);
808     TempVar lowBits = getTemp();
809     LocalSet* setLow = builder->makeLocalSet(lowBits, curr->value);
810     Block* result = builder->blockify(setLow);
811 
812     switch (curr->op) {
813       case ClzInt64:
814         lower(result, ClzInt32, std::move(highBits), std::move(lowBits));
815         break;
816       case CtzInt64:
817         WASM_UNREACHABLE("i64.ctz should be removed already");
818         break;
819       default:
820         abort();
821     }
822   }
823 
unaryNeedsLoweringwasm::I64ToI32Lowering824   bool unaryNeedsLowering(UnaryOp op) {
825     switch (op) {
826       case ClzInt64:
827       case CtzInt64:
828       case PopcntInt64:
829       case EqZInt64:
830       case ExtendSInt32:
831       case ExtendUInt32:
832       case WrapInt64:
833       case TruncSFloat32ToInt64:
834       case TruncUFloat32ToInt64:
835       case TruncSFloat64ToInt64:
836       case TruncUFloat64ToInt64:
837       case ReinterpretFloat64:
838       case ConvertSInt64ToFloat32:
839       case ConvertSInt64ToFloat64:
840       case ConvertUInt64ToFloat32:
841       case ConvertUInt64ToFloat64:
842       case ReinterpretInt64:
843         return true;
844       default:
845         return false;
846     }
847   }
848 
visitUnarywasm::I64ToI32Lowering849   void visitUnary(Unary* curr) {
850     if (!unaryNeedsLowering(curr->op)) {
851       return;
852     }
853     if (handleUnreachable(curr)) {
854       return;
855     }
856     assert(hasOutParam(curr->value) || curr->type == Type::i64 ||
857            curr->type == Type::f64);
858     switch (curr->op) {
859       case ClzInt64:
860       case CtzInt64:
861         lowerCountZeros(curr);
862         break;
863       case EqZInt64:
864         lowerEqZInt64(curr);
865         break;
866       case ExtendSInt32:
867         lowerExtendSInt32(curr);
868         break;
869       case ExtendUInt32:
870         lowerExtendUInt32(curr);
871         break;
872       case WrapInt64:
873         lowerWrapInt64(curr);
874         break;
875       case ReinterpretFloat64:
876         lowerReinterpretFloat64(curr);
877         break;
878       case ReinterpretInt64:
879         lowerReinterpretInt64(curr);
880         break;
881       case TruncSFloat32ToInt64:
882       case TruncUFloat32ToInt64:
883       case TruncSFloat64ToInt64:
884       case TruncUFloat64ToInt64:
885         lowerTruncFloatToInt(curr);
886         break;
887       case ConvertSInt64ToFloat32:
888       case ConvertSInt64ToFloat64:
889       case ConvertUInt64ToFloat32:
890       case ConvertUInt64ToFloat64:
891         lowerConvertIntToFloat(curr);
892         break;
893       case PopcntInt64:
894         WASM_UNREACHABLE("i64.popcnt should already be removed");
895       default:
896         std::cerr << "Unhandled unary operator: " << curr->op << std::endl;
897         abort();
898     }
899   }
900 
lowerAddwasm::I64ToI32Lowering901   Block* lowerAdd(Block* result,
902                   TempVar&& leftLow,
903                   TempVar&& leftHigh,
904                   TempVar&& rightLow,
905                   TempVar&& rightHigh) {
906     TempVar lowResult = getTemp();
907     TempVar highResult = getTemp();
908     LocalSet* addLow = builder->makeLocalSet(
909       lowResult,
910       builder->makeBinary(AddInt32,
911                           builder->makeLocalGet(leftLow, Type::i32),
912                           builder->makeLocalGet(rightLow, Type::i32)));
913     LocalSet* addHigh = builder->makeLocalSet(
914       highResult,
915       builder->makeBinary(AddInt32,
916                           builder->makeLocalGet(leftHigh, Type::i32),
917                           builder->makeLocalGet(rightHigh, Type::i32)));
918     LocalSet* carryBit = builder->makeLocalSet(
919       highResult,
920       builder->makeBinary(AddInt32,
921                           builder->makeLocalGet(highResult, Type::i32),
922                           builder->makeConst(int32_t(1))));
923     If* checkOverflow = builder->makeIf(
924       builder->makeBinary(LtUInt32,
925                           builder->makeLocalGet(lowResult, Type::i32),
926                           builder->makeLocalGet(rightLow, Type::i32)),
927       carryBit);
928     LocalGet* getLow = builder->makeLocalGet(lowResult, Type::i32);
929     result = builder->blockify(result, addLow, addHigh, checkOverflow, getLow);
930     setOutParam(result, std::move(highResult));
931     return result;
932   }
933 
lowerSubwasm::I64ToI32Lowering934   Block* lowerSub(Block* result,
935                   TempVar&& leftLow,
936                   TempVar&& leftHigh,
937                   TempVar&& rightLow,
938                   TempVar&& rightHigh) {
939     TempVar lowResult = getTemp();
940     TempVar highResult = getTemp();
941     TempVar borrow = getTemp();
942     LocalSet* subLow = builder->makeLocalSet(
943       lowResult,
944       builder->makeBinary(SubInt32,
945                           builder->makeLocalGet(leftLow, Type::i32),
946                           builder->makeLocalGet(rightLow, Type::i32)));
947     LocalSet* borrowBit = builder->makeLocalSet(
948       borrow,
949       builder->makeBinary(LtUInt32,
950                           builder->makeLocalGet(leftLow, Type::i32),
951                           builder->makeLocalGet(rightLow, Type::i32)));
952     LocalSet* subHigh1 = builder->makeLocalSet(
953       highResult,
954       builder->makeBinary(AddInt32,
955                           builder->makeLocalGet(borrow, Type::i32),
956                           builder->makeLocalGet(rightHigh, Type::i32)));
957     LocalSet* subHigh2 = builder->makeLocalSet(
958       highResult,
959       builder->makeBinary(SubInt32,
960                           builder->makeLocalGet(leftHigh, Type::i32),
961                           builder->makeLocalGet(highResult, Type::i32)));
962     LocalGet* getLow = builder->makeLocalGet(lowResult, Type::i32);
963     result =
964       builder->blockify(result, subLow, borrowBit, subHigh1, subHigh2, getLow);
965     setOutParam(result, std::move(highResult));
966     return result;
967   }
968 
lowerBitwisewasm::I64ToI32Lowering969   Block* lowerBitwise(BinaryOp op,
970                       Block* result,
971                       TempVar&& leftLow,
972                       TempVar&& leftHigh,
973                       TempVar&& rightLow,
974                       TempVar&& rightHigh) {
975     BinaryOp op32;
976     switch (op) {
977       case AndInt64:
978         op32 = AndInt32;
979         break;
980       case OrInt64:
981         op32 = OrInt32;
982         break;
983       case XorInt64:
984         op32 = XorInt32;
985         break;
986       default:
987         abort();
988     }
989     result = builder->blockify(
990       result,
991       builder->makeLocalSet(
992         rightHigh,
993         builder->makeBinary(op32,
994                             builder->makeLocalGet(leftHigh, Type::i32),
995                             builder->makeLocalGet(rightHigh, Type::i32))),
996       builder->makeBinary(op32,
997                           builder->makeLocalGet(leftLow, Type::i32),
998                           builder->makeLocalGet(rightLow, Type::i32)));
999     setOutParam(result, std::move(rightHigh));
1000     return result;
1001   }
1002 
makeLargeShlwasm::I64ToI32Lowering1003   Block* makeLargeShl(Index highBits, Index leftLow, Index shift) {
1004     return builder->blockify(
1005       builder->makeLocalSet(
1006         highBits,
1007         builder->makeBinary(ShlInt32,
1008                             builder->makeLocalGet(leftLow, Type::i32),
1009                             builder->makeLocalGet(shift, Type::i32))),
1010       builder->makeConst(int32_t(0)));
1011   }
1012 
1013   // a >> b where `b` >= 32
1014   //
1015   // implement as:
1016   //
1017   // hi = leftHigh >> 31 // copy sign bit
1018   // lo = leftHigh >> (b - 32)
makeLargeShrSwasm::I64ToI32Lowering1019   Block* makeLargeShrS(Index highBits, Index leftHigh, Index shift) {
1020     return builder->blockify(
1021       builder->makeLocalSet(
1022         highBits,
1023         builder->makeBinary(ShrSInt32,
1024                             builder->makeLocalGet(leftHigh, Type::i32),
1025                             builder->makeConst(int32_t(31)))),
1026       builder->makeBinary(ShrSInt32,
1027                           builder->makeLocalGet(leftHigh, Type::i32),
1028                           builder->makeLocalGet(shift, Type::i32)));
1029   }
1030 
makeLargeShrUwasm::I64ToI32Lowering1031   Block* makeLargeShrU(Index highBits, Index leftHigh, Index shift) {
1032     return builder->blockify(
1033       builder->makeLocalSet(highBits, builder->makeConst(int32_t(0))),
1034       builder->makeBinary(ShrUInt32,
1035                           builder->makeLocalGet(leftHigh, Type::i32),
1036                           builder->makeLocalGet(shift, Type::i32)));
1037   }
1038 
makeSmallShlwasm::I64ToI32Lowering1039   Block* makeSmallShl(Index highBits,
1040                       Index leftLow,
1041                       Index leftHigh,
1042                       Index shift,
1043                       Binary* shiftMask,
1044                       Binary* widthLessShift) {
1045     Binary* shiftedInBits = builder->makeBinary(
1046       AndInt32,
1047       shiftMask,
1048       builder->makeBinary(
1049         ShrUInt32, builder->makeLocalGet(leftLow, Type::i32), widthLessShift));
1050     Binary* shiftHigh =
1051       builder->makeBinary(ShlInt32,
1052                           builder->makeLocalGet(leftHigh, Type::i32),
1053                           builder->makeLocalGet(shift, Type::i32));
1054     return builder->blockify(
1055       builder->makeLocalSet(
1056         highBits, builder->makeBinary(OrInt32, shiftedInBits, shiftHigh)),
1057       builder->makeBinary(ShlInt32,
1058                           builder->makeLocalGet(leftLow, Type::i32),
1059                           builder->makeLocalGet(shift, Type::i32)));
1060   }
1061 
1062   // a >> b where `b` < 32
1063   //
1064   // implement as:
1065   //
1066   // hi = leftHigh >> b
1067   // lo = (leftLow >>> b) | (leftHigh << (32 - b))
makeSmallShrSwasm::I64ToI32Lowering1068   Block* makeSmallShrS(Index highBits,
1069                        Index leftLow,
1070                        Index leftHigh,
1071                        Index shift,
1072                        Binary* shiftMask,
1073                        Binary* widthLessShift) {
1074     Binary* shiftedInBits = builder->makeBinary(
1075       ShlInt32,
1076       builder->makeBinary(
1077         AndInt32, shiftMask, builder->makeLocalGet(leftHigh, Type::i32)),
1078       widthLessShift);
1079     Binary* shiftLow =
1080       builder->makeBinary(ShrUInt32,
1081                           builder->makeLocalGet(leftLow, Type::i32),
1082                           builder->makeLocalGet(shift, Type::i32));
1083     return builder->blockify(
1084       builder->makeLocalSet(
1085         highBits,
1086         builder->makeBinary(ShrSInt32,
1087                             builder->makeLocalGet(leftHigh, Type::i32),
1088                             builder->makeLocalGet(shift, Type::i32))),
1089       builder->makeBinary(OrInt32, shiftedInBits, shiftLow));
1090   }
1091 
makeSmallShrUwasm::I64ToI32Lowering1092   Block* makeSmallShrU(Index highBits,
1093                        Index leftLow,
1094                        Index leftHigh,
1095                        Index shift,
1096                        Binary* shiftMask,
1097                        Binary* widthLessShift) {
1098     Binary* shiftedInBits = builder->makeBinary(
1099       ShlInt32,
1100       builder->makeBinary(
1101         AndInt32, shiftMask, builder->makeLocalGet(leftHigh, Type::i32)),
1102       widthLessShift);
1103     Binary* shiftLow =
1104       builder->makeBinary(ShrUInt32,
1105                           builder->makeLocalGet(leftLow, Type::i32),
1106                           builder->makeLocalGet(shift, Type::i32));
1107     return builder->blockify(
1108       builder->makeLocalSet(
1109         highBits,
1110         builder->makeBinary(ShrUInt32,
1111                             builder->makeLocalGet(leftHigh, Type::i32),
1112                             builder->makeLocalGet(shift, Type::i32))),
1113       builder->makeBinary(OrInt32, shiftedInBits, shiftLow));
1114   }
1115 
lowerShiftwasm::I64ToI32Lowering1116   Block* lowerShift(BinaryOp op,
1117                     Block* result,
1118                     TempVar&& leftLow,
1119                     TempVar&& leftHigh,
1120                     TempVar&& rightLow,
1121                     TempVar&& rightHigh) {
1122     assert(op == ShlInt64 || op == ShrUInt64 || op == ShrSInt64);
1123     // shift left lowered as:
1124     // if 32 <= rightLow % 64:
1125     //     high = leftLow << k; low = 0
1126     // else:
1127     //     high = (((1 << k) - 1) & (leftLow >> (32 - k))) | (leftHigh << k);
1128     //     low = leftLow << k
1129     // where k = shift % 32. shift right is similar.
1130     TempVar shift = getTemp();
1131     LocalSet* setShift = builder->makeLocalSet(
1132       shift,
1133       builder->makeBinary(AndInt32,
1134                           builder->makeLocalGet(rightLow, Type::i32),
1135                           builder->makeConst(int32_t(32 - 1))));
1136     Binary* isLargeShift = builder->makeBinary(
1137       LeUInt32,
1138       builder->makeConst(int32_t(32)),
1139       builder->makeBinary(AndInt32,
1140                           builder->makeLocalGet(rightLow, Type::i32),
1141                           builder->makeConst(int32_t(64 - 1))));
1142     Block* largeShiftBlock;
1143     switch (op) {
1144       case ShlInt64:
1145         largeShiftBlock = makeLargeShl(rightHigh, leftLow, shift);
1146         break;
1147       case ShrSInt64:
1148         largeShiftBlock = makeLargeShrS(rightHigh, leftHigh, shift);
1149         break;
1150       case ShrUInt64:
1151         largeShiftBlock = makeLargeShrU(rightHigh, leftHigh, shift);
1152         break;
1153       default:
1154         abort();
1155     }
1156     Binary* shiftMask = builder->makeBinary(
1157       SubInt32,
1158       builder->makeBinary(ShlInt32,
1159                           builder->makeConst(int32_t(1)),
1160                           builder->makeLocalGet(shift, Type::i32)),
1161       builder->makeConst(int32_t(1)));
1162     Binary* widthLessShift =
1163       builder->makeBinary(SubInt32,
1164                           builder->makeConst(int32_t(32)),
1165                           builder->makeLocalGet(shift, Type::i32));
1166     Block* smallShiftBlock;
1167     switch (op) {
1168       case ShlInt64: {
1169         smallShiftBlock = makeSmallShl(
1170           rightHigh, leftLow, leftHigh, shift, shiftMask, widthLessShift);
1171         break;
1172       }
1173       case ShrSInt64: {
1174         smallShiftBlock = makeSmallShrS(
1175           rightHigh, leftLow, leftHigh, shift, shiftMask, widthLessShift);
1176         break;
1177       }
1178       case ShrUInt64: {
1179         smallShiftBlock = makeSmallShrU(
1180           rightHigh, leftLow, leftHigh, shift, shiftMask, widthLessShift);
1181         break;
1182       }
1183       default:
1184         abort();
1185     }
1186     If* ifLargeShift =
1187       builder->makeIf(isLargeShift, largeShiftBlock, smallShiftBlock);
1188     result = builder->blockify(result, setShift, ifLargeShift);
1189     setOutParam(result, std::move(rightHigh));
1190     return result;
1191   }
1192 
lowerEqwasm::I64ToI32Lowering1193   Block* lowerEq(Block* result,
1194                  TempVar&& leftLow,
1195                  TempVar&& leftHigh,
1196                  TempVar&& rightLow,
1197                  TempVar&& rightHigh) {
1198     return builder->blockify(
1199       result,
1200       builder->makeBinary(
1201         AndInt32,
1202         builder->makeBinary(EqInt32,
1203                             builder->makeLocalGet(leftLow, Type::i32),
1204                             builder->makeLocalGet(rightLow, Type::i32)),
1205         builder->makeBinary(EqInt32,
1206                             builder->makeLocalGet(leftHigh, Type::i32),
1207                             builder->makeLocalGet(rightHigh, Type::i32))));
1208   }
1209 
lowerNewasm::I64ToI32Lowering1210   Block* lowerNe(Block* result,
1211                  TempVar&& leftLow,
1212                  TempVar&& leftHigh,
1213                  TempVar&& rightLow,
1214                  TempVar&& rightHigh) {
1215     return builder->blockify(
1216       result,
1217       builder->makeBinary(
1218         OrInt32,
1219         builder->makeBinary(NeInt32,
1220                             builder->makeLocalGet(leftLow, Type::i32),
1221                             builder->makeLocalGet(rightLow, Type::i32)),
1222         builder->makeBinary(NeInt32,
1223                             builder->makeLocalGet(leftHigh, Type::i32),
1224                             builder->makeLocalGet(rightHigh, Type::i32))));
1225   }
1226 
lowerUCompwasm::I64ToI32Lowering1227   Block* lowerUComp(BinaryOp op,
1228                     Block* result,
1229                     TempVar&& leftLow,
1230                     TempVar&& leftHigh,
1231                     TempVar&& rightLow,
1232                     TempVar&& rightHigh) {
1233     BinaryOp highOp, lowOp;
1234     switch (op) {
1235       case LtUInt64:
1236         highOp = LtUInt32;
1237         lowOp = LtUInt32;
1238         break;
1239       case LeUInt64:
1240         highOp = LtUInt32;
1241         lowOp = LeUInt32;
1242         break;
1243       case GtUInt64:
1244         highOp = GtUInt32;
1245         lowOp = GtUInt32;
1246         break;
1247       case GeUInt64:
1248         highOp = GtUInt32;
1249         lowOp = GeUInt32;
1250         break;
1251       default:
1252         abort();
1253     }
1254     Binary* compHigh =
1255       builder->makeBinary(highOp,
1256                           builder->makeLocalGet(leftHigh, Type::i32),
1257                           builder->makeLocalGet(rightHigh, Type::i32));
1258     Binary* eqHigh =
1259       builder->makeBinary(EqInt32,
1260                           builder->makeLocalGet(leftHigh, Type::i32),
1261                           builder->makeLocalGet(rightHigh, Type::i32));
1262     Binary* compLow =
1263       builder->makeBinary(lowOp,
1264                           builder->makeLocalGet(leftLow, Type::i32),
1265                           builder->makeLocalGet(rightLow, Type::i32));
1266     return builder->blockify(
1267       result,
1268       builder->makeBinary(
1269         OrInt32, compHigh, builder->makeBinary(AndInt32, eqHigh, compLow)));
1270   }
1271 
lowerSCompwasm::I64ToI32Lowering1272   Block* lowerSComp(BinaryOp op,
1273                     Block* result,
1274                     TempVar&& leftLow,
1275                     TempVar&& leftHigh,
1276                     TempVar&& rightLow,
1277                     TempVar&& rightHigh) {
1278     BinaryOp highOp1, highOp2, lowOp;
1279     switch (op) {
1280       case LtSInt64:
1281         highOp1 = LtSInt32;
1282         highOp2 = LeSInt32;
1283         lowOp = GeUInt32;
1284         break;
1285       case LeSInt64:
1286         highOp1 = LtSInt32;
1287         highOp2 = LeSInt32;
1288         lowOp = GtUInt32;
1289         break;
1290       case GtSInt64:
1291         highOp1 = GtSInt32;
1292         highOp2 = GeSInt32;
1293         lowOp = LeUInt32;
1294         break;
1295       case GeSInt64:
1296         highOp1 = GtSInt32;
1297         highOp2 = GeSInt32;
1298         lowOp = LtUInt32;
1299         break;
1300       default:
1301         abort();
1302     }
1303     Binary* compHigh1 =
1304       builder->makeBinary(highOp1,
1305                           builder->makeLocalGet(leftHigh, Type::i32),
1306                           builder->makeLocalGet(rightHigh, Type::i32));
1307     Binary* compHigh2 =
1308       builder->makeBinary(highOp2,
1309                           builder->makeLocalGet(leftHigh, Type::i32),
1310                           builder->makeLocalGet(rightHigh, Type::i32));
1311     Binary* compLow =
1312       builder->makeBinary(lowOp,
1313                           builder->makeLocalGet(leftLow, Type::i32),
1314                           builder->makeLocalGet(rightLow, Type::i32));
1315     If* lowIf = builder->makeIf(
1316       compLow, builder->makeConst(int32_t(0)), builder->makeConst(int32_t(1)));
1317     If* highIf2 =
1318       builder->makeIf(compHigh2, lowIf, builder->makeConst(int32_t(0)));
1319     If* highIf1 =
1320       builder->makeIf(compHigh1, builder->makeConst(int32_t(1)), highIf2);
1321     return builder->blockify(result, highIf1);
1322   }
1323 
binaryNeedsLoweringwasm::I64ToI32Lowering1324   bool binaryNeedsLowering(BinaryOp op) {
1325     switch (op) {
1326       case AddInt64:
1327       case SubInt64:
1328       case MulInt64:
1329       case DivSInt64:
1330       case DivUInt64:
1331       case RemSInt64:
1332       case RemUInt64:
1333       case AndInt64:
1334       case OrInt64:
1335       case XorInt64:
1336       case ShlInt64:
1337       case ShrUInt64:
1338       case ShrSInt64:
1339       case RotLInt64:
1340       case RotRInt64:
1341       case EqInt64:
1342       case NeInt64:
1343       case LtSInt64:
1344       case LtUInt64:
1345       case LeSInt64:
1346       case LeUInt64:
1347       case GtSInt64:
1348       case GtUInt64:
1349       case GeSInt64:
1350       case GeUInt64:
1351         return true;
1352       default:
1353         return false;
1354     }
1355   }
1356 
visitBinarywasm::I64ToI32Lowering1357   void visitBinary(Binary* curr) {
1358     if (handleUnreachable(curr)) {
1359       return;
1360     }
1361     if (!binaryNeedsLowering(curr->op)) {
1362       return;
1363     }
1364     // left and right reachable, lower normally
1365     TempVar leftLow = getTemp();
1366     TempVar leftHigh = fetchOutParam(curr->left);
1367     TempVar rightLow = getTemp();
1368     TempVar rightHigh = fetchOutParam(curr->right);
1369     LocalSet* setRight = builder->makeLocalSet(rightLow, curr->right);
1370     LocalSet* setLeft = builder->makeLocalSet(leftLow, curr->left);
1371     Block* result = builder->blockify(setLeft, setRight);
1372     switch (curr->op) {
1373       case AddInt64: {
1374         replaceCurrent(lowerAdd(result,
1375                                 std::move(leftLow),
1376                                 std::move(leftHigh),
1377                                 std::move(rightLow),
1378                                 std::move(rightHigh)));
1379         break;
1380       }
1381       case SubInt64: {
1382         replaceCurrent(lowerSub(result,
1383                                 std::move(leftLow),
1384                                 std::move(leftHigh),
1385                                 std::move(rightLow),
1386                                 std::move(rightHigh)));
1387         break;
1388       }
1389       case MulInt64:
1390       case DivSInt64:
1391       case DivUInt64:
1392       case RemSInt64:
1393       case RemUInt64:
1394       case RotLInt64:
1395       case RotRInt64:
1396         WASM_UNREACHABLE("should have been removed by now");
1397 
1398       case AndInt64:
1399       case OrInt64:
1400       case XorInt64: {
1401         replaceCurrent(lowerBitwise(curr->op,
1402                                     result,
1403                                     std::move(leftLow),
1404                                     std::move(leftHigh),
1405                                     std::move(rightLow),
1406                                     std::move(rightHigh)));
1407         break;
1408       }
1409       case ShlInt64:
1410       case ShrSInt64:
1411       case ShrUInt64: {
1412         replaceCurrent(lowerShift(curr->op,
1413                                   result,
1414                                   std::move(leftLow),
1415                                   std::move(leftHigh),
1416                                   std::move(rightLow),
1417                                   std::move(rightHigh)));
1418         break;
1419       }
1420       case EqInt64: {
1421         replaceCurrent(lowerEq(result,
1422                                std::move(leftLow),
1423                                std::move(leftHigh),
1424                                std::move(rightLow),
1425                                std::move(rightHigh)));
1426         break;
1427       }
1428       case NeInt64: {
1429         replaceCurrent(lowerNe(result,
1430                                std::move(leftLow),
1431                                std::move(leftHigh),
1432                                std::move(rightLow),
1433                                std::move(rightHigh)));
1434         break;
1435       }
1436       case LtSInt64:
1437       case LeSInt64:
1438       case GtSInt64:
1439       case GeSInt64:
1440         replaceCurrent(lowerSComp(curr->op,
1441                                   result,
1442                                   std::move(leftLow),
1443                                   std::move(leftHigh),
1444                                   std::move(rightLow),
1445                                   std::move(rightHigh)));
1446         break;
1447       case LtUInt64:
1448       case LeUInt64:
1449       case GtUInt64:
1450       case GeUInt64: {
1451         replaceCurrent(lowerUComp(curr->op,
1452                                   result,
1453                                   std::move(leftLow),
1454                                   std::move(leftHigh),
1455                                   std::move(rightLow),
1456                                   std::move(rightHigh)));
1457         break;
1458       }
1459       default: {
1460         std::cerr << "Unhandled binary op " << curr->op << std::endl;
1461         abort();
1462       }
1463     }
1464   }
1465 
visitSelectwasm::I64ToI32Lowering1466   void visitSelect(Select* curr) {
1467     if (handleUnreachable(curr)) {
1468       return;
1469     }
1470     if (!hasOutParam(curr->ifTrue)) {
1471       assert(!hasOutParam(curr->ifFalse));
1472       return;
1473     }
1474     assert(hasOutParam(curr->ifFalse));
1475     TempVar highBits = getTemp();
1476     TempVar lowBits = getTemp();
1477     TempVar cond = getTemp();
1478     Block* result = builder->blockify(
1479       builder->makeLocalSet(cond, curr->condition),
1480       builder->makeLocalSet(
1481         lowBits,
1482         builder->makeSelect(
1483           builder->makeLocalGet(cond, Type::i32), curr->ifTrue, curr->ifFalse)),
1484       builder->makeLocalSet(
1485         highBits,
1486         builder->makeSelect(
1487           builder->makeLocalGet(cond, Type::i32),
1488           builder->makeLocalGet(fetchOutParam(curr->ifTrue), Type::i32),
1489           builder->makeLocalGet(fetchOutParam(curr->ifFalse), Type::i32))),
1490       builder->makeLocalGet(lowBits, Type::i32));
1491     setOutParam(result, std::move(highBits));
1492     replaceCurrent(result);
1493   }
1494 
visitDropwasm::I64ToI32Lowering1495   void visitDrop(Drop* curr) {
1496     if (!hasOutParam(curr->value)) {
1497       return;
1498     }
1499     // free temp var
1500     fetchOutParam(curr->value);
1501   }
1502 
visitReturnwasm::I64ToI32Lowering1503   void visitReturn(Return* curr) {
1504     if (!hasOutParam(curr->value)) {
1505       return;
1506     }
1507     TempVar lowBits = getTemp();
1508     TempVar highBits = fetchOutParam(curr->value);
1509     LocalSet* setLow = builder->makeLocalSet(lowBits, curr->value);
1510     GlobalSet* setHigh = builder->makeGlobalSet(
1511       INT64_TO_32_HIGH_BITS, builder->makeLocalGet(highBits, Type::i32));
1512     curr->value = builder->makeLocalGet(lowBits, Type::i32);
1513     Block* result = builder->blockify(setLow, setHigh, curr);
1514     replaceCurrent(result);
1515   }
1516 
1517 private:
1518   std::unique_ptr<Builder> builder;
1519   std::unordered_map<Index, Index> indexMap;
1520   std::unordered_map<int, std::vector<Index>> freeTemps;
1521   std::unordered_map<Expression*, TempVar> highBitVars;
1522   std::unordered_map<Index, Type> tempTypes;
1523   std::unordered_set<Name> originallyI64Globals;
1524   Index nextTemp;
1525 
getTempwasm::I64ToI32Lowering1526   TempVar getTemp(Type ty = Type::i32) {
1527     Index ret;
1528     auto& freeList = freeTemps[ty.getBasic()];
1529     if (freeList.size() > 0) {
1530       ret = freeList.back();
1531       freeList.pop_back();
1532     } else {
1533       ret = nextTemp++;
1534       tempTypes[ret] = ty;
1535     }
1536     assert(tempTypes[ret] == ty);
1537     return TempVar(ret, ty, *this);
1538   }
1539 
hasOutParamwasm::I64ToI32Lowering1540   bool hasOutParam(Expression* e) {
1541     return highBitVars.find(e) != highBitVars.end();
1542   }
1543 
setOutParamwasm::I64ToI32Lowering1544   void setOutParam(Expression* e, TempVar&& var) {
1545     highBitVars.emplace(e, std::move(var));
1546   }
1547 
fetchOutParamwasm::I64ToI32Lowering1548   TempVar fetchOutParam(Expression* e) {
1549     auto outParamIt = highBitVars.find(e);
1550     assert(outParamIt != highBitVars.end());
1551     TempVar ret = std::move(outParamIt->second);
1552     highBitVars.erase(e);
1553     return ret;
1554   }
1555 
1556   // If e.g. a select is unreachable, then one arm may have an out param
1557   // but not the other. In this case dce should really have been run
1558   // before; handle it in a simple way here by replacing the node with
1559   // a block of its children.
1560   // This is valid only for nodes that execute their children
1561   // unconditionally before themselves, so it is not valid for an if,
1562   // in particular.
handleUnreachablewasm::I64ToI32Lowering1563   bool handleUnreachable(Expression* curr) {
1564     if (curr->type != Type::unreachable) {
1565       return false;
1566     }
1567     std::vector<Expression*> children;
1568     bool hasUnreachable = false;
1569     for (auto* child : ChildIterator(curr)) {
1570       if (child->type.isConcrete()) {
1571         child = builder->makeDrop(child);
1572       } else if (child->type == Type::unreachable) {
1573         hasUnreachable = true;
1574       }
1575       children.push_back(child);
1576     }
1577     if (!hasUnreachable) {
1578       return false;
1579     }
1580     // This has an unreachable child, so we can replace it with
1581     // the children.
1582     auto* block = builder->makeBlock(children);
1583     assert(block->type == Type::unreachable);
1584     replaceCurrent(block);
1585     return true;
1586   }
1587 };
1588 
createI64ToI32LoweringPass()1589 Pass* createI64ToI32LoweringPass() { return new I64ToI32Lowering(); }
1590 
1591 } // namespace wasm
1592