PredicateTree.cpp File Reference

#include "PredicateTree.h"
#include "RootOrdering.h"
#include "mlir/Dialect/PDL/IR/PDL.h"
#include "mlir/Dialect/PDL/IR/PDLTypes.h"
#include "mlir/Dialect/PDLInterp/IR/PDLInterp.h"
#include "mlir/IR/BuiltinOps.h"
#include "mlir/Interfaces/InferTypeOpInterface.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/TypeSwitch.h"
#include "llvm/Support/Debug.h"
#include <queue>

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "pdl-predicate-tree"

Functions
static void	getTreePredicates (std::vector< PositionalPredicate > &predList, Value val, PredicateBuilder &builder, DenseMap< Value, Position * > &inputs, Position *pos)
	Collect the tree predicates anchored at the given value. More...
static bool	comparePosDepth (Position *lhs, Position *rhs)
	Compares the depths of two positions. More...
static unsigned	getNumNonRangeValues (ValueRange values)
	Returns the number of non-range elements within values. More...
static void	getTreePredicates (std::vector< PositionalPredicate > &predList, Value val, PredicateBuilder &builder, DenseMap< Value, Position * > &inputs, AttributePosition *pos)
static void	getOperandTreePredicates (std::vector< PositionalPredicate > &predList, Value val, PredicateBuilder &builder, DenseMap< Value, Position * > &inputs, Position *pos)
	Collect all of the predicates for the given operand position. More...
static void	getTreePredicates (std::vector< PositionalPredicate > &predList, Value val, PredicateBuilder &builder, DenseMap< Value, Position * > &inputs, OperationPosition *pos, std::optional< unsigned > ignoreOperand=std::nullopt)
static void	getTreePredicates (std::vector< PositionalPredicate > &predList, Value val, PredicateBuilder &builder, DenseMap< Value, Position * > &inputs, TypePosition *pos)
static void	getAttributePredicates (pdl::AttributeOp op, std::vector< PositionalPredicate > &predList, PredicateBuilder &builder, DenseMap< Value, Position * > &inputs)
static void	getConstraintPredicates (pdl::ApplyNativeConstraintOp op, std::vector< PositionalPredicate > &predList, PredicateBuilder &builder, DenseMap< Value, Position * > &inputs)
static void	getResultPredicates (pdl::ResultOp op, std::vector< PositionalPredicate > &predList, PredicateBuilder &builder, DenseMap< Value, Position * > &inputs)
static void	getResultPredicates (pdl::ResultsOp op, std::vector< PositionalPredicate > &predList, PredicateBuilder &builder, DenseMap< Value, Position * > &inputs)
static void	getTypePredicates (Value typeValue, function_ref< Attribute()> typeAttrFn, PredicateBuilder &builder, DenseMap< Value, Position * > &inputs)
static void	getNonTreePredicates (pdl::PatternOp pattern, std::vector< PositionalPredicate > &predList, PredicateBuilder &builder, DenseMap< Value, Position * > &inputs)
	Collect all of the predicates that cannot be determined via walking the tree. More...
static SmallVector< Value >	detectRoots (pdl::PatternOp pattern)
	Given a pattern, determines the set of roots present in this pattern. More...
static void	buildCostGraph (ArrayRef< Value > roots, RootOrderingGraph &graph, ParentMaps &parentMaps)
	Given a list of candidate roots, builds the cost graph for connecting them. More...
static bool	useOperandGroup (pdl::OperationOp op, unsigned index)
	Returns true if the operand at the given index needs to be queried using an operand group, i.e., if it is variadic itself or follows a variadic operand. More...
static void	visitUpward (std::vector< PositionalPredicate > &predList, OpIndex opIndex, PredicateBuilder &builder, DenseMap< Value, Position * > &valueToPosition, Position *&pos, unsigned rootID)
	Visit a node during upward traversal. More...
static Value	buildPredicateList (pdl::PatternOp pattern, PredicateBuilder &builder, std::vector< PositionalPredicate > &predList, DenseMap< Value, Position * > &valueToPosition)
	Given a pattern operation, build the set of matcher predicates necessary to match this pattern. More...
