Evaluator.h

Go to the documentation of this file.

//===- Evaluator.h - Object Model dialect evaluator -----------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file contains the Object Model dialect declaration.
//
//===----------------------------------------------------------------------===//
 
#ifndef CIRCT_DIALECT_OM_EVALUATOR_EVALUATOR_H
#define CIRCT_DIALECT_OM_EVALUATOR_EVALUATOR_H
 
#include "circt/Dialect/OM/OMOps.h"
#include "circt/Support/LLVM.h"
#include "mlir/IR/BuiltinOps.h"
#include "mlir/IR/Diagnostics.h"
#include "mlir/IR/Location.h"
#include "mlir/IR/MLIRContext.h"
#include "mlir/IR/SymbolTable.h"
#include "mlir/Support/LogicalResult.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/Support/Debug.h"
 
#include <queue>
#include <utility>
 
namespace circt {
namespace om {
 
namespace evaluator {
class EvaluatorValue;
 
/// A value of an object in memory. It is either a composite Object, or a
/// primitive Attribute. Further refinement is expected.
using EvaluatorValuePtr = std::shared_ptr<EvaluatorValue>;
 
/// The fields of a composite Object, currently represented as a map. Further
/// refinement is expected.
using ObjectFields = SmallDenseMap<StringAttr, EvaluatorValuePtr>;
 
/// Base class for evaluator runtime values.
/// Enables the shared_from_this functionality so Evaluator Value pointers can
/// be passed through the CAPI and unwrapped back into C++ smart pointers with
/// the appropriate reference count.
class EvaluatorValue : public std::enable_shared_from_this<EvaluatorValue> {
public:
  // Implement LLVM RTTI.
  enum class Kind { Attr, Object, List, Reference, BasePath, Path };
  EvaluatorValue(MLIRContext *ctx, Kind kind, Location loc)
      : kind(kind), ctx(ctx), loc(loc) {}
  Kind getKind() const { return kind; }
  MLIRContext *getContext() const { return ctx; }
 
  // Return true the value is fully evaluated.
  // Unknown values are considered fully evaluated.
  bool isFullyEvaluated() const { return fullyEvaluated; }
  void markFullyEvaluated() {
    assert(!fullyEvaluated && "should not mark twice");
    fullyEvaluated = true;
    // Increment the counter if one is set.
    if (fullyEvaluatedCounter)
      ++(*fullyEvaluatedCounter);
  }
 
  /// Set a counter to increment when this value becomes fully evaluated.
  void setFullyEvaluatedCounter(uint64_t *counter) {
    fullyEvaluatedCounter = counter;
  }
 
  /// Return true if the value is unknown (has unknown in its fan-in).
  /// A value is unknown if it depends on an UnknownValueOp or if any of its
  /// inputs are unknown. Unknown values propagate through operations.
  bool isUnknown() const { return unknown; }
 
  /// Mark this value as unknown.
  /// This also marks the value as fully evaluated if it isn't already, since
  /// unknown values are considered fully evaluated. This maintains the
  /// invariant that unknown implies fullyEvaluated.
  void markUnknown() {
    unknown = true;
    if (!fullyEvaluated)
      markFullyEvaluated();
  }
 
  /// Return the associated MLIR context.
  MLIRContext *getContext() { return ctx; }
 
  // Return a MLIR type which the value represents.
  Type getType() const;
 
  // Finalize the evaluator value. Strip intermidiate reference values.
  LogicalResult finalize();
 
  // Return the Location associated with the Value.
  Location getLoc() const { return loc; }
  // Set the Location associated with the Value.
  void setLoc(Location l) { loc = l; }
  // Set the Location, if it is unknown.
  void setLocIfUnknown(Location l) {
    if (isa<UnknownLoc>(loc))
      loc = l;
  }
 
private:
  const Kind kind;
  MLIRContext *ctx;
  Location loc;
  bool fullyEvaluated = false;
  bool finalized = false;
  bool unknown = false;
  uint64_t *fullyEvaluatedCounter = nullptr;
};
 
/// Values which can be used as pointers to different values.
/// ReferenceValue is replaced with its element and erased at the end of
/// evaluation.
class ReferenceValue : public EvaluatorValue {
public:
  ReferenceValue(Type type, Location loc)
      : EvaluatorValue(type.getContext(), Kind::Reference, loc), value(nullptr),
        type(type) {}
 
  // Implement LLVM RTTI.
  static bool classof(const EvaluatorValue *e) {
    return e->getKind() == Kind::Reference;
  }
 
