Memory: optimize encoding of bytes by widening byte size if possible
MODIFY
ir/globals.cpp
ir/globals.cpp
@@ -11,6 +11,7 @@ unsigned num_nonlocals;
unsigned bits_for_bid;
unsigned bits_for_offset;
unsigned bits_size_t;
+unsigned bits_byte;
bool little_endian;
bool nullptr_is_used;
bool has_int2ptr;

MODIFY
ir/globals.h
ir/globals.h
@@ -23,6 +23,9 @@ extern unsigned bits_for_offset;
/// sizeof(size_t). This is assume to be equal to pointer size
extern unsigned bits_size_t;
+/// Number of bits for a byte.
+extern unsigned bits_byte;
+
extern bool little_endian;
/// Wether the null pointer is used in either function

MODIFY
ir/instr.h
ir/instr.h
@@ -403,6 +403,8 @@ public:
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;
+ Value *getNum() const { return num; }
+ Value *getSize() const { return size; }
};
@@ -447,6 +449,7 @@ public:
: Instr(type, std::move(name)), ptr(&ptr), align(align) {}
std::vector<Value*> operands() const override;
+ unsigned getAlign() const { return align; }
void rauw(const Value &what, Value &with) override;
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
@@ -463,6 +466,9 @@ public:
: Instr(Type::voidTy, "store"), ptr(&ptr), val(&val), align(align) {}
std::vector<Value*> operands() const override;
+ Value *getValue() const { return val; }
+ Value *getPointer() const { return ptr; }
+ unsigned getAlign() const { return align; }
void rauw(const Value &what, Value &with) override;
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;