static bool	isSamePredicate (MatcherNode *node, OrderedPredicate *predicate)
	Returns true if the given matcher refers to the same predicate as the given ordered predicate. More...
std::unique_ptr< MatcherNode > &	getOrCreateChild (SwitchNode *node, OrderedPredicate *predicate, pdl::PatternOp pattern)
	Get or insert a child matcher for the given parent switch node, given a predicate and parent pattern. More...
static void	propagatePattern (std::unique_ptr< MatcherNode > &node, OrderedPredicateList &list, std::vector< OrderedPredicate * >::iterator current, std::vector< OrderedPredicate * >::iterator end)
	Build the matcher CFG by "pushing" patterns through by sorted predicate order. More...
static void	foldSwitchToBool (std::unique_ptr< MatcherNode > &node)
	Fold any switch nodes nested under node to boolean nodes when possible. More...
static void	insertExitNode (std::unique_ptr< MatcherNode > *root)
	Insert an exit node at the end of the failure path of the root. More...
template<typename Iterator , typename Compare >
static void	stableTopologicalSort (Iterator begin, Iterator end, Compare cmp)
	Sorts the range begin/end with the partial order given by cmp. More...
static bool	dependsOn (OrderedPredicate *a, OrderedPredicate *b)
	Returns true if 'b' depends on a result of 'a'. More...

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "pdl-predicate-tree"

Definition at line 23 of file PredicateTree.cpp.

Function Documentation

buildCostGraph()

static void buildCostGraph ( ArrayRef< Value >  roots, RootOrderingGraph &  graph, ParentMaps &  parentMaps  )

static

Given a list of candidate roots, builds the cost graph for connecting them.

The graph is formed by traversing the DAG of operations starting from each root and marking the depth of each connector value (operand). Then we join the candidate roots based on the common connector values, taking the one with the minimum depth. Along the way, we compute, for each candidate root, a mapping from each operation (in the DAG underneath this root) to its parent operation and the corresponding operand index.

Definition at line 422 of file PredicateTree.cpp.

References mlir::detail::enumerate(), and mlir::getType().

Referenced by buildPredicateList().

buildPredicateList()

static Value buildPredicateList ( pdl::PatternOp  pattern, PredicateBuilder &  builder, std::vector< PositionalPredicate > &  predList, DenseMap< Value, Position * > &  valueToPosition  )

static

Given a pattern operation, build the set of matcher predicates necessary to match this pattern.

Definition at line 614 of file PredicateTree.cpp.

References buildCostGraph(), mlir::pdl_to_pdl_interp::RootOrderingEntry::connector, mlir::pdl_to_pdl_interp::RootOrderingEntry::cost, detectRoots(), mlir::detail::enumerate(), mlir::Value::getLoc(), getNonTreePredicates(), mlir::pdl_to_pdl_interp::PredicateBuilder::getRoot(), getTreePredicates(), mlir::pdl_to_pdl_interp::OptimalBranching::preOrderTraversal(), mlir::pdl_to_pdl_interp::OptimalBranching::solve(), and visitUpward().

Referenced by mlir::pdl_to_pdl_interp::MatcherNode::generateMatcherTree().

comparePosDepth()

static bool comparePosDepth ( Position *  lhs, Position *  rhs  )

static

Compares the depths of two positions.

Definition at line 38 of file PredicateTree.cpp.

References mlir::pdl_to_pdl_interp::Position::getOperationDepth().

Referenced by getConstraintPredicates(), and getTreePredicates().

dependsOn()

static bool dependsOn ( OrderedPredicate *  a, OrderedPredicate *  b  )

static

Returns true if 'b' depends on a result of 'a'.

Definition at line 920 of file PredicateTree.cpp.

Referenced by mlir::pdl_to_pdl_interp::MatcherNode::generateMatcherTree().

detectRoots()

static SmallVector<Value> detectRoots ( pdl::PatternOp  pattern )

static

Given a pattern, determines the set of roots present in this pattern.

These are the operations whose results are not consumed by other operations.

Definition at line 390 of file PredicateTree.cpp.

Referenced by buildPredicateList().

