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