src/binaryen/src/ir/type-updating.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_type_updating_h
  18 #define wasm_ir_type_updating_h
  19
  20 #include "wasm-traversal.h"
  21
  22 namespace wasm {
  23
  24 // a class that tracks type dependencies between nodes, letting you
  25 // update types efficiently when removing and altering code.
  26 // altering code can alter types in the following way:
  27 //   * removing a break can make a block unreachable, if nothing else
  28 //     reaches it
  29 //   * altering the type of a child to unreachable can make the parent
  30 //     unreachable
  31 struct TypeUpdater : public ExpressionStackWalker<TypeUpdater, UnifiedExpressionVisitor<TypeUpdater>> {
  32   // Part 1: Scanning
  33
  34   // track names to their blocks, so that when we remove a break to
  35   // a block, we know how to find it if we need to update it
  36   struct BlockInfo {
  37     Block* block = nullptr;
  38     int numBreaks = 0;
  39   };
  40   std::map<Name, BlockInfo> blockInfos;
  41
  42   // track the parent of each node, as child type changes may lead to
  43   // unreachability
  44   std::map<Expression*, Expression*> parents;
  45
  46   void visitExpression(Expression* curr) {
  47     if (expressionStack.size() > 1) {
  48       parents[curr] = expressionStack[expressionStack.size() - 2];
  49     } else {
  50       parents[curr] = nullptr; // this is the top level
  51     }
  52     // discover block/break relationships
  53     if (auto* block = curr->dynCast<Block>()) {
  54       if (block->name.is()) {
  55         blockInfos[block->name].block = block;
  56       }
  57     } else if (auto* br = curr->dynCast<Break>()) {
  58       // ensure info exists, discoverBreaks can then fill it
  59       blockInfos[br->name];
  60     } else if (auto* sw = curr->dynCast<Switch>()) {
  61       // ensure info exists, discoverBreaks can then fill it
  62       for (auto target : sw->targets) {
  63         blockInfos[target];
  64       }
  65       blockInfos[sw->default_];
  66     }
  67     // add a break to the info, for break and switch
  68     discoverBreaks(curr, +1);
  69   }
  70
  71   // Part 2: Updating
  72
  73   // Node replacements, additions, removals and type changes should be noted. An
  74   // exception is nodes you know will never be looked at again.
  75
  76   // note the replacement of one node with another. this should be called
  77   // after performing the replacement.
  78   // this does *not* look into the node by default. see noteReplacementWithRecursiveRemoval
  79   // (we don't support recursive addition because in practice we do not create
  80   // new trees in the passes that use this, they just move around children)
  81   void noteReplacement(Expression* from, Expression* to, bool recursivelyRemove=false) {
  82     auto parent = parents[from];
  83     if (recursivelyRemove) {
  84       noteRecursiveRemoval(from);
  85     } else {
  86       noteRemoval(from);
  87     }
  88     // if we are replacing with a child, i.e. a node that was already present
  89     // in the ast, then we just have a type and parent to update
  90     if (parents.find(to) != parents.end()) {
  91       parents[to] = parent;
  92       if (from->type != to->type) {
  93         propagateTypesUp(to);
  94       }
  95     } else {
  96       noteAddition(to, parent, from);
  97     }
  98   }
  99
 100   void noteReplacementWithRecursiveRemoval(Expression* from, Expression* to) {
 101     noteReplacement(from, to, true);
 102   }
 103
 104   // note the removal of a node
 105   void noteRemoval(Expression* curr) {
 106     noteRemovalOrAddition(curr, nullptr);
 107     parents.erase(curr);
 108   }
 109
 110   // note the removal of a node and all its children
 111   void noteRecursiveRemoval(Expression* curr) {
 112     struct Recurser : public PostWalker<Recurser, UnifiedExpressionVisitor<Recurser>> {
 113       TypeUpdater& parent;
 114
 115       Recurser(TypeUpdater& parent, Expression* root) : parent(parent) {
 116         walk(root);
 117       }
 118
 119       void visitExpression(Expression* curr) {
 120         parent.noteRemoval(curr);
 121       }
 122     };
 123
 124     Recurser(*this, curr);
 125   }
 126
 127   void noteAddition(Expression* curr, Expression* parent, Expression* previous = nullptr) {
 128     assert(parents.find(curr) == parents.end()); // must not already exist
 129     noteRemovalOrAddition(curr, parent);
 130     // if we didn't replace with the exact same type, propagate types up
 131     if (!(previous && previous->type == curr->type)) {
 132       propagateTypesUp(curr);
 133     }
 134   }
 135
 136   // if parent is nullptr, this is a removal
 137   void noteRemovalOrAddition(Expression* curr, Expression* parent) {
 138     parents[curr] = parent;
 139     discoverBreaks(curr, parent ? +1 : -1);
 140   }
 141
 142   // adds (or removes) breaks depending on break/switch contents
 143   void discoverBreaks(Expression* curr, int change) {
 144     if (auto* br = curr->dynCast<Break>()) {
 145       noteBreakChange(br->name, change, br->value);
 146     } else if (auto* sw = curr->dynCast<Switch>()) {
 147       applySwitchChanges(sw, change);
 148     }
 149   }
 150
 151   void applySwitchChanges(Switch* sw, int change) {
 152     std::set<Name> seen;
 153     for (auto target : sw->targets) {
 154       if (seen.insert(target).second) {
 155         noteBreakChange(target, change, sw->value);
 156       }
 157     }
 158     if (seen.insert(sw->default_).second) {
 159       noteBreakChange(sw->default_, change, sw->value);
 160     }
 161   }
 162
 163   // note the addition of a node
 164   void noteBreakChange(Name name, int change, Expression* value) {
 165     auto iter = blockInfos.find(name);
 166     if (iter == blockInfos.end()) {
 167       return; // we can ignore breaks to loops
 168     }
 169     auto& info = iter->second;
 170     info.numBreaks += change;
 171     assert(info.numBreaks >= 0);
 172     auto* block = info.block;
 173     if (block) { // if to a loop, can ignore
 174       if (info.numBreaks == 0) {
 175         // dropped to 0! the block may now be unreachable. that
 176         // requires that it doesn't have a fallthrough
 177         makeBlockUnreachableIfNoFallThrough(block);
 178       } else if (change == 1 && info.numBreaks == 1) {
 179         // bumped to 1! the block may now be reachable
 180         if (block->type != unreachable) {
 181           return; // was already reachable, had a fallthrough
 182         }
 183         changeTypeTo(block, value ? value->type : none);
 184       }
 185     }
 186   }
 187
 188   // alters the type of a node to a new type.
 189   // this propagates the type change through all the parents.
 190   void changeTypeTo(Expression* curr, WasmType newType) {
 191     if (curr->type == newType) return; // nothing to do
 192     curr->type = newType;
 193     propagateTypesUp(curr);
 194   }
 195
 196   // given a node that has a new type, or is a new node, update
 197   // all the parents accordingly. the existence of the node and
 198   // any changes to it already occurred, this just updates the
 199   // parents following that. i.e., nothing is done to the
 200   // node we start on, it's done.
 201   // the one thing we need to do here is propagate unreachability,
 202   // no other change is possible
 203   void propagateTypesUp(Expression* curr) {
 204     if (curr->type != unreachable) return;
 205     while (1) {
 206       auto* child = curr;
 207       curr = parents[child];
 208       if (!curr) return;
 209       // get ready to apply unreachability to this node
 210       if (curr->type == unreachable) {
 211         return; // already unreachable, stop here
 212       }
 213       // most nodes become unreachable if a child is unreachable,
 214       // but exceptions exist
 215       if (auto* block = curr->dynCast<Block>()) {
 216         // if the block has a fallthrough, it can keep its type
 217         if (isConcreteWasmType(block->list.back()->type)) {
 218           return; // did not turn
 219         }
 220         // if the block has breaks, it can keep its type
 221         if (!block->name.is() || blockInfos[block->name].numBreaks == 0) {
 222           curr->type = unreachable;
 223         } else {
 224           return; // did not turn
 225         }
 226       } else if (auto* iff = curr->dynCast<If>()) {
 227         // may not be unreachable if just one side is
 228         iff->finalize();
 229         if (curr->type != unreachable) {
 230           return; // did not turn
 231         }
 232       } else {
 233         curr->type = unreachable;
 234       }
 235     }
 236   }
 237
 238   // efficiently update the type of a block, given the data we know. this
 239   // can remove a concrete type and turn the block unreachable when it is
 240   // unreachable, and it does this efficiently, without scanning the full
 241   // contents
 242   void maybeUpdateTypeToUnreachable(Block* curr) {
 243     if (!isConcreteWasmType(curr->type)) {
 244       return; // nothing concrete to change to unreachable
 245     }
 246     if (curr->name.is() && blockInfos[curr->name].numBreaks > 0) {
 247       return; // has a break, not unreachable
 248     }
 249     // look for a fallthrough
 250     makeBlockUnreachableIfNoFallThrough(curr);
 251   }
 252
 253   void makeBlockUnreachableIfNoFallThrough(Block* curr) {
 254     if (curr->type == unreachable) {
 255       return; // no change possible
 256     }
 257     if (!curr->list.empty() &&
 258         isConcreteWasmType(curr->list.back()->type)) {
 259       return; // should keep type due to fallthrough, even if has an unreachable child
 260     }
 261     for (auto* child : curr->list) {
 262       if (child->type == unreachable) {
 263         // no fallthrough, and an unreachable, => this block is now unreachable
 264         changeTypeTo(curr, unreachable);
 265         return;
 266       }
 267     }
 268   }
 269
 270   // efficiently update the type of an if, given the data we know. this
 271   // can remove a concrete type and turn the if unreachable when it is
 272   // unreachable
 273   void maybeUpdateTypeToUnreachable(If* curr) {
 274     if (!isConcreteWasmType(curr->type)) {
 275       return; // nothing concrete to change to unreachable
 276     }
 277     curr->finalize();
 278     if (curr->type == unreachable) {
 279       propagateTypesUp(curr);
 280     }
 281   }
 282 };
 283
 284 } // namespace wasm
 285
 286 #endif // wasm_ir_type_updating_h