add function top sort in preparation for unroll
MODIFY
ir/function.cpp
ir/function.cpp
@@ -112,6 +112,11 @@ const BasicBlock* Function::getBBIfExists(std::string_view name) const {
return I != BBs.end() ? &I->second : nullptr;
}
+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());

MODIFY
ir/function.h
ir/function.h
@@ -102,6 +102,8 @@ public:
BasicBlock& getBB(std::string_view name, bool push_front = false);
const BasicBlock& getBB(std::string_view name) const;
const BasicBlock* getBBIfExists(std::string_view name) const;
+
+ void setBBOrder(std::vector<BasicBlock*> &&BB_order);
void removeBB(BasicBlock &BB);
void addConstant(std::unique_ptr<Value> &&c);

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>
#include <map>
#include <set>
#include <sstream>
+#include <unordered_map>
using namespace IR;
using namespace smt;
@@ -1133,6 +1135,32 @@ 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);
@@ -1185,6 +1213,11 @@ void Transform::preprocess() {
: src.getGlobalVarNames());
} while (changed);
}
+
+ if (0) {
+ top_sort(src);
+ top_sort(tgt);
+ }
}
void Transform::print(ostream &os, const TransformPrintOpts &opt) const {

add function top sort in preparation for unroll