effects.h

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

#ifndef wasm_ir_effects_h
#define wasm_ir_effects_h

#include <cassert>
#include <unordered_set>

#include "ir/intrinsics.h"
#include "pass.h"
#include "support/name.h"
#include "support/utilities.h"
#include "wasm-traversal.h"
#include "wasm-type.h"
#include "wasm.h"

namespace wasm {

// Analyze various possible effects.

class EffectAnalyzer {
public:
  EffectAnalyzer(const PassOptions& passOptions, const Module& module)
    : ignoreImplicitTraps(passOptions.ignoreImplicitTraps),
      trapsNeverHappen(passOptions.trapsNeverHappen), branchesOut(false),
      calls(false), readsMemory(false), writesMemory(false),
      readsSharedMemory(false), writesSharedMemory(false), readsTable(false),
      writesTable(false), readsMutableStruct(false), writesStruct(false),
      readsSharedMutableStruct(false), writesSharedStruct(false),
      readsMutableArray(false), writesArray(false),
      readsSharedMutableArray(false), writesSharedArray(false), trap(false),
      implicitTrap(false), throws_(false), danglingPop(false),
      mayNotReturn(false), hasReturnCallThrow(false), module(module),
      features(module.features) {}

  EffectAnalyzer(const PassOptions& passOptions,
                 const Module& module,
                 Expression* ast)
    : EffectAnalyzer(passOptions, module) {
    walk(ast);
  }

  EffectAnalyzer(const PassOptions& passOptions, Module& module, Function* func)
    : EffectAnalyzer(passOptions, module) {
    walk(func);
  }

  bool ignoreImplicitTraps : 1;
  bool trapsNeverHappen : 1;

  // Definitely branches out of this expression, or does a return, etc.
  // breakTargets tracks individual targets, which we may eventually see are
  // internal, while this is set when we see something that will definitely
  // not be internal, or is otherwise special like an infinite loop (which
  // does not technically branch "out", but it does break the normal assumption
  // of control flow proceeding normally).
  bool branchesOut : 1;

  bool calls : 1;
  bool readsMemory : 1;
  bool writesMemory : 1;
  bool readsSharedMemory : 1;
  bool writesSharedMemory : 1;
  bool readsTable : 1;
  bool writesTable : 1;

  // TODO: More specific type-based alias analysis, and not just at the
  //       struct/array level.
  bool readsMutableStruct : 1;
  bool writesStruct : 1;
  bool readsSharedMutableStruct : 1;
  bool writesSharedStruct : 1;
  bool readsMutableArray : 1;
  bool writesArray : 1;
  bool readsSharedMutableArray : 1;
  bool writesSharedArray : 1;

  // A trap, either from an unreachable instruction, or from an implicit trap
  // that we do not ignore (see below).
  //
  // Note that we ignore trap differences, so it is ok to reorder traps with
  // each other, but it is not ok to remove them or reorder them with other
  // effects in a noticeable way.
  //
  // Note also that we ignore *optional* runtime-specific traps: we only
  // consider as trapping something that will trap in *all* VMs, and *all* the
  // time. For example, a single allocation might trap in a VM in a particular
  // execution, if it happens to run out of memory just there, but that is not
  // enough for us to mark it as having a trap effect. (Note that not marking
  // each allocation as possibly trapping has the nice benefit of making it
  // possible to eliminate an allocation whose result is not captured.) OTOH, we
  // *do* mark a potentially infinite number of allocations as trapping, as all
  // VMs would trap eventually, and the same for potentially infinite recursion,
  // etc.
  bool trap : 1;

  // A trap from an instruction like a load or div/rem, which may trap on corner
  // cases. If we do not ignore implicit traps then these are counted as a trap.
  bool implicitTrap : 1;

  bool throws_ : 1;

  // If this expression contains 'pop's that are not enclosed in 'catch' body.
  // For example, (drop (pop i32)) should set this to true.
  bool danglingPop : 1;

  // Whether this code may "hang" and not eventually complete. An infinite loop,
  // or a continuation that is never continued, are examples of that.
  bool mayNotReturn : 1;

  // Since return calls return out of the body of the function before performing
  // their call, they are indistinguishable from normal returns from the
  // perspective of their surrounding code, and the return-callee's effects only
  // become visible when considering the effects of the whole function
  // containing the return call. To model this correctly, stash the callee's
  // effects on the side and only merge them in after walking a full function
  // body.
  //
  // We currently do this stashing only for the throw effect, but in principle
  // we could do it for all effects if it made a difference. (Only throw is
  // noticeable now because the only thing that can change between doing the
  // call here and doing it outside at the function exit is the scoping of
  // try-catch blocks. If future wasm scoping additions are added, we may need
  // more here.)
  bool hasReturnCallThrow : 1;

  const Module& module;
  FeatureSet features;

  std::set<Index> localsRead;
  std::set<Index> localsWritten;
  std::unordered_set<Name> mutableGlobalsRead;
  std::unordered_set<Name> globalsWritten;

  // The nested depth of try-catch_all. If an instruction that may throw is
  // inside an inner try-catch_all, we don't mark it as 'throws_', because it
  // will be caught by an inner catch_all. We only count 'try's with a
  // 'catch_all' because instructions within a 'try' without a 'catch_all' can
  // still throw outside of the try.
  size_t tryDepth = 0;
  // The nested depth of catch. This is necessary to track danglng pops.
  size_t catchDepth = 0;

  // The strongest memory orders used to read and write to any shared location
  // (e.g. shared memories, shared GC structs, etc), if any.
  MemoryOrder readOrder = MemoryOrder::Unordered;
  MemoryOrder writeOrder = MemoryOrder::Unordered;

  // Walk an expression and all its children.
  void walk(Expression* ast) {
    InternalAnalyzer(*this).walk(ast);
    post();
  }

  // Visit an expression, without any children.
  void visit(Expression* ast) {
    InternalAnalyzer(*this).visit(ast);
    post();
  }

  // Walk an entire function body. This will ignore effects that are not
  // noticeable from the perspective of the caller, that is, effects that are
  // only noticeable during the call, but "vanish" when the call stack is
  // unwound.
  //
  // Unlike walking just the body, walking the function will also
  // include the effects of any return calls the function makes. For that
  // reason, it is a bug if a user of this code calls walk(Expression*) and not
  // walk(Function*) if their intention is to scan an entire function body.
  // Putting it another way, a return_call is syntax sugar for a return and a
  // call, where the call executes at the function scope, so there is a
  // meaningful difference between scanning an expression and scanning
  // the entire function body.
  void walk(Function* func) {
    walk(func->body);

    // Effects of return-called functions will be visible to the caller.
    if (hasReturnCallThrow) {
      throws_ = true;
    }

    // We can ignore branching out of the function body - this can only be
    // a return, and that is only noticeable in the function, not outside.
    branchesOut = false;

    // When the function exits, changes to locals cannot be noticed any more.
    localsWritten.clear();
    localsRead.clear();
  }

  // Helper functions to check for various effect types