foldSwitchToBool()

static void foldSwitchToBool ( std::unique_ptr< MatcherNode > &  node )

static

Fold any switch nodes nested under node to boolean nodes when possible.

node is updated in-place if it is a switch.

Definition at line 867 of file PredicateTree.cpp.

Referenced by mlir::pdl_to_pdl_interp::MatcherNode::generateMatcherTree().

getAttributePredicates()

static void getAttributePredicates ( pdl::AttributeOp  op, std::vector< PositionalPredicate > &  predList, PredicateBuilder &  builder, DenseMap< Value, Position * > &  inputs  )

static

Definition at line 251 of file PredicateTree.cpp.

References mlir::pdl_to_pdl_interp::PredicateBuilder::getAttributeLiteral().

Referenced by getNonTreePredicates().

getConstraintPredicates()

static void getConstraintPredicates ( pdl::ApplyNativeConstraintOp  op, std::vector< PositionalPredicate > &  predList, PredicateBuilder &  builder, DenseMap< Value, Position * > &  inputs  )

static

Definition at line 263 of file PredicateTree.cpp.

References comparePosDepth(), mlir::detail::enumerate(), mlir::pdl_to_pdl_interp::PredicateBuilder::getConstraint(), mlir::pdl_to_pdl_interp::PredicateBuilder::getConstraintPosition(), mlir::pdl_to_pdl_interp::PredicateBuilder::getEqualTo(), and mlir::ResultRange::getTypes().

Referenced by getNonTreePredicates().

getNonTreePredicates()

static void getNonTreePredicates ( pdl::PatternOp  pattern, std::vector< PositionalPredicate > &  predList, PredicateBuilder &  builder, DenseMap< Value, Position * > &  inputs  )

static

Collect all of the predicates that cannot be determined via walking the tree.

Definition at line 346 of file PredicateTree.cpp.

References getAttributePredicates(), getConstraintPredicates(), getResultPredicates(), and getTypePredicates().

Referenced by buildPredicateList().

getNumNonRangeValues()

static unsigned getNumNonRangeValues ( ValueRange  values )

static

Returns the number of non-range elements within values.

Definition at line 43 of file PredicateTree.cpp.

References mlir::ValueRange::getTypes().

Referenced by getTreePredicates().

getOperandTreePredicates()

static void getOperandTreePredicates ( std::vector< PositionalPredicate > &  predList, Value  val, PredicateBuilder &  builder, DenseMap< Value, Position * > &  inputs, Position *  pos  )

static

Collect all of the predicates for the given operand position.

Definition at line 65 of file PredicateTree.cpp.

References mlir::Value::getDefiningOp(), mlir::pdl_to_pdl_interp::PredicateBuilder::getEqualTo(), mlir::pdl_to_pdl_interp::PredicateBuilder::getIsNotNull(), mlir::pdl_to_pdl_interp::PredicateBuilder::getOperandDefiningOp(), mlir::pdl_to_pdl_interp::PredicateBuilder::getResult(), mlir::pdl_to_pdl_interp::PredicateBuilder::getResultGroup(), getTreePredicates(), mlir::Value::getType(), and mlir::pdl_to_pdl_interp::PredicateBuilder::getType().

Referenced by getTreePredicates().

getOrCreateChild()

std::unique_ptr<MatcherNode>& getOrCreateChild	(	SwitchNode *	node,
		OrderedPredicate *	predicate,
		pdl::PatternOp	pattern
	)

Get or insert a child matcher for the given parent switch node, given a predicate and parent pattern.

Definition at line 812 of file PredicateTree.cpp.

References mlir::pdl_to_pdl_interp::SwitchNode::getChildren(), and isSamePredicate().

Referenced by propagatePattern().

getResultPredicates() [1/2]

static void getResultPredicates ( pdl::ResultOp  op, std::vector< PositionalPredicate > &  predList, PredicateBuilder &  builder, DenseMap< Value, Position * > &  inputs  )

static

Definition at line 300 of file PredicateTree.cpp.

References mlir::pdl_to_pdl_interp::PredicateBuilder::getIsNotNull(), and mlir::pdl_to_pdl_interp::PredicateBuilder::getResult().

