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 #ifndef wasm_ir_cost_h
18 #define wasm_ir_cost_h
19 
20 #include <wasm-traversal.h>
21 #include <wasm.h>
22 
23 namespace wasm {
24 
25 // Measure the execution cost of an AST. Very handwave-ey
26 
27 struct CostAnalyzer : public Visitor<CostAnalyzer, Index> {
CostAnalyzerCostAnalyzer28   CostAnalyzer(Expression* ast) { cost = visit(ast); }
29 
30   Index cost;
31 
maybeVisitCostAnalyzer32   Index maybeVisit(Expression* curr) { return curr ? visit(curr) : 0; }
33 
visitBlockCostAnalyzer34   Index visitBlock(Block* curr) {
35     Index ret = 0;
36     for (auto* child : curr->list) {
37       ret += visit(child);
38     }
39     return ret;
40   }
visitIfCostAnalyzer41   Index visitIf(If* curr) {
42     return 1 + visit(curr->condition) +
43            std::max(visit(curr->ifTrue), maybeVisit(curr->ifFalse));
44   }
visitLoopCostAnalyzer45   Index visitLoop(Loop* curr) { return 5 * visit(curr->body); }
visitBreakCostAnalyzer46   Index visitBreak(Break* curr) {
47     return 1 + maybeVisit(curr->value) + maybeVisit(curr->condition);
48   }
visitSwitchCostAnalyzer49   Index visitSwitch(Switch* curr) {
50     return 2 + visit(curr->condition) + maybeVisit(curr->value);
51   }
visitCallCostAnalyzer52   Index visitCall(Call* curr) {
53     // XXX this does not take into account if the call is to an import, which
54     //     may be costlier in general
55     Index ret = 4;
56     for (auto* child : curr->operands) {
57       ret += visit(child);
58     }
59     return ret;
60   }
visitCallIndirectCostAnalyzer61   Index visitCallIndirect(CallIndirect* curr) {
62     Index ret = 6 + visit(curr->target);
63     for (auto* child : curr->operands) {
64       ret += visit(child);
65     }
66     return ret;
67   }
visitLocalGetCostAnalyzer68   Index visitLocalGet(LocalGet* curr) { return 0; }
visitLocalSetCostAnalyzer69   Index visitLocalSet(LocalSet* curr) { return 1; }
visitGlobalGetCostAnalyzer70   Index visitGlobalGet(GlobalGet* curr) { return 1; }
visitGlobalSetCostAnalyzer71   Index visitGlobalSet(GlobalSet* curr) { return 2; }
visitLoadCostAnalyzer72   Index visitLoad(Load* curr) {
73     return 1 + visit(curr->ptr) + 10 * curr->isAtomic;
74   }
visitStoreCostAnalyzer75   Index visitStore(Store* curr) {
76     return 2 + visit(curr->ptr) + visit(curr->value) + 10 * curr->isAtomic;
77   }
visitAtomicRMWCostAnalyzer78   Index visitAtomicRMW(AtomicRMW* curr) { return 100; }
visitAtomicCmpxchgCostAnalyzer79   Index visitAtomicCmpxchg(AtomicCmpxchg* curr) { return 100; }
visitConstCostAnalyzer80   Index visitConst(Const* curr) { return 1; }
visitUnaryCostAnalyzer81   Index visitUnary(Unary* curr) {
82     Index ret = 0;
83     switch (curr->op) {
84       case ClzInt32:
85       case CtzInt32:
86       case PopcntInt32:
87       case NegFloat32:
88       case AbsFloat32:
89       case CeilFloat32:
90       case FloorFloat32:
91       case TruncFloat32:
92       case NearestFloat32:
93       case ClzInt64:
94       case CtzInt64:
95       case PopcntInt64:
96       case NegFloat64:
97       case AbsFloat64:
98       case CeilFloat64:
99       case FloorFloat64:
100       case TruncFloat64:
101       case NearestFloat64:
102       case EqZInt32:
103       case EqZInt64:
104       case ExtendSInt32:
105       case ExtendUInt32:
106       case WrapInt64:
107       case PromoteFloat32:
108       case DemoteFloat64:
109       case TruncSFloat32ToInt32:
110       case TruncUFloat32ToInt32:
111       case TruncSFloat64ToInt32:
112       case TruncUFloat64ToInt32:
113       case ReinterpretFloat32:
114       case TruncSFloat32ToInt64:
115       case TruncUFloat32ToInt64:
116       case TruncSFloat64ToInt64:
117       case TruncUFloat64ToInt64:
118       case ReinterpretFloat64:
119       case ReinterpretInt32:
120       case ConvertSInt32ToFloat32:
121       case ConvertUInt32ToFloat32:
122       case ConvertSInt64ToFloat32:
123       case ConvertUInt64ToFloat32:
124       case ReinterpretInt64:
125       case ConvertSInt32ToFloat64:
126       case ConvertUInt32ToFloat64:
127       case ConvertSInt64ToFloat64:
128       case ConvertUInt64ToFloat64:
129       case ExtendS8Int32:
130       case ExtendS16Int32:
131       case ExtendS8Int64:
132       case ExtendS16Int64:
133       case ExtendS32Int64:
134       case TruncSatSFloat32ToInt32:
135       case TruncSatUFloat32ToInt32:
136       case TruncSatSFloat64ToInt32:
137       case TruncSatUFloat64ToInt32:
138       case TruncSatSFloat32ToInt64:
139       case TruncSatUFloat32ToInt64:
140       case TruncSatSFloat64ToInt64:
141       case TruncSatUFloat64ToInt64:
142         ret = 1;
143         break;
144       case SqrtFloat32:
145       case SqrtFloat64:
146         ret = 2;
147         break;
148       case SplatVecI8x16:
149       case SplatVecI16x8:
150       case SplatVecI32x4:
151       case SplatVecI64x2:
152       case SplatVecF32x4:
153       case SplatVecF64x2:
154       case NotVec128:
155       case AbsVecI8x16:
156       case NegVecI8x16:
157       case AnyTrueVecI8x16:
158       case AllTrueVecI8x16:
159       case BitmaskVecI8x16:
160       case AbsVecI16x8:
161       case NegVecI16x8:
162       case AnyTrueVecI16x8:
163       case AllTrueVecI16x8:
164       case BitmaskVecI16x8:
165       case AbsVecI32x4:
166       case NegVecI32x4:
167       case AnyTrueVecI32x4:
168       case AllTrueVecI32x4:
169       case BitmaskVecI32x4:
170       case NegVecI64x2:
171       case AnyTrueVecI64x2:
172       case AllTrueVecI64x2:
173       case AbsVecF32x4:
174       case NegVecF32x4:
175       case SqrtVecF32x4:
176       case CeilVecF32x4:
177       case FloorVecF32x4:
178       case TruncVecF32x4:
179       case NearestVecF32x4:
180       case AbsVecF64x2:
181       case NegVecF64x2:
182       case SqrtVecF64x2:
183       case CeilVecF64x2:
184       case FloorVecF64x2:
185       case TruncVecF64x2:
186       case NearestVecF64x2:
187       case TruncSatSVecF32x4ToVecI32x4:
188       case TruncSatUVecF32x4ToVecI32x4:
189       case TruncSatSVecF64x2ToVecI64x2:
190       case TruncSatUVecF64x2ToVecI64x2:
191       case ConvertSVecI32x4ToVecF32x4:
192       case ConvertUVecI32x4ToVecF32x4:
193       case ConvertSVecI64x2ToVecF64x2:
194       case ConvertUVecI64x2ToVecF64x2:
195       case WidenLowSVecI8x16ToVecI16x8:
196       case WidenHighSVecI8x16ToVecI16x8:
197       case WidenLowUVecI8x16ToVecI16x8:
198       case WidenHighUVecI8x16ToVecI16x8:
199       case WidenLowSVecI16x8ToVecI32x4:
200       case WidenHighSVecI16x8ToVecI32x4:
201       case WidenLowUVecI16x8ToVecI32x4:
202       case WidenHighUVecI16x8ToVecI32x4:
203         return 1;
204       case InvalidUnary:
205         WASM_UNREACHABLE("invalid unary op");
206     }
207     return ret + visit(curr->value);
208   }
visitBinaryCostAnalyzer209   Index visitBinary(Binary* curr) {
210     Index ret = 0;
211     switch (curr->op) {
212       case AddInt32:
213         ret = 1;
214         break;
215       case SubInt32:
216         ret = 1;
217         break;
218       case MulInt32:
219         ret = 2;
220         break;
221       case DivSInt32:
222         ret = 3;
223         break;
224       case DivUInt32:
225         ret = 3;
226         break;
227       case RemSInt32:
228         ret = 3;
229         break;
230       case RemUInt32:
231         ret = 3;
232         break;
233       case AndInt32:
234         ret = 1;
235         break;
236       case OrInt32:
237         ret = 1;
238         break;
239       case XorInt32:
240         ret = 1;
241         break;
242       case ShlInt32:
243         ret = 1;
244         break;
245       case ShrUInt32:
246         ret = 1;
247         break;
248       case ShrSInt32:
249         ret = 1;
250         break;
251       case RotLInt32:
252         ret = 1;
253         break;
254       case RotRInt32:
255         ret = 1;
256         break;
257       case AddInt64:
258         ret = 1;
259         break;
260       case SubInt64:
261         ret = 1;
262         break;
263       case MulInt64:
264         ret = 2;
265         break;
266       case DivSInt64:
267         ret = 3;
268         break;
269       case DivUInt64:
270         ret = 3;
271         break;
272       case RemSInt64:
273         ret = 3;
274         break;
275       case RemUInt64:
276         ret = 3;
277         break;
278       case AndInt64:
279         ret = 1;
280         break;
281       case OrInt64:
282         ret = 1;
283         break;
284       case XorInt64:
285         ret = 1;
286         break;
287       case ShlInt64:
288         ret = 1;
289         break;
290       case ShrUInt64:
291         ret = 1;
292         break;
293       case ShrSInt64:
294         ret = 1;
295         break;
296       case RotLInt64:
297         ret = 1;
298         break;
299       case RotRInt64:
300         ret = 1;
301         break;
302       case AddFloat32:
303         ret = 1;
304         break;
305       case SubFloat32:
306         ret = 1;
307         break;
308       case MulFloat32:
309         ret = 2;
310         break;
311       case DivFloat32:
312         ret = 3;
313         break;
314       case CopySignFloat32:
315         ret = 1;
316         break;
317       case MinFloat32:
318         ret = 1;
319         break;
320       case MaxFloat32:
321         ret = 1;
322         break;
323       case AddFloat64:
324         ret = 1;
325         break;
326       case SubFloat64:
327         ret = 1;
328         break;
329       case MulFloat64:
330         ret = 2;
331         break;
332       case DivFloat64:
333         ret = 3;
334         break;
335       case CopySignFloat64:
336         ret = 1;
337         break;
338       case MinFloat64:
339         ret = 1;
340         break;
341       case MaxFloat64:
342         ret = 1;
343         break;
344       case LtUInt32:
345         ret = 1;
346         break;
347       case LtSInt32:
348         ret = 1;
349         break;
350       case LeUInt32:
351         ret = 1;
352         break;
353       case LeSInt32:
354         ret = 1;
355         break;
356       case GtUInt32:
357         ret = 1;
358         break;
359       case GtSInt32:
360         ret = 1;
361         break;
362       case GeUInt32:
363         ret = 1;
364         break;
365       case GeSInt32:
366         ret = 1;
367         break;
368       case LtUInt64:
369         ret = 1;
370         break;
371       case LtSInt64:
372         ret = 1;
373         break;
374       case LeUInt64:
375         ret = 1;
376         break;
377       case LeSInt64:
378         ret = 1;
379         break;
380       case GtUInt64:
381         ret = 1;
382         break;
383       case GtSInt64:
384         ret = 1;
385         break;
386       case GeUInt64:
387         ret = 1;
388         break;
389       case GeSInt64:
390         ret = 1;
391         break;
392       case LtFloat32:
393         ret = 1;
394         break;
395       case GtFloat32:
396         ret = 1;
397         break;
398       case LeFloat32:
399         ret = 1;
400         break;
401       case GeFloat32:
402         ret = 1;
403         break;
404       case LtFloat64:
405         ret = 1;
406         break;
407       case GtFloat64:
408         ret = 1;
409         break;
410       case LeFloat64:
411         ret = 1;
412         break;
413       case GeFloat64:
414         ret = 1;
415         break;
416       case EqInt32:
417         ret = 1;
418         break;
419       case NeInt32:
420         ret = 1;
421         break;
422       case EqInt64:
423         ret = 1;
424         break;
425       case NeInt64:
426         ret = 1;
427         break;
428       case EqFloat32:
429         ret = 1;
430         break;
431       case NeFloat32:
432         ret = 1;
433         break;
434       case EqFloat64:
435         ret = 1;
436         break;
437       case NeFloat64:
438         ret = 1;
439         break;
440       case EqVecI8x16:
441         ret = 1;
442         break;
443       case NeVecI8x16:
444         ret = 1;
445         break;
446       case LtSVecI8x16:
447         ret = 1;
448         break;
449       case LtUVecI8x16:
450         ret = 1;
451         break;
452       case LeSVecI8x16:
453         ret = 1;
454         break;
455       case LeUVecI8x16:
456         ret = 1;
457         break;
458       case GtSVecI8x16:
459         ret = 1;
460         break;
461       case GtUVecI8x16:
462         ret = 1;
463         break;
464       case GeSVecI8x16:
465         ret = 1;
466         break;
467       case GeUVecI8x16:
468         ret = 1;
469         break;
470       case EqVecI16x8:
471         ret = 1;
472         break;
473       case NeVecI16x8:
474         ret = 1;
475         break;
476       case LtSVecI16x8:
477         ret = 1;
478         break;
479       case LtUVecI16x8:
480         ret = 1;
481         break;
482       case LeSVecI16x8:
483         ret = 1;
484         break;
485       case LeUVecI16x8:
486         ret = 1;
487         break;
488       case GtSVecI16x8:
489         ret = 1;
490         break;
491       case GtUVecI16x8:
492         ret = 1;
493         break;
494       case GeSVecI16x8:
495         ret = 1;
496         break;
497       case GeUVecI16x8:
498         ret = 1;
499         break;
500       case EqVecI32x4:
501         ret = 1;
502         break;
503       case NeVecI32x4:
504         ret = 1;
505         break;
506       case LtSVecI32x4:
507         ret = 1;
508         break;
509       case LtUVecI32x4:
510         ret = 1;
511         break;
512       case LeSVecI32x4:
513         ret = 1;
514         break;
515       case LeUVecI32x4:
516         ret = 1;
517         break;
518       case GtSVecI32x4:
519         ret = 1;
520         break;
521       case GtUVecI32x4:
522         ret = 1;
523         break;
524       case GeSVecI32x4:
525         ret = 1;
526         break;
527       case GeUVecI32x4:
528         ret = 1;
529         break;
530       case EqVecF32x4:
531         ret = 1;
532         break;
533       case NeVecF32x4:
534         ret = 1;
535         break;
536       case LtVecF32x4:
537         ret = 1;
538         break;
539       case LeVecF32x4:
540         ret = 1;
541         break;
542       case GtVecF32x4:
543         ret = 1;
544         break;
545       case GeVecF32x4:
546         ret = 1;
547         break;
548       case EqVecF64x2:
549         ret = 1;
550         break;
551       case NeVecF64x2:
552         ret = 1;
553         break;
554       case LtVecF64x2:
555         ret = 1;
556         break;
557       case LeVecF64x2:
558         ret = 1;
559         break;
560       case GtVecF64x2:
561         ret = 1;
562         break;
563       case GeVecF64x2:
564         ret = 1;
565         break;
566       case AndVec128:
567         ret = 1;
568         break;
569       case OrVec128:
570         ret = 1;
571         break;
572       case XorVec128:
573         ret = 1;
574         break;
575       case AndNotVec128:
576         ret = 1;
577         break;
578       case AddVecI8x16:
579         ret = 1;
580         break;
581       case AddSatSVecI8x16:
582         ret = 1;
583         break;
584       case AddSatUVecI8x16:
585         ret = 1;
586         break;
587       case SubVecI8x16:
588         ret = 1;
589         break;
590       case SubSatSVecI8x16:
591         ret = 1;
592         break;
593       case SubSatUVecI8x16:
594         ret = 1;
595         break;
596       case MulVecI8x16:
597         ret = 2;
598         break;
599       case MinSVecI8x16:
600         ret = 1;
601         break;
602       case MinUVecI8x16:
603         ret = 1;
604         break;
605       case MaxSVecI8x16:
606         ret = 1;
607         break;
608       case MaxUVecI8x16:
609         ret = 1;
610         break;
611       case AvgrUVecI8x16:
612         ret = 1;
613         break;
614       case AddVecI16x8:
615         ret = 1;
616         break;
617       case AddSatSVecI16x8:
618         ret = 1;
619         break;
620       case AddSatUVecI16x8:
621         ret = 1;
622         break;
623       case SubVecI16x8:
624         ret = 1;
625         break;
626       case SubSatSVecI16x8:
627         ret = 1;
628         break;
629       case SubSatUVecI16x8:
630         ret = 1;
631         break;
632       case MulVecI16x8:
633         ret = 2;
634         break;
635       case MinSVecI16x8:
636         ret = 1;
637         break;
638       case MinUVecI16x8:
639         ret = 1;
640         break;
641       case MaxSVecI16x8:
642         ret = 1;
643         break;
644       case MaxUVecI16x8:
645         ret = 1;
646         break;
647       case AvgrUVecI16x8:
648         ret = 1;
649         break;
650       case AddVecI32x4:
651         ret = 1;
652         break;
653       case SubVecI32x4:
654         ret = 1;
655         break;
656       case MulVecI32x4:
657         ret = 2;
658         break;
659       case MinSVecI32x4:
660         ret = 1;
661         break;
662       case MinUVecI32x4:
663         ret = 1;
664         break;
665       case MaxSVecI32x4:
666         ret = 1;
667         break;
668       case MaxUVecI32x4:
669         ret = 1;
670         break;
671       case DotSVecI16x8ToVecI32x4:
672         ret = 1;
673         break;
674       case AddVecI64x2:
675         ret = 1;
676         break;
677       case SubVecI64x2:
678         ret = 1;
679         break;
680       case MulVecI64x2:
681         ret = 1;
682         break;
683       case AddVecF32x4:
684         ret = 1;
685         break;
686       case SubVecF32x4:
687         ret = 1;
688         break;
689       case MulVecF32x4:
690         ret = 2;
691         break;
692       case DivVecF32x4:
693         ret = 3;
694         break;
695       case MinVecF32x4:
696         ret = 1;
697         break;
698       case MaxVecF32x4:
699         ret = 1;
700         break;
701       case PMinVecF32x4:
702         ret = 1;
703         break;
704       case PMaxVecF32x4:
705         ret = 1;
706         break;
707       case AddVecF64x2:
708         ret = 1;
709         break;
710       case SubVecF64x2:
711         ret = 1;
712         break;
713       case MulVecF64x2:
714         ret = 2;
715         break;
716       case DivVecF64x2:
717         ret = 3;
718         break;
719       case MinVecF64x2:
720         ret = 1;
721         break;
722       case MaxVecF64x2:
723         ret = 1;
724         break;
725       case PMinVecF64x2:
726         ret = 1;
727         break;
728       case PMaxVecF64x2:
729         ret = 1;
730         break;
731       case NarrowSVecI16x8ToVecI8x16:
732         ret = 1;
733         break;
734       case NarrowUVecI16x8ToVecI8x16:
735         ret = 1;
736         break;
737       case NarrowSVecI32x4ToVecI16x8:
738         ret = 1;
739         break;
740       case NarrowUVecI32x4ToVecI16x8:
741         ret = 1;
742         break;
743       case SwizzleVec8x16:
744         ret = 1;
745         break;
746       case InvalidBinary:
747         WASM_UNREACHABLE("invalid binary op");
748     }
749     return ret + visit(curr->left) + visit(curr->right);
750   }
visitSelectCostAnalyzer751   Index visitSelect(Select* curr) {
752     return 2 + visit(curr->condition) + visit(curr->ifTrue) +
753            visit(curr->ifFalse);
754   }
visitDropCostAnalyzer755   Index visitDrop(Drop* curr) { return visit(curr->value); }
visitReturnCostAnalyzer756   Index visitReturn(Return* curr) { return maybeVisit(curr->value); }
visitMemorySizeCostAnalyzer757   Index visitMemorySize(MemorySize* curr) { return 1; }
visitMemoryGrowCostAnalyzer758   Index visitMemoryGrow(MemoryGrow* curr) { return 100; }
visitRefNullCostAnalyzer759   Index visitRefNull(RefNull* curr) { return 1; }
visitRefIsNullCostAnalyzer760   Index visitRefIsNull(RefIsNull* curr) { return 1 + visit(curr->value); }
visitRefFuncCostAnalyzer761   Index visitRefFunc(RefFunc* curr) { return 1; }
visitRefEqCostAnalyzer762   Index visitRefEq(RefEq* curr) {
763     return 1 + visit(curr->left) + visit(curr->right);
764   }
visitTryCostAnalyzer765   Index visitTry(Try* curr) {
766     // We assume no exception will be thrown in most cases
767     return visit(curr->body);
768   }
visitThrowCostAnalyzer769   Index visitThrow(Throw* curr) { return 100; }
visitRethrowCostAnalyzer770   Index visitRethrow(Rethrow* curr) { return 100; }
visitBrOnExnCostAnalyzer771   Index visitBrOnExn(BrOnExn* curr) {
772     return 1 + visit(curr->exnref) + curr->sent.size();
773   }
visitNopCostAnalyzer774   Index visitNop(Nop* curr) { return 0; }
visitUnreachableCostAnalyzer775   Index visitUnreachable(Unreachable* curr) { return 0; }
776 };
777 
778 } // namespace wasm
779 
780 #endif // wasm_ir_cost_h
781