src/passes/OptimizeAddedConstants.cpp

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

//
// Optimize added constants into load/store offsets. This requires the
// assumption that low memory is unused, so that we can replace an add (which
// might wrap) with a load/store offset (which does not).
//
// The propagate option also propagates offsets across set/get local pairs.
//
// Optimizing constants into load/store offsets is almost always
// beneficial for speed, as VMs can optimize these operations better.
// If a LocalGraph is provided, this can also propagate values along get/set
// pairs. In such a case, we may increase code size slightly or reduce
// compressibility (e.g., replace (load (get $x)) with (load offset=Z (get $y)),
// where Z is big enough to not fit in a single byte), but this is good for
// speed, and may lead to code size reductions elsewhere by using fewer locals.
//

#include <ir/local-graph.h>
#include <ir/local-utils.h>
#include <pass.h>
#include <wasm-builder.h>
#include <wasm.h>

namespace wasm {

namespace {

// Similar to Parents from parents.h, but we only care about gets, so it is much
// more efficient to just collect their parents.
struct GetParents {
  GetParents(Expression* expr) { inner.walk(expr); }

  Expression* getParent(LocalGet* curr) const {
    auto iter = inner.parentMap.find(curr);
    assert(iter != inner.parentMap.end());
    return iter->second;
  }

private:
  struct Inner : public ExpressionStackWalker<Inner> {
    void visitLocalGet(LocalGet* curr) { parentMap[curr] = getParent(); }