  bool accessesLocal() const {
    return localsRead.size() + localsWritten.size() > 0;
  }
  bool accessesMutableGlobal() const {
    return globalsWritten.size() + mutableGlobalsRead.size() > 0;
  }
  bool accessesMemory() const { return calls || readsMemory || writesMemory; }
  bool accessesSharedMemory() const {
    return calls || readsSharedMemory || writesSharedMemory;
  }
  bool accessesTable() const { return calls || readsTable || writesTable; }
  bool accessesMutableStruct() const {
    return calls || readsMutableStruct || writesStruct;
  }
  bool accessesSharedMutableStruct() const {
    return calls || readsSharedMutableStruct || writesSharedStruct;
  }
  bool accessesArray() const {
    return calls || readsMutableArray || writesArray;
  }
  bool accessesSharedArray() const {
    return calls || readsSharedMutableArray || writesSharedArray;
  }
  bool throws() const { return throws_ || !delegateTargets.empty(); }
  // Check whether this may transfer control flow to somewhere outside of this
  // expression (aside from just flowing out normally). That includes a break
  // or a throw (if the throw is not known to be caught inside this expression;
  // note that if the throw is not caught in this expression then it might be
  // caught in this function but outside of this expression, or it might not be
  // caught in the function at all, which would mean control flow cannot be
  // transferred inside the function, but this expression does not know that).
  bool transfersControlFlow() const {
    return branchesOut || throws() || hasExternalBreakTargets();
  }

  // Changes something in globally-stored state.
  bool writesGlobalState() const {
    return globalsWritten.size() || writesMemory || writesSharedMemory ||
           writesTable || writesStruct || writesSharedStruct || writesArray ||
           writesSharedArray || calls;
  }
  bool readsMutableGlobalState() const {
    return mutableGlobalsRead.size() || readsMemory || readsSharedMemory ||
           readsTable || readsMutableStruct || readsSharedMutableStruct ||
           readsMutableArray || readsSharedMutableArray || calls;
  }
  bool accessesSharedGlobalState() const {
    return readsSharedMemory || writesSharedMemory ||
           readsSharedMutableStruct || writesSharedStruct ||
           readsSharedMutableArray || writesSharedArray || calls;
  }

  bool hasSynchronization() const {
    return readOrder != MemoryOrder::Unordered ||
           writeOrder != MemoryOrder::Unordered;
  }

  bool hasNonTrapSideEffects() const {
    return localsWritten.size() > 0 || danglingPop || writesGlobalState() ||
           throws() || transfersControlFlow() || hasSynchronization() ||
           mayNotReturn;
  }

  bool hasSideEffects() const { return trap || hasNonTrapSideEffects(); }

  // Check if there are side effects, and they are of a kind that cannot be
  // removed by optimization passes.
  //
  // The difference between this and hasSideEffects is subtle, and only related
  // to trapsNeverHappen - if trapsNeverHappen then any trap we see is removable
  // by optimizations. In general, you should call hasSideEffects, and only call
  // this method if you are certain that it is a place that would not perform an
  // unsafe transformation with a trap. Specifically, if a pass calls this
  // and gets the result that there are no unremovable side effects, then it
  // must either
  //
  //  1. Remove any side effects present, if any, so they no longer exist.
  //  2. Keep the code exactly where it is.
  //
  // If instead of 1&2 a pass kept the side effect and also reordered the code
  // with other things, then that could be bad, as the side effect might have
  // been behind a condition that avoids it occurring.
  //
  // TODO: Go through the optimizer and use this in all places that do not move
  //       code around.
  bool hasUnremovableSideEffects() const {
    return hasNonTrapSideEffects() || (trap && !trapsNeverHappen);
  }

  bool hasAnything() const {
    return hasSideEffects() || accessesLocal() || readsMutableGlobalState();
  }

  // check if we break to anything external from ourselves
  bool hasExternalBreakTargets() const { return !breakTargets.empty(); }

  // Checks if these effects must remain ordered before another set of effects
  // (e.g., if we write, we must remain ordered before someone that reads).
  //
  // This assumes the things whose effects we are comparing will both execute,
  // at least if neither of them transfers control flow away. We assume there is
  // no transfer of control flow *between* them. It is not valid to call this
  // method in other situations, like this:
  //
  //   A
  //   (br_if 0 (local.get 0)) ;; this may transfer control flow away
  //   B
  //
  // Calling this method in that situation is invalid because only A may
  // execute and not B. The following are examples of situations where it is
  // valid to call this method:
  //
  //   A
  //   ;; nothing in between them at all
  //   B
  //
  //   A
  //   (local.set 0 (i32.const 0)) ;; something in between without a possible
  //                               ;; control flow transfer
  //   B
  //
  // (Note that if they appear in inside a loop, A and B may overlap or even be
  // the same expression; this is fine because A still executes before B, even
  // if also executes during and after B across different loop iterations.) That
  // A and B both execute only matters in the case of traps-never-happen: in
  // that mode we can move traps but only if doing so would not make them start
  // to appear when they did not previously. In the example with the br_if we
  // can't reorder A and B if B traps, but in the valid examples we can reorder
  // them even if B traps (even if A has a global effect like a global.set,
  // since we assume B does not trap in traps-never-happen).
  bool orderedBefore(const EffectAnalyzer& other) const {
    // Cannot reorder control flow and side effects.
    if ((transfersControlFlow() && other.hasSideEffects()) ||
        (other.transfersControlFlow() && hasSideEffects())) {
      return true;
    }
    // write-write, write-read, and read-write conflicts on possibly aliasing
    // locations prevent reordering. Calls may access these locations.
    if (((writesMemory || calls) && other.accessesMemory()) ||
        ((other.writesMemory || other.calls) && accessesMemory()) ||
        ((writesSharedMemory || calls) && other.accessesSharedMemory()) ||
        ((other.writesSharedMemory || other.calls) && accessesSharedMemory()) ||
        ((writesTable || calls) && other.accessesTable()) ||
        ((other.writesTable || other.calls) && accessesTable()) ||
        ((writesStruct || calls) && other.accessesMutableStruct()) ||
        ((other.writesStruct || other.calls) && accessesMutableStruct()) ||
        ((writesSharedStruct || calls) &&
         other.accessesSharedMutableStruct()) ||
        ((other.writesSharedStruct || other.calls) &&
         accessesSharedMutableStruct()) ||
        ((writesArray || calls) && other.accessesArray()) ||
        ((other.writesArray || other.calls) && accessesArray()) ||
        ((writesSharedArray || calls) && other.accessesSharedArray()) ||
        ((other.writesSharedArray || other.calls) && accessesSharedArray())) {
      return true;
    }
    // Cannot reorder anything before dangling pops.
    if (danglingPop) {
      return true;
    }
    // Relaxed (or stronger) loads cannot be reordered after relaxed (or
    // stronger) stores.
    if (readOrder >= MemoryOrder::Relaxed &&
        other.writeOrder >= MemoryOrder::Relaxed) {
      return true;
    }
    // Shared location accesses cannot be reordered after (but may be able to be
    // reordered before) release stores.
    if (other.writeOrder >= MemoryOrder::AcqRel &&
        accessesSharedGlobalState()) {
      return true;
    }
    // Shared location accesses cannot be reordered before (but may be able to
    // be reordered after) acquire loads.
    if (readOrder >= MemoryOrder::AcqRel && other.accessesSharedGlobalState()) {
      return true;
    }
    // No shared location accesses may be reordered in either direction around a
    // seqcst operation.
    if (((readOrder == MemoryOrder::SeqCst ||
          writeOrder == MemoryOrder::SeqCst) &&
         other.accessesSharedGlobalState()) ||
        ((other.readOrder == MemoryOrder::SeqCst ||
          other.writeOrder == MemoryOrder::SeqCst) &&
         accessesSharedGlobalState())) {
      return true;
    }
    // write-write, write-read, and read-write conflicts on a local prevent
    // reordering.
    for (auto local : localsWritten) {
      if (other.localsRead.contains(local) ||
          other.localsWritten.contains(local)) {
        return true;
      }
    }
    for (auto local : localsRead) {
      if (other.localsWritten.contains(local)) {
        return true;
      }
    }
    // write-write, write-read, and read-write conflicts on globals prevent
    // reordering. Unlike for locals, calls can access globals.
    if ((other.calls && accessesMutableGlobal()) ||
        (calls && other.accessesMutableGlobal())) {
      return true;
    }
    for (auto global : globalsWritten) {
      if (other.mutableGlobalsRead.contains(global) ||
          other.globalsWritten.contains(global)) {
        return true;
      }
    }
    for (auto global : mutableGlobalsRead) {
      if (other.globalsWritten.contains(global)) {
        return true;
      }
    }
    // Note that the above includes disallowing the reordering of a trap with an
    // exception (as an exception can transfer control flow inside the current
    // function, so transfersControlFlow would be true) - while we allow the
    // reordering of traps with each other, we do not reorder exceptions with
    // anything.
    assert(!((trap && other.throws()) || (throws() && other.trap)));
    // We can't reorder an implicit trap in a way that could alter what global
    // state is modified. However, in trapsNeverHappen mode we assume traps do
    // not occur in practice, which lets us ignore this, at least in the case
    // that the code executes. As mentioned above, we assume that there is no
    // transfer of control flow between the things we are comparing, so all we
    // need to do is check for such transfers in them.
    if (!trapsNeverHappen || transfersControlFlow() ||
        other.transfersControlFlow()) {
      if ((trap && other.writesGlobalState()) ||
          (other.trap && writesGlobalState())) {
        return true;
      }
    }
    return false;
  }

