1 /*
2 * Copyright 2016 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 // Optimize combinations of instructions
19 //
20
21 #include <algorithm>
22 #include <type_traits>
23
24 #include <ir/abstract.h>
25 #include <ir/bits.h>
26 #include <ir/cost.h>
27 #include <ir/effects.h>
28 #include <ir/literal-utils.h>
29 #include <ir/load-utils.h>
30 #include <ir/manipulation.h>
31 #include <ir/match.h>
32 #include <ir/properties.h>
33 #include <ir/utils.h>
34 #include <pass.h>
35 #include <support/threads.h>
36 #include <wasm-s-parser.h>
37 #include <wasm.h>
38
39 // TODO: Use the new sign-extension opcodes where appropriate. This needs to be
40 // conditionalized on the availability of atomics.
41
42 namespace wasm {
43
44 Name I32_EXPR = "i32.expr";
45 Name I64_EXPR = "i64.expr";
46 Name F32_EXPR = "f32.expr";
47 Name F64_EXPR = "f64.expr";
48 Name ANY_EXPR = "any.expr";
49
50 // Useful information about locals
51 struct LocalInfo {
52 static const Index kUnknown = Index(-1);
53
54 Index maxBits;
55 Index signExtedBits;
56 };
57
58 struct LocalScanner : PostWalker<LocalScanner> {
59 std::vector<LocalInfo>& localInfo;
60 const PassOptions& passOptions;
61
LocalScannerwasm::LocalScanner62 LocalScanner(std::vector<LocalInfo>& localInfo,
63 const PassOptions& passOptions)
64 : localInfo(localInfo), passOptions(passOptions) {}
65
doWalkFunctionwasm::LocalScanner66 void doWalkFunction(Function* func) {
67 // prepare
68 localInfo.resize(func->getNumLocals());
69 for (Index i = 0; i < func->getNumLocals(); i++) {
70 auto& info = localInfo[i];
71 if (func->isParam(i)) {
72 info.maxBits = getBitsForType(func->getLocalType(i)); // worst-case
73 info.signExtedBits = LocalInfo::kUnknown; // we will never know anything
74 } else {
75 info.maxBits = info.signExtedBits = 0; // we are open to learning
76 }
77 }
78 // walk
79 PostWalker<LocalScanner>::doWalkFunction(func);
80 // finalize
81 for (Index i = 0; i < func->getNumLocals(); i++) {
82 auto& info = localInfo[i];
83 if (info.signExtedBits == LocalInfo::kUnknown) {
84 info.signExtedBits = 0;
85 }
86 }
87 }
88
visitLocalSetwasm::LocalScanner89 void visitLocalSet(LocalSet* curr) {
90 auto* func = getFunction();
91 if (func->isParam(curr->index)) {
92 return;
93 }
94 auto type = getFunction()->getLocalType(curr->index);
95 if (type != Type::i32 && type != Type::i64) {
96 return;
97 }
98 // an integer var, worth processing
99 auto* value = Properties::getFallthrough(
100 curr->value, passOptions, getModule()->features);
101 auto& info = localInfo[curr->index];
102 info.maxBits = std::max(info.maxBits, Bits::getMaxBits(value, this));
103 auto signExtBits = LocalInfo::kUnknown;
104 if (Properties::getSignExtValue(value)) {
105 signExtBits = Properties::getSignExtBits(value);
106 } else if (auto* load = value->dynCast<Load>()) {
107 if (LoadUtils::isSignRelevant(load) && load->signed_) {
108 signExtBits = load->bytes * 8;
109 }
110 }
111 if (info.signExtedBits == 0) {
112 info.signExtedBits = signExtBits; // first info we see
113 } else if (info.signExtedBits != signExtBits) {
114 // contradictory information, give up
115 info.signExtedBits = LocalInfo::kUnknown;
116 }
117 }
118
119 // define this for the templated getMaxBits method. we know nothing here yet
120 // about locals, so return the maxes
getMaxBitsForLocalwasm::LocalScanner121 Index getMaxBitsForLocal(LocalGet* get) { return getBitsForType(get->type); }
122
getBitsForTypewasm::LocalScanner123 Index getBitsForType(Type type) {
124 TODO_SINGLE_COMPOUND(type);
125 switch (type.getBasic()) {
126 case Type::i32:
127 return 32;
128 case Type::i64:
129 return 64;
130 default:
131 return -1;
132 }
133 }
134 };
135
136 // Create a custom matcher for checking side effects
137 template<class Opt> struct PureMatcherKind {};
138 template<class Opt>
139 struct Match::Internal::KindTypeRegistry<PureMatcherKind<Opt>> {
140 using matched_t = Expression*;
141 using data_t = Opt*;
142 };
143 template<class Opt> struct Match::Internal::MatchSelf<PureMatcherKind<Opt>> {
operator ()wasm::Match::Internal::MatchSelf144 bool operator()(Expression* curr, Opt* opt) {
145 return !opt->effects(curr).hasSideEffects();
146 }
147 };
148
149 // Main pass class
150 struct OptimizeInstructions
151 : public WalkerPass<
152 PostWalker<OptimizeInstructions,
153 UnifiedExpressionVisitor<OptimizeInstructions>>> {
isFunctionParallelwasm::OptimizeInstructions154 bool isFunctionParallel() override { return true; }
155
createwasm::OptimizeInstructions156 Pass* create() override { return new OptimizeInstructions; }
157
158 bool fastMath;
159
doWalkFunctionwasm::OptimizeInstructions160 void doWalkFunction(Function* func) {
161 fastMath = getPassOptions().fastMath;
162 // first, scan locals
163 {
164 LocalScanner scanner(localInfo, getPassOptions());
165 scanner.setModule(getModule());
166 scanner.walkFunction(func);
167 }
168 // main walk
169 super::doWalkFunction(func);
170 }
171
visitExpressionwasm::OptimizeInstructions172 void visitExpression(Expression* curr) {
173 // we may be able to apply multiple patterns, one may open opportunities
174 // that look deeper NB: patterns must not have cycles
175 while (1) {
176 auto* handOptimized = handOptimize(curr);
177 if (handOptimized) {
178 curr = handOptimized;
179 replaceCurrent(curr);
180 continue;
181 }
182 break;
183 }
184 }
185
effectswasm::OptimizeInstructions186 EffectAnalyzer effects(Expression* expr) {
187 return EffectAnalyzer(getPassOptions(), getModule()->features, expr);
188 }
189
purewasm::OptimizeInstructions190 decltype(auto) pure(Expression** binder) {
191 using namespace Match::Internal;
192 return Matcher<PureMatcherKind<OptimizeInstructions>>(binder, this);
193 }
194
canReorderwasm::OptimizeInstructions195 bool canReorder(Expression* a, Expression* b) {
196 return EffectAnalyzer::canReorder(
197 getPassOptions(), getModule()->features, a, b);
198 }
199
200 // Optimizations that don't yet fit in the pattern DSL, but could be
201 // eventually maybe
handOptimizewasm::OptimizeInstructions202 Expression* handOptimize(Expression* curr) {
203 FeatureSet features = getModule()->features;
204 // if this contains dead code, don't bother trying to optimize it, the type
205 // might change (if might not be unreachable if just one arm is, for
206 // example). this optimization pass focuses on actually executing code. the
207 // only exceptions are control flow changes
208 if (curr->type == Type::unreachable && !curr->is<Break>() &&
209 !curr->is<Switch>() && !curr->is<If>()) {
210 return nullptr;
211 }
212 if (auto* binary = curr->dynCast<Binary>()) {
213 if (isSymmetric(binary)) {
214 canonicalize(binary);
215 }
216 }
217
218 {
219 // TODO: It is an ongoing project to port more transformations to the
220 // match API. Once most of the transformations have been ported, the
221 // `using namespace Match` can be hoisted to function scope and this extra
222 // block scope can be removed.
223 using namespace Match;
224 Builder builder(*getModule());
225 {
226 // try to get rid of (0 - ..), that is, a zero only used to negate an
227 // int. an add of a subtract can be flipped in order to remove it:
228 // (i32.add
229 // (i32.sub
230 // (i32.const 0)
231 // X
232 // )
233 // Y
234 // )
235 // =>
236 // (i32.sub
237 // Y
238 // X
239 // )
240 // Note that this reorders X and Y, so we need to be careful about that.
241 Expression *x, *y;
242 Binary* sub;
243 if (matches(curr,
244 binary(AddInt32,
245 binary(&sub, SubInt32, i32(0), any(&x)),
246 any(&y))) &&
247 canReorder(x, y)) {
248 sub->left = y;
249 sub->right = x;
250 return sub;
251 }
252 }
253 {
254 // The flip case is even easier, as no reordering occurs:
255 // (i32.add
256 // Y
257 // (i32.sub
258 // (i32.const 0)
259 // X
260 // )
261 // )
262 // =>
263 // (i32.sub
264 // Y
265 // X
266 // )
267 Expression* y;
268 Binary* sub;
269 if (matches(curr,
270 binary(AddInt32,
271 any(&y),
272 binary(&sub, SubInt32, i32(0), any())))) {
273 sub->left = y;
274 return sub;
275 }
276 }
277 {
278 // eqz((signed)x % C_pot) => eqz(x & (abs(C_pot) - 1))
279 Const* c;
280 Binary* inner;
281 if (matches(curr,
282 unary(Abstract::EqZ,
283 binary(&inner, Abstract::RemS, any(), ival(&c)))) &&
284 (c->value.isSignedMin() ||
285 Bits::isPowerOf2(c->value.abs().getInteger()))) {
286 inner->op = Abstract::getBinary(c->type, Abstract::And);
287 if (c->value.isSignedMin()) {
288 c->value = Literal::makeSignedMax(c->type);
289 } else {
290 c->value = c->value.abs().sub(Literal::makeOne(c->type));
291 }
292 return curr;
293 }
294 }
295 {
296 // try de-morgan's AND law,
297 // (eqz X) and (eqz Y) === eqz (X or Y)
298 // Note that the OR and XOR laws do not work here, as these
299 // are not booleans (we could check if they are, but a boolean
300 // would already optimize with the eqz anyhow, unless propagating).
301 // But for AND, the left is true iff X and Y are each all zero bits,
302 // and the right is true if the union of their bits is zero; same.
303 Unary* un;
304 Binary* bin;
305 Expression *x, *y;
306 if (matches(curr,
307 binary(&bin,
308 AndInt32,
309 unary(&un, EqZInt32, any(&x)),
310 unary(EqZInt32, any(&y))))) {
311 bin->op = OrInt32;
312 bin->left = x;
313 bin->right = y;
314 un->value = bin;
315 return un;
316 }
317 }
318 {
319 // i32.eqz(i32.wrap_i64(x)) => i64.eqz(x)
320 // where maxBits(x) <= 32
321 Unary* inner;
322 Expression* x;
323 if (matches(curr, unary(EqZInt32, unary(&inner, WrapInt64, any(&x)))) &&
324 Bits::getMaxBits(x, this) <= 32) {
325 inner->op = EqZInt64;
326 inner->value = x;
327 return inner;
328 }
329 }
330 {
331 // x <<>> (C & (31 | 63)) ==> x <<>> C'
332 // x <<>> (y & (31 | 63)) ==> x <<>> y
333 // where '<<>>':
334 // '<<', '>>', '>>>'. 'rotl' or 'rotr'
335 BinaryOp op;
336 Const* c;
337 Expression *x, *y;
338
339 // x <<>> C
340 if (matches(curr, binary(&op, any(&x), ival(&c))) &&
341 Abstract::hasAnyShift(op)) {
342 // truncate RHS constant to effective size as:
343 // i32(x) <<>> const(C & 31))
344 // i64(x) <<>> const(C & 63))
345 c->value = c->value.and_(
346 Literal::makeFromInt32(c->type.getByteSize() * 8 - 1, c->type));
347 // x <<>> 0 ==> x
348 if (c->value.isZero()) {
349 return x;
350 }
351 }
352 if (matches(
353 curr,
354 binary(&op, any(&x), binary(Abstract::And, any(&y), ival(&c)))) &&
355 Abstract::hasAnyShift(op)) {
356 // i32(x) <<>> (y & 31) ==> x <<>> y
357 // i64(x) <<>> (y & 63) ==> x <<>> y
358 if ((c->type == Type::i32 && (c->value.geti32() & 31) == 31) ||
359 (c->type == Type::i64 && (c->value.geti64() & 63LL) == 63LL)) {
360 curr->cast<Binary>()->right = y;
361 return curr;
362 }
363 }
364 }
365 }
366
367 if (auto* select = curr->dynCast<Select>()) {
368 return optimizeSelect(select);
369 }
370
371 if (auto* binary = curr->dynCast<Binary>()) {
372 if (auto* ext = Properties::getAlmostSignExt(binary)) {
373 Index extraShifts;
374 auto bits = Properties::getAlmostSignExtBits(binary, extraShifts);
375 if (extraShifts == 0) {
376 if (auto* load =
377 Properties::getFallthrough(ext, getPassOptions(), features)
378 ->dynCast<Load>()) {
379 // pattern match a load of 8 bits and a sign extend using a shl of
380 // 24 then shr_s of 24 as well, etc.
381 if (LoadUtils::canBeSigned(load) &&
382 ((load->bytes == 1 && bits == 8) ||
383 (load->bytes == 2 && bits == 16))) {
384 // if the value falls through, we can't alter the load, as it
385 // might be captured in a tee
386 if (load->signed_ == true || load == ext) {
387 load->signed_ = true;
388 return ext;
389 }
390 }
391 }
392 }
393 // if the sign-extend input cannot have a sign bit, we don't need it
394 // we also don't need it if it already has an identical-sized sign
395 // extend
396 if (Bits::getMaxBits(ext, this) + extraShifts < bits ||
397 isSignExted(ext, bits)) {
398 return removeAlmostSignExt(binary);
399 }
400 } else if (binary->op == EqInt32 || binary->op == NeInt32) {
401 if (auto* c = binary->right->dynCast<Const>()) {
402 if (auto* ext = Properties::getSignExtValue(binary->left)) {
403 // we are comparing a sign extend to a constant, which means we can
404 // use a cheaper zext
405 auto bits = Properties::getSignExtBits(binary->left);
406 binary->left = makeZeroExt(ext, bits);
407 // when we replace the sign-ext of the non-constant with a zero-ext,
408 // we are forcing the high bits to be all zero, instead of all zero
409 // or all one depending on the sign bit. so we may be changing the
410 // high bits from all one to all zero:
411 // * if the constant value's higher bits are mixed, then it can't
412 // be equal anyhow
413 // * if they are all zero, we may get a false true if the
414 // non-constant's upper bits were one. this can only happen if
415 // the non-constant's sign bit is set, so this false true is a
416 // risk only if the constant's sign bit is set (otherwise,
417 // false). But a constant with a sign bit but with upper bits
418 // zero is impossible to be equal to a sign-extended value
419 // anyhow, so the entire thing is false.
420 // * if they were all one, we may get a false false, if the only
421 // difference is in those upper bits. that means we are equal on
422 // the other bits, including the sign bit. so we can just mask
423 // off the upper bits in the constant value, in this case,
424 // forcing them to zero like we do in the zero-extend.
425 int32_t constValue = c->value.geti32();
426 auto upperConstValue = constValue & ~Bits::lowBitMask(bits);
427 uint32_t count = Bits::popCount(upperConstValue);
428 auto constSignBit = constValue & (1 << (bits - 1));
429 if ((count > 0 && count < 32 - bits) ||
430 (constSignBit && count == 0)) {
431 // mixed or [zero upper const bits with sign bit set]; the
432 // compared values can never be identical, so force something
433 // definitely impossible even after zext
434 assert(bits < 32);
435 c->value = Literal(int32_t(0x80000000));
436 // TODO: if no side effects, we can just replace it all with 1 or
437 // 0
438 } else {
439 // otherwise, they are all ones, so we can mask them off as
440 // mentioned before
441 c->value = c->value.and_(Literal(Bits::lowBitMask(bits)));
442 }
443 return binary;
444 }
445 } else if (auto* left = Properties::getSignExtValue(binary->left)) {
446 if (auto* right = Properties::getSignExtValue(binary->right)) {
447 auto bits = Properties::getSignExtBits(binary->left);
448 if (Properties::getSignExtBits(binary->right) == bits) {
449 // we are comparing two sign-exts with the same bits, so we may as
450 // well replace both with cheaper zexts
451 binary->left = makeZeroExt(left, bits);
452 binary->right = makeZeroExt(right, bits);
453 return binary;
454 }
455 } else if (auto* load = binary->right->dynCast<Load>()) {
456 // we are comparing a load to a sign-ext, we may be able to switch
457 // to zext
458 auto leftBits = Properties::getSignExtBits(binary->left);
459 if (load->signed_ && leftBits == load->bytes * 8) {
460 load->signed_ = false;
461 binary->left = makeZeroExt(left, leftBits);
462 return binary;
463 }
464 }
465 } else if (auto* load = binary->left->dynCast<Load>()) {
466 if (auto* right = Properties::getSignExtValue(binary->right)) {
467 // we are comparing a load to a sign-ext, we may be able to switch
468 // to zext
469 auto rightBits = Properties::getSignExtBits(binary->right);
470 if (load->signed_ && rightBits == load->bytes * 8) {
471 load->signed_ = false;
472 binary->right = makeZeroExt(right, rightBits);
473 return binary;
474 }
475 }
476 }
477 // note that both left and right may be consts, but then we let
478 // precompute compute the constant result
479 } else if (binary->op == AddInt32) {
480 if (auto* ret = optimizeAddedConstants(binary)) {
481 return ret;
482 }
483 } else if (binary->op == SubInt32) {
484 if (auto* ret = optimizeAddedConstants(binary)) {
485 return ret;
486 }
487 }
488 // a bunch of operations on a constant right side can be simplified
489 if (auto* right = binary->right->dynCast<Const>()) {
490 if (binary->op == AndInt32) {
491 auto mask = right->value.geti32();
492 // and with -1 does nothing (common in asm.js output)
493 if (mask == -1) {
494 return binary->left;
495 }
496 // small loads do not need to be masked, the load itself masks
497 if (auto* load = binary->left->dynCast<Load>()) {
498 if ((load->bytes == 1 && mask == 0xff) ||
499 (load->bytes == 2 && mask == 0xffff)) {
500 load->signed_ = false;
501 return binary->left;
502 }
503 } else if (auto maskedBits = Bits::getMaskedBits(mask)) {
504 if (Bits::getMaxBits(binary->left, this) <= maskedBits) {
505 // a mask of lower bits is not needed if we are already smaller
506 return binary->left;
507 }
508 }
509 }
510 // some math operations have trivial results
511 if (auto* ret = optimizeWithConstantOnRight(binary)) {
512 return ret;
513 }
514 // the square of some operations can be merged
515 if (auto* left = binary->left->dynCast<Binary>()) {
516 if (left->op == binary->op) {
517 if (auto* leftRight = left->right->dynCast<Const>()) {
518 if (left->op == AndInt32) {
519 leftRight->value = leftRight->value.and_(right->value);
520 return left;
521 } else if (left->op == OrInt32) {
522 leftRight->value = leftRight->value.or_(right->value);
523 return left;
524 } else if (left->op == ShlInt32 || left->op == ShrUInt32 ||
525 left->op == ShrSInt32 || left->op == ShlInt64 ||
526 left->op == ShrUInt64 || left->op == ShrSInt64) {
527 // shifts only use an effective amount from the constant, so
528 // adding must be done carefully
529 auto total = Bits::getEffectiveShifts(leftRight) +
530 Bits::getEffectiveShifts(right);
531 if (total == Bits::getEffectiveShifts(total, right->type)) {
532 // no overflow, we can do this
533 leftRight->value = Literal::makeFromInt32(total, right->type);
534 return left;
535 } // TODO: handle overflows
536 }
537 }
538 }
539 }
540 if (right->type == Type::i32) {
541 BinaryOp op;
542 int32_t c = right->value.geti32();
543 // First, try to lower signed operations to unsigned if that is
544 // possible. Some unsigned operations like div_u or rem_u are usually
545 // faster on VMs. Also this opens more possibilities for further
546 // simplifications afterwards.
547 if (c >= 0 &&
548 (op = makeUnsignedBinaryOp(binary->op)) != InvalidBinary &&
549 Bits::getMaxBits(binary->left, this) <= 31) {
550 binary->op = op;
551 }
552 if (c < 0 && c > std::numeric_limits<int32_t>::min() &&
553 binary->op == DivUInt32) {
554 // u32(x) / C ==> u32(x) >= C iff C > 2^31
555 // We avoid applying this for C == 2^31 due to conflict
556 // with other rule which transform to more prefereble
557 // right shift operation.
558 binary->op = c == -1 ? EqInt32 : GeUInt32;
559 return binary;
560 }
561 if (Bits::isPowerOf2((uint32_t)c)) {
562 switch (binary->op) {
563 case MulInt32:
564 return optimizePowerOf2Mul(binary, (uint32_t)c);
565 case RemUInt32:
566 return optimizePowerOf2URem(binary, (uint32_t)c);
567 case DivUInt32:
568 return optimizePowerOf2UDiv(binary, (uint32_t)c);
569 default:
570 break;
571 }
572 }
573 }
574 if (right->type == Type::i64) {
575 BinaryOp op;
576 int64_t c = right->value.geti64();
577 // See description above for Type::i32
578 if (c >= 0 &&
579 (op = makeUnsignedBinaryOp(binary->op)) != InvalidBinary &&
580 Bits::getMaxBits(binary->left, this) <= 63) {
581 binary->op = op;
582 }
583 if (getPassOptions().shrinkLevel == 0 && c < 0 &&
584 c > std::numeric_limits<int64_t>::min() &&
585 binary->op == DivUInt64) {
586 // u64(x) / C ==> u64(u64(x) >= C) iff C > 2^63
587 // We avoid applying this for C == 2^31 due to conflict
588 // with other rule which transform to more prefereble
589 // right shift operation.
590 // And apply this only for shrinkLevel == 0 due to it
591 // increasing size by one byte.
592 binary->op = c == -1LL ? EqInt64 : GeUInt64;
593 binary->type = Type::i32;
594 return Builder(*getModule()).makeUnary(ExtendUInt32, binary);
595 }
596 if (Bits::isPowerOf2((uint64_t)c)) {
597 switch (binary->op) {
598 case MulInt64:
599 return optimizePowerOf2Mul(binary, (uint64_t)c);
600 case RemUInt64:
601 return optimizePowerOf2URem(binary, (uint64_t)c);
602 case DivUInt64:
603 return optimizePowerOf2UDiv(binary, (uint64_t)c);
604 default:
605 break;
606 }
607 }
608 }
609 }
610 // a bunch of operations on a constant left side can be simplified
611 if (binary->left->is<Const>()) {
612 if (auto* ret = optimizeWithConstantOnLeft(binary)) {
613 return ret;
614 }
615 }
616 // bitwise operations
617 // for and and or, we can potentially conditionalize
618 if (binary->op == AndInt32 || binary->op == OrInt32) {
619 if (auto* ret = conditionalizeExpensiveOnBitwise(binary)) {
620 return ret;
621 }
622 }
623 // for or, we can potentially combine
624 if (binary->op == OrInt32) {
625 if (auto* ret = combineOr(binary)) {
626 return ret;
627 }
628 }
629 // relation/comparisons allow for math optimizations
630 if (binary->isRelational()) {
631 if (auto* ret = optimizeRelational(binary)) {
632 return ret;
633 }
634 }
635 // finally, try more expensive operations on the binary in
636 // the case that they have no side effects
637 if (!effects(binary->left).hasSideEffects()) {
638 if (ExpressionAnalyzer::equal(binary->left, binary->right)) {
639 if (auto* ret = optimizeBinaryWithEqualEffectlessChildren(binary)) {
640 return ret;
641 }
642 }
643 }
644
645 if (auto* ret = deduplicateBinary(binary)) {
646 return ret;
647 }
648 } else if (auto* unary = curr->dynCast<Unary>()) {
649 if (unary->op == EqZInt32) {
650 if (auto* inner = unary->value->dynCast<Binary>()) {
651 // Try to invert a relational operation using De Morgan's law
652 auto op = invertBinaryOp(inner->op);
653 if (op != InvalidBinary) {
654 inner->op = op;
655 return inner;
656 }
657 }
658 // eqz of a sign extension can be of zero-extension
659 if (auto* ext = Properties::getSignExtValue(unary->value)) {
660 // we are comparing a sign extend to a constant, which means we can
661 // use a cheaper zext
662 auto bits = Properties::getSignExtBits(unary->value);
663 unary->value = makeZeroExt(ext, bits);
664 return unary;
665 }
666 }
667
668 if (auto* ret = deduplicateUnary(unary)) {
669 return ret;
670 }
671 } else if (auto* set = curr->dynCast<GlobalSet>()) {
672 // optimize out a set of a get
673 auto* get = set->value->dynCast<GlobalGet>();
674 if (get && get->name == set->name) {
675 ExpressionManipulator::nop(curr);
676 }
677 } else if (auto* iff = curr->dynCast<If>()) {
678 iff->condition = optimizeBoolean(iff->condition);
679 if (iff->ifFalse) {
680 if (auto* unary = iff->condition->dynCast<Unary>()) {
681 if (unary->op == EqZInt32) {
682 // flip if-else arms to get rid of an eqz
683 iff->condition = unary->value;
684 std::swap(iff->ifTrue, iff->ifFalse);
685 }
686 }
687 if (iff->condition->type != Type::unreachable &&
688 ExpressionAnalyzer::equal(iff->ifTrue, iff->ifFalse)) {
689 // sides are identical, fold
690 // if we can replace the if with one arm, and no side effects in the
691 // condition, do that
692 auto needCondition = effects(iff->condition).hasSideEffects();
693 auto isSubType = Type::isSubType(iff->ifTrue->type, iff->type);
694 if (isSubType && !needCondition) {
695 return iff->ifTrue;
696 } else {
697 Builder builder(*getModule());
698 if (isSubType) {
699 return builder.makeSequence(builder.makeDrop(iff->condition),
700 iff->ifTrue);
701 } else {
702 // the types diff. as the condition is reachable, that means the
703 // if must be concrete while the arm is not
704 assert(iff->type.isConcrete() &&
705 iff->ifTrue->type == Type::unreachable);
706 // emit a block with a forced type
707 auto* ret = builder.makeBlock();
708 if (needCondition) {
709 ret->list.push_back(builder.makeDrop(iff->condition));
710 }
711 ret->list.push_back(iff->ifTrue);
712 ret->finalize(iff->type);
713 return ret;
714 }
715 }
716 }
717 }
718 } else if (auto* br = curr->dynCast<Break>()) {
719 if (br->condition) {
720 br->condition = optimizeBoolean(br->condition);
721 }
722 } else if (auto* load = curr->dynCast<Load>()) {
723 optimizeMemoryAccess(load->ptr, load->offset);
724 } else if (auto* store = curr->dynCast<Store>()) {
725 optimizeMemoryAccess(store->ptr, store->offset);
726 // stores of fewer bits truncates anyhow
727 if (auto* binary = store->value->dynCast<Binary>()) {
728 if (binary->op == AndInt32) {
729 if (auto* right = binary->right->dynCast<Const>()) {
730 if (right->type == Type::i32) {
731 auto mask = right->value.geti32();
732 if ((store->bytes == 1 && mask == 0xff) ||
733 (store->bytes == 2 && mask == 0xffff)) {
734 store->value = binary->left;
735 }
736 }
737 }
738 } else if (auto* ext = Properties::getSignExtValue(binary)) {
739 // if sign extending the exact bit size we store, we can skip the
740 // extension if extending something bigger, then we just alter bits we
741 // don't save anyhow
742 if (Properties::getSignExtBits(binary) >= Index(store->bytes) * 8) {
743 store->value = ext;
744 }
745 }
746 } else if (auto* unary = store->value->dynCast<Unary>()) {
747 if (unary->op == WrapInt64) {
748 // instead of wrapping to 32, just store some of the bits in the i64
749 store->valueType = Type::i64;
750 store->value = unary->value;
751 }
752 }
753 } else if (auto* memCopy = curr->dynCast<MemoryCopy>()) {
754 assert(features.hasBulkMemory());
755 if (auto* ret = optimizeMemoryCopy(memCopy)) {
756 return ret;
757 }
758 }
759 return nullptr;
760 }
761
getMaxBitsForLocalwasm::OptimizeInstructions762 Index getMaxBitsForLocal(LocalGet* get) {
763 // check what we know about the local
764 return localInfo[get->index].maxBits;
765 }
766
767 private:
768 // Information about our locals
769 std::vector<LocalInfo> localInfo;
770
771 // Canonicalizing the order of a symmetric binary helps us
772 // write more concise pattern matching code elsewhere.
canonicalizewasm::OptimizeInstructions773 void canonicalize(Binary* binary) {
774 assert(isSymmetric(binary));
775 auto swap = [&]() {
776 assert(canReorder(binary->left, binary->right));
777 std::swap(binary->left, binary->right);
778 };
779 auto maybeSwap = [&]() {
780 if (canReorder(binary->left, binary->right)) {
781 swap();
782 }
783 };
784 // Prefer a const on the right.
785 if (binary->left->is<Const>() && !binary->right->is<Const>()) {
786 return swap();
787 }
788 if (binary->right->is<Const>()) {
789 return;
790 }
791 // Prefer a get on the right.
792 if (binary->left->is<LocalGet>() && !binary->right->is<LocalGet>()) {
793 return maybeSwap();
794 }
795 // Sort by the node id type, if different.
796 if (binary->left->_id != binary->right->_id) {
797 if (binary->left->_id > binary->right->_id) {
798 return maybeSwap();
799 }
800 return;
801 }
802 // If the children have the same node id, we have to go deeper.
803 if (auto* left = binary->left->dynCast<Unary>()) {
804 auto* right = binary->right->cast<Unary>();
805 if (left->op > right->op) {
806 return maybeSwap();
807 }
808 }
809 if (auto* left = binary->left->dynCast<Binary>()) {
810 auto* right = binary->right->cast<Binary>();
811 if (left->op > right->op) {
812 return maybeSwap();
813 }
814 }
815 if (auto* left = binary->left->dynCast<LocalGet>()) {
816 auto* right = binary->right->cast<LocalGet>();
817 if (left->index > right->index) {
818 return maybeSwap();
819 }
820 }
821 }
822
823 // Optimize given that the expression is flowing into a boolean context
optimizeBooleanwasm::OptimizeInstructions824 Expression* optimizeBoolean(Expression* boolean) {
825 // TODO use a general getFallthroughs
826 if (auto* unary = boolean->dynCast<Unary>()) {
827 if (unary) {
828 if (unary->op == EqZInt32) {
829 auto* unary2 = unary->value->dynCast<Unary>();
830 if (unary2 && unary2->op == EqZInt32) {
831 // double eqz
832 return unary2->value;
833 }
834 if (auto* binary = unary->value->dynCast<Binary>()) {
835 // !(x <=> y) ==> x <!=> y
836 auto op = invertBinaryOp(binary->op);
837 if (op != InvalidBinary) {
838 binary->op = op;
839 return binary;
840 }
841 }
842 }
843 }
844 } else if (auto* binary = boolean->dynCast<Binary>()) {
845 if (binary->op == SubInt32) {
846 if (auto* c = binary->left->dynCast<Const>()) {
847 if (c->value.geti32() == 0) {
848 // bool(0 - x) ==> bool(x)
849 return binary->right;
850 }
851 }
852 } else if (binary->op == OrInt32) {
853 // an or flowing into a boolean context can consider each input as
854 // boolean
855 binary->left = optimizeBoolean(binary->left);
856 binary->right = optimizeBoolean(binary->right);
857 } else if (binary->op == NeInt32) {
858 if (auto* c = binary->right->dynCast<Const>()) {
859 // x != 0 is just x if it's used as a bool
860 if (c->value.geti32() == 0) {
861 return binary->left;
862 }
863 // TODO: Perhaps use it for separate final pass???
864 // x != -1 ==> x ^ -1
865 // if (num->value.geti32() == -1) {
866 // binary->op = XorInt32;
867 // return binary;
868 // }
869 }
870 }
871 if (auto* ext = Properties::getSignExtValue(binary)) {
872 // use a cheaper zero-extent, we just care about the boolean value
873 // anyhow
874 return makeZeroExt(ext, Properties::getSignExtBits(binary));
875 }
876 } else if (auto* block = boolean->dynCast<Block>()) {
877 if (block->type == Type::i32 && block->list.size() > 0) {
878 block->list.back() = optimizeBoolean(block->list.back());
879 }
880 } else if (auto* iff = boolean->dynCast<If>()) {
881 if (iff->type == Type::i32) {
882 iff->ifTrue = optimizeBoolean(iff->ifTrue);
883 iff->ifFalse = optimizeBoolean(iff->ifFalse);
884 }
885 } else if (auto* select = boolean->dynCast<Select>()) {
886 select->ifTrue = optimizeBoolean(select->ifTrue);
887 select->ifFalse = optimizeBoolean(select->ifFalse);
888 } else if (auto* tryy = boolean->dynCast<Try>()) {
889 if (tryy->type == Type::i32) {
890 tryy->body = optimizeBoolean(tryy->body);
891 tryy->catchBody = optimizeBoolean(tryy->catchBody);
892 }
893 }
894 // TODO: recurse into br values?
895 return boolean;
896 }
897
optimizeSelectwasm::OptimizeInstructions898 Expression* optimizeSelect(Select* curr) {
899 using namespace Match;
900 Builder builder(*getModule());
901 curr->condition = optimizeBoolean(curr->condition);
902 {
903 // Constant condition, we can just pick the correct side (barring side
904 // effects)
905 Expression *ifTrue, *ifFalse;
906 if (matches(curr, select(pure(&ifTrue), any(&ifFalse), i32(0)))) {
907 return ifFalse;
908 }
909 if (matches(curr, select(any(&ifTrue), any(&ifFalse), i32(0)))) {
910 return builder.makeSequence(builder.makeDrop(ifTrue), ifFalse);
911 }
912 int32_t cond;
913 if (matches(curr, select(any(&ifTrue), pure(&ifFalse), i32(&cond)))) {
914 // The condition must be non-zero because a zero would have matched one
915 // of the previous patterns.
916 assert(cond != 0);
917 return ifTrue;
918 }
919 // Don't bother when `ifFalse` isn't pure - we would need to reverse the
920 // order using a temp local, which would be bad
921 }
922 {
923 // Flip select to remove eqz if we can reorder
924 Select* s;
925 Expression *ifTrue, *ifFalse, *c;
926 if (matches(
927 curr,
928 select(
929 &s, any(&ifTrue), any(&ifFalse), unary(EqZInt32, any(&c)))) &&
930 canReorder(ifTrue, ifFalse)) {
931 s->ifTrue = ifFalse;
932 s->ifFalse = ifTrue;
933 s->condition = c;
934 }
935 }
936 {
937 // Simplify selects between 0 and 1
938 Expression* c;
939 bool reversed = matches(curr, select(ival(0), ival(1), any(&c)));
940 if (reversed || matches(curr, select(ival(1), ival(0), any(&c)))) {
941 if (reversed) {
942 c = optimizeBoolean(builder.makeUnary(EqZInt32, c));
943 }
944 if (!Properties::emitsBoolean(c)) {
945 // cond ? 1 : 0 ==> !!cond
946 c = builder.makeUnary(EqZInt32, builder.makeUnary(EqZInt32, c));
947 }
948 return curr->type == Type::i64 ? builder.makeUnary(ExtendUInt32, c) : c;
949 }
950 }
951 {
952 // Sides are identical, fold
953 Expression *ifTrue, *ifFalse, *c;
954 if (matches(curr, select(any(&ifTrue), any(&ifFalse), any(&c))) &&
955 ExpressionAnalyzer::equal(ifTrue, ifFalse)) {
956 auto value = effects(ifTrue);
957 if (value.hasSideEffects()) {
958 // At best we don't need the condition, but need to execute the
959 // value twice. a block is larger than a select by 2 bytes, and we
960 // must drop one value, so 3, while we save the condition, so it's
961 // not clear this is worth it, TODO
962 } else {
963 // value has no side effects
964 auto condition = effects(c);
965 if (!condition.hasSideEffects()) {
966 return ifTrue;
967 } else {
968 // The condition is last, so we need a new local, and it may be a
969 // bad idea to use a block like we do for an if. Do it only if we
970 // can reorder
971 if (!condition.invalidates(value)) {
972 return builder.makeSequence(builder.makeDrop(c), ifTrue);
973 }
974 }
975 }
976 }
977 }
978 return nullptr;
979 }
980
981 // find added constants in an expression tree, including multiplied/shifted,
982 // and combine them note that we ignore division/shift-right, as rounding
983 // makes this nonlinear, so not a valid opt
optimizeAddedConstantswasm::OptimizeInstructions984 Expression* optimizeAddedConstants(Binary* binary) {
985 uint32_t constant = 0;
986 std::vector<Const*> constants;
987
988 struct SeekState {
989 Expression* curr;
990 int mul;
991 SeekState(Expression* curr, int mul) : curr(curr), mul(mul) {}
992 };
993 std::vector<SeekState> seekStack;
994 seekStack.emplace_back(binary, 1);
995 while (!seekStack.empty()) {
996 auto state = seekStack.back();
997 seekStack.pop_back();
998 auto curr = state.curr;
999 auto mul = state.mul;
1000 if (auto* c = curr->dynCast<Const>()) {
1001 uint32_t value = c->value.geti32();
1002 if (value != 0) {
1003 constant += value * mul;
1004 constants.push_back(c);
1005 }
1006 continue;
1007 } else if (auto* binary = curr->dynCast<Binary>()) {
1008 if (binary->op == AddInt32) {
1009 seekStack.emplace_back(binary->right, mul);
1010 seekStack.emplace_back(binary->left, mul);
1011 continue;
1012 } else if (binary->op == SubInt32) {
1013 // if the left is a zero, ignore it, it's how we negate ints
1014 auto* left = binary->left->dynCast<Const>();
1015 seekStack.emplace_back(binary->right, -mul);
1016 if (!left || left->value.geti32() != 0) {
1017 seekStack.emplace_back(binary->left, mul);
1018 }
1019 continue;
1020 } else if (binary->op == ShlInt32) {
1021 if (auto* c = binary->right->dynCast<Const>()) {
1022 seekStack.emplace_back(
1023 binary->left, mul * Bits::pow2(Bits::getEffectiveShifts(c)));
1024 continue;
1025 }
1026 } else if (binary->op == MulInt32) {
1027 if (auto* c = binary->left->dynCast<Const>()) {
1028 seekStack.emplace_back(binary->right, mul * c->value.geti32());
1029 continue;
1030 } else if (auto* c = binary->right->dynCast<Const>()) {
1031 seekStack.emplace_back(binary->left, mul * c->value.geti32());
1032 continue;
1033 }
1034 }
1035 }
1036 };
1037 // find all factors
1038 if (constants.size() <= 1) {
1039 // nothing much to do, except for the trivial case of adding/subbing a
1040 // zero
1041 if (auto* c = binary->right->dynCast<Const>()) {
1042 if (c->value.geti32() == 0) {
1043 return binary->left;
1044 }
1045 }
1046 return nullptr;
1047 }
1048 // wipe out all constants, we'll replace with a single added one
1049 for (auto* c : constants) {
1050 c->value = Literal(int32_t(0));
1051 }
1052 // remove added/subbed zeros
1053 struct ZeroRemover : public PostWalker<ZeroRemover> {
1054 // TODO: we could save the binarys and costs we drop, and reuse them later
1055
1056 PassOptions& passOptions;
1057
1058 ZeroRemover(PassOptions& passOptions) : passOptions(passOptions) {}
1059
1060 void visitBinary(Binary* curr) {
1061 FeatureSet features = getModule()->features;
1062 auto* left = curr->left->dynCast<Const>();
1063 auto* right = curr->right->dynCast<Const>();
1064 if (curr->op == AddInt32) {
1065 if (left && left->value.geti32() == 0) {
1066 replaceCurrent(curr->right);
1067 return;
1068 }
1069 if (right && right->value.geti32() == 0) {
1070 replaceCurrent(curr->left);
1071 return;
1072 }
1073 } else if (curr->op == SubInt32) {
1074 // we must leave a left zero, as it is how we negate ints
1075 if (right && right->value.geti32() == 0) {
1076 replaceCurrent(curr->left);
1077 return;
1078 }
1079 } else if (curr->op == ShlInt32) {
1080 // shifting a 0 is a 0, or anything by 0 has no effect, all unless the
1081 // shift has side effects
1082 if (((left && left->value.geti32() == 0) ||
1083 (right && Bits::getEffectiveShifts(right) == 0)) &&
1084 !EffectAnalyzer(passOptions, features, curr->right)
1085 .hasSideEffects()) {
1086 replaceCurrent(curr->left);
1087 return;
1088 }
1089 } else if (curr->op == MulInt32) {
1090 // multiplying by zero is a zero, unless the other side has side
1091 // effects
1092 if (left && left->value.geti32() == 0 &&
1093 !EffectAnalyzer(passOptions, features, curr->right)
1094 .hasSideEffects()) {
1095 replaceCurrent(left);
1096 return;
1097 }
1098 if (right && right->value.geti32() == 0 &&
1099 !EffectAnalyzer(passOptions, features, curr->left)
1100 .hasSideEffects()) {
1101 replaceCurrent(right);
1102 return;
1103 }
1104 }
1105 }
1106 };
1107 Expression* walked = binary;
1108 ZeroRemover remover(getPassOptions());
1109 remover.setModule(getModule());
1110 remover.walk(walked);
1111 if (constant == 0) {
1112 return walked; // nothing more to do
1113 }
1114 if (auto* c = walked->dynCast<Const>()) {
1115 assert(c->value.geti32() == 0);
1116 c->value = Literal(constant);
1117 return c;
1118 }
1119 Builder builder(*getModule());
1120 return builder.makeBinary(
1121 AddInt32, walked, builder.makeConst(Literal(constant)));
1122 }
1123
1124 // expensive1 | expensive2 can be turned into expensive1 ? 1 : expensive2,
1125 // and expensive | cheap can be turned into cheap ? 1 : expensive,
1126 // so that we can avoid one expensive computation, if it has no side effects.
conditionalizeExpensiveOnBitwisewasm::OptimizeInstructions1127 Expression* conditionalizeExpensiveOnBitwise(Binary* binary) {
1128 // this operation can increase code size, so don't always do it
1129 auto& options = getPassRunner()->options;
1130 if (options.optimizeLevel < 2 || options.shrinkLevel > 0) {
1131 return nullptr;
1132 }
1133 const auto MIN_COST = 7;
1134 assert(binary->op == AndInt32 || binary->op == OrInt32);
1135 if (binary->right->is<Const>()) {
1136 return nullptr; // trivial
1137 }
1138 // bitwise logical operator on two non-numerical values, check if they are
1139 // boolean
1140 auto* left = binary->left;
1141 auto* right = binary->right;
1142 if (!Properties::emitsBoolean(left) || !Properties::emitsBoolean(right)) {
1143 return nullptr;
1144 }
1145 auto leftEffects = effects(left);
1146 auto rightEffects = effects(right);
1147 auto leftHasSideEffects = leftEffects.hasSideEffects();
1148 auto rightHasSideEffects = rightEffects.hasSideEffects();
1149 if (leftHasSideEffects && rightHasSideEffects) {
1150 return nullptr; // both must execute
1151 }
1152 // canonicalize with side effects, if any, happening on the left
1153 if (rightHasSideEffects) {
1154 if (CostAnalyzer(left).cost < MIN_COST) {
1155 return nullptr; // avoidable code is too cheap
1156 }
1157 if (leftEffects.invalidates(rightEffects)) {
1158 return nullptr; // cannot reorder
1159 }
1160 std::swap(left, right);
1161 } else if (leftHasSideEffects) {
1162 if (CostAnalyzer(right).cost < MIN_COST) {
1163 return nullptr; // avoidable code is too cheap
1164 }
1165 } else {
1166 // no side effects, reorder based on cost estimation
1167 auto leftCost = CostAnalyzer(left).cost;
1168 auto rightCost = CostAnalyzer(right).cost;
1169 if (std::max(leftCost, rightCost) < MIN_COST) {
1170 return nullptr; // avoidable code is too cheap
1171 }
1172 // canonicalize with expensive code on the right
1173 if (leftCost > rightCost) {
1174 std::swap(left, right);
1175 }
1176 }
1177 // worth it! perform conditionalization
1178 Builder builder(*getModule());
1179 if (binary->op == OrInt32) {
1180 return builder.makeIf(
1181 left, builder.makeConst(Literal(int32_t(1))), right);
1182 } else { // &
1183 return builder.makeIf(
1184 left, right, builder.makeConst(Literal(int32_t(0))));
1185 }
1186 }
1187
1188 // We can combine `or` operations, e.g.
1189 // (x > y) | (x == y) ==> x >= y
combineOrwasm::OptimizeInstructions1190 Expression* combineOr(Binary* binary) {
1191 assert(binary->op == OrInt32);
1192 if (auto* left = binary->left->dynCast<Binary>()) {
1193 if (auto* right = binary->right->dynCast<Binary>()) {
1194 if (left->op != right->op &&
1195 ExpressionAnalyzer::equal(left->left, right->left) &&
1196 ExpressionAnalyzer::equal(left->right, right->right) &&
1197 !effects(left->left).hasSideEffects() &&
1198 !effects(left->right).hasSideEffects()) {
1199 switch (left->op) {
1200 // (x > y) | (x == y) ==> x >= y
1201 case EqInt32: {
1202 if (right->op == GtSInt32) {
1203 left->op = GeSInt32;
1204 return left;
1205 }
1206 break;
1207 }
1208 default: {
1209 }
1210 }
1211 }
1212 }
1213 }
1214 return nullptr;
1215 }
1216
1217 // fold constant factors into the offset
optimizeMemoryAccesswasm::OptimizeInstructions1218 void optimizeMemoryAccess(Expression*& ptr, Address& offset) {
1219 // ptr may be a const, but it isn't worth folding that in (we still have a
1220 // const); in fact, it's better to do the opposite for gzip purposes as well
1221 // as for readability.
1222 auto* last = ptr->dynCast<Const>();
1223 if (last) {
1224 uint64_t value64 = last->value.getInteger();
1225 uint64_t offset64 = offset;
1226 if (getModule()->memory.is64()) {
1227 last->value = Literal(int64_t(value64 + offset64));
1228 offset = 0;
1229 } else {
1230 // don't do this if it would wrap the pointer
1231 if (value64 <= uint64_t(std::numeric_limits<int32_t>::max()) &&
1232 offset64 <= uint64_t(std::numeric_limits<int32_t>::max()) &&
1233 value64 + offset64 <=
1234 uint64_t(std::numeric_limits<int32_t>::max())) {
1235 last->value = Literal(int32_t(value64 + offset64));
1236 offset = 0;
1237 }
1238 }
1239 }
1240 }
1241
1242 // Optimize a multiply by a power of two on the right, which
1243 // can be a shift.
1244 // This doesn't shrink code size, and VMs likely optimize it anyhow,
1245 // but it's still worth doing since
1246 // * Often shifts are more common than muls.
1247 // * The constant is smaller.
optimizePowerOf2Mulwasm::OptimizeInstructions1248 template<typename T> Expression* optimizePowerOf2Mul(Binary* binary, T c) {
1249 static_assert(std::is_same<T, uint32_t>::value ||
1250 std::is_same<T, uint64_t>::value,
1251 "type mismatch");
1252 auto shifts = Bits::countTrailingZeroes(c);
1253 binary->op = std::is_same<T, uint32_t>::value ? ShlInt32 : ShlInt64;
1254 binary->right->cast<Const>()->value = Literal(static_cast<T>(shifts));
1255 return binary;
1256 }
1257
1258 // Optimize an unsigned divide / remainder by a power of two on the right
1259 // This doesn't shrink code size, and VMs likely optimize it anyhow,
1260 // but it's still worth doing since
1261 // * Usually ands are more common than urems.
1262 // * The constant is slightly smaller.
optimizePowerOf2UDivwasm::OptimizeInstructions1263 template<typename T> Expression* optimizePowerOf2UDiv(Binary* binary, T c) {
1264 static_assert(std::is_same<T, uint32_t>::value ||
1265 std::is_same<T, uint64_t>::value,
1266 "type mismatch");
1267 auto shifts = Bits::countTrailingZeroes(c);
1268 binary->op = std::is_same<T, uint32_t>::value ? ShrUInt32 : ShrUInt64;
1269 binary->right->cast<Const>()->value = Literal(static_cast<T>(shifts));
1270 return binary;
1271 }
1272
optimizePowerOf2URemwasm::OptimizeInstructions1273 template<typename T> Expression* optimizePowerOf2URem(Binary* binary, T c) {
1274 static_assert(std::is_same<T, uint32_t>::value ||
1275 std::is_same<T, uint64_t>::value,
1276 "type mismatch");
1277 binary->op = std::is_same<T, uint32_t>::value ? AndInt32 : AndInt64;
1278 binary->right->cast<Const>()->value = Literal(c - 1);
1279 return binary;
1280 }
1281
makeZeroExtwasm::OptimizeInstructions1282 Expression* makeZeroExt(Expression* curr, int32_t bits) {
1283 Builder builder(*getModule());
1284 return builder.makeBinary(
1285 AndInt32, curr, builder.makeConst(Literal(Bits::lowBitMask(bits))));
1286 }
1287
1288 // given an "almost" sign extend - either a proper one, or it
1289 // has too many shifts left - we remove the sign extend. If there are
1290 // too many shifts, we split the shifts first, so this removes the
1291 // two sign extend shifts and adds one (smaller one)
removeAlmostSignExtwasm::OptimizeInstructions1292 Expression* removeAlmostSignExt(Binary* outer) {
1293 auto* inner = outer->left->cast<Binary>();
1294 auto* outerConst = outer->right->cast<Const>();
1295 auto* innerConst = inner->right->cast<Const>();
1296 auto* value = inner->left;
1297 if (outerConst->value == innerConst->value) {
1298 return value;
1299 }
1300 // add a shift, by reusing the existing node
1301 innerConst->value = innerConst->value.sub(outerConst->value);
1302 return inner;
1303 }
1304
1305 // check if an expression is already sign-extended
isSignExtedwasm::OptimizeInstructions1306 bool isSignExted(Expression* curr, Index bits) {
1307 if (Properties::getSignExtValue(curr)) {
1308 return Properties::getSignExtBits(curr) == bits;
1309 }
1310 if (auto* get = curr->dynCast<LocalGet>()) {
1311 // check what we know about the local
1312 return localInfo[get->index].signExtedBits == bits;
1313 }
1314 return false;
1315 }
1316
1317 // optimize trivial math operations, given that the right side of a binary
1318 // is a constant
optimizeWithConstantOnRightwasm::OptimizeInstructions1319 Expression* optimizeWithConstantOnRight(Binary* curr) {
1320 using namespace Match;
1321 Builder builder(*getModule());
1322 Expression* left;
1323 auto* right = curr->right->cast<Const>();
1324 auto type = curr->right->type;
1325
1326 // Operations on zero
1327 if (matches(curr, binary(Abstract::Shl, any(&left), ival(0))) ||
1328 matches(curr, binary(Abstract::ShrU, any(&left), ival(0))) ||
1329 matches(curr, binary(Abstract::ShrS, any(&left), ival(0))) ||
1330 matches(curr, binary(Abstract::Or, any(&left), ival(0))) ||
1331 matches(curr, binary(Abstract::Xor, any(&left), ival(0)))) {
1332 return left;
1333 }
1334 if (matches(curr, binary(Abstract::Mul, pure(&left), ival(0))) ||
1335 matches(curr, binary(Abstract::And, pure(&left), ival(0)))) {
1336 return right;
1337 }
1338 // x == 0 ==> eqz x
1339 if (matches(curr, binary(Abstract::Eq, any(&left), ival(0)))) {
1340 return builder.makeUnary(Abstract::getUnary(type, Abstract::EqZ), left);
1341 }
1342 // Operations on one
1343 // (signed)x % 1 ==> 0
1344 if (matches(curr, binary(Abstract::RemS, pure(&left), ival(1)))) {
1345 right->value = Literal::makeZero(type);
1346 return right;
1347 }
1348 // (signed)x % C_pot != 0 ==> (x & (abs(C_pot) - 1)) != 0
1349 {
1350 Const* c;
1351 Binary* inner;
1352 if (matches(curr,
1353 binary(Abstract::Ne,
1354 binary(&inner, Abstract::RemS, any(), ival(&c)),
1355 ival(0))) &&
1356 (c->value.isSignedMin() ||
1357 Bits::isPowerOf2(c->value.abs().getInteger()))) {
1358 inner->op = Abstract::getBinary(c->type, Abstract::And);
1359 if (c->value.isSignedMin()) {
1360 c->value = Literal::makeSignedMax(c->type);
1361 } else {
1362 c->value = c->value.abs().sub(Literal::makeOne(c->type));
1363 }
1364 return curr;
1365 }
1366 }
1367 // bool(x) | 1 ==> 1
1368 if (matches(curr, binary(Abstract::Or, pure(&left), ival(1))) &&
1369 Bits::getMaxBits(left, this) == 1) {
1370 return right;
1371 }
1372 // bool(x) & 1 ==> bool(x)
1373 if (matches(curr, binary(Abstract::And, any(&left), ival(1))) &&
1374 Bits::getMaxBits(left, this) == 1) {
1375 return left;
1376 }
1377 // bool(x) == 1 ==> bool(x)
1378 if (matches(curr, binary(EqInt32, any(&left), i32(1))) &&
1379 Bits::getMaxBits(left, this) == 1) {
1380 return left;
1381 }
1382 // i64(bool(x)) == 1 ==> i32(bool(x))
1383 // i64(bool(x)) != 0 ==> i32(bool(x))
1384 if ((matches(curr, binary(EqInt64, any(&left), i64(1))) ||
1385 matches(curr, binary(NeInt64, any(&left), i64(0)))) &&
1386 Bits::getMaxBits(left, this) == 1) {
1387 return builder.makeUnary(WrapInt64, left);
1388 }
1389 // bool(x) != 1 ==> !bool(x)
1390 if (matches(curr, binary(Abstract::Ne, any(&left), ival(1))) &&
1391 Bits::getMaxBits(curr->left, this) == 1) {
1392 return builder.makeUnary(Abstract::getUnary(type, Abstract::EqZ), left);
1393 }
1394
1395 // Operations on all 1s
1396 // x & -1 ==> x
1397 if (matches(curr, binary(Abstract::And, any(&left), ival(-1)))) {
1398 return left;
1399 }
1400 // x | -1 ==> -1
1401 if (matches(curr, binary(Abstract::Or, pure(&left), ival(-1)))) {
1402 return right;
1403 }
1404 // (signed)x % -1 ==> 0
1405 if (matches(curr, binary(Abstract::RemS, pure(&left), ival(-1)))) {
1406 right->value = Literal::makeZero(type);
1407 return right;
1408 }
1409 // (unsigned)x > -1 ==> 0
1410 if (matches(curr, binary(Abstract::GtU, pure(&left), ival(-1)))) {
1411 right->value = Literal::makeZero(Type::i32);
1412 right->type = Type::i32;
1413 return right;
1414 }
1415 // (unsigned)x < -1 ==> x != -1
1416 // Friendlier to JS emitting as we don't need to write an unsigned -1 value
1417 // which is large.
1418 if (matches(curr, binary(Abstract::LtU, any(), ival(-1)))) {
1419 curr->op = Abstract::getBinary(type, Abstract::Ne);
1420 return curr;
1421 }
1422 // x * -1 ==> 0 - x
1423 if (matches(curr, binary(Abstract::Mul, any(&left), ival(-1)))) {
1424 right->value = Literal::makeZero(type);
1425 curr->op = Abstract::getBinary(type, Abstract::Sub);
1426 curr->left = right;
1427 curr->right = left;
1428 return curr;
1429 }
1430 // (unsigned)x <= -1 ==> 1
1431 if (matches(curr, binary(Abstract::LeU, pure(&left), ival(-1)))) {
1432 right->value = Literal::makeOne(Type::i32);
1433 right->type = Type::i32;
1434 return right;
1435 }
1436 {
1437 // ~(1 << x) aka (1 << x) ^ -1 ==> rotl(-2, x)
1438 Expression* x;
1439 if (matches(curr,
1440 binary(Abstract::Xor,
1441 binary(Abstract::Shl, ival(1), any(&x)),
1442 ival(-1)))) {
1443 curr->op = Abstract::getBinary(type, Abstract::RotL);
1444 right->value = Literal::makeFromInt32(-2, type);
1445 curr->left = right;
1446 curr->right = x;
1447 return curr;
1448 }
1449 }
1450 {
1451 // Wasm binary encoding uses signed LEBs, which slightly favor negative
1452 // numbers: -64 is more efficient than +64 etc., as well as other powers
1453 // of two 7 bits etc. higher. we therefore prefer x - -64 over x + 64. in
1454 // theory we could just prefer negative numbers over positive, but that
1455 // can have bad effects on gzip compression (as it would mean more
1456 // subtractions than the more common additions). TODO: Simplify this by
1457 // adding an ival matcher than can bind int64_t vars.
1458 int64_t value;
1459 if ((matches(curr, binary(Abstract::Add, any(), ival(&value))) ||
1460 matches(curr, binary(Abstract::Sub, any(), ival(&value)))) &&
1461 (value == 0x40 || value == 0x2000 || value == 0x100000 ||
1462 value == 0x8000000 || value == 0x400000000LL ||
1463 value == 0x20000000000LL || value == 0x1000000000000LL ||
1464 value == 0x80000000000000LL || value == 0x4000000000000000LL)) {
1465 right->value = right->value.neg();
1466 if (matches(curr, binary(Abstract::Add, any(), constant()))) {
1467 curr->op = Abstract::getBinary(type, Abstract::Sub);
1468 } else {
1469 curr->op = Abstract::getBinary(type, Abstract::Add);
1470 }
1471 return curr;
1472 }
1473 }
1474 {
1475 double value;
1476 if (matches(curr, binary(Abstract::Sub, any(), fval(&value))) &&
1477 value == 0.0) {
1478 // x - (-0.0) ==> x + 0.0
1479 if (std::signbit(value)) {
1480 curr->op = Abstract::getBinary(type, Abstract::Add);
1481 right->value = right->value.neg();
1482 return curr;
1483 } else if (fastMath) {
1484 // x - 0.0 ==> x
1485 return curr->left;
1486 }
1487 }
1488 }
1489 {
1490 // x + (-0.0) ==> x
1491 double value;
1492 if (fastMath &&
1493 matches(curr, binary(Abstract::Add, any(), fval(&value))) &&
1494 value == 0.0 && std::signbit(value)) {
1495 return curr->left;
1496 }
1497 }
1498 // x * -1.0 ==> -x
1499 if (fastMath && matches(curr, binary(Abstract::Mul, any(), fval(-1.0)))) {
1500 return builder.makeUnary(Abstract::getUnary(type, Abstract::Neg), left);
1501 }
1502 if (matches(curr, binary(Abstract::Mul, any(&left), constant(1))) ||
1503 matches(curr, binary(Abstract::DivS, any(&left), constant(1))) ||
1504 matches(curr, binary(Abstract::DivU, any(&left), constant(1)))) {
1505 if (curr->type.isInteger() || fastMath) {
1506 return left;
1507 }
1508 }
1509 return nullptr;
1510 }
1511
1512 // optimize trivial math operations, given that the left side of a binary
1513 // is a constant. since we canonicalize constants to the right for symmetrical
1514 // operations, we only need to handle asymmetrical ones here
1515 // TODO: templatize on type?
optimizeWithConstantOnLeftwasm::OptimizeInstructions1516 Expression* optimizeWithConstantOnLeft(Binary* binary) {
1517 auto type = binary->left->type;
1518 auto* left = binary->left->cast<Const>();
1519 if (type.isInteger()) {
1520 // operations on zero
1521 if (left->value == Literal::makeFromInt32(0, type)) {
1522 if ((binary->op == Abstract::getBinary(type, Abstract::Shl) ||
1523 binary->op == Abstract::getBinary(type, Abstract::ShrU) ||
1524 binary->op == Abstract::getBinary(type, Abstract::ShrS)) &&
1525 !effects(binary->right).hasSideEffects()) {
1526 return binary->left;
1527 }
1528 }
1529 }
1530 return nullptr;
1531 }
1532
1533 // TODO: templatize on type?
optimizeRelationalwasm::OptimizeInstructions1534 Expression* optimizeRelational(Binary* binary) {
1535 // TODO: inequalities can also work, if the constants do not overflow
1536 auto type = binary->right->type;
1537 // integer math, even on 2s complement, allows stuff like
1538 // x + 5 == 7
1539 // =>
1540 // x == 2
1541 if (binary->left->type.isInteger()) {
1542 if (binary->op == Abstract::getBinary(type, Abstract::Eq) ||
1543 binary->op == Abstract::getBinary(type, Abstract::Ne)) {
1544 if (auto* left = binary->left->dynCast<Binary>()) {
1545 if (left->op == Abstract::getBinary(type, Abstract::Add) ||
1546 left->op == Abstract::getBinary(type, Abstract::Sub)) {
1547 if (auto* leftConst = left->right->dynCast<Const>()) {
1548 if (auto* rightConst = binary->right->dynCast<Const>()) {
1549 return combineRelationalConstants(
1550 binary, left, leftConst, nullptr, rightConst);
1551 } else if (auto* rightBinary = binary->right->dynCast<Binary>()) {
1552 if (rightBinary->op ==
1553 Abstract::getBinary(type, Abstract::Add) ||
1554 rightBinary->op ==
1555 Abstract::getBinary(type, Abstract::Sub)) {
1556 if (auto* rightConst = rightBinary->right->dynCast<Const>()) {
1557 return combineRelationalConstants(
1558 binary, left, leftConst, rightBinary, rightConst);
1559 }
1560 }
1561 }
1562 }
1563 }
1564 }
1565 }
1566 }
1567 return nullptr;
1568 }
1569
deduplicateUnarywasm::OptimizeInstructions1570 Expression* deduplicateUnary(Unary* unaryOuter) {
1571 if (auto* unaryInner = unaryOuter->value->dynCast<Unary>()) {
1572 if (unaryInner->op == unaryOuter->op) {
1573 switch (unaryInner->op) {
1574 case NegFloat32:
1575 case NegFloat64: {
1576 // neg(neg(x)) ==> x
1577 return unaryInner->value;
1578 }
1579 case AbsFloat32:
1580 case CeilFloat32:
1581 case FloorFloat32:
1582 case TruncFloat32:
1583 case NearestFloat32:
1584 case AbsFloat64:
1585 case CeilFloat64:
1586 case FloorFloat64:
1587 case TruncFloat64:
1588 case NearestFloat64: {
1589 // unaryOp(unaryOp(x)) ==> unaryOp(x)
1590 return unaryInner;
1591 }
1592 case ExtendS8Int32:
1593 case ExtendS16Int32: {
1594 assert(getModule()->features.hasSignExt());
1595 return unaryInner;
1596 }
1597 case EqZInt32: {
1598 // eqz(eqz(bool(x))) ==> bool(x)
1599 if (Bits::getMaxBits(unaryInner->value, this) == 1) {
1600 return unaryInner->value;
1601 }
1602 break;
1603 }
1604 default: {
1605 }
1606 }
1607 }
1608 }
1609 return nullptr;
1610 }
1611
deduplicateBinarywasm::OptimizeInstructions1612 Expression* deduplicateBinary(Binary* outer) {
1613 Type type = outer->type;
1614 if (type.isInteger()) {
1615 if (auto* inner = outer->right->dynCast<Binary>()) {
1616 if (outer->op == inner->op) {
1617 if (!EffectAnalyzer(
1618 getPassOptions(), getModule()->features, outer->left)
1619 .hasSideEffects()) {
1620 if (ExpressionAnalyzer::equal(inner->left, outer->left)) {
1621 // x - (x - y) ==> y
1622 // x ^ (x ^ y) ==> y
1623 if (outer->op == Abstract::getBinary(type, Abstract::Sub) ||
1624 outer->op == Abstract::getBinary(type, Abstract::Xor)) {
1625 return inner->right;
1626 }
1627 // x & (x & y) ==> x & y
1628 // x | (x | y) ==> x | y
1629 if (outer->op == Abstract::getBinary(type, Abstract::And) ||
1630 outer->op == Abstract::getBinary(type, Abstract::Or)) {
1631 return inner;
1632 }
1633 }
1634 if (ExpressionAnalyzer::equal(inner->right, outer->left) &&
1635 canReorder(outer->left, inner->left)) {
1636 // x ^ (y ^ x) ==> y
1637 // (note that we need the check for reordering here because if
1638 // e.g. y writes to a local that x reads, the second appearance
1639 // of x would be different from the first)
1640 if (outer->op == Abstract::getBinary(type, Abstract::Xor)) {
1641 return inner->left;
1642 }
1643
1644 // x & (y & x) ==> y & x
1645 // x | (y | x) ==> y | x
1646 // (here we need the check for reordering for the more obvious
1647 // reason that previously x appeared before y, and now y appears
1648 // first; or, if we tried to emit x [&|] y here, reversing the
1649 // order, we'd be in the same situation as the previous comment)
1650 if (outer->op == Abstract::getBinary(type, Abstract::And) ||
1651 outer->op == Abstract::getBinary(type, Abstract::Or)) {
1652 return inner;
1653 }
1654 }
1655 }
1656 }
1657 }
1658 if (auto* inner = outer->left->dynCast<Binary>()) {
1659 if (outer->op == inner->op) {
1660 if (!EffectAnalyzer(
1661 getPassOptions(), getModule()->features, outer->right)
1662 .hasSideEffects()) {
1663 if (ExpressionAnalyzer::equal(inner->right, outer->right)) {
1664 // (x ^ y) ^ y ==> x
1665 if (outer->op == Abstract::getBinary(type, Abstract::Xor)) {
1666 return inner->left;
1667 }
1668 // (x % y) % y ==> x % y
1669 // (x & y) & y ==> x & y
1670 // (x | y) | y ==> x | y
1671 if (outer->op == Abstract::getBinary(type, Abstract::RemS) ||
1672 outer->op == Abstract::getBinary(type, Abstract::RemU) ||
1673 outer->op == Abstract::getBinary(type, Abstract::And) ||
1674 outer->op == Abstract::getBinary(type, Abstract::Or)) {
1675 return inner;
1676 }
1677 }
1678 // See comments in the parallel code earlier about ordering here.
1679 if (ExpressionAnalyzer::equal(inner->left, outer->right) &&
1680 canReorder(inner->left, inner->right)) {
1681 // (x ^ y) ^ x ==> y
1682 if (outer->op == Abstract::getBinary(type, Abstract::Xor)) {
1683 return inner->right;
1684 }
1685 // (x & y) & x ==> x & y
1686 // (x | y) | x ==> x | y
1687 if (outer->op == Abstract::getBinary(type, Abstract::And) ||
1688 outer->op == Abstract::getBinary(type, Abstract::Or)) {
1689 return inner;
1690 }
1691 }
1692 }
1693 }
1694 }
1695 }
1696 return nullptr;
1697 }
1698
1699 // given a relational binary with a const on both sides, combine the constants
1700 // left is also a binary, and has a constant; right may be just a constant, in
1701 // which case right is nullptr
combineRelationalConstantswasm::OptimizeInstructions1702 Expression* combineRelationalConstants(Binary* binary,
1703 Binary* left,
1704 Const* leftConst,
1705 Binary* right,
1706 Const* rightConst) {
1707 auto type = binary->right->type;
1708 // we fold constants to the right
1709 Literal extra = leftConst->value;
1710 if (left->op == Abstract::getBinary(type, Abstract::Sub)) {
1711 extra = extra.neg();
1712 }
1713 if (right && right->op == Abstract::getBinary(type, Abstract::Sub)) {
1714 extra = extra.neg();
1715 }
1716 rightConst->value = rightConst->value.sub(extra);
1717 binary->left = left->left;
1718 return binary;
1719 }
1720
optimizeMemoryCopywasm::OptimizeInstructions1721 Expression* optimizeMemoryCopy(MemoryCopy* memCopy) {
1722 PassOptions options = getPassOptions();
1723
1724 if (options.ignoreImplicitTraps) {
1725 if (ExpressionAnalyzer::equal(memCopy->dest, memCopy->source)) {
1726 // memory.copy(x, x, sz) ==> {drop(x), drop(x), drop(sz)}
1727 Builder builder(*getModule());
1728 return builder.makeBlock({builder.makeDrop(memCopy->dest),
1729 builder.makeDrop(memCopy->source),
1730 builder.makeDrop(memCopy->size)});
1731 }
1732 }
1733
1734 // memory.copy(dst, src, C) ==> store(dst, load(src))
1735 if (auto* csize = memCopy->size->dynCast<Const>()) {
1736 auto bytes = csize->value.geti32();
1737 Builder builder(*getModule());
1738
1739 switch (bytes) {
1740 case 0: {
1741 if (options.ignoreImplicitTraps) {
1742 // memory.copy(dst, src, 0) ==> {drop(dst), drop(src)}
1743 return builder.makeBlock({builder.makeDrop(memCopy->dest),
1744 builder.makeDrop(memCopy->source)});
1745 }
1746 break;
1747 }
1748 case 1:
1749 case 2:
1750 case 4: {
1751 return builder.makeStore(
1752 bytes, // bytes
1753 0, // offset
1754 1, // align
1755 memCopy->dest,
1756 builder.makeLoad(bytes, false, 0, 1, memCopy->source, Type::i32),
1757 Type::i32);
1758 }
1759 case 8: {
1760 return builder.makeStore(
1761 bytes, // bytes
1762 0, // offset
1763 1, // align
1764 memCopy->dest,
1765 builder.makeLoad(bytes, false, 0, 1, memCopy->source, Type::i64),
1766 Type::i64);
1767 }
1768 case 16: {
1769 if (options.shrinkLevel == 0) {
1770 // This adds an extra 2 bytes so apply it only for
1771 // minimal shrink level
1772 if (getModule()->features.hasSIMD()) {
1773 return builder.makeStore(
1774 bytes, // bytes
1775 0, // offset
1776 1, // align
1777 memCopy->dest,
1778 builder.makeLoad(
1779 bytes, false, 0, 1, memCopy->source, Type::v128),
1780 Type::v128);
1781 }
1782 }
1783 }
1784 default: {
1785 }
1786 }
1787 }
1788 return nullptr;
1789 }
1790
1791 // given a binary expression with equal children and no side effects in
1792 // either, we can fold various things
optimizeBinaryWithEqualEffectlessChildrenwasm::OptimizeInstructions1793 Expression* optimizeBinaryWithEqualEffectlessChildren(Binary* binary) {
1794 // TODO add: perhaps worth doing 2*x if x is quite large?
1795 switch (binary->op) {
1796 case SubInt32:
1797 case XorInt32:
1798 case SubInt64:
1799 case XorInt64:
1800 return LiteralUtils::makeZero(binary->left->type, *getModule());
1801 case NeInt32:
1802 case LtSInt32:
1803 case LtUInt32:
1804 case GtSInt32:
1805 case GtUInt32:
1806 case NeInt64:
1807 case LtSInt64:
1808 case LtUInt64:
1809 case GtSInt64:
1810 case GtUInt64:
1811 return LiteralUtils::makeZero(Type::i32, *getModule());
1812 case AndInt32:
1813 case OrInt32:
1814 case AndInt64:
1815 case OrInt64:
1816 return binary->left;
1817 case EqInt32:
1818 case LeSInt32:
1819 case LeUInt32:
1820 case GeSInt32:
1821 case GeUInt32:
1822 case EqInt64:
1823 case LeSInt64:
1824 case LeUInt64:
1825 case GeSInt64:
1826 case GeUInt64:
1827 return LiteralUtils::makeFromInt32(1, Type::i32, *getModule());
1828 default:
1829 return nullptr;
1830 }
1831 }
1832
invertBinaryOpwasm::OptimizeInstructions1833 BinaryOp invertBinaryOp(BinaryOp op) {
1834 // use de-morgan's laws
1835 switch (op) {
1836 case EqInt32:
1837 return NeInt32;
1838 case NeInt32:
1839 return EqInt32;
1840 case LtSInt32:
1841 return GeSInt32;
1842 case LtUInt32:
1843 return GeUInt32;
1844 case LeSInt32:
1845 return GtSInt32;
1846 case LeUInt32:
1847 return GtUInt32;
1848 case GtSInt32:
1849 return LeSInt32;
1850 case GtUInt32:
1851 return LeUInt32;
1852 case GeSInt32:
1853 return LtSInt32;
1854 case GeUInt32:
1855 return LtUInt32;
1856
1857 case EqInt64:
1858 return NeInt64;
1859 case NeInt64:
1860 return EqInt64;
1861 case LtSInt64:
1862 return GeSInt64;
1863 case LtUInt64:
1864 return GeUInt64;
1865 case LeSInt64:
1866 return GtSInt64;
1867 case LeUInt64:
1868 return GtUInt64;
1869 case GtSInt64:
1870 return LeSInt64;
1871 case GtUInt64:
1872 return LeUInt64;
1873 case GeSInt64:
1874 return LtSInt64;
1875 case GeUInt64:
1876 return LtUInt64;
1877
1878 case EqFloat32:
1879 return NeFloat32;
1880 case NeFloat32:
1881 return EqFloat32;
1882
1883 case EqFloat64:
1884 return NeFloat64;
1885 case NeFloat64:
1886 return EqFloat64;
1887
1888 default:
1889 return InvalidBinary;
1890 }
1891 }
1892
makeUnsignedBinaryOpwasm::OptimizeInstructions1893 BinaryOp makeUnsignedBinaryOp(BinaryOp op) {
1894 switch (op) {
1895 case DivSInt32:
1896 return DivUInt32;
1897 case RemSInt32:
1898 return RemUInt32;
1899 case ShrSInt32:
1900 return ShrUInt32;
1901 case LtSInt32:
1902 return LtUInt32;
1903 case LeSInt32:
1904 return LeUInt32;
1905 case GtSInt32:
1906 return GtUInt32;
1907 case GeSInt32:
1908 return GeUInt32;
1909
1910 case DivSInt64:
1911 return DivUInt64;
1912 case RemSInt64:
1913 return RemUInt64;
1914 case ShrSInt64:
1915 return ShrUInt64;
1916 case LtSInt64:
1917 return LtUInt64;
1918 case LeSInt64:
1919 return LeUInt64;
1920 case GtSInt64:
1921 return GtUInt64;
1922 case GeSInt64:
1923 return GeUInt64;
1924
1925 default:
1926 return InvalidBinary;
1927 }
1928 }
1929
isSymmetricwasm::OptimizeInstructions1930 bool isSymmetric(Binary* binary) {
1931 if (Properties::isSymmetric(binary)) {
1932 return true;
1933 }
1934 switch (binary->op) {
1935 case AddFloat32:
1936 case MulFloat32:
1937 case AddFloat64:
1938 case MulFloat64: {
1939 // If the LHS is known to be non-NaN, the operands can commute.
1940 // We don't care about the RHS because right now we only know if
1941 // an expression is non-NaN if it is constant, but if the RHS is
1942 // constant, then this expression is already canonicalized.
1943 if (auto* c = binary->left->dynCast<Const>()) {
1944 return !c->value.isNaN();
1945 }
1946 return false;
1947 }
1948 default:
1949 return false;
1950 }
1951 }
1952 };
1953
createOptimizeInstructionsPass()1954 Pass* createOptimizeInstructionsPass() { return new OptimizeInstructions(); }
1955
1956 } // namespace wasm
1957