src/ir/bits.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_bits_h
#define wasm_ir_bits_h

#include "ir/boolean.h"
#include "ir/literal-utils.h"
#include "ir/load-utils.h"
#include "ir/match.h"
#include "support/bits.h"
#include "wasm-builder.h"

namespace wasm::Bits {

// Get a mask to keep only the low # of bits.
inline int32_t lowBitMask(int32_t bits) {
  uint32_t ret = -1;
  if (bits <= 0) {
    return 0;
  }
  if (bits >= 32) {
    return ret;
  }
  return ret >> (32 - bits);
}

inline int64_t lowBitMask64(int64_t bits) {
  uint64_t ret = -1;
  if (bits <= 0) {
    return 0;
  }
  if (bits >= 64) {
    return ret;
  }
  return ret >> (64 - bits);
}

// checks if the input is a mask of lower bits, i.e., all 1s up to some high
// bit, and all zeros from there. returns the number of masked bits, or 0 if
// this is not such a mask
inline uint32_t getMaskedBits(uint32_t mask) {
  if (mask == uint32_t(-1)) {
    return 32; // all the bits
  }
  if (mask == 0) {
    return 0; // trivially not a mask
  }
  // otherwise, see if x & (x + 1) turns this into non-zero value
  // 00011111 & (00011111 + 1) => 0
  if (mask & (mask + 1)) {
    return 0;
  }
  // this is indeed a mask
  return 32 - countLeadingZeroes(mask);
}

// gets the number of effective shifts a shift operation does. In
// wasm, only 5 bits matter for 32-bit shifts, and 6 for 64.
inline Index getEffectiveShifts(Index amount, Type type) {
  if (type == Type::i32) {
    return amount & 31;
  } else if (type == Type::i64) {
    return amount & 63;
  }
  WASM_UNREACHABLE("unexpected type");
}

inline Index getEffectiveShifts(Expression* expr) {
  auto* amount = expr->cast<Const>();
  if (amount->type == Type::i32) {
    return getEffectiveShifts(amount->value.geti32(), Type::i32);
  } else if (amount->type == Type::i64) {
    return getEffectiveShifts(amount->value.geti64(), Type::i64);
  }
  WASM_UNREACHABLE("unexpected type");
}

inline Expression* makeSignExt(Expression* value, Index bytes, Module& wasm) {
  if (value->type == Type::i32) {
    if (bytes == 1 || bytes == 2) {
      auto shifts = bytes == 1 ? 24 : 16;
      Builder builder(wasm);
      return builder.makeBinary(
        ShrSInt32,
        builder.makeBinary(
          ShlInt32,
          value,
          LiteralUtils::makeFromInt32(shifts, Type::i32, wasm)),
        LiteralUtils::makeFromInt32(shifts, Type::i32, wasm));
    }
    assert(bytes == 4);
    return value; // nothing to do
  } else {
    assert(value->type == Type::i64);
    if (bytes == 1 || bytes == 2 || bytes == 4) {
      auto shifts = bytes == 1 ? 56 : (bytes == 2 ? 48 : 32);
      Builder builder(wasm);
      return builder.makeBinary(
        ShrSInt64,
        builder.makeBinary(
          ShlInt64,
          value,
          LiteralUtils::makeFromInt32(shifts, Type::i64, wasm)),
        LiteralUtils::makeFromInt32(shifts, Type::i64, wasm));
    }
    assert(bytes == 8);
    return value; // nothing to do
  }
}

// Given a value that is read from a field, as a replacement for a
// StructGet/ArrayGet that we inferred the value of, and given the signedness of
// the get and the field info, if we are doing a signed read of a packed field
// then sign-extend it, or if it is unsigned then truncate. This fixes up cases
// where we can replace the StructGet/ArrayGet with the value we know must be
// there (without making any assumptions about |value|, that is, we do not
// assume it has been truncated already).
inline Expression* makePackedFieldGet(Expression* value,
                                      const Field& field,
                                      bool signed_,
                                      Module& wasm) {
  if (!field.isPacked()) {
    return value;
  }

  if (signed_) {
    return makeSignExt(value, field.getByteSize(), wasm);
  }

  Builder builder(wasm);
  auto mask = Bits::lowBitMask(field.getByteSize() * 8);
  return builder.makeBinary(AndInt32, value, builder.makeConst(int32_t(mask)));
}

// Check if an expression is a sign-extend, and if so, returns the value
// that is extended, otherwise nullptr
inline Expression* getSignExtValue(Expression* curr) {
  // We only care about integers here, and ignore unreachables, etc.
  if (!curr->type.isInteger()) {
    return nullptr;
  }
  if (auto* unary = curr->dynCast<Unary>()) {
    switch (unary->op) {
      case ExtendS8Int32:
      case ExtendS16Int32:
      case ExtendS8Int64:
      case ExtendS16Int64:
      case ExtendS32Int64:
        // The operand may have become unreachable before refinalization updates
        // `curr->type`.
        return unary->value->type.isInteger() ? unary->value : nullptr;
      default:
        return nullptr;
    }
  }
  using namespace Abstract;
  using namespace Match;
  int64_t leftShift = 0, rightShift = 0;
  Expression* extended = nullptr;
  if (matches(curr,
              binary(ShrS,
                     binary(Shl, any(&extended), ival(&leftShift)),
                     ival(&rightShift)))) {
    auto leftShifts = getEffectiveShifts(leftShift, curr->type);
    auto rightShifts = getEffectiveShifts(rightShift, curr->type);
    if (leftShifts != 0 && leftShifts == rightShifts) {
      return extended;
    }
  }
  return nullptr;
}

// Check if an expression is almost a sign-extend: perhaps the inner shift
// is too large. We can split the shifts in that case, which is sometimes
// useful (e.g. if we can remove the signext)
inline Expression* getAlmostSignExt(Expression* curr) {
  using namespace Abstract;
  using namespace Match;
  int64_t leftShift = 0, rightShift = 0;
  Expression* extended = nullptr;
  if (matches(curr,
              binary(ShrS,
                     binary(Shl, any(&extended), ival(&leftShift)),
                     ival(&rightShift)))) {
    auto leftShifts = getEffectiveShifts(leftShift, curr->type);
    auto rightShifts = getEffectiveShifts(rightShift, curr->type);
    if (rightShifts != 0 && rightShifts <= leftShifts) {
      return extended;
    }
  }
  return nullptr;
}

// Returns the number of low bits kept by an almost-sign-extend (including any
// extra left-shifted zero bits), and sets |extraLeftShifts| to the number of
// extra left shifts.
inline Index getAlmostSignExtKeptBits(Expression* curr,
                                      Index& extraLeftShifts) {
  auto* leftShift = curr->cast<Binary>()->left->cast<Binary>()->right;
  auto* rightShift = curr->cast<Binary>()->right;
  extraLeftShifts =
    getEffectiveShifts(leftShift) - getEffectiveShifts(rightShift);
  return curr->type.getByteSize() * 8 - getEffectiveShifts(rightShift);
}

// Check if an expression is a zero-extend, and if so, returns the value
// that is extended, otherwise nullptr
inline Expression* getZeroExtValue(Expression* curr) {
  // We only care about i32s here, and ignore i64s, unreachables, etc.
  if (curr->type != Type::i32) {
    return nullptr;
  }
  using namespace Match;
  int32_t mask = 0;
  Expression* extended = nullptr;
  if (matches(curr, binary(AndInt32, any(&extended), i32(&mask))) &&
      getMaskedBits(mask) != 0) {
    return extended;
  }
  return nullptr;
}

// Returns the number of low bits kept by a zero-extend operation.
inline Index getZeroExtKeptBits(Expression* curr) {
  assert(curr->type == Type::i32);
  int32_t mask = curr->cast<Binary>()->right->cast<Const>()->value.geti32();
  return getMaskedBits(mask);
}

// Interface for providing known bit properties of locals.
struct LocalInfoProvider {
  virtual ~LocalInfoProvider() = default;
  virtual Index getMaxBitsForLocal(LocalGet* get) const = 0;
  virtual Index getSignExtKeptBitsForLocal(LocalGet* get) const = 0;
};

// LocalInfoProvider helper that has pessimistic results for the bits used in
// locals.
struct DummyLocalInfoProvider : LocalInfoProvider {
  Index getMaxBitsForLocal(LocalGet* get) const override {
    if (get->type == Type::i32) {
      return 32;
    } else if (get->type == Type::i64) {
      return 64;
    }
    WASM_UNREACHABLE("type has no integer bit size");
  }