  bool orderedAfter(const EffectAnalyzer& other) {
    return other.orderedBefore(*this);
  }

  // Whether these effects are prevented from moving past the other effects in
  // either direction.
  // TODO: Update users to check order more precisely and remove this.
  bool invalidates(const EffectAnalyzer& other) {
    return orderedBefore(other) || orderedAfter(other);
  }

  void mergeIn(const EffectAnalyzer& other) {
    branchesOut = branchesOut || other.branchesOut;
    calls = calls || other.calls;
    readsMemory = readsMemory || other.readsMemory;
    writesMemory = writesMemory || other.writesMemory;
    readsSharedMemory = readsSharedMemory || other.readsSharedMemory;
    writesSharedMemory = writesSharedMemory || other.writesSharedMemory;
    readsTable = readsTable || other.readsTable;
    writesTable = writesTable || other.writesTable;
    readsMutableStruct = readsMutableStruct || other.readsMutableStruct;
    writesStruct = writesStruct || other.writesStruct;
    readsSharedMutableStruct =
      readsSharedMutableStruct || other.readsSharedMutableStruct;
    writesSharedStruct = writesSharedStruct || other.writesSharedStruct;
    readsMutableArray = readsMutableArray || other.readsMutableArray;
    writesArray = writesArray || other.writesArray;
    readsSharedMutableArray =
      readsSharedMutableArray || other.readsSharedMutableArray;
    writesSharedArray = writesSharedArray || other.writesSharedArray;
    trap = trap || other.trap;
    implicitTrap = implicitTrap || other.implicitTrap;
    trapsNeverHappen = trapsNeverHappen || other.trapsNeverHappen;
    throws_ = throws_ || other.throws_;
    danglingPop = danglingPop || other.danglingPop;
    mayNotReturn = mayNotReturn || other.mayNotReturn;
    hasReturnCallThrow = hasReturnCallThrow || other.hasReturnCallThrow;
    readOrder = std::max(readOrder, other.readOrder);
    writeOrder = std::max(writeOrder, other.writeOrder);

    for (auto i : other.localsRead) {
      localsRead.insert(i);
    }
    for (auto i : other.localsWritten) {
      localsWritten.insert(i);
    }
    for (auto i : other.mutableGlobalsRead) {
      mutableGlobalsRead.insert(i);
    }
    for (auto i : other.globalsWritten) {
      globalsWritten.insert(i);
    }
    for (auto i : other.breakTargets) {
      breakTargets.insert(i);
    }
    for (auto i : other.delegateTargets) {
      delegateTargets.insert(i);
    }
  }

  // the checks above happen after the node's children were processed, in the
  // order of execution we must also check for control flow that happens before
  // the children, i.e., loops
  bool checkPre(Expression* curr) {
    if (curr->is<Loop>()) {
      branchesOut = true;
      return true;
    }
    return false;
  }

  bool checkPost(Expression* curr) {
    visit(curr);
    if (curr->is<Loop>()) {
      branchesOut = true;
    }
    return hasAnything();
  }

