do top sort after unroll
MODIFY
ir/function.cpp
ir/function.cpp
#include "ir/function.h"
#include "ir/instr.h"
#include "util/errors.h"
+#include "util/sort.h"
#include "util/unionfind.h"
#include <fstream>
#include <set>
@@ -139,11 +140,6 @@ BasicBlock& Function::cloneBB(const BasicBlock &BB, const string &suffix,
return newbb;
}
-void Function::setBBOrder(vector<BasicBlock*> &&BBs) {
- assert(BBs.size() == BB_order.size());
- BB_order = move(BBs);
-}
-
void Function::removeBB(BasicBlock &BB) {
BBs.erase(BB.getName());
@@ -326,6 +322,34 @@ bool Function::removeUnusedStuff(const multimap<Value*, Value*> &users,
return changed;
}
+void Function::topSort() {
+ auto &bbs = getBBs();
+ edgesTy edges(bbs.size());
+ unordered_map<const BasicBlock*, unsigned> bb_map;
+
+ unsigned i = 0;
+ for (auto bb : bbs) {
+ bb_map.emplace(bb, i++);
+ }
+
+ i = 0;
+ for (auto bb : bbs) {
+ for (auto &dst : bb->targets()) {
+ edges[i].emplace(bb_map.at(&dst));
+ }
+ ++i;
+ }
+
+ vector<BasicBlock*> sorted_bbs;
+ sorted_bbs.reserve(bbs.size());
+ for (auto v : util::top_sort(edges)) {
+ sorted_bbs.emplace_back(bbs[v]);
+ }
+
+ assert(sorted_bbs.size() == BB_order.size());
+ BB_order = move(sorted_bbs);
+}
+
void Function::unroll(unsigned k) {
if (k == 0)
return;
@@ -423,7 +447,8 @@ void Function::unroll(unsigned k) {
// TODO: handle phis
}
- // TODO: topsort the function
+
+ topSort();
}
void Function::print(ostream &os, bool print_header) const {

MODIFY
ir/function.h
ir/function.h
@@ -106,7 +106,6 @@ public:
BasicBlock& cloneBB(const BasicBlock &BB, const std::string &suffix,
std::unordered_map<const Value*, Value*> &vmap);
- void setBBOrder(std::vector<BasicBlock*> &&BB_order);
void removeBB(BasicBlock &BB);
void addConstant(std::unique_ptr<Value> &&c);
@@ -173,6 +172,7 @@ public:
bool removeUnusedStuff(const std::multimap<Value*, Value*> &users,
const std::vector<std::string_view> &src_glbs);
+ void topSort();
void unroll(unsigned k);
void print(std::ostream &os, bool print_header = true) const;

MODIFY
tools/transform.cpp
tools/transform.cpp
#include "smt/solver.h"
#include "util/config.h"
#include "util/errors.h"
-#include "util/sort.h"
#include "util/stopwatch.h"
#include "util/symexec.h"
#include <algorithm>
@@ -1135,32 +1134,6 @@ static void remove_unreachable_bbs(Function &f) {
}
}
-static void top_sort(Function &f) {
- auto &bbs = f.getBBs();
- edgesTy edges(bbs.size());
- unordered_map<const BasicBlock*, unsigned> bb_map;
-
- unsigned i = 0;
- for (auto bb : bbs) {
- bb_map.emplace(bb, i++);
- }
-
- i = 0;
- for (auto bb : bbs) {
- for (auto &dst : bb->targets()) {
- edges[i].emplace(bb_map.at(&dst));
- }
- ++i;
- }
-
- vector<BasicBlock*> sorted_bbs;
- sorted_bbs.reserve(bbs.size());
- for (auto v : util::top_sort(edges)) {
- sorted_bbs.emplace_back(bbs[v]);
- }
- f.setBBOrder(move(sorted_bbs));
-}
-
void Transform::preprocess() {
remove_unreachable_bbs(src);
remove_unreachable_bbs(tgt);
@@ -1216,11 +1189,6 @@ void Transform::preprocess() {
src.unroll(config::src_unroll_cnt);
tgt.unroll(config::tgt_unroll_cnt);
-
- if (0) {
- top_sort(src);
- top_sort(tgt);
- }
}
void Transform::print(ostream &os, const TransformPrintOpts &opt) const {

do top sort after unroll