1//===- PredicateTree.cpp - Predicate tree merging -------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "PredicateTree.h"
10#include "RootOrdering.h"
11
12#include "mlir/Dialect/PDL/IR/PDLTypes.h"
13#include "mlir/IR/BuiltinOps.h"
14#include "llvm/ADT/MapVector.h"
15#include "llvm/ADT/SmallPtrSet.h"
16#include "llvm/ADT/TypeSwitch.h"
17#include "llvm/Support/Debug.h"
18#include "llvm/Support/DebugLog.h"
19#include <queue>
20
21#define DEBUG_TYPE "pdl-predicate-tree"
22
23using namespace mlir;
24using namespace mlir::pdl_to_pdl_interp;
25
26//===----------------------------------------------------------------------===//
27// Predicate List Building
28//===----------------------------------------------------------------------===//
29
30static void getTreePredicates(std::vector<PositionalPredicate> &predList,
31 Value val, PredicateBuilder &builder,
32 DenseMap<Value, Position *> &inputs,
33 Position *pos);
34
35/// Compares the depths of two positions.
36static bool comparePosDepth(Position *lhs, Position *rhs) {
37 return lhs->getOperationDepth() < rhs->getOperationDepth();
38}
39
40/// Returns the number of non-range elements within `values`.
41static unsigned getNumNonRangeValues(ValueRange values) {
42 return llvm::count_if(Range: values.getTypes(),
43 P: [](Type type) { return !isa<pdl::RangeType>(Val: type); });
44}
45
46static void getTreePredicates(std::vector<PositionalPredicate> &predList,
47 Value val, PredicateBuilder &builder,
48 DenseMap<Value, Position *> &inputs,
49 AttributePosition *pos) {
50 assert(isa<pdl::AttributeType>(val.getType()) && "expected attribute type");
51 predList.emplace_back(args&: pos, args: builder.getIsNotNull());
52
53 if (auto attr = val.getDefiningOp<pdl::AttributeOp>()) {
54 // If the attribute has a type or value, add a constraint.
55 if (Value type = attr.getValueType())
56 getTreePredicates(predList, val: type, builder, inputs, pos: builder.getType(p: pos));
57 else if (Attribute value = attr.getValueAttr())
58 predList.emplace_back(args&: pos, args: builder.getAttributeConstraint(attr: value));
59 }
60}
61
62/// Collect all of the predicates for the given operand position.
63static void getOperandTreePredicates(std::vector<PositionalPredicate> &predList,
64 Value val, PredicateBuilder &builder,
65 DenseMap<Value, Position *> &inputs,
66 Position *pos) {
67 Type valueType = val.getType();
68 bool isVariadic = isa<pdl::RangeType>(Val: valueType);
69
70 // If this is a typed operand, add a type constraint.
71 TypeSwitch<Operation *>(val.getDefiningOp())
72 .Case<pdl::OperandOp, pdl::OperandsOp>(caseFn: [&](auto op) {
73 // Prevent traversal into a null value if the operand has a proper
74 // index.
75 if (std::is_same<pdl::OperandOp, decltype(op)>::value ||
76 cast<OperandGroupPosition>(Val: pos)->getOperandGroupNumber())
77 predList.emplace_back(args&: pos, args: builder.getIsNotNull());
78
79 if (Value type = op.getValueType())
80 getTreePredicates(predList, val: type, builder, inputs,
81 pos: builder.getType(p: pos));
82 })
83 .Case<pdl::ResultOp, pdl::ResultsOp>(caseFn: [&](auto op) {
84 std::optional<unsigned> index = op.getIndex();
85
86 // Prevent traversal into a null value if the result has a proper index.
87 if (index)
88 predList.emplace_back(args&: pos, args: builder.getIsNotNull());
89
90 // Get the parent operation of this operand.
91 OperationPosition *parentPos = builder.getOperandDefiningOp(p: pos);
92 predList.emplace_back(args&: parentPos, args: builder.getIsNotNull());
93
94 // Ensure that the operands match the corresponding results of the
95 // parent operation.
96 Position *resultPos = nullptr;
97 if (std::is_same<pdl::ResultOp, decltype(op)>::value)
98 resultPos = builder.getResult(p: parentPos, result: *index);
99 else
100 resultPos = builder.getResultGroup(p: parentPos, group: index, isVariadic);
101 predList.emplace_back(args&: resultPos, args: builder.getEqualTo(pos));
102
103 // Collect the predicates of the parent operation.
104 getTreePredicates(predList, op.getParent(), builder, inputs,
105 (Position *)parentPos);
106 });
107}
108
109static void
110getTreePredicates(std::vector<PositionalPredicate> &predList, Value val,
111 PredicateBuilder &builder,
112 DenseMap<Value, Position *> &inputs, OperationPosition *pos,
113 std::optional<unsigned> ignoreOperand = std::nullopt) {
114 assert(isa<pdl::OperationType>(val.getType()) && "expected operation");
115 pdl::OperationOp op = cast<pdl::OperationOp>(Val: val.getDefiningOp());
116 OperationPosition *opPos = cast<OperationPosition>(Val: pos);
117
118 // Ensure getDefiningOp returns a non-null operation.
119 if (!opPos->isRoot())
120 predList.emplace_back(args&: pos, args: builder.getIsNotNull());
121
122 // Check that this is the correct root operation.
123 if (std::optional<StringRef> opName = op.getOpName())
124 predList.emplace_back(args&: pos, args: builder.getOperationName(name: *opName));
125
126 // Check that the operation has the proper number of operands. If there are
127 // any variable length operands, we check a minimum instead of an exact count.
128 OperandRange operands = op.getOperandValues();
129 unsigned minOperands = getNumNonRangeValues(values: operands);
130 if (minOperands != operands.size()) {
131 if (minOperands)
132 predList.emplace_back(args&: pos, args: builder.getOperandCountAtLeast(count: minOperands));
133 } else {
134 predList.emplace_back(args&: pos, args: builder.getOperandCount(count: minOperands));
135 }
136
137 // Check that the operation has the proper number of results. If there are
138 // any variable length results, we check a minimum instead of an exact count.
139 OperandRange types = op.getTypeValues();
140 unsigned minResults = getNumNonRangeValues(values: types);
141 if (minResults == types.size())
142 predList.emplace_back(args&: pos, args: builder.getResultCount(count: types.size()));
143 else if (minResults)
144 predList.emplace_back(args&: pos, args: builder.getResultCountAtLeast(count: minResults));
145
146 // Recurse into any attributes, operands, or results.
147 for (auto [attrName, attr] :
148 llvm::zip(t: op.getAttributeValueNames(), u: op.getAttributeValues())) {
149 getTreePredicates(
150 predList, val: attr, builder, inputs,
151 pos: builder.getAttribute(p: opPos, name: cast<StringAttr>(Val: attrName).getValue()));
152 }
153
154 // Process the operands and results of the operation. For all values up to
155 // the first variable length value, we use the concrete operand/result
156 // number. After that, we use the "group" given that we can't know the
157 // concrete indices until runtime. If there is only one variadic operand
158 // group, we treat it as all of the operands/results of the operation.
159 /// Operands.
160 if (operands.size() == 1 && isa<pdl::RangeType>(Val: operands[0].getType())) {
161 // Ignore the operands if we are performing an upward traversal (in that
162 // case, they have already been visited).
163 if (opPos->isRoot() || opPos->isOperandDefiningOp())
164 getTreePredicates(predList, val: operands.front(), builder, inputs,
165 pos: builder.getAllOperands(p: opPos));
166 } else {
167 bool foundVariableLength = false;
168 for (const auto &operandIt : llvm::enumerate(First&: operands)) {
169 bool isVariadic = isa<pdl::RangeType>(Val: operandIt.value().getType());
170 foundVariableLength |= isVariadic;
171
172 // Ignore the specified operand, usually because this position was
173 // visited in an upward traversal via an iterative choice.
174 if (ignoreOperand == operandIt.index())
175 continue;
176
177 Position *pos =
178 foundVariableLength
179 ? builder.getOperandGroup(p: opPos, group: operandIt.index(), isVariadic)
180 : builder.getOperand(p: opPos, operand: operandIt.index());
181 getTreePredicates(predList, val: operandIt.value(), builder, inputs, pos);
182 }
183 }
184 /// Results.
185 if (types.size() == 1 && isa<pdl::RangeType>(Val: types[0].getType())) {
186 getTreePredicates(predList, val: types.front(), builder, inputs,
187 pos: builder.getType(p: builder.getAllResults(p: opPos)));
188 return;
189 }
190
191 bool foundVariableLength = false;
192 for (auto [idx, typeValue] : llvm::enumerate(First&: types)) {
193 bool isVariadic = isa<pdl::RangeType>(Val: typeValue.getType());
194 foundVariableLength |= isVariadic;
195
196 auto *resultPos = foundVariableLength
197 ? builder.getResultGroup(p: pos, group: idx, isVariadic)
198 : builder.getResult(p: pos, result: idx);
199 predList.emplace_back(args&: resultPos, args: builder.getIsNotNull());
200 getTreePredicates(predList, val: typeValue, builder, inputs,
201 pos: builder.getType(p: resultPos));
202 }
203}
204
205static void getTreePredicates(std::vector<PositionalPredicate> &predList,
206 Value val, PredicateBuilder &builder,
207 DenseMap<Value, Position *> &inputs,
208 TypePosition *pos) {
209 // Check for a constraint on a constant type.
210 if (pdl::TypeOp typeOp = val.getDefiningOp<pdl::TypeOp>()) {
211 if (Attribute type = typeOp.getConstantTypeAttr())
212 predList.emplace_back(args&: pos, args: builder.getTypeConstraint(type));
213 } else if (pdl::TypesOp typeOp = val.getDefiningOp<pdl::TypesOp>()) {
214 if (Attribute typeAttr = typeOp.getConstantTypesAttr())
215 predList.emplace_back(args&: pos, args: builder.getTypeConstraint(type: typeAttr));
216 }
217}
218
219/// Collect the tree predicates anchored at the given value.
220static void getTreePredicates(std::vector<PositionalPredicate> &predList,
221 Value val, PredicateBuilder &builder,
222 DenseMap<Value, Position *> &inputs,
223 Position *pos) {
224 // Make sure this input value is accessible to the rewrite.
225 auto it = inputs.try_emplace(Key: val, Args&: pos);
226 if (!it.second) {
227 // If this is an input value that has been visited in the tree, add a
228 // constraint to ensure that both instances refer to the same value.
229 if (isa<pdl::AttributeOp, pdl::OperandOp, pdl::OperandsOp, pdl::OperationOp,
230 pdl::TypeOp>(Val: val.getDefiningOp())) {
231 auto minMaxPositions =
232 std::minmax(a: pos, b: it.first->second, comp: comparePosDepth);
233 predList.emplace_back(args: minMaxPositions.second,
234 args: builder.getEqualTo(pos: minMaxPositions.first));
235 }
236 return;
237 }
238
239 TypeSwitch<Position *>(pos)
240 .Case<AttributePosition, OperationPosition, TypePosition>(caseFn: [&](auto *pos) {
241 getTreePredicates(predList, val, builder, inputs, pos);
242 })
243 .Case<OperandPosition, OperandGroupPosition>(caseFn: [&](auto *pos) {
244 getOperandTreePredicates(predList, val, builder, inputs, pos);
245 })
246 .DefaultUnreachable(message: "unexpected position kind");
247}
248
249static void getAttributePredicates(pdl::AttributeOp op,
250 std::vector<PositionalPredicate> &predList,
251 PredicateBuilder &builder,
252 DenseMap<Value, Position *> &inputs) {
253 Position *&attrPos = inputs[op];
254 if (attrPos)
255 return;
256 Attribute value = op.getValueAttr();
257 assert(value && "expected non-tree `pdl.attribute` to contain a value");
258 attrPos = builder.getAttributeLiteral(attr: value);
259}
260
261static void getConstraintPredicates(pdl::ApplyNativeConstraintOp op,
262 std::vector<PositionalPredicate> &predList,
263 PredicateBuilder &builder,
264 DenseMap<Value, Position *> &inputs) {
265 OperandRange arguments = op.getArgs();
266
267 std::vector<Position *> allPositions;
268 allPositions.reserve(n: arguments.size());
269 for (Value arg : arguments)
270 allPositions.push_back(x: inputs.lookup(Val: arg));
271
272 // Push the constraint to the furthest position.
273 Position *pos = *llvm::max_element(Range&: allPositions, C: comparePosDepth);
274 ResultRange results = op.getResults();
275 PredicateBuilder::Predicate pred = builder.getConstraint(
276 name: op.getName(), args: allPositions, resultTypes: SmallVector<Type>(results.getTypes()),
277 isNegated: op.getIsNegated());
278
279 // For each result register a position so it can be used later
280 for (auto [i, result] : llvm::enumerate(First&: results)) {
281 ConstraintQuestion *q = cast<ConstraintQuestion>(Val: pred.first);
282 ConstraintPosition *pos = builder.getConstraintPosition(q, index: i);
283 auto [it, inserted] = inputs.try_emplace(Key: result, Args&: pos);
284 // If this is an input value that has been visited in the tree, add a
285 // constraint to ensure that both instances refer to the same value.
286 if (!inserted) {
287 Position *first = pos;
288 Position *second = it->second;
289 if (comparePosDepth(lhs: second, rhs: first))
290 std::tie(args&: second, args&: first) = std::make_pair(x&: first, y&: second);
291
292 predList.emplace_back(args&: second, args: builder.getEqualTo(pos: first));
293 }
294 }
295 predList.emplace_back(args&: pos, args&: pred);
296}
297
298static void getResultPredicates(pdl::ResultOp op,
299 std::vector<PositionalPredicate> &predList,
300 PredicateBuilder &builder,
301 DenseMap<Value, Position *> &inputs) {
302 Position *&resultPos = inputs[op];
303 if (resultPos)
304 return;
305
306 // Ensure that the result isn't null.
307 auto *parentPos = cast<OperationPosition>(Val: inputs.lookup(Val: op.getParent()));
308 resultPos = builder.getResult(p: parentPos, result: op.getIndex());
309 predList.emplace_back(args&: resultPos, args: builder.getIsNotNull());
310}
311
312static void getResultPredicates(pdl::ResultsOp op,
313 std::vector<PositionalPredicate> &predList,
314 PredicateBuilder &builder,
315 DenseMap<Value, Position *> &inputs) {
316 Position *&resultPos = inputs[op];
317 if (resultPos)
318 return;
319
320 // Ensure that the result isn't null if the result has an index.
321 auto *parentPos = cast<OperationPosition>(Val: inputs.lookup(Val: op.getParent()));
322 bool isVariadic = isa<pdl::RangeType>(Val: op.getType());
323 std::optional<unsigned> index = op.getIndex();
324 resultPos = builder.getResultGroup(p: parentPos, group: index, isVariadic);
325 if (index)
326 predList.emplace_back(args&: resultPos, args: builder.getIsNotNull());
327}
328
329static void getTypePredicates(Value typeValue,
330 function_ref<Attribute()> typeAttrFn,
331 PredicateBuilder &builder,
332 DenseMap<Value, Position *> &inputs) {
333 Position *&typePos = inputs[typeValue];
334 if (typePos)
335 return;
336 Attribute typeAttr = typeAttrFn();
337 assert(typeAttr &&
338 "expected non-tree `pdl.type`/`pdl.types` to contain a value");
339 typePos = builder.getTypeLiteral(attr: typeAttr);
340}
341
342/// Collect all of the predicates that cannot be determined via walking the
343/// tree.
344static void getNonTreePredicates(pdl::PatternOp pattern,
345 std::vector<PositionalPredicate> &predList,
346 PredicateBuilder &builder,
347 DenseMap<Value, Position *> &inputs) {
348 for (Operation &op : pattern.getBodyRegion().getOps()) {
349 TypeSwitch<Operation *>(&op)
350 .Case(caseFn: [&](pdl::AttributeOp attrOp) {
351 getAttributePredicates(op: attrOp, predList, builder, inputs);
352 })
353 .Case(caseFn: [&](pdl::ApplyNativeConstraintOp constraintOp) {
354 getConstraintPredicates(op: constraintOp, predList, builder, inputs);
355 })
356 .Case<pdl::ResultOp, pdl::ResultsOp>(caseFn: [&](auto resultOp) {
357 getResultPredicates(resultOp, predList, builder, inputs);
358 })
359 .Case(caseFn: [&](pdl::TypeOp typeOp) {
360 getTypePredicates(
361 typeValue: typeOp, typeAttrFn: [&] { return typeOp.getConstantTypeAttr(); }, builder,
362 inputs);
363 })
364 .Case(caseFn: [&](pdl::TypesOp typeOp) {
365 getTypePredicates(
366 typeValue: typeOp, typeAttrFn: [&] { return typeOp.getConstantTypesAttr(); }, builder,
367 inputs);
368 });
369 }
370}
371
372namespace {
373
374/// An op accepting a value at an optional index.
375struct OpIndex {
376 Value parent;
377 std::optional<unsigned> index;
378};
379
380/// The parent and operand index of each operation for each root, stored
381/// as a nested map [root][operation].
382using ParentMaps = DenseMap<Value, DenseMap<Value, OpIndex>>;
383
384} // namespace
385
386/// Given a pattern, determines the set of roots present in this pattern.
387/// These are the operations whose results are not consumed by other operations.
388static SmallVector<Value> detectRoots(pdl::PatternOp pattern) {
389 // First, collect all the operations that are used as operands
390 // to other operations. These are not roots by default.
391 DenseSet<Value> used;
392 for (auto operationOp : pattern.getBodyRegion().getOps<pdl::OperationOp>()) {
393 for (Value operand : operationOp.getOperandValues())
394 TypeSwitch<Operation *>(operand.getDefiningOp())
395 .Case<pdl::ResultOp, pdl::ResultsOp>(
396 caseFn: [&used](auto resultOp) { used.insert(resultOp.getParent()); });
397 }
398
399 // Remove the specified root from the use set, so that we can
400 // always select it as a root, even if it is used by other operations.
401 if (Value root = pattern.getRewriter().getRoot())
402 used.erase(V: root);
403
404 // Finally, collect all the unused operations.
405 SmallVector<Value> roots;
406 for (Value operationOp : pattern.getBodyRegion().getOps<pdl::OperationOp>())
407 if (!used.contains(V: operationOp))
408 roots.push_back(Elt: operationOp);
409
410 return roots;
411}
412
413/// Given a list of candidate roots, builds the cost graph for connecting them.
414/// The graph is formed by traversing the DAG of operations starting from each
415/// root and marking the depth of each connector value (operand). Then we join
416/// the candidate roots based on the common connector values, taking the one
417/// with the minimum depth. Along the way, we compute, for each candidate root,
418/// a mapping from each operation (in the DAG underneath this root) to its
419/// parent operation and the corresponding operand index.
420static void buildCostGraph(ArrayRef<Value> roots, RootOrderingGraph &graph,
421 ParentMaps &parentMaps) {
422
423 // The entry of a queue. The entry consists of the following items:
424 // * the value in the DAG underneath the root;
425 // * the parent of the value;
426 // * the operand index of the value in its parent;
427 // * the depth of the visited value.
428 struct Entry {
429 Entry(Value value, Value parent, std::optional<unsigned> index,
430 unsigned depth)
431 : value(value), parent(parent), index(index), depth(depth) {}
432
433 Value value;
434 Value parent;
435 std::optional<unsigned> index;
436 unsigned depth;
437 };
438
439 // A root of a value and its depth (distance from root to the value).
440 struct RootDepth {
441 Value root;
442 unsigned depth = 0;
443 };
444
445 // Map from candidate connector values to their roots and depths. Using a
446 // small vector with 1 entry because most values belong to a single root.
447 llvm::MapVector<Value, SmallVector<RootDepth, 1>> connectorsRootsDepths;
448
449 // Perform a breadth-first traversal of the op DAG rooted at each root.
450 for (Value root : roots) {
451 // The queue of visited values. A value may be present multiple times in
452 // the queue, for multiple parents. We only accept the first occurrence,
453 // which is guaranteed to have the lowest depth.
454 std::queue<Entry> toVisit;
455 toVisit.emplace(args&: root, args: Value(), args: 0, args: 0);
456
457 // The map from value to its parent for the current root.
458 DenseMap<Value, OpIndex> &parentMap = parentMaps[root];
459
460 while (!toVisit.empty()) {
461 Entry entry = toVisit.front();
462 toVisit.pop();
463 // Skip if already visited.
464 if (!parentMap.insert(KV: {entry.value, {.parent: entry.parent, .index: entry.index}}).second)
465 continue;
466
467 // Mark the root and depth of the value.
468 connectorsRootsDepths[entry.value].push_back(Elt: {.root: root, .depth: entry.depth});
469
470 // Traverse the operands of an operation and result ops.
471 // We intentionally do not traverse attributes and types, because those
472 // are expensive to join on.
473 TypeSwitch<Operation *>(entry.value.getDefiningOp())
474 .Case(caseFn: [&](pdl::OperationOp operationOp) {
475 OperandRange operands = operationOp.getOperandValues();
476 // Special case when we pass all the operands in one range.
477 // For those, the index is empty.
478 if (operands.size() == 1 &&
479 isa<pdl::RangeType>(Val: operands[0].getType())) {
480 toVisit.emplace(args: operands[0], args&: entry.value, args: std::nullopt,
481 args: entry.depth + 1);
482 return;
483 }
484
485 // Default case: visit all the operands.
486 for (const auto &p :
487 llvm::enumerate(First: operationOp.getOperandValues()))
488 toVisit.emplace(args&: p.value(), args&: entry.value, args: p.index(),
489 args: entry.depth + 1);
490 })
491 .Case<pdl::ResultOp, pdl::ResultsOp>(caseFn: [&](auto resultOp) {
492 toVisit.emplace(resultOp.getParent(), entry.value,
493 resultOp.getIndex(), entry.depth);
494 });
495 }
496 }
497
498 // Now build the cost graph.
499 // This is simply a minimum over all depths for the target root.
500 unsigned nextID = 0;
501 for (const auto &connectorRootsDepths : connectorsRootsDepths) {
502 Value value = connectorRootsDepths.first;
503 ArrayRef<RootDepth> rootsDepths = connectorRootsDepths.second;
504 // If there is only one root for this value, this will not trigger
505 // any edges in the cost graph (a perf optimization).
506 if (rootsDepths.size() == 1)
507 continue;
508
509 for (const RootDepth &p : rootsDepths) {
510 for (const RootDepth &q : rootsDepths) {
511 if (&p == &q)
512 continue;
513 // Insert or retrieve the property of edge from p to q.
514 RootOrderingEntry &entry = graph[q.root][p.root];
515 if (!entry.connector /* new edge */ || entry.cost.first > q.depth) {
516 if (!entry.connector)
517 entry.cost.second = nextID++;
518 entry.cost.first = q.depth;
519 entry.connector = value;
520 }
521 }
522 }
523 }
524
525 assert((llvm::hasSingleElement(roots) || graph.size() == roots.size()) &&
526 "the pattern contains a candidate root disconnected from the others");
527}
528
529/// Returns true if the operand at the given index needs to be queried using an
530/// operand group, i.e., if it is variadic itself or follows a variadic operand.
531static bool useOperandGroup(pdl::OperationOp op, unsigned index) {
532 OperandRange operands = op.getOperandValues();
533 assert(index < operands.size() && "operand index out of range");
534 for (unsigned i = 0; i <= index; ++i)
535 if (isa<pdl::RangeType>(Val: operands[i].getType()))
536 return true;
537 return false;
538}
539
540/// Visit a node during upward traversal.
541static void visitUpward(std::vector<PositionalPredicate> &predList,
542 OpIndex opIndex, PredicateBuilder &builder,
543 DenseMap<Value, Position *> &valueToPosition,
544 Position *&pos, unsigned rootID) {
545 Value value = opIndex.parent;
546 TypeSwitch<Operation *>(value.getDefiningOp())
547 .Case(caseFn: [&](pdl::OperationOp operationOp) {
548 LDBG() << " * Value: " << value;
549
550 // Get users and iterate over them.
551 Position *usersPos = builder.getUsers(p: pos, /*useRepresentative=*/true);
552 Position *foreachPos = builder.getForEach(p: usersPos, id: rootID);
553 OperationPosition *opPos = builder.getPassthroughOp(p: foreachPos);
554
555 // Compare the operand(s) of the user against the input value(s).
556 Position *operandPos;
557 if (!opIndex.index) {
558 // We are querying all the operands of the operation.
559 operandPos = builder.getAllOperands(p: opPos);
560 } else if (useOperandGroup(op: operationOp, index: *opIndex.index)) {
561 // We are querying an operand group.
562 Type type = operationOp.getOperandValues()[*opIndex.index].getType();
563 bool variadic = isa<pdl::RangeType>(Val: type);
564 operandPos = builder.getOperandGroup(p: opPos, group: opIndex.index, isVariadic: variadic);
565 } else {
566 // We are querying an individual operand.
567 operandPos = builder.getOperand(p: opPos, operand: *opIndex.index);
568 }
569 predList.emplace_back(args&: operandPos, args: builder.getEqualTo(pos));
570
571 // Guard against duplicate upward visits. These are not possible,
572 // because if this value was already visited, it would have been
573 // cheaper to start the traversal at this value rather than at the
574 // `connector`, violating the optimality of our spanning tree.
575 bool inserted = valueToPosition.try_emplace(Key: value, Args&: opPos).second;
576 (void)inserted;
577 assert(inserted && "duplicate upward visit");
578
579 // Obtain the tree predicates at the current value.
580 getTreePredicates(predList, val: value, builder, inputs&: valueToPosition, pos: opPos,
581 ignoreOperand: opIndex.index);
582
583 // Update the position
584 pos = opPos;
585 })
586 .Case(caseFn: [&](pdl::ResultOp resultOp) {
587 // Traverse up an individual result.
588 auto *opPos = dyn_cast<OperationPosition>(Val: pos);
589 assert(opPos && "operations and results must be interleaved");
590 pos = builder.getResult(p: opPos, result: *opIndex.index);
591
592 // Insert the result position in case we have not visited it yet.
593 valueToPosition.try_emplace(Key: value, Args&: pos);
594 })
595 .Case(caseFn: [&](pdl::ResultsOp resultOp) {
596 // Traverse up a group of results.
597 auto *opPos = dyn_cast<OperationPosition>(Val: pos);
598 assert(opPos && "operations and results must be interleaved");
599 bool isVariadic = isa<pdl::RangeType>(Val: value.getType());
600 if (opIndex.index)
601 pos = builder.getResultGroup(p: opPos, group: opIndex.index, isVariadic);
602 else
603 pos = builder.getAllResults(p: opPos);
604
605 // Insert the result position in case we have not visited it yet.
606 valueToPosition.try_emplace(Key: value, Args&: pos);
607 });
608}
609
610/// Given a pattern operation, build the set of matcher predicates necessary to
611/// match this pattern.
612static Value buildPredicateList(pdl::PatternOp pattern,
613 PredicateBuilder &builder,
614 std::vector<PositionalPredicate> &predList,
615 DenseMap<Value, Position *> &valueToPosition) {
616 SmallVector<Value> roots = detectRoots(pattern);
617
618 // Build the root ordering graph and compute the parent maps.
619 RootOrderingGraph graph;
620 ParentMaps parentMaps;
621 buildCostGraph(roots, graph, parentMaps);
622 LDBG() << "Graph:";
623 for (auto &target : graph) {
624 LDBG() << " * " << target.first.getLoc() << " " << target.first;
625 for (auto &source : target.second) {
626 RootOrderingEntry &entry = source.second;
627 LDBG() << " <- " << source.first << ": " << entry.cost.first << ":"
628 << entry.cost.second << " via " << entry.connector.getLoc();
629 }
630 }
631
632 // Solve the optimal branching problem for each candidate root, or use the
633 // provided one.
634 Value bestRoot = pattern.getRewriter().getRoot();
635 OptimalBranching::EdgeList bestEdges;
636 if (!bestRoot) {
637 unsigned bestCost = 0;
638 LDBG() << "Candidate roots:";
639 for (Value root : roots) {
640 OptimalBranching solver(graph, root);
641 unsigned cost = solver.solve();
642 LDBG() << " * " << root << ": " << cost;
643 if (!bestRoot || bestCost > cost) {
644 bestCost = cost;
645 bestRoot = root;
646 bestEdges = solver.preOrderTraversal(nodes: roots);
647 }
648 }
649 } else {
650 OptimalBranching solver(graph, bestRoot);
651 solver.solve();
652 bestEdges = solver.preOrderTraversal(nodes: roots);
653 }
654
655 // Print the best solution.
656 LDBG() << "Best tree:";
657 for (const std::pair<Value, Value> &edge : bestEdges) {
658 if (edge.second)
659 LDBG() << " * " << edge.first << " <- " << edge.second;
660 else
661 LDBG() << " * " << edge.first;
662 }
663
664 LDBG() << "Calling key getTreePredicates (Value: " << bestRoot << ")";
665
666 // The best root is the starting point for the traversal. Get the tree
667 // predicates for the DAG rooted at bestRoot.
668 getTreePredicates(predList, val: bestRoot, builder, inputs&: valueToPosition,
669 pos: builder.getRoot());
670
671 // Traverse the selected optimal branching. For all edges in order, traverse
672 // up starting from the connector, until the candidate root is reached, and
673 // call getTreePredicates at every node along the way.
674 for (const auto &it : llvm::enumerate(First&: bestEdges)) {
675 Value target = it.value().first;
676 Value source = it.value().second;
677
678 // Check if we already visited the target root. This happens in two cases:
679 // 1) the initial root (bestRoot);
680 // 2) a root that is dominated by (contained in the subtree rooted at) an
681 // already visited root.
682 if (valueToPosition.count(Val: target))
683 continue;
684
685 // Determine the connector.
686 Value connector = graph[target][source].connector;
687 assert(connector && "invalid edge");
688 LDBG() << " * Connector: " << connector.getLoc();
689 DenseMap<Value, OpIndex> parentMap = parentMaps.lookup(Val: target);
690 Position *pos = valueToPosition.lookup(Val: connector);
691 assert(pos && "connector has not been traversed yet");
692
693 // Traverse from the connector upwards towards the target root.
694 for (Value value = connector; value != target;) {
695 OpIndex opIndex = parentMap.lookup(Val: value);
696 assert(opIndex.parent && "missing parent");
697 visitUpward(predList, opIndex, builder, valueToPosition, pos, rootID: it.index());
698 value = opIndex.parent;
699 }
700 }
701
702 getNonTreePredicates(pattern, predList, builder, inputs&: valueToPosition);
703
704 return bestRoot;
705}
706
707//===----------------------------------------------------------------------===//
708// Pattern Predicate Tree Merging
709//===----------------------------------------------------------------------===//
710
711namespace {
712
713/// This class represents a specific predicate applied to a position, and
714/// provides hashing and ordering operators. This class allows for computing a
715/// frequence sum and ordering predicates based on a cost model.
716struct OrderedPredicate {
717 OrderedPredicate(const std::pair<Position *, Qualifier *> &ip)
718 : position(ip.first), question(ip.second) {}
719 OrderedPredicate(const PositionalPredicate &ip)
720 : position(ip.position), question(ip.question) {}
721
722 /// The position this predicate is applied to.
723 Position *position;
724
725 /// The question that is applied by this predicate onto the position.
726 Qualifier *question;
727
728 /// The first and second order benefit sums.
729 /// The primary sum is the number of occurrences of this predicate among all
730 /// of the patterns.
731 unsigned primary = 0;
732 /// The secondary sum is a squared summation of the primary sum of all of the
733 /// predicates within each pattern that contains this predicate. This allows
734 /// for favoring predicates that are more commonly shared within a pattern, as
735 /// opposed to those shared across patterns.
736 unsigned secondary = 0;
737
738 /// The tie breaking ID, used to preserve a deterministic (insertion) order
739 /// among all the predicates with the same priority, depth, and position /
740 /// predicate dependency.
741 unsigned id = 0;
742
743 /// A map between a pattern operation and the answer to the predicate question
744 /// within that pattern.
745 DenseMap<Operation *, Qualifier *> patternToAnswer;
746
747 /// Returns true if this predicate is ordered before `rhs`, based on the cost
748 /// model.
749 bool operator<(const OrderedPredicate &rhs) const {
750 // Sort by:
751 // * higher first and secondary order sums
752 // * lower depth
753 // * lower position dependency
754 // * lower predicate dependency
755 // * lower tie breaking ID
756 auto *rhsPos = rhs.position;
757 return std::make_tuple(args: primary, args: secondary, args: rhsPos->getOperationDepth(),
758 args: rhsPos->getKind(), args: rhs.question->getKind(), args: rhs.id) >
759 std::make_tuple(args: rhs.primary, args: rhs.secondary,
760 args: position->getOperationDepth(), args: position->getKind(),
761 args: question->getKind(), args: id);
762 }
763};
764
765/// A DenseMapInfo for OrderedPredicate based solely on the position and
766/// question.
767struct OrderedPredicateDenseInfo {
768 static bool isEqual(const OrderedPredicate &lhs,
769 const OrderedPredicate &rhs) {
770 return lhs.position == rhs.position && lhs.question == rhs.question;
771 }
772 static unsigned getHashValue(const OrderedPredicate &p) {
773 return llvm::hash_combine(args: p.position, args: p.question);
774 }
775};
776
777/// This class wraps a set of ordered predicates that are used within a specific
778/// pattern operation.
779struct OrderedPredicateList {
780 OrderedPredicateList(pdl::PatternOp pattern, Value root)
781 : pattern(pattern), root(root) {}
782
783 pdl::PatternOp pattern;
784 Value root;
785 DenseSet<OrderedPredicate *> predicates;
786};
787} // namespace
788
789/// Returns true if the given matcher refers to the same predicate as the given
790/// ordered predicate. This means that the position and questions of the two
791/// match.
792static bool isSamePredicate(MatcherNode *node, OrderedPredicate *predicate) {
793 return node->getPosition() == predicate->position &&
794 node->getQuestion() == predicate->question;
795}
796
797/// Get or insert a child matcher for the given parent switch node, given a
798/// predicate and parent pattern.
799static std::unique_ptr<MatcherNode> &
800getOrCreateChild(SwitchNode *node, OrderedPredicate *predicate,
801 pdl::PatternOp pattern) {
802 assert(isSamePredicate(node, predicate) &&
803 "expected matcher to equal the given predicate");
804
805 auto it = predicate->patternToAnswer.find(Val: pattern);
806 assert(it != predicate->patternToAnswer.end() &&
807 "expected pattern to exist in predicate");
808 return node->getChildren()[it->second];
809}
810
811/// Build the matcher CFG by "pushing" patterns through by sorted predicate
812/// order. A pattern will traverse as far as possible using common predicates
813/// and then either diverge from the CFG or reach the end of a branch and start
814/// creating new nodes.
815static void propagatePattern(std::unique_ptr<MatcherNode> &node,
816 OrderedPredicateList &list,
817 std::vector<OrderedPredicate *>::iterator current,
818 std::vector<OrderedPredicate *>::iterator end) {
819 if (current == end) {
820 // We've hit the end of a pattern, so create a successful result node.
821 node =
822 std::make_unique<SuccessNode>(args&: list.pattern, args&: list.root, args: std::move(node));
823
824 // If the pattern doesn't contain this predicate, ignore it.
825 } else if (!list.predicates.contains(V: *current)) {
826 propagatePattern(node, list, current: std::next(x: current), end);
827
828 // If the current matcher node is invalid, create a new one for this
829 // position and continue propagation.
830 } else if (!node) {
831 // Create a new node at this position and continue
832 node = std::make_unique<SwitchNode>(args&: (*current)->position,
833 args&: (*current)->question);
834 propagatePattern(
835 node&: getOrCreateChild(node: cast<SwitchNode>(Val: &*node), predicate: *current, pattern: list.pattern),
836 list, current: std::next(x: current), end);
837
838 // If the matcher has already been created, and it is for this predicate we
839 // continue propagation to the child.
840 } else if (isSamePredicate(node: node.get(), predicate: *current)) {
841 propagatePattern(
842 node&: getOrCreateChild(node: cast<SwitchNode>(Val: &*node), predicate: *current, pattern: list.pattern),
843 list, current: std::next(x: current), end);
844
845 // If the matcher doesn't match the current predicate, insert a branch as
846 // the common set of matchers has diverged.
847 } else {
848 propagatePattern(node&: node->getFailureNode(), list, current, end);
849 }
850}
851
852/// Fold any switch nodes nested under `node` to boolean nodes when possible.
853/// `node` is updated in-place if it is a switch.
854static void foldSwitchToBool(std::unique_ptr<MatcherNode> &node) {
855 if (!node)
856 return;
857
858 if (SwitchNode *switchNode = dyn_cast<SwitchNode>(Val: &*node)) {
859 SwitchNode::ChildMapT &children = switchNode->getChildren();
860 for (auto &it : children)
861 foldSwitchToBool(node&: it.second);
862
863 // If the node only contains one child, collapse it into a boolean predicate
864 // node.
865 if (children.size() == 1) {
866 auto *childIt = children.begin();
867 node = std::make_unique<BoolNode>(
868 args: node->getPosition(), args: node->getQuestion(), args&: childIt->first,
869 args: std::move(childIt->second), args: std::move(node->getFailureNode()));
870 }
871 } else if (BoolNode *boolNode = dyn_cast<BoolNode>(Val: &*node)) {
872 foldSwitchToBool(node&: boolNode->getSuccessNode());
873 }
874
875 foldSwitchToBool(node&: node->getFailureNode());
876}
877
878/// Insert an exit node at the end of the failure path of the `root`.
879static void insertExitNode(std::unique_ptr<MatcherNode> *root) {
880 while (*root)
881 root = &(*root)->getFailureNode();
882 *root = std::make_unique<ExitNode>();
883}
884
885/// Sorts the range begin/end with the partial order given by cmp.
886template <typename Iterator, typename Compare>
887static void stableTopologicalSort(Iterator begin, Iterator end, Compare cmp) {
888 while (begin != end) {
889 // Cannot compute sortBeforeOthers in the predicate of stable_partition
890 // because stable_partition will not keep the [begin, end) range intact
891 // while it runs.
892 llvm::SmallPtrSet<typename Iterator::value_type, 16> sortBeforeOthers;
893 for (auto i = begin; i != end; ++i) {
894 if (std::none_of(begin, end, [&](auto const &b) { return cmp(b, *i); }))
895 sortBeforeOthers.insert(*i);
896 }
897
898 auto const next = std::stable_partition(begin, end, [&](auto const &a) {
899 return sortBeforeOthers.contains(a);
900 });
901 assert(next != begin && "not a partial ordering");
902 begin = next;
903 }
904}
905
906/// Returns true if 'b' depends on a result of 'a'.
907static bool dependsOn(OrderedPredicate *a, OrderedPredicate *b) {
908 auto *cqa = dyn_cast<ConstraintQuestion>(Val: a->question);
909 if (!cqa)
910 return false;
911
912 auto positionDependsOnA = [&](Position *p) {
913 auto *cp = dyn_cast<ConstraintPosition>(Val: p);
914 return cp && cp->getQuestion() == cqa;
915 };
916
917 if (auto *cqb = dyn_cast<ConstraintQuestion>(Val: b->question)) {
918 // Does any argument of b use a?
919 return llvm::any_of(Range: cqb->getArgs(), P: positionDependsOnA);
920 }
921 if (auto *equalTo = dyn_cast<EqualToQuestion>(Val: b->question)) {
922 return positionDependsOnA(b->position) ||
923 positionDependsOnA(equalTo->getValue());
924 }
925 return positionDependsOnA(b->position);
926}
927
928/// Given a module containing PDL pattern operations, generate a matcher tree
929/// using the patterns within the given module and return the root matcher node.
930std::unique_ptr<MatcherNode>
931MatcherNode::generateMatcherTree(ModuleOp module, PredicateBuilder &builder,
932 DenseMap<Value, Position *> &valueToPosition) {
933 // The set of predicates contained within the pattern operations of the
934 // module.
935 struct PatternPredicates {
936 PatternPredicates(pdl::PatternOp pattern, Value root,
937 std::vector<PositionalPredicate> predicates)
938 : pattern(pattern), root(root), predicates(std::move(predicates)) {}
939
940 /// A pattern.
941 pdl::PatternOp pattern;
942
943 /// A root of the pattern chosen among the candidate roots in pdl.rewrite.
944 Value root;
945
946 /// The extracted predicates for this pattern and root.
947 std::vector<PositionalPredicate> predicates;
948 };
949
950 SmallVector<PatternPredicates, 16> patternsAndPredicates;
951 for (pdl::PatternOp pattern : module.getOps<pdl::PatternOp>()) {
952 std::vector<PositionalPredicate> predicateList;
953 Value root =
954 buildPredicateList(pattern, builder, predList&: predicateList, valueToPosition);
955 patternsAndPredicates.emplace_back(Args&: pattern, Args&: root, Args: std::move(predicateList));
956 }
957
958 // Associate a pattern result with each unique predicate.
959 DenseSet<OrderedPredicate, OrderedPredicateDenseInfo> uniqued;
960 for (auto &patternAndPredList : patternsAndPredicates) {
961 for (auto &predicate : patternAndPredList.predicates) {
962 auto it = uniqued.insert(V: predicate);
963 it.first->patternToAnswer.try_emplace(Key: patternAndPredList.pattern,
964 Args&: predicate.answer);
965 // Mark the insertion order (0-based indexing).
966 if (it.second)
967 it.first->id = uniqued.size() - 1;
968 }
969 }
970
971 // Associate each pattern to a set of its ordered predicates for later lookup.
972 std::vector<OrderedPredicateList> lists;
973 lists.reserve(n: patternsAndPredicates.size());
974 for (auto &patternAndPredList : patternsAndPredicates) {
975 OrderedPredicateList list(patternAndPredList.pattern,
976 patternAndPredList.root);
977 for (auto &predicate : patternAndPredList.predicates) {
978 OrderedPredicate *orderedPredicate = &*uniqued.find(V: predicate);
979 list.predicates.insert(V: orderedPredicate);
980
981 // Increment the primary sum for each reference to a particular predicate.
982 ++orderedPredicate->primary;
983 }
984 lists.push_back(x: std::move(list));
985 }
986
987 // For a particular pattern, get the total primary sum and add it to the
988 // secondary sum of each predicate. Square the primary sums to emphasize
989 // shared predicates within rather than across patterns.
990 for (auto &list : lists) {
991 unsigned total = 0;
992 for (auto *predicate : list.predicates)
993 total += predicate->primary * predicate->primary;
994 for (auto *predicate : list.predicates)
995 predicate->secondary += total;
996 }
997
998 // Sort the set of predicates now that the cost primary and secondary sums
999 // have been computed.
1000 std::vector<OrderedPredicate *> ordered;
1001 ordered.reserve(n: uniqued.size());
1002 for (auto &ip : uniqued)
1003 ordered.push_back(x: &ip);
1004 llvm::sort(C&: ordered, Comp: [](OrderedPredicate *lhs, OrderedPredicate *rhs) {
1005 return *lhs < *rhs;
1006 });
1007
1008 // Mostly keep the now established order, but also ensure that
1009 // ConstraintQuestions come after the results they use.
1010 stableTopologicalSort(begin: ordered.begin(), end: ordered.end(), cmp: dependsOn);
1011
1012 // Build the matchers for each of the pattern predicate lists.
1013 std::unique_ptr<MatcherNode> root;
1014 for (OrderedPredicateList &list : lists)
1015 propagatePattern(node&: root, list, current: ordered.begin(), end: ordered.end());
1016
1017 // Collapse the graph and insert the exit node.
1018 foldSwitchToBool(node&: root);
1019 insertExitNode(root: &root);
1020 return root;
1021}
1022
1023//===----------------------------------------------------------------------===//
1024// MatcherNode
1025//===----------------------------------------------------------------------===//
1026
1027MatcherNode::MatcherNode(TypeID matcherTypeID, Position *p, Qualifier *q,
1028 std::unique_ptr<MatcherNode> failureNode)
1029 : position(p), question(q), failureNode(std::move(failureNode)),
1030 matcherTypeID(matcherTypeID) {}
1031
1032//===----------------------------------------------------------------------===//
1033// BoolNode
1034//===----------------------------------------------------------------------===//
1035
1036BoolNode::BoolNode(Position *position, Qualifier *question, Qualifier *answer,
1037 std::unique_ptr<MatcherNode> successNode,
1038 std::unique_ptr<MatcherNode> failureNode)
1039 : MatcherNode(TypeID::get<BoolNode>(), position, question,
1040 std::move(failureNode)),
1041 answer(answer), successNode(std::move(successNode)) {}
1042
1043//===----------------------------------------------------------------------===//
1044// SuccessNode
1045//===----------------------------------------------------------------------===//
1046
1047SuccessNode::SuccessNode(pdl::PatternOp pattern, Value root,
1048 std::unique_ptr<MatcherNode> failureNode)
1049 : MatcherNode(TypeID::get<SuccessNode>(), /*position=*/nullptr,
1050 /*question=*/nullptr, std::move(failureNode)),
1051 pattern(pattern), root(root) {}
1052
1053//===----------------------------------------------------------------------===//
1054// SwitchNode
1055//===----------------------------------------------------------------------===//
1056
1057SwitchNode::SwitchNode(Position *position, Qualifier *question)
1058 : MatcherNode(TypeID::get<SwitchNode>(), position, question) {}
1059