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