MLIR: lib/Conversion/PDLToPDLInterp/PredicateTree.cpp File Reference (original) (raw)
#include "[PredicateTree.h](PredicateTree%5F8h%5Fsource.html)"#include "[RootOrdering.h](RootOrdering%5F8h%5Fsource.html)"#include "[mlir/Dialect/PDL/IR/PDL.h](mlir%5F2Dialect%5F2PDL%5F2IR%5F2PDL%5F8h%5Fsource.html)"#include "[mlir/Dialect/PDL/IR/PDLTypes.h](PDLTypes%5F8h%5Fsource.html)"#include "[mlir/Dialect/PDLInterp/IR/PDLInterp.h](PDLInterp%5F8h%5Fsource.html)"#include "[mlir/IR/BuiltinOps.h](BuiltinOps%5F8h%5Fsource.html)"#include "[mlir/Interfaces/InferTypeOpInterface.h](InferTypeOpInterface%5F8h%5Fsource.html)"#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.
| 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... | |
◆ DEBUG_TYPE
#define DEBUG_TYPE "pdl-predicate-tree"
◆ buildCostGraph()
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()
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()
◆ dependsOn()
| static bool dependsOn ( OrderedPredicate * a, OrderedPredicate * b ) | static |
|---|
◆ detectRoots()
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 |
|---|
◆ getAttributePredicates()
◆ getConstraintPredicates()
◆ getNonTreePredicates()
◆ getNumNonRangeValues()
| static unsigned getNumNonRangeValues ( ValueRange values) | static |
|---|
◆ getOperandTreePredicates()
◆ getOrCreateChild()
| std::unique_ptr<MatcherNode>& getOrCreateChild | ( | SwitchNode * | node, |
|---|---|---|---|
| OrderedPredicate * | predicate, | ||
| pdl::PatternOp | pattern | ||
| ) |
◆ getResultPredicates() [1/2]
◆ getResultPredicates() [2/2]
◆ getTreePredicates() [1/4]
◆ getTreePredicates() [2/4]
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]
◆ getTreePredicates() [4/4]
◆ getTypePredicates()
◆ insertExitNode()
| static void insertExitNode ( std::unique_ptr< MatcherNode > * root) | static |
|---|
◆ isSamePredicate()
| static bool isSamePredicate ( MatcherNode * node, OrderedPredicate * predicate ) | static |
|---|
◆ propagatePattern()
| static void propagatePattern ( std::unique_ptr< MatcherNode > & node, OrderedPredicateList & list, std::vector< OrderedPredicate * >::iterator current, std::vector< OrderedPredicate * >::iterator end ) | static |
|---|
◆ stableTopologicalSort()
template<typename Iterator , typename Compare >
| static void stableTopologicalSort ( Iterator begin, Iterator end, Compare cmp ) | static |
|---|
◆ 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()
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().