junrushao1994 commented on a change in pull request #8767: URL: https://github.com/apache/tvm/pull/8767#discussion_r693402002
########## 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>(); + ObjectPtr<ForNode> n = make_object<ForNode>(*copy); + if (new_loop.defined()) { + n->body = new_loop; + } else { + n->body = loop_sref->StmtAs<ForNode>()->body; + } + const VarNode* used_var; Review comment: Always initialize variables (although we know it won't be used as uninitialized) ```suggestion const VarNode* used_var = 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: commits-unsubscr...@tvm.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org