  Type getValueType() const { return type; }
  EvaluatorValuePtr getValue() const { return value; }
  void setValue(EvaluatorValuePtr newValue) {
    value = std::move(newValue);
    markFullyEvaluated();
  }
 
  // Finalize the value.
  LogicalResult finalizeImpl();
 
  // Return the first non-reference value that is reachable from the reference.
  FailureOr<EvaluatorValuePtr> getStrippedValue() const {
    llvm::SmallPtrSet<ReferenceValue *, 4> visited;
    auto currentValue = value;
    while (auto *v = dyn_cast<ReferenceValue>(currentValue.get())) {
      // Detect a cycle.
      if (!visited.insert(v).second)
        return failure();
      currentValue = v->getValue();
    }
    return success(currentValue);
  }
 
private:
  EvaluatorValuePtr value;
  Type type;
};
 
/// Values which can be directly representable by MLIR attributes.
class AttributeValue : public EvaluatorValue {
public:
  Attribute getAttr() const { return attr; }
  template <typename AttrTy>
  AttrTy getAs() const {
    return dyn_cast<AttrTy>(attr);
  }
  static bool classof(const EvaluatorValue *e) {
    return e->getKind() == Kind::Attr;
  }
 
  // Set Attribute for partially evaluated case.
  LogicalResult setAttr(Attribute attr);
 
  // Finalize the value.
  LogicalResult finalizeImpl();
 
  Type getType() const { return type; }
 
  // Factory methods that create AttributeValue objects
  static std::shared_ptr<EvaluatorValue> get(Attribute attr,
                                             LocationAttr loc = {});
  static std::shared_ptr<EvaluatorValue> get(Type type, LocationAttr loc = {});
 
private:
  // Make AttributeValue constructible only by the factory methods
  struct PrivateTag {};
 
  // Constructor that requires a PrivateTag
  AttributeValue(PrivateTag, Attribute attr, Location loc)
      : EvaluatorValue(attr.getContext(), Kind::Attr, loc), attr(attr),
        type(cast<TypedAttr>(attr).getType()) {
    markFullyEvaluated();
  }
 
  // Constructor for partially evaluated AttributeValue
  AttributeValue(PrivateTag, Type type, Location loc)
      : EvaluatorValue(type.getContext(), Kind::Attr, loc), type(type) {}
 
  Attribute attr = {};
  Type type;
 
  // Friend declaration for the factory methods
  friend std::shared_ptr<EvaluatorValue> get(Attribute attr, LocationAttr loc);
  friend std::shared_ptr<EvaluatorValue> get(Type type, LocationAttr loc);
};
 
// This perform finalization to `value`.
static inline LogicalResult finalizeEvaluatorValue(EvaluatorValuePtr &value) {
  if (failed(value->finalize()))
    return failure();
  if (auto *ref = llvm::dyn_cast<ReferenceValue>(value.get())) {
    auto v = ref->getStrippedValue();
    if (failed(v))
      return v;
    value = v.value();
  }
  return success();
}
 
/// A List which contains variadic length of elements with the same type.
class ListValue : public EvaluatorValue {
public:
  ListValue(om::ListType type, SmallVector<EvaluatorValuePtr> elements,
            Location loc)
      : EvaluatorValue(type.getContext(), Kind::List, loc), type(type),
        elements(std::move(elements)) {
    markFullyEvaluated();
  }
 
  void setElements(SmallVector<EvaluatorValuePtr> newElements) {
    elements = std::move(newElements);
    markFullyEvaluated();
  }
 
  // Finalize the value.
  LogicalResult finalizeImpl();
 
  // Partially evaluated value.
  ListValue(om::ListType type, Location loc)
      : EvaluatorValue(type.getContext(), Kind::List, loc), type(type) {}
 
  const auto &getElements() const { return elements; }
 
  /// Return the type of the value, which is a ListType.
  om::ListType getListType() const { return type; }
 
  /// Implement LLVM RTTI.
  static bool classof(const EvaluatorValue *e) {
    return e->getKind() == Kind::List;
  }
 
private:
  om::ListType type;
  SmallVector<EvaluatorValuePtr> elements;
};
 
/// A composite Object, which has a type and fields.
class ObjectValue : public EvaluatorValue {
public:
  ObjectValue(om::ClassLike cls, ObjectFields fields, Location loc)
      : EvaluatorValue(cls.getContext(), Kind::Object, loc), cls(cls),
        fields(std::move(fields)) {
    markFullyEvaluated();
  }
 