  Index getSignExtKeptBitsForLocal(LocalGet* get) const override { return 0; }
};

class Provider {
  const LocalInfoProvider& localInfoProvider;

  static inline const DummyLocalInfoProvider dummyLocalInfoProvider{};

public:
  Provider(const LocalInfoProvider* localInfoProvider = nullptr)
    : localInfoProvider(localInfoProvider ? *localInfoProvider
                                          : dummyLocalInfoProvider) {}

  // Returns the maximum amount of bits used in an integer expression
  // not extremely precise (doesn't look into add operands, etc.)
  Index getMaxBits(Expression* curr) const {
    if (Properties::emitsBoolean(curr)) {
      return 1;
    }
    if (auto* c = curr->dynCast<Const>()) {
      switch (curr->type.getBasic()) {
        case Type::i32:
          return 32 - c->value.countLeadingZeroes().geti32();
        case Type::i64:
          return 64 - c->value.countLeadingZeroes().geti64();
        default:
          WASM_UNREACHABLE("invalid type");
      }
    } else if (auto* binary = curr->dynCast<Binary>()) {
      switch (binary->op) {
        // 32-bit
        case RotLInt32:
        case RotRInt32:
        case SubInt32:
          return 32;
        case AddInt32: {
          auto maxBitsLeft = getMaxBits(binary->left);
          auto maxBitsRight = getMaxBits(binary->right);
          return std::min(Index(32), std::max(maxBitsLeft, maxBitsRight) + 1);
        }
        case MulInt32: {
          auto maxBitsRight = getMaxBits(binary->right);
          auto maxBitsLeft = getMaxBits(binary->left);
          return std::min(Index(32), maxBitsLeft + maxBitsRight);
        }
        case DivSInt32: {
          if (auto* c = binary->right->dynCast<Const>()) {
            int32_t maxBitsLeft = getMaxBits(binary->left);
            // If either side might be negative, then the result will be
            // negative
            if (maxBitsLeft == 32 || c->value.geti32() < 0) {
              return 32;
            }
            int32_t bitsRight = getMaxBits(c);
            // Apply std::min: Result bits cannot exceed dividend bits
            return std::min(maxBitsLeft,
                            std::max(0, maxBitsLeft - bitsRight + 1));
          }
          return 32;
        }
        case DivUInt32: {
          int32_t maxBitsLeft = getMaxBits(binary->left);
          if (auto* c = binary->right->dynCast<Const>()) {
            int32_t bitsRight = getMaxBits(c);
            // Apply std::min: Result bits cannot exceed dividend bits
            return std::min(maxBitsLeft,
                            std::max(0, maxBitsLeft - bitsRight + 1));
          }
          return maxBitsLeft;
        }
        case RemSInt32: {
          if (auto* c = binary->right->dynCast<Const>()) {
            auto maxBitsLeft = getMaxBits(binary->left);
            // if left may be negative, the result may be negative
            if (maxBitsLeft == 32) {
              return 32;
            }
            auto bitsRight = Index(ceilLog2(c->value.geti32()));
            return std::min(maxBitsLeft, bitsRight);
          }
          return 32;
        }
        case RemUInt32: {
          if (auto* c = binary->right->dynCast<Const>()) {
            auto maxBitsLeft = getMaxBits(binary->left);
            auto bitsRight = Index(ceilLog2(c->value.geti32()));
            return std::min(maxBitsLeft, bitsRight);
          }
          return 32;
        }
        case AndInt32: {
          return std::min(getMaxBits(binary->left), getMaxBits(binary->right));
        }
        case OrInt32:
        case XorInt32: {
          return std::max(getMaxBits(binary->left), getMaxBits(binary->right));
        }
        case ShlInt32: {
          if (auto* shifts = binary->right->dynCast<Const>()) {
            return std::min(
              Index(32), getMaxBits(binary->left) + getEffectiveShifts(shifts));
          }
          return 32;
        }
        case ShrUInt32: {
          if (auto* shift = binary->right->dynCast<Const>()) {
            auto maxBits = getMaxBits(binary->left);
            auto shifts =
              std::min(Index(getEffectiveShifts(shift)),
                       maxBits); // can ignore more shifts than zero us out
            return std::max(Index(0), maxBits - shifts);
          }
          return 32;
        }
        case ShrSInt32: {
          if (auto* shift = binary->right->dynCast<Const>()) {
            auto maxBits = getMaxBits(binary->left);
            // if left may be negative, the result may be negative
            if (maxBits == 32) {
              return 32;
            }
            auto shifts =
              std::min(Index(getEffectiveShifts(shift)),
                       maxBits); // can ignore more shifts than zero us out
            return std::max(Index(0), maxBits - shifts);
          }
          return 32;
        }
        case RotLInt64:
        case RotRInt64:
        case SubInt64:
          return 64;
        case AddInt64: {
          auto maxBitsLeft = getMaxBits(binary->left);
          auto maxBitsRight = getMaxBits(binary->right);
          return std::min(Index(64), std::max(maxBitsLeft, maxBitsRight) + 1);
        }
        case MulInt64: {
          auto maxBitsRight = getMaxBits(binary->right);
          auto maxBitsLeft = getMaxBits(binary->left);
          return std::min(Index(64), maxBitsLeft + maxBitsRight);
        }
        case DivSInt64: {
          if (auto* c = binary->right->dynCast<Const>()) {
            int32_t maxBitsLeft = getMaxBits(binary->left);
            // if left or right const value is negative
            if (maxBitsLeft == 64 || c->value.geti64() < 0) {
              return 64;
            }
            int32_t bitsRight = getMaxBits(c);
            // Apply std::min: Result bits cannot exceed dividend bits
            return std::min(maxBitsLeft,
                            std::max(0, maxBitsLeft - bitsRight + 1));
          }
          return 64;
        }
        case DivUInt64: {
          int32_t maxBitsLeft = getMaxBits(binary->left);
          if (auto* c = binary->right->dynCast<Const>()) {
            int32_t bitsRight = getMaxBits(c);
            // Apply std::min: Result bits cannot exceed dividend bits
            return std::min(maxBitsLeft,
                            std::max(0, maxBitsLeft - bitsRight + 1));
          }
          return maxBitsLeft;
        }
        case RemSInt64: {
          if (auto* c = binary->right->dynCast<Const>()) {
            auto maxBitsLeft = getMaxBits(binary->left);
            // if left may be negative, the result may be negative
            if (maxBitsLeft == 64) {
              return 64;
            }
            auto bitsRight = Index(ceilLog2(c->value.geti64()));
            return std::min(maxBitsLeft, bitsRight);
          }
          return 64;
        }
        case RemUInt64: {
          if (auto* c = binary->right->dynCast<Const>()) {
            auto maxBitsLeft = getMaxBits(binary->left);
            auto bitsRight = Index(ceilLog2(c->value.geti64()));
            return std::min(maxBitsLeft, bitsRight);
          }
          return 64;
        }
        case AndInt64: {
          return std::min(getMaxBits(binary->left), getMaxBits(binary->right));
        }
        case OrInt64:
        case XorInt64: {
          return std::max(getMaxBits(binary->left), getMaxBits(binary->right));
        }
        case ShlInt64: {
          if (auto* shifts = binary->right->dynCast<Const>()) {
            auto maxBits = getMaxBits(binary->left);
            return std::min(Index(64), getEffectiveShifts(shifts) + maxBits);
          }
          return 64;
        }
        case ShrUInt64: {
          if (auto* shift = binary->right->dynCast<Const>()) {
            auto maxBits = getMaxBits(binary->left);
            auto shifts =
              std::min(Index(getEffectiveShifts(shift)),
                       maxBits); // can ignore more shifts than zero us out
            return std::max(Index(0), maxBits - shifts);
          }
          return 64;
        }
        case ShrSInt64: {
          if (auto* shift = binary->right->dynCast<Const>()) {
            auto maxBits = getMaxBits(binary->left);
            // if left may be negative, the result may be negative
            if (maxBits == 64) {
              return 64;
            }
            auto shifts =
              std::min(Index(getEffectiveShifts(shift)),
                       maxBits); // can ignore more shifts than zero us out
            return std::max(Index(0), maxBits - shifts);
          }
          return 64;
        }
        // comparisons
        case EqInt32:
        case NeInt32:
        case LtSInt32:
        case LtUInt32:
        case LeSInt32:
        case LeUInt32:
        case GtSInt32:
        case GtUInt32:
        case GeSInt32:
        case GeUInt32:

        case EqInt64:
        case NeInt64:
        case LtSInt64:
        case LtUInt64:
        case LeSInt64:
        case LeUInt64:
        case GtSInt64:
        case GtUInt64:
        case GeSInt64:
        case GeUInt64:

        case EqFloat32:
        case NeFloat32:
        case LtFloat32:
        case LeFloat32:
        case GtFloat32:
        case GeFloat32:

        case EqFloat64:
        case NeFloat64:
        case LtFloat64:
        case LeFloat64:
        case GtFloat64:
        case GeFloat64:
          WASM_UNREACHABLE("relationals handled before");
        default: {
        }
      }
    } else if (auto* unary = curr->dynCast<Unary>()) {
      switch (unary->op) {
        case ClzInt32:
        case CtzInt32:
        case PopcntInt32:
          return 6;
        case ClzInt64:
        case CtzInt64:
        case PopcntInt64:
          return 7;
        case EqZInt32:
        case EqZInt64:
          WASM_UNREACHABLE("relationals handled before");
        case WrapInt64:
        case ExtendUInt32:
          return std::min(Index(32), getMaxBits(unary->value));
        case ExtendS8Int32: {
          auto maxBits = getMaxBits(unary->value);
          return maxBits >= 8 ? Index(32) : maxBits;
        }
        case ExtendS16Int32: {
          auto maxBits = getMaxBits(unary->value);
          return maxBits >= 16 ? Index(32) : maxBits;
        }
        case ExtendS8Int64: {
          auto maxBits = getMaxBits(unary->value);
          return maxBits >= 8 ? Index(64) : maxBits;
        }
        case ExtendS16Int64: {
          auto maxBits = getMaxBits(unary->value);
          return maxBits >= 16 ? Index(64) : maxBits;
        }
        case ExtendS32Int64:
        case ExtendSInt32: {
          auto maxBits = getMaxBits(unary->value);
          return maxBits >= 32 ? Index(64) : maxBits;
        }
        default: {
        }
      }
    } else if (auto* set = curr->dynCast<LocalSet>()) {
      // a tee passes through the value
      return getMaxBits(set->value);
    } else if (auto* get = curr->dynCast<LocalGet>()) {
      return localInfoProvider.getMaxBitsForLocal(get);
    } else if (auto* load = curr->dynCast<Load>()) {
      // if signed, then the sign-extension might fill all the bits
      // if unsigned, then we have a limit
      if (LoadUtils::isSignRelevant(load) && !load->signed_) {
        return 8 * load->bytes;
      }
    } else if (auto* block = curr->dynCast<Block>()) {
      if (!block->name.is() && !block->list.empty() &&
          block->type.isConcrete()) {
        return getMaxBits(block->list.back());
      }
    }
    switch (curr->type.getBasic()) {
      case Type::i32:
        return 32;
      case Type::i64:
        return 64;
      case Type::unreachable:
        return 64; // not interesting, but don't crash
      default:
        WASM_UNREACHABLE("invalid type");
    }
  }

