MLIR  16.0.0git
Macros | Functions
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/TypeSwitch.h"
#include "llvm/Support/Debug.h"
#include <queue>
+ Include dependency graph for PredicateTree.cpp:

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, Optional< unsigned > ignoreOperand=llvm::None)
 
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< ValuedetectRoots (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...
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "pdl-predicate-tree"

Definition at line 22 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 402 of file PredicateTree.cpp.

References mlir::pdl_to_pdl_interp::RootOrderingEntry::connector, mlir::pdl_to_pdl_interp::RootOrderingEntry::cost, mlir::detail::enumerate(), mlir::OperandRange::getType(), and value.

Referenced by buildPredicateList().

◆ buildPredicateList()

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

◆ comparePosDepth()

static bool comparePosDepth ( Position lhs,
Position rhs 
)
static

Compares the depths of two positions.

Definition at line 37 of file PredicateTree.cpp.

Referenced by getConstraintPredicates(), and getTreePredicates().

◆ 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 370 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 846 of file PredicateTree.cpp.

◆ getAttributePredicates()

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

◆ getConstraintPredicates()

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

◆ 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 326 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 42 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

◆ 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 791 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

◆ getResultPredicates() [2/2]

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

◆ getTreePredicates() [1/4]

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

◆ getTreePredicates() [2/4]

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

◆ getTreePredicates() [3/4]

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

◆ getTreePredicates() [4/4]

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

◆ getTypePredicates()

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

◆ 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 871 of file PredicateTree.cpp.

◆ 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 784 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 807 of file PredicateTree.cpp.

References getOrCreateChild(), and isSamePredicate().

◆ 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 512 of file PredicateTree.cpp.

Referenced by visitUpward().

◆ visitUpward()

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