1 /* 2 * Copyright 2018 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_iteration_h 18 #define wasm_ir_iteration_h 19 20 #include "ir/properties.h" 21 #include "wasm-traversal.h" 22 #include "wasm.h" 23 24 namespace wasm { 25 26 // 27 // Allows iteration over the children of the expression, in order of execution 28 // where relevant. 29 // 30 // * This skips missing children, e.g. if an if has no else, it is represented 31 // as having 2 children (and not 3 with the last a nullptr). 32 // 33 // In general, it is preferable not to use this class and to directly access the 34 // children (using e.g. iff->ifTrue etc.), as that is faster. However, in cases 35 // where speed does not matter, this can be convenient. TODO: reimplement these 36 // to avoid materializing all the chilren at once. 37 // 38 // ChildIterator - Iterates over all children 39 // 40 // ValueChildIterator - Iterates over all children that produce values used by 41 // this instruction. For example, includes If::condition 42 // but not If::ifTrue. 43 // 44 template<template<class, class> class Scanner> class AbstractChildIterator { 45 using Self = AbstractChildIterator<Scanner>; 46 struct Iterator { 47 const Self& parent; 48 Index index; 49 IteratorIterator50 Iterator(const Self& parent, Index index) : parent(parent), index(index) {} 51 52 bool operator!=(const Iterator& other) const { 53 return index != other.index || &parent != &(other.parent); 54 } 55 56 void operator++() { index++; } 57 58 Expression* operator*() { return parent.children[index]; } 59 }; 60 61 public: 62 SmallVector<Expression*, 4> children; 63 AbstractChildIterator(Expression * parent)64 AbstractChildIterator(Expression* parent) { 65 struct Traverser : public PostWalker<Traverser> { 66 Expression* parent; 67 SmallVector<Expression*, 4>* children; 68 69 // We need to scan subchildren exactly once - just the parent. 70 bool scanned = false; 71 72 static void scan(Traverser* self, Expression** currp) { 73 if (!self->scanned) { 74 self->scanned = true; 75 Scanner<Traverser, UnifiedExpressionVisitor<Traverser>>::scan(self, 76 currp); 77 } else { 78 // This is one of the children. Do not scan further, just note it. 79 self->children->push_back(*currp); 80 } 81 } 82 } traverser; 83 traverser.parent = parent; 84 traverser.children = &children; 85 traverser.walk(parent); 86 } 87 begin()88 Iterator begin() const { return Iterator(*this, 0); } end()89 Iterator end() const { return Iterator(*this, children.size()); } 90 }; 91 92 template<class SubType, class Visitor> 93 struct ValueChildScanner : PostWalker<SubType, Visitor> { scanValueChildScanner94 static void scan(SubType* self, Expression** currp) { 95 auto* curr = *currp; 96 if (Properties::isControlFlowStructure(curr)) { 97 // If conditions are the only value children of control flow structures 98 if (auto* iff = curr->dynCast<If>()) { 99 self->pushTask(SubType::scan, &iff->condition); 100 } 101 } else { 102 // All children on non-control flow expressions are value children 103 PostWalker<SubType, Visitor>::scan(self, currp); 104 } 105 } 106 }; 107 108 using ChildIterator = AbstractChildIterator<PostWalker>; 109 using ValueChildIterator = AbstractChildIterator<ValueChildScanner>; 110 111 // Returns true if the current expression contains a certain kind of expression, 112 // within the given depth of BFS. If depth is -1, this searches all children. 113 template<typename T> bool containsChild(Expression* parent, int depth = -1) { 114 std::vector<Expression*> exprs; 115 std::vector<Expression*> nextExprs; 116 exprs.push_back(parent); 117 while (!exprs.empty() && depth > 0) { 118 for (auto* expr : exprs) { 119 for (auto* child : ChildIterator(expr)) { 120 if (child->is<T>()) { 121 return true; 122 } 123 nextExprs.push_back(child); 124 } 125 } 126 exprs.swap(nextExprs); 127 nextExprs.clear(); 128 if (depth > 0) { 129 depth--; 130 } 131 } 132 return false; 133 } 134 135 } // namespace wasm 136 137 #endif // wasm_ir_iteration_h 138