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

//
// Memory Packing.
//
// Reduces binary size by splitting data segments around ranges of zeros. This
// pass assumes that memory initialized by active segments is zero on
// instantiation and therefore simply drops the zero ranges from the active
// segments. For passive segments, we perform the same splitting, but we also
// record how each segment was split and update all instructions that use it
// accordingly. To preserve trapping semantics for memory.init instructions, it
// is sometimes necessary to explicitly track whether input segments would have
// been dropped in globals. We are careful to emit only as many of these globals
// as necessary.
//

#include "ir/manipulation.h"
#include "ir/module-utils.h"
#include "ir/names.h"
#include "ir/utils.h"
#include "pass.h"
#include "support/space.h"
#include "support/stdckdint.h"
#include "wasm-binary.h"
#include "wasm-builder.h"
#include "wasm-limits.h"
#include "wasm.h"

namespace wasm {

namespace {

// A subsection of an original memory segment. If `isZero` is true, memory.fill
// will be used instead of memory.init for this range.
struct Range {
  bool isZero;
  // The range [start, end) - that is, start is included while end is not.
  size_t start;
  size_t end;
};

// A function that produces the transformed instruction. We need to use a
// function here instead of simple data because the replacement code sequence
// may require allocating new locals, which in turn requires the enclosing
// Function, which is only available in the parallelized instruction replacement
// phase. However, we can't move the entire calculation of replacement code
// sequences into the parallel phase because the lowering of data.drops depends
// on the lowering of memory.inits to determine whether a drop state global is
// necessary. The solution is that we calculate the shape of the replacement
// code sequence up front and use a closure just to allocate and insert new
// locals as necessary.
using Replacement = std::function<Expression*(Function*)>;

// Maps each instruction to the replacement that must be applied to it.
using Replacements = std::unordered_map<Expression*, Replacement>;

// A collection of instructions referring to a particular segment.
using Referrers = std::vector<Expression*>;

// Map segment indices to referrers.
using ReferrersMap = std::unordered_map<Name, Referrers>;

// memory.init: 2 byte opcode + 1 byte segment index + 1 byte memory index +
//              3 x 2 byte operands
const size_t MEMORY_INIT_SIZE = 10;

// memory.fill: 2 byte opcode + 1 byte memory index + 3 x 2 byte operands
const size_t MEMORY_FILL_SIZE = 9;

// data.drop: 2 byte opcode + ~1 byte index immediate
const size_t DATA_DROP_SIZE = 3;

Expression*
makeGtShiftedMemorySize(Builder& builder, Module& module, MemoryInit* curr) {
  auto mem = module.getMemory(curr->memory);
  return builder.makeBinary(
    mem->is64() ? GtUInt64 : GtUInt32,
    curr->dest,
    builder.makeBinary(mem->is64() ? ShlInt64 : ShlInt32,
                       builder.makeMemorySize(mem->name),
                       builder.makeConstPtr(16, mem->addressType)));
}

} // anonymous namespace

struct MemoryPacking : public Pass {
  // This pass operates on linear memory, and does not affect reference locals.
  // TODO: don't run at all if the module has no memories
  bool requiresNonNullableLocalFixups() override { return false; }

