Add 'operator() &&' to DisjointExpr to avoid copies
In particular, this saves a bunch of copies of Memory, which are very expensive
Gives a nice peak memory reduction in large functions
MODIFY
ir/fast_math.cpp
ir/fast_math.cpp
@@ -268,7 +268,7 @@ public:
if (!has_all)
continue;
- auto [val, domain, qvar, pre] = vals();
+ auto [val, domain, qvar, pre] = std::move(vals)();
assert(domain.isTrue());
exprs[node_id] = std::move(val);
// TODO: handle qvar, pre

MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -2760,7 +2760,7 @@ StateValue Phi::toSMT(State &s) const {
}
}
- StateValue sv = *ret();
+ StateValue sv = *std::move(ret)();
auto identity = [](const expr &x) { return x; };
return fm_poison(s, sv.value, sv.non_poison, identity, getType(), fmath, true,
false);
@@ -4033,7 +4033,8 @@ StateValue VaCopy::toSMT(State &s) const {
// FIXME: dst should be empty or we have a mem leak
// alive, next_arg, num_args, is_va_start, active
- data[dst_raw] = { true, *next_arg(), *num_args(), *is_va_start(), true };
+ data[dst_raw] = { true, *std::move(next_arg)(), *std::move(num_args)(),
+ *std::move(is_va_start)(), true };
return {};
}
@@ -4094,7 +4095,7 @@ StateValue VaArg::toSMT(State &s) const {
entry.next_arg = expr::mkIf(eq, next_arg, entry.next_arg);
}
- return *ret();
+ return *std::move(ret)();
}
expr VaArg::getTypeConstraints(const Function &f) const {

MODIFY
ir/memory.cpp
ir/memory.cpp
@@ -926,7 +926,7 @@ vector<Byte> Memory::load(const Pointer &ptr, unsigned bytes, set<expr> &undef,
vector<Byte> ret;
for (auto &disj : loaded) {
- ret.emplace_back(*this, *disj());
+ ret.emplace_back(*this, *std::move(disj)());
}
return ret;
}
@@ -1925,7 +1925,7 @@ void Memory::copy(const Pointer &src, const Pointer &dst) {
dst_blk.type |= blk.type;
};
access(src, bits_byte/8, bits_byte/8, false, fn);
- dst_blk.val = *val();
+ dst_blk.val = *std::move(val)();
}
void Memory::fillPoison(const expr &bid) {
@@ -2145,9 +2145,9 @@ void Memory::escapeLocalPtr(const expr &ptr, const expr &is_ptr) {
}
}
-Memory Memory::mkIf(const expr &cond, const Memory &then, const Memory &els) {
+Memory Memory::mkIf(const expr &cond, Memory &&then, Memory &&els) {
assert(then.state == els.state);
- Memory ret(then);
+ Memory &ret = then;
for (unsigned bid = 0, end = ret.numNonlocals(); bid < end; ++bid) {
if (always_nowrite(bid, false, true))
continue;
@@ -2185,7 +2185,7 @@ Memory Memory::mkIf(const expr &cond, const Memory &then, const Memory &els) {
}
ret.next_nonlocal_bid = max(then.next_nonlocal_bid, els.next_nonlocal_bid);
- return ret;
+ return std::move(ret);
}
#define P(name, expr) do { \

MODIFY
ir/memory.h
ir/memory.h
@@ -325,8 +325,7 @@ public:
smt::expr checkNocapture() const;
void escapeLocalPtr(const smt::expr &ptr, const smt::expr &is_ptr);
- static Memory mkIf(const smt::expr &cond, const Memory &then,
- const Memory &els);
+ static Memory mkIf(const smt::expr &cond, Memory &&then, Memory &&els);
auto operator<=>(const Memory &rhs) const = default;

MODIFY
ir/pointer.cpp
ir/pointer.cpp
@@ -304,12 +304,12 @@ expr Pointer::inbounds(bool simplify_ptr, bool strict) {
}
// trim set of valid ptrs
- if (auto ptrs = all_ptrs())
+ if (auto ptrs = std::move(all_ptrs)())
p = *ptrs;
else
p = expr::mkUInt(0, totalBits());
- return *ret();
+ return *std::move(ret)();
}
expr Pointer::blockAlignment() const {
@@ -409,17 +409,17 @@ AndExpr Pointer::isDereferenceable(const expr &bytes0, uint64_t align,
}
AndExpr exprs;
- exprs.add(bytes == 0 || *UB());
+ exprs.add(bytes == 0 || *std::move(UB)());
// cannot store more bytes than address space
if (bytes0.bits() > bits_size_t)
exprs.add(bytes0.extract(bytes0.bits() - 1, bits_size_t) == 0);
// address must be always aligned regardless of access size
- exprs.add(*is_aligned());
+ exprs.add(*std::move(is_aligned)());
// trim set of valid ptrs
- if (auto ptrs = all_ptrs())
+ if (auto ptrs = std::move(all_ptrs)())
p = *ptrs;
else
p = expr::mkUInt(0, totalBits());

MODIFY
ir/state.cpp
ir/state.cpp
@@ -115,15 +115,16 @@ State::ValueAnalysis::FnCallRanges::project(const string &name) const {
}
State::VarArgsData
-State::VarArgsData::mkIf(const expr &cond, const VarArgsData &then,
- const VarArgsData &els) {
+State::VarArgsData::mkIf(const expr &cond, VarArgsData &&then,
+ VarArgsData &&els) {
VarArgsData ret;
for (auto &[ptr, entry] : then.data) {
auto other = els.data.find(ptr);
if (other == els.data.end()) {
- ret.data.try_emplace(ptr, cond && entry.alive, expr(entry.next_arg),
- expr(entry.num_args), expr(entry.is_va_start),
- expr(entry.active));
+ ret.data.try_emplace(ptr, cond && entry.alive, std::move(entry.next_arg),
+ std::move(entry.num_args),
+ std::move(entry.is_va_start),
+ std::move(entry.active));
} else {
#define C(f) expr::mkIf(cond, entry.f, other->second.f)
ret.data.try_emplace(ptr, C(alive), C(next_arg), C(num_args),
@@ -135,9 +136,9 @@ State::VarArgsData::mkIf(const expr &cond, const VarArgsData &then,
for (auto &[ptr, entry] : els.data) {
if (then.data.count(ptr))
continue;
- ret.data.try_emplace(ptr, !cond && entry.alive, expr(entry.next_arg),
- expr(entry.num_args), expr(entry.is_va_start),
- expr(entry.active));
+ ret.data.try_emplace(ptr, !cond && entry.alive, std::move(entry.next_arg),
+ std::move(entry.num_args),
+ std::move(entry.is_va_start), std::move(entry.active));
}
return ret;
@@ -146,7 +147,8 @@ State::VarArgsData::mkIf(const expr &cond, const VarArgsData &then,
State::State(const Function &f, bool source)
: f(f), source(source), memory(*this),
fp_rounding_mode(expr::mkVar("fp_rounding_mode", 3)),
- return_val(f.getType().getDummyValue(false)), return_memory(memory) {}
+ return_val(DisjointExpr(f.getType().getDummyValue(false))),
+ return_memory(DisjointExpr(memory)) {}
void State::resetGlobals() {
Memory::resetGlobals();
@@ -589,10 +591,10 @@ bool State::startBB(const BasicBlock &bb) {
}
assert(!isFirst);
- domain.path = path();
- domain.UB = *UB();
- memory = *in_memory();
- var_args_data = *var_args_in();
+ domain.path = std::move(path)();
+ domain.UB = *std::move(UB)();
+ memory = *std::move(in_memory)();
+ var_args_data = *std::move(var_args_in)();
return domain;
}
@@ -635,8 +637,8 @@ void State::addCondJump(const expr &cond, const BasicBlock &dst_true,
}
void State::addReturn(StateValue &&val) {
- return_val.add(std::move(val), domain.path);
- return_memory.add(memory, domain.path);
+ get<0>(return_val).add(std::move(val), domain.path);
+ get<0>(return_memory).add(memory, domain.path);
auto dom = domain();
return_domain.add(expr(dom));
function_domain.add(std::move(dom));
@@ -670,7 +672,7 @@ void State::addNoReturn(const expr &cond) {
if (cond.isFalse())
return;
domain.noreturn = !cond;
- return_memory.add(memory, domain.path && cond);
+ get<0>(return_memory).add(memory, domain.path && cond);
function_domain.add(domain() && cond);
return_undef_vars.insert(undef_vars.begin(), undef_vars.end());
return_undef_vars.insert(domain.undef_vars.begin(), domain.undef_vars.end());
@@ -916,7 +918,7 @@ State::addFnCall(const string &name, vector<StateValue> &&inputs,
}
if (data) {
- auto [d, domain, qvar, pre] = data();
+ auto [d, domain, qvar, pre] = std::move(data)();
addUB(std::move(domain));
addUB(std::move(d.ub));
addNoReturn(std::move(d.noreturns));
@@ -1023,6 +1025,18 @@ expr State::sinkDomain() const {
return ret();
}
+const StateValue& State::returnValCached() {
+ if (auto *v = get_if<DisjointExpr<StateValue>>(&return_val))
+ return_val = *std::move(*v)();
+ return get<StateValue>(return_val);
+}
+
+Memory& State::returnMemory() {
+ if (auto *m = get_if<DisjointExpr<Memory>>(&return_memory))
+ return_memory = *std::move(*m)();
+ return get<Memory>(return_memory);
+}
+
expr State::getJumpCond(const BasicBlock &src, const BasicBlock &dst) const {
auto I = predecessor_data.find(&dst);
if (I == predecessor_data.end())
@@ -1054,7 +1068,7 @@ void State::markGlobalAsAllocated(const string &glbvar) {
itr->second.second = true;
}
-void State::syncSEdataWithSrc(const State &src) {
+void State::syncSEdataWithSrc(State &src) {
assert(glbvar_bids.empty());
assert(src.isSource() && !isSource());
glbvar_bids = src.glbvar_bids;

MODIFY
ir/state.h
ir/state.h
#include <unordered_map>
#include <unordered_set>
#include <utility>
+#include <variant>
#include <vector>
namespace IR {
@@ -85,8 +86,8 @@ private:
struct VarArgsData {
std::map<smt::expr, VarArgsEntry> data;
- static VarArgsData mkIf(const smt::expr &cond, const VarArgsData &then,
- const VarArgsData &els);
+ static VarArgsData mkIf(const smt::expr &cond, VarArgsData &&then,
+ VarArgsData &&els);
auto operator<=>(const VarArgsData &rhs) const = default;
};
@@ -142,8 +143,8 @@ private:
smt::OrExpr return_domain;
// function_domain: a condition for function having well-defined behavior
smt::OrExpr function_domain;
- smt::DisjointExpr<StateValue> return_val;
- smt::DisjointExpr<Memory> return_memory;
+ std::variant<smt::DisjointExpr<StateValue>, StateValue> return_val;
+ std::variant<smt::DisjointExpr<Memory>, Memory> return_memory;
std::set<smt::expr> return_undef_vars;
struct FnCallInput {
@@ -184,6 +185,8 @@ private:
VarArgsData var_args_data;
+ const StateValue& returnValCached();
+
public:
State(const Function &f, bool source);
@@ -261,10 +264,10 @@ public:
}
smt::expr sinkDomain() const;
- Memory returnMemory() const { return *return_memory(); }
+ Memory& returnMemory();
- ValTy returnVal() const {
- return { *return_val(), return_domain(), function_domain(),
+ ValTy returnVal() {
+ return { returnValCached(), return_domain(), function_domain(),
return_undef_vars };
}
@@ -281,7 +284,7 @@ public:
bool hasGlobalVarBid(const std::string &glbvar, unsigned &bid,
bool &allocated) const;
void markGlobalAsAllocated(const std::string &glbvar);
- void syncSEdataWithSrc(const State &src);
+ void syncSEdataWithSrc(State &src);
void mkAxioms(State &tgt);

MODIFY
ir/type.cpp
ir/type.cpp
@@ -298,7 +298,7 @@ void VoidType::fixup(const Model &m) {
}
pair<expr, expr>
-VoidType::refines(const State &src_s, const State &tgt_s, const StateValue &src,
+VoidType::refines(State &src_s, State &tgt_s, const StateValue &src,
const StateValue &tgt) const {
return { true, true };
}
@@ -356,7 +356,7 @@ expr IntType::enforceIntType(unsigned bits) const {
}
pair<expr, expr>
-IntType::refines(const State &src_s, const State &tgt_s, const StateValue &src,
+IntType::refines(State &src_s, State &tgt_s, const StateValue &src,
const StateValue &tgt) const {
return { src.non_poison.implies(tgt.non_poison),
(src.non_poison && tgt.non_poison).implies(src.value == tgt.value) };
@@ -544,8 +544,8 @@ expr FloatType::enforceFloatType() const {
}
pair<expr, expr>
-FloatType::refines(const State &src_s, const State &tgt_s,
- const StateValue &src, const StateValue &tgt) const {
+FloatType::refines(State &src_s, State &tgt_s, const StateValue &src,
+ const StateValue &tgt) const {
expr non_poison = src.non_poison && tgt.non_poison;
return { src.non_poison.implies(tgt.non_poison),
(src.non_poison && tgt.non_poison).implies(src.value == tgt.value) };
@@ -659,9 +659,9 @@ StateValue PtrType::fromInt(StateValue v) const {
}
pair<expr, expr>
-PtrType::refines(const State &src_s, const State &tgt_s, const StateValue &src,
+PtrType::refines(State &src_s, State &tgt_s, const StateValue &src,
const StateValue &tgt) const {
- auto sm = src_s.returnMemory(), tm = tgt_s.returnMemory();
+ auto &sm = src_s.returnMemory(), &tm = tgt_s.returnMemory();
Pointer p(sm, src.value);
Pointer q(tm, tgt.value);
@@ -936,8 +936,8 @@ StateValue AggregateType::fromInt(StateValue v) const {
}
pair<expr, expr>
-AggregateType::refines(const State &src_s, const State &tgt_s,
- const StateValue &src, const StateValue &tgt) const {
+AggregateType::refines(State &src_s, State &tgt_s, const StateValue &src,
+ const StateValue &tgt) const {
set<expr> poison, value;
for (unsigned i = 0; i < elements; ++i) {
auto [p, v] = children[i]->refines(src_s, tgt_s, extract(src, i),
@@ -1379,8 +1379,8 @@ StateValue SymbolicType::fromInt(StateValue val) const {
}
pair<expr, expr>
-SymbolicType::refines(const State &src_s, const State &tgt_s,
- const StateValue &src, const StateValue &tgt) const {
+SymbolicType::refines(State &src_s, State &tgt_s, const StateValue &src,
+ const StateValue &tgt) const {
DISPATCH(refines(src_s, tgt_s, src, tgt), UNREACHABLE());
}

MODIFY
ir/type.h
ir/type.h
@@ -107,7 +107,7 @@ public:
// returns pair of refinement constraints for <poison, !poison && value>
virtual std::pair<smt::expr, smt::expr>
- refines(const State &src_s, const State &tgt_s, const StateValue &src,
+ refines(State &src_s, State &tgt_s, const StateValue &src,
const StateValue &tgt) const = 0;
virtual StateValue mkUndef(State &s) const;
@@ -137,7 +137,7 @@ public:
smt::expr getTypeConstraints() const override;
void fixup(const smt::Model &m) override;
std::pair<smt::expr, smt::expr>
- refines(const State &src_s, const State &tgt_s, const StateValue &src,
+ refines(State &src_s, State &tgt_s, const StateValue &src,
const StateValue &tgt) const override;
smt::expr
mkInput(State &s, const char *name, const ParamAttrs &attrs) const override;
@@ -165,7 +165,7 @@ public:
bool isIntType() const override;
smt::expr enforceIntType(unsigned bits = 0) const override;
std::pair<smt::expr, smt::expr>
- refines(const State &src_s, const State &tgt_s, const StateValue &src,
+ refines(State &src_s, State &tgt_s, const StateValue &src,
const StateValue &tgt) const override;
smt::expr
mkInput(State &s, const char *name, const ParamAttrs &attrs) const override;
@@ -211,7 +211,7 @@ public:
smt::expr fromInt(smt::expr v) const override;
IR::StateValue fromInt(IR::StateValue v) const override;
std::pair<smt::expr, smt::expr>
- refines(const State &src_s, const State &tgt_s, const StateValue &src,
+ refines(State &src_s, State &tgt_s, const StateValue &src,
const StateValue &tgt) const override;
smt::expr
mkInput(State &s, const char *name, const ParamAttrs &attrs) const override;
@@ -244,7 +244,7 @@ public:
smt::expr fromInt(smt::expr v) const override;
IR::StateValue fromInt(IR::StateValue v) const override;
std::pair<smt::expr, smt::expr>
- refines(const State &src_s, const State &tgt_s, const StateValue &src,
+ refines(State &src_s, State &tgt_s, const StateValue &src,
const StateValue &tgt) const override;
StateValue mkUndef(State &s) const override;
smt::expr
@@ -302,7 +302,7 @@ public:
smt::expr fromInt(smt::expr v) const override;
IR::StateValue fromInt(IR::StateValue v) const override;
std::pair<smt::expr, smt::expr>
- refines(const State &src_s, const State &tgt_s, const StateValue &src,
+ refines(State &src_s, State &tgt_s, const StateValue &src,
const StateValue &tgt) const override;
StateValue mkUndef(State &s) const override;
smt::expr
@@ -410,7 +410,7 @@ public:
smt::expr fromInt(smt::expr v) const override;
IR::StateValue fromInt(IR::StateValue v) const override;
std::pair<smt::expr, smt::expr>
- refines(const State &src_s, const State &tgt_s, const StateValue &src,
+ refines(State &src_s, State &tgt_s, const StateValue &src,
const StateValue &tgt) const override;
StateValue mkUndef(State &s) const override;
smt::expr

MODIFY
smt/exprs.cpp
smt/exprs.cpp
@@ -198,7 +198,7 @@ optional<expr> FunctionExpr::operator()(const expr &key) const {
for (auto &[k, v] : fn) {
disj.add(v, k == key);
}
- return disj();
+ return std::move(disj)();
}
const expr* FunctionExpr::lookup(const expr &key) const {

MODIFY
smt/exprs.h
smt/exprs.h
@@ -81,15 +81,32 @@ public:
}
}
- std::optional<T> operator()() const {
+ std::optional<T> operator()() const& {
std::optional<T> ret;
for (auto &[val, domain] : vals) {
if (domain.isTrue())
return val;
- ret = ret ? T::mkIf(domain, val, *ret) : val;
+ ret = ret ? T::mkIf(domain, val, *std::move(ret)) : val;
}
- return ret ? ret : default_val;
+ if (ret)
+ return ret;
+ return default_val;
+ }
+
+ std::optional<T> operator()() && {
+ std::optional<T> ret;
+ for (auto &[val0, domain] : vals) {
+ auto &val = const_cast<T&>(val0);
+ if (domain.isTrue())
+ return std::move(val);
+
+ ret = ret ? T::mkIf(domain, std::move(val), *std::move(ret))
+ : std::move(val);
+ }
+ if (ret)
+ return ret;
+ return std::move(default_val);
}
std::optional<T> lookup(const expr &domain) const {
@@ -136,7 +153,7 @@ public:
}
// returns: data, domain, quant var, precondition
- std::tuple<T,expr,expr,expr> operator()() const {
+ std::tuple<T,expr,expr,expr> operator()() && {
if (vals.size() == 1)
return { vals.begin()->first, vals.begin()->second, expr(), true };
@@ -152,7 +169,8 @@ public:
for (unsigned i = vals.size(); i > 0; --i) {
auto cmp = qvar == (i-1);
pre = expr::mkIf(cmp, I->second, pre);
- ret = first ? I->first : T::mkIf(cmp, I->first, ret);
+ ret = first ? std::move(I->first)
+ : T::mkIf(cmp, std::move(I->first), std::move(ret));
first = false;
++I;
}

MODIFY
tools/alive-exec.cpp
tools/alive-exec.cpp
@@ -120,7 +120,7 @@ void execFunction(llvm::Function &F, llvm::TargetLibraryInfoWrapperPass &TLI,
smt_init->reset();
try {
auto p = verifier.exec();
- const auto &state = *p.first;
+ auto &state = *p.first;
const auto &fn = t.src;
const auto *bb = &fn.getFirstBB();

MODIFY
tools/transform.cpp
tools/transform.cpp
@@ -388,8 +388,8 @@ static expr encode_undef_refinement(const Type &type, const State::ValTy &a,
}
static void
-check_refinement(Errors &errs, const Transform &t, const State &src_state,
- const State &tgt_state, const Value *var, const Type &type,
+check_refinement(Errors &errs, const Transform &t, State &src_state,
+ State &tgt_state, const Value *var, const Type &type,
const State::ValTy &ap, const State::ValTy &bp,
bool check_each_var) {
auto &fndom_a = ap.domain;
@@ -529,8 +529,8 @@ check_refinement(Errors &errs, const Transform &t, const State &src_state,
CHECK(dom && !value_cnstr, print_value, "Value mismatch");
// 6. Check memory
- auto src_mem = src_state.returnMemory();
- auto tgt_mem = tgt_state.returnMemory();
+ auto &src_mem = src_state.returnMemory();
+ auto &tgt_mem = tgt_state.returnMemory();
auto [memory_cnstr0, ptr_refinement0, mem_undef]
= src_mem.refined(tgt_mem, false);
auto &ptr_refinement = ptr_refinement0;

Add 'operator() &&' to DisjointExpr to avoid copies
In particular, this saves a bunch of copies of Memory, which are very expensive
Gives a nice peak memory reduction in large functions