  // As getMaxBits, but returns the minimum amount of bits.
  Index getMinBits(Expression* curr) const {
    if (auto* c = curr->dynCast<Const>()) {
      // Constants are simple: the min and max are identical.
      return getMaxBits(c);
    }

    // TODO: everything else
    return 0;
  }

  // If |curr| is known to be sign-extended, returns the number of low bits kept
  // before sign-extending into the upper bits, or 0 otherwise.
  Index getSignExtKeptBits(Expression* curr) const {
    if (getSignExtValue(curr)) {
      if (auto* unary = curr->dynCast<Unary>()) {
        switch (unary->op) {
          case ExtendS8Int32:
          case ExtendS8Int64:
            return 8;
          case ExtendS16Int32:
          case ExtendS16Int64:
            return 16;
          case ExtendS32Int64:
            return 32;
          default:
            WASM_UNREACHABLE("invalid unary operation");
        }
      } else {
        auto* rightShift = curr->cast<Binary>()->right;
        return curr->type.getByteSize() * 8 - getEffectiveShifts(rightShift);
      }
    }
    if (auto* get = curr->dynCast<LocalGet>()) {
      return localInfoProvider.getSignExtKeptBitsForLocal(get);
    }
    return 0;
  }
};

inline Index getMaxBits(Expression* curr) {
  return Provider().getMaxBits(curr);
}

inline Index getMinBits(Expression* curr) {
  return Provider().getMinBits(curr);
}

inline Index getSignExtKeptBits(Expression* curr) {
  return Provider().getSignExtKeptBits(curr);
}

} // namespace wasm::Bits

#endif // wasm_ir_bits_h