// Copyright 2022 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/compiler/simplified-lowering-verifier.h"

#include "src/compiler/operation-typer.h"
#include "src/compiler/type-cache.h"

namespace v8 {
namespace internal {
namespace compiler {

Truncation LeastGeneralTruncation(const Truncation& t1, const Truncation& t2) {
  if (t1.IsLessGeneralThan(t2)) return t1;
  CHECK(t2.IsLessGeneralThan(t1));
  return t2;
}

Truncation LeastGeneralTruncation(const Truncation& t1, const Truncation& t2,
                                  const Truncation& t3) {
  return LeastGeneralTruncation(LeastGeneralTruncation(t1, t2), t3);
}

void SimplifiedLoweringVerifier::CheckType(Node* node, const Type& type) {
  CHECK(NodeProperties::IsTyped(node));
  Type node_type = NodeProperties::GetType(node);
  if (!type.Is(node_type)) {
    std::ostringstream type_str;
    type.PrintTo(type_str);
    std::ostringstream node_type_str;
    node_type.PrintTo(node_type_str);

    FATAL(
        "SimplifiedLoweringVerifierError: verified type %s of node #%d:%s "
        "does not match with type %s assigned during lowering",
        type_str.str().c_str(), node->id(), node->op()->mnemonic(),
        node_type_str.str().c_str());
  }
}

void SimplifiedLoweringVerifier::CheckAndSet(Node* node, const Type& type,
                                             const Truncation& trunc) {
  DCHECK(!type.IsInvalid());

  if (NodeProperties::IsTyped(node)) {
    CheckType(node, type);
  } else {
    // We store the type inferred by the verification pass. We do not update
    // the node's type directly, because following phases might encounter
    // unsound types as long as the verification is not complete.
    SetType(node, type);
  }
  SetTruncation(node, GeneralizeTruncation(trunc, type));
}

bool IsModuloTruncation(const Truncation& truncation) {
  return truncation.IsUsedAsWord32() || truncation.IsUsedAsWord64() ||
         Truncation::Any().IsLessGeneralThan(truncation);
}

Truncation SimplifiedLoweringVerifier::GeneralizeTruncation(
    const Truncation& truncation, const Type& type) const {
  IdentifyZeros identify_zeros = truncation.identify_zeros();
  if (!type.Maybe(Type::MinusZero())) {
    identify_zeros = IdentifyZeros::kDistinguishZeros;
  }

  switch (truncation.kind()) {
    case Truncation::TruncationKind::kAny: {
      return Truncation::Any(identify_zeros);
    }
    case Truncation::TruncationKind::kWord32: {
      if (type.Is(Type::Signed32OrMinusZero()) ||
          type.Is(Type::Unsigned32OrMinusZero())) {
        return Truncation::Any(identify_zeros);
      }
      return Truncation(Truncation::TruncationKind::kWord32, identify_zeros);
    }
    case Truncation::TruncationKind::kWord64: {
      if (type.Is(Type::BigInt())) {
        DCHECK_EQ(identify_zeros, IdentifyZeros::kDistinguishZeros);
        if (type.Is(Type::SignedBigInt64()) ||
            type.Is(Type::UnsignedBigInt64())) {
          return Truncation::Any(IdentifyZeros::kDistinguishZeros);
        }
      } else if (type.Is(TypeCache::Get()->kSafeIntegerOrMinusZero)) {
        return Truncation::Any(identify_zeros);
      }
      return Truncation(Truncation::TruncationKind::kWord64, identify_zeros);
    }

    default:
      // TODO(nicohartmann): Support remaining truncations.
      UNREACHABLE();
  }
}

void SimplifiedLoweringVerifier::VisitNode(Node* node,
                                           OperationTyper& op_typer) {
  switch (node->opcode()) {
    case IrOpcode::kInt64Constant: {
      // Constants might be untyped, because they are cached in the graph and
      // used in different contexts such that no single type can be assigned.
      // Their type is provided by an introduced TypeGuard where necessary.
      break;
    }
    case IrOpcode::kCheckedFloat64ToInt32: {
      Type input_type = InputType(node, 0);
      DCHECK(input_type.Is(Type::Number()));

      const auto& p = CheckMinusZeroParametersOf(node->op());
      if (p.mode() == CheckForMinusZeroMode::kCheckForMinusZero) {
        // Remove -0 from input_type.
        input_type =
            Type::Intersect(input_type, Type::Signed32(), graph_zone());
      } else {
        input_type = Type::Intersect(input_type, Type::Signed32OrMinusZero(),
                                     graph_zone());
      }
      CheckAndSet(node, input_type, Truncation::Word32());
      break;
    }
    case IrOpcode::kInt32Add: {
      Type output_type =
          op_typer.NumberAdd(InputType(node, 0), InputType(node, 1));
      Truncation output_trunc = LeastGeneralTruncation(InputTruncation(node, 0),
                                                       InputTruncation(node, 1),
                                                       Truncation::Word32());
      CHECK(IsModuloTruncation(output_trunc));
      CheckAndSet(node, output_type, output_trunc);
      break;
    }
    case IrOpcode::kInt32Sub: {
      Type output_type =
          op_typer.NumberSubtract(InputType(node, 0), InputType(node, 1));
      Truncation output_trunc = LeastGeneralTruncation(InputTruncation(node, 0),
                                                       InputTruncation(node, 1),
                                                       Truncation::Word32());
      CHECK(IsModuloTruncation(output_trunc));
      CheckAndSet(node, output_type, output_trunc);
      break;
    }
    case IrOpcode::kChangeInt31ToTaggedSigned: {
      // ChangeInt31ToTaggedSigned is not truncating any values, so we can
      // simply forward input.
      CheckAndSet(node, InputType(node, 0), InputTruncation(node, 0));
      break;
    }
    case IrOpcode::kChangeInt32ToTagged: {
      // ChangeInt32ToTagged is not truncating any values, so we can simply
      // forward input.
      CheckAndSet(node, InputType(node, 0), InputTruncation(node, 0));
      break;
    }
    case IrOpcode::kInt64Add: {
      Type left_type = InputType(node, 0);
      Type right_type = InputType(node, 1);

      Type output_type;
      if (left_type.Is(Type::BigInt()) && right_type.Is(Type::BigInt())) {
        // BigInt x BigInt -> BigInt
        output_type = op_typer.BigIntAdd(left_type, right_type);
      } else if (left_type.Is(Type::Number()) &&
                 right_type.Is(Type::Number())) {
        // Number x Number -> Number
        output_type = op_typer.NumberAdd(left_type, right_type);
      } else {
        // Invalid type combination.
        std::ostringstream left_str, right_str;
        left_type.PrintTo(left_str);
        right_type.PrintTo(right_str);
        FATAL(
            "SimplifiedLoweringVerifierError: invalid combination of input "
            "types "
            "%s and %s for node #%d:%s",
            left_str.str().c_str(), right_str.str().c_str(), node->id(),
            node->op()->mnemonic());
      }

      Truncation output_trunc = LeastGeneralTruncation(InputTruncation(node, 0),
                                                       InputTruncation(node, 1),
                                                       Truncation::Word64());
      CHECK(IsModuloTruncation(output_trunc));
      CheckAndSet(node, output_type, output_trunc);
      break;
    }
    case IrOpcode::kChangeInt32ToInt64: {
      // ChangeInt32ToInt64 is not truncating any values, so we can simply
      // forward input.
      CheckAndSet(node, InputType(node, 0), InputTruncation(node, 0));
      break;
    }
    case IrOpcode::kDeadValue: {
      CheckAndSet(node, Type::None(), Truncation::Any());
      break;
    }
    case IrOpcode::kTypeGuard: {
      Type output_type = op_typer.TypeTypeGuard(node->op(), InputType(node, 0));
      // TypeGuard has no effect on trunction, but the restricted type may help
      // generalize it.
      CheckAndSet(node, output_type, InputTruncation(node, 0));
      break;
    }
    case IrOpcode::kTruncateBigIntToWord64: {
      Type input_type = InputType(node, 0);
      CHECK(input_type.Is(Type::BigInt()));
      CHECK(Truncation::Word64().IsLessGeneralThan(InputTruncation(node, 0)));
      CheckAndSet(node, input_type, Truncation::Word64());
      break;
    }
    case IrOpcode::kChangeTaggedSignedToInt64: {
      Type input_type = InputType(node, 0);
      CHECK(input_type.Is(Type::Number()));
      Truncation output_trunc = LeastGeneralTruncation(InputTruncation(node, 0),
                                                       Truncation::Word64());
      CheckAndSet(node, input_type, output_trunc);
      break;
    }
    case IrOpcode::kCheckBigInt: {
      Type input_type = InputType(node, 0);
      input_type = Type::Intersect(input_type, Type::BigInt(), graph_zone());
      CheckAndSet(node, input_type, InputTruncation(node, 0));
      break;
    }
    case IrOpcode::kReturn: {
      const int return_value_count = ValueInputCountOfReturn(node->op());
      for (int i = 0; i < return_value_count; ++i) {
        Type input_type = InputType(node, 1 + i);
        Truncation input_trunc = InputTruncation(node, 1 + i);
        input_trunc = GeneralizeTruncation(input_trunc, input_type);
        // No values must be lost due to truncation.
        CHECK_EQ(input_trunc, Truncation::Any());
      }
      break;
    }
    case IrOpcode::kSLVerifierHint: {
      Type output_type = InputType(node, 0);
      Truncation output_trunc = InputTruncation(node, 0);
      const auto& p = SLVerifierHintParametersOf(node->op());

      if (const Operator* semantics = p.semantics()) {
        switch (semantics->opcode()) {
          case IrOpcode::kPlainPrimitiveToNumber:
            output_type = op_typer.ToNumber(output_type);
            break;
          default:
            UNREACHABLE();
        }
        CheckType(node, output_type);
      }

      if (p.override_output_type()) {
        output_type = *p.override_output_type();
      }

      SetType(node, output_type);
      SetTruncation(node, GeneralizeTruncation(output_trunc, output_type));
      break;
    }

    default:
      // TODO(nicohartmann): Support remaining operators.
      break;
  }
}

}  // namespace compiler
}  // namespace internal
}  // namespace v8