  // Partially evaluated value.
  ObjectValue(om::ClassLike cls, Location loc)
      : EvaluatorValue(cls.getContext(), Kind::Object, loc), cls(cls) {}
 
  om::ClassLike getClassOp() const { return cls; }
  const auto &getFields() const { return fields; }
 
  void setFields(llvm::SmallDenseMap<StringAttr, EvaluatorValuePtr> newFields) {
    fields = std::move(newFields);
    markFullyEvaluated();
  }
 
  /// Return the type of the value, which is a ClassType.
  om::ClassType getObjectType() const {
    auto clsNonConst = const_cast<om::ClassLike &>(cls);
    return ClassType::get(clsNonConst.getContext(),
                          FlatSymbolRefAttr::get(clsNonConst.getSymNameAttr()));
  }
 
  Type getType() const { return getObjectType(); }
 
  /// Implement LLVM RTTI.
  static bool classof(const EvaluatorValue *e) {
    return e->getKind() == Kind::Object;
  }
 
  /// Get a field of the Object by name.
  FailureOr<EvaluatorValuePtr> getField(StringAttr field);
  FailureOr<EvaluatorValuePtr> getField(StringRef field) {
    return getField(StringAttr::get(getContext(), field));
  }
 
  /// Get all the field names of the Object.
  ArrayAttr getFieldNames();
 
  // Finalize the evaluator value.
  LogicalResult finalizeImpl();
 
private:
  om::ClassLike cls;
  llvm::SmallDenseMap<StringAttr, EvaluatorValuePtr> fields;
};
 
/// A Basepath value.
class BasePathValue : public EvaluatorValue {
public:
  BasePathValue(MLIRContext *context);
 
  /// Create a path value representing a basepath.
  BasePathValue(om::PathAttr path, Location loc);
 
  om::PathAttr getPath() const;
 
  /// Set the basepath which this path is relative to.
  void setBasepath(const BasePathValue &basepath);
 
  /// Finalize the evaluator value.
  LogicalResult finalizeImpl() { return success(); }
 
  /// Implement LLVM RTTI.
  static bool classof(const EvaluatorValue *e) {
    return e->getKind() == Kind::BasePath;
  }
 
private:
  om::PathAttr path;
};
 
/// A Path value.
class PathValue : public EvaluatorValue {
public:
  /// Create a path value representing a regular path.
  PathValue(om::TargetKindAttr targetKind, om::PathAttr path, StringAttr module,
            StringAttr ref, StringAttr field, Location loc);
 
  static PathValue getEmptyPath(Location loc);
 
  om::TargetKindAttr getTargetKind() const { return targetKind; }
 
  om::PathAttr getPath() const { return path; }
 
  StringAttr getModule() const { return module; }
 
  StringAttr getRef() const { return ref; }
 
  StringAttr getField() const { return field; }
 
  StringAttr getAsString() const;
 
  void setBasepath(const BasePathValue &basepath);
 
  // Finalize the evaluator value.
  LogicalResult finalizeImpl() { return success(); }
 
  /// Implement LLVM RTTI.
  static bool classof(const EvaluatorValue *e) {
    return e->getKind() == Kind::Path;
  }
 
private:
  om::TargetKindAttr targetKind;
  om::PathAttr path;
  StringAttr module;
  StringAttr ref;
  StringAttr field;
};
 
} // namespace evaluator
 
using Object = evaluator::ObjectValue;
using EvaluatorValuePtr = evaluator::EvaluatorValuePtr;
 
SmallVector<EvaluatorValuePtr>
getEvaluatorValuesFromAttributes(MLIRContext *context,
                                 ArrayRef<Attribute> attributes);
 
/// An Evaluator, which is constructed with an IR module and can instantiate
/// Objects. Further refinement is expected.
class Evaluator {
public:
  /// Construct an Evaluator with an IR module.
  Evaluator(ModuleOp mod);
 
  /// Instantiate an Object with its class name and actual parameters.
  FailureOr<evaluator::EvaluatorValuePtr>
  instantiate(StringAttr className, ArrayRef<EvaluatorValuePtr> actualParams);
 
  /// Get the Module this Evaluator is built from.
  mlir::ModuleOp getModule();
 
  FailureOr<evaluator::EvaluatorValuePtr>
  getPartiallyEvaluatedValue(Type type, Location loc);
 
  using ActualParameters =
      SmallVectorImpl<std::shared_ptr<evaluator::EvaluatorValue>> *;
 
