src/binaryen/src/ir/cost.h

   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 namespace wasm {
  21
  22 // Measure the execution cost of an AST. Very handwave-ey
  23
  24 struct CostAnalyzer : public Visitor<CostAnalyzer, Index> {
  25   CostAnalyzer(Expression *ast) {
  26     assert(ast);
  27     cost = visit(ast);
  28   }
  29
  30   Index cost;
  31
  32   Index maybeVisit(Expression* curr) {
  33     return curr ? visit(curr) : 0;
  34   }
  35
  36   Index visitBlock(Block *curr) {
  37     Index ret = 0;
  38     for (auto* child : curr->list) ret += visit(child);
  39     return ret;
  40   }
  41   Index visitIf(If *curr) {
  42     return 1 + visit(curr->condition) + std::max(visit(curr->ifTrue), maybeVisit(curr->ifFalse));
  43   }
  44   Index visitLoop(Loop *curr) {
  45     return 5 * visit(curr->body);
  46   }
  47   Index visitBreak(Break *curr) {
  48     return 1 + maybeVisit(curr->value) + maybeVisit(curr->condition);
  49   }
  50   Index visitSwitch(Switch *curr) {
  51     return 2 + visit(curr->condition) + maybeVisit(curr->value);
  52   }
  53   Index visitCall(Call *curr) {
  54     Index ret = 4;
  55     for (auto* child : curr->operands) ret += visit(child);
  56     return ret;
  57   }
  58   Index visitCallImport(CallImport *curr) {
  59     Index ret = 15;
  60     for (auto* child : curr->operands) ret += visit(child);
  61     return ret;
  62   }
  63   Index visitCallIndirect(CallIndirect *curr) {
  64     Index ret = 6 + visit(curr->target);
  65     for (auto* child : curr->operands) ret += visit(child);
  66     return ret;
  67   }
  68   Index visitGetLocal(GetLocal *curr) {
  69     return 0;
  70   }
  71   Index visitSetLocal(SetLocal *curr) {
  72     return 1;
  73   }
  74   Index visitGetGlobal(GetGlobal *curr) {
  75     return 1;
  76   }
  77   Index visitSetGlobal(SetGlobal *curr) {
  78     return 2;
  79   }
  80   Index visitLoad(Load *curr) {
  81     return 1 + visit(curr->ptr) + 10 * curr->isAtomic;
  82   }
  83   Index visitStore(Store *curr) {
  84     return 2 + visit(curr->ptr) + visit(curr->value) + 10 * curr->isAtomic;
  85   }
  86   Index visitAtomicRMW(AtomicRMW *curr) {
  87     return 100;
  88   }
  89   Index visitAtomicCmpxchg(AtomicCmpxchg* curr) {
  90     return 100;
  91   }
  92   Index visitConst(Const *curr) {
  93     return 1;
  94   }
  95   Index visitUnary(Unary *curr) {
  96     Index ret = 0;
  97     switch (curr->op) {
  98       case ClzInt32:
  99       case CtzInt32:
 100       case PopcntInt32:
 101       case NegFloat32:
 102       case AbsFloat32:
 103       case CeilFloat32:
 104       case FloorFloat32:
 105       case TruncFloat32:
 106       case NearestFloat32:
 107       case ClzInt64:
 108       case CtzInt64:
 109       case PopcntInt64:
 110       case NegFloat64:
 111       case AbsFloat64:
 112       case CeilFloat64:
 113       case FloorFloat64:
 114       case TruncFloat64:
 115       case NearestFloat64:
 116       case EqZInt32:
 117       case EqZInt64:
 118       case ExtendSInt32:
 119       case ExtendUInt32:
 120       case WrapInt64:
 121       case PromoteFloat32:
 122       case DemoteFloat64:
 123       case TruncSFloat32ToInt32:
 124       case TruncUFloat32ToInt32:
 125       case TruncSFloat64ToInt32:
 126       case TruncUFloat64ToInt32:
 127       case ReinterpretFloat32:
 128       case TruncSFloat32ToInt64:
 129       case TruncUFloat32ToInt64:
 130       case TruncSFloat64ToInt64:
 131       case TruncUFloat64ToInt64:
 132       case ReinterpretFloat64:
 133       case ReinterpretInt32:
 134       case ConvertSInt32ToFloat32:
 135       case ConvertUInt32ToFloat32:
 136       case ConvertSInt64ToFloat32:
 137       case ConvertUInt64ToFloat32:
 138       case ReinterpretInt64:
 139       case ConvertSInt32ToFloat64:
 140       case ConvertUInt32ToFloat64:
 141       case ConvertSInt64ToFloat64:
 142       case ConvertUInt64ToFloat64: ret = 1; break;
 143       case SqrtFloat32:
 144       case SqrtFloat64: ret = 2; break;
 145       default: WASM_UNREACHABLE();
 146     }
 147     return ret + visit(curr->value);
 148   }
 149   Index visitBinary(Binary *curr) {
 150     Index ret = 0;
 151     switch (curr->op) {
 152       case AddInt32:        ret = 1; break;
 153       case SubInt32:        ret = 1; break;
 154       case MulInt32:        ret = 2; break;
 155       case DivSInt32:       ret = 3; break;
 156       case DivUInt32:       ret = 3; break;
 157       case RemSInt32:       ret = 3; break;
 158       case RemUInt32:       ret = 3; break;
 159       case AndInt32:        ret = 1; break;
 160       case OrInt32:         ret = 1; break;
 161       case XorInt32:        ret = 1; break;
 162       case ShlInt32:        ret = 1; break;
 163       case ShrUInt32:       ret = 1; break;
 164       case ShrSInt32:       ret = 1; break;
 165       case RotLInt32:       ret = 1; break;
 166       case RotRInt32:       ret = 1; break;
 167       case AddInt64:        ret = 1; break;
 168       case SubInt64:        ret = 1; break;
 169       case MulInt64:        ret = 2; break;
 170       case DivSInt64:       ret = 3; break;
 171       case DivUInt64:       ret = 3; break;
 172       case RemSInt64:       ret = 3; break;
 173       case RemUInt64:       ret = 3; break;
 174       case AndInt64:        ret = 1; break;
 175       case OrInt64:         ret = 1; break;
 176       case XorInt64:        ret = 1; break;
 177       case ShlInt64:        ret = 1; break;
 178       case ShrUInt64:       ret = 1; break;
 179       case ShrSInt64:       ret = 1; break;
 180       case RotLInt64:       ret = 1; break;
 181       case RotRInt64:       ret = 1; break;
 182       case AddFloat32:      ret = 1; break;
 183       case SubFloat32:      ret = 1; break;
 184       case MulFloat32:      ret = 2; break;
 185       case DivFloat32:      ret = 3; break;
 186       case CopySignFloat32: ret = 1; break;
 187       case MinFloat32:      ret = 1; break;
 188       case MaxFloat32:      ret = 1; break;
 189       case AddFloat64:      ret = 1; break;
 190       case SubFloat64:      ret = 1; break;
 191       case MulFloat64:      ret = 2; break;
 192       case DivFloat64:      ret = 3; break;
 193       case CopySignFloat64: ret = 1; break;
 194       case MinFloat64:      ret = 1; break;
 195       case MaxFloat64:      ret = 1; break;
 196       case LtUInt32:        ret = 1; break;
 197       case LtSInt32:        ret = 1; break;
 198       case LeUInt32:        ret = 1; break;
 199       case LeSInt32:        ret = 1; break;
 200       case GtUInt32:        ret = 1; break;
 201       case GtSInt32:        ret = 1; break;
 202       case GeUInt32:        ret = 1; break;
 203       case GeSInt32:        ret = 1; break;
 204       case LtUInt64:        ret = 1; break;
 205       case LtSInt64:        ret = 1; break;
 206       case LeUInt64:        ret = 1; break;
 207       case LeSInt64:        ret = 1; break;
 208       case GtUInt64:        ret = 1; break;
 209       case GtSInt64:        ret = 1; break;
 210       case GeUInt64:        ret = 1; break;
 211       case GeSInt64:        ret = 1; break;
 212       case LtFloat32:       ret = 1; break;
 213       case GtFloat32:       ret = 1; break;
 214       case LeFloat32:       ret = 1; break;
 215       case GeFloat32:       ret = 1; break;
 216       case LtFloat64:       ret = 1; break;
 217       case GtFloat64:       ret = 1; break;
 218       case LeFloat64:       ret = 1; break;
 219       case GeFloat64:       ret = 1; break;
 220       case EqInt32:         ret = 1; break;
 221       case NeInt32:         ret = 1; break;
 222       case EqInt64:         ret = 1; break;
 223       case NeInt64:         ret = 1; break;
 224       case EqFloat32:       ret = 1; break;
 225       case NeFloat32:       ret = 1; break;
 226       case EqFloat64:       ret = 1; break;
 227       case NeFloat64:       ret = 1; break;
 228       default: WASM_UNREACHABLE();
 229     }
 230     return ret + visit(curr->left) + visit(curr->right);
 231   }
 232   Index visitSelect(Select *curr) {
 233     return 2 + visit(curr->condition) + visit(curr->ifTrue) + visit(curr->ifFalse);
 234   }
 235   Index visitDrop(Drop *curr) {
 236     return visit(curr->value);
 237   }
 238   Index visitReturn(Return *curr) {
 239     return maybeVisit(curr->value);
 240   }
 241   Index visitHost(Host *curr) {
 242     return 100;
 243   }
 244   Index visitNop(Nop *curr) {
 245     return 0;
 246   }
 247   Index visitUnreachable(Unreachable *curr) {
 248     return 0;
 249   }
 250 };
 251
 252 } // namespace wasm
 253
 254 #endif // wasm_ir_cost_h
 255