    std::unordered_map<Expression*, Expression*> parentMap;
  } inner;
};

} // anonymous namespace

template<typename P, typename T> class MemoryAccessOptimizer {
public:
  MemoryAccessOptimizer(P* parent,
                        T* curr,
                        Module* module,
                        LazyLocalGraph* localGraph)
    : parent(parent), curr(curr), module(module), localGraph(localGraph) {
    memory64 = module->getMemory(curr->memory)->is64();
  }

  // Tries to optimize, and returns whether we propagated a change.
  bool optimize() {
    // The pointer itself may be a constant, if e.g. it was precomputed or
    // a get that we propagated.
    if (curr->ptr->template is<Const>()) {
      optimizeConstantPointer();
      return false;
    }
    if (auto* add = curr->ptr->template dynCast<Binary>()) {
      if (add->op == AddInt32 || add->op == AddInt64) {
        // Look for a constant on both sides.
        if (tryToOptimizeConstant(add->right, add->left) ||
            tryToOptimizeConstant(add->left, add->right)) {
          return false;
        }
      }
    }
    if (localGraph) {
      // A final important case is a propagated add:
      //
      //  x = y + 10
      //  ..
      //  load(x)
      // =>
      //  x = y + 10
      //  ..
      //  load(y, offset=10)
      //
      // This is only valid if y does not change in the middle!
      if (auto* get = curr->ptr->template dynCast<LocalGet>()) {
        auto& sets = localGraph->getSets(get);
        if (sets.size() == 1) {
          auto* set = *sets.begin();
          // May be a zero-init (in which case, we can ignore it). Must also be
          // valid to propagate, as checked earlier in the parent.
          if (set && parent->isPropagatable(set)) {
            auto* value = set->value;
            if (auto* add = value->template dynCast<Binary>()) {
              if (add->op == AddInt32) {
                // We can optimize on either side, but only if both we find
                // a constant *and* the other side cannot change in the middle.
                // TODO If it could change, we may add a new local to capture
                //      the old value.
                if (tryToOptimizePropagatedAdd(
                      add->right, add->left, get, set) ||
                    tryToOptimizePropagatedAdd(
                      add->left, add->right, get, set)) {
                  return true;
                }
              }
            }
          }
        }
      }
    }
    return false;
  }

private:
  P* parent;
  T* curr;
  Module* module;
  LazyLocalGraph* localGraph;
  bool memory64;

  void optimizeConstantPointer() {
    // The constant and an offset are interchangeable:
    //   (load (const X))  <=>  (load offset=X (const 0))
    // It may not matter if we do this or not - it's the same size,
    // and in both cases the compiler can see it's a constant location.
    // For code clarity and compressibility, we prefer to put the
    // entire address in the constant.
    if (curr->offset) {
      // Note that the offset may already be larger than low memory - the
      // code may know that is valid, even if we can't. Only handle the
      // obviously valid case where an overflow can't occur.
      auto* c = curr->ptr->template cast<Const>();
      if (memory64) {
        uint64_t base = c->value.geti64();
        uint64_t offset = curr->offset;

        uint64_t max = std::numeric_limits<uint64_t>::max();
        bool overflow = (base > max - offset);
        if (!overflow) {
          c->value = c->value.add(Literal(offset));
          curr->offset = 0;
        }
      } else {
        uint32_t base = c->value.geti32();
        uint32_t offset = curr->offset;
        if (uint64_t(base) + uint64_t(offset) < (uint64_t(1) << 32)) {
          c->value = c->value.add(Literal(uint32_t(curr->offset)));
          curr->offset = 0;
        }
      }
    }
  }

  struct Result {
    bool succeeded;
    Address total;
    Result() : succeeded(false) {}
    Result(Address total) : succeeded(true), total(total) {}
  };

  // See if we can optimize an offset from an expression. If we report
  // success, the returned offset can be added as a replacement for the
  // expression here.
  bool tryToOptimizeConstant(Expression* oneSide, Expression* otherSide) {
    if (auto* c = oneSide->dynCast<Const>()) {
      auto result = canOptimizeConstant(c->value);
      if (result.succeeded) {
        curr->offset = result.total;
        curr->ptr = otherSide;
        if (curr->ptr->template is<Const>()) {
          optimizeConstantPointer();
        }
        return true;
      }
    }
    return false;
  }

  bool tryToOptimizePropagatedAdd(Expression* oneSide,
                                  Expression* otherSide,
                                  LocalGet* ptr,
                                  LocalSet* set) {
    if (auto* c = oneSide->dynCast<Const>()) {
      if (otherSide->is<Const>()) {
        // Both sides are constant - this is not optimized code, ignore.
        return false;
      }
      auto result = canOptimizeConstant(c->value);
      if (result.succeeded) {
        // Looks good, but we need to make sure the other side cannot change:
        //
        //  x = y + 10
        //  y = y + 1
        //  load(x)
        //
        // This example should *not* be optimized into
        //
        //  load(y, offset=10)
        //
        // If the other side is a get, we may be able to prove that we can just
        // use that same local, if both it and the pointer are in SSA form. In
        // that case,
        //
        //  y = .. // single assignment that dominates all uses
        //  x = y + 10 // single assignment that dominates all uses
        //  [..]
        //  load(x) => load(y, offset=10)
        //
        // This is valid since dominance is transitive, so y's definition
        // dominates the load, and it is ok to replace x with y + 10 there.
        Index index = -1;
        bool canReuseIndex = false;
        if (auto* get = otherSide->dynCast<LocalGet>()) {
          if (localGraph->isSSA(get->index) && localGraph->isSSA(ptr->index)) {
            index = get->index;
            canReuseIndex = true;
          }
        }
        // If we can't reuse the index, then create a new one,
        //
        //  x = y + 10
        //  y = y + 1
        //  load(x)
        // =>
        //  y' = y
        //  x = y' + 10
        //  y = y + 1
        //  load(y', offset=10)
        //
        // Often x has no other uses and later passes can remove it.
        if (!canReuseIndex) {
          index = parent->getHelperIndex(set);
        }
        curr->offset = result.total;
        curr->ptr = Builder(*module).makeLocalGet(index, Type::i32);
        return true;
      }
    }
    return false;
  }

  // Sees if we can optimize a particular constant.
  Result canOptimizeConstant(Literal literal) {
    uint64_t value = literal.getInteger();
    // Avoid uninteresting corner cases with peculiar offsets.
    if (value < PassOptions::LowMemoryBound) {
      // The total offset must not allow reaching reasonable memory
      // by overflowing.
      auto total = curr->offset + value;
      if (total < PassOptions::LowMemoryBound) {
        return Result(total);
      }
    }
    return Result();
  }
};

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

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

  bool propagate;

  OptimizeAddedConstants(bool propagate) : propagate(propagate) {}

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

  void visitLoad(Load* curr) {
    MemoryAccessOptimizer<OptimizeAddedConstants, Load> optimizer(
      this, curr, getModule(), localGraph.get());
    if (optimizer.optimize()) {
      propagated = true;
    }
  }

  void visitStore(Store* curr) {
    MemoryAccessOptimizer<OptimizeAddedConstants, Store> optimizer(
      this, curr, getModule(), localGraph.get());
    if (optimizer.optimize()) {
      propagated = true;
    }
  }

