Memory: use non-local bid 0 as a plain block id if there is no null block
MODIFY
ir/globals.cpp
ir/globals.cpp
@@ -31,6 +31,7 @@ bool has_nocapture;
bool has_readonly;
bool has_readnone;
bool has_dead_allocas;
+bool has_null_block;
bool does_int_mem_access;
bool does_ptr_mem_access;
bool does_ptr_store;

MODIFY
ir/globals.h
ir/globals.h
@@ -59,6 +59,10 @@ extern bool has_readnone;
/// Whether there are allocas that are initially dead (need start_lifetime)
extern bool has_dead_allocas;
+/// Whether there is a pointer that can point to the null block
+/// ex) undef ptr constant, fn arg
+extern bool has_null_block;
+
/// Whether the programs do memory accesses that load/store int/ptrs
extern bool does_int_mem_access;
extern bool does_ptr_mem_access;

MODIFY
ir/memory.cpp
ir/memory.cpp
@@ -476,7 +476,8 @@ expr Pointer::getAddress(bool simplify) const {
auto zero = expr::mkUInt(0, bits_size_t - 1);
// fast path for null ptrs
auto non_local
- = simplify && bid.isZero() ? zero : expr::mkUF("blk_addr", { bid }, zero);
+ = simplify && bid.isZero() && IR::has_null_block ?
+ zero : expr::mkUF("blk_addr", { bid }, zero);
// Non-local block area is the lower half
non_local = expr::mkUInt(0, 1).concat(non_local);
@@ -900,13 +901,13 @@ void Pointer::stripAttrs() {
Pointer Pointer::mkNullPointer(const Memory &m) {
// Null pointer exists if either source or target uses it.
- assert(num_nonlocals > 0);
+ assert(IR::has_null_block);
// A null pointer points to block 0 without any attribute.
return { m, 0, false };
}
expr Pointer::isNull() const {
- if (num_nonlocals == 0)
+ if (!IR::has_null_block)
return false;
return *this == mkNullPointer(m);
}
@@ -1003,9 +1004,10 @@ static expr load(const Pointer &p, const expr &local, const expr &non_local) {
return mkIf_fold(p.isLocal(), local.load(idx), non_local.load(idx));
}
-// Global block id 0 is reserved for a null block.
static unsigned last_local_bid = 0;
-static unsigned last_nonlocal_bid = 1;
+// Global block id 0 is reserved for a null block if IR::has_null_block is true.
+// State::resetGlobals() sets last_nonlocal_bid to IR::has_null_block.
+static unsigned last_nonlocal_bid = 0;
static bool memory_unused() {
return num_locals == 0 && num_nonlocals == 0;
@@ -1093,7 +1095,7 @@ Memory::Memory(State &state) : state(&state) {
// the block) should not overflow.
// Initialize a memory block for null pointer.
- if (IR::num_nonlocals > 0)
+ if (IR::has_null_block)
alloc(expr::mkUInt(0, bits_size_t), bits_program_pointer, GLOBAL, false,
false, 0);
@@ -1113,7 +1115,7 @@ void Memory::mkAxioms(const Memory &other) const {
// transformation can increase alignment
unsigned align = heap_block_alignment;
- for (unsigned bid = 1; bid < IR::num_nonlocals; ++bid) {
+ for (unsigned bid = IR::has_null_block; bid < IR::num_nonlocals; ++bid) {
Pointer p(*this, bid, false);
Pointer q(other, bid, false);
auto p_align = p.blockAlignment();
@@ -1126,12 +1128,12 @@ void Memory::mkAxioms(const Memory &other) const {
if (!observes_addresses())
return;
- if (IR::num_nonlocals > 0)
+ if (IR::has_null_block)
state->addAxiom(Pointer::mkNullPointer(*this).getAddress(false) == 0);
// Non-local blocks are disjoint.
// Ignore null pointer block
- for (unsigned bid = 1; bid < IR::num_nonlocals; ++bid) {
+ for (unsigned bid = has_null_block; bid < IR::num_nonlocals; ++bid) {
Pointer p1(*this, bid, false);
expr disj = p1.getAddress() != 0;
@@ -1635,7 +1637,7 @@ expr Memory::int2ptr(const expr &val) const {
pair<expr,Pointer>
Memory::refined(const Memory &other, bool skip_constants,
const vector<pair<StateValue, bool>> *set_ptrs) const {
- if (IR::num_nonlocals <= 1)
+ if (IR::num_nonlocals <= IR::has_null_block)
return { true, Pointer(*this, expr()) };
assert(!memory_unused());
@@ -1651,7 +1653,7 @@ Memory::refined(const Memory &other, bool skip_constants,
m.non_local_blk_nonwritable.end();
};
- for (unsigned bid = 1; bid < IR::num_nonlocals_src; ++bid) {
+ for (unsigned bid = IR::has_null_block; bid < IR::num_nonlocals_src; ++bid) {
if (skip_constants && is_constglb(*this, bid)) {
assert(is_constglb(other, bid));
continue;
@@ -1686,7 +1688,7 @@ expr Memory::checkNocapture() const {
auto ofs = expr::mkVar(name.c_str(), bits_for_offset);
expr res(true);
- for (unsigned bid = 1; bid < numNonlocals(); ++bid) {
+ for (unsigned bid = IR::has_null_block; bid < numNonlocals(); ++bid) {
Pointer p(*this, expr::mkUInt(bid, bits_for_bid), ofs);
Byte b(*this, non_local_block_val.load(p.shortPtr()));
Pointer loadp(*this, b.ptrValue());

MODIFY
ir/state.cpp
ir/state.cpp
@@ -38,7 +38,7 @@ State::State(Function &f, bool source)
return_val(f.getType().getDummyValue(false)), return_memory(memory) {}
void State::resetGlobals() {
- Memory::resetBids(1);
+ Memory::resetBids(has_null_block);
}
const StateValue& State::exec(const Value &v) {

ADD
tests/alive-tv/opt-memory/has_null_block-2.srctgt.ll
+; TEST-ARGS: -dbg
+
+define i8* @src() {
+ %q = call i8* @malloc(i32 1)
+ ret i8* %q
+}
+
+define i8* @tgt() {
+ %q = call i8* @malloc(i32 1)
+ ret i8* %q
+}
+
+declare i8* @malloc(i32)
+
+; CHECK: has_null_block: 1

ADD
tests/alive-tv/opt-memory/has_null_block-3.srctgt.ll
+; TEST-ARGS: -dbg
+
+define i8* @src(i8* %p) {
+ ret i8* %p
+}
+
+define i8* @tgt(i8* %p) {
+ ret i8* %p
+}
+
+; CHECK: has_null_block: 1

ADD
tests/alive-tv/opt-memory/has_null_block-4.srctgt.ll
+; TEST-ARGS: -dbg
+
+@x = global i8* null
+
+define i8* @src() {
+ %q = load i8*, i8** @x
+ ret i8* %q
+}
+
+define i8* @tgt() {
+ %q = load i8*, i8** @x
+ ret i8* %q
+}
+
+; CHECK: has_null_block: 1

ADD
tests/alive-tv/opt-memory/has_null_block-5.srctgt.ll
+; TEST-ARGS: -dbg
+
+define i8* @src() {
+ ret i8* null
+}
+
+define i8* @tgt() {
+ ret i8* null
+}
+
+; CHECK: has_null_block: 1

ADD
tests/alive-tv/opt-memory/has_null_block.srctgt.ll
+; TEST-ARGS: -dbg
+
+@x = global i32 0
+
+define i32 @src() {
+ %p = alloca i32
+ %p2 = getelementptr i32, i32* %p, i32 0
+ %y = load i32, i32* @x
+ ret i32 %y
+}
+
+define i32 @tgt() {
+ %p = alloca i32
+ %p2 = getelementptr i32, i32* %p, i32 0
+ %y = load i32, i32* @x
+ ret i32 %y
+}
+
+; CHECK: has_null_block: 0

MODIFY
tools/transform.cpp
tools/transform.cpp
@@ -720,6 +720,7 @@ static void calculateAndInitConstants(Transform &t) {
has_malloc = false;
has_free = false;
has_fncall = false;
+ has_null_block = false;
does_ptr_store = false;
does_ptr_mem_access = false;
does_int_mem_access = false;
@@ -767,11 +768,13 @@ static void calculateAndInitConstants(Transform &t) {
}
}
- num_nonlocals_src = num_globals_src + num_ptrinputs + num_max_nonlocals_inst;
// check if null block is needed
- if (num_nonlocals_src > 0 || num_globals > 0 ||
- nullptr_is_used || has_malloc || has_ptr_load || has_fncall)
- ++num_nonlocals_src;
+ // Global variables cannot be null pointers
+ has_null_block = num_ptrinputs > 0 || nullptr_is_used || has_malloc ||
+ has_ptr_load || has_fncall;
+
+ num_nonlocals_src = num_globals_src + num_ptrinputs + num_max_nonlocals_inst +
+ has_null_block;
// Allow at least one non-const global for calls to change
num_nonlocals_src += has_fncall;
@@ -859,6 +862,7 @@ static void calculateAndInitConstants(Transform &t) {
<< "\nhas_ptr2int: " << has_ptr2int
<< "\nhas_malloc: " << has_malloc
<< "\nhas_free: " << has_free
+ << "\nhas_null_block: " << has_null_block
<< "\ndoes_ptr_store: " << does_ptr_store
<< "\ndoes_ptr_mem_access: " << does_ptr_mem_access
<< "\ndoes_int_mem_access: " << does_int_mem_access

Memory: use non-local bid 0 as a plain block id if there is no null block (#367)