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