  std::unordered_set<Name> breakTargets;
  std::unordered_set<Name> delegateTargets;

private:
  struct InternalAnalyzer
    : public PostWalker<InternalAnalyzer, OverriddenVisitor<InternalAnalyzer>> {

    EffectAnalyzer& parent;

    InternalAnalyzer(EffectAnalyzer& parent) : parent(parent) {}

    static void scan(InternalAnalyzer* self, Expression** currp) {
      Expression* curr = *currp;
      // We need to decrement try depth before catch starts, so handle it
      // separately
      if (curr->is<Try>()) {
        self->pushTask(doVisitTry, currp);
        self->pushTask(doEndCatch, currp);
        auto& catchBodies = curr->cast<Try>()->catchBodies;
        for (int i = int(catchBodies.size()) - 1; i >= 0; i--) {
          self->pushTask(scan, &catchBodies[i]);
        }
        self->pushTask(doStartCatch, currp);
        self->pushTask(scan, &curr->cast<Try>()->body);
        self->pushTask(doStartTry, currp);
        return;
      }
      if (auto* tryTable = curr->dynCast<TryTable>()) {
        // We need to increment try depth before starting.
        self->pushTask(doEndTryTable, currp);
        self->pushTask(doVisitTryTable, currp);
        self->pushTask(scan, &tryTable->body);
        self->pushTask(doStartTryTable, currp);
        return;
      }
      PostWalker<InternalAnalyzer, OverriddenVisitor<InternalAnalyzer>>::scan(
        self, currp);
    }

    static void doStartTry(InternalAnalyzer* self, Expression** currp) {
      Try* curr = (*currp)->cast<Try>();
      // We only count 'try's with a 'catch_all' because instructions within a
      // 'try' without a 'catch_all' can still throw outside of the try.
      if (curr->hasCatchAll()) {
        self->parent.tryDepth++;
      }
    }

    static void doStartCatch(InternalAnalyzer* self, Expression** currp) {
      Try* curr = (*currp)->cast<Try>();
      // This is conservative. When an inner try-delegate targets the current
      // expression, even if the try-delegate's body can't throw, we consider
      // the current expression can throw for simplicity, unless the current
      // expression is not inside a try-catch_all. It is hard to figure out
      // whether the original try-delegate's body throws or not at this point.
      if (curr->name.is()) {
        if (self->parent.delegateTargets.contains(curr->name) &&
            self->parent.tryDepth == 0) {
          self->parent.throws_ = true;
        }
        self->parent.delegateTargets.erase(curr->name);
      }
      // We only count 'try's with a 'catch_all' because instructions within a
      // 'try' without a 'catch_all' can still throw outside of the try.
      if (curr->hasCatchAll()) {
        assert(self->parent.tryDepth > 0 && "try depth cannot be negative");
        self->parent.tryDepth--;
      }
      self->parent.catchDepth++;
    }

    static void doEndCatch(InternalAnalyzer* self, Expression** currp) {
      assert(self->parent.catchDepth > 0 && "catch depth cannot be negative");
      self->parent.catchDepth--;
    }

    static void doStartTryTable(InternalAnalyzer* self, Expression** currp) {
      auto* curr = (*currp)->cast<TryTable>();
      // We only count 'try_table's with a 'catch_all' because instructions
      // within a 'try_table' without a 'catch_all' can still throw outside of
      // the try.
      if (curr->hasCatchAll()) {
        self->parent.tryDepth++;
      }
    }

    static void doEndTryTable(InternalAnalyzer* self, Expression** currp) {
      auto* curr = (*currp)->cast<TryTable>();
      if (curr->hasCatchAll()) {
        assert(self->parent.tryDepth > 0 && "try depth cannot be negative");
        self->parent.tryDepth--;
      }
    }

    void readsMemory(Name memory, MemoryOrder order) {
      if (parent.module.getMemory(memory)->shared) {
        parent.readsSharedMemory = true;
        parent.readOrder = std::max(parent.readOrder, order);
      } else {
        parent.readsMemory = true;
      }
    }

    void writesMemory(Name memory, MemoryOrder order) {
      if (parent.module.getMemory(memory)->shared) {
        parent.writesSharedMemory = true;
        parent.writeOrder = std::max(parent.writeOrder, order);
      } else {
        parent.writesMemory = true;
      }
    }

    void readsStruct(HeapType type, Index index, MemoryOrder order) {
      assert(type.isStruct());
      if (type.getStruct().fields[index].mutable_ == Mutable) {
        if (type.isShared()) {
          parent.readsSharedMutableStruct = true;
          parent.readOrder = std::max(parent.readOrder, order);
        } else {
          parent.readsMutableStruct = true;
        }
      }
    }

    void writesStruct(HeapType type, Index index, MemoryOrder order) {
      assert(type.isStruct());
      if (type.isShared()) {
        parent.writesSharedStruct = true;
        parent.writeOrder = std::max(parent.writeOrder, order);
      } else {
        parent.writesStruct = true;
      }
    }

    void readsArray(HeapType type, MemoryOrder order) {
      assert(type.isArray());
      if (type.getArray().element.mutable_ == Mutable) {
        if (type.isShared()) {
          parent.readsSharedMutableArray = true;
          parent.readOrder = std::max(parent.readOrder, order);
        } else {
          parent.readsMutableArray = true;
        }
      }
    }

    void writesArray(HeapType type, MemoryOrder order) {
      assert(type.isArray());
      if (type.isShared()) {
        parent.writesSharedArray = true;
        parent.writeOrder = std::max(parent.writeOrder, order);
      } else {
        parent.writesArray = true;
      }
    }

    // Handle effects due to a null type arriving in a place where a null input
    // causes trapping. That is, handle the case of the type proving that the
    // input is null.
    // Returns true iff there is no need to consider further effects.
    bool trapOnNull(Type type) {
      if (type == Type::unreachable) {
        return true;
      }
      assert(type.isRef());
      if (type.isNull()) {
        parent.trap = true;
        return true;
      }
      if (type.isNullable()) {
        parent.implicitTrap = true;
      }

      return false;
    }

    // Handle effects due to an explicit null check of the operands in `exprs`.
    // Returns true iff there is no need to consider further effects.
    bool trapOnNull(std::initializer_list<Expression*> exprs) {
      for (auto* expr : exprs) {
        if (expr && trapOnNull(expr->type)) {
          return true;
        }
      }
      return false;
    }

    bool trapOnNull(Expression* expr) { return trapOnNull({expr}); }

    void visitBlock(Block* curr) {
      if (curr->name.is()) {
        parent.breakTargets.erase(curr->name); // these were internal breaks
      }
    }
    void visitIf(If* curr) {}
    void visitLoop(Loop* curr) {
      if (curr->name.is() && parent.breakTargets.erase(curr->name) > 0) {
        parent.mayNotReturn = true;
      }
    }
    void visitBreak(Break* curr) { parent.breakTargets.insert(curr->name); }
    void visitSwitch(Switch* curr) {
      for (auto name : curr->targets) {
        parent.breakTargets.insert(name);
      }
      parent.breakTargets.insert(curr->default_);
    }

    void visitCall(Call* curr) {
      if (Intrinsics(parent.module).isCallWithoutEffects(curr)) {
        // The only effect this can have is to branch (which is an effect of the
        // return, not the call).
        if (curr->isReturn) {
          parent.branchesOut = true;
        }
        return;
      }

      const EffectAnalyzer* callTargetEffects = nullptr;
      if (auto* target = parent.module.getFunctionOrNull(curr->target);
          target && target->effects) {
        callTargetEffects = target->effects.get();
      }
      addCallEffects(curr, callTargetEffects);
    }
    void visitCallIndirect(CallIndirect* curr) {
      auto* table = parent.module.getTable(curr->table);
      if (trapOnNull(table->type)) {
        return;
      }

      if (!Type::isSubType(Type(curr->heapType, Nullability::NonNullable),
                           table->type)) {
        parent.trap = true;
        return;
      }

      // Due to index out of bounds. Type-related traps are handled above and
      // may set either implicitTrap or trap (or neither).
      parent.implicitTrap = true;

      const EffectAnalyzer* callTargetEffects = nullptr;
      if (auto it = parent.module.indirectCallEffects.find(curr->heapType);
          it != parent.module.indirectCallEffects.end()) {
        callTargetEffects = it->second.get();
      }
      addCallEffects(curr, callTargetEffects);
    }
    void visitCallRef(CallRef* curr) {
      if (trapOnNull(curr->target)) {
        return;
      }

      const EffectAnalyzer* callTargetEffects = nullptr;
      if (auto it = parent.module.indirectCallEffects.find(
            curr->target->type.getHeapType());
          it != parent.module.indirectCallEffects.end()) {
        callTargetEffects = it->second.get();
      }
      addCallEffects(curr, callTargetEffects);
    }
    void visitLocalGet(LocalGet* curr) {
      parent.localsRead.insert(curr->index);
    }
    void visitLocalSet(LocalSet* curr) {
      parent.localsWritten.insert(curr->index);
    }
    void visitGlobalGet(GlobalGet* curr) {
      if (parent.module.getGlobal(curr->name)->mutable_ == Mutable) {
        parent.mutableGlobalsRead.insert(curr->name);
      }
    }
    void visitGlobalSet(GlobalSet* curr) {
      parent.globalsWritten.insert(curr->name);
    }
    void visitLoad(Load* curr) {
      readsMemory(curr->memory, curr->order);
      parent.implicitTrap = true;
    }
    void visitStore(Store* curr) {
      writesMemory(curr->memory, curr->order);
      parent.implicitTrap = true;
    }
    void visitAtomicRMW(AtomicRMW* curr) {
      readsMemory(curr->memory, curr->order);
      writesMemory(curr->memory, curr->order);
      parent.implicitTrap = true;
    }
    void visitAtomicCmpxchg(AtomicCmpxchg* curr) {
      readsMemory(curr->memory, curr->order);
      writesMemory(curr->memory, curr->order);
      parent.implicitTrap = true;
    }
    void visitAtomicWait(AtomicWait* curr) {
      // Waits on unshared memories trap.
      if (!parent.module.getMemory(curr->memory)->shared) {
        parent.trap = true;
        return;
      }
      // AtomicWait doesn't strictly write memory, but it does modify the
      // waiters list associated with the specified address, which we can think
      // of as a write.
      parent.readsSharedMemory = true;
      parent.writesSharedMemory = true;
      parent.readOrder = parent.writeOrder = MemoryOrder::SeqCst;
      // Traps on unaligned accesses.
      parent.implicitTrap = true;
    }
    void visitAtomicNotify(AtomicNotify* curr) {
      // Notifies on unshared memories just return 0 or trap on unaligned
      // accesses.
      parent.implicitTrap = true;
      if (!parent.module.getMemory(curr->memory)->shared) {
        return;
      }
      // AtomicNotify doesn't strictly write memory, but it does
      // modify the waiters list associated with the specified address, which we
      // can think of as a write.
      parent.readsSharedMemory = true;
      parent.writesSharedMemory = true;
      parent.readOrder = parent.writeOrder = MemoryOrder::SeqCst;
    }
    void visitAtomicFence(AtomicFence* curr) {
      // AtomicFence should not be reordered with any shared location accesses,
      // so we set these to true.
      parent.readsSharedMemory = true;
      parent.writesSharedMemory = true;
      parent.readsSharedMutableStruct = true;
      parent.writesSharedStruct = true;
      parent.readsSharedMutableArray = true;
      parent.writesSharedArray = true;
      parent.readOrder = parent.writeOrder = MemoryOrder::SeqCst;
    }
    void visitPause(Pause* curr) {
      // We don't want this to be moved out of loops, but it doesn't otherwises
      // matter much how it gets reordered. Say we transfer control as a coarse
      // approximation of this.
      parent.branchesOut = true;
    }
    void visitSIMDExtract(SIMDExtract* curr) {}
    void visitSIMDReplace(SIMDReplace* curr) {}
    void visitSIMDShuffle(SIMDShuffle* curr) {}
    void visitSIMDTernary(SIMDTernary* curr) {}
    void visitSIMDShift(SIMDShift* curr) {}
    void visitSIMDLoad(SIMDLoad* curr) {
      readsMemory(curr->memory, MemoryOrder::Unordered);
      parent.implicitTrap = true;
    }
    void visitSIMDLoadStoreLane(SIMDLoadStoreLane* curr) {
      if (curr->isLoad()) {
        readsMemory(curr->memory, MemoryOrder::Unordered);
      } else {
        writesMemory(curr->memory, MemoryOrder::Unordered);
      }
      parent.implicitTrap = true;
    }
    void visitMemoryInit(MemoryInit* curr) {
      writesMemory(curr->memory, MemoryOrder::Unordered);
      parent.implicitTrap = true;
    }
    void visitDataDrop(DataDrop* curr) {
      // data.drop does not actually write memory, but it does alter the size of
      // a segment, which can be noticeable later by memory.init, so we need to
      // mark it as having a global side effect of some kind.
      parent.writesMemory = true;
      parent.implicitTrap = true;
    }
    void visitMemoryCopy(MemoryCopy* curr) {
      readsMemory(curr->sourceMemory, MemoryOrder::Unordered);
      writesMemory(curr->destMemory, MemoryOrder::Unordered);
      parent.implicitTrap = true;
    }
    void visitMemoryFill(MemoryFill* curr) {
      writesMemory(curr->memory, MemoryOrder::Unordered);
      parent.implicitTrap = true;
    }
    void visitConst(Const* curr) {}
    void visitUnary(Unary* curr) {
      switch (curr->op) {
        case TruncSFloat32ToInt32:
        case TruncSFloat32ToInt64:
        case TruncUFloat32ToInt32:
        case TruncUFloat32ToInt64:
        case TruncSFloat64ToInt32:
        case TruncSFloat64ToInt64:
        case TruncUFloat64ToInt32:
        case TruncUFloat64ToInt64: {
          parent.implicitTrap = true;
          break;
        }
        default: {
        }
      }
    }
    void visitBinary(Binary* curr) {
      switch (curr->op) {
        case DivSInt32:
        case DivUInt32:
        case RemSInt32:
        case RemUInt32:
        case DivSInt64:
        case DivUInt64:
        case RemSInt64:
        case RemUInt64: {
          // div and rem may contain implicit trap only if RHS is
          // non-constant or constant which equal zero or -1 for
          // signed divisions. Reminder traps only with zero
          // divider.
          if (auto* c = curr->right->dynCast<Const>()) {
            if (c->value.isZero()) {
              parent.implicitTrap = true;
            } else if ((curr->op == DivSInt32 || curr->op == DivSInt64) &&
                       c->value.getInteger() == -1LL) {
              parent.implicitTrap = true;
            }
          } else {
            parent.implicitTrap = true;
          }
          break;
        }
        default: {
        }
      }
    }
    void visitWideIntAddSub(WideIntAddSub* curr) {}
    void visitWideIntMul(WideIntMul* curr) {}
    void visitSelect(Select* curr) {}
    void visitDrop(Drop* curr) {}
    void visitReturn(Return* curr) { parent.branchesOut = true; }
    void visitMemorySize(MemorySize* curr) {
      // memory.size accesses the size of the memory, and thus can be modeled as
      // reading memory. When the memory is shared, this synchronizes with
      // memory.grow on other threads.
      readsMemory(curr->memory, MemoryOrder::SeqCst);
    }
    void visitMemoryGrow(MemoryGrow* curr) {
      // memory.grow technically does a read-modify-write operation on the
      // memory size in the successful case, modifying the set of valid
      // addresses, and just a read operation in the failure case. It
      // synchronizes with memory.size on other threads, but only when operating
      // on shared memories.
      readsMemory(curr->memory, MemoryOrder::SeqCst);
      writesMemory(curr->memory, MemoryOrder::SeqCst);
    }
    void visitRefNull(RefNull* curr) {}
    void visitRefIsNull(RefIsNull* curr) {}
    void visitRefFunc(RefFunc* curr) {}
    void visitRefEq(RefEq* curr) {}
    void visitTableGet(TableGet* curr) {
      parent.readsTable = true;
      parent.implicitTrap = true;
    }
    void visitTableSet(TableSet* curr) {
      parent.writesTable = true;
      parent.implicitTrap = true;
    }
    void visitTableSize(TableSize* curr) { parent.readsTable = true; }
    void visitTableGrow(TableGrow* curr) {
      // table.grow technically does a read-modify-write operation on the
      // table size in the successful case, modifying the set of valid
      // indices, and just a read operation in the failure case
      parent.readsTable = true;
      parent.writesTable = true;
    }
    void visitTableFill(TableFill* curr) {
      parent.writesTable = true;
      parent.implicitTrap = true;
    }
    void visitTableCopy(TableCopy* curr) {
      parent.readsTable = true;
      parent.writesTable = true;
      parent.implicitTrap = true;
    }
    void visitTableInit(TableInit* curr) {
      parent.writesTable = true;
      parent.implicitTrap = true;
    }
    void visitElemDrop(ElemDrop* curr) { parent.writesTable = true; }
    void visitTry(Try* curr) {
      if (curr->delegateTarget.is()) {
        parent.delegateTargets.insert(curr->delegateTarget);
      }
    }
    void visitTryTable(TryTable* curr) {
      for (auto name : curr->catchDests) {
        parent.breakTargets.insert(name);
      }
    }
    void visitThrow(Throw* curr) {
      if (parent.tryDepth == 0) {
        parent.throws_ = true;
      }
    }
    void visitRethrow(Rethrow* curr) {
      if (parent.tryDepth == 0) {
        parent.throws_ = true;
      }
    }
    void visitThrowRef(ThrowRef* curr) {
      if (trapOnNull(curr->exnref)) {
        return;
      }
      if (parent.tryDepth == 0) {
        parent.throws_ = true;
      }
    }
    void visitNop(Nop* curr) {}
    void visitUnreachable(Unreachable* curr) { parent.trap = true; }
    void visitPop(Pop* curr) {
      if (parent.catchDepth == 0) {
        parent.danglingPop = true;
      }
    }
    void visitTupleMake(TupleMake* curr) {}
    void visitTupleExtract(TupleExtract* curr) {}
    void visitRefI31(RefI31* curr) {}
    void visitI31Get(I31Get* curr) { trapOnNull(curr->i31); }
    void visitRefTest(RefTest* curr) {}

    void visitRefCast(RefCast* curr) {
      if (trapOnNull(curr->desc)) {
        return;
      }
      // Traps if the cast fails.
      parent.implicitTrap = true;
    }
    void visitRefGetDesc(RefGetDesc* curr) { trapOnNull(curr->ref); }
    void visitBrOn(BrOn* curr) {
      parent.breakTargets.insert(curr->name);
      trapOnNull(curr->desc);
    }
    void visitStructNew(StructNew* curr) { trapOnNull(curr->desc); }
    void visitStructGet(StructGet* curr) {
      if (trapOnNull(curr->ref)) {
        return;
      }
      readsStruct(curr->ref->type.getHeapType(), curr->index, curr->order);
    }
    void visitStructSet(StructSet* curr) {
      if (trapOnNull(curr->ref)) {
        return;
      }
      writesStruct(curr->ref->type.getHeapType(), curr->index, curr->order);
    }
    template<typename StructRMWExpr>
    void visitStructRMWExpr(StructRMWExpr* curr) {
      if (trapOnNull(curr->ref)) {
        return;
      }
      auto heapType = curr->ref->type.getHeapType();
      readsStruct(heapType, curr->index, curr->order);
      writesStruct(heapType, curr->index, curr->order);
    }
    void visitStructRMW(StructRMW* curr) { visitStructRMWExpr(curr); }
    void visitStructCmpxchg(StructCmpxchg* curr) { visitStructRMWExpr(curr); }
    void visitStructWait(StructWait* curr) {
      if (trapOnNull({curr->ref, curr->waitqueue})) {
        return;
      }

      // StructWait doesn't strictly write a struct, but it does modify the
      // waiters list associated with the waitqueue, which we can think
      // of as a write.
      parent.readsSharedMutableStruct = true;
      parent.writesSharedStruct = true;
      parent.readOrder = parent.writeOrder = MemoryOrder::SeqCst;

      // If the timeout is negative and no-one wakes us.
      parent.mayNotReturn = true;
    }
    void visitWaitqueueNew(WaitqueueNew* curr) {}
    void visitWaitqueueNotify(WaitqueueNotify* curr) {
      if (trapOnNull(curr->waitqueue)) {
        return;
      }
      // WaitqueueNotify doesn't strictly write anything, but it does
      // modify the waiters list associated with the waitqueue, which we
      // can think of as a write.
      parent.readsSharedMutableStruct = true;
      parent.writesSharedStruct = true;
      parent.readOrder = parent.writeOrder = MemoryOrder::SeqCst;
    }
    void visitPublish(Publish* curr) {
      // Publish is a no-op on anything besides shared structs and arrays.
      if (!curr->ref->type.isRef()) {
        return;
      }
      auto heapType = curr->ref->type.getHeapType();
      if (!heapType.isShared()) {
        return;
      }
      if (!heapType.isStruct() && !heapType.isMaybeShared(HeapType::struct_) &&
          !heapType.isArray() && !heapType.isMaybeShared(HeapType::array) &&
          !heapType.isMaybeShared(HeapType::eq) &&
          !heapType.isMaybeShared(HeapType::any)) {
        return;
      }
      // TODO: Modeling `publish` as an arbitrary call is not sufficient. While
      // it conservatively prevents writes to global state (shared or unshared
      // structs/arrays, globals, memory, tables) from reordering across
      // `publish`, it has two major shortcomings:
      //
      // 1. It is overly conservative for reads and independent writes: it
      //    prevents reads of all kinds from reordering around `publish`, even
      //    though reads of all memory orders should be allowed to reorder
      //    freely. It also blocks unrelated writes from reordering.
      // 2. It does NOT prevent writes of the published object to local
      //    variables from moving before `publish`, because calls do not
      //    conflict with local accesses. For example, in:
      //      (local.set $p (publish (local.get $s)))
      //      (local.set $x (local.get $s))
      //    `SimplifyLocals` could sink `publish` past `local.set $x`, moving
      //    the write of `$s` to `$x` before `publish`.
      //
      // A potential design to model `publish` properly would track new data in
      // `EffectAnalyzer`:
      //
      // - `publishedLocals`: A set of local indices published by `publish`
      //   (e.g. from `curr->ref`). Any expression that writes to a local or
      //   global state while reading a published local would conflict with
      //   `publish`, preventing writes of the published object to unshared
      //   locations or locals from hoisting before `publish`. Pure reads would
      //   not be marked as writing and could reorder freely.
      // - `publishedHeapTypes` and `writtenValueHeapTypes`: To safely handle
      //   aliasing across locals and non-local expressions without external
      //   analysis, `EffectAnalyzer` could track the heap types of published
      //   references and compare them against the types of values being
      //   written in `LocalSet`, `GlobalSet`, `TableSet`, `StructSet`, and
      //   `ArraySet`.
      parent.calls = true;
    }
    void visitArrayNew(ArrayNew* curr) {}
    void visitArrayNewData(ArrayNewData* curr) {
      // Traps on out of bounds access to segments or access to dropped
      // segments.
      parent.implicitTrap = true;
    }
    void visitArrayNewElem(ArrayNewElem* curr) {
      // Traps on out of bounds access to segments or access to dropped
      // segments.
      parent.implicitTrap = true;
    }
    void visitArrayNewFixed(ArrayNewFixed* curr) {}
    void visitArrayGet(ArrayGet* curr) {
      if (trapOnNull(curr->ref)) {
        return;
      }
      // Null refs and OOB access.
      parent.implicitTrap = true;
      readsArray(curr->ref->type.getHeapType(), curr->order);
    }
    void visitArraySet(ArraySet* curr) {
      if (trapOnNull(curr->ref)) {
        return;
      }
      // Null refs and OOB access.
      parent.implicitTrap = true;
      writesArray(curr->ref->type.getHeapType(), curr->order);
    }
    void visitArrayLoad(ArrayLoad* curr) {
      if (trapOnNull(curr->ref)) {
        return;
      }
      // Null refs and OOB access.
      parent.implicitTrap = true;
      readsArray(curr->ref->type.getHeapType(), MemoryOrder::Unordered);
    }

    void visitArrayStore(ArrayStore* curr) {
      if (curr->ref->type.isNull()) {
        parent.trap = true;
        return;
      }
      parent.writesArray = true;
      // traps when the arg is null or the index out of bounds
      parent.implicitTrap = true;
    }
    void visitArrayLen(ArrayLen* curr) {
      trapOnNull(curr->ref);
      // No need to model this as reading the array since the length cannot be
      // written, so there can be no conflicts.
    }

    void visitArrayCopy(ArrayCopy* curr) {
      if (trapOnNull({curr->srcRef, curr->destRef})) {
        return;
      }
      // Null refs and OOB access.
      parent.implicitTrap = true;
      readsArray(curr->srcRef->type.getHeapType(), MemoryOrder::Unordered);
      writesArray(curr->destRef->type.getHeapType(), MemoryOrder::Unordered);
    }
    void visitArrayFill(ArrayFill* curr) {
      if (trapOnNull(curr->ref)) {
        return;
      }
      // Null refs and OOB access.
      parent.implicitTrap = true;
      writesArray(curr->ref->type.getHeapType(), MemoryOrder::Unordered);
    }
    template<typename ArrayInit> void visitArrayInit(ArrayInit* curr) {
      if (trapOnNull(curr->ref)) {
        return;
      }
      parent.writesArray = true;
      // OOB access to array or element segment.
      parent.implicitTrap = true;
      writesArray(curr->ref->type.getHeapType(), MemoryOrder::Unordered);
    }
    void visitArrayInitData(ArrayInitData* curr) { visitArrayInit(curr); }
    void visitArrayInitElem(ArrayInitElem* curr) { visitArrayInit(curr); }
    template<typename ArrayRMWExpr> void visitArrayRMWExpr(ArrayRMWExpr* curr) {
      if (trapOnNull(curr->ref)) {
        return;
      }
      // Null refs and OOB access.
      parent.implicitTrap = true;
      auto heapType = curr->ref->type.getHeapType();
      readsArray(heapType, curr->order);
      writesArray(heapType, curr->order);
    }
    void visitArrayRMW(ArrayRMW* curr) { visitArrayRMWExpr(curr); }
    void visitArrayCmpxchg(ArrayCmpxchg* curr) { visitArrayRMWExpr(curr); }
    void visitRefAs(RefAs* curr) {
      if (curr->op == AnyConvertExtern || curr->op == ExternConvertAny) {
        // These conversions are infallible.
        return;
      }
      assert(curr->op == RefAsNonNull);
      trapOnNull(curr->value);
    }
    void visitStringNew(StringNew* curr) {
      switch (curr->op) {
        case StringNewLossyUTF8Array:
        case StringNewWTF16Array:
          if (trapOnNull(curr->ref)) {
            return;
          }
          // OOB access to array.
          parent.implicitTrap = true;
          parent.readsMutableArray = true;
          return;
        case StringNewFromCodePoint:
          // Invalid code points.
          parent.implicitTrap = true;
          return;
      }
    }
    void visitStringConst(StringConst* curr) {}
    void visitStringMeasure(StringMeasure* curr) { trapOnNull(curr->ref); }
    void visitStringEncode(StringEncode* curr) {
      if (trapOnNull({curr->str, curr->array})) {
        return;
      }
      // OOB array access.
      parent.implicitTrap = true;
      parent.writesArray = true;
    }
    void visitStringConcat(StringConcat* curr) {
      trapOnNull({curr->left, curr->right});
    }
    void visitStringEq(StringEq* curr) {
      switch (curr->op) {
        case StringEqEqual:
          // Nulls are ok.
          return;
        case StringEqCompare:
          trapOnNull({curr->left, curr->right});
          return;
      }
    }
    void visitStringTest(StringTest* curr) {}
    void visitStringWTF16Get(StringWTF16Get* curr) {
      if (trapOnNull(curr->ref)) {
        return;
      }
      // OOB string access.
      parent.implicitTrap = true;
    }
    void visitStringSliceWTF(StringSliceWTF* curr) {
      if (trapOnNull(curr->ref)) {
        return;
      }
      // OOB string access.
      parent.implicitTrap = true;
    }
    void visitContNew(ContNew* curr) { trapOnNull(curr->func); }
    void visitContBind(ContBind* curr) {
      if (trapOnNull(curr->cont)) {
        return;
      }
      // The input continuation is modified, as it will trap if resumed. This is
      // a globally-noticeable effect, which we model as a call for now, but we
      // could in theory use something more refined here (|modifiesContinuation|
      // perhaps, to parallel |writesMemory| etc.).
      parent.calls = true;
    }
    void visitSuspend(Suspend* curr) {
      // Similar to resume/call: Suspending means that we execute arbitrary
      // other code before we may resume here.
      parent.calls = true;
      if (parent.features.hasExceptionHandling() && parent.tryDepth == 0) {
        parent.throws_ = true;
      }

      // A suspend may go unhandled and therefore trap.
      parent.implicitTrap = true;
    }
    void visitResume(Resume* curr) {
      if (trapOnNull(curr->cont)) {
        return;
      }
      // This acts as a kitchen sink effect.
      parent.calls = true;

      if (parent.features.hasExceptionHandling() && parent.tryDepth == 0) {
        parent.throws_ = true;
      }
    }
    void visitResumeThrow(ResumeThrow* curr) {
      if (trapOnNull(curr->cont)) {
        return;
      }

      // This acts as a kitchen sink effect.
      parent.calls = true;

      if (parent.features.hasExceptionHandling() && parent.tryDepth == 0) {
        parent.throws_ = true;
      }
    }
    void visitStackSwitch(StackSwitch* curr) {
      if (trapOnNull(curr->cont)) {
        return;
      }

      // This acts as a kitchen sink effect.
      parent.calls = true;

      if (parent.features.hasExceptionHandling() && parent.tryDepth == 0) {
        parent.throws_ = true;
      }
    }

  private:
    // Populate a call's effects using effects computed from GlobalEffects. Note
    // that calls may have other effects that aren't captured by the function
    // body of the target (e.g. a call_ref may trap on null refs).
    template<typename CallType>
    void addCallEffectsFromGlobalEffects(const CallType* curr,
                                         const EffectAnalyzer& funcEffects) {
      if (curr->isReturn) {
        if (funcEffects.throws()) {
          parent.hasReturnCallThrow = true;
        }
      }

      if (funcEffects.throws_ && (parent.tryDepth > 0 || curr->isReturn)) {
        // We can ignore a throw here, as the parent catches it.
        //
        // Also, we can filter out throws for return calls because they are
        // already more precisely captured by `branchesOut`, which models the
        // return, and `hasReturnCallThrow`, which models the throw that will
        // happen after the return.
        auto filteredEffects = funcEffects;
        filteredEffects.throws_ = false;
        parent.mergeIn(filteredEffects);
      } else {
        parent.mergeIn(funcEffects);
      }
    }

    // Common effects logic for the 3 types of call: `call`, `call_indirect`,
    // and `call_ref`.
    template<typename CallType>
    void addCallEffects(const CallType* curr,
                        const EffectAnalyzer* callTargetEffects) {
      if (curr->isReturn) {
        parent.branchesOut = true;
      }

      if (callTargetEffects) {
        addCallEffectsFromGlobalEffects(curr, *callTargetEffects);
        return;
      }

      parent.calls = true;
      // If EH is enabled and we don't have global effects information,
      // assume that the call target may throw.
      if (parent.features.hasExceptionHandling()) {
        if (curr->isReturn) {
          parent.hasReturnCallThrow = true;
        }
        if (parent.tryDepth == 0 && !curr->isReturn) {
          parent.throws_ = true;
        }
      }
    }
  };

public:
  // Helpers

