Support lifetime.start (2/2)
MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -1681,14 +1681,17 @@ void Alloc::rauw(const Value &what, Value &with) {
void Alloc::print(std::ostream &os) const {
os << getName() << " = alloca " << *size << ", align " << align;
+ if (initially_dead)
+ os << ", dead";
}
StateValue Alloc::toSMT(State &s) const {
auto &[sz, np] = s[*size];
auto &m = s.getMemory();
- auto p = m.alloc(sz, align, Memory::STACK);
+ auto [p, allocated] = m.alloc(sz, align, Memory::STACK, nullopt,
+ nullptr, !initially_dead);
// Alloca cannot be null; when OOM, the program halts with stack overflow.
- s.addUB(np && p != Pointer::mkNullPointer(m)());
+ s.addUB(np && (allocated || initially_dead));
return { move(p), true };
}
@@ -1699,7 +1702,8 @@ expr Alloc::getTypeConstraints(const Function &f) const {
}
unique_ptr<Instr> Alloc::dup(const string &suffix) const {
- return make_unique<Alloc>(getType(), getName() + suffix, *size, align);
+ return make_unique<Alloc>(getType(), getName() + suffix, *size, align,
+ initially_dead);
}
@@ -1718,15 +1722,16 @@ void Malloc::print(std::ostream &os) const {
StateValue Malloc::toSMT(State &s) const {
auto &[sz, np] = s[*size];
// TODO: malloc's alignment is implementation defined.
- auto p = s.getMemory().alloc(sz, 8, Memory::HEAP);
+ auto [p, allocated] = s.getMemory().alloc(sz, 8, Memory::HEAP);
if (isNonNull) {
// TODO: In C++ we need to throw an exception if the allocation fails, but
// exception hasn't been modeled yet
- s.addUB(p != Pointer::mkNullPointer(s.getMemory())());
+ s.addUB(move(allocated));
}
- return { move(p), expr(np) };
+ expr nullp = Pointer::mkNullPointer(s.getMemory())();
+ return { expr::mkIf(move(allocated), move(p), move(nullp)), expr(np) };
}
expr Malloc::getTypeConstraints(const Function &f) const {
@@ -1759,11 +1764,13 @@ StateValue Calloc::toSMT(State &s) const {
// TODO: check calloc align.
expr size = nm * sz;
- auto p = s.getMemory().alloc(size, 8, Memory::HEAP, std::nullopt,
- nullptr, nm.mul_no_uoverflow(sz));
+ auto [p0, allocated] = s.getMemory().alloc(size, 8, Memory::HEAP,
+ std::nullopt, nullptr,
+ nm.mul_no_uoverflow(sz));
- expr is_null = p == Pointer::mkNullPointer(s.getMemory())();
- expr calloc_sz = expr::mkIf(is_null, expr::mkUInt(0, sz.bits()), size);
+ expr nullp = Pointer::mkNullPointer(s.getMemory())();
+ expr p = expr::mkIf(allocated, move(p0), move(nullp));
+ expr calloc_sz = expr::mkIf(allocated, size, expr::mkUInt(0, sz.bits()));
// If memset's size is zero, then ptr can be NULL.
s.getMemory().memset(p, { expr::mkUInt(0, 8), true }, calloc_sz, 1);
@@ -1798,8 +1805,9 @@ void StartLifetime::print(std::ostream &os) const {
StateValue StartLifetime::toSMT(State &s) const {
auto &[p, np] = s[*ptr];
- s.addUB(np);
- s.getMemory().start_lifetime(p);
+ expr allocated = s.getMemory().start_lifetime(p);
+ // This should be coherent with Alloc's OOM semantics
+ s.addUB(np && allocated);
return {};
}

MODIFY
ir/instr.h
ir/instr.h
@@ -372,9 +372,12 @@ public:
class Alloc final : public Instr {
Value *size;
unsigned align;
+ bool initially_dead;
public:
- Alloc(Type &type, std::string &&name, Value &size, unsigned align)
- : Instr(type, std::move(name)), size(&size), align(align) {}
+ Alloc(Type &type, std::string &&name, Value &size, unsigned align,
+ bool initially_dead)
+ : Instr(type, std::move(name)), size(&size), align(align),
+ initially_dead(initially_dead) {}
std::vector<Value*> operands() const override;
void rauw(const Value &what, Value &with) override;

MODIFY
ir/memory.cpp
ir/memory.cpp
@@ -793,7 +793,7 @@ static expr disjoint_local_blocks(const Memory &m, const expr &addr,
return disj;
}
-expr Memory::alloc(const expr &size, unsigned align, BlockKind blockKind,
+pair<expr, expr> Memory::alloc(const expr &size, unsigned align, BlockKind blockKind,
optional<unsigned> bidopt, unsigned *bid_out,
const expr &precond) {
assert(!memory_unused());
@@ -886,14 +886,33 @@ expr Memory::alloc(const expr &size, unsigned align, BlockKind blockKind,
(is_local ? local_blk_kind : non_local_blk_kind)
.add(short_bid, expr::mkUInt(alloc_ty, 2));
- return expr::mkIf(allocated, p(), Pointer::mkNullPointer(*this)());
+ return { p.release(), move(allocated) };
}
-void Memory::start_lifetime(const expr &ptr_local) {
+expr Memory::start_lifetime(const expr &ptr_local) {
assert(!memory_unused());
Pointer p(*this, ptr_local);
+
+ auto align = *local_blk_align(p.get_short_bid());
+ auto size_upperbound = p.block_size() + align.zextOrTrunc(bits_size_t) -
+ expr::mkUInt(1, bits_size_t);
+ auto allocated = size_upperbound.ule(local_avail_space.zext(1));
+
+ if (observes_addresses()) {
+ // Disjointness of block's address range with other local blocks
+ state->addPre(
+ allocated.implies(disjoint_local_blocks(*this, p.get_address(),
+ p.block_size(), local_blk_addr)));
+ }
+ auto size_upperbound_trunc = size_upperbound.trunc(bits_size_t - 1);
+ // Reduces memory usage even if the alloca was alive before lifetime.start
+ // for performance
+ local_avail_space = expr::mkIf(allocated,
+ local_avail_space - size_upperbound_trunc,
+ local_avail_space);
+ // alloca is always alive after lifetime.start(), otherwise it should be UB
local_block_liveness = local_block_liveness.store(p.get_short_bid(), true);
- // TODO: encode disjointness of lock blocks if lifetime starts
+ return allocated;
}
void Memory::free(const expr &ptr, bool unconstrained) {

MODIFY
ir/memory.h
ir/memory.h
@@ -200,20 +200,19 @@ public:
smt::expr mkInput(const char *name) const;
std::pair<smt::expr, smt::expr> mkUndefInput() const;
- // Allocates a new memory block.
+ // Allocates a new memory block and returns (pointer expr, allocated).
// If bid is not specified, it creates a fresh block id by increasing
// last_bid.
// If bid is specified, the bid is used, and last_bid is not increased.
- // In this case, it is caller's responsibility to give a unique bid, and
- // bumpLastBid() should be called in advance to correctly do this.
+ // In this case, it is caller's responsibility to give a unique bid.
// The newly assigned bid is stored to bid_out if bid_out != nullptr.
- smt::expr alloc(const smt::expr &size, unsigned align, BlockKind blockKind,
- std::optional<unsigned> bid = std::nullopt,
- unsigned *bid_out = nullptr,
- const smt::expr &precond = true);
+ std::pair<smt::expr, smt::expr> alloc(const smt::expr &size, unsigned align,
+ BlockKind blockKind, std::optional<unsigned> bid = std::nullopt,
+ unsigned *bid_out = nullptr, const smt::expr &precond = true);
// Start lifetime of a local block.
- void start_lifetime(const smt::expr &ptr_local);
+ // Returns whether it is successfully allocated.
+ smt::expr start_lifetime(const smt::expr &ptr_local);
// If unconstrained is true, the pointer offset, liveness, and block kind
// are not checked.

MODIFY
ir/value.cpp
ir/value.cpp
@@ -94,14 +94,14 @@ StateValue GlobalVariable::toSMT(State &s) const {
if (!allocated) {
// Use the same block id that is used by src
assert(!s.isSource());
- ptrval = s.getMemory().alloc(sizeexpr, align, blkkind, glbvar_bid);
+ ptrval = s.getMemory().alloc(sizeexpr, align, blkkind, glbvar_bid).first;
s.markGlobalAsAllocated(getName());
} else {
ptrval = Pointer(s.getMemory(), glbvar_bid, false).release();
}
} else {
ptrval = s.getMemory().alloc(sizeexpr, align, blkkind, nullopt,
- &glbvar_bid);
+ &glbvar_bid).first;
s.addGlobalVarBid(getName(), glbvar_bid);
}
return { move(ptrval), true };

MODIFY
llvm_util/llvm2alive.cpp
llvm_util/llvm2alive.cpp
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/InstVisitor.h"
#include "llvm/IR/Operator.h"
+#include <set>
#include <utility>
#include <vector>
@@ -349,6 +350,23 @@ public:
RETURN_IDENTIFIER(move(inst));
}
+ bool hasLifetimeStart(llvm::User &i, std::set<llvm::Value *> &visited) {
+ for (auto I = i.user_begin(), E = i.user_end(); I != E; ++I) {
+ llvm::User *U = *I;
+ if (!visited.insert(U).second)
+ continue;
+ if (auto I = llvm::dyn_cast<llvm::IntrinsicInst>(U)) {
+ if (I->getIntrinsicID() == llvm::Intrinsic::lifetime_start)
+ return true;
+ }
+ if ((llvm::isa<llvm::BitCastInst>(U) ||
+ llvm::isa<llvm::GetElementPtrInst>(U) ||
+ llvm::isa<llvm::PHINode>(U)) && hasLifetimeStart(*U, visited))
+ return true;
+ }
+ return false;
+ }
+
RetTy visitAllocaInst(llvm::AllocaInst &i) {
// TODO
if (i.isArrayAllocation() || !i.isStaticAlloca())
@@ -358,10 +376,12 @@ public:
if (!ty)
return error(i);
+ std::set<llvm::Value *> visited;
// FIXME: size bits shouldn't be a constant
auto size = make_intconst(DL().getTypeAllocSize(i.getAllocatedType()), 64);
RETURN_IDENTIFIER(make_unique<Alloc>(*ty, value_name(i), *size,
- pref_alignment(i, i.getAllocatedType())));
+ pref_alignment(i, i.getAllocatedType()),
+ hasLifetimeStart(i, visited)));
}
RetTy visitGetElementPtrInst(llvm::GetElementPtrInst &i) {

MODIFY
tests/alive-tv/memory/lifetime-2.src.ll
tests/alive-tv/memory/lifetime-2.src.ll
declare void @llvm.lifetime.start.p0i8(i64, i8*)
declare void @llvm.lifetime.end.p0i8(i64, i8*)
-define i32 @f() {
+define i32 @f_end() {
%p = alloca i32
%p0 = bitcast i32* %p to i8*
@@ -14,3 +14,17 @@ define i32 @f() {
ret i32 %v
}
+define i32 @f_start() {
+ %p = alloca i32
+
+ store i32 10, i32* %p
+ ; load before lifetime.start can be optimized to undef
+ %v = load i32, i32* %p
+
+ %p0 = bitcast i32* %p to i8*
+ call void @llvm.lifetime.start.p0i8(i64 4, i8* %p0)
+ call void @llvm.lifetime.end.p0i8(i64 4, i8* %p0)
+
+ ret i32 %v
+}
+

MODIFY
tests/alive-tv/memory/lifetime-2.tgt.ll
tests/alive-tv/memory/lifetime-2.tgt.ll
declare void @llvm.lifetime.start.p0i8(i64, i8*)
declare void @llvm.lifetime.end.p0i8(i64, i8*)
-define i32 @f() {
+define i32 @f_end() {
%p = alloca i32
%p0 = bitcast i32* %p to i8*
@@ -13,3 +13,13 @@ define i32 @f() {
ret i32 undef
}
+define i32 @f_start() {
+ %p = alloca i32
+
+ %p0 = bitcast i32* %p to i8*
+ call void @llvm.lifetime.start.p0i8(i64 4, i8* %p0)
+ call void @llvm.lifetime.end.p0i8(i64 4, i8* %p0)
+
+ ret i32 undef
+}
+

ADD
tests/alive-tv/memory/lifetime-reorder.src.ll
+declare void @llvm.lifetime.start.p0i8(i64, i8*)
+declare void @llvm.lifetime.end.p0i8(i64, i8*)
+
+define i8 @gep1() {
+ %p = alloca i32
+
+ %p0 = bitcast i32* %p to i8*
+ call void @llvm.lifetime.start.p0i8(i64 4, i8* %p0)
+ %p1 = getelementptr i8, i8* %p0, i32 1
+ store i8 10, i8* %p1
+ %v = load i8, i8* %p1
+ call void @llvm.lifetime.end.p0i8(i64 4, i8* %p0)
+
+ ret i8 %v
+}
+
+define i8 @gep2() {
+ %p = alloca i32
+
+ %p0 = bitcast i32* %p to i8*
+ %p1 = getelementptr i8, i8* %p0, i32 1
+ call void @llvm.lifetime.start.p0i8(i64 4, i8* %p0)
+ store i8 10, i8* %p1
+ %v = load i8, i8* %p1
+ call void @llvm.lifetime.end.p0i8(i64 4, i8* %p0)
+
+ ret i8 %v
+}
+
+define i64 @ptrtoint1() {
+ %p = alloca i32
+ %dummy = alloca i64
+
+ %p0 = bitcast i32* %p to i8*
+ %i = ptrtoint i32* %p to i64
+ call void @llvm.lifetime.start.p0i8(i64 4, i8* %p0)
+ call void @llvm.lifetime.end.p0i8(i64 4, i8* %p0)
+
+ ret i64 %i
+}
+
+define i64 @ptrtoint2() {
+ %p = alloca i32
+ %dummy = alloca i64
+
+ %p0 = bitcast i32* %p to i8*
+ call void @llvm.lifetime.start.p0i8(i64 4, i8* %p0)
+ %i = ptrtoint i32* %p to i64
+ call void @llvm.lifetime.end.p0i8(i64 4, i8* %p0)
+
+ ret i64 %i
+}

ADD
tests/alive-tv/memory/lifetime-reorder.tgt.ll
+declare void @llvm.lifetime.start.p0i8(i64, i8*)
+declare void @llvm.lifetime.end.p0i8(i64, i8*)
+
+define i8 @gep1() {
+ %p = alloca i32
+
+ %p0 = bitcast i32* %p to i8*
+ %p1 = getelementptr i8, i8* %p0, i32 1
+ call void @llvm.lifetime.start.p0i8(i64 4, i8* %p0)
+ store i8 10, i8* %p1
+ %v = load i8, i8* %p1
+ call void @llvm.lifetime.end.p0i8(i64 4, i8* %p0)
+
+ ret i8 %v
+}
+
+define i8 @gep2() {
+ %p = alloca i32
+
+ %p0 = bitcast i32* %p to i8*
+ call void @llvm.lifetime.start.p0i8(i64 4, i8* %p0)
+ %p1 = getelementptr i8, i8* %p0, i32 1
+ store i8 10, i8* %p1
+ %v = load i8, i8* %p1
+ call void @llvm.lifetime.end.p0i8(i64 4, i8* %p0)
+
+ ret i8 %v
+}
+
+define i64 @ptrtoint1() {
+ %p = alloca i32
+ %dummy = alloca i64
+
+ %p0 = bitcast i32* %p to i8*
+ call void @llvm.lifetime.start.p0i8(i64 4, i8* %p0)
+ %i = ptrtoint i32* %p to i64
+ call void @llvm.lifetime.end.p0i8(i64 4, i8* %p0)
+
+ ret i64 %i
+}
+
+define i64 @ptrtoint2() {
+ %p = alloca i32
+ %dummy = alloca i64
+
+ %p0 = bitcast i32* %p to i8*
+ %i = ptrtoint i32* %p to i64
+ call void @llvm.lifetime.start.p0i8(i64 4, i8* %p0)
+ call void @llvm.lifetime.end.p0i8(i64 4, i8* %p0)
+
+ ret i64 %i
+}

Support lifetime.start (2/2) (#242)