  using ObjectKey = std::pair<Value, ActualParameters>;
 
  /// Get the number of fully evaluated nodes tracked by this evaluator.
  uint64_t getFullyEvaluatedCount() const { return fullyEvaluatedCount; }
 
private:
  bool isFullyEvaluated(Value value, ActualParameters key) {
    return isFullyEvaluated({value, key});
  }
 
  bool isFullyEvaluated(ObjectKey key) {
    auto val = objects.lookup(key);
    return val && val->isFullyEvaluated();
  }
 
  /// Attach the evaluation counter to a newly created value.
  void attachCounter(evaluator::EvaluatorValuePtr &value) {
    if (value && !value->isFullyEvaluated())
      value->setFullyEvaluatedCounter(&fullyEvaluatedCount);
  }
 
  FailureOr<evaluator::EvaluatorValuePtr>
  instantiateImpl(StringAttr className,
                  ArrayRef<EvaluatorValuePtr> actualParams);
 
  FailureOr<EvaluatorValuePtr>
  getOrCreateValue(Value value, ActualParameters actualParams, Location loc);
  FailureOr<EvaluatorValuePtr>
  allocateObjectInstance(StringAttr clasName, ActualParameters actualParams);
 
  /// Evaluate a Value in a Class body according to the small expression grammar
  /// described in the rationale document. The actual parameters are the values
  /// supplied at the current instantiation of the Class being evaluated.
  FailureOr<EvaluatorValuePtr>
  evaluateValue(Value value, ActualParameters actualParams, Location loc);
 
  /// Evaluator dispatch functions for the small expression grammar.
  FailureOr<EvaluatorValuePtr> evaluateParameter(BlockArgument formalParam,
                                                 ActualParameters actualParams,
                                                 Location loc);
 
  FailureOr<EvaluatorValuePtr>
  evaluateConstant(ConstantOp op, ActualParameters actualParams, Location loc);
 
  /// Instantiate an Object with its class name and actual parameters.
  FailureOr<EvaluatorValuePtr>
  evaluateObjectInstance(StringAttr className, ActualParameters actualParams,
                         Location loc, ObjectKey instanceKey = {});
  FailureOr<EvaluatorValuePtr>
  evaluateObjectInstance(ObjectOp op, ActualParameters actualParams);
  FailureOr<EvaluatorValuePtr>
  evaluateElaboratedObject(ElaboratedObjectOp op, ActualParameters actualParams,
                           Location loc);
  FailureOr<EvaluatorValuePtr>
  evaluateObjectField(ObjectFieldOp op, ActualParameters actualParams,
                      Location loc);
  FailureOr<EvaluatorValuePtr> evaluateListCreate(ListCreateOp op,
                                                  ActualParameters actualParams,
                                                  Location loc);
  FailureOr<EvaluatorValuePtr> evaluateListConcat(ListConcatOp op,
                                                  ActualParameters actualParams,
                                                  Location loc);
  FailureOr<EvaluatorValuePtr>
  evaluateIntegerBinary(IntegerBinaryOp op, ActualParameters actualParams,
                        Location loc);
  FailureOr<EvaluatorValuePtr>
  evaluateStringConcat(StringConcatOp op, ActualParameters actualParams,
                       Location loc);
  FailureOr<EvaluatorValuePtr>
  evaluateBinaryEquality(BinaryEqualityOp op, ActualParameters actualParams,
                         Location loc);
  FailureOr<evaluator::EvaluatorValuePtr>
  evaluateBasePathCreate(FrozenBasePathCreateOp op,
                         ActualParameters actualParams, Location loc);
  FailureOr<evaluator::EvaluatorValuePtr>
  evaluatePathCreate(FrozenPathCreateOp op, ActualParameters actualParams,
                     Location loc);
  FailureOr<evaluator::EvaluatorValuePtr>
  evaluateEmptyPath(FrozenEmptyPathOp op, ActualParameters actualParams,
                    Location loc);
  FailureOr<evaluator::EvaluatorValuePtr>
  evaluateUnknownValue(UnknownValueOp op, Location loc);
 
  LogicalResult evaluatePropertyAssert(PropertyAssertOp op,
                                       ActualParameters actualParams);
 
  FailureOr<evaluator::EvaluatorValuePtr> createUnknownValue(Type type,
                                                             Location loc);
 
  FailureOr<ActualParameters>
  createParametersFromOperands(ValueRange range, ActualParameters actualParams,
                               Location loc);
 
