Add support for nofree attribute
MODIFY
ir/attrs.cpp
ir/attrs.cpp
@@ -38,6 +38,8 @@ ostream& operator<<(ostream &os, const FnAttrs &attr) {
os << " dereferenceable(" << attr.derefBytes << ")";
if (attr.has(FnAttrs::NonNull))
os << " nonnull";
+ if (attr.has(FnAttrs::NoFree))
+ os << " nofree";
return os;
}

MODIFY
ir/attrs.h
ir/attrs.h
@@ -33,7 +33,8 @@ class FnAttrs final {
public:
enum Attribute { None = 0, NoRead = 1 << 0, NoWrite = 1 << 1,
ArgMemOnly = 1 << 2, NNaN = 1 << 3, NoReturn = 1 << 4,
- Dereferenceable = 1 << 5, NonNull = 1 << 6 };
+ Dereferenceable = 1 << 5, NonNull = 1 << 6,
+ NoFree = 1 << 7 };
FnAttrs(unsigned bits = None) : bits(bits) {}

MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -2385,6 +2385,10 @@ StateValue Free::toSMT(State &s) const {
s.addUB(np);
// If not heaponly, don't encode constraints
s.getMemory().free(p, !heaponly);
+
+ if (s.getFn().getFnAttrs().has(FnAttrs::NoFree) && heaponly)
+ s.addUB(expr(false));
+
return {};
}

