junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r693401332
##########
File path: src/tir/schedule/primitive/loop_transformation.cc
##########
@@ -385,6 +511,116 @@ StmtSRef Fuse(ScheduleState self, const Array<StmtSRef>&
loop_srefs) {
return self->stmt2ref.at(new_stmt.get());
}
+void Reorder(ScheduleState self, const Array<StmtSRef>& ordered_loop_srefs) {
+ if (ordered_loop_srefs.empty() || ordered_loop_srefs.size() == 1) {
+ return;
+ }
+ std::unordered_set<const StmtSRefNode*> loop_srefs;
+ loop_srefs.reserve(ordered_loop_srefs.size());
+ // Step 1. Check uniqueness.
+ for (const StmtSRef& loop_sref : ordered_loop_srefs) {
+ const ForNode* loop = TVM_SREF_TO_FOR(loop, loop_sref);
+ auto inserted = loop_srefs.insert(loop_sref.get());
+ if (!inserted.second) {
+ throw LoopMultiAppearanceError(self->mod, GetRef<For>(loop));
+ }
+ }
+ // Step 2. Gather loops to be reordered
+ // For each loop sref in the input sref array, traverse upwards along its
parent pointer in the
+ // sref tree, and stop on either a block, or a previously-visited loop
+ // - the top of the reorder range is the last loop visited in the first
traversal which exists in
+ // the input array
+ // - the bottom of the reorder range is the last loop in the input array
which is not visited in
+ // the previous traversals
+ const StmtSRefNode* top = nullptr;
+ const StmtSRefNode* bottom = ordered_loop_srefs[0].get();
+ std::unordered_set<const StmtSRefNode*> visited;
+ bool scope_block_visited = false;
+ for (size_t i = 0; i < ordered_loop_srefs.size(); i++) {
+ const StmtSRefNode* loop_sref = ordered_loop_srefs[i].get();
+ if (visited.count(loop_sref)) {
+ continue;
+ }
+ for (const StmtSRefNode* v = loop_sref;; v = v->parent) {
+ // Case 1. If `v` corresponds to a block, stop traversal.
+ if (v->stmt->IsInstance<BlockNode>()) {
+ if (scope_block_visited) {
+ throw LoopsNotAChainError(self->mod, NullOpt,
+
LoopsNotAChainError::ProblemKind::kNotUnderAScope);
+ }
+ scope_block_visited = true;
+ break;
+ }
+ // Case 2. If `v` corresponds to a previously-visited loop, stop
traversal and update
+ // `bottom`.
+ if (visited.count(v)) {
+ if (v == bottom) {
+ throw LoopsNotAChainError(self->mod, GetRef<Stmt>(v->stmt),
+
LoopsNotAChainError::ProblemKind::kHaveNonSingleBranchStmt);
+ }
+ bottom = loop_sref;
+ break;
+ }
+ // Case 3. Add `v` into `visited`
+ visited.insert(v);
+ // If it's the first traversal and the loop corresponding to `v` is in
the input array,
+ // update `top`.
+ if (loop_srefs.count(v) && i == 0) {
+ top = v;
+ }
+ }
+ }
+ // Step 3. Collect all loops in the chain and check the loops are
single-branch
+ std::vector<const StmtSRefNode*> chain;
+ for (const StmtSRefNode* loop_sref = bottom;; loop_sref = loop_sref->parent)
{
+ if (!chain.empty()) {
+ const ForNode* outer_loop = TVM_SREF_TO_FOR(outer_loop,
GetRef<StmtSRef>(loop_sref));
+ const ForNode* inner_loop = TVM_SREF_TO_FOR(inner_loop,
GetRef<StmtSRef>(chain.back()));
+ if (outer_loop->body.get() != inner_loop) {
+ throw LoopsNotAChainError(self->mod, GetRef<For>(outer_loop),
+
LoopsNotAChainError::ProblemKind::kHaveNonSingleBranchStmt);
+ }
+ }
+ chain.push_back(loop_sref);
+ if (loop_sref == top) {
+ break;
+ }
+ }
+ // Step 4. Check the block below has all its block_var to be data-parallel
or reduction,
+ // and the block has an affine binding.
+ BlockPropertyError::CheckBlockIterTypeAndAffineBinding(self, bottom);
+ // Step 5. Replace the original loops with the reordered loops and check
that outer loop is
+ // not dependent on inner loop
+ std::unordered_set<const VarNode*> inner_vars;
+ For new_loop;
+ int index = ordered_loop_srefs.size() - 1;
+ for (const StmtSRefNode* loop_sref : chain) {
+ const ForNode* copy = loop_srefs.count(loop_sref)
+ ? ordered_loop_srefs[index--]->StmtAs<ForNode>()
+ : loop_sref->StmtAs<ForNode>();
Review comment:
Just to rephrase it a little bit to be more readable
```suggestion
const ForNode* copy = nullptr;
if (loop_srefs.count(loop_sref)) {
copy = ordered_loop_srefs[index]->StmtAs<ForNode>();
--index;
} else {
copy = loop_sref->StmtAs<ForNode>();
}
ICHECK(copy != nullptr);
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
