src/ir/ExpressionAnalyzer.cpp

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

#include "ir/iteration.h"
#include "ir/load-utils.h"
#include "ir/utils.h"
#include "shared-constants.h"
#include "support/hash.h"
#include "support/small_vector.h"
#include "wasm-traversal.h"
#include "wasm.h"

namespace wasm {

// Given a stack of expressions, checks if the topmost is used as a result.
// For example, if the parent is a block and the node is before the last
// position, it is not used.
bool ExpressionAnalyzer::isResultUsed(ExpressionStack& stack, Function* func) {
  for (int i = int(stack.size()) - 2; i >= 0; i--) {
    auto* curr = stack[i];
    auto* above = stack[i + 1];
    // only if and block can drop values (pre-drop expression was added) FIXME
    if (curr->is<Block>()) {
      auto* block = curr->cast<Block>();
      for (size_t j = 0; j < block->list.size() - 1; j++) {
        if (block->list[j] == above) {
          return false;
        }
      }
      assert(block->list.back() == above);
      // continue down
    } else if (curr->is<If>()) {
      auto* iff = curr->cast<If>();
      if (above == iff->condition) {
        return true;
      }
      if (!iff->ifFalse) {
        return false;
      }
      assert(above == iff->ifTrue || above == iff->ifFalse);
      // continue down
    } else {
      if (curr->is<Drop>()) {
        return false;
      }
      return true; // all other node types use the result
    }
  }
  // The value might be used, so it depends on if the function returns
  return func->getResults() != Type::none;
}

// Checks if a value is dropped.
bool ExpressionAnalyzer::isResultDropped(ExpressionStack& stack) {
  for (int i = int(stack.size()) - 2; i >= 0; i--) {
    auto* curr = stack[i];
    auto* above = stack[i + 1];
    if (curr->is<Block>()) {
      auto* block = curr->cast<Block>();
      for (size_t j = 0; j < block->list.size() - 1; j++) {
        if (block->list[j] == above) {
          return false;
        }
      }
      assert(block->list.back() == above);
      // continue down
    } else if (curr->is<If>()) {
      auto* iff = curr->cast<If>();
      if (above == iff->condition) {
        return false;
      }
      if (!iff->ifFalse) {
        return false;
      }
      assert(above == iff->ifTrue || above == iff->ifFalse);
      // continue down
    } else {
      if (curr->is<Drop>()) {
        return true; // dropped
      }
      return false; // all other node types use the result
    }
  }
  return false;
}

bool ExpressionAnalyzer::flexibleEqual(Expression* left,
                                       Expression* right,
                                       ExprComparer comparer) {
  struct Comparer {
    // for each name on the left, the corresponding name on the right
    std::map<Name, Name> rightNames;
    std::vector<Expression*> leftStack;
    std::vector<Expression*> rightStack;

    bool noteNames(Name left, Name right) {
      if (left.is() != right.is()) {
        return false;
      }
      if (left.is()) {
        assert(rightNames.find(left) == rightNames.end());
        rightNames[left] = right;
      }
      return true;
    }

    bool compare(Expression* left, Expression* right, ExprComparer comparer) {
      // The empty name is the same on both sides.
      rightNames[Name()] = Name();

      leftStack.push_back(left);
      rightStack.push_back(right);

      while (leftStack.size() > 0 && rightStack.size() > 0) {
        left = leftStack.back();
        leftStack.pop_back();
        right = rightStack.back();
        rightStack.pop_back();
        if (!left != !right) {
          return false;
        }
        if (!left) {
          continue;
        }
        // There are actual expressions to compare here. Start with the custom
        // comparer function that was provided.
        if (comparer(left, right)) {
          continue;
        }
        if (left->type != right->type) {
          return false;
        }
        // Do the actual comparison, updating the names and stacks accordingly.
        if (!compareNodes(left, right)) {
          return false;
        }
      }
      if (leftStack.size() > 0 || rightStack.size() > 0) {
        return false;
      }
      return true;
    }

    bool compareNodes(Expression* left, Expression* right) {
      if (left->_id != right->_id) {
        return false;
      }

#define DELEGATE_ID left->_id

// Create cast versions of it for later operations.
#define DELEGATE_START(id)                                                     \
  [[maybe_unused]] auto* castLeft = left->cast<id>();                          \
  [[maybe_unused]] auto* castRight = right->cast<id>();

// Handle each type of field, comparing it appropriately.
#define DELEGATE_FIELD_CHILD(id, field)                                        \
  leftStack.push_back(castLeft->field);                                        \
  rightStack.push_back(castRight->field);

#define DELEGATE_FIELD_CHILD_VECTOR(id, field)                                 \
  if (castLeft->field.size() != castRight->field.size()) {                     \
    return false;                                                              \
  }                                                                            \
  for (auto* child : castLeft->field) {                                        \
    leftStack.push_back(child);                                                \
  }                                                                            \
  for (auto* child : castRight->field) {                                       \
    rightStack.push_back(child);                                               \
  }

#define COMPARE_FIELD(field)                                                   \
  if (castLeft->field != castRight->field) {                                   \
    return false;                                                              \
  }

#define DELEGATE_FIELD_INT(id, field) COMPARE_FIELD(field)
#define DELEGATE_FIELD_LITERAL(id, field) COMPARE_FIELD(field)
#define DELEGATE_FIELD_NAME(id, field) COMPARE_FIELD(field)
#define DELEGATE_FIELD_TYPE(id, field) COMPARE_FIELD(field)
#define DELEGATE_FIELD_HEAPTYPE(id, field) COMPARE_FIELD(field)
#define DELEGATE_FIELD_ADDRESS(id, field) COMPARE_FIELD(field)

#define COMPARE_LIST(field)                                                    \
  if (castLeft->field.size() != castRight->field.size()) {                     \
    return false;                                                              \
  }                                                                            \
  for (Index i = 0; i < castLeft->field.size(); i++) {                         \
    if (castLeft->field[i] != castRight->field[i]) {                           \
      return false;                                                            \
    }                                                                          \
  }

#define DELEGATE_FIELD_INT_ARRAY(id, field) COMPARE_LIST(field)
#define DELEGATE_FIELD_INT_VECTOR(id, field) COMPARE_LIST(field)
#define DELEGATE_FIELD_NAME_VECTOR(id, field) COMPARE_LIST(field)
#define DELEGATE_FIELD_TYPE_VECTOR(id, field) COMPARE_LIST(field)

#define DELEGATE_FIELD_SCOPE_NAME_DEF(id, field)                               \
  if (castLeft->field.is() != castRight->field.is()) {                         \
    return false;                                                              \
  }                                                                            \
  rightNames[castLeft->field] = castRight->field;

#define DELEGATE_FIELD_SCOPE_NAME_USE(id, field)                               \
  if (!compareNames(castLeft->field, castRight->field)) {                      \
    return false;                                                              \
  }

#define DELEGATE_FIELD_SCOPE_NAME_USE_VECTOR(id, field)                        \
  if (castLeft->field.size() != castRight->field.size()) {                     \
    return false;                                                              \
  }                                                                            \
  for (Index i = 0; i < castLeft->field.size(); i++) {                         \
    if (!compareNames(castLeft->field[i], castRight->field[i])) {              \
      return false;                                                            \
    }                                                                          \
  }

#include "wasm-delegations-fields.def"

      return true;
    }

    bool compareNames(Name left, Name right) {
      auto iter = rightNames.find(left);
      // If it's not found, that means it was defined out of the expression
      // being compared, in which case we can just treat it literally - it
      // must be exactly identical.
      if (iter != rightNames.end()) {
        left = iter->second;
      }
      return left == right;
    }
  };

  return Comparer().compare(left, right, comparer);
}

namespace {

struct Hasher {
  bool visitChildren;

