================
@@ -583,3 +602,467 @@ Region *mlir::getEnclosingRepetitiveRegion(Value value) {
LDBG() << "No enclosing repetitive region found for value";
return nullptr;
}
+
+/// Return "true" if `a` can be used in lieu of `b`, where `b` is a region
+/// successor input and `a` is a "possible value" of `b`. Possible values are
+/// successor operand values that are (maybe transitively) forwarded to `b`.
+static bool isDefinedBefore(Operation *regionBranchOp, Value a, Value b) {
+ assert((b.getDefiningOp() == regionBranchOp ||
+ b.getParentRegion()->getParentOp() == regionBranchOp) &&
+ "b must be a region successor input");
+
+ // Case 1: `a` is defined inside of the region branch op. `a` must be
+ // directly nested in the region branch op. Otherwise, it could not have
+ // been among the possible values for a region successor input.
+ if (a.getParentRegion()->getParentOp() == regionBranchOp) {
+ // Case 1.1: If `b` is a result of the region branch op, `a` is not in
+ // scope for `b`.
+ // Example:
+ // %b = region_op({
+ // ^bb0(%a1: ...):
+ // %a2 = ...
+ // })
+ if (isa<OpResult>(b))
+ return false;
+
+ // Case 1.2: `b` is an entry block argument of a region. `a` is in scope
+ // for `b` only if it is also an entry block argument of the same region.
+ // Example:
+ // region_op({
+ // ^bb0(%b: ..., %a: ...):
+ // ...
+ // })
+ assert(isa<BlockArgument>(b) && "b must be a block argument");
+ return isa<BlockArgument>(a) && cast<BlockArgument>(a).getOwner() ==
+ cast<BlockArgument>(b).getOwner();
+ }
+
+ // Case 2: `a` is defined outside of the region branch op. In that case, we
+ // can safely assume that `a` was defined before `b`. Otherwise, it could not
+ // be among the possible values for a region successor input.
+ // Example:
+ // { <- %a1 parent region begins here.
+ // ^bb0(%a1: ...):
+ // %a2 = ...
+ // %b1 = reigon_op({
+ // ^bb1(%b2: ...):
+ // ...
+ // })
+ // }
+ return true;
+}
+
+/// Compute all non-successor input values that a successor input could have
+/// based on the given successor input to successor operand mapping.
+///
+/// Example 1:
+/// %r = scf.for ... iter_args(%arg0 = %0) -> ... {
+/// scf.yield %arg0 : ...
+/// }
+/// getPossibleValuesOfSuccessorInput(%arg0) = {%0}
+/// getPossibleValuesOfSuccessorInput(%r) = {%0}
+///
+/// Example 2:
+/// %r = scf.for ... iter_args(%arg0 = %0) -> ... {
+/// ...
+/// scf.yield %1 : ...
+/// }
+/// getPossibleValuesOfSuccessorInput(%arg0) = {%0, %1}
+/// getPossibleValuesOfSuccessorInput(%r) = {%0, %1}
+static llvm::SmallDenseSet<Value> computePossibleValuesOfSuccessorInput(
+ Value value, const RegionBranchInverseSuccessorMapping &inputToOperands) {
+ llvm::SmallDenseSet<Value> possibleValues;
+ llvm::SmallDenseSet<Value> visited;
+ SmallVector<Value> worklist;
+
+ // Starting with the given value, trace back all predecessor values (i.e.,
+ // preceding successor operands) and add them to the set of possible values.
+ // If the successor operand is again a successor input, do not add it to
+ // result set, but instead continue the traversal.
+ worklist.push_back(value);
+ while (!worklist.empty()) {
+ Value next = worklist.pop_back_val();
+ auto it = inputToOperands.find(next);
+ if (it == inputToOperands.end()) {
+ possibleValues.insert(next);
+ continue;
+ }
+ for (OpOperand *operand : it->second)
+ if (visited.insert(operand->get()).second)
+ worklist.push_back(operand->get());
+ }
+
+ return possibleValues;
+}
+
+namespace {
+/// Try to make successor inputs dead by replacing their uses with values that
+/// are not successor inputs. This pattern enables additional canonicalization
+/// opportunities for RemoveDeadRegionBranchOpSuccessorInputs.
+///
+/// Example:
+///
+/// %r = scf.for ... iter_args(%arg0 = %0) -> ... {
+/// scf.yield %arg0 : ...
+/// }
+/// use(%r)
+///
+/// According to `computePossibleValuesOfSuccessorInput`, the only possible
+/// non-successor input value of %r and %arg0 is %0. Therefore, their uses can
+/// be replaced with %0, resulting in the following IR:
+///
+/// %r = scf.for ... iter_args(%arg0 = %0) -> ... {
+/// scf.yield %0 : ...
+/// }
+/// use(%0)
+///
+/// The IR can now be further canonicalized by
+/// RemoveDeadRegionBranchOpSuccessorInputs.
----------------
matthias-springer wrote:
Your input IR and output IR in example above is invalid. Presumably, you meant
`use(%r0)` in the input IR? And `%r0, %r1 = scf.for ...` in the output IR?
Input IR:
```
%r0, %r1 = scf.for %iv = %lb to %ub step %step iter_args(%arg0=%0, %arg1=%1)
-> (i32, i32) {
scf.yield %arg1, %arg1 : i32, i32
}
use(%r0)
use(%r2)
```
After the pattern application, it will be `scf.yield %1, %1` (as you said), but
`use(%r0)` and `use(%1)`.
Note that `getPossibleValues(%r0) = {%0, %1}`.
https://github.com/llvm/llvm-project/pull/174094
_______________________________________________
llvm-branch-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