  void doWalkFunction(Function* func) {
    if (!getPassOptions().lowMemoryUnused) {
      Fatal() << "OptimizeAddedConstants can only be run when the "
              << "--low-memory-unused flag is set.";
    }

    if (getModule()->memories.empty()) {
      // There can be no loads and stores without a memory.
      return;
    }

    // Multiple passes may be needed if we have x + 4 + 8 etc. (nested structs
    // in C can cause this, but it's rare). Note that we only need that for the
    // propagation case (as 4 + 8 would be optimized directly if it were
    // adjacent).
    while (1) {
      propagated = false;
      helperIndexes.clear();
      propagatable.clear();
      if (propagate) {
        localGraph = std::make_unique<LazyLocalGraph>(func, getModule());
        findPropagatable();
      }
      Super::doWalkFunction(func);
      if (!helperIndexes.empty()) {
        createHelperIndexes();
      }
      if (propagated) {
        cleanUpAfterPropagation();
      } else {
        return;
      }
    }
  }

  // For a given expression, store it to a local and return us the local index
  // we can use, in order to get that value someplace else. We are provided not
  // the expression, but the set in which it is in, as the arm of an add that is
  // the set's value (the other arm is a constant, and we are not a constant).
  // We cache these, that is, use a single one for all requests.
  Index getHelperIndex(LocalSet* set) {
    auto iter = helperIndexes.find(set);
    if (iter != helperIndexes.end()) {
      return iter->second;
    }
    return helperIndexes[set] =
             Builder(*getModule()).addVar(getFunction(), Type::i32);
  }

  bool isPropagatable(LocalSet* set) { return propagatable.contains(set); }

private:
  bool propagated;

  std::unique_ptr<LazyLocalGraph> localGraph;

  // Whether a set is propagatable.
  std::set<LocalSet*> propagatable;

  void findPropagatable() {
    // Conservatively, only propagate if all uses can be removed of the
    // original. That is,
    //  x = a + 10
    //  f(x)
    //  g(x)
    // should be optimized to
    //  f(a, offset=10)
    //  g(a, offset=10)
    // but if x has other uses, then avoid doing so - we'll be doing that add
    // anyhow, so the load/store offset trick won't actually help.
    GetParents parents(getFunction()->body);
    for (auto& [location, _] : localGraph->getLocations()) {
      if (auto* set = location->dynCast<LocalSet>()) {
        if (auto* add = set->value->dynCast<Binary>()) {
          if (add->op == AddInt32) {
            if (add->left->is<Const>() || add->right->is<Const>()) {
              // Looks like this might be relevant, check all uses.
              bool canPropagate = true;
              for (auto* get : localGraph->getSetInfluences(set)) {
                auto* parent = parents.getParent(get);
                // if this is at the top level, it's the whole body - no set can
                // exist!
                assert(parent);
                if (!(parent->is<Load>() || parent->is<Store>())) {
                  canPropagate = false;
                  break;
                }
              }
              if (canPropagate) {
                propagatable.insert(set);
              }
            }
          }
        }
      }
    }
  }

  void cleanUpAfterPropagation() {
    // Remove sets that no longer have uses. This allows further propagation by
    // letting us see the accurate amount of uses of each set.
    UnneededSetRemover remover(getFunction(), getPassOptions(), *getModule());
  }

  std::map<LocalSet*, Index> helperIndexes;

  void createHelperIndexes() {
    struct Creator : public PostWalker<Creator> {
      std::map<LocalSet*, Index>& helperIndexes;
      Module* module;

      Creator(std::map<LocalSet*, Index>& helperIndexes)
        : helperIndexes(helperIndexes) {}

      void visitLocalSet(LocalSet* curr) {
        auto iter = helperIndexes.find(curr);
        if (iter != helperIndexes.end()) {
          auto index = iter->second;
          auto* binary = curr->value->cast<Binary>();
          Expression** target;
          if (binary->left->is<Const>()) {
            target = &binary->right;
          } else {
            assert(binary->right->is<Const>());
            target = &binary->left;
          }
          auto* value = *target;
          Builder builder(*module);
          *target = builder.makeLocalGet(index, Type::i32);
          replaceCurrent(
            builder.makeSequence(builder.makeLocalSet(index, value), curr));
        }
      }
    } creator(helperIndexes);
    creator.module = getModule();
    creator.walk(getFunction()->body);
  }
};

Pass* createOptimizeAddedConstantsPass() {
  return new OptimizeAddedConstants(false);
}

Pass* createOptimizeAddedConstantsPropagatePass() {
  return new OptimizeAddedConstants(true);
}

} // namespace wasm