src/binaryen/src/ir/branch-utils.h

   1 /*
   2  * Copyright 2017 WebAssembly Community Group participants
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #ifndef wasm_ir_branch_h
  18 #define wasm_ir_branch_h
  19
  20 #include "wasm.h"
  21 #include "wasm-traversal.h"
  22
  23 namespace wasm {
  24
  25 namespace BranchUtils {
  26
  27 // Some branches are obviously not actually reachable (e.g. (br $out (unreachable)))
  28
  29 inline bool isBranchReachable(Break* br) {
  30   return !(br->value     && br->value->type     == unreachable) &&
  31          !(br->condition && br->condition->type == unreachable);
  32 }
  33
  34 inline bool isBranchReachable(Switch* sw) {
  35   return !(sw->value && sw->value->type     == unreachable) &&
  36                         sw->condition->type != unreachable;
  37 }
  38
  39 inline bool isBranchReachable(Expression* expr) {
  40   if (auto* br = expr->dynCast<Break>()) {
  41     return isBranchReachable(br);
  42   } else if (auto* sw = expr->dynCast<Switch>()) {
  43     return isBranchReachable(sw);
  44   }
  45   WASM_UNREACHABLE();
  46 }
  47
  48 // returns the set of targets to which we branch that are
  49 // outside of a node
  50 inline std::set<Name> getExitingBranches(Expression* ast) {
  51   struct Scanner : public PostWalker<Scanner> {
  52     std::set<Name> targets;
  53
  54     void visitBreak(Break* curr) {
  55       targets.insert(curr->name);
  56     }
  57     void visitSwitch(Switch* curr) {
  58       for (auto target : targets) {
  59         targets.insert(target);
  60       }
  61       targets.insert(curr->default_);
  62     }
  63     void visitBlock(Block* curr) {
  64       if (curr->name.is()) {
  65         targets.erase(curr->name);
  66       }
  67     }
  68     void visitLoop(Loop* curr) {
  69       if (curr->name.is()) {
  70         targets.erase(curr->name);
  71       }
  72     }
  73   };
  74   Scanner scanner;
  75   scanner.walk(ast);
  76   // anything not erased is a branch out
  77   return scanner.targets;
  78 }
  79
  80 // returns the list of all branch targets in a node
  81
  82 inline std::set<Name> getBranchTargets(Expression* ast) {
  83   struct Scanner : public PostWalker<Scanner> {
  84     std::set<Name> targets;
  85
  86     void visitBlock(Block* curr) {
  87       if (curr->name.is()) {
  88         targets.insert(curr->name);
  89       }
  90     }
  91     void visitLoop(Loop* curr) {
  92       if (curr->name.is()) {
  93         targets.insert(curr->name);
  94       }
  95     }
  96   };
  97   Scanner scanner;
  98   scanner.walk(ast);
  99   return scanner.targets;
 100 }
 101
 102 // Finds if there are branches targeting a name. Note that since names are
 103 // unique in our IR, we just need to look for the name, and do not need
 104 // to analyze scoping.
 105 // By default we consider all branches, so any place there is a branch that
 106 // names the target. You can unset 'named' to only note branches that appear
 107 // reachable (i.e., are not obviously unreachable).
 108 struct BranchSeeker : public PostWalker<BranchSeeker> {
 109   Name target;
 110   bool named = true;
 111
 112   Index found;
 113   WasmType valueType;
 114
 115   BranchSeeker(Name target) : target(target), found(0) {}
 116
 117   void noteFound(Expression* value) {
 118     found++;
 119     if (found == 1) valueType = unreachable;
 120     if (!value) valueType = none;
 121     else if (value->type != unreachable) valueType = value->type;
 122   }
 123
 124   void visitBreak(Break *curr) {
 125     if (!named) {
 126       // ignore an unreachable break
 127       if (curr->condition && curr->condition->type == unreachable) return;
 128       if (curr->value && curr->value->type == unreachable) return;
 129     }
 130     // check the break
 131     if (curr->name == target) noteFound(curr->value);
 132   }
 133
 134   void visitSwitch(Switch *curr) {
 135     if (!named) {
 136       // ignore an unreachable switch
 137       if (curr->condition->type == unreachable) return;
 138       if (curr->value && curr->value->type == unreachable) return;
 139     }
 140     // check the switch
 141     for (auto name : curr->targets) {
 142       if (name == target) noteFound(curr->value);
 143     }
 144     if (curr->default_ == target) noteFound(curr->value);
 145   }
 146
 147   static bool hasReachable(Expression* tree, Name target) {
 148     if (!target.is()) return false;
 149     BranchSeeker seeker(target);
 150     seeker.named = false;
 151     seeker.walk(tree);
 152     return seeker.found > 0;
 153   }
 154
 155   static Index countReachable(Expression* tree, Name target) {
 156     if (!target.is()) return 0;
 157     BranchSeeker seeker(target);
 158     seeker.named = false;
 159     seeker.walk(tree);
 160     return seeker.found;
 161   }
 162
 163   static bool hasNamed(Expression* tree, Name target) {
 164     if (!target.is()) return false;
 165     BranchSeeker seeker(target);
 166     seeker.walk(tree);
 167     return seeker.found > 0;
 168   }
 169
 170   static Index countNamed(Expression* tree, Name target) {
 171     if (!target.is()) return 0;
 172     BranchSeeker seeker(target);
 173     seeker.walk(tree);
 174     return seeker.found;
 175   }
 176 };
 177
 178 } // namespace BranchUtils
 179
 180 } // namespace wasm
 181
 182 #endif // wasm_ir_branch_h
 183