Unrolling without handling phis
MODIFY
ir/function.cpp
ir/function.cpp
#include "ir/instr.h"
#include "util/errors.h"
#include "util/unionfind.h"
-#include <fstream>
using namespace smt;
using namespace util;
@@ -48,6 +47,13 @@ JumpInstr::it_helper BasicBlock::targets() const {
return {};
}
+void BasicBlock::replaceTargetWith(const BasicBlock *from,
+ const BasicBlock *to) {
+ if (auto jump = dynamic_cast<JumpInstr*>(&this->back())) {
+ jump->replaceTargetWith(from, to);
+ }
+}
+
unique_ptr<BasicBlock> BasicBlock::dup(const string &suffix) const {
auto newbb = make_unique<BasicBlock>(name + suffix);
for (auto &i : instrs()) {
@@ -92,6 +98,24 @@ void Function::fixupTypes(const Model &m) {
}
}
+BasicBlock& Function::cloneBB(const BasicBlock &BB, const string &suffix,
+ unordered_map<const Value*, Value*> &vmap) {
+ string bb_name = BB.getName() + suffix;
+ auto &newbb = getBB(bb_name, false);
+ for (auto &i : BB.instrs()) {
+ auto d = i.dup(suffix);
+ for (auto &op : d->operands()) {
+ auto it = vmap.find(op);
+ if (it != vmap.end()) {
+ d->rauw(*op, *it->second);
+ }
+ }
+ vmap[&i] = d.get();
+ newbb.addInstr(move(d));
+ }
+ return newbb;
+}
+
BasicBlock& Function::getBB(string_view name, bool push_front) {
auto p = BBs.try_emplace(string(name), name);
if (p.second) {
@@ -240,7 +264,8 @@ void Function::instr_iterator::next_bb() {
void Function::instr_iterator::operator++(void) {
if (++II != IE)
return;
- ++BBI;
+ while (++BBI != BBE && (*BBI)->empty())
+ ;
next_bb();
}
@@ -302,8 +327,94 @@ void Function::unroll(unsigned k) {
if (k == 0)
return;
LoopAnalysis la(*this);
- ofstream out("a.gv");
- la.printDot(out);
+
+ auto &roots = la.getRoots();
+ if (roots.empty())
+ return;
+
+ auto &nodes = la.getHeaderNodes();
+
+ BasicBlock &sink = getBB("#sink");
+
+ vector<pair<const BasicBlock*, bool>> worklist;
+
+ for (auto &root : roots) {
+ worklist.emplace_back(root, false);
+ }
+
+ while (!worklist.empty()) {
+ auto &[H, flag] = worklist.back();
+ if (!flag) {
+ flag = true;
+ auto tgts = la.getChildren(H);
+ for (; tgts.first != tgts.second; ++tgts.first)
+ worklist.emplace_back(tgts.first->second, false);
+ continue;
+ }
+
+ worklist.pop_back();
+
+ auto header = const_cast<BasicBlock*>(H);
+ auto &bb_nodes = nodes[header];
+ map<const BasicBlock*, vector<const BasicBlock*>> bbmap;
+ for (auto &&bb_i : bb_nodes) {
+ bbmap[bb_i].push_back(bb_i);
+ }
+
+ // clone bbs
+ unordered_map<const Value*, Value*> vmap;
+ for (unsigned unroll = 1; unroll <= k; ++unroll) {
+ for (auto &&bb_i : bb_nodes) {
+ string twine = "_" + header->getName() + "@" + to_string(unroll);
+ bbmap[bb_i].push_back(&cloneBB(*bb_i, twine, vmap));
+ }
+ }
+
+ unordered_set nodes_set(bb_nodes.begin(), bb_nodes.end());
+
+ for (auto &&bb_i : bb_nodes) {
+ // rewire jumps
+ for (unsigned unroll = 0; unroll <= k; ++unroll) {
+ auto cloned = const_cast<BasicBlock*>(bbmap[bb_i][unroll]);
+ map<const BasicBlock*, const BasicBlock*> replacement;
+ for (auto &tgt : cloned->targets()) {
+
+ // do not touch exit point
+ if (!nodes_set.count(&tgt))
+ continue;
+
+ const BasicBlock *to = nullptr;
+ // handle backedge
+ if (&tgt == header) {
+ if (unroll == k)
+ to = &sink;
+ else
+ to = bbmap[&tgt][unroll + 1];
+ }
+ // handle targets inside loop
+ else
+ to = bbmap[&tgt][unroll];
+
+ replacement[&tgt] = to;
+ }
+ for (auto &[from, to] : replacement)
+ cloned->replaceTargetWith(from, to);
+ }
+ }
+
+ // TODO: handle phis
+
+ // add cloned BBs to each ancestors of loop H
+ const BasicBlock *root = H;
+ while (la.hasParent(root)) {
+ auto next = la.getParent(root);
+ auto &ancestor_nodes = nodes[next];
+ for (auto &[_, v] : bbmap)
+ ancestor_nodes.insert(ancestor_nodes.end(), v.begin() + 1, v.end());
+ root = next;
+ }
+ }
+ // TODO: topsort the function
}
void Function::print(ostream &os, bool print_header) const {
@@ -568,6 +679,44 @@ void LoopAnalysis::analysis() {
uf.merge(x, w);
}
}
+
+ if (type[0] != NodeType::nonheader)
+ tree_roots.push_back(node[0]);
+
+ for (unsigned i = 0; i < bb_count; ++i) {
+ if (type[i] != NodeType::nonheader)
+ header_nodes[node[i]].push_back(node[i]);
+ }
+
+ for (unsigned i = 0; i < bb_count; ++i) {
+ if (type[0] == NodeType::nonheader && header[i] == 0 &&
+ type[i] != NodeType::nonheader)
+ tree_roots.push_back(node[i]);
+
+ // populate header_nodes
+ unsigned root = i;
+ while (header[root] != 0) {
+ header_nodes[node[header[root]]].push_back(node[i]);
+ root = header[root];
+ }
+
+ // populate edges in nested tree
+ if (type[i] != NodeType::nonheader &&
+ type[header[i]] != NodeType::nonheader) {
+ tree_topdown.emplace(node[header[i]], node[i]);
+ tree_bottomup.emplace(node[i], node[header[i]]);
+ }
+ }
+
+ // sort nodes with DFST pre-order so that BB cloning won't break dominance
+ for (auto &[bb, nodes] : header_nodes) {
+ (void) bb;
+ sort(nodes.begin(), nodes.end(),
+ [&](const BasicBlock *a, const BasicBlock *b) -> bool {
+ return number[a] < number[b];
+ }
+ );
+ }
}
void LoopAnalysis::printDot(ostream &os) const {

MODIFY
ir/function.h
ir/function.h
@@ -46,6 +46,7 @@ public:
bool empty() const { return m_instrs.empty(); }
JumpInstr::it_helper targets() const;
+ void replaceTargetWith(const BasicBlock *from, const BasicBlock *to);
std::unique_ptr<BasicBlock> dup(const std::string &suffix) const;
@@ -100,6 +101,8 @@ public:
const BasicBlock& getFirstBB() const { return *BB_order[0]; }
BasicBlock& getFirstBB() { return *BB_order[0]; }
BasicBlock& getBB(std::string_view name, bool push_front = false);
+ BasicBlock& cloneBB(const BasicBlock &BB, const std::string &suffix,
+ std::unordered_map<const Value*, Value*> &vmap);
const BasicBlock& getBB(std::string_view name) const;
const BasicBlock* getBBIfExists(std::string_view name) const;
@@ -240,9 +243,28 @@ class LoopAnalysis final {
std::vector<unsigned> header;
enum NodeType { nonheader, self, reducible, irreducible };
std::vector<NodeType> type;
+ std::map<const BasicBlock*, std::vector<const BasicBlock*>> header_nodes;
+ std::multimap<const BasicBlock*, const BasicBlock*> tree_topdown;
+ std::map<const BasicBlock*, const BasicBlock*> tree_bottomup;
+ std::vector<const BasicBlock*> tree_roots;
void analysis();
public:
LoopAnalysis(Function &f) : f(f), cfg(f) { analysis(); }
+ std::map<const BasicBlock*, std::vector<const BasicBlock*>>&
+ getHeaderNodes() { return header_nodes; }
+ const std::vector<const BasicBlock*>& getRoots() const {
+ return std::move(tree_roots);
+ }
+ auto getChildren(const BasicBlock *bb) const {
+ return tree_topdown.equal_range(bb);
+ }
+ bool hasParent(const BasicBlock *bb) const {
+ return tree_bottomup.count(bb);
+ }
+ const BasicBlock* getParent(const BasicBlock *bb) const {
+ return tree_bottomup.at(bb);
+ }
+
void printDot(std::ostream &os) const;
};

MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -2114,7 +2114,7 @@ const BasicBlock& JumpInstr::target_iterator::operator*() const {
return idx == 0 ? br->getTrue() : *br->getFalse();
if (auto sw = dynamic_cast<Switch*>(instr))
- return idx == 0 ? sw->getDefault() : sw->getTarget(idx-1).second;
+ return idx == 0 ? *sw->getDefault() : *sw->getTarget(idx-1).second;
UNREACHABLE();
}
@@ -2134,6 +2134,13 @@ JumpInstr::target_iterator JumpInstr::it_helper::end() const {
}
+void Branch::replaceTargetWith(const BasicBlock *from, const BasicBlock *to) {
+ if (dst_true == from)
+ dst_true = to;
+ if (dst_false == from)
+ dst_false = to;
+}
+
vector<Value*> Branch::operands() const {
if (cond)
return { cond };
@@ -2148,7 +2155,7 @@ void Branch::print(ostream &os) const {
os << "br ";
if (cond)
os << *cond << ", ";
- os << "label " << dst_true.getName();
+ os << "label " << dst_true->getName();
if (dst_false)
os << ", label " << dst_false->getName();
}
@@ -2156,9 +2163,9 @@ void Branch::print(ostream &os) const {
StateValue Branch::toSMT(State &s) const {
if (cond) {
auto &c = s.getAndAddPoisonUB(*cond, true);
- s.addCondJump(c.value, dst_true, *dst_false);
+ s.addCondJump(c.value, *dst_true, *dst_false);
} else {
- s.addJump(dst_true);
+ s.addJump(*dst_true);
}
return {};
}
@@ -2171,13 +2178,23 @@ expr Branch::getTypeConstraints(const Function &f) const {
unique_ptr<Instr> Branch::dup(const string &suffix) const {
if (dst_false)
- return make_unique<Branch>(*cond, dst_true, *dst_false);
- return make_unique<Branch>(dst_true);
+ return make_unique<Branch>(*cond, *dst_true, *dst_false);
+ return make_unique<Branch>(*dst_true);
}
void Switch::addTarget(Value &val, const BasicBlock &target) {
- targets.emplace_back(&val, target);
+ targets.emplace_back(&val, &target);
+}
+
+void Switch::replaceTargetWith(const BasicBlock *from, const BasicBlock *to) {
+ if (default_target == from)
+ default_target = to;
+
+ for (auto &[_, bb] : targets) {
+ if (bb == from)
+ bb = to;
+ }
}
vector<Value*> Switch::operands() const {
@@ -2198,9 +2215,9 @@ void Switch::rauw(const Value &what, Value &with) {
}
void Switch::print(ostream &os) const {
- os << "switch " << *value << ", label " << default_target.getName() << " [\n";
+ os << "switch " << *value << ", label " << default_target->getName() << " [\n";
for (auto &[val, target] : targets) {
- os << " " << *val << ", label " << target.getName() << '\n';
+ os << " " << *val << ", label " << target->getName() << '\n';
}
os << " ]";
}
@@ -2214,10 +2231,10 @@ StateValue Switch::toSMT(State &s) const {
assert(target.non_poison.isTrue());
expr cmp = val.value == target.value;
default_cond &= !cmp;
- s.addJump(move(cmp), bb);
+ s.addJump(move(cmp), *bb);
}
- s.addJump(move(default_cond), default_target);
+ s.addJump(move(default_cond), *default_target);
s.addUB(expr(false));
return {};
}
@@ -2231,9 +2248,9 @@ expr Switch::getTypeConstraints(const Function &f) const {
}
unique_ptr<Instr> Switch::dup(const string &suffix) const {
- auto sw = make_unique<Switch>(*value, default_target);
+ auto sw = make_unique<Switch>(*value, *default_target);
for (auto &[value_cond, bb] : targets) {
- sw->addTarget(*value_cond, bb);
+ sw->addTarget(*value_cond, *bb);
}
return sw;
}

MODIFY
ir/instr.h
ir/instr.h
@@ -328,21 +328,26 @@ public:
target_iterator end() const;
};
it_helper targets() { return this; }
+ virtual void replaceTargetWith(const BasicBlock *From,
+ const BasicBlock *To) = 0;
};
class Branch final : public JumpInstr {
Value *cond = nullptr;
- const BasicBlock &dst_true, *dst_false = nullptr;
+ const BasicBlock *dst_true, *dst_false = nullptr;
public:
- Branch(const BasicBlock &dst) : JumpInstr(Type::voidTy, "br"), dst_true(dst) {}
+ Branch(const BasicBlock &dst)
+ : JumpInstr(Type::voidTy, "br"), dst_true(&dst) {}
Branch(Value &cond, const BasicBlock &dst_true, const BasicBlock &dst_false)
- : JumpInstr(Type::voidTy, "br"), cond(&cond), dst_true(dst_true),
+ : JumpInstr(Type::voidTy, "br"), cond(&cond), dst_true(&dst_true),
dst_false(&dst_false) {}
- auto& getTrue() const { return dst_true; }
+ auto& getTrue() const { return *dst_true; }
auto getFalse() const { return dst_false; }
+
+ void replaceTargetWith(const BasicBlock *F, const BasicBlock *T) override;
std::vector<Value*> operands() const override;
void rauw(const Value &what, Value &with) override;
void print(std::ostream &os) const override;
@@ -354,13 +359,13 @@ public:
class Switch final : public JumpInstr {
Value *value;
- const BasicBlock &default_target;
- std::vector<std::pair<Value*, const BasicBlock&>> targets;
+ const BasicBlock *default_target;
+ std::vector<std::pair<Value*, const BasicBlock*>> targets;
public:
Switch(Value &value, const BasicBlock &default_target)
: JumpInstr(Type::voidTy, "switch"), value(&value),
- default_target(default_target) {}
+ default_target(&default_target) {}
void addTarget(Value &val, const BasicBlock &target);
@@ -368,6 +373,7 @@ public:
auto& getTarget(unsigned i) const { return targets[i]; }
auto& getDefault() const { return default_target; }
+ void replaceTargetWith(const BasicBlock *F, const BasicBlock *T) override;
std::vector<Value*> operands() const override;
void rauw(const Value &what, Value &with) override;
void print(std::ostream &os) const override;

MODIFY
tools/alive-exec.cpp
tools/alive-exec.cpp
@@ -170,7 +170,7 @@ static void execFunction(llvm::Function &F, llvm::Triple &triple,
ofstream fileDom(f.getName() + ".dom.dot");
IR::DomTree(f, cfg).printDot(fileDom);
}
- Func->unroll(opt_unrolling_factor);
+ config::src_unroll_cnt = opt_unrolling_factor;
Transform t;
t.src = move(*Func);

MODIFY
tools/alive-tv.cpp
tools/alive-tv.cpp
@@ -291,7 +291,6 @@ static void compareFunctions(llvm::Function &F1, llvm::Function &F2,
++errorCount;
return;
}
- Func1->unroll(opt_src_unrolling_factor);
auto Func2 = llvm2alive(F2, llvm::TargetLibraryInfoWrapperPass(targetTriple)
.getTLI(F2), Func1->getGlobalVarNames());
@@ -301,7 +300,6 @@ static void compareFunctions(llvm::Function &F1, llvm::Function &F2,
++errorCount;
return;
}
- Func2->unroll(opt_tgt_unrolling_factor);
smt_init->reset();
Transform t;
@@ -439,6 +437,8 @@ convenient way to demonstrate an existing optimizer bug.
config::disable_undef_input = opt_disable_undef;
config::disable_poison_input = opt_disable_poison;
config::debug = opt_debug;
+ config::src_unroll_cnt = opt_src_unrolling_factor;
+ config::tgt_unroll_cnt = opt_tgt_unrolling_factor;
if (opt_smt_log)
smt::start_logging();

MODIFY
tools/transform.cpp
tools/transform.cpp
@@ -1214,6 +1214,9 @@ void Transform::preprocess() {
} while (changed);
}
+ src.unroll(config::src_unroll_cnt);
+ tgt.unroll(config::tgt_unroll_cnt);
+
if (0) {
top_sort(src);
top_sort(tgt);

MODIFY
tv/tv.cpp
tv/tv.cpp
@@ -152,6 +152,16 @@ llvm::cl::opt<bool> opt_elapsed_time(
llvm::cl::desc("Print the elapsed time"),
llvm::cl::cat(TVOptions), llvm::cl::init(false));
+llvm::cl::opt<unsigned> opt_src_unrolling_factor(
+ "tv-src-unroll",
+ llvm::cl::desc("Unrolling factor for src function (default=0)"),
+ llvm::cl::init(0));
+
+llvm::cl::opt<unsigned> opt_tgt_unrolling_factor(
+ "tv-tgt-unroll",
+ llvm::cl::desc("Unrolling factor for tgt function (default=0)"),
+ llvm::cl::init(0));
+
struct FnInfo {
Function fn;
unsigned order;
@@ -360,6 +370,8 @@ struct TVPass final : public llvm::FunctionPass {
config::disable_undef_input = opt_disable_undef_input;
config::disable_poison_input = opt_disable_poison_input;
config::debug = opt_debug;
+ config::src_unroll_cnt = opt_src_unrolling_factor;
+ config::tgt_unroll_cnt = opt_tgt_unrolling_factor;
llvm_util::omit_array_size = opt_omit_array_size;
llvm_util_init.emplace(*out, module.getDataLayout());

MODIFY
util/config.cpp
util/config.cpp
@@ -16,6 +16,8 @@ bool io_nobuiltin = false;
bool disable_poison_input = false;
bool disable_undef_input = false;
bool debug = false;
+unsigned src_unroll_cnt = 0;
+unsigned tgt_unroll_cnt = 0;
ostream &dbg() {
return *debug_os;

MODIFY
util/config.h
util/config.h
@@ -19,6 +19,10 @@ extern bool disable_undef_input;
extern bool debug;
+extern unsigned src_unroll_cnt;
+
+extern unsigned tgt_unroll_cnt;
+
std::ostream &dbg();
void set_debug(std::ostream &os);

Unrolling without handling phis (#510)