stub CFG functionality & add dot printer
MODIFY
ir/function.cpp
ir/function.cpp
@@ -91,9 +91,9 @@ void Function::addInput(unique_ptr<Input> &&i) {
}
Function::instr_iterator::
-instr_iterator(vector<BasicBlock*>::const_iterator BBI,
- vector<BasicBlock*>::const_iterator BBE)
- : BBI(BBI), BBE(BBE) {
+instr_iterator(vector<BasicBlock*>::const_iterator &&BBI,
+ vector<BasicBlock*>::const_iterator &&BBE)
+ : BBI(move(BBI)), BBE(move(BBE)) {
next_bb();
}
@@ -147,4 +147,71 @@ ostream& operator<<(ostream &os, const Function &f) {
return os;
}
+
+void CFG::edge_iterator::next() {
+ // jump to next BB with a terminator that is not a return instruction
+ while (it != end && dynamic_cast<Return*>(&(*it)->back())) {
+ ++it;
+ }
+}
+
+CFG::edge_iterator::edge_iterator(vector<BasicBlock*>::iterator &&it,
+ vector<BasicBlock*>::iterator &&end)
+ : it(move(it)), end(move(end)) {
+ next();
+}
+
+tuple<const BasicBlock&, const BasicBlock&, const Instr&>
+ CFG::edge_iterator::operator*() const {
+ const BasicBlock *dst;
+ auto instr = &(*it)->back();
+ if (auto br = dynamic_cast<Branch*>(instr)) {
+ dst = idx == 0 ? &br->getTrue() : br->getFalse();
+ } else if (auto sw = dynamic_cast<Switch*>(instr)) {
+ dst = idx == 0 ? &sw->getDefault() : &sw->getTarget(idx-1).second;
+ } else {
+ UNREACHABLE();
+ }
+ return { **it, *dst, *instr };
+}
+
+void CFG::edge_iterator::operator++(void) {
+ auto instr = &(*it)->back();
+ auto inc = [&](bool next_bb) {
+ if (next_bb) {
+ idx = 0;
+ ++it;
+ next();
+ } else {
+ ++idx;
+ }
+ };
+
+ if (auto br = dynamic_cast<Branch*>(instr)) {
+ inc(idx > 0 || !br->getFalse());
+ } else if (auto sw = dynamic_cast<Switch*>(instr)) {
+ inc(idx == sw->getNumTargets());
+ } else {
+ UNREACHABLE();
+ }
+}
+
+static string_view bb_dot_name(const string &name) {
+ if (name[0] == '%')
+ return string_view(name).substr(1);
+ return name;
+}
+
+void CFG::printDot(ostream &os) const {
+ os << "digraph {\n"
+ "\"" << bb_dot_name(f.getBBs()[0]->getName()) << "\" [shape=box];\n";
+
+ for (const auto &[src, dst, instr] : *this) {
+ (void)instr;
+ os << '"' << bb_dot_name(src.getName()) << "\" -> \""
+ << bb_dot_name(dst.getName()) << "\";\n";
+ }
+ os << "}\n";
+}
+
}

