src/passes/Flatten.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 code into "Flat IR" form. See ir/flat.h.
//
// TODO: handle non-nullability. for example:
//
//      (module
//       (type $none (func))
//       (func $foo
//        (drop
//         (block (result funcref (ref $none))
//          (tuple.make 2
//           (ref.null func)
//           (ref.func $foo)
//          )
//         )
//        )
//       )
//      )
//
// The tuple has a non-nullable type, and so it cannot currently be set to a
// local, but in principle there's no reason it couldn't be. For now, error on
// this.

#include <ir/branch-utils.h>
#include <ir/effects.h>
#include <ir/eh-utils.h>
#include <ir/flat.h>
#include <ir/properties.h>
#include <ir/utils.h>
#include <pass.h>
#include <wasm-builder.h>
#include <wasm.h>

namespace wasm {

// We use the following algorithm: we maintain a list of "preludes", code
// that runs right before an expression. When we visit an expression we
// must handle it and its preludes. If the expression has side effects,
// we reduce it to a local.get and add a prelude for that. We then handle
// the preludes, by moving them to the parent or handling them directly.
// we can move them to the parent if the parent is not a control flow
// structure. Otherwise, if the parent is a control flow structure, it
// will incorporate the preludes of its children accordingly.
// As a result, when we reach a node, we know its children have no
// side effects (they have been moved to a prelude), or we are a
// control flow structure (which allows children with side effects,
// e.g. a return as a block element).
// Once exception is that we allow an (unreachable) node, which is used
// when we move something unreachable to another place, and need a
// placeholder. We will never reach that (unreachable) anyhow
struct Flatten
  : public WalkerPass<
      ExpressionStackWalker<Flatten, UnifiedExpressionVisitor<Flatten>>> {
  bool isFunctionParallel() override { return true; }

  // Flattening splits the original locals into a great many other ones, losing
  // track of the originals that DWARF refers to.
  // FIXME DWARF updating does not handle local changes yet.
  bool invalidatesDWARF() override { return true; }

  std::unique_ptr<Pass> create() override {
    return std::make_unique<Flatten>();
  }

  // For each expression, a bunch of expressions that should execute right
  // before it
  std::unordered_map<Expression*, std::vector<Expression*>> preludes;

  // Break values are sent through a temp local
  std::unordered_map<Name, Index> breakTemps;

  void visitExpression(Expression* curr) {
    std::vector<Expression*> ourPreludes;
    Builder builder(*getModule());

    // Nothing to do for constants and nop.
    if (Properties::isConstantExpression(curr) || curr->is<Nop>()) {
      return;
    }

    if (Properties::isControlFlowStructure(curr)) {
      // handle control flow explicitly. our children do not have control flow,
      // but they do have preludes which we need to set up in the right place

      // no one should have given us preludes, they are on the children
      assert(preludes.find(curr) == preludes.end());

      if (auto* block = curr->dynCast<Block>()) {
        // make a new list, where each item's preludes are added before it
        ExpressionList newList(getModule()->allocator);
        for (auto* item : block->list) {
          auto iter = preludes.find(item);
          if (iter != preludes.end()) {
            auto& itemPreludes = iter->second;
            for (auto* prelude : itemPreludes) {
              newList.push_back(prelude);
            }
            itemPreludes.clear();
          }
          newList.push_back(item);
        }
        block->list.swap(newList);
        // remove a block return value
        auto type = block->type;
        if (type.isConcrete()) {
          // if there is a temp index for breaking to the block, use that
          Index temp;
          auto iter = breakTemps.find(block->name);
          if (iter != breakTemps.end()) {
            temp = iter->second;
          } else {
            temp = builder.addVar(getFunction(), type);
          }
          auto*& last = block->list.back();
          if (last->type.isConcrete()) {
            last = builder.makeLocalSet(temp, last);
          }
          block->finalize(Type::none);
          // and we leave just a get of the value
          auto* rep = builder.makeLocalGet(temp, type);
          replaceCurrent(rep);
          // the whole block is now a prelude
          ourPreludes.push_back(block);
        }
        // the block now has no return value, and may have become unreachable
        block->finalize(Type::none);

      } else if (auto* iff = curr->dynCast<If>()) {
        // condition preludes go before the entire if
        auto* rep = getPreludesWithExpression(iff->condition, iff);
        // arm preludes go in the arms. we must also remove an if value
        auto* originalIfTrue = iff->ifTrue;
        auto* originalIfFalse = iff->ifFalse;
        auto type = iff->ifFalse ? Type::getLeastUpperBound(iff->ifTrue->type,
                                                            iff->ifFalse->type)
                                 : Type::none;
        Expression* prelude = nullptr;
        if (type.isConcrete()) {
          Index temp = builder.addVar(getFunction(), type);
          if (iff->ifTrue->type.isConcrete()) {
            iff->ifTrue = builder.makeLocalSet(temp, iff->ifTrue);
          }
          if (iff->ifFalse->type.isConcrete()) {
            iff->ifFalse = builder.makeLocalSet(temp, iff->ifFalse);
          }
          if (curr->type.isConcrete()) {
            // the whole if (+any preludes from the condition) is now a prelude
            prelude = rep;
            // and we leave just a get of the value
            rep = builder.makeLocalGet(temp, type);
          }
        }
        iff->ifTrue = getPreludesWithExpression(originalIfTrue, iff->ifTrue);
        if (iff->ifFalse) {
          iff->ifFalse =
            getPreludesWithExpression(originalIfFalse, iff->ifFalse);
        }
        iff->finalize();
        if (prelude) {
          ReFinalizeNode().visit(prelude);
          ourPreludes.push_back(prelude);
        }
        replaceCurrent(rep);

      } else if (auto* loop = curr->dynCast<Loop>()) {
        // remove a loop value
        Expression* rep = loop;
        auto* originalBody = loop->body;
        auto type = loop->type;
        if (type.isConcrete()) {
          Index temp = builder.addVar(getFunction(), type);
          loop->body = builder.makeLocalSet(temp, loop->body);
          // and we leave just a get of the value
          rep = builder.makeLocalGet(temp, type);
          // the whole if is now a prelude
          ourPreludes.push_back(loop);
          loop->type = Type::none;
        }
        loop->body = getPreludesWithExpression(originalBody, loop->body);
        loop->finalize();
        replaceCurrent(rep);

      } else if (auto* tryy = curr->dynCast<Try>()) {
        // remove a try value
        Expression* rep = tryy;
        auto* originalBody = tryy->body;
        std::vector<Expression*> originalCatchBodies(tryy->catchBodies.begin(),
                                                     tryy->catchBodies.end());
        auto type = tryy->type;
        if (type.isConcrete()) {
          Index temp = builder.addVar(getFunction(), type);
          if (tryy->body->type.isConcrete()) {
            tryy->body = builder.makeLocalSet(temp, tryy->body);
          }
          for (Index i = 0; i < tryy->catchBodies.size(); i++) {
            if (tryy->catchBodies[i]->type.isConcrete()) {
              tryy->catchBodies[i] =
                builder.makeLocalSet(temp, tryy->catchBodies[i]);
            }
          }
          // and we leave just a get of the value
          rep = builder.makeLocalGet(temp, type);
          // the whole try is now a prelude
          ourPreludes.push_back(tryy);
        }
        tryy->body = getPreludesWithExpression(originalBody, tryy->body);
        for (Index i = 0; i < tryy->catchBodies.size(); i++) {
          tryy->catchBodies[i] = getPreludesWithExpression(
            originalCatchBodies[i], tryy->catchBodies[i]);
        }
        tryy->finalize();
        replaceCurrent(rep);

      } else {
        WASM_UNREACHABLE("unexpected expr type");
      }

    } else {
      // for anything else, there may be existing preludes
      auto iter = preludes.find(curr);
      if (iter != preludes.end()) {
        ourPreludes.swap(iter->second);
      }

      // special handling
      if (auto* set = curr->dynCast<LocalSet>()) {
        if (set->isTee()) {
          // we disallow local.tee
          if (set->value->type == Type::unreachable) {
            replaceCurrent(set->value); // trivial, no set happens
          } else {
            // use a set in a prelude + a get
            set->makeSet();
            ourPreludes.push_back(set);
            Type localType = getFunction()->getLocalType(set->index);
            replaceCurrent(builder.makeLocalGet(set->index, localType));
          }
        }

      } else if (auto* br = curr->dynCast<Break>()) {
        if (br->value) {
          auto type = br->value->type;
          if (type.isConcrete()) {
            // we are sending a value. use a local instead
            Type blockType = findBreakTarget(br->name)->type;
            Index temp = getTempForBreakTarget(br->name, blockType);
            ourPreludes.push_back(builder.makeLocalSet(temp, br->value));

            // br_if leaves a value on the stack if not taken, which later can
            // be the last element of the enclosing innermost block and flow
            // out. The local we created using 'getTempForBreakTarget' returns
            // the return type of the block this branch is targeting, which may
            // not be the same with the innermost block's return type. For
            // example,
            // (block $any (result anyref)
            //   (block (result funcref)
            //     (local.tee $0
            //       (br_if $any
            //         (ref.null func)
            //         (i32.const 0)
            //       )
            //     )
            //   )
            // )
            // In this case we need two locals to store (ref.null); one with
            // funcref type that's for the target block ($label0) and one more
            // with anyref type in case for flowing out. Here we create the
            // second 'flowing out' local in case two block's types are
            // different.
            if (type != blockType) {
              temp = builder.addVar(getFunction(), type);
              ourPreludes.push_back(builder.makeLocalSet(
                temp, ExpressionManipulator::copy(br->value, *getModule())));
            }

            if (br->condition) {
              // the value must also flow out
              ourPreludes.push_back(br);
              if (br->type.isConcrete()) {
                replaceCurrent(builder.makeLocalGet(temp, type));
              } else {
                assert(br->type == Type::unreachable);
                replaceCurrent(builder.makeUnreachable());
              }
            }
            br->value = nullptr;
            br->finalize();
          } else {
            assert(type == Type::unreachable);
            // we don't need the br at all
            replaceCurrent(br->value);
          }
        }

      } else if (auto* sw = curr->dynCast<Switch>()) {
        if (sw->value) {
          auto type = sw->value->type;
          if (type.isConcrete()) {
            // we are sending a value. use a local instead
            Index temp = builder.addVar(getFunction(), type);
            ourPreludes.push_back(builder.makeLocalSet(temp, sw->value));
            // we don't know which break target will be hit - assign to them all
            auto names = BranchUtils::getUniqueTargets(sw);
            for (auto name : names) {
              ourPreludes.push_back(
                builder.makeLocalSet(getTempForBreakTarget(name, type),
                                     builder.makeLocalGet(temp, type)));
            }
            sw->value = nullptr;
            sw->finalize();
          } else {
            assert(type == Type::unreachable);
            // we don't need the br at all
            replaceCurrent(sw->value);
          }
        }
      }
    }

    if (curr->is<BrOn>() || curr->is<TryTable>()) {
      Fatal() << "Unsupported instruction for Flatten: "
              << getExpressionName(curr);
    }

    // continue for general handling of everything, control flow or otherwise
    curr = getCurrent(); // we may have replaced it
    // we have changed children
    ReFinalizeNode().visit(curr);
    if (curr->type == Type::unreachable) {
      ourPreludes.push_back(curr);
      replaceCurrent(builder.makeUnreachable());
    } else if (curr->type.isConcrete()) {
      // use a local
      auto type = curr->type;
      Index temp = builder.addVar(getFunction(), type);
      ourPreludes.push_back(builder.makeLocalSet(temp, curr));
      replaceCurrent(builder.makeLocalGet(temp, type));
    }

    // next, finish up: migrate our preludes if we can
    if (!ourPreludes.empty()) {
      auto* parent = getParent();
      if (parent && !Properties::isControlFlowStructure(parent)) {
        auto& parentPreludes = preludes[parent];
        for (auto* prelude : ourPreludes) {
          parentPreludes.push_back(prelude);
        }
      } else {
        // keep our preludes, parent will handle them
        preludes[getCurrent()].swap(ourPreludes);
      }
    }
  }

  void visitFunction(Function* curr) {
    auto* originalBody = curr->body;
    // if the body is a block with a result, turn that into a return
    if (curr->body->type.isConcrete()) {
      curr->body = Builder(*getModule()).makeReturn(curr->body);
    }
    // the body may have preludes
    curr->body = getPreludesWithExpression(originalBody, curr->body);

    // Flatten can generate blocks within 'catch', making pops invalid. Fix them
    // up.
    EHUtils::handleBlockNestedPops(curr, *getModule());
  }

private:
  // gets an expression, either by itself, or in a block with its
  // preludes (which we use up) before it
  Expression* getPreludesWithExpression(Expression* curr) {
    return getPreludesWithExpression(curr, curr);
  }

  // gets an expression, either by itself, or in a block with some
  // preludes (which we use up) for another expression before it
  Expression* getPreludesWithExpression(Expression* preluder,
                                        Expression* after) {
    auto iter = preludes.find(preluder);
    if (iter == preludes.end()) {
      return after;
    }
    // we have preludes
    auto& thePreludes = iter->second;
    auto* ret = Builder(*getModule()).makeBlock(thePreludes);
    thePreludes.clear();
    ret->list.push_back(after);
    ret->finalize();
    return ret;
  }

  // get the temp local to be used for breaks to that target. allocates
  // one if there isn't one yet
  Index getTempForBreakTarget(Name name, Type type) {
    auto iter = breakTemps.find(name);
    if (iter != breakTemps.end()) {
      return iter->second;
    } else {
      return breakTemps[name] =
               Builder(*getModule()).addVar(getFunction(), type);
    }
  }
};

Pass* createFlattenPass() { return new Flatten(); }

} // namespace wasm