  size_t digest = wasm::hash(0);

  Index internalCounter = 0;
  // for each internal name, its unique id
  std::map<Name, Index> internalNames;
  ExpressionStack stack;

  Hasher(Expression* curr,
         bool visitChildren,
         ExpressionAnalyzer::ExprHasher custom)
    : visitChildren(visitChildren) {
    stack.push_back(curr);
    // DELEGATE_CALLER_TARGET is a fake target used to denote delegating to
    // the caller. Add it here to prevent the unknown name error.
    noteScopeName(DELEGATE_CALLER_TARGET);

    while (stack.size() > 0) {
      curr = stack.back();
      stack.pop_back();
      if (!curr) {
        // This was an optional child that was not present. Hash a 0 to
        // represent that.
        rehash(digest, 0);
        continue;
      }
      rehash(digest, curr->_id);
      // we often don't need to hash the type, as it is tied to other values
      // we are hashing anyhow, but there are exceptions: for example, a
      // local.get's type is determined by the function, so if we are
      // hashing only expression fragments, then two from different
      // functions may turn out the same even if the type differs. Likewise,
      // if we hash between modules, then we need to take int account
      // call_imports type, etc. The simplest thing is just to hash the
      // type for all of them.
      rehash(digest, curr->type.getID());
      // If the custom hasher handled this expr, then we have nothing to do.
      if (custom(curr, digest)) {
        continue;
      }
      // Hash the contents of the expression normally.
      hashExpression(curr);
    }
  }

