memory: add multi-byte support to memcpy
MODIFY
ir/globals.cpp
ir/globals.cpp
@@ -34,6 +34,7 @@ bool does_int_mem_access;
bool does_ptr_mem_access;
bool does_ptr_store;
bool does_sub_byte_access;
+unsigned heap_block_alignment;
bool isUndef(const expr &e) {

MODIFY
ir/globals.h
ir/globals.h
@@ -65,6 +65,8 @@ extern bool does_ptr_store;
/// Whether the programs do memory accesses of less than bits_byte
extern bool does_sub_byte_access;
+extern unsigned heap_block_alignment;
+
bool isUndef(const smt::expr &e);

MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -1830,10 +1830,10 @@ void Malloc::print(std::ostream &os) const {
StateValue Malloc::toSMT(State &s) const {
auto &[sz, np_size] = s.getAndAddUndefs(*size);
- // TODO: malloc's alignment is implementation defined.
+ unsigned align = heap_block_alignment;
expr nonnull = expr::mkBoolVar("malloc_never_fails");
- auto [p_new, allocated] = s.getMemory().alloc(sz, 8, Memory::HEAP, np_size,
- nonnull);
+ auto [p_new, allocated] = s.getMemory().alloc(sz, align, Memory::HEAP,
+ np_size, nonnull);
if (!ptr) {
if (isNonNull) {
@@ -1853,7 +1853,7 @@ StateValue Malloc::toSMT(State &s) const {
expr::mkIf(p_sz.ule(sz_zext), p_sz, sz_zext),
expr::mkUInt(0, p_sz.bits()));
- s.getMemory().memcpy(p_new, p, memcpy_size, 1, 1, true);
+ s.getMemory().memcpy(p_new, p, memcpy_size, align, align, true);
// 1) realloc(ptr, 0) always free the ptr.
// 2) If allocation failed, we should not free previous ptr.
@@ -1895,15 +1895,15 @@ StateValue Calloc::toSMT(State &s) const {
auto &[sz, np_sz] = s.getAndAddUndefs(*size);
auto np = np_num && np_sz;
- // TODO: check calloc align.
+ unsigned align = heap_block_alignment;
expr size = nm * sz;
expr nonnull = expr::mkBoolVar("malloc_never_fails");
- auto [p, allocated] = s.getMemory().alloc(size, 8, Memory::HEAP,
+ auto [p, allocated] = s.getMemory().alloc(size, align, Memory::HEAP,
np && nm.mul_no_uoverflow(sz),
nonnull);
expr calloc_sz = expr::mkIf(allocated, size, expr::mkUInt(0, sz.bits()));
- s.getMemory().memset(p, { expr::mkUInt(0, 8), true }, calloc_sz, 1);
+ s.getMemory().memset(p, { expr::mkUInt(0, 8), true }, calloc_sz, align);
return { move(p), move(np) };
}

MODIFY
ir/instr.h
ir/instr.h
@@ -559,6 +559,8 @@ public:
align_dst(align_dst), align_src(align_src), move(move) {}
Value& getBytes() const { return *bytes; }
+ unsigned getSrcAlign() const { return align_src; }
+ unsigned getDstAlign() const { return align_dst; }
std::vector<Value*> operands() const override;
void rauw(const Value &what, Value &with) override;
void print(std::ostream &os) const override;

MODIFY
ir/memory.cpp
ir/memory.cpp
@@ -1056,9 +1056,15 @@ void Memory::mkAxioms(const Memory &other) const {
return;
// transformation can increase alignment
+ unsigned align = heap_block_alignment;
for (unsigned bid = 1; bid < IR::num_nonlocals; ++bid) {
- state->addAxiom(Pointer(*this, bid, false).block_alignment().ule(
- Pointer(other, bid, false).block_alignment()));
+ Pointer p(*this, bid, false);
+ Pointer q(other, bid, false);
+ auto p_align = p.block_alignment();
+ auto q_align = q.block_alignment();
+ state->addAxiom(expr::mkIf(p.is_heap_allocated(),
+ p_align == align && q_align == align,
+ p_align.ule(q_align)));
}
if (!observes_addresses())
@@ -1516,7 +1522,8 @@ void Memory::memset(const expr &p, const StateValue &val, const expr &bytesize,
void Memory::memcpy(const expr &d, const expr &s, const expr &bytesize,
unsigned align_dst, unsigned align_src, bool is_move) {
assert(!memory_unused());
- assert(bits_byte == 8);
+ unsigned bytesz = bits_byte / 8;
+
Pointer dst(*this, d), src(*this, s);
state->addUB(dst.is_dereferenceable(bytesize, align_dst, true));
state->addUB(src.is_dereferenceable(bytesize, align_src, false));
@@ -1528,9 +1535,9 @@ void Memory::memcpy(const expr &d, const expr &s, const expr &bytesize,
return;
uint64_t n;
- if (bytesize.isUInt(n) && n <= 4) {
+ if (bytesize.isUInt(n) && (n / bytesz) <= 4) {
auto old_local = local_block_val, old_nonlocal = non_local_block_val;
- for (unsigned i = 0; i < n; ++i) {
+ for (unsigned i = 0; i < n; i += bytesz) {
store(dst + i, ::load(src + i, old_local, old_nonlocal),
local_block_val, non_local_block_val);
}

MODIFY
tests/alive-tv/opt-memory/bwiden-calloc.src.ll
tests/alive-tv/opt-memory/bwiden-calloc.src.ll
@@ -9,8 +9,7 @@ define i32 @calloc_init(i32 %x) {
ret i32 %v
}
-; calloc's bwiden is not supported yet
-; CHECK: bits_byte: 8
+; CHECK: bits_byte: 32
declare noalias i8* @calloc(i64, i64)
declare void @free(i8*)

MODIFY
tools/transform.cpp
tools/transform.cpp
@@ -562,10 +562,18 @@ static uint64_t get_access_size(const Type &ty) {
}
static uint64_t get_access_size(const Instr &inst) {
- if (dynamic_cast<const Calloc*>(&inst) ||
- dynamic_cast<const Memcpy *>(&inst)) {
- // TODO
+ if (auto i = dynamic_cast<const Calloc*>(&inst)) {
does_int_mem_access = true;
+ if (auto n = get_int(i->getNum()))
+ if (auto sz = get_int(i->getSize()))
+ // assume calloc is 8 bytes aligned
+ return gcd(8, *n * *sz);
+ return 1;
+ }
+
+ if (auto i = dynamic_cast<const Memcpy*>(&inst)) {
+ if (auto bytes = get_int(i->getBytes()))
+ return gcd(gcd(i->getSrcAlign(), i->getDstAlign()), *bytes);
return 1;
}
@@ -602,6 +610,7 @@ static void calculateAndInitConstants(Transform &t) {
// TODO: get this from data layout, varies among address spaces
bits_program_pointer = 64;
+ heap_block_alignment = 8;
for (auto GVT : globals_tgt) {
auto I = find_if(globals_src.begin(), globals_src.end(),

memory: add multi-byte support to memcpy