  void run(Module* module) override;
  bool canOptimize(std::vector<std::unique_ptr<Memory>>& memories,
                   std::vector<std::unique_ptr<DataSegment>>& dataSegments);
  void
  zeroOutTrampledData(std::vector<std::unique_ptr<DataSegment>>& dataSegments);
  void optimizeSegmentOps(Module* module);
  void getSegmentReferrers(Module* module, ReferrersMap& referrers);
  void dropUnusedSegments(Module* module,
                          std::vector<std::unique_ptr<DataSegment>>& segments,
                          ReferrersMap& referrers);
  bool canSplit(const std::unique_ptr<DataSegment>& segment,
                const Referrers& referrers);
  void calculateRanges(Module* module,
                       const std::unique_ptr<DataSegment>& segment,
                       const Referrers& referrers,
                       std::vector<Range>& ranges);
  void createSplitSegments(Builder& builder,
                           const DataSegment* segment,
                           std::vector<Range>& ranges,
                           std::vector<std::unique_ptr<DataSegment>>& packed,
                           size_t segmentsRemaining);
  void createReplacements(Module* module,
                          const std::vector<Range>& ranges,
                          const std::vector<Name>& segments,
                          const Referrers& referrers,
                          Replacements& replacements);
  void replaceSegmentOps(Module* module, Replacements& replacements);
};

void MemoryPacking::run(Module* module) {
  // Does not have multimemory support
  if (!canOptimize(module->memories, module->dataSegments)) {
    return;
  }

  bool canHaveSegmentReferrers =
    module->features.hasBulkMemory() || module->features.hasGC();

  auto& segments = module->dataSegments;

  // For each segment, a list of instructions that refer to it
  ReferrersMap referrers;

  if (canHaveSegmentReferrers) {
    // Optimize out memory.inits and data.drops that can be entirely replaced
    // with other instruction sequences. This can increase the number of unused
    // segments that can be dropped entirely and allows later replacement
    // creation to make more assumptions about what these instructions will look
    // like, such as memory.inits not having both zero offset and size.
    optimizeSegmentOps(module);
    getSegmentReferrers(module, referrers);
    dropUnusedSegments(module, segments, referrers);
  }

  // The new, split memory segments
  std::vector<std::unique_ptr<DataSegment>> packed;

  Replacements replacements;
  Builder builder(*module);
  for (size_t index = 0; index < segments.size(); ++index) {
    auto& segment = segments[index];
    auto& currReferrers = referrers[segment->name];

    std::vector<Range> ranges;

    if (canSplit(segment, currReferrers)) {
      calculateRanges(module, segment, currReferrers, ranges);
    } else {
      // A single range covers the entire segment. Set isZero to false so the
      // original memory.init will be used even if segment is all zeroes.
      ranges.push_back({false, 0, segment->data.size()});
    }

    size_t segmentsRemaining = segments.size() - index;
    size_t currSegmentsStart = packed.size();
    createSplitSegments(
      builder, segment.get(), ranges, packed, segmentsRemaining);
    std::vector<Name> currSegmentNames;
    for (size_t i = currSegmentsStart; i < packed.size(); ++i) {
      currSegmentNames.push_back(packed[i]->name);
    }
    createReplacements(
      module, ranges, currSegmentNames, currReferrers, replacements);
  }

  segments.swap(packed);
  module->updateDataSegmentsMap();

  if (canHaveSegmentReferrers) {
    replaceSegmentOps(module, replacements);
  }
}

// Whether the byte range [offset, offset + size) provably fits in the
// declared minimum size of the memory, so that writing the segment cannot
// trap.
static bool
provablyInBounds(const Memory& memory, uint64_t offset, uint64_t size) {
  uint64_t end;
  if (std::ckd_add(&end, offset, size)) {
    // The mathematical end is 2^64 + |end| (the wrapped value). That is in
    // bounds only when it is exactly 2^64, that is, |end| is 0, and the
    // memory's declared minimum size is the maximal 2^64 bytes. (With
    // one-byte pages the largest declarable minimum is 2^64 - 1 bytes, so a
    // segment ending at 2^64 is never in bounds there.)
    if (end != 0 || memory.pageSizeLog2 == 0) {
      return false;
    }
    return memory.initial == (uint64_t(1) << (64 - memory.pageSizeLog2));
  }
  // Compare page counts rather than byte counts: the byte size of a maximal
  // memory64 (2^48 pages) does not fit in 64 bits. Compute the number of
  // pages needed to hold |end| bytes, rounding up as a partial page needs a
  // whole page.
  uint64_t endPages = end >> memory.pageSizeLog2;
  if (end % memory.pageSize() != 0) {
    endPages++;
  }
  return endPages <= memory.initial;
}

bool MemoryPacking::canOptimize(
  std::vector<std::unique_ptr<Memory>>& memories,
  std::vector<std::unique_ptr<DataSegment>>& dataSegments) {
  if (memories.empty() || memories.size() > 1) {
    return false;
  }
  auto& memory = memories[0];
  // We must optimize under the assumption that memory has been initialized to
  // zero. That is the case for a memory declared in the module, but for a
  // memory that is imported, we must be told that it is zero-initialized.
  if (memory->imported() && !getPassOptions().zeroFilledMemory) {
    return false;
  }

  // One segment is always ok to optimize, as it does not have the potential
  // problems handled below.
  if (dataSegments.size() <= 1) {
    return true;
  }
  // Check if it is ok for us to optimize.
  for (auto& segment : dataSegments) {
    if (segment->isActive()) {
      auto* c = segment->offset->dynCast<Const>();
      // If an active segment has a non-constant offset, then what gets written
      // cannot be known until runtime. That is, the active segments are written
      // out at startup, in order, and one may trample the data of another, like
      //
      //  (data (i32.const 100) "a")
      //  (data (i32.const 100) "\00")
      //
      // It is *not* ok to optimize out the zero in the last segment, as it is
      // actually needed, it will zero out the "a" that was written earlier. And
      // if a segment has an imported offset,
      //
      //  (data (i32.const 100) "a")
      //  (data (global.get $x) "\00")
      //
      // then we can't tell if that last segment will end up overwriting or not.
      // The only case we can easily handle is if there is just a single
      // segment, which we handled earlier. (Note that that includes the main
      // case of having a non-constant offset, dynamic linking, in which we have
      // a single segment.)
      if (!c) {
        return false;
      }
    }
  }
  // All active segments have constant offsets, known at this time, so we may be
  // able to optimize, but must still check for the trampling problem mentioned
  // earlier.
  DisjointSpans space;
  for (auto& segment : dataSegments) {
    if (segment->isActive()) {
      auto* c = segment->offset->cast<Const>();
      Address start = c->value.getUnsigned();
      DisjointSpans::Span span{start, start + segment->data.size()};
      if (space.addAndCheckOverlap(span)) {
        // Some segments overlap, that is, a later segment tramples the data of
        // an earlier one. If the memory is imported then a trap on a later
        // out-of-bounds segment leaves the data written so far visible in the
        // imported memory (which outlives the failed instantiation), so even
        // trampled data matters. We can only optimize if we prove no active
        // segment can trap, which is the case when each is in bounds of the
        // memory's declared minimum size: then instantiation always applies
        // every segment, and only the final memory contents are observable,
        // exactly as for a memory defined in the module.
        // TODO: This could be finer-grained: it is enough for the segments
        //       after a trampled segment, up to and including its trampling
        //       segment, to be provably in-bounds, as then no trap can occur
        //       between the trampled write and the trampling one.
        if (memory->imported()) {
          for (auto& seg : dataSegments) {
            if (seg->isActive() &&
                !provablyInBounds(
                  *memory,
                  seg->offset->cast<Const>()->value.getUnsigned(),
                  seg->data.size())) {
              std::cerr
                << "warning: active memory segments overlap, and some may "
                << "be out of bounds of the imported memory's declared "
                << "minimum size, which prevents some optimizations.\n";
              return false;
            }
          }
        }
        // Zero out the trampled data, which the normal optimization of zeros
        // will then remove. For a memory defined in the module
        // partially-applied segments can never be observed (either
        // instantiation completes and all the segments are applied in order,
        // or it traps and the memory is never exposed), and for an imported
        // memory we just proved that no trap is possible.
        zeroOutTrampledData(dataSegments);
        break;
      }
    }
  }
  return true;
}

void MemoryPacking::zeroOutTrampledData(
  std::vector<std::unique_ptr<DataSegment>>& dataSegments) {
  // Active segments are applied in order at instantiation, before any code can
  // run, so when segments overlap only the last write to each byte is ever
  // observable. Zero out all bytes that a later segment overwrites. This
  // assumes all active segments have constant offsets, which canOptimize
  // verifies before calling us.
  //
  // Iterate in reverse, tracking the disjoint regions of memory covered by the
  // segments seen so far as a map from a region's start address to its end.
  std::map<uint64_t, uint64_t> covered;
  for (auto it = dataSegments.rbegin(); it != dataSegments.rend(); ++it) {
    auto& segment = *it;
    if (!segment->isActive() || segment->data.empty()) {
      continue;
    }
    uint64_t start = segment->offset->cast<Const>()->value.getUnsigned();
    uint64_t end = start + segment->data.size();
    // Zero out our bytes that later segments cover. Look for overlapping
    // regions starting from the last one beginning at or before us.
    auto covering = covered.upper_bound(start);
    if (covering != covered.begin()) {
      --covering;
    }
    for (; covering != covered.end() && covering->first < end; ++covering) {
      uint64_t overlapStart = std::max(start, covering->first);
      uint64_t overlapEnd = std::min(end, covering->second);
      if (overlapStart < overlapEnd) {
        std::fill(segment->data.begin() + (overlapStart - start),
                  segment->data.begin() + (overlapEnd - start),
                  0);
      }
    }
    // Add our span to the covered regions, merging with any regions it
    // touches.
    auto next = covered.upper_bound(start);
    if (next != covered.begin()) {
      auto prev = std::prev(next);
      if (prev->second >= start) {
        start = prev->first;
        end = std::max(end, prev->second);
        next = prev;
      }
    }
    while (next != covered.end() && next->first <= end) {
      end = std::max(end, next->second);
      next = covered.erase(next);
    }
    covered[start] = end;
  }
}

bool MemoryPacking::canSplit(const std::unique_ptr<DataSegment>& segment,
                             const Referrers& referrers) {
  // Don't mess with segments related to llvm coverage tools such as
  // __llvm_covfun. There segments are expected/parsed by external downstream
  // tools (llvm-cov) so they need to be left intact.
  // See https://clang.llvm.org/docs/SourceBasedCodeCoverage.html
  if (segment->name.is() && segment->name.startsWith("__llvm")) {
    return false;
  }

  if (segment->data.empty()) {
    // Ignore empty segments, leaving them in place. We may not need them, but
    // leave that for RemoveUnusedModuleElements to decide (as they may trap
    // during startup if out of bounds, which is an effect).
    return false;
  }

  for (auto* referrer : referrers) {
    if (auto* curr = referrer->dynCast<MemoryInit>()) {
      if (segment->isPassive()) {
        // Do not try to split if there is a nonconstant offset or size
        if (!curr->offset->is<Const>() || !curr->size->is<Const>()) {
          return false;
        }
      }
    } else if (referrer->is<ArrayNewData>() || referrer->is<ArrayInitData>()) {
      // TODO: Split segments referenced by GC instructions.
      return false;
    }
  }

  // Active segments can only be split if they have constant offsets
  return segment->isPassive() || segment->offset->is<Const>();
}

void MemoryPacking::calculateRanges(Module* module,
                                    const std::unique_ptr<DataSegment>& segment,
                                    const Referrers& referrers,
                                    std::vector<Range>& ranges) {
  auto& data = segment->data;
  if (data.size() == 0) {
    return;
  }

  // A segment that might trap during startup must be handled carefully, as we
  // do not want to remove that trap (unless we are allowed to by TNH).
  auto preserveTrap = !getPassOptions().trapsNeverHappen && segment->offset;
  if (preserveTrap) {
    // Check if we can rule out a trap by it being in bounds.
    if (auto* c = segment->offset->dynCast<Const>()) {
      auto* memory = module->getMemory(segment->memory);
      if (provablyInBounds(
            *memory, c->value.getUnsigned(), segment->data.size())) {
        preserveTrap = false;
      }
    }
  }

  // Calculate initial zero and nonzero ranges
  size_t start = 0;
  while (start < data.size()) {
    size_t end = start;
    while (end < data.size() && data[end] == 0) {
      end++;
    }
    if (end > start) {
      ranges.push_back({true, start, end});
      start = end;
    }
    while (end < data.size() && data[end] != 0) {
      end++;
    }
    if (end > start) {
      ranges.push_back({false, start, end});
      start = end;
    }
  }

  // Calculate the number of consecutive zeroes for which splitting is
  // beneficial. This is an approximation that assumes all memory.inits cover an
  // entire segment and that all its arguments are constants. These assumptions
  // are true of all memory.inits generated by the tools.
  size_t threshold = 0;
  if (segment->isPassive()) {
    // Passive segment metadata size
    threshold += 2;
    // Zeroes on the edge do not increase the number of segments or data.drops,
    // so their threshold is lower. The threshold for interior zeroes depends on
    // an estimate of the number of new memory.fill and data.drop instructions
    // splitting would introduce.
    size_t edgeThreshold = 0;
    for (auto* referrer : referrers) {
      if (referrer->is<MemoryInit>()) {
        // Splitting adds a new memory.fill and a new memory.init
        threshold += MEMORY_FILL_SIZE + MEMORY_INIT_SIZE;
        edgeThreshold += MEMORY_FILL_SIZE;
      } else {
        threshold += DATA_DROP_SIZE;
      }
    }

    // Merge edge zeroes if they are not worth splitting. Note that we must not
    // have a trap we must preserve here (if we did, we'd need to handle that in
    // the code below).
    assert(!preserveTrap);
    if (ranges.size() >= 2) {
      auto last = ranges.end() - 1;
      auto penultimate = ranges.end() - 2;
      if (last->isZero && last->end - last->start <= edgeThreshold) {
        penultimate->end = last->end;
        ranges.erase(last);
      }
    }
    if (ranges.size() >= 2) {
      auto first = ranges.begin();
      auto second = ranges.begin() + 1;
      if (first->isZero && first->end - first->start <= edgeThreshold) {
        second->start = first->start;
        ranges.erase(first);
      }
    }
  } else {
    // Legacy ballpark overhead of active segment with offset.
    // TODO: Tune this
    threshold = 8;
  }

  // Merge ranges across small spans of zeroes.
  std::vector<Range> mergedRanges = {ranges.front()};
  size_t i;
  for (i = 1; i < ranges.size() - 1; ++i) {
    auto left = mergedRanges.end() - 1;
    auto curr = ranges.begin() + i;
    auto right = ranges.begin() + i + 1;
    if (curr->isZero && curr->end - curr->start <= threshold) {
      left->end = right->end;
      ++i;
    } else {
      mergedRanges.push_back(*curr);
    }
  }
  // Add the final range if it hasn't already been merged in.
  if (i < ranges.size()) {
    mergedRanges.push_back(ranges.back());
  }
  // If we need to preserve a trap then we must keep the topmost byte of the
  // segment, which is enough to cause a trap if we do in fact trap.
  if (preserveTrap) {
    // Check if the last byte is in a zero range. Such a range will be dropped
    // later, so add a non-zero range with that byte. (It is slightly odd to
    // add a range with a zero marked as non-zero, but that is how we ensure it
    // is preserved later in the output.)
    auto& back = mergedRanges.back();
    if (back.isZero) {
      // Remove the last byte from |back|. Decrementing this prevents it from
      // overlapping with the new segment we are about to add. Note that this
      // might make |back| have size 0, but that is not a problem as it will be
      // dropped later anyhow, since it contains zeroes.
      back.end--;
      auto lastByte = data.size() - 1;
      mergedRanges.push_back({false, lastByte, lastByte + 1});
    }
  }
  std::swap(ranges, mergedRanges);
}

void MemoryPacking::optimizeSegmentOps(Module* module) {
  struct Optimizer : WalkerPass<PostWalker<Optimizer>> {
    bool isFunctionParallel() override { return true; }

    // This operates on linear memory, and does not affect reference locals.
    bool requiresNonNullableLocalFixups() override { return false; }

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

    bool needsRefinalizing;

    void visitMemoryInit(MemoryInit* curr) {
      Builder builder(*getModule());
      auto* segment = getModule()->getDataSegment(curr->segment);
      size_t maxRuntimeSize = segment->isPassive() ? segment->data.size() : 0;
      bool mustNop = false;
      bool mustTrap = false;
      auto* offset = curr->offset->dynCast<Const>();
      auto* size = curr->size->dynCast<Const>();
      if (offset && offset->value.getUnsigned() > maxRuntimeSize) {
        mustTrap = true;
      }
      if (size && size->value.getUnsigned() > maxRuntimeSize) {
        mustTrap = true;
      }
      if (offset && size) {
        auto offsetVal = offset->value.getUnsigned();
        auto sizeVal = size->value.getUnsigned();
        if (offsetVal + sizeVal > maxRuntimeSize) {
          mustTrap = true;
        } else if (offsetVal == 0 && sizeVal == 0) {
          mustNop = true;
        }
      }
      assert(!mustNop || !mustTrap);
      if (mustNop) {
        // Offset and size are 0, so just trap if dest > memory.size
        replaceCurrent(
          builder.makeIf(makeGtShiftedMemorySize(builder, *getModule(), curr),
                         builder.makeUnreachable()));
      } else if (mustTrap) {
        // Drop dest, offset, and size then trap
        replaceCurrent(builder.blockify(builder.makeDrop(curr->dest),
                                        builder.makeDrop(curr->offset),
                                        builder.makeDrop(curr->size),
                                        builder.makeUnreachable()));
        needsRefinalizing = true;
      } else if (segment->isActive()) {
        // trap if (dest > memory.size | offset | size) != 0
        replaceCurrent(builder.makeIf(
          builder.makeBinary(
            OrInt32,
            makeGtShiftedMemorySize(builder, *getModule(), curr),
            builder.makeBinary(OrInt32, curr->offset, curr->size)),
          builder.makeUnreachable()));
      }
    }
    void visitDataDrop(DataDrop* curr) {
      if (getModule()->getDataSegment(curr->segment)->isActive()) {
        ExpressionManipulator::nop(curr);
      }
    }
    void doWalkFunction(Function* func) {
      needsRefinalizing = false;
      Super::doWalkFunction(func);
      if (needsRefinalizing) {
        ReFinalize().walkFunctionInModule(func, getModule());
      }
    }
  } optimizer;
  optimizer.run(getPassRunner(), module);
}

void MemoryPacking::getSegmentReferrers(Module* module,
                                        ReferrersMap& referrers) {
  auto collectReferrers = [&](Function* func, ReferrersMap& referrers) {
    if (func->imported()) {
      return;
    }
    struct Collector
      : WalkerPass<PostWalker<Collector, UnifiedExpressionVisitor<Collector>>> {
      ReferrersMap& referrers;
      Collector(ReferrersMap& referrers) : referrers(referrers) {}

      void visitExpression(Expression* curr) {
#define DELEGATE_ID curr->_id

#define DELEGATE_START(id) [[maybe_unused]] auto* cast = curr->cast<id>();

#define DELEGATE_GET_FIELD(id, field) cast->field

#define DELEGATE_FIELD_TYPE(id, field)
#define DELEGATE_FIELD_HEAPTYPE(id, field)
#define DELEGATE_FIELD_CHILD(id, field)
#define DELEGATE_FIELD_OPTIONAL_CHILD(id, field)
#define DELEGATE_FIELD_INT(id, field)
#define DELEGATE_FIELD_LITERAL(id, field)
#define DELEGATE_FIELD_NAME(id, field)
#define DELEGATE_FIELD_SCOPE_NAME_DEF(id, field)
#define DELEGATE_FIELD_SCOPE_NAME_USE(id, field)
#define DELEGATE_FIELD_ADDRESS(id, field)

#define DELEGATE_FIELD_NAME_KIND(id, field, kind)                              \
  if (kind == ModuleItemKind::DataSegment) {                                   \
    referrers[cast->field].push_back(curr);                                    \
  }

#include "wasm-delegations-fields.def"
      }
    } collector(referrers);
    collector.walkFunctionInModule(func, module);
  };
  ModuleUtils::ParallelFunctionAnalysis<ReferrersMap> analysis(
    *module, collectReferrers);
  for (auto& [_, funcReferrersMap] : analysis.map) {
    for (auto& [i, segReferrers] : funcReferrersMap) {
      referrers[i].insert(
        referrers[i].end(), segReferrers.begin(), segReferrers.end());
    }
  }
}

void MemoryPacking::dropUnusedSegments(
  Module* module,
  std::vector<std::unique_ptr<DataSegment>>& segments,
  ReferrersMap& referrers) {
  std::vector<std::unique_ptr<DataSegment>> usedSegments;
  // Remove segments that are never used
  // TODO: remove unused portions of partially used segments as well
  for (size_t i = 0; i < segments.size(); ++i) {
    bool used = false;
    auto referrersIt = referrers.find(segments[i]->name);
    bool hasReferrers = referrersIt != referrers.end();
    if (segments[i]->isPassive()) {
      if (hasReferrers) {
        for (auto* referrer : referrersIt->second) {
          if (!referrer->is<DataDrop>()) {
            used = true;
            break;
          }
        }
      }
    } else {
      // Active segment.
      used = true;
    }
    if (used) {
      usedSegments.push_back(std::move(segments[i]));
    } else if (hasReferrers) {
      // All referrers are data.drops. Make them nops.
      for (auto* referrer : referrersIt->second) {
        ExpressionManipulator::nop(referrer);
      }
    }
  }
  std::swap(segments, usedSegments);
  module->updateDataSegmentsMap();
}

// Given the start of a segment and an offset into it, compute the sum of the
// two to get the absolute address the data should be at. This takes into
// account overflows in that we saturate to UINT_MAX: we do not want an overflow
// to take us down into a small address; in the invalid case of an overflow we
// stay at the largest possible unsigned value, which will keep us trapping.
template<typename T>
Expression* addStartAndOffset(T start, T offset, Builder& builder) {
  T total;
  if (std::ckd_add(&total, start, offset)) {
    total = std::numeric_limits<T>::max();
  }
  return builder.makeConst(T(total));
}

void MemoryPacking::createSplitSegments(
  Builder& builder,
  const DataSegment* segment,
  std::vector<Range>& ranges,
  std::vector<std::unique_ptr<DataSegment>>& packed,
  size_t segmentsRemaining) {
  size_t segmentCount = 0;
  bool hasExplicitName = false;
  for (size_t i = 0; i < ranges.size(); ++i) {
    Range& range = ranges[i];
    if (range.isZero) {
      continue;
    }
    Expression* offset = nullptr;
    if (segment->isActive()) {
      if (auto* c = segment->offset->dynCast<Const>()) {
        if (c->value.type == Type::i32) {
          offset = addStartAndOffset<uint32_t>(
            range.start, c->value.geti32(), builder);
        } else {
          assert(c->value.type == Type::i64);
          offset = addStartAndOffset<uint64_t>(
            range.start, c->value.geti64(), builder);
        }
      } else {
        assert(ranges.size() == 1);
        offset = segment->offset;
      }
    }
    if (WebLimitations::MaxDataSegments <= packed.size() + segmentsRemaining) {
      // Give up splitting and merge all remaining ranges except end zeroes
      auto lastNonzero = ranges.end() - 1;
      if (lastNonzero->isZero) {
        --lastNonzero;
      }
      range.end = lastNonzero->end;
      ranges.erase(ranges.begin() + i + 1, lastNonzero + 1);
    }
    Name name;
    if (segment->name.is()) {
      // Name the first range after the original segment and all following
      // ranges get numbered accordingly.  This means that for segments that
      // cannot be split (segments that contains a single range) the input and
      // output segment have the same name.
      if (!segmentCount) {
        name = segment->name;
        hasExplicitName = segment->hasExplicitName;
      } else {
        name = segment->name.toString() + "." + std::to_string(segmentCount);
      }
      segmentCount++;
    }
    auto curr = Builder::makeDataSegment(name,
                                         segment->memory,
                                         offset,
                                         segment->data.data() + range.start,
                                         range.end - range.start);
    curr->hasExplicitName = hasExplicitName;
    packed.push_back(std::move(curr));
  }
}

void MemoryPacking::createReplacements(Module* module,
                                       const std::vector<Range>& ranges,
                                       const std::vector<Name>& segments,
                                       const Referrers& referrers,
                                       Replacements& replacements) {
  // If there was no transformation, we do not need to do anything.
  if (ranges.size() == 1 && !ranges.front().isZero) {
    return;
  }

  Builder builder(*module);

  Name dropStateGlobal;

  // Return the drop state global, initializing it if it does not exist. This
  // may change module-global state and has the important side effect of setting
  // dropStateGlobal, so it must be evaluated eagerly, not in the replacements.
  auto getDropStateGlobal = [&]() {
    if (dropStateGlobal != Name()) {
      return dropStateGlobal;
    }
    dropStateGlobal =
      Names::getValidGlobalName(*module, "__mem_segment_drop_state");
    module->addGlobal(builder.makeGlobal(dropStateGlobal,
                                         Type::i32,
                                         builder.makeConst(int32_t(0)),
                                         Builder::Mutable));
    return dropStateGlobal;
  };

  // Create replacements for memory.init instructions first
  for (auto referrer : referrers) {
    auto* init = referrer->dynCast<MemoryInit>();
    if (init == nullptr) {
      continue;
    }

    // Nonconstant offsets or sizes will have inhibited splitting
    size_t start = init->offset->cast<Const>()->value.getUnsigned();
    size_t end = start + init->size->cast<Const>()->value.getUnsigned();

    // Index in `segments` of the segment used in emitted memory.init
    // instructions
    size_t initIndex = 0;

    // Index of the range from which this memory.init starts reading
    size_t firstRangeIdx = 0;
    while (firstRangeIdx < ranges.size() &&
           ranges[firstRangeIdx].end <= start) {
      if (!ranges[firstRangeIdx].isZero) {
        ++initIndex;
      }
      ++firstRangeIdx;
    }

    // Handle zero-length memory.inits separately so we can later assume that
    // start is in bounds and that some range will be intersected.
    if (start == end) {
      // Offset is nonzero because init would otherwise have previously been
      // optimized out, so trap if the dest is out of bounds or the segment is
      // dropped
      Expression* result = builder.makeIf(
        builder.makeBinary(
          OrInt32,
          makeGtShiftedMemorySize(builder, *module, init),
          builder.makeGlobalGet(getDropStateGlobal(), Type::i32)),
        builder.makeUnreachable());
      replacements[init] = [result](Function*) { return result; };
      continue;
    }

    assert(firstRangeIdx < ranges.size());

    // Split init into multiple memory.inits and memory.fills, storing the
    // original base destination in a local if it is not a constant. If the
    // first access is a memory.fill, explicitly check the drop status first to
    // avoid writing zeroes when we should have trapped.
    Expression* result = nullptr;
    auto appendResult = [&](Expression* expr) {
      result = result ? builder.blockify(result, expr) : expr;
    };

    // The local var holding the dest is not known until replacement time. Keep
    // track of the locations where it will need to be patched in.
    Index* setVar = nullptr;
    std::vector<Index*> getVars;
    if (!init->dest->is<Const>()) {
      auto set = builder.makeLocalSet(-1, init->dest);
      setVar = &set->index;
      appendResult(set);
    }

    // We only need to explicitly check the drop state when we will emit
    // memory.fill first, since memory.init will implicitly do the check for us.
    if (ranges[firstRangeIdx].isZero) {
      appendResult(
        builder.makeIf(builder.makeGlobalGet(getDropStateGlobal(), Type::i32),
                       builder.makeUnreachable()));
    }

    size_t bytesWritten = 0;

    auto is64 = module->getMemory(init->memory)->is64();
    for (size_t i = firstRangeIdx; i < ranges.size() && ranges[i].start < end;
         ++i) {
      auto& range = ranges[i];

      // Calculate dest, either as a const or as an addition to the dest local
      Expression* dest;
      Type ptrType = module->getMemory(init->memory)->addressType;
      if (auto* c = init->dest->dynCast<Const>()) {
        dest =
          builder.makeConstPtr(c->value.getInteger() + bytesWritten, ptrType);
      } else {
        auto* get = builder.makeLocalGet(-1, ptrType);
        getVars.push_back(&get->index);
        dest = get;
        if (bytesWritten > 0) {
          Const* addend = builder.makeConstPtr(bytesWritten, ptrType);
          dest = builder.makeBinary(is64 ? AddInt64 : AddInt32, dest, addend);
        }
      }

      // How many bytes are read from this range
      size_t bytes = std::min(range.end, end) - std::max(range.start, start);
      bytesWritten += bytes;

      // Create new memory.init or memory.fill
      if (range.isZero) {
        Expression* value = builder.makeConst(Literal::makeZero(Type::i32));
        Expression* size = builder.makeConstPtr(bytes, ptrType);
        appendResult(builder.makeMemoryFill(dest, value, size, init->memory));
      } else {
        size_t offsetBytes = std::max(start, range.start) - range.start;
        Expression* offset = builder.makeConst(int32_t(offsetBytes));
        Expression* size = builder.makeConst(int32_t(bytes));
        appendResult(builder.makeMemoryInit(
          segments[initIndex], dest, offset, size, init->memory));
        initIndex++;
      }
    }

    // Non-zero length memory.inits must have intersected some range
    assert(result);
    replacements[init] =
      [module, init, setVar, getVars, result](Function* function) {
        if (setVar != nullptr) {
          auto addressType = module->getMemory(init->memory)->addressType;
          Index destVar = Builder(*module).addVar(function, addressType);
          *setVar = destVar;
          for (auto* getVar : getVars) {
            *getVar = destVar;
          }
        }
        return result;
      };
  }

  // Create replacements for data.drop instructions now that we know whether we
  // need a drop state global
  for (auto drop : referrers) {
    if (!drop->is<DataDrop>()) {
      continue;
    }

    Expression* result = nullptr;
    auto appendResult = [&](Expression* expr) {
      result = result ? builder.blockify(result, expr) : expr;
    };

    // Track drop state in a global only if some memory.init required it
    if (dropStateGlobal != Name()) {
      appendResult(
        builder.makeGlobalSet(dropStateGlobal, builder.makeConst(int32_t(1))));
    }
    size_t dropIndex = 0;
    for (auto range : ranges) {
      if (!range.isZero) {
        appendResult(builder.makeDataDrop(segments[dropIndex++]));
      }
    }
    replacements[drop] = [result, module](Function*) {
      return result ? result : Builder(*module).makeNop();
    };
  }
}

void MemoryPacking::replaceSegmentOps(Module* module,
                                      Replacements& replacements) {
  struct Replacer : WalkerPass<PostWalker<Replacer>> {
    bool isFunctionParallel() override { return true; }

    // This operates on linear memory, and does not affect reference locals.
    bool requiresNonNullableLocalFixups() override { return false; }

    Replacements& replacements;

    Replacer(Replacements& replacements) : replacements(replacements) {};
    std::unique_ptr<Pass> create() override {
      return std::make_unique<Replacer>(replacements);
    }

    void visitMemoryInit(MemoryInit* curr) {
      if (auto replacement = replacements.find(curr);
          replacement != replacements.end()) {
        replaceCurrent(replacement->second(getFunction()));
      }
    }

    void visitDataDrop(DataDrop* curr) {
      if (auto replacement = replacements.find(curr);
          replacement != replacements.end()) {
        replaceCurrent(replacement->second(getFunction()));
      }
    }

    void visitArrayNewData(ArrayNewData* curr) {
      if (auto replacement = replacements.find(curr);
          replacement != replacements.end()) {
        replaceCurrent(replacement->second(getFunction()));
      }
    }
  } replacer(replacements);
  replacer.run(getPassRunner(), module);
}

Pass* createMemoryPackingPass() { return new MemoryPacking(); }

} // namespace wasm