  // See comment on orderedBefore() for the assumptions on the inputs here.
  // TODO: Update users so we can check just one direction here.
  static bool canReorder(const PassOptions& passOptions,
                         Module& module,
                         Expression* a,
                         Expression* b) {
    EffectAnalyzer aEffects(passOptions, module, a);
    EffectAnalyzer bEffects(passOptions, module, b);
    return !aEffects.orderedBefore(bEffects) &&
           !bEffects.orderedBefore(aEffects);
  }

  // C-API

  enum SideEffects : uint32_t {
    None = 0,
    Branches = 1 << 0,
    Calls = 1 << 1,
    ReadsLocal = 1 << 2,
    WritesLocal = 1 << 3,
    ReadsGlobal = 1 << 4,
    WritesGlobal = 1 << 5,
    ReadsMemory = 1 << 6,
    WritesMemory = 1 << 7,
    ReadsTable = 1 << 8,
    WritesTable = 1 << 9,
    ImplicitTrap = 1 << 10,
    IsAtomic = 1 << 11,
    Throws = 1 << 12,
    DanglingPop = 1 << 13,
    TrapsNeverHappen = 1 << 14,
    Any = (1 << 15) - 1
  };
  uint32_t getSideEffects() const {
    uint32_t effects = 0;
    if (branchesOut || hasExternalBreakTargets()) {
      effects |= SideEffects::Branches;
    }
    if (calls) {
      effects |= SideEffects::Calls;
    }
    if (localsRead.size() > 0) {
      effects |= SideEffects::ReadsLocal;
    }
    if (localsWritten.size() > 0) {
      effects |= SideEffects::WritesLocal;
    }
    if (mutableGlobalsRead.size()) {
      effects |= SideEffects::ReadsGlobal;
    }
    if (globalsWritten.size() > 0) {
      effects |= SideEffects::WritesGlobal;
    }
    // TODO: Expand the C API to handle shared locations, structs, and arrays.
    if (readsMemory || readsSharedMemory) {
      effects |= SideEffects::ReadsMemory;
    }
    if (writesMemory || writesSharedMemory) {
      effects |= SideEffects::WritesMemory;
    }
    if (readsTable) {
      effects |= SideEffects::ReadsTable;
    }
    if (writesTable) {
      effects |= SideEffects::WritesTable;
    }
    if (implicitTrap) {
      effects |= SideEffects::ImplicitTrap;
    }
    if (trapsNeverHappen) {
      effects |= SideEffects::TrapsNeverHappen;
    }
    // TODO: Expand the C API to handle memory orders.
    if (readOrder != MemoryOrder::Unordered ||
        writeOrder != MemoryOrder::Unordered) {
      effects |= SideEffects::IsAtomic;
    }
    if (throws_) {
      effects |= SideEffects::Throws;
    }
    if (danglingPop) {
      effects |= SideEffects::DanglingPop;
    }
    return effects;
  }

  // Ignores all forms of control flow transfers: breaks, returns, and
  // exceptions. (Note that traps are not considered relevant here - a trap does
  // not just transfer control flow, but can be seen as halting the entire
  // program.)
  //
  // This function matches transfersControlFlow(), that is, after calling this
  // method transfersControlFlow() will always return false.
  void ignoreControlFlowTransfers() {
    branchesOut = false;
    breakTargets.clear();
    throws_ = false;
    delegateTargets.clear();
    assert(!transfersControlFlow());
  }

private:
  void post() {
    assert(tryDepth == 0);

    if (ignoreImplicitTraps) {
      implicitTrap = false;
    } else if (implicitTrap) {
      trap = true;
    }
  }
};

// Calculate effects only on the node itself (shallowly), and not on
// children.
class ShallowEffectAnalyzer : public EffectAnalyzer {
public:
  ShallowEffectAnalyzer(const PassOptions& passOptions,
                        Module& module,
                        Expression* ast = nullptr)
    : EffectAnalyzer(passOptions, module) {
    if (ast) {
      visit(ast);
    }
  }
};

std::ostream& operator<<(std::ostream& o, const EffectAnalyzer& effects);

} // namespace wasm

#endif // wasm_ir_effects_h