  void hashExpression(Expression* curr) {

#define DELEGATE_ID curr->_id

// Create cast versions of it for later operations.
#define DELEGATE_START(id) [[maybe_unused]] auto* cast = curr->cast<id>();

// Handle each type of field, comparing it appropriately.
#define DELEGATE_GET_FIELD(id, field) cast->field

#define DELEGATE_FIELD_CHILD(id, field)                                        \
  if (visitChildren) {                                                         \
    stack.push_back(cast->field);                                              \
  }

#define HASH_FIELD(field) rehash(digest, cast->field);

#define DELEGATE_FIELD_INT(id, field) HASH_FIELD(field)
#define DELEGATE_FIELD_LITERAL(id, field) HASH_FIELD(field)

#define DELEGATE_FIELD_NAME(id, field) visitNonScopeName(cast->field);
#define DELEGATE_FIELD_TYPE(id, field) visitType(cast->field);
#define DELEGATE_FIELD_HEAPTYPE(id, field) visitHeapType(cast->field);
#define DELEGATE_FIELD_ADDRESS(id, field) visitAddress(cast->field);

// Note that we only note the scope name, but do not also visit it. That means
// that (block $x) and (block) get the same hash. In other words, we only change
// the hash based on uses of scope names, that is when there is a noticeable
// difference in break targets.
#define DELEGATE_FIELD_SCOPE_NAME_DEF(id, field) noteScopeName(cast->field);

#define DELEGATE_FIELD_SCOPE_NAME_USE(id, field) visitScopeName(cast->field);

#include "wasm-delegations-fields.def"
  }

  void noteScopeName(Name curr) {
    if (curr.is()) {
      internalNames[curr] = internalCounter++;
    }
  }
  void visitScopeName(Name curr) {
    // We consider 3 cases here, and prefix a hash value of 0, 1, or 2 to
    // maximally differentiate them.

    // Try's delegate target can be null.
    if (!curr.is()) {
      rehash(digest, 0);
      return;
    }
    // Names are relative, we give the same hash for
    //   (block $x (br $x))
    //   (block $y (br $y))
    // But if the name is not known to us, hash the absolute one.
    if (!internalNames.contains(curr)) {
      rehash(digest, 1);
      // Perform the same hashing as a generic name.
      visitNonScopeName(curr);
      return;
    }
    rehash(digest, 2);
    rehash(digest, internalNames[curr]);
  }
  void visitNonScopeName(Name curr) { rehash(digest, curr); }
  void visitType(Type curr) { rehash(digest, curr.getID()); }
  void visitHeapType(HeapType curr) { rehash(digest, curr.getID()); }
  void visitAddress(Address curr) { rehash(digest, curr.addr); }
};

} // anonymous namespace

size_t ExpressionAnalyzer::flexibleHash(Expression* curr,
                                        ExpressionAnalyzer::ExprHasher custom) {
  return Hasher(curr, true, custom).digest;
}

size_t ExpressionAnalyzer::shallowHash(Expression* curr) {
  return Hasher(curr, false, ExpressionAnalyzer::nothingHasher).digest;
}

} // namespace wasm