PredicateTree.h

Go to the documentation of this file.

//===- PredicateTree.h - Predicate tree node definitions --------*- C++ -*-===//
//
// 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 definitions for nodes of a tree structure for representing
// the general control flow within a pattern match.
//
//===----------------------------------------------------------------------===//

#ifndef MLIR_LIB_CONVERSION_PDLTOPDLINTERP_PREDICATETREE_H_
#define MLIR_LIB_CONVERSION_PDLTOPDLINTERP_PREDICATETREE_H_

#include "Predicate.h"
#include "mlir/Dialect/PDL/IR/PDLOps.h"
#include "llvm/ADT/MapVector.h"

namespace mlir {
class ModuleOp;

namespace pdl_to_pdl_interp {

class MatcherNode;

/// A PositionalPredicate is a predicate that is associated with a specific
/// positional value.
struct PositionalPredicate {
  PositionalPredicate(Position *pos,
                      const PredicateBuilder::Predicate &predicate)
      : position(pos), question(predicate.first), answer(predicate.second) {}

  /// The position the predicate is applied to.
  Position *position;

  /// The question that the predicate applies.
  Qualifier *question;

  /// The expected answer of the predicate.
  Qualifier *answer;
};

//===----------------------------------------------------------------------===//
// MatcherNode
//===----------------------------------------------------------------------===//

/// This class represents the base of a predicate matcher node.
class MatcherNode {
public:
  virtual ~MatcherNode() = default;

  /// Given a module containing PDL pattern operations, generate a matcher tree
  /// using the patterns within the given module and return the root matcher
  /// node. `valueToPosition` is a map that is populated with the original
  /// pdl values and their corresponding positions in the matcher tree.
  static std::unique_ptr<MatcherNode>
  generateMatcherTree(ModuleOp module, PredicateBuilder &builder,
                      DenseMap<Value, Position *> &valueToPosition);

  /// Returns the position on which the question predicate should be checked.
  Position *getPosition() const { return position; }

  /// Returns the predicate checked on this node.
  Qualifier *getQuestion() const { return question; }

  /// Returns the node that should be visited if this, or a subsequent node
  /// fails.
  std::unique_ptr<MatcherNode> &getFailureNode() { return failureNode; }

  /// Sets the node that should be visited if this, or a subsequent node fails.
  void setFailureNode(std::unique_ptr<MatcherNode> node) {
    failureNode = std::move(node);
  }

  /// Returns the unique type ID of this matcher instance. This should not be
  /// used directly, and is provided to support type casting.
  TypeID getMatcherTypeID() const { return matcherTypeID; }

protected:
  MatcherNode(TypeID matcherTypeID, Position *position = nullptr,
              Qualifier *question = nullptr,
              std::unique_ptr<MatcherNode> failureNode = nullptr);

private:
  /// The position on which the predicate should be checked.
  Position *position;

  /// The predicate that is checked on the given position.
  Qualifier *question;

  /// The node to visit if this node fails.
  std::unique_ptr<MatcherNode> failureNode;

  /// An owning store for the failure node if it is owned by this node.
  std::unique_ptr<MatcherNode> failureNodeStorage;

  /// A unique identifier for the derived matcher node, used for type casting.
  TypeID matcherTypeID;
};

//===----------------------------------------------------------------------===//
// BoolNode

/// A BoolNode denotes a question with a boolean-like result. These nodes branch
/// to a single node on a successful result, otherwise defaulting to the failure
/// node.
struct BoolNode : public MatcherNode {
  BoolNode(Position *position, Qualifier *question, Qualifier *answer,
           std::unique_ptr<MatcherNode> successNode,
           std::unique_ptr<MatcherNode> failureNode = nullptr);

  /// Returns if the given matcher node is an instance of this class, used to
  /// support type casting.
  static bool classof(const MatcherNode *node) {
    return node->getMatcherTypeID() == TypeID::get<BoolNode>();
  }

  /// Returns the expected answer of this boolean node.
  Qualifier *getAnswer() const { return answer; }

  /// Returns the node that should be visited on success.
  std::unique_ptr<MatcherNode> &getSuccessNode() { return successNode; }

private:
  /// The expected answer of this boolean node.
  Qualifier *answer;

  /// The next node if this node succeeds. Otherwise, go to the failure node.
  std::unique_ptr<MatcherNode> successNode;
};

//===----------------------------------------------------------------------===//
// ExitNode

/// An ExitNode is a special sentinel node that denotes the end of matcher.
struct ExitNode : public MatcherNode {
  ExitNode() : MatcherNode(TypeID::get<ExitNode>()) {}

  /// Returns if the given matcher node is an instance of this class, used to
  /// support type casting.
  static bool classof(const MatcherNode *node) {
    return node->getMatcherTypeID() == TypeID::get<ExitNode>();
  }
};

//===----------------------------------------------------------------------===//
// SuccessNode

/// A SuccessNode denotes that a given high level pattern has successfully been
/// matched. This does not terminate the matcher, as there may be multiple
/// successful matches.
struct SuccessNode : public MatcherNode {
  explicit SuccessNode(pdl::PatternOp pattern, Value root,
                       std::unique_ptr<MatcherNode> failureNode);

  /// Returns if the given matcher node is an instance of this class, used to
  /// support type casting.
  static bool classof(const MatcherNode *node) {
    return node->getMatcherTypeID() == TypeID::get<SuccessNode>();
  }

  /// Return the high level pattern operation that is matched with this node.
  pdl::PatternOp getPattern() const { return pattern; }

  /// Return the chosen root of the pattern.
  Value getRoot() const { return root; }

private:
  /// The high level pattern operation that was successfully matched with this
  /// node.
  pdl::PatternOp pattern;

  /// The chosen root of the pattern.
  Value root;
};

//===----------------------------------------------------------------------===//
// SwitchNode

/// A SwitchNode denotes a question with multiple potential results. These nodes
/// branch to a specific node based on the result of the question.
struct SwitchNode : public MatcherNode {
  SwitchNode(Position *position, Qualifier *question);

  /// Returns if the given matcher node is an instance of this class, used to
  /// support type casting.
  static bool classof(const MatcherNode *node) {
    return node->getMatcherTypeID() == TypeID::get<SwitchNode>();
  }

  /// Returns the children of this switch node. The children are contained
  /// within a mapping between the various case answers to destination matcher
  /// nodes.
  using ChildMapT = llvm::MapVector<Qualifier *, std::unique_ptr<MatcherNode>>;
  ChildMapT &getChildren() { return children; }

  /// Returns the child at the given index.
  std::pair<Qualifier *, std::unique_ptr<MatcherNode>> &getChild(unsigned i) {
    assert(i < children.size() && "invalid child index");
    return *std::next(children.begin(), i);
  }

private:
  /// Switch predicate "answers" select the child. Answers that are not found
  /// default to the failure node.
  ChildMapT children;
};

} // namespace pdl_to_pdl_interp
} // namespace mlir

#endif // MLIR_CONVERSION_PDLTOPDLINTERP_PREDICATETREE_H_