path: root/src/passes/FlattenControlFlow.cpp

/*
 * Copyright 2017 WebAssembly Community Group participants
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

//
// Flattens control flow, e.g.
//
//  (i32.add
//    (if (..condition..)
//      (..if true..)
//      (..if false..)
//    )
//    (i32.const 1)
//  )
// =>
//  (if (..condition..)
//    (set_local $temp
//      (..if true..)
//    )
//    (set_local $temp
//      (..if false..)
//    )
//  )
//  (i32.add
//    (get_local $temp)
//    (i32.const 1)
//  )
//
// Formally, this pass flattens control flow in the precise sense of
// making the AST have these properties:
//
//  1. Control flow structures (block, loop, if) and control flow
//     operations (br, br_if, br_table, return, unreachable) may
//     only be block children, a loop body, or an if-true or if-false.
//     (I.e., they cannot be nested inside an i32.add, a drop, a
//     call, an if-condition, etc.)
//  2. Disallow block, loop, and if return values, i.e., do not use
//     control flow to pass around values.
//
// Note that we do still allow normal arbitrary nesting of expressions
// *without* control flow (i.e., this is not a reduction to 3-address
// code form). We also allow nesting of control flow, but just nested
// in other control flow, like an if in the true arm of an if, and
// so forth. What we achieve here is that when you see an expression,
// you know it has no control flow inside it, it will be fully
// executed.
//

#include <wasm.h>
#include <pass.h>
#include <wasm-builder.h>
#include <ast_utils.h>

namespace wasm {

// Looks for control flow changes and structures, excluding blocks (as we
// want to put all control flow on them)
struct ControlFlowChecker : public Visitor<ControlFlowChecker> {
  static bool is(Expression* node) {
    ControlFlowChecker finder;
    finder.visit(node);
    return finder.hasControlFlow;
  }

  bool hasControlFlow = false;

  void visitBreak(Break *curr) { hasControlFlow = true; }
  void visitSwitch(Switch *curr) { hasControlFlow = true; }
  void visitBlock(Block *curr) { hasControlFlow = true; }
  void visitLoop(Loop* curr) { hasControlFlow = true; }
  void visitIf(If* curr) { hasControlFlow = true; }
  void visitReturn(Return *curr) { hasControlFlow = true; }
  void visitUnreachable(Unreachable *curr) { hasControlFlow = true; }
};

struct FlattenControlFlow : public WalkerPass<PostWalker<FlattenControlFlow>> {
  bool isFunctionParallel() override { return true; }

  Pass* create() override { return new FlattenControlFlow; }

  std::unique_ptr<Builder> builder;
  // we get rid of block/if/loop values. this map tells us for
  // each break target what local index to use.
  // if this is a flowing value, there might not be a name assigned
  // (block ending, block with no name; or if value), so we use
  // the expr (and there will be exactly one set and get of it,
  // so we don't need a name)
  std::map<Name, Index> breakNameIndexes;
  std::map<Expression*, Index> breakExprIndexes;

  void doWalkFunction(Function* func) {
    builder = make_unique<Builder>(*getModule());
    walk(func->body);
    if (func->result != none) {
      // if the body had a fallthrough, receive it and return it
      auto iter = breakExprIndexes.find(func->body);
      if (iter != breakExprIndexes.end()) {
        func->body = builder->makeSequence(
          func->body,
          builder->makeReturn(
            builder->makeGetLocal(iter->second, func->result)
          )
        );
      }
    }
  }

  // returns the index to assign values to for a break target. allocates
  // the local if this is the first time we see it.
  // expr is used if this is a flowing value.
  Index getBreakTargetIndex(Name name, WasmType type, Expression* expr = nullptr, Index index = -1) {
    assert(isConcreteWasmType(type)); // we shouldn't get here if the value ins't actually set
    if (name.is()) {
      auto iter = breakNameIndexes.find(name);
      if (iter == breakNameIndexes.end()) {
        if (index == Index(-1)) {
          index = builder->addVar(getFunction(), type);
        }
        breakNameIndexes[name] = index;
        if (expr) {
          breakExprIndexes[expr] = index;
        }
        return index;
      }
      if (expr) {
        breakExprIndexes[expr] = iter->second;
      }
      return iter->second;
    } else {
      assert(expr);
      auto iter = breakExprIndexes.find(expr);
      if (iter == breakExprIndexes.end()) {
        if (index == Index(-1)) {
          index = builder->addVar(getFunction(), type);
        }
        return breakExprIndexes[expr] = index;
      }
      return iter->second;
    }
  }

  // When we reach a fallthrough value, it has already been flattened, and its value
  // assigned to the proper local. Or, it may not have needed to be flattened,
  // and we can just assign to a local. This method simply returns the fallthrough
  // replacement code.
  Expression* getFallthroughReplacement(Expression* child, Index myIndex) {
    auto iter = breakExprIndexes.find(child);
    if (iter != breakExprIndexes.end()) {
      // it was flattened and saved to a local
      return builder->makeSequence(
        child, // which no longer flows a value, now it sets the child index
        builder->makeSetLocal(
          myIndex,
          builder->makeGetLocal(iter->second, getFunction()->getLocalType(iter->second))
        )
      );
    }
    // a simple expression
    if (child->type == unreachable) {
      // no need to even set the local
      return child;
    } else {
      assert(!ControlFlowChecker::is(child));
      return builder->makeSetLocal(
        myIndex,
        child
      );
    }
  }

  // flattening fallthroughs makes them have type none. this gets their true type
  WasmType getFallthroughType(Expression* child) {
    auto iter = breakExprIndexes.find(child);
    if (iter != breakExprIndexes.end()) {
      // it was flattened and saved to a local
      return getFunction()->getLocalType(iter->second);
    }
    assert(child->type != none);
    return child->type;
  }

  // Splitter helper
  struct Splitter {
    Splitter(FlattenControlFlow& parent, Expression* node) : parent(parent), node(node) {}

    ~Splitter() {
      finish();
    }

    FlattenControlFlow& parent;
    Expression* node;

    std::vector<Expression**> children; // TODO: reuse in parent, avoiding mallocing on each node

    void note(Expression*& child) {
      // we accept nullptr inputs, for a non-existing child
      if (!child) return;
      children.push_back(&child);
    }

    Expression* replacement; // the final replacement for the current node
    bool stop = false; // if a child is unreachable, we can stop

    void finish() {
      if (children.empty()) return;
      // first, scan the list
      bool hasControlFlowChild = false;
      bool hasUnreachableChild = false;
      for (auto** childp : children) {
        // it's enough to look at the child, ignoring the contents, as the contents
        // have already been processed before we got here, so they must have been
        // flattened if necessary.
        auto* child = *childp;
        if (ControlFlowChecker::is(child)) {
          hasControlFlowChild = true;
        }
        if (child->type == unreachable) {
          hasUnreachableChild = true;
        }
      }
      if (!hasControlFlowChild) {
        // nothing to do here.
        assert(!hasUnreachableChild); // all of them should be executed
        return;
      }
      // we have at least one child we need to split out, so to preserve the order of operations,
      // split them all out
      Builder* builder = parent.builder.get();
      std::vector<Index> tempIndexes;
      for (auto** childp : children) {
        auto* child = *childp;
        if (isConcreteWasmType(child->type)) {
          tempIndexes.push_back(builder->addVar(parent.getFunction(), child->type));
        } else {
          tempIndexes.push_back(-1);
        }
      }
      // create a new replacement block
      auto* block = builder->makeBlock();
      for (Index i = 0; i < children.size(); i++) {
        auto* child = *children[i];
        auto type = child->type;
        if (isConcreteWasmType(type)) {
          // set the child to a local, and use it later
          block->list.push_back(builder->makeSetLocal(tempIndexes[i], child));
          *children[i] = builder->makeGetLocal(tempIndexes[i], type);
        } else if (type == none) {
          // a nested none can not happen normally, here it occurs after we flattened a nested
          // we can use the local it already assigned to. TODO: don't even allocate one here
          block->list.push_back(child);
          assert(parent.breakExprIndexes.count(child) > 0);
          auto index = parent.breakExprIndexes[child];
          *children[i] = builder->makeGetLocal(
            index,
            parent.getFunction()->getLocalType(index)
          );
        } else if (type == unreachable) {
          block->list.push_back(child);
          break; // no need to push any more
        } else {
          WASM_UNREACHABLE();
        }
      }
      if (!hasUnreachableChild) {
        // we reached the end, so we need to emit the expression itself
        // (which has been modified to replace children usages with get_locals)
        block->list.push_back(node);
      }
      block->finalize();
      // finally, we just created a new block, ending in node. If node is e.g.
      // i32.add, then our block would return a value. so we must convert
      // this new block to return a value through a local
      parent.visitBlock(block);
      // the block is now done
      parent.replaceCurrent(block);
      // if the node was potentially a flowthrough value, then it has an entry
      // in breakExprIndexes, and since we are replacing it with this block,
      // we must note it's index as the same, so it is found by the parent.
      if (parent.breakExprIndexes.find(node) != parent.breakExprIndexes.end()) {
        parent.breakExprIndexes[block] = parent.breakExprIndexes[node];
      }
    }
  };

  void visitBlock(Block* curr) {
    if (isConcreteWasmType(curr->type)) {
      curr->list.back() = getFallthroughReplacement(curr->list.back(), getBreakTargetIndex(curr->name, curr->type, curr));
      curr->finalize();
    }
  }
  void visitLoop(Loop* curr) {
    if (isConcreteWasmType(curr->type)) {
      curr->body = getFallthroughReplacement(curr->body, getBreakTargetIndex(Name(), curr->type, curr));
      curr->finalize();
    }
  }
  void visitIf(If* curr) {
    if (isConcreteWasmType(curr->type)) {
      auto targetIndex = getBreakTargetIndex(Name(), curr->type, curr);
      curr->ifTrue = getFallthroughReplacement(curr->ifTrue, targetIndex);
      curr->ifFalse = getFallthroughReplacement(curr->ifFalse, targetIndex);
      curr->finalize();
    }
    Splitter splitter(*this, curr);
    splitter.note(curr->condition);
  }
  void visitBreak(Break* curr) {
    Expression* processed = curr;
    // first of all, get rid of the value if there is one
    if (curr->value) {
      if (curr->value->type != unreachable) {
        auto type = getFallthroughType(curr->value);
        auto index = getBreakTargetIndex(curr->name, type);
        auto* value = getFallthroughReplacement(curr->value, index);
        curr->value = nullptr;
        curr->finalize();
        processed = builder->makeSequence(
          value,
          curr
        );
        replaceCurrent(processed);
        if (curr->condition) {
          // we already called getBreakTargetIndex for the value we send to our
          // break target if we break. as this is a br_if with a value, it also
          // flows out that value, so our parent needs to know how to receive it.
          // we note the already-existing index we prepared before, for that value.
          getBreakTargetIndex(Name(), type, processed, index);
        }
      } else {
        // we have a value, but it has unreachable type. we can just replace
        // ourselves with it, we won't reach a condition (if there is one) or the br
        // itself
        replaceCurrent(curr->value);
        return;
      }
    }
    Splitter splitter(*this, processed);
    splitter.note(curr->condition);
  }
  void visitSwitch(Switch* curr) {
    Expression* processed = curr;

    // first of all, get rid of the value if there is one
    if (curr->value) {
      if (curr->value->type != unreachable) {
        auto type = getFallthroughType(curr->value);
        // we must assign the value to *all* the targets
        auto temp = builder->addVar(getFunction(), type);
        auto* value = getFallthroughReplacement(curr->value, temp);
        curr->value = nullptr;
        auto* block = builder->makeBlock();
        block->list.push_back(value);
        std::set<Name> names;
        for (auto target : curr->targets) {
          if (names.insert(target).second) {
            block->list.push_back(
              builder->makeSetLocal(
                getBreakTargetIndex(target, type),
                builder->makeGetLocal(temp, type)
              )
            );
          }
        }
        if (names.insert(curr->default_).second) {
          block->list.push_back(
            builder->makeSetLocal(
              getBreakTargetIndex(curr->default_, type),
              builder->makeGetLocal(temp, type)
            )
          );
        }
        block->list.push_back(curr);
        block->finalize();
        replaceCurrent(block);
      } else {
        // we have a value, but it has unreachable type. we can just replace
        // ourselves with it, we won't reach a condition (if there is one) or the br
        // itself
        replaceCurrent(curr->value);
        return;
      }
    }
    Splitter splitter(*this, processed);
    splitter.note(curr->value);
    splitter.note(curr->condition);
  }
  void visitCall(Call* curr) {
    Splitter splitter(*this, curr);
    for (auto*& operand : curr->operands) {
      splitter.note(operand);
    }
  }
  void visitCallImport(CallImport* curr) {
    Splitter splitter(*this, curr);
    for (auto*& operand : curr->operands) {
      splitter.note(operand);
    }
  }
  void visitCallIndirect(CallIndirect* curr) {
    Splitter splitter(*this, curr);
    for (auto*& operand : curr->operands) {
      splitter.note(operand);
    }
    splitter.note(curr->target);
  }
  void visitSetLocal(SetLocal* curr) {
    Splitter splitter(*this, curr);
    splitter.note(curr->value);
  }
  void visitSetGlobal(SetGlobal* curr) {
    Splitter splitter(*this, curr);
    splitter.note(curr->value);
  }
  void visitLoad(Load* curr) {
    Splitter splitter(*this, curr);
    splitter.note(curr->ptr);
  }
  void visitStore(Store* curr) {
    Splitter splitter(*this, curr);
    splitter.note(curr->ptr);
    splitter.note(curr->value);
  }
  void visitUnary(Unary* curr) {
    Splitter splitter(*this, curr);
    splitter.note(curr->value);
  }
  void visitBinary(Binary* curr) {
    Splitter splitter(*this, curr);
    splitter.note(curr->left);
    splitter.note(curr->right);
  }
  void visitSelect(Select* curr) {
    Splitter splitter(*this, curr);
    splitter.note(curr->ifTrue);
    splitter.note(curr->ifFalse);
    splitter.note(curr->condition);
  }
  void visitDrop(Drop* curr) {
    Splitter splitter(*this, curr);
    splitter.note(curr->value);
  }
  void visitReturn(Return* curr) {
    Splitter splitter(*this, curr);
    splitter.note(curr->value);
  }
  void visitHost(Host* curr) {
    Splitter splitter(*this, curr);
    for (auto*& operand : curr->operands) {
      splitter.note(operand);
    }
  }

  void visitFunction(Function* curr) {
    // removing breaks can alter types
    ReFinalize().walkFunctionInModule(curr, getModule());
  }
};

Pass *createFlattenControlFlowPass() {
  return new FlattenControlFlow();
}

} // namespace wasm