junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r693399727
##########
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;
Review comment:
add a `reserve` here to avoid re-allocation, even though it is an
uplimit not a precious number
```C++
chain.reserve(visited.size());
```
##########
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;
Review comment:
add a `reserve` here to avoid re-allocation, even though it is an
uplimit not a precise number
```C++
chain.reserve(visited.size());
```
##########
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;
Review comment:
add a `reserve` here to avoid re-allocation, even though it is an
uplimit instead of the precise number
```C++
chain.reserve(visited.size());
```
--
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