  /// The symbol table for the IR module the Evaluator was constructed with.
  /// Used to look up class definitions.
  SymbolTable symbolTable;
 
  /// This uniquely stores vectors that represent parameters.
  SmallVector<
      std::unique_ptr<SmallVector<std::shared_ptr<evaluator::EvaluatorValue>>>>
      actualParametersBuffers;
 
  /// Worklists that track values which need to be fully evaluated.
  /// We use two worklists to detect cycles: process all items from one,
  /// and if any become fully evaluated, swap and continue.
  std::vector<ObjectKey> worklist;
  std::vector<ObjectKey> nextWorklist;
 
  /// A queue of pending property assertions to be evaluated after the worklist
  /// is fully drained. Each entry is a (PropertyAssertOp, ActualParameters)
  /// pair. Property assertions are deferred because their operands may be
  /// ReferenceValues that are not yet resolved when the class body is first
  /// processed.
  std::queue<std::pair<PropertyAssertOp, ActualParameters>> pendingAsserts;
 
  /// Evaluator value storage. Return an evaluator value for the given
  /// instantiation context (a pair of Value and parameters).
  DenseMap<ObjectKey, std::shared_ptr<evaluator::EvaluatorValue>> objects;
 
  /// Counter for fully evaluated nodes.
  uint64_t fullyEvaluatedCount = 0;
 
#ifndef NDEBUG
  /// Current nesting depth for debug output indentation.
  unsigned debugNesting = 0;
 
  /// RAII helper to increment/decrement debugNesting.
  struct DebugNesting {
    unsigned &depth;
    DebugNesting(unsigned &depth) : depth(depth) { ++depth; }
    ~DebugNesting() { --depth; }
  };
 
  raw_ostream &dbgs(unsigned extra = 0) {
    return llvm::dbgs().indent(debugNesting * 2 + extra * 2);
  }
 
  llvm::indent indent(unsigned extra = 0) {
    return llvm::indent(debugNesting, 2) + extra;
  }
#endif
};
 
/// Helper to enable printing objects in Diagnostics.
static inline mlir::Diagnostic &
operator<<(mlir::Diagnostic &diag,
           const evaluator::EvaluatorValue &evaluatorValue) {
  if (auto *attr = llvm::dyn_cast<evaluator::AttributeValue>(&evaluatorValue))
    diag << attr->getAttr();
  else if (auto *object =
               llvm::dyn_cast<evaluator::ObjectValue>(&evaluatorValue))
    diag << "Object(" << object->getType() << ")";
  else if (auto *list = llvm::dyn_cast<evaluator::ListValue>(&evaluatorValue))
    diag << "List(" << list->getType() << ")";
  else if (auto *ref =
               llvm::dyn_cast<evaluator::ReferenceValue>(&evaluatorValue))
    diag << "Reference(" << ref->getValueType() << ")";
  else if (llvm::isa<evaluator::BasePathValue>(&evaluatorValue))
    diag << "BasePath()";
  else if (llvm::isa<evaluator::PathValue>(&evaluatorValue))
    diag << "Path()";
  else
    assert(false && "unhandled evaluator value");
 
  // Add unknown marker if the value is unknown
  if (evaluatorValue.isUnknown())
    diag << " [unknown]";
  return diag;
}
 
/// Helper to enable printing objects in Diagnostics.
static inline mlir::Diagnostic &
operator<<(mlir::Diagnostic &diag, const EvaluatorValuePtr &evaluatorValue) {
  return diag << *evaluatorValue.get();
}
 
#ifndef NDEBUG
/// Helper to enable printing objects to raw_ostream (e.g., llvm::dbgs()).
/// Delegates to the Diagnostic overload via an intermediate string.
static inline llvm::raw_ostream &
operator<<(llvm::raw_ostream &os,
           const evaluator::EvaluatorValue &evaluatorValue) {
  std::string buf;
  llvm::raw_string_ostream ss(buf);
  mlir::Diagnostic diag(UnknownLoc::get(evaluatorValue.getContext()),
                        mlir::DiagnosticSeverity::Note);
  diag << evaluatorValue;
  ss << diag;
  return os << ss.str();
}
 
static inline llvm::raw_ostream &
operator<<(llvm::raw_ostream &os, const EvaluatorValuePtr &evaluatorValue) {
  if (evaluatorValue)
    return os << *evaluatorValue.get();
  return os << "<null>";
}
#endif // NDEBUG
 
} // namespace om
} // namespace circt
 
#endif // CIRCT_DIALECT_OM_EVALUATOR_EVALUATOR_H