path: root/src/passes/Unsubtyping.cpp

/*
 * Copyright 2023 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.
 */

#include <unordered_map>

#include "ir/branch-utils.h"
#include "ir/subtypes.h"
#include "ir/type-updating.h"
#include "ir/utils.h"
#include "pass.h"
#include "support/unique_deferring_queue.h"
#include "wasm-traversal.h"
#include "wasm-type.h"
#include "wasm.h"

// Compute and use the minimal subtype relation required to maintain module
// validity and behavior. This minimal relation will be a subset of the original
// subtype relation. Start by walking the IR and collecting pairs of types that
// need to be in the subtype relation for each expression to validate. For
// example, a local.set requires that the type of its operand be a subtype of
// the local's type. Casts do not generate subtypings at this point because it
// is not necessary for the cast target to be a subtype of the cast source for
// the cast to validate.
//
// From that initial subtype relation, we then start finding new subtypings that
// are required by the subtypings we have found already. These transitively
// required subtypings come from two sources.
//
// The first source is type definitions. Consider these type definitions:
//
//   (type $A (sub (struct (ref $X))))
//   (type $B (sub $A (struct (ref $Y))))
//
// If we have determined that $B must remain a subtype of $A, then we know that
// $Y must remain a subtype of $X as well, since the type definitions would not
// be valid otherwise. Similarly, knowing that $X must remain a subtype of $Y
// may transitively require other subtypings as well based on their type
// definitions.
//
// The second source of transitive subtyping requirements is casts. Although
// casting from one type to another does not necessarily require that those
// types are related, we do need to make sure that we do not change the
// behavior of casts by removing subtype relationships they might observe. For
// example, consider this module:
//
// (module
//  ;; original subtyping: $bot <: $mid <: $top
//  (type $top (sub (struct)))
//  (type $mid (sub $top (struct)))
//  (type $bot (sub $mid (struct)))
//
//  (func $f
//   (local $top (ref $top))
//   (local $mid (ref $mid))
//
//   ;; Requires $bot <: $top
//   (local.set $top (struct.new $bot))
//
//   ;; Cast $top to $mid
//   (local.set $mid (ref.cast (ref $mid) (local.get $top)))
//  )
// )
//
// The only subtype relation directly required by the IR for this module is $bot
// <: $top. However, if we optimized the module so that $bot <: $top was the
// only subtype relation, we would change the behavior of the cast. In the
// original module, a value of type (ref $bot) is cast to (ref $mid). The cast
// succeeds because in the original module, $bot <: $mid. If we optimize so that
// we have $bot <: $top and no other subtypings, though, the cast will fail
// because the value of type (ref $bot) no longer inhabits (ref $mid). To
// prevent the cast's behavior from changing, we need to ensure that $bot <:
// $mid.
//
// The set of subtyping requirements generated by a cast from $src to $dest is
// that for every known remaining subtype $v of $src, if $v <: $dest in the
// original module, then $v <: $dest in the optimized module. In other words,
// for every type $v of values we know can flow into the cast, if the cast would
// have succeeded for values of type $v before, then we know the cast must
// continue to succeed for values of type $v. These requirements arising from
// casts can also generate transitive requirements because we learn about new
// types of values that can flow into casts as we learn about new subtypes of
// cast sources.
//
// Starting with the initial subtype relation determined by walking the IR,
// repeatedly search for new subtypings by analyzing type definitions and casts
// in lock step until we reach a fixed point. This is the minimal subtype
// relation that preserves module validity and behavior that can be found
// without a more precise analysis of types that might flow into each cast.