MODIFY
ir/memory.cpp
ir/memory.cpp
@@ -707,7 +707,7 @@ expr Pointer::isBlockAlive() const {
// If programs have no free(), we assume all blocks are always live.
// For non-local blocks, there's enough non-determinism through block size,
// that can be 0 or non-0
- if (!has_free && !has_fncall && !has_dead_allocas)
+ if (!has_free && !has_dead_allocas)
return true;
// globals are always live
@@ -728,7 +728,7 @@ expr Pointer::getAllocType() const {
// If programs have no malloc & free, we don't need to store this information
// since it is only used to check if free/delete is ok and
// for memory refinement of local malloc'ed blocks
- if (!has_malloc && !has_free && !has_fncall && !has_alloca)
+ if (!has_malloc && !has_free && !has_alloca)
return expr::mkUInt(GLOBAL, 2);
// if malloc is used, but no free, we can still ignore info for non-locals
@@ -1262,7 +1262,7 @@ expr Memory::CallState::implies(const CallState &st) const {
}
Memory::CallState
-Memory::mkCallState(const vector<PtrInput> *ptr_inputs) const {
+Memory::mkCallState(const vector<PtrInput> *ptr_inputs, bool nofree) const {
CallState st;
st.empty = false;
@@ -1295,10 +1295,10 @@ Memory::mkCallState(const vector<PtrInput> *ptr_inputs) const {
non_local_block_val.load(idx)));
}
- if (num_nonlocals_src) {
+ if (num_nonlocals_src && !nofree) {
expr one = expr::mkUInt(1, num_nonlocals);
expr zero = expr::mkUInt(0, num_nonlocals);
- expr mask = one;
+ expr mask = has_null_block ? one : zero;
for (unsigned bid = has_null_block; bid < num_nonlocals; ++bid) {
expr ok_arg = true;
if (ptr_inputs) {
@@ -1714,6 +1714,11 @@ expr Memory::checkNocapture() const {
return res;
}
+expr Memory::checkNoFree(const CallState &state_after) const {
+ // TODO: encode local block's liveness
+ return state_after.non_local_block_liveness == non_local_block_liveness;
+}
+
Memory Memory::mkIf(const expr &cond, const Memory &then, const Memory &els) {
assert(then.state == els.state);
Memory ret(then);

MODIFY
ir/memory.h
ir/memory.h
@@ -260,7 +260,8 @@ public:
std::pair<smt::expr, smt::expr>
mkFnRet(const char *name,
const std::vector<PtrInput> &ptr_inputs) const;
- CallState mkCallState(const std::vector<PtrInput> *ptr_inputs) const;
+ CallState mkCallState(const std::vector<PtrInput> *ptr_inputs, bool nofree)
+ const;
void setState(const CallState &st);
// Allocates a new memory block and returns (pointer expr, allocated).
@@ -309,6 +310,7 @@ public:
// Returns true if a nocapture pointer byte is not in the memory.
smt::expr checkNocapture() const;
+ smt::expr checkNoFree(const CallState &state_after) const;
unsigned numLocals() const;
unsigned numNonlocals() const;

MODIFY
ir/state.cpp
ir/state.cpp
@@ -263,16 +263,23 @@ State::addFnCall(const string &name, vector<StateValue> &&inputs,
}
string ub_name = name + "#ub";
- I->second = { move(values), expr::mkFreshVar(ub_name.c_str(), false),
+ I->second
+ = { move(values), expr::mkFreshVar(ub_name.c_str(), false),
writes_memory
- ? memory.mkCallState(argmemonly ? &I->first.args_ptr : nullptr)
- : Memory::CallState(), true };
+ ? memory.mkCallState(argmemonly ? &I->first.args_ptr : nullptr,
+ attrs.has(FnAttrs::NoFree))
+ : Memory::CallState(),
+ true };
} else {
I->second.used = true;
}
addUB(I->second.ub);
+ // Caller has nofree attribute; callee should guarantee that it didn't free
+ if (getFn().getFnAttrs().has(FnAttrs::NoFree))
+ addUB(memory.checkNoFree(I->second.callstate));
+
if (writes_memory)
memory.setState(I->second.callstate);

MODIFY
llvm_util/llvm2alive.cpp
llvm_util/llvm2alive.cpp
@@ -250,11 +250,14 @@ public:
return error(i);
FnAttrs attrs;
- if (i.hasFnAttr(llvm::Attribute::ReadOnly))
+ if (i.hasFnAttr(llvm::Attribute::ReadOnly)) {
attrs.set(FnAttrs::NoWrite);
+ attrs.set(FnAttrs::NoFree);
+ }
if (i.hasFnAttr(llvm::Attribute::ReadNone)) {
attrs.set(FnAttrs::NoRead);
attrs.set(FnAttrs::NoWrite);
+ attrs.set(FnAttrs::NoFree);
}
if (i.hasFnAttr(llvm::Attribute::WriteOnly))
attrs.set(FnAttrs::NoRead);
@@ -262,6 +265,8 @@ public:
attrs.set(FnAttrs::ArgMemOnly);
if (i.hasFnAttr(llvm::Attribute::NoReturn))
attrs.set(FnAttrs::NoReturn);
+ if (i.hasFnAttr(llvm::Attribute::NoFree))
+ attrs.set(FnAttrs::NoFree);
if (auto op = dyn_cast<llvm::FPMathOperator>(&i)) {
if (op->hasNoNaNs())
attrs.set(FnAttrs::NNaN);
@@ -941,6 +946,9 @@ public:
}
auto &attrs = Fn.getFnAttrs();
+ if (f.hasFnAttribute(llvm::Attribute::NoFree))
+ attrs.set(FnAttrs::NoFree);
+
const auto &ridx = llvm::AttributeList::ReturnIndex;
if (uint64_t b = f.getDereferenceableBytes(ridx)) {
attrs.set(FnAttrs::Dereferenceable);

ADD
tests/alive-tv/attrs/dereferenceable-callsite-fail.srctgt.ll
+; dereferenceable attribute does not guarantee that the pointer is unfreed
+
+define i32 @src(i1 %c, i32* %p) {
+ENTRY:
+ call void @f(i32* %p)
+ br i1 %c, label %A, label %EXIT
+A:
+ %v1 = load i32, i32* %p
+ br label %EXIT
+EXIT:
+ %val = phi i32 [%v1, %A], [0, %ENTRY]
+ ret i32 %val
+}
+
+define i32 @tgt(i1 %c, i32* %p) {
+ call void @f(i32* %p)
+ %v1 = load i32, i32* %p
+ %val = select i1 %c, i32 %v1, i32 0
+ ret i32 %val
+}
+
+; ERROR: Source is more defined than target
+declare void @f(i32* dereferenceable(4) %ptr)

MODIFY
tests/alive-tv/attrs/dereferenceable-callsite-max.srctgt.ll
tests/alive-tv/attrs/dereferenceable-callsite-max.srctgt.ll
define i32 @src(i1 %c, i32* %p) {
ENTRY:
- call void @f(i32* dereferenceable(4) %p)
br i1 %c, label %A, label %EXIT
A:
%v1 = load i32, i32* %p
br label %EXIT
EXIT:
%val = phi i32 [%v1, %A], [0, %ENTRY]
+ call void @f(i32* dereferenceable(4) %p)
ret i32 %val
}
define i32 @tgt(i1 %c, i32* %p) {
- call void @f(i32* dereferenceable(4) %p)
%v1 = load i32, i32* %p
%val = select i1 %c, i32 %v1, i32 0
+ call void @f(i32* dereferenceable(4) %p)
ret i32 %val
}

MODIFY
tests/alive-tv/attrs/dereferenceable-callsite.srctgt.ll
tests/alive-tv/attrs/dereferenceable-callsite.srctgt.ll
define i32 @src(i1 %c, i32* %p) {
ENTRY:
- call void @f(i32* dereferenceable(4) %p)
br i1 %c, label %A, label %EXIT
A:
%v1 = load i32, i32* %p
br label %EXIT
EXIT:
%val = phi i32 [%v1, %A], [0, %ENTRY]
+ call void @f(i32* dereferenceable(4) %p)
ret i32 %val
}
define i32 @tgt(i1 %c, i32* %p) {
- call void @f(i32* dereferenceable(4) %p)
%v1 = load i32, i32* %p
%val = select i1 %c, i32 %v1, i32 0
+ call void @f(i32* dereferenceable(4) %p)
ret i32 %val
}

MODIFY
tests/alive-tv/attrs/dereferenceable-callsite2.srctgt.ll
tests/alive-tv/attrs/dereferenceable-callsite2.srctgt.ll
define i32 @src(i1 %c, i32* %p) {
ENTRY:
- call void @f(i32* %p)
br i1 %c, label %A, label %EXIT
A:
%v1 = load i32, i32* %p
br label %EXIT
EXIT:
%val = phi i32 [%v1, %A], [0, %ENTRY]
+ call void @f(i32* %p)
ret i32 %val
}
define i32 @tgt(i1 %c, i32* %p) {
- call void @f(i32* %p)
%v1 = load i32, i32* %p
%val = select i1 %c, i32 %v1, i32 0
+ call void @f(i32* %p)
ret i32 %val
}

ADD
tests/alive-tv/attrs/dereferenceable-nofree.srctgt.ll
+define i32 @src(i1 %c, i32* %p) {
+ENTRY:
+ call void @f(i32* %p)
+ br i1 %c, label %A, label %EXIT
+A:
+ %v1 = load i32, i32* %p
+ br label %EXIT
+EXIT:
+ %val = phi i32 [%v1, %A], [0, %ENTRY]
+ ret i32 %val
+}
+
+define i32 @tgt(i1 %c, i32* %p) {
+ call void @f(i32* %p)
+ %v1 = load i32, i32* %p
+ %val = select i1 %c, i32 %v1, i32 0
+ ret i32 %val
+}
+
+declare void @f(i32* dereferenceable(4) %ptr) nofree

ADD
tests/alive-tv/attrs/nofree.srctgt.ll
+define void @src(i1 %c) nofree {
+ %p = call i8* @malloc(i64 4)
+ br i1 %c, label %A, label %EXIT
+A:
+ call void @free(i8* %p)
+ br label %EXIT
+EXIT:
+ ret void
+}
+
+define void @tgt(i1 %c) nofree {
+ %p = call i8* @malloc(i64 4)
+ call void @free(i8* %p)
+ ret void
+}
+
+; ERROR: Source is more defined than target
+
+declare void @free(i8*)
+declare i8* @malloc(i64)

MODIFY
tools/transform.cpp
tools/transform.cpp
@@ -560,7 +560,10 @@ static void calculateAndInitConstants(Transform &t) {
nullptr_is_used |= has_nullptr(op);
}
- has_fncall |= dynamic_cast<const FnCall*>(&i) != nullptr;
+ if (auto *fc = dynamic_cast<const FnCall*>(&i)) {
+ has_fncall |= true;
+ has_free |= !fc->getAttributes().has(FnAttrs::NoFree);
+ }
if (auto *mi = dynamic_cast<const MemInstr *>(&i)) {
max_alloc_size = max(max_alloc_size, mi->getMaxAllocSize());

Add support for nofree attribute (#413)