add basic block duplication functionality
MODIFY
ir/function.cpp
ir/function.cpp
@@ -27,6 +27,14 @@ void BasicBlock::addInstr(unique_ptr<Instr> &&i) {
m_instrs.push_back(move(i));
}
+unique_ptr<BasicBlock> BasicBlock::dup(const string &suffix) const {
+ auto newbb = make_unique<BasicBlock>(name + suffix);
+ for (auto &i : instrs()) {
+ newbb->addInstr(i.dup(suffix));
+ }
+ return newbb;
+}
+
ostream& operator<<(ostream &os, const BasicBlock &bb) {
if (!bb.name.empty())
os << bb.name << ":\n";

MODIFY
ir/function.h
ir/function.h
@@ -42,6 +42,8 @@ public:
}
Instr& back() { return *m_instrs.back(); }
+ std::unique_ptr<BasicBlock> dup(const std::string &suffix) const;
+
friend std::ostream& operator<<(std::ostream &os, const BasicBlock &bb);
};

MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -248,10 +248,15 @@ expr BinOp::getTypeConstraints(const Function &f) const {
move(instrconstr);
}
+unique_ptr<Instr> BinOp::dup(const string &suffix) const {
+ return make_unique<BinOp>(getType(), getName()+suffix, lhs, rhs, op, flags);
+}
+
void UnaryOp::print(ostream &os) const {
const char *str = nullptr;
switch (op) {
+ case Copy: str = ""; break;
case BitReverse: str = "bitreverse "; break;
case BSwap: str = "bswap "; break;
case Ctpop: str = "ctpop "; break;
@@ -265,6 +270,9 @@ StateValue UnaryOp::toSMT(State &s) const {
expr newval;
switch (op) {
+ case Copy:
+ newval = v;
+ break;
case BitReverse:
newval = v.bitreverse();
break;
@@ -279,21 +287,27 @@ StateValue UnaryOp::toSMT(State &s) const {
}
expr UnaryOp::getTypeConstraints(const Function &f) const {
- expr instrconstr;
+ expr instrconstr = true;
switch(op) {
case BSwap:
instrconstr = val.getType().sizeVar().urem(expr::mkUInt(16, 8)) == 0;
+ [[fallthrough]];
+ case BitReverse:
+ case Ctpop:
+ instrconstr &= getType().enforceIntOrPtrOrVectorType();
+ case Copy:
break;
- default:
- instrconstr = true;
}
return Value::getTypeConstraints() &&
- getType().enforceIntOrPtrOrVectorType() &&
getType() == val.getType() &&
move(instrconstr);
}
+unique_ptr<Instr> UnaryOp::dup(const string &suffix) const {
+ return make_unique<UnaryOp>(getType(), getName() + suffix, val, op);
+}
+
void TernaryOp::print(ostream &os) const {
const char *str = nullptr;
@@ -338,6 +352,10 @@ expr TernaryOp::getTypeConstraints(const Function &f) const {
getType() == C.getType();
}
+unique_ptr<Instr> TernaryOp::dup(const string &suffix) const {
+ return make_unique<TernaryOp>(getType(), getName() + suffix, A, B, C, op);
+}
+
void ConversionOp::print(ostream &os) const {
const char *str = nullptr;
@@ -391,6 +409,10 @@ expr ConversionOp::getTypeConstraints(const Function &f) const {
move(sizeconstr);
}
+unique_ptr<Instr> ConversionOp::dup(const string &suffix) const {
+ return make_unique<ConversionOp>(getType(), getName() + suffix, val, op);
+}
+
void Select::print(ostream &os) const {
os << getName() << " = select " << cond << ", " << a << ", " << b;
@@ -414,6 +436,10 @@ expr Select::getTypeConstraints(const Function &f) const {
getType() == b.getType();
}
+unique_ptr<Instr> Select::dup(const string &suffix) const {
+ return make_unique<Select>(getType(), getName() + suffix, cond, a, b);
+}
+
ICmp::ICmp(Type &type, string &&name, Cond cond, Value &a, Value &b)
: Instr(type, move(name)), a(a), b(b), cond(cond), defined(cond != Any) {
@@ -491,6 +517,10 @@ expr ICmp::eqType(const Instr &i) const {
return eq;
}
+unique_ptr<Instr> ICmp::dup(const string &suffix) const {
+ return make_unique<ICmp>(getType(), getName() + suffix, cond, a, b);
+}
+
void Freeze::print(ostream &os) const {
os << getName() << " = freeze " << val;
@@ -507,7 +537,7 @@ StateValue Freeze::toSMT(State &s) const {
expr nondet = expr::mkVar(name.c_str(), bits());
s.addQuantVar(nondet);
- return { expr::mkIf(p, v, std::move(nondet)), true };
+ return { expr::mkIf(p, v, move(nondet)), true };
}
expr Freeze::getTypeConstraints(const Function &f) const {
@@ -515,18 +545,8 @@ expr Freeze::getTypeConstraints(const Function &f) const {
getType() == val.getType();
}
-
-void CopyOp::print(ostream &os) const {
- os << getName() << " = " << val;
-}
-
-StateValue CopyOp::toSMT(State &s) const {
- return s[val];
-}
-
-expr CopyOp::getTypeConstraints(const Function &f) const {
- return Value::getTypeConstraints() &&
- getType() == val.getType();
+unique_ptr<Instr> Freeze::dup(const string &suffix) const {
+ return make_unique<Freeze>(getType(), getName() + suffix, val);
}
@@ -574,6 +594,10 @@ expr Phi::getTypeConstraints(const Function &f) const {
return c;
}
+unique_ptr<Instr> Phi::dup(const string &suffix) const {
+ return make_unique<Phi>(getType(), getName() + suffix, ValTy(values));
+}
+
void Branch::print(ostream &os) const {
os << "br ";
@@ -598,6 +622,12 @@ expr Branch::getTypeConstraints(const Function &f) const {
cond->getType().sizeVar() == 1u;
}
+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);
+}
+
void Switch::addTarget(Value &val, const BasicBlock &target) {
targets.emplace_back(val, target);
@@ -615,10 +645,10 @@ StateValue Switch::toSMT(State &s) const {
auto val = s[value];
expr default_cond(true);
- for (auto &p : targets) {
- auto target = s[p.first];
+ for (auto &[value_cond, bb] : targets) {
+ auto target = s[value_cond];
assert(target.non_poison.isTrue());
- s.addJump({ val.value == target.value, expr(val.non_poison) }, p.second);
+ s.addJump({ val.value == target.value, expr(val.non_poison) }, bb);
default_cond &= val.value != target.value;
}
@@ -635,6 +665,14 @@ expr Switch::getTypeConstraints(const Function &f) const {
return typ;
}
+unique_ptr<Instr> Switch::dup(const string &suffix) const {
+ auto sw = make_unique<Switch>(value, default_target);
+ for (auto &[value_cond, bb] : targets) {
+ sw->addTarget(value_cond, bb);
+ }
+ return sw;
+}
+
void Return::print(ostream &os) const {
os << "ret " << val;
@@ -651,6 +689,10 @@ expr Return::getTypeConstraints(const Function &f) const {
f.getType() == getType();
}
+unique_ptr<Instr> Return::dup(const string &suffix) const {
+ return make_unique<Return>(getType(), val);
+}
+
void Assume::print(ostream &os) const {
os << (if_non_poison ? "assume_non_poison " : "assume ") << cond;
@@ -669,4 +711,8 @@ expr Assume::getTypeConstraints(const Function &f) const {
return cond.getType().enforceIntType();
}
+unique_ptr<Instr> Assume::dup(const string &suffix) const {
+ return make_unique<Assume>(cond, if_non_poison);
+}
+
}

MODIFY
ir/instr.h
ir/instr.h
@@ -21,6 +21,7 @@ public:
virtual smt::expr eqType(const Instr &i) const;
smt::expr getTypeConstraints() const override;
virtual smt::expr getTypeConstraints(const Function &f) const = 0;
+ virtual std::unique_ptr<Instr> dup(const std::string &suffix) const = 0;
};
@@ -43,12 +44,13 @@ public:
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
smt::expr getTypeConstraints(const Function &f) const override;
+ std::unique_ptr<Instr> dup(const std::string &suffix) const override;
};
class UnaryOp final : public Instr {
public:
- enum Op { BitReverse, BSwap, Ctpop };
+ enum Op { Copy, BitReverse, BSwap, Ctpop };
private:
Value &val;
@@ -60,6 +62,7 @@ public:
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
smt::expr getTypeConstraints(const Function &f) const override;
+ std::unique_ptr<Instr> dup(const std::string &suffix) const override;
};
class TernaryOp final : public Instr {
@@ -77,6 +80,7 @@ public:
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
smt::expr getTypeConstraints(const Function &f) const override;
+ std::unique_ptr<Instr> dup(const std::string &suffix) const override;
};
class ConversionOp final : public Instr {
@@ -93,6 +97,7 @@ public:
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
smt::expr getTypeConstraints(const Function &f) const override;
+ std::unique_ptr<Instr> dup(const std::string &suffix) const override;
};
@@ -104,6 +109,7 @@ public:
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
smt::expr getTypeConstraints(const Function &f) const override;
+ std::unique_ptr<Instr> dup(const std::string &suffix) const override;
};
@@ -125,6 +131,7 @@ public:
smt::expr getTypeConstraints(const Function &f) const override;
void fixupTypes(const smt::Model &m) override;
smt::expr eqType(const Instr &i) const override;
+ std::unique_ptr<Instr> dup(const std::string &suffix) const override;
};
@@ -137,18 +144,7 @@ public:
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
smt::expr getTypeConstraints(const Function &f) const override;
-};
-
-
-class CopyOp final : public Instr {
- Value &val;
-public:
- CopyOp(Type &type, std::string &&name, Value &val)
- : Instr(type, std::move(name)), val(val) {}
-
- void print(std::ostream &os) const override;
- StateValue toSMT(State &s) const override;
- smt::expr getTypeConstraints(const Function &f) const override;
+ std::unique_ptr<Instr> dup(const std::string &suffix) const override;
};
@@ -164,6 +160,7 @@ public:
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
smt::expr getTypeConstraints(const Function &f) const override;
+ std::unique_ptr<Instr> dup(const std::string &suffix) const override;
};
@@ -182,6 +179,7 @@ public:
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
smt::expr getTypeConstraints(const Function &f) const override;
+ std::unique_ptr<Instr> dup(const std::string &suffix) const override;
};
@@ -204,6 +202,7 @@ public:
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
smt::expr getTypeConstraints(const Function &f) const override;
+ std::unique_ptr<Instr> dup(const std::string &suffix) const override;
};
@@ -215,6 +214,7 @@ public:
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
smt::expr getTypeConstraints(const Function &f) const override;
+ std::unique_ptr<Instr> dup(const std::string &suffix) const override;
};
@@ -228,6 +228,7 @@ public:
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
smt::expr getTypeConstraints(const Function &f) const override;
+ std::unique_ptr<Instr> dup(const std::string &suffix) const override;
};
}

MODIFY
tools/alive_parser.cpp
tools/alive_parser.cpp
@@ -532,7 +532,7 @@ static unique_ptr<Instr> parse_copyop(string_view name, token t) {
tokenizer.unget(t);
auto &ty = parse_type();
auto &op = parse_operand(ty);
- return make_unique<CopyOp>(ty, string(name), op);
+ return make_unique<UnaryOp>(ty, string(name), op, UnaryOp::Copy);
}
static unique_ptr<Instr> parse_instr(string_view name) {

MODIFY
tv/tv.cpp
tv/tv.cpp
@@ -344,6 +344,7 @@ public:
case llvm::Intrinsic::bitreverse:
case llvm::Intrinsic::bswap:
case llvm::Intrinsic::ctpop:
+ case llvm::Intrinsic::expect:
{
PARSE_UNOP();
UnaryOp::Op op;
@@ -351,6 +352,7 @@ public:
case llvm::Intrinsic::bitreverse: op = UnaryOp::BitReverse; break;
case llvm::Intrinsic::bswap: op = UnaryOp::BSwap; break;
case llvm::Intrinsic::ctpop: op = UnaryOp::Ctpop; break;
+ case llvm::Intrinsic::expect: op = UnaryOp::Copy; break;
default: UNREACHABLE();
}
RETURN_IDENTIFIER(make_unique<UnaryOp>(*ty, value_name(i), *val, op));
@@ -368,11 +370,6 @@ public:
RETURN_IDENTIFIER(make_unique<TernaryOp>(*ty, value_name(i), *a, *b, *c,
op));
}
- case llvm::Intrinsic::expect:
- {
- PARSE_UNOP();
- RETURN_IDENTIFIER(make_unique<CopyOp>(*ty, value_name(i), *val));
- }
// do nothing intrinsics
case llvm::Intrinsic::dbg_addr:

add basic block duplication functionality