Referenced by getNonTreePredicates().

getResultPredicates() [2/2]

static void getResultPredicates ( pdl::ResultsOp  op, std::vector< PositionalPredicate > &  predList, PredicateBuilder &  builder, DenseMap< Value, Position * > &  inputs  )

static

Definition at line 314 of file PredicateTree.cpp.

References mlir::pdl_to_pdl_interp::PredicateBuilder::getIsNotNull(), and mlir::pdl_to_pdl_interp::PredicateBuilder::getResultGroup().

getTreePredicates() [1/4]

static void getTreePredicates ( std::vector< PositionalPredicate > &  predList, Value  val, PredicateBuilder &  builder, DenseMap< Value, Position * > &  inputs, AttributePosition *  pos  )

static

Definition at line 48 of file PredicateTree.cpp.

References mlir::pdl_to_pdl_interp::PredicateBuilder::getAttributeConstraint(), mlir::Value::getDefiningOp(), mlir::pdl_to_pdl_interp::PredicateBuilder::getIsNotNull(), getTreePredicates(), mlir::Value::getType(), and mlir::pdl_to_pdl_interp::PredicateBuilder::getType().

getTreePredicates() [2/4]

static void getTreePredicates ( std::vector< PositionalPredicate > &  predList, Value  val, PredicateBuilder &  builder, DenseMap< Value, Position * > &  inputs, OperationPosition *  pos, std::optional< unsigned >  ignoreOperand = std::nullopt  )

static

Operands.

Results.

Definition at line 112 of file PredicateTree.cpp.

References mlir::detail::enumerate(), mlir::pdl_to_pdl_interp::PredicateBuilder::getAllOperands(), mlir::pdl_to_pdl_interp::PredicateBuilder::getAllResults(), mlir::pdl_to_pdl_interp::PredicateBuilder::getAttribute(), mlir::Value::getDefiningOp(), mlir::pdl_to_pdl_interp::PredicateBuilder::getIsNotNull(), getNumNonRangeValues(), mlir::pdl_to_pdl_interp::PredicateBuilder::getOperand(), mlir::pdl_to_pdl_interp::PredicateBuilder::getOperandCount(), mlir::pdl_to_pdl_interp::PredicateBuilder::getOperandCountAtLeast(), mlir::pdl_to_pdl_interp::PredicateBuilder::getOperandGroup(), mlir::pdl_to_pdl_interp::PredicateBuilder::getOperationName(), mlir::pdl_to_pdl_interp::PredicateBuilder::getResult(), mlir::pdl_to_pdl_interp::PredicateBuilder::getResultCount(), mlir::pdl_to_pdl_interp::PredicateBuilder::getResultCountAtLeast(), mlir::pdl_to_pdl_interp::PredicateBuilder::getResultGroup(), getTreePredicates(), mlir::Value::getType(), mlir::OperandRange::getType(), mlir::pdl_to_pdl_interp::PredicateBuilder::getType(), mlir::pdl_to_pdl_interp::PredicateBase< ConcreteT, BaseT, Key, Kind >::getValue(), mlir::pdl_to_pdl_interp::OperationPosition::isOperandDefiningOp(), and mlir::pdl_to_pdl_interp::OperationPosition::isRoot().

getTreePredicates() [3/4]

static void getTreePredicates ( std::vector< PositionalPredicate > &  predList, Value  val, PredicateBuilder &  builder, DenseMap< Value, Position * > &  inputs, Position *  pos  )

static

Collect the tree predicates anchored at the given value.

Definition at line 222 of file PredicateTree.cpp.

References comparePosDepth(), mlir::Value::getDefiningOp(), mlir::pdl_to_pdl_interp::PredicateBuilder::getEqualTo(), and getOperandTreePredicates().

Referenced by buildPredicateList(), getOperandTreePredicates(), getTreePredicates(), and visitUpward().

getTreePredicates() [4/4]

static void getTreePredicates ( std::vector< PositionalPredicate > &  predList, Value  val, PredicateBuilder &  builder, DenseMap< Value, Position * > &  inputs, TypePosition *  pos  )