namespace wasm {

namespace {

struct Unsubtyping
  : WalkerPass<ControlFlowWalker<Unsubtyping, OverriddenVisitor<Unsubtyping>>> {
  // The new set of supertype relations.
  std::unordered_map<HeapType, HeapType> supertypes;

  // Map from cast source types to their destinations.
  std::unordered_map<HeapType, std::unordered_set<HeapType>> castTypes;

  // The set of subtypes that need to have their type definitions analyzed to
  // transitively find other subtype relations they depend on. We add to it
  // every time we find a new subtype relationship we need to keep.
  UniqueDeferredQueue<HeapType> work;

  void run(Module* wasm) override {
    if (!wasm->features.hasGC()) {
      return;
    }
    analyzePublicTypes(*wasm);
    walkModule(wasm);
    analyzeTransitiveDependencies();
    optimizeTypes(*wasm);
    // Cast types may be refinable if their source and target types are no
    // longer related. TODO: Experiment with running this only after checking
    // whether it is necessary.
    ReFinalize().run(getPassRunner(), wasm);
  }

  // Note that sub must remain a subtype of super.
  void noteSubtype(HeapType sub, HeapType super) {
    if (sub == super || sub.isBottom() || super.isBottom()) {
      return;
    }

    auto [it, inserted] = supertypes.insert({sub, super});
    if (inserted) {
      work.push(sub);
      // TODO: Incrementally check all subtypes (inclusive) of sub against super
      // and all its supertypes if we have already analyzed casts.
      return;
    }
    // We already had a recorded supertype. The new supertype might be deeper,
    // shallower, or identical to the old supertype.
    auto oldSuper = it->second;
    if (super == oldSuper) {
      return;
    }
    // There are two different supertypes, but each type can only have a single
    // direct subtype so the supertype chain cannot fork and one of the
    // supertypes must be a supertype of the other. Recursively record that
    // relationship as well.
    if (HeapType::isSubType(super, oldSuper)) {
      // sub <: super <: oldSuper
      it->second = super;
      work.push(sub);
      // TODO: Incrementally check all subtypes (inclusive) of sub against super
      // if we have already analyzed casts.
      noteSubtype(super, oldSuper);
    } else {
      // sub <: oldSuper <: super
      noteSubtype(oldSuper, super);
    }
  }

  void noteSubtype(Type sub, Type super) {
    if (sub.isTuple()) {
      assert(super.isTuple() && sub.size() == super.size());
      for (size_t i = 0, size = sub.size(); i < size; ++i) {
        noteSubtype(sub[i], super[i]);
      }
      return;
    }
    if (!sub.isRef() || !super.isRef()) {
      return;
    }
    noteSubtype(sub.getHeapType(), super.getHeapType());
  }

  void noteCast(HeapType src, HeapType dest) {
    if (src == dest || dest.isBottom()) {
      return;
    }
    assert(HeapType::isSubType(dest, src));
    castTypes[src].insert(dest);
  }

  void noteCast(Type src, Type dest) {
    assert(!src.isTuple() && !dest.isTuple());
    if (src == Type::unreachable) {
      return;
    }
    assert(src.isRef() && dest.isRef());
    noteCast(src.getHeapType(), dest.getHeapType());
  }

  void analyzePublicTypes(Module& wasm) {
    // We cannot change supertypes for anything public.
    for (auto type : ModuleUtils::getPublicHeapTypes(wasm)) {
      if (auto super = type.getDeclaredSuperType()) {
        noteSubtype(type, *super);
      }
    }
  }

  void analyzeTransitiveDependencies() {
    // While we have found new subtypings and have not reached a fixed point...
    while (!work.empty()) {
      // Subtype relationships that we are keeping might depend on other subtype
      // relationships that we are not yet planning to keep. Transitively find
      // all the relationships we need to keep all our type definitions valid.
      while (!work.empty()) {
        auto type = work.pop();
        auto super = supertypes.at(type);
        if (super.isBasic()) {
          continue;
        }
        if (type.isStruct()) {
          const auto& fields = type.getStruct().fields;
          const auto& superFields = super.getStruct().fields;
          for (size_t i = 0, size = superFields.size(); i < size; ++i) {
            noteSubtype(fields[i].type, superFields[i].type);
          }
        } else if (type.isArray()) {
          auto elem = type.getArray().element;
          noteSubtype(elem.type, super.getArray().element.type);
        } else {
          assert(type.isSignature());
          auto sig = type.getSignature();
          auto superSig = super.getSignature();
          noteSubtype(superSig.params, sig.params);
          noteSubtype(sig.results, superSig.results);
        }
      }

      // Analyze all casts at once.
      // TODO: This is expensive. Analyze casts incrementally after we
      // initially analyze them.
      analyzeCasts();
    }
  }

  void analyzeCasts() {
    // For each cast (src, dest) pair, any type that remains a subtype of src
    // (meaning its values can inhabit locations typed src) and that was
    // originally a subtype of dest (meaning its values would have passed the
    // cast) should remain a subtype of dest so that its values continue to pass
    // the cast.
    //
    // For every type, walk up its new supertype chain to find cast sources and
    // compare against their associated cast destinations.
    for (auto it = supertypes.begin(); it != supertypes.end(); ++it) {
      auto type = it->first;
      for (auto srcIt = it; srcIt != supertypes.end();
           srcIt = supertypes.find(srcIt->second)) {
        auto src = srcIt->second;
        auto destsIt = castTypes.find(src);
        if (destsIt == castTypes.end()) {
          continue;
        }
        for (auto dest : destsIt->second) {
          if (HeapType::isSubType(type, dest)) {
            noteSubtype(type, dest);
          }
        }
      }
    }
  }

  void optimizeTypes(Module& wasm) {
    struct Rewriter : GlobalTypeRewriter {
      Unsubtyping& parent;
      Rewriter(Unsubtyping& parent, Module& wasm)
        : GlobalTypeRewriter(wasm), parent(parent) {}
      std::optional<HeapType> getDeclaredSuperType(HeapType type) override {
        if (auto it = parent.supertypes.find(type);
            it != parent.supertypes.end() && !it->second.isBasic()) {
          return it->second;
        }
        return std::nullopt;
      }
    };
    Rewriter(*this, wasm).update();
  }

  void doWalkModule(Module* wasm) {
    // Visit the functions in parallel, filling in `supertypes` and `castTypes`
    // on separate instances which will later be merged.
    ModuleUtils::ParallelFunctionAnalysis<Unsubtyping> analysis(
      *wasm, [&](Function* func, Unsubtyping& unsubtyping) {
        if (!func->imported()) {
          unsubtyping.walkFunctionInModule(func, wasm);
        }
      });
    // Collect the results from the functions.
    for (auto& [_, unsubtyping] : analysis.map) {
      for (auto [sub, super] : unsubtyping.supertypes) {
        noteSubtype(sub, super);
      }
      for (auto& [src, dests] : unsubtyping.castTypes) {
        for (auto dest : dests) {
          noteCast(src, dest);
        }
      }
    }
    // Collect constraints from top-level items.
    for (auto& global : wasm->globals) {
      visitGlobal(global.get());
    }
    for (auto& seg : wasm->elementSegments) {
      visitElementSegment(seg.get());
    }
    // Visit the rest of the code that is not in functions.
    walkModuleCode(wasm);
  }

  void visitFunction(Function* func) {
    if (func->body) {
      noteSubtype(func->body->type, func->getResults());
    }
  }
  void visitGlobal(Global* global) {
    if (global->init) {
      noteSubtype(global->init->type, global->type);
    }
  }
  void visitElementSegment(ElementSegment* seg) {
    if (seg->offset) {
      noteSubtype(seg->type, getModule()->getTable(seg->table)->type);
    }
    for (auto init : seg->data) {
      noteSubtype(init->type, seg->type);
    }
  }
  void visitNop(Nop* curr) {}
  void visitBlock(Block* curr) {
    if (!curr->list.empty()) {
      noteSubtype(curr->list.back()->type, curr->type);
    }
  }
  void visitIf(If* curr) {
    if (curr->ifFalse) {
      noteSubtype(curr->ifTrue->type, curr->type);
      noteSubtype(curr->ifFalse->type, curr->type);
    }
  }
  void visitLoop(Loop* curr) { noteSubtype(curr->body->type, curr->type); }
  void visitBreak(Break* curr) {
    if (curr->value) {
      noteSubtype(curr->value->type, findBreakTarget(curr->name)->type);
    }
  }
  void visitSwitch(Switch* curr) {
    if (curr->value) {
      for (auto name : BranchUtils::getUniqueTargets(curr)) {
        noteSubtype(curr->value->type, findBreakTarget(name)->type);
      }
    }
  }
  template<typename T> void handleCall(T* curr, Signature sig) {
    assert(curr->operands.size() == sig.params.size());
    for (size_t i = 0, size = sig.params.size(); i < size; ++i) {
      noteSubtype(curr->operands[i]->type, sig.params[i]);
    }
    if (curr->isReturn) {
      noteSubtype(sig.results, getFunction()->getResults());
    }
  }
  void visitCall(Call* curr) {
    handleCall(curr, getModule()->getFunction(curr->target)->getSig());
  }
  void visitCallIndirect(CallIndirect* curr) {
    handleCall(curr, curr->heapType.getSignature());
    auto* table = getModule()->getTable(curr->table);
    auto tableType = table->type.getHeapType();
    if (HeapType::isSubType(tableType, curr->heapType)) {
      // Unlike other casts, where cast targets are always subtypes of cast
      // sources, call_indirect target types may be supertypes of their source
      // table types. In this case, the cast will always succeed, but only if we
      // keep the types related.
      noteSubtype(tableType, curr->heapType);
    } else if (HeapType::isSubType(curr->heapType, tableType)) {
      noteCast(tableType, curr->heapType);
    } else {
      // The types are unrelated and the cast will fail. We can keep the types
      // unrelated.
    }
  }
  void visitLocalGet(LocalGet* curr) {}
  void visitLocalSet(LocalSet* curr) {
    noteSubtype(curr->value->type, getFunction()->getLocalType(curr->index));
  }
  void visitGlobalGet(GlobalGet* curr) {}
  void visitGlobalSet(GlobalSet* curr) {
    noteSubtype(curr->value->type, getModule()->getGlobal(curr->name)->type);
  }
  void visitLoad(Load* curr) {}
  void visitStore(Store* curr) {}
  void visitAtomicRMW(AtomicRMW* curr) {}
  void visitAtomicCmpxchg(AtomicCmpxchg* curr) {}
  void visitAtomicWait(AtomicWait* curr) {}
  void visitAtomicNotify(AtomicNotify* curr) {}
  void visitAtomicFence(AtomicFence* curr) {}
  void visitSIMDExtract(SIMDExtract* curr) {}
  void visitSIMDReplace(SIMDReplace* curr) {}
  void visitSIMDShuffle(SIMDShuffle* curr) {}
  void visitSIMDTernary(SIMDTernary* curr) {}
  void visitSIMDShift(SIMDShift* curr) {}
  void visitSIMDLoad(SIMDLoad* curr) {}
  void visitSIMDLoadStoreLane(SIMDLoadStoreLane* curr) {}
  void visitMemoryInit(MemoryInit* curr) {}
  void visitDataDrop(DataDrop* curr) {}
  void visitMemoryCopy(MemoryCopy* curr) {}
  void visitMemoryFill(MemoryFill* curr) {}
  void visitConst(Const* curr) {}
  void visitUnary(Unary* curr) {}
  void visitBinary(Binary* curr) {}
  void visitSelect(Select* curr) {
    noteSubtype(curr->ifTrue->type, curr->type);
    noteSubtype(curr->ifFalse->type, curr->type);
  }
  void visitDrop(Drop* curr) {}
  void visitReturn(Return* curr) {
    if (curr->value) {
      noteSubtype(curr->value->type, getFunction()->getResults());
    }
  }
  void visitMemorySize(MemorySize* curr) {}
  void visitMemoryGrow(MemoryGrow* curr) {}
  void visitUnreachable(Unreachable* curr) {}
  void visitPop(Pop* curr) {}
  void visitRefNull(RefNull* curr) {}
  void visitRefIsNull(RefIsNull* curr) {}
  void visitRefFunc(RefFunc* curr) {}
  void visitRefEq(RefEq* curr) {}
  void visitTableGet(TableGet* curr) {}
  void visitTableSet(TableSet* curr) {
    noteSubtype(curr->value->type, getModule()->getTable(curr->table)->type);
  }
  void visitTableSize(TableSize* curr) {}
  void visitTableGrow(TableGrow* curr) {}
  void visitTableFill(TableFill* curr) {
    noteSubtype(curr->value->type, getModule()->getTable(curr->table)->type);
  }
  void visitTry(Try* curr) {
    noteSubtype(curr->body->type, curr->type);
    for (auto* body : curr->catchBodies) {
      noteSubtype(body->type, curr->type);
    }
  }
  void visitThrow(Throw* curr) {
    Type params = getModule()->getTag(curr->tag)->sig.params;
    assert(params.size() == curr->operands.size());
    for (size_t i = 0, size = curr->operands.size(); i < size; ++i) {
      noteSubtype(curr->operands[i]->type, params[i]);
    }
  }
  void visitRethrow(Rethrow* curr) {}
  void visitTupleMake(TupleMake* curr) {}
  void visitTupleExtract(TupleExtract* curr) {}
  void visitRefI31(RefI31* curr) {}
  void visitI31Get(I31Get* curr) {}
  void visitCallRef(CallRef* curr) {
    if (!curr->target->type.isSignature()) {
      return;
    }
    handleCall(curr, curr->target->type.getHeapType().getSignature());
  }
  void visitRefTest(RefTest* curr) {
    noteCast(curr->ref->type, curr->castType);
  }
  void visitRefCast(RefCast* curr) { noteCast(curr->ref->type, curr->type); }
  void visitBrOn(BrOn* curr) {
    if (curr->op == BrOnCast || curr->op == BrOnCastFail) {
      noteCast(curr->ref->type, curr->castType);
    }
    noteSubtype(curr->getSentType(), findBreakTarget(curr->name)->type);
  }
  void visitStructNew(StructNew* curr) {
    if (!curr->type.isStruct() || curr->isWithDefault()) {
      return;
    }
    const auto& fields = curr->type.getHeapType().getStruct().fields;
    assert(fields.size() == curr->operands.size());
    for (size_t i = 0, size = fields.size(); i < size; ++i) {
      noteSubtype(curr->operands[i]->type, fields[i].type);
    }
  }
  void visitStructGet(StructGet* curr) {}
  void visitStructSet(StructSet* curr) {
    if (!curr->ref->type.isStruct()) {
      return;
    }
    const auto& fields = curr->ref->type.getHeapType().getStruct().fields;
    noteSubtype(curr->value->type, fields[curr->index].type);
  }
  void visitArrayNew(ArrayNew* curr) {
    if (!curr->type.isArray() || curr->isWithDefault()) {
      return;
    }
    auto array = curr->type.getHeapType().getArray();
    noteSubtype(curr->init->type, array.element.type);
  }
  void visitArrayNewData(ArrayNewData* curr) {}
  void visitArrayNewElem(ArrayNewElem* curr) {
    if (!curr->type.isArray()) {
      return;
    }
    auto array = curr->type.getHeapType().getArray();
    auto* seg = getModule()->getElementSegment(curr->segment);
    noteSubtype(seg->type, array.element.type);
  }
  void visitArrayNewFixed(ArrayNewFixed* curr) {
    if (!curr->type.isArray()) {
      return;
    }
    auto array = curr->type.getHeapType().getArray();
    for (auto* value : curr->values) {
      noteSubtype(value->type, array.element.type);
    }
  }
  void visitArrayGet(ArrayGet* curr) {}
  void visitArraySet(ArraySet* curr) {
    if (!curr->ref->type.isArray()) {
      return;
    }
    auto array = curr->ref->type.getHeapType().getArray();
    noteSubtype(curr->value->type, array.element.type);
  }
  void visitArrayLen(ArrayLen* curr) {}
  void visitArrayCopy(ArrayCopy* curr) {
    if (!curr->srcRef->type.isArray() || !curr->destRef->type.isArray()) {
      return;
    }
    auto src = curr->srcRef->type.getHeapType().getArray();
    auto dest = curr->destRef->type.getHeapType().getArray();
    noteSubtype(src.element.type, dest.element.type);
  }
  void visitArrayFill(ArrayFill* curr) {
    if (!curr->ref->type.isArray()) {
      return;
    }
    auto array = curr->ref->type.getHeapType().getArray();
    noteSubtype(curr->value->type, array.element.type);
  }
  void visitArrayInitData(ArrayInitData* curr) {}
  void visitArrayInitElem(ArrayInitElem* curr) {
    if (!curr->ref->type.isArray()) {
      return;
    }
    auto array = curr->ref->type.getHeapType().getArray();
    auto* seg = getModule()->getElementSegment(curr->segment);
    noteSubtype(seg->type, array.element.type);
  }
  void visitRefAs(RefAs* curr) {}
  void visitStringNew(StringNew* curr) {}
  void visitStringConst(StringConst* curr) {}
  void visitStringMeasure(StringMeasure* curr) {}
  void visitStringEncode(StringEncode* curr) {}
  void visitStringConcat(StringConcat* curr) {}
  void visitStringEq(StringEq* curr) {}
  void visitStringAs(StringAs* curr) {}
  void visitStringWTF8Advance(StringWTF8Advance* curr) {}
  void visitStringWTF16Get(StringWTF16Get* curr) {}
  void visitStringIterNext(StringIterNext* curr) {}
  void visitStringIterMove(StringIterMove* curr) {}
  void visitStringSliceWTF(StringSliceWTF* curr) {}
  void visitStringSliceIter(StringSliceIter* curr) {}
};

} // anonymous namespace

Pass* createUnsubtypingPass() { return new Unsubtyping(); }

} // namespace wasm