[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r693459325
##
File path: src/tir/schedule/primitive/loop_transformation.cc
##
@@ -385,6 +511,122 @@ StmtSRef Fuse(ScheduleState self, const Array&
loop_srefs) {
return self->stmt2ref.at(new_stmt.get());
}
+void Reorder(ScheduleState self, const Array& ordered_loop_srefs) {
+ if (ordered_loop_srefs.empty() || ordered_loop_srefs.size() == 1) {
Review comment:
to make it more concise:
```suggestion
if (ordered_loop_srefs.size() <= 1) {
```
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r693412063
##
File path: src/tir/schedule/primitive/loop_transformation.cc
##
@@ -385,6 +511,113 @@ StmtSRef Fuse(ScheduleState self, const Array&
loop_srefs) {
return self->stmt2ref.at(new_stmt.get());
}
+void Reorder(ScheduleState self, const Array& ordered_loop_srefs) {
+ std::unordered_set loop_srefs;
+ loop_srefs.reserve(ordered_loop_srefs.size());
+ if (ordered_loop_srefs.empty() || ordered_loop_srefs.size() == 1) {
+return;
+ }
+ // Step 1. check uniqueness
+ for (const StmtSRef& loop_sref : ordered_loop_srefs) {
+const ForNode* loop = TVM_SREF_TO_FOR(loop, loop_sref);
+// uniqueness check
+auto inserted = loop_srefs.insert(loop_sref.get());
+if (!inserted.second) {
+ throw LoopMultiAppearanceError(self->mod, GetRef(loop));
+}
+ }
+ // Step 2. gather loops to be reordered
Review comment:
Chatted with Hongyi again and we improved the algorithm again :-)
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r693402064
##
File path: src/tir/schedule/primitive/loop_transformation.cc
##
@@ -385,6 +511,116 @@ StmtSRef Fuse(ScheduleState self, const Array&
loop_srefs) {
return self->stmt2ref.at(new_stmt.get());
}
+void Reorder(ScheduleState self, const Array& ordered_loop_srefs) {
+ if (ordered_loop_srefs.empty() || ordered_loop_srefs.size() == 1) {
+return;
+ }
+ std::unordered_set 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(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 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()) {
+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(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 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(loop_sref));
+ const ForNode* inner_loop = TVM_SREF_TO_FOR(inner_loop,
GetRef(chain.back()));
+ if (outer_loop->body.get() != inner_loop) {
+throw LoopsNotAChainError(self->mod, GetRef(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 inner_vars;
Review comment:
```suggestion
std::unordered_set inner_vars;
inner_vars.reserve(chain.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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
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&
loop_srefs) {
return self->stmt2ref.at(new_stmt.get());
}
+void Reorder(ScheduleState self, const Array& ordered_loop_srefs) {
+ if (ordered_loop_srefs.empty() || ordered_loop_srefs.size() == 1) {
+return;
+ }
+ std::unordered_set 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(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 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()) {
+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(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 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(loop_sref));
+ const ForNode* inner_loop = TVM_SREF_TO_FOR(inner_loop,
GetRef(chain.back()));
+ if (outer_loop->body.get() != inner_loop) {
+throw LoopsNotAChainError(self->mod, GetRef(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 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()
+ : loop_sref->StmtAs();
+ObjectPtr n = make_object(*copy);
+if (new_loop.defined()) {
+ n->body = new_loop;
+} else {
+ n->body = loop_sref->StmtAs()->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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r693401580
##
File path: src/tir/schedule/primitive/loop_transformation.cc
##
@@ -385,6 +511,116 @@ StmtSRef Fuse(ScheduleState self, const Array&
loop_srefs) {
return self->stmt2ref.at(new_stmt.get());
}
+void Reorder(ScheduleState self, const Array& ordered_loop_srefs) {
+ if (ordered_loop_srefs.empty() || ordered_loop_srefs.size() == 1) {
+return;
+ }
+ std::unordered_set 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(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 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()) {
+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(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 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(loop_sref));
+ const ForNode* inner_loop = TVM_SREF_TO_FOR(inner_loop,
GetRef(chain.back()));
+ if (outer_loop->body.get() != inner_loop) {
+throw LoopsNotAChainError(self->mod, GetRef(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 inner_vars;
+ For new_loop;
Review comment:
Explicit null-initialization
```suggestion
For new_loop{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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
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&
loop_srefs) {
return self->stmt2ref.at(new_stmt.get());
}
+void Reorder(ScheduleState self, const Array& ordered_loop_srefs) {
+ if (ordered_loop_srefs.empty() || ordered_loop_srefs.size() == 1) {
+return;
+ }
+ std::unordered_set 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(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 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()) {
+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(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 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(loop_sref));
+ const ForNode* inner_loop = TVM_SREF_TO_FOR(inner_loop,
GetRef(chain.back()));
+ if (outer_loop->body.get() != inner_loop) {
+throw LoopsNotAChainError(self->mod, GetRef(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 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()
+ : loop_sref->StmtAs();
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();
--index;
} else {
copy = loop_sref->StmtAs();
}
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: commits-unsubscr...@tvm.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r693401171
##
File path: src/tir/schedule/primitive/loop_transformation.cc
##
@@ -385,6 +511,116 @@ StmtSRef Fuse(ScheduleState self, const Array&
loop_srefs) {
return self->stmt2ref.at(new_stmt.get());
}
+void Reorder(ScheduleState self, const Array& ordered_loop_srefs) {
+ if (ordered_loop_srefs.empty() || ordered_loop_srefs.size() == 1) {
+return;
+ }
+ std::unordered_set 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(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 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()) {
+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(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 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(loop_sref));
+ const ForNode* inner_loop = TVM_SREF_TO_FOR(inner_loop,
GetRef(chain.back()));
+ if (outer_loop->body.get() != inner_loop) {
+throw LoopsNotAChainError(self->mod, GetRef(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 inner_vars;
+ For new_loop;
+ int index = ordered_loop_srefs.size() - 1;
Review comment:
I know it is impossible for numerical underflow here, but we always
treat `.size()` really carefully :-)
```suggestion
int index = static_cast(ordered_loop_srefs.size()) - 1;
```
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r693400687
##
File path: src/tir/schedule/primitive/loop_transformation.cc
##
@@ -385,6 +511,116 @@ StmtSRef Fuse(ScheduleState self, const Array&
loop_srefs) {
return self->stmt2ref.at(new_stmt.get());
}
+void Reorder(ScheduleState self, const Array& ordered_loop_srefs) {
+ if (ordered_loop_srefs.empty() || ordered_loop_srefs.size() == 1) {
+return;
+ }
+ std::unordered_set 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(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 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()) {
+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(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) {
Review comment:
Check the lighter condition first
```suggestion
if (i == 0 && loop_srefs.count(v)) {
```
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r693400463
##
File path: src/tir/schedule/primitive/loop_transformation.cc
##
@@ -385,6 +511,116 @@ StmtSRef Fuse(ScheduleState self, const Array&
loop_srefs) {
return self->stmt2ref.at(new_stmt.get());
}
+void Reorder(ScheduleState self, const Array& ordered_loop_srefs) {
+ if (ordered_loop_srefs.empty() || ordered_loop_srefs.size() == 1) {
+return;
+ }
+ std::unordered_set 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(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 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()) {
+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(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 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(loop_sref));
+ const ForNode* inner_loop = TVM_SREF_TO_FOR(inner_loop,
GetRef(chain.back()));
+ if (outer_loop->body.get() != inner_loop) {
+throw LoopsNotAChainError(self->mod, GetRef(outer_loop),
+
LoopsNotAChainError::ProblemKind::kHaveNonSingleBranchStmt);
+ }
+}
+chain.push_back(loop_sref);
+if (loop_sref == top) {
+ break;
+}
+ }
Review comment:
```suggestion
for (const StmtSRefNode* loop_sref = bottom; loop_sref != top; ) {
const StmtSRefNode* parent_loop_sref = loop_sref->parent;
const ForNode* outer = parent_loop_sref->StmtAs();
const ForNode* inner = loop_sref->StmtAs();
ICHECK(outer != nullptr && inner != nullptr);
if (outer->body.get() != inner) {
throw LoopsNotAChainError(self->mod, GetRef(outer),
LoopsNotAChainError::ProblemKind::kHaveNonSingleBranchStmt);
}
chain.push_back(loop_sref);
loop_sref = parent_loop_sref;
}
chain.push_back(top);
```
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r693400173
##
File path: src/tir/schedule/primitive/loop_transformation.cc
##
@@ -385,6 +511,113 @@ StmtSRef Fuse(ScheduleState self, const Array&
loop_srefs) {
return self->stmt2ref.at(new_stmt.get());
}
+void Reorder(ScheduleState self, const Array& ordered_loop_srefs) {
+ std::unordered_set loop_srefs;
+ loop_srefs.reserve(ordered_loop_srefs.size());
+ if (ordered_loop_srefs.empty() || ordered_loop_srefs.size() == 1) {
+return;
+ }
+ // Step 1. check uniqueness
+ for (const StmtSRef& loop_sref : ordered_loop_srefs) {
+const ForNode* loop = TVM_SREF_TO_FOR(loop, loop_sref);
+// uniqueness check
+auto inserted = loop_srefs.insert(loop_sref.get());
+if (!inserted.second) {
+ throw LoopMultiAppearanceError(self->mod, GetRef(loop));
+}
+ }
+ // Step 2. gather loops to be reordered
+ // For each loop, traverse upwards along the parent pointer, 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
traverse 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 traverses
+ const StmtSRefNode* top = nullptr;
+ const StmtSRefNode* bottom = nullptr;
+ // Maps a parent sref to its child sref
+ std::unordered_map successor;
+ for (size_t i = 0; i < ordered_loop_srefs.size(); i++) {
+const StmtSRefNode* sref = ordered_loop_srefs[i].get();
+// if sref is not visited before, update `bottom`
+if (!successor.count(sref->parent)) {
+ bottom = sref;
+}
+while (true) {
+ // stop at blocknode
+ if (sref->stmt->IsInstance()) {
+if (i != 0) {
+ throw LoopsNotAChainError(self->mod, NullOpt,
+
LoopsNotAChainError::ProblemKind::kNotUnderAScope);
+} else {
+ break;
+}
+ }
+ const StmtSRefNode* parent_sref = sref->parent;
+ // stop at previously-visited loop
+ if (successor.count(parent_sref)) {
+if (successor[parent_sref] == sref) {
+ break;
+} else {
+ throw LoopsNotAChainError(self->mod, GetRef(parent_sref->stmt),
+
LoopsNotAChainError::ProblemKind::kHaveNonSingleBranchStmt);
+}
+ } else {
+successor[parent_sref] = sref;
+ }
+ // if it's the first traverse and the loop is in the input array, update
`top`
+ if (loop_srefs.count(sref) && i == 0) {
+top = sref;
+ }
+ sref = parent_sref;
+}
+ }
+ // Step 3. Check that loops are single-branch
+ const ForNode* outer_loop = TVM_SREF_TO_FOR(outer_loop,
GetRef(top));
+ for (const StmtSRefNode* loop_sref = top; loop_sref != bottom;) {
+loop_sref = successor[loop_sref];
+const ForNode* inner_loop = TVM_SREF_TO_FOR(inner_loop,
GetRef(loop_sref));
+if (outer_loop->body.get() != inner_loop) {
+ throw LoopsNotAChainError(self->mod, GetRef(outer_loop),
+
LoopsNotAChainError::ProblemKind::kHaveNonSingleBranchStmt);
+}
Review comment:
Okay I thought a bit and agree you are right in this particular case. We
dont need to add such a method for now, given the logic here is only a single
line, but in general we need to add `HasOnlyChild` some day
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
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&
loop_srefs) {
return self->stmt2ref.at(new_stmt.get());
}
+void Reorder(ScheduleState self, const Array& ordered_loop_srefs) {
+ if (ordered_loop_srefs.empty() || ordered_loop_srefs.size() == 1) {
+return;
+ }
+ std::unordered_set 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(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 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()) {
+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(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 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&
loop_srefs) {
return self->stmt2ref.at(new_stmt.get());
}
+void Reorder(ScheduleState self, const Array& ordered_loop_srefs) {
+ if (ordered_loop_srefs.empty() || ordered_loop_srefs.size() == 1) {
+return;
+ }
+ std::unordered_set 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(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 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()) {
+if (scope_block_visited) {
+ throw LoopsNotAChainError(self->mod, NullOpt,
+
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r693399446
##
File path: src/tir/schedule/primitive/loop_transformation.cc
##
@@ -385,6 +511,116 @@ StmtSRef Fuse(ScheduleState self, const Array&
loop_srefs) {
return self->stmt2ref.at(new_stmt.get());
}
+void Reorder(ScheduleState self, const Array& ordered_loop_srefs) {
+ if (ordered_loop_srefs.empty() || ordered_loop_srefs.size() == 1) {
+return;
+ }
+ std::unordered_set 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(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 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()) {
+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) {
Review comment:
shouldn't it be
```suggestion
if (v != bottom) {
```
Please add a unittest for it :-)
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r693399202
##
File path: src/tir/schedule/primitive/loop_transformation.cc
##
@@ -385,6 +511,116 @@ StmtSRef Fuse(ScheduleState self, const Array&
loop_srefs) {
return self->stmt2ref.at(new_stmt.get());
}
+void Reorder(ScheduleState self, const Array& ordered_loop_srefs) {
+ if (ordered_loop_srefs.empty() || ordered_loop_srefs.size() == 1) {
+return;
+ }
+ std::unordered_set 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);
Review comment:
move this into the if-clause - it's only used there.
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r693398936
##
File path: src/tir/schedule/primitive/loop_transformation.cc
##
@@ -385,6 +511,113 @@ StmtSRef Fuse(ScheduleState self, const Array&
loop_srefs) {
return self->stmt2ref.at(new_stmt.get());
}
+void Reorder(ScheduleState self, const Array& ordered_loop_srefs) {
+ std::unordered_set loop_srefs;
+ loop_srefs.reserve(ordered_loop_srefs.size());
+ if (ordered_loop_srefs.empty() || ordered_loop_srefs.size() == 1) {
+return;
+ }
+ // Step 1. check uniqueness
+ for (const StmtSRef& loop_sref : ordered_loop_srefs) {
+const ForNode* loop = TVM_SREF_TO_FOR(loop, loop_sref);
+// uniqueness check
+auto inserted = loop_srefs.insert(loop_sref.get());
+if (!inserted.second) {
+ throw LoopMultiAppearanceError(self->mod, GetRef(loop));
+}
+ }
+ // Step 2. gather loops to be reordered
+ // For each loop, traverse upwards along the parent pointer, 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
traverse 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 traverses
+ const StmtSRefNode* top = nullptr;
+ const StmtSRefNode* bottom = nullptr;
+ // Maps a parent sref to its child sref
+ std::unordered_map successor;
+ for (size_t i = 0; i < ordered_loop_srefs.size(); i++) {
+const StmtSRefNode* sref = ordered_loop_srefs[i].get();
+// if sref is not visited before, update `bottom`
+if (!successor.count(sref->parent)) {
+ bottom = sref;
+}
+while (true) {
+ // stop at blocknode
+ if (sref->stmt->IsInstance()) {
+if (i != 0) {
+ throw LoopsNotAChainError(self->mod, NullOpt,
+
LoopsNotAChainError::ProblemKind::kNotUnderAScope);
+} else {
+ break;
+}
+ }
+ const StmtSRefNode* parent_sref = sref->parent;
+ // stop at previously-visited loop
+ if (successor.count(parent_sref)) {
+if (successor[parent_sref] == sref) {
+ break;
+} else {
+ throw LoopsNotAChainError(self->mod, GetRef(parent_sref->stmt),
+
LoopsNotAChainError::ProblemKind::kHaveNonSingleBranchStmt);
+}
+ } else {
+successor[parent_sref] = sref;
+ }
+ // if it's the first traverse and the loop is in the input array, update
`top`
+ if (loop_srefs.count(sref) && i == 0) {
+top = sref;
+ }
+ sref = parent_sref;
+}
+ }
+ // Step 3. Check that loops are single-branch
+ const ForNode* outer_loop = TVM_SREF_TO_FOR(outer_loop,
GetRef(top));
+ for (const StmtSRefNode* loop_sref = top; loop_sref != bottom;) {
+loop_sref = successor[loop_sref];
+const ForNode* inner_loop = TVM_SREF_TO_FOR(inner_loop,
GetRef(loop_sref));
+if (outer_loop->body.get() != inner_loop) {
+ throw LoopsNotAChainError(self->mod, GetRef(outer_loop),
+
LoopsNotAChainError::ProblemKind::kHaveNonSingleBranchStmt);
+}
Review comment:
It is a utility function that is shared by several pieces of the
codebase, so it does make sense to me to give it a semantically meaningful name
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r693302382
##
File path: src/tir/schedule/primitive/loop_transformation.cc
##
@@ -385,6 +511,113 @@ StmtSRef Fuse(ScheduleState self, const Array&
loop_srefs) {
return self->stmt2ref.at(new_stmt.get());
}
+void Reorder(ScheduleState self, const Array& ordered_loop_srefs) {
+ std::unordered_set loop_srefs;
+ loop_srefs.reserve(ordered_loop_srefs.size());
+ if (ordered_loop_srefs.empty() || ordered_loop_srefs.size() == 1) {
+return;
+ }
+ // Step 1. check uniqueness
+ for (const StmtSRef& loop_sref : ordered_loop_srefs) {
+const ForNode* loop = TVM_SREF_TO_FOR(loop, loop_sref);
+// uniqueness check
+auto inserted = loop_srefs.insert(loop_sref.get());
+if (!inserted.second) {
+ throw LoopMultiAppearanceError(self->mod, GetRef(loop));
+}
+ }
+ // Step 2. gather loops to be reordered
+ // For each loop, traverse upwards along the parent pointer, 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
traverse 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 traverses
+ const StmtSRefNode* top = nullptr;
+ const StmtSRefNode* bottom = nullptr;
+ // Maps a parent sref to its child sref
+ std::unordered_map successor;
+ for (size_t i = 0; i < ordered_loop_srefs.size(); i++) {
+const StmtSRefNode* sref = ordered_loop_srefs[i].get();
+// if sref is not visited before, update `bottom`
+if (!successor.count(sref->parent)) {
+ bottom = sref;
+}
+while (true) {
+ // stop at blocknode
+ if (sref->stmt->IsInstance()) {
+if (i != 0) {
+ throw LoopsNotAChainError(self->mod, NullOpt,
+
LoopsNotAChainError::ProblemKind::kNotUnderAScope);
+} else {
+ break;
+}
+ }
+ const StmtSRefNode* parent_sref = sref->parent;
+ // stop at previously-visited loop
+ if (successor.count(parent_sref)) {
+if (successor[parent_sref] == sref) {
+ break;
+} else {
+ throw LoopsNotAChainError(self->mod, GetRef(parent_sref->stmt),
+
LoopsNotAChainError::ProblemKind::kHaveNonSingleBranchStmt);
+}
+ } else {
+successor[parent_sref] = sref;
+ }
+ // if it's the first traverse and the loop is in the input array, update
`top`
+ if (loop_srefs.count(sref) && i == 0) {
+top = sref;
+ }
+ sref = parent_sref;
+}
+ }
+ // Step 3. Check that loops are single-branch
+ const ForNode* outer_loop = TVM_SREF_TO_FOR(outer_loop,
GetRef(top));
+ for (const StmtSRefNode* loop_sref = top; loop_sref != bottom;) {
+loop_sref = successor[loop_sref];
+const ForNode* inner_loop = TVM_SREF_TO_FOR(inner_loop,
GetRef(loop_sref));
+if (outer_loop->body.get() != inner_loop) {
+ throw LoopsNotAChainError(self->mod, GetRef(outer_loop),
+
LoopsNotAChainError::ProblemKind::kHaveNonSingleBranchStmt);
+}
Review comment:
Abstract it into an analysis method `IsOnlyChildOnAST(Loop, Stmt)`
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r693260433
##
File path: src/tir/schedule/primitive/loop_transformation.cc
##
@@ -253,6 +302,83 @@ class WrongFactorProductError : public ScheduleError {
For loop_;
};
+class LoopMultiAppearanceError : public ScheduleError {
+ public:
+ explicit LoopMultiAppearanceError(IRModule mod, For loop) : mod_(mod),
loop_(std::move(loop)) {}
+
+ String FastErrorString() const final {
+return "ScheduleError: Some loop appears in the input array for multiple
times.";
+ }
+
+ String DetailRenderTemplate() const final {
+return "Loop {0} appears in the input array for multiple times.";
+ }
+
+ IRModule mod() const final { return mod_; }
+ Array LocationsOfInterest() const final { return {loop_}; }
+
+ IRModule mod_;
+ For loop_;
+};
+
+class LoopsNotALineError : public ScheduleError {
+ public:
+ enum class ProblemKind { kNotUnderAScope, kHaveNonSingleBranchStmt };
+
+ explicit LoopsNotALineError(IRModule mod, Optional problematic_loop,
ProblemKind kind)
+ : mod_(mod), problematic_loop_(std::move(problematic_loop)), kind_(kind)
{}
+
+ String FastErrorString() const final { return "ScheduleError: the loops are
not in a line"; }
Review comment:
"in a line" sound weird. Are you referring to "chain"?
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r691686504
##
File path: src/tir/schedule/primitive/loop_transformation.cc
##
@@ -385,6 +540,108 @@ StmtSRef Fuse(ScheduleState self, const Array&
loop_srefs) {
return self->stmt2ref.at(new_stmt.get());
}
+void Reorder(ScheduleState self, const Array& ordered_loop_srefs) {
+ std::unordered_set loop_srefs;
+ loop_srefs.reserve(ordered_loop_srefs.size());
+ if (ordered_loop_srefs.empty() || ordered_loop_srefs.size() == 1) {
+return;
+ }
+ // Step 1. check uniqueness
+ for (const StmtSRef loop_sref : ordered_loop_srefs) {
+const ForNode* loop = TVM_SREF_TO_FOR(loop, loop_sref);
+// uniqueness check
+auto inserted = loop_srefs.insert(loop_sref.get());
+if (!inserted.second) {
+ throw LoopMultiAppearanceError(self->mod, GetRef(loop));
+}
+ }
+ // Step 2. gather loops to be reordered
+ // The algorithm is to scan the inverse preorder of the whole loop tree in
the scope.
+ // For some Loop x, it is potentially in the reorder range if
+ // - x is in the reorder list
+ // - x has only one child which is a loop and is potentially in the
reorder range
+ // After the inverse DFS, we can know the exact reorder range
+ // `top` and `bottom` denote the boundary of the loop range that need
reordering
+ const StmtSRefNode* top = nullptr;
+ const StmtSRefNode* bottom = nullptr;
+ // Maps a parent sref to its child sref
+ std::unordered_map successor;
+ int n_loops_not_found = ordered_loop_srefs.size();
+ // Gather all the loops under the block scope
+ std::vector inverse_preorder_loops =
GetLoopsInversePreOrderUnderScope(
+ self, GetScopeRoot(self, ordered_loop_srefs[0],
/*require_stage_pipeline=*/true));
+ for (const StmtSRefNode* loop : inverse_preorder_loops) {
+bool is_in_reorder_list = loop_srefs.count(loop);
+bool has_successor_in_reorder_list = successor.count(loop);
+if (is_in_reorder_list || has_successor_in_reorder_list) {
+ const StmtSRefNode* parent = loop->parent;
+ // If the successor of `parent` exists, then `parent` can't be a
single-branch loop
+ auto inserted = successor.insert({parent, loop});
+ if (!inserted.second) {
+throw LoopsNotALineError(self->mod, GetRef(parent->stmt),
+ LoopsNotALineError::kHaveNonSingleBranchStmt);
+ }
+ // `bottom` is the first loop encountered
+ if (bottom == nullptr) {
+bottom = loop;
+ }
+ // `top` is the last loop encountered
+ if (is_in_reorder_list) {
+top = loop;
+--n_loops_not_found;
+ }
+}
+ }
Review comment:
I have some reservation on the overall design of the first two steps.
Ideally we do not need to visit the entire scope, and no need to use
complicated code to extra the relationship between these loop nests.
Here is what I am proposing to do:
1. Have a class called `LoopNest`
2. `LoopNest` is initialized by a list of loops
3. `LoopNest` stores a consecutive chain of loops, where each element is the
only child of the previous one in the list.
4. Reordering is basically permuting the loop nest
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r691580122
##
File path: src/tir/schedule/primitive/loop_transformation.cc
##
@@ -253,6 +277,137 @@ class WrongFactorProductError : public ScheduleError {
For loop_;
};
+class LoopMultiAppearanceError : public ScheduleError {
+ public:
+ explicit LoopMultiAppearanceError(IRModule mod, For loop)
+ : mod_(std::move(mod)), loop_(std::move(loop)) {}
+
+ String FastErrorString() const final {
+return "ScheduleError: Some loop appears in the input array for multiple
times.";
+ }
+
+ String DetailRenderTemplate() const final {
+return "Loop {0} appears in the input array for multiple times.";
+ }
+
+ IRModule mod() const final { return mod_; }
+ Array LocationsOfInterest() const final { return {loop_}; }
+
+ IRModule mod_;
+ For loop_;
+};
+
+class LoopsNotALineError : public ScheduleError {
+ public:
+ enum ProblemKind { kNotUnderAScope, kHaveNonSingleBranchStmt };
+
+ explicit LoopsNotALineError(IRModule mod, Optional problematic_loop,
ProblemKind kind)
+ : mod_(std::move(mod)), problematic_loop_(std::move(problematic_loop)),
kind_(kind) {}
+
+ String FastErrorString() const final { return "ScheduleError: the loops are
not in a line"; }
+
+ String DetailRenderTemplate() const final {
+std::stringstream ss;
+ss << "The loops are not in a line because";
+if (kind_ == kNotUnderAScope) {
+ ss << " they are not under the same scope.";
+} else {
+ ss << " there is a non-single-branch stmt in between. Problematic stmt:
{0}";
+}
+return ss.str();
+ }
+
+ IRModule mod() const final { return mod_; }
+ Array LocationsOfInterest() const final {
+if (kind_ == kNotUnderAScope) {
+ return {};
+} else {
+ ICHECK(problematic_loop_.defined());
+ return {problematic_loop_.value()};
+}
+ }
+
+ IRModule mod_;
+ Optional problematic_loop_;
+ ProblemKind kind_;
+};
+
+class DependentLoopError : public ScheduleError {
+ public:
+ explicit DependentLoopError(IRModule mod, For loop, String inner_var)
+ : mod_(std::move(mod)), loop_(std::move(loop)),
inner_var_(std::move(inner_var)) {}
+
+ String FastErrorString() const final {
+return "ScheduleError: An outer loop's `min` or `extent` is dependent on
an inner loop "
+ "in the new order";
+ }
+
+ String DetailRenderTemplate() const final {
+return "Outer Loop {0}'s `min` or `extent` is dependent on an inner loop "
+ inner_var_ +
+ " in the new order";
+ }
+
+ IRModule mod() const final { return mod_; }
+ Array LocationsOfInterest() const final { return {loop_}; }
+
+ IRModule mod_;
+ For loop_;
+ String inner_var_;
+};
+
+/*!
+ * \brief Collect all loops under a specific block scope in the inverse
pre-order
+ * \param self The state of the schedule
+ * \param root_block_sref the sref to the root of block scope
+ * \return The array of srefs of all loops under the block scope, in inverse
pre-order
+ */
+std::vector GetLoopsInversePreOrderUnderScope(
+const ScheduleState& self, const StmtSRef& root_block_sref) {
+ std::vector loops;
+ const BlockNode* root_block = TVM_SREF_TO_BLOCK(root_block, root_block_sref);
+ // Gather all the loops under parent_block
+ PreOrderVisit(root_block->body, [, self](const ObjectRef& node) {
+// Stops at a new BlockNode
+if (node->IsInstance()) {
+ return false;
+}
+// Collects every ForNode
+if (const auto* loop = node.as()) {
+ loops.push_back(self->stmt2ref.at(loop).operator->());
+}
+return true;
+ });
+ // Reverse to get inverse preorder
+ std::reverse(loops.begin(), loops.end());
+ return loops;
+}
+/*!
+ * \brief Check that all the blocks under the specific stmt have affine
bindings and only have
+ * data-parallel or reduction block iters
+ * \param self The state of the schedule
+ * \param sref The sref to the specific stmt
+ */
+void CheckBlockIterTypeAndAffineBinding(const ScheduleState& self, const
StmtSRefNode* sref) {
Review comment:
Move this into `BlockIterTypeError` and rename the error to
`BlockPropertyError`, where property includes affinity as well as iter types
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r691576602
##
File path: src/tir/schedule/primitive/loop_transformation.cc
##
@@ -253,6 +277,137 @@ class WrongFactorProductError : public ScheduleError {
For loop_;
};
+class LoopMultiAppearanceError : public ScheduleError {
+ public:
+ explicit LoopMultiAppearanceError(IRModule mod, For loop)
+ : mod_(std::move(mod)), loop_(std::move(loop)) {}
+
+ String FastErrorString() const final {
+return "ScheduleError: Some loop appears in the input array for multiple
times.";
+ }
+
+ String DetailRenderTemplate() const final {
+return "Loop {0} appears in the input array for multiple times.";
+ }
+
+ IRModule mod() const final { return mod_; }
+ Array LocationsOfInterest() const final { return {loop_}; }
+
+ IRModule mod_;
+ For loop_;
+};
+
+class LoopsNotALineError : public ScheduleError {
+ public:
+ enum ProblemKind { kNotUnderAScope, kHaveNonSingleBranchStmt };
Review comment:
use enum class instead
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r691552975
##
File path: src/tir/schedule/primitive/loop_transformation.cc
##
@@ -155,7 +177,7 @@ class HasAnnotationOrThreadBindingError : public
ScheduleError {
class OuterNotInnerParent : public ScheduleError {
public:
explicit OuterNotInnerParent(IRModule mod, For outer, For inner)
- : mod_(mod), outer_(std::move(outer)), inner_(std::move(inner)) {}
+ : mod_(std::move(mod)), outer_(std::move(outer)),
inner_(std::move(inner)) {}
Review comment:
You don't actually need this `std::move` here due to copy elision.
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r691550977
##
File path: src/tir/schedule/primitive.h
##
@@ -64,6 +64,21 @@ TVM_DLL Array Split(ScheduleState self, const
StmtSRef& loop_sref,
* \return The sref to the fused loop
*/
TVM_DLL StmtSRef Fuse(ScheduleState self, const Array& loop_srefs);
+/*!
+ * \brief Reorder a list of loops. It doesn't require the loops to be
consecutive.
+ * It requires:
+ * 1) The loops are in the same line. That means: the loops can be ordered to
[l_1, l_2, ... ,
+ * l_n] where l_i is an ancestor of l_{i+1} and there are only
single-branch loops between
+ * l_1 and l_n (which also indicates they are under the same scope).
+ * 2) In the new order, an outer loop cannot depend on inner loops.
+ * 3) The block below the loops have affine bindings and only have
data-parallel or reduction block
+ * iters
+ * 4) A loop cannot appear multiple times in the input array.
Review comment:
Update the docs
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r691550055
##
File path: python/tvm/tir/schedule/schedule.py
##
@@ -442,6 +442,64 @@ def after_split(a: ty.handle, b: ty.handle) -> None:
# that there is at most one None in `factors`
return _ffi_api.ScheduleSplit(self, loop, factors) # type: ignore #
pylint: disable=no-member
+def reorder(self, *loops: List[LoopRV]) -> None:
+"""
+Reorder a list of loops. It doesn't require the loops to be
consecutive.
+It requires:
+1) The loops are in the same line. That means: the loops can be
ordered to [l_1, l_2, ... ,
+l_n] where l_i is an ancestor of l_{i+1} and there are only
single-branch loops between
+l_1 and l_n (which also indicates they are under the same scope).
+2) In the new order, an outer loop cannot depend on inner loops.
+3) The block below the loops have affine bindings and only have
data-parallel or reduction
+block iters
+4) A loop cannot appear multiple times in the input array.
+
+Parameters
+--
+*loops : List[LoopRV]
Review comment:
To be consistent with the C++ API
```suggestion
*ordered_loops : List[LoopRV]
```
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r691549866
##
File path: python/tvm/tir/schedule/schedule.py
##
@@ -442,6 +442,64 @@ def after_split(a: ty.handle, b: ty.handle) -> None:
# that there is at most one None in `factors`
return _ffi_api.ScheduleSplit(self, loop, factors) # type: ignore #
pylint: disable=no-member
+def reorder(self, *loops: List[LoopRV]) -> None:
+"""
+Reorder a list of loops. It doesn't require the loops to be
consecutive.
+It requires:
+1) The loops are in the same line. That means: the loops can be
ordered to [l_1, l_2, ... ,
+l_n] where l_i is an ancestor of l_{i+1} and there are only
single-branch loops between
+l_1 and l_n (which also indicates they are under the same scope).
+2) In the new order, an outer loop cannot depend on inner loops.
+3) The block below the loops have affine bindings and only have
data-parallel or reduction
+block iters
+4) A loop cannot appear multiple times in the input array.
Review comment:
Update the docs
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767: URL: https://github.com/apache/tvm/pull/8767#discussion_r691549659 ## File path: python/tvm/tir/schedule/schedule.py ## @@ -442,6 +442,64 @@ def after_split(a: ty.handle, b: ty.handle) -> None: # that there is at most one None in `factors` return _ffi_api.ScheduleSplit(self, loop, factors) # type: ignore # pylint: disable=no-member +def reorder(self, *loops: List[LoopRV]) -> None: Review comment: To be consistent with the C++ API ```suggestion def reorder(self, *ordered_loops: List[LoopRV]) -> None: ``` -- 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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r691549171
##
File path: include/tvm/tir/schedule/schedule.h
##
@@ -219,6 +219,19 @@ class ScheduleNode : public runtime::Object {
* \return The new loops after split
*/
virtual Array Split(const LoopRV& loop_rv, const
Array>& factors) = 0;
+ /*!
+ * \brief Reorder a list of loops. It doesn't require the loops to be
consecutive.
+ * It requires:
+ * 1) The loops are in the same line. That means: the loops can be ordered
to [l_1, l_2, ... ,
+ * l_n] where l_i is an ancestor of l_{i+1} and there are only
single-branch loops between
+ * l_1 and l_n (which also indicates they are under the same scope).
+ * 2) In the new order, an outer loop cannot depend on inner loops.
+ * 3) The block below the loops have affine bindings and only have
data-parallel or reduction
+ * block iters
+ * 4) A loop cannot appear multiple times in the input array.
Review comment:
```suggestion
* 4) No duplicated loops are allowed in the arguments.
```
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r691548739
##
File path: include/tvm/tir/schedule/schedule.h
##
@@ -219,6 +219,19 @@ class ScheduleNode : public runtime::Object {
* \return The new loops after split
*/
virtual Array Split(const LoopRV& loop_rv, const
Array>& factors) = 0;
+ /*!
+ * \brief Reorder a list of loops. It doesn't require the loops to be
consecutive.
+ * It requires:
+ * 1) The loops are in the same line. That means: the loops can be ordered
to [l_1, l_2, ... ,
+ * l_n] where l_i is an ancestor of l_{i+1} and there are only
single-branch loops between
+ * l_1 and l_n (which also indicates they are under the same scope).
+ * 2) In the new order, an outer loop cannot depend on inner loops.
+ * 3) The block below the loops have affine bindings and only have
data-parallel or reduction
+ * block iters
Review comment:
```suggestion
* 3) For every block under the loop nests, its block binding must be
affine, and the block variables must be either data parallel or reduction.
```
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r691548093
##
File path: include/tvm/tir/schedule/schedule.h
##
@@ -219,6 +219,19 @@ class ScheduleNode : public runtime::Object {
* \return The new loops after split
*/
virtual Array Split(const LoopRV& loop_rv, const
Array>& factors) = 0;
+ /*!
+ * \brief Reorder a list of loops. It doesn't require the loops to be
consecutive.
+ * It requires:
+ * 1) The loops are in the same line. That means: the loops can be ordered
to [l_1, l_2, ... ,
+ * l_n] where l_i is an ancestor of l_{i+1} and there are only
single-branch loops between
+ * l_1 and l_n (which also indicates they are under the same scope).
+ * 2) In the new order, an outer loop cannot depend on inner loops.
Review comment:
```suggestion
* 2) After reordering, the domain of an outer loop cannot depend on any
of the inner loops
```
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767:
URL: https://github.com/apache/tvm/pull/8767#discussion_r691547322
##
File path: include/tvm/tir/schedule/schedule.h
##
@@ -219,6 +219,19 @@ class ScheduleNode : public runtime::Object {
* \return The new loops after split
*/
virtual Array Split(const LoopRV& loop_rv, const
Array>& factors) = 0;
+ /*!
+ * \brief Reorder a list of loops. It doesn't require the loops to be
consecutive.
+ * It requires:
+ * 1) The loops are in the same line. That means: the loops can be ordered
to [l_1, l_2, ... ,
+ * l_n] where l_i is an ancestor of l_{i+1} and there are only
single-branch loops between
+ * l_1 and l_n (which also indicates they are under the same scope).
Review comment:
```suggestion
* 1) The loops are in the same line. That means: the loops can be ordered
to [l_1, l_2, ... ,
* l_n] where l_i is the parent of l_{i+1} in the AST, and l_{i + 1}
is always the only child of l_i.
```
--
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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767: URL: https://github.com/apache/tvm/pull/8767#discussion_r690932639 ## File path: src/tir/schedule/analysis.h ## @@ -132,6 +132,15 @@ void CheckReductionBlock(const ScheduleState& self, const StmtSRef& block_sref, bool IsAffineBinding(const BlockRealize& realize, const Map& loop_var_ranges, arith::Analyzer* analyzer); +/*! + * \brief Check whether a block has an affine binding using the cached flag, and throw an exception + * if the block does not have an affine binding. + * \param self The schedule state + * \param block The block to be checked + * \throw ScheduleError If the input block does not have an affine binding + */ +void CheckAffineBinding(const ScheduleState& self, Block block); Review comment: Given the method is not consuming the block in most of the cases ```suggestion void CheckAffineBinding(const ScheduleState& self, const Block& block); ``` -- 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
[GitHub] [tvm] junrushao1994 commented on a change in pull request #8767: [TensorIR][M2a] Reorder
junrushao1994 commented on a change in pull request #8767: URL: https://github.com/apache/tvm/pull/8767#discussion_r690932639 ## File path: src/tir/schedule/analysis.h ## @@ -132,6 +132,15 @@ void CheckReductionBlock(const ScheduleState& self, const StmtSRef& block_sref, bool IsAffineBinding(const BlockRealize& realize, const Map& loop_var_ranges, arith::Analyzer* analyzer); +/*! + * \brief Check whether a block has an affine binding using the cached flag, and throw an exception + * if the block does not have an affine binding. + * \param self The schedule state + * \param block The block to be checked + * \throw ScheduleError If the input block does not have an affine binding + */ +void CheckAffineBinding(const ScheduleState& self, Block block); Review comment: Given the method is not consuming the block in most of the cases ```suggestion void CheckAffineBinding(const ScheduleState& self, const Block& block); ``` -- 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