static

Definition at line 207 of file PredicateTree.cpp.

References mlir::Value::getDefiningOp(), and mlir::pdl_to_pdl_interp::PredicateBuilder::getTypeConstraint().

getTypePredicates()

static void getTypePredicates ( Value  typeValue, function_ref< Attribute()>  typeAttrFn, PredicateBuilder &  builder, DenseMap< Value, Position * > &  inputs  )

static

Definition at line 331 of file PredicateTree.cpp.

References mlir::pdl_to_pdl_interp::PredicateBuilder::getTypeLiteral().

Referenced by getNonTreePredicates().

insertExitNode()

static void insertExitNode ( std::unique_ptr< MatcherNode > *  root )

static

Insert an exit node at the end of the failure path of the root.

Definition at line 892 of file PredicateTree.cpp.

Referenced by mlir::pdl_to_pdl_interp::MatcherNode::generateMatcherTree().

isSamePredicate()

static bool isSamePredicate ( MatcherNode *  node, OrderedPredicate *  predicate  )

static

Returns true if the given matcher refers to the same predicate as the given ordered predicate.

This means that the position and questions of the two match.

Definition at line 805 of file PredicateTree.cpp.

References mlir::pdl_to_pdl_interp::MatcherNode::getPosition(), and mlir::pdl_to_pdl_interp::MatcherNode::getQuestion().

Referenced by getOrCreateChild(), and propagatePattern().

propagatePattern()

static void propagatePattern ( std::unique_ptr< MatcherNode > &  node, OrderedPredicateList &  list, std::vector< OrderedPredicate * >::iterator  current, std::vector< OrderedPredicate * >::iterator  end  )

static

Build the matcher CFG by "pushing" patterns through by sorted predicate order.

A pattern will traverse as far as possible using common predicates and then either diverge from the CFG or reach the end of a branch and start creating new nodes.

Definition at line 828 of file PredicateTree.cpp.

References getOrCreateChild(), and isSamePredicate().

Referenced by mlir::pdl_to_pdl_interp::MatcherNode::generateMatcherTree().

stableTopologicalSort()

template<typename Iterator , typename Compare >

static void stableTopologicalSort ( Iterator  begin, Iterator  end, Compare  cmp  )

static

Sorts the range begin/end with the partial order given by cmp.

Definition at line 900 of file PredicateTree.cpp.

Referenced by mlir::pdl_to_pdl_interp::MatcherNode::generateMatcherTree().

useOperandGroup()

static bool useOperandGroup ( pdl::OperationOp  op, unsigned  index  )

static

Returns true if the operand at the given index needs to be queried using an operand group, i.e., if it is variadic itself or follows a variadic operand.

Definition at line 533 of file PredicateTree.cpp.

References mlir::getType().

Referenced by visitUpward().

visitUpward()

static void visitUpward ( std::vector< PositionalPredicate > &  predList, OpIndex  opIndex, PredicateBuilder &  builder, DenseMap< Value, Position * > &  valueToPosition, Position *&  pos, unsigned  rootID  )

static

Visit a node during upward traversal.

Definition at line 543 of file PredicateTree.cpp.

References mlir::pdl_to_pdl_interp::PredicateBuilder::getAllOperands(), mlir::pdl_to_pdl_interp::PredicateBuilder::getAllResults(), mlir::Value::getDefiningOp(), mlir::pdl_to_pdl_interp::PredicateBuilder::getEqualTo(), mlir::pdl_to_pdl_interp::PredicateBuilder::getForEach(), mlir::pdl_to_pdl_interp::PredicateBuilder::getOperand(), mlir::pdl_to_pdl_interp::PredicateBuilder::getOperandGroup(), mlir::pdl_to_pdl_interp::PredicateBuilder::getPassthroughOp(), mlir::pdl_to_pdl_interp::PredicateBuilder::getResult(), mlir::pdl_to_pdl_interp::PredicateBuilder::getResultGroup(), getTreePredicates(), mlir::Value::getType(), mlir::pdl_to_pdl_interp::PredicateBuilder::getUsers(), and useOperandGroup().

Referenced by buildPredicateList().