MODIFY
ir/memory.cpp
ir/memory.cpp
@@ -16,14 +16,14 @@ namespace {
// A data structure that represents a byte.
// A byte is either a pointer byte or a non-pointer byte.
// Pointer byte's representation:
-// +-+------------------+-------------------+----------------+-------------+
-// |1| non-poison byte? | ptr offset | block id | byte offset |
-// | | (1 bit) | (bits_for_offset) | (bits_for_bid) | (3 bits) |
-// +-+------------------+-------------------+----------------+-------------+
+// +-+-------+-----------+------------------+----------------+-------------+
+// |1|padding|non-poison?| ptr offset | block id | byte offset |
+// | | |(1 bit) | (bits_for_offset)| (bits_for_bid) | (3 bits) |
+// +-+-------+-----------+------------------+----------------+-------------+
// Non-pointer byte's representation:
// +-+--------------------------+--------------------+---------------------+
-// |0| padding(000000000) | non-poison bits? | data |
-// | | | (8 bits) | (8 bits) |
+// |0| padding(zero) | non-poison bits? | data |
+// | | | (bits_byte) | (bits_byte) |
// +-+--------------------------+--------------------+---------------------+
class Byte {
const Memory &m;
@@ -44,20 +44,25 @@ public:
expr byteofs = expr::mkUInt(i, 3);
expr np = non_poison.toBVBool();
- p = expr::mkUInt(1, 1).concat(np).concat(ptr()).concat(byteofs);
+ unsigned padding = m.bitsByte() - 1 - 1 - bits_for_offset - bits_for_bid - 3;
+ p = expr::mkUInt(1, 1);
+ if (padding)
+ p = p.concat(expr::mkUInt(0, padding));
+ p = p.concat(np).concat(ptr()).concat(byteofs);
assert(!p.isValid() || p.bits() == m.bitsByte());
}
// Creates a non-pointer byte that has data and non_poison.
- // data and non_poison should have 8 bits.
+ // data and non_poison should have bits_byte bits.
Byte(const Memory &m, const expr &data, const expr &non_poison) : m(m) {
- assert(m.bitsByte() > 1 + 8 + 8);
- assert(!data.isValid() || data.bits() == 8);
- assert(!non_poison.isValid() || non_poison.bits() == 8);
-
- unsigned padding = m.bitsByte() - 1 - 8 - 8;
- p = expr::mkUInt(0, 1).concat(expr::mkUInt(0, padding)).concat(non_poison)
- .concat(data);
+ assert(!data.isValid() || data.bits() == bits_byte);
+ assert(!non_poison.isValid() || non_poison.bits() == bits_byte);
+
+ unsigned padding = m.bitsByte() - 1 - 2 * bits_byte;
+ p = expr::mkUInt(0, 1);
+ if (padding)
+ p = p.concat(expr::mkUInt(0, padding));
+ p = p.concat(non_poison).concat(data);
assert(!p.isValid() || p.bits() == m.bitsByte());
}
@@ -72,12 +77,15 @@ public:
return p.extract(bit, bit) == 1;
}
- expr ptr_value() const { return p.extract(p.bits() - 3, 3); }
+ expr ptr_value() const {
+ return p.extract(bits_for_offset + bits_for_bid + 2, 3);
+ }
expr ptr_byteoffset() const { return p.extract(2, 0); }
// Assuming that this is a non-pointer byte
- expr nonptr_nonpoison() const { return p.extract(15, 8); };
- expr nonptr_value() const { return p.extract(7, 0); }
+ expr nonptr_nonpoison() const { return p.extract(bits_byte * 2 - 1,
+ bits_byte); };
+ expr nonptr_value() const { return p.extract(bits_byte - 1, 0); }
const expr& operator()() const { return p; }
@@ -86,7 +94,7 @@ public:
}
static Byte mkPoisonByte(const Memory &m) {
- IntType ty("", 8);
+ IntType ty("", bits_byte);
auto v = ty.toBV(ty.getDummyValue(false));
return { m, v.value, v.non_poison };
}
@@ -98,20 +106,21 @@ vector<Byte> valueToBytes(const StateValue &val, const Type &fromType,
vector<Byte> bytes;
if (fromType.isPtrType()) {
Pointer p(mem, val.value);
- unsigned bytesize = bits_size_t / 8;
+ unsigned bytesize = bits_size_t / bits_byte;
for (unsigned i = 0; i < bytesize; ++i)
bytes.emplace_back(p, i, val.non_poison);
} else {
StateValue bvval = fromType.toBV(val);
unsigned bitsize = bvval.bits();
- unsigned bytesize = divide_up(bitsize, 8);
+ unsigned bytesize = divide_up(bitsize, bits_byte);
- bvval = bvval.zext(bytesize * 8 - bitsize);
+ bvval = bvval.zext(bytesize * bits_byte - bitsize);
for (unsigned i = 0; i < bytesize; ++i) {
- expr data = bvval.value.extract((i + 1) * 8 - 1, i * 8);
- expr np = bvval.non_poison.extract((i + 1) * 8 - 1, i * 8);
+ expr data = bvval.value.extract((i + 1) * bits_byte - 1, i * bits_byte);
+ expr np = bvval.non_poison.extract((i + 1) * bits_byte - 1,
+ i * bits_byte);
bytes.emplace_back(mem, data, np);
}
}
@@ -122,6 +131,7 @@ StateValue bytesToValue(const vector<Byte> &bytes, const Type &toType) {
assert(!bytes.empty());
if (toType.isPtrType()) {
+ assert(bytes.size() == bits_size_t / bits_byte);
expr loaded_ptr;
// The result is not poison if all of these hold:
// (1) There's no poison byte, and they are all pointer bytes
@@ -146,15 +156,15 @@ StateValue bytesToValue(const vector<Byte> &bytes, const Type &toType) {
} else {
auto bitsize = toType.bits();
- assert(divide_up(bitsize, 8) == bytes.size());
+ assert(divide_up(bitsize, bits_byte) == bytes.size());
StateValue val;
bool first = true;
- IntType i8Ty("", 8);
+ IntType ibyteTy("", bits_byte);
for (auto &b: bytes) {
StateValue v(b.nonptr_value(),
- i8Ty.combine_poison(!b.is_ptr(), b.nonptr_nonpoison()));
+ ibyteTy.combine_poison(!b.is_ptr(), b.nonptr_nonpoison()));
val = first ? move(v) : v.concat(val);
first = false;
}
@@ -293,7 +303,8 @@ expr Pointer::inbounds() const {
}
expr Pointer::is_aligned(unsigned align, bool exact) const {
- if (!exact && align <= 1)
+ assert(align != 0);
+ if (!exact && align == 1)
return true;
auto bits = ilog2(align);
@@ -595,7 +606,7 @@ void Memory::resetLocalBids() {
}
unsigned Memory::bitsByte() const {
- return 1 + 1 + bits_for_bid + bits_for_offset + 3;
+ return max(1 + 1 + bits_for_bid + bits_for_offset + 3, 1 + 2 * bits_byte);
}
expr Memory::mkInput(const char *name) const {
@@ -737,9 +748,14 @@ void Memory::store(const expr &p, const StateValue &v, const Type &type,
vector<Byte> bytes = valueToBytes(v, type, *this);
Pointer ptr(*this, p);
- ptr.is_dereferenceable(bytes.size(), align, !state->isInitializationPhase());
+ unsigned bytesz = bits_byte / 8;
+ assert(align % bytesz == 0);
+
+ ptr.is_dereferenceable(bytes.size() * bytesz, align,
+ !state->isInitializationPhase());
for (unsigned i = 0, e = bytes.size(); i < e; ++i) {
- auto ptr_i = little_endian ? (ptr + i) : (ptr + (e - i - 1));
+ auto ptr_i = little_endian ? (ptr + i * bytesz) :
+ (ptr + (e - i - 1) * bytesz);
store(ptr_i, bytes[i](), local_block_val, non_local_block_val);
}
}
@@ -747,14 +763,18 @@ void Memory::store(const expr &p, const StateValue &v, const Type &type,
StateValue Memory::load(const expr &p, const Type &type, unsigned align) {
assert(!memory_unused());
auto bitsize = type.isPtrType() ? bits_size_t : type.bits();
- unsigned bytesize = divide_up(bitsize, 8);
+ assert(bits_byte == 8 || bitsize % bits_byte == 0);
+ unsigned bytecount = divide_up(bitsize, bits_byte);
+ unsigned bytesz = bits_byte / 8;
+ assert(align % bytesz == 0);
Pointer ptr(*this, p);
- ptr.is_dereferenceable(bytesize, align, false);
+ ptr.is_dereferenceable(bytecount * bytesz, align, false);
vector<Byte> loadedBytes;
- for (unsigned i = 0; i < bytesize; ++i) {
- auto ptr_i = little_endian ? (ptr + i) : (ptr + (bytesize - i - 1));
+ for (unsigned i = 0; i < bytecount; ++i) {
+ auto ptr_i = little_endian ? (ptr + i * bytesz) :
+ (ptr + (bytecount - i - 1) * bytesz);
loadedBytes.emplace_back(*this, ::load(ptr_i, local_block_val,
non_local_block_val));
}
@@ -764,11 +784,12 @@ StateValue Memory::load(const expr &p, const Type &type, unsigned align) {
void Memory::memset(const expr &p, const StateValue &val, const expr &bytesize,
unsigned align) {
assert(!memory_unused());
+ assert(bits_byte == 8);
assert(!val.isValid() || val.bits() == 8);
Pointer ptr(*this, p);
ptr.is_dereferenceable(bytesize, align, true);
- vector<Byte> bytes = valueToBytes(val, IntType("", 8), *this);
+ vector<Byte> bytes = valueToBytes(val, IntType("", bits_byte), *this);
assert(bytes.size() == 1);
uint64_t n;
@@ -786,6 +807,7 @@ 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);
Pointer dst(*this, d), src(*this, s);
dst.is_dereferenceable(bytesize, align_dst, true);
src.is_dereferenceable(bytesize, align_src, false);

ADD
tests/alive-tv/memory-opt/bwiden-calloc.src.ll
+; TEST-ARGS: -disable-undef-input -dbg
+; -disable-undef-input was given to address timeout.
+
+define i32 @calloc_init(i32 %x) {
+ %ptr0 = call noalias i8* @calloc(i64 1, i64 4)
+ %ptr = bitcast i8* %ptr0 to i32*
+ store i32 %x, i32* %ptr, align 4
+ %v = load i32, i32* %ptr, align 4
+ call void @free(i8* %ptr0)
+ ret i32 %v
+}
+
+; calloc's bwiden is not supported yet
+; CHECK: bits_byte: 8
+
+declare noalias i8* @calloc(i64, i64)
+declare void @free(i8*)

ADD
tests/alive-tv/memory-opt/bwiden-calloc.tgt.ll
+define i32 @calloc_init(i32 %x) {
+ %ptr0 = call noalias i8* @calloc(i64 1, i64 4)
+ %ptr = bitcast i8* %ptr0 to i32*
+ store i32 %x, i32* %ptr, align 4
+ call void @free(i8* %ptr0)
+ ret i32 %x
+}
+
+; calloc's bwiden is not supported yet
+; CHECK: bits_byte: 8
+
+declare noalias i8* @calloc(i64, i64)
+declare void @free(i8*)

ADD
tests/alive-tv/memory-opt/bwiden_2.src.ll
+; TEST-ARGS: -dbg
+
+define i32 @f() {
+ %a = alloca i32
+ %b = alloca i16
+ %c = alloca i32
+ store i32 1, i32* %a, align 4
+ store i16 257, i16* %b, align 2
+ store i32 3, i32* %c, align 4
+ %x = load i32, i32* %a, align 4
+ %y0 = load i16, i16* %b, align 2
+ %y = zext i16 %y0 to i32
+ %z = load i32, i32* %c, align 4
+ %res1 = add i32 %x, %y
+ %res2 = add i32 %res1, %z
+ ret i32 %res2
+}
+
+; CHECK: bits_byte: 16

ADD
tests/alive-tv/memory-opt/bwiden_2.tgt.ll
+define i32 @f() {
+ ret i32 261
+}

ADD
tests/alive-tv/memory-opt/bwiden_4.src.ll
+; TEST-ARGS: -dbg
+
+define i32 @f() {
+ %a = alloca i32
+ %b = alloca i32, align 8
+ %c = alloca i32
+ store i32 1, i32* %a, align 4
+ store i32 2, i32* %b, align 8
+ store i32 3, i32* %c, align 4
+ %x = load i32, i32* %a, align 4
+ %y = load i32, i32* %b, align 4
+ %z = load i32, i32* %c, align 4
+ %res1 = add i32 %x, %y
+ %res2 = add i32 %res1, %z
+ ret i32 %res2
+}
+
+; CHECK: bits_byte: 32

ADD
tests/alive-tv/memory-opt/bwiden_4.tgt.ll
+define i32 @f() {
+ ret i32 6
+}

ADD
tests/alive-tv/memory-opt/bwiden_8.src.ll
+; TEST-ARGS: -dbg
+
+define i64 @f() {
+ %a = alloca i64
+ %b = alloca i64
+ %c = alloca i64
+ store i64 1, i64* %a, align 8
+ store i64 2, i64* %b, align 8
+ store i64 3, i64* %c, align 8
+ %x = load i64, i64* %a, align 8
+ %y = load i64, i64* %b, align 8
+ %z = load i64, i64* %c, align 8
+ %res1 = add i64 %x, %y
+ %res2 = add i64 %res1, %z
+ ret i64 %res2
+}
+
+; CHECK: bits_byte: 64

ADD
tests/alive-tv/memory-opt/bwiden_8.tgt.ll
+define i64 @f() {
+ ret i64 6
+}

MODIFY
tools/transform.cpp
tools/transform.cpp
#include "util/config.h"
#include "util/errors.h"
#include "util/symexec.h"
+#include <algorithm>
#include <map>
#include <set>
#include <sstream>
@@ -346,6 +347,9 @@ static void calculateAndInitConstants(Transform &t) {
const auto &globals_src = t.src.getGlobalVars();
unsigned num_globals = globals_src.size();
+ // TODO: get this from data layout, varies among address spaces
+ bits_size_t = 64;
+
for (auto GVT : globals_tgt) {
auto I = find_if(globals_src.begin(), globals_src.end(),
[GVT](auto *GV) -> bool { return GVT->getName() == GV->getName(); });
@@ -379,6 +383,45 @@ static void calculateAndInitConstants(Transform &t) {
return false;
return true;
};
+ // Returns access size. 0 if no access, -1 if unknown
+ const uint64_t UNKNOWN = 1, NO_ACCESS = 0;
+ auto get_access_size = [&](const Instr &inst) -> uint64_t {
+ if (dynamic_cast<const BinOp *>(&inst) ||
+ dynamic_cast<const UnaryOp *>(&inst) ||
+ dynamic_cast<const TernaryOp *>(&inst) ||
+ dynamic_cast<const ConversionOp *>(&inst) ||
+ dynamic_cast<const Return *>(&inst))
+ return NO_ACCESS;
+
+ if (dynamic_cast<const Alloc *>(&inst) ||
+ dynamic_cast<const Malloc *>(&inst))
+ // They are uninitialized (no actual bytes written), so assume that they
+ // are not accessed.
+ // Calloc is different: it contains memset to zero
+ return NO_ACCESS;
+
+ Type *value_ty = nullptr;
+ unsigned align = 0;
+ if (auto st = dynamic_cast<const Store *>(&inst)) {
+ value_ty = &st->getValue()->getType();
+ align = st->getAlign();
+ } else if (auto ld = dynamic_cast<const Load *>(&inst)) {
+ value_ty = &ld->getType();
+ align = ld->getAlign();
+ }
+
+ if (value_ty) {
+ if (dynamic_cast<const IntType *>(value_ty) ||
+ dynamic_cast<const FloatType *>(value_ty))
+ return gcd(align, util::divide_up(value_ty->bits(), 8));
+ else if (dynamic_cast<const PtrType *>(value_ty))
+ return gcd(align, bits_size_t / 8);
+ // Aggregate types should consider padding
+ return UNKNOWN;
+ }
+
+ return UNKNOWN;
+ };
// The number of instructions that can return a pointer to a non-local block.
num_max_nonlocals_inst = 0;
@@ -408,6 +451,8 @@ static void calculateAndInitConstants(Transform &t) {
nullptr_is_used = false;
has_int2ptr = false;
has_ptr2int = false;
+ // Mininum access size (in bytes)
+ uint64_t min_access_size = 512;
for (auto fn : { &t.src, &t.tgt }) {
for (auto BB : fn->getBBs()) {
@@ -419,6 +464,10 @@ static void calculateAndInitConstants(Transform &t) {
has_int2ptr |= conv->getOp() == ConversionOp::Int2Ptr;
has_ptr2int |= conv->getOp() == ConversionOp::Ptr2Int;
}
+
+ auto accsz = get_access_size(I);
+ if (accsz != NO_ACCESS)
+ min_access_size = gcd(min_access_size, accsz);
}
}
}
@@ -432,7 +481,9 @@ static void calculateAndInitConstants(Transform &t) {
// TODO
bits_for_offset = 64;
- bits_size_t = 64;
+
+ // size of byte
+ bits_byte = 8 * (unsigned)min_access_size;
little_endian = t.src.isLittleEndian();
@@ -443,6 +494,7 @@ static void calculateAndInitConstants(Transform &t) {
"bits_for_bid: " << bits_for_bid << "\n"
"bits_for_offset: " << bits_for_offset << "\n"
"bits_size_t: " << bits_size_t << "\n"
+ "bits_byte: " << bits_byte << "\n"
"little_endian: " << little_endian << "\n"
"nullptr_is_used: " << nullptr_is_used << "\n"
"has_int2ptr: " << has_int2ptr << "\n"

MODIFY
util/compiler.cpp
util/compiler.cpp
@@ -61,4 +61,12 @@ uint64_t divide_up(uint64_t n, uint64_t amount) {
return (n + amount - 1) / amount;
}
+uint64_t gcd(uint64_t n, uint64_t m) {
+ assert(n != 0 || m != 0);
+ if (n < m) return gcd(m, n);
+ else if (m == 0) return n;
+ else if (n % m == 0) return m;
+ return gcd(m, n % m);
+}
+
}

MODIFY
util/compiler.h
util/compiler.h
@@ -49,5 +49,5 @@ unsigned num_leading_zeros(uint64_t n);
unsigned num_trailing_zeros(uint64_t n);
uint64_t divide_up(uint64_t n, uint64_t amount); // division with ceiling
-
+uint64_t gcd(uint64_t a, uint64_t b);
}

Memory: optimize encoding of bytes by widening byte size if possible (#197)