MODIFY
ir/function.h
ir/function.h
#include <ostream>
#include <string>
#include <string_view>
+#include <tuple>
#include <unordered_map>
#include <vector>
@@ -101,8 +102,8 @@ public:
const_iterator II, IE;
void next_bb();
public:
- instr_iterator(std::vector<BasicBlock*>::const_iterator BBI,
- std::vector<BasicBlock*>::const_iterator BBE);
+ instr_iterator(std::vector<BasicBlock*>::const_iterator &&BBI,
+ std::vector<BasicBlock*>::const_iterator &&BBE);
const IR::Instr& operator*() const { return *II; }
void operator++(void);
bool operator!=(instr_iterator &rhs) const { return BBI != rhs.BBI; }
@@ -115,11 +116,41 @@ public:
instr_iterator begin() { return { f.BB_order.begin(), f.BB_order.end() }; }
instr_iterator end() { return { f.BB_order.end(), f.BB_order.end() }; }
};
- instr_helper instrs() { return { *this }; }
- instr_helper instrs() const { return { *this }; }
+ instr_helper instrs() { return *this; }
+ instr_helper instrs() const { return *this; }
+
+ bool empty() const { return BB_order.empty(); }
void print(std::ostream &os, bool print_header = true) const;
friend std::ostream &operator<<(std::ostream &os, const Function &f);
};
+
+class CFG final {
+ Function &f;
+
+public:
+ CFG(Function &f) : f(f) {}
+
+ class edge_iterator {
+ std::vector<BasicBlock*>::iterator it, end;
+ unsigned idx = 0;
+ void next();
+ public:
+ edge_iterator(std::vector<BasicBlock*>::iterator &&it,
+ std::vector<BasicBlock*>::iterator &&end);
+ std::tuple<const BasicBlock&, const BasicBlock&, const Instr&>
+ operator*() const;
+ void operator++(void);
+ bool operator!=(edge_iterator &rhs) const { return it != rhs.it; }
+ };
+
+ edge_iterator begin() const {
+ return { f.getBBs().begin(), f.getBBs().end() };
+ }
+ edge_iterator end() const { return { f.getBBs().end(), f.getBBs().end() }; }
+
+ void printDot(std::ostream &os) const;
+};
+
}

MODIFY
ir/instr.h
ir/instr.h
@@ -177,6 +177,8 @@ public:
: Instr(Type::voidTy, "br"), cond(&cond), dst_true(dst_true),
dst_false(&dst_false) {}
+ auto& getTrue() const { return dst_true; }
+ auto getFalse() const { return dst_false; }
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
smt::expr getTypeConstraints(const Function &f) const override;
@@ -195,6 +197,10 @@ public:
void addTarget(Value &val, const BasicBlock &target);
+ auto getNumTargets() const { return targets.size(); }
+ auto& getTarget(unsigned i) const { return targets[i]; }
+ auto& getDefault() const { return default_target; }
+
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
smt::expr getTypeConstraints(const Function &f) const override;

MODIFY
tv/tv.cpp
tv/tv.cpp
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/raw_ostream.h"
+#include <fstream>
#include <iostream>
#include <optional>
#include <string>
#include <unordered_map>
+#include <utility>
#include <vector>
using namespace IR;
@@ -50,6 +52,10 @@ llvm::cl::opt<bool> opt_tactic_verbose(
"tv-tactic-verbose", llvm::cl::desc("Alive: SMT Tactic verbose mode"),
llvm::cl::init(false));
+llvm::cl::opt<bool> opt_print_dot(
+ "tv-dot", llvm::cl::desc("Alive: print .dot file with CFG of each function"),
+ llvm::cl::init(false));
+
#if 0
string_view s(llvm::StringRef str) {
return { str.data(), str.size() };
@@ -59,7 +65,7 @@ string_view s(llvm::StringRef str) {
optional<smt::smt_initializer> smt_init;
TransformPrintOpts print_opts;
vector<unique_ptr<IntType>> int_types;
-unordered_map<string, Function> fns;
+unordered_map<string, pair<Function, unsigned>> fns;
unordered_map<const llvm::Value*, Value*> identifiers;
Function *current_fn;
@@ -499,13 +505,21 @@ struct TVPass : public llvm::FunctionPass {
return false;
}
- auto [old_fn, inserted] = fns.try_emplace(fn->getName(), move(*fn));
+ auto [old_fn, inserted] = fns.try_emplace(fn->getName(), move(*fn), 0);
+
+ if (opt_print_dot) {
+ auto &f = inserted ? old_fn->second.first : *fn;
+ ofstream file(f.getName() + '.' + to_string(old_fn->second.second++)
+ + ".dot");
+ CFG(f).printDot(file);
+ }
+
if (inserted)
return false;
smt_init->reset();
Transform t;
- t.src = move(old_fn->second);
+ t.src = move(old_fn->second.first);
t.tgt = move(*fn);
TransformVerify verifier(t, false);
t.print(cerr, print_opts);
@@ -518,7 +532,7 @@ struct TVPass : public llvm::FunctionPass {
cerr << "Transformation seems to be correct!\n\n";
}
- old_fn->second = move(t.tgt);
+ old_fn->second.first = move(t.tgt);
return false;
}

stub CFG functionality & add dot printer