add support for calloc
MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -1714,6 +1714,54 @@ unique_ptr<Instr> Malloc::dup(const string &suffix) const {
return make_unique<Malloc>(getType(), getName() + suffix, *size, isNonNull);
}
+vector<Value*> Calloc::operands() const {
+ return { num, size };
+}
+
+void Calloc::rauw(const Value &what, Value &with) {
+ RAUW(num);
+ RAUW(size);
+}
+
+void Calloc::print(std::ostream &os) const {
+ os << getName() << " = calloc " << *num << ", " << *size;
+}
+
+StateValue Calloc::toSMT(State &s) const {
+ auto &[nm, np_num] = s[*num];
+ auto &[sz, np_sz] = s[*size];
+
+ // TODO: check calloc align.
+ auto p = s.getMemory().alloc(nm * sz, 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()), nm * sz);
+
+ // If memset's size is zero, then ptr can be NULL.
+ s.getMemory().memset(p, { expr::mkUInt(0, 8), true }, calloc_sz, 1);
+
+ auto nullp = Pointer::mkNullPointer(s.getMemory());
+ auto flag = expr::mkFreshVar("calloc_isnull", expr(true));
+ // TODO: We're moving from nondet. allocation to memory usage tracking, so
+ // this part should be changed.
+ s.addQuantVar(flag);
+ return { expr::mkIf(move(flag), nullp.release(), move(p)),
+ expr(np_num && np_sz) };
+}
+
+expr Calloc::getTypeConstraints(const Function &f) const {
+ return Value::getTypeConstraints() &&
+ getType().enforcePtrType() &&
+ num->getType().enforceIntType() &&
+ size->getType().enforceIntType() &&
+ num->getType() == size->getType();
+}
+
+unique_ptr<Instr> Calloc::dup(const string &suffix) const {
+ return make_unique<Calloc>(getType(), getName() + suffix, *num, *size);
+}
vector<Value*> Free::operands() const {
return { ptr };

MODIFY
ir/instr.h
ir/instr.h
@@ -389,6 +389,20 @@ public:
std::unique_ptr<Instr> dup(const std::string &suffix) const override;
};
+class Calloc final : public Instr {
+ Value *num, *size;
+public:
+ Calloc(Type &type, std::string &&name, Value &num, Value &size)
+ : Instr(type, std::move(name)), num(&num), size(&size) {}
+
+ std::vector<Value*> operands() const override;
+ void rauw(const Value &what, Value &with) override;
+ void print(std::ostream &os) const override;
+ 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;
+};
+
class Free final : public Instr {
Value *ptr;
public:

MODIFY
ir/memory.cpp
ir/memory.cpp
@@ -462,7 +462,8 @@ pair<expr, vector<expr>> Memory::mkInput(const char *name) {
}
expr Memory::alloc(const expr &size, unsigned align, BlockKind blockKind,
- optional<unsigned> bidopt, unsigned *bid_out) {
+ optional<unsigned> bidopt, unsigned *bid_out,
+ const expr &precond) {
// Produce a local block if blockKind is heap or stack.
bool is_local = blockKind != GLOBAL && blockKind != CONSTGLOBAL;
@@ -481,6 +482,8 @@ expr Memory::alloc(const expr &size, unsigned align, BlockKind blockKind,
size_zext = size_zext.trunc(bits_size_t - 1);
size_zext = expr::mkIf(allocated, size_zext, expr::mkUInt(0, bits_size_t-1));
+ allocated &= precond;
+
Pointer p(*this, bid, is_local);
auto short_bid = p.get_short_bid();
// TODO: If address space is not 0, the address can be 0.
@@ -519,7 +522,6 @@ expr Memory::alloc(const expr &size, unsigned align, BlockKind blockKind,
p.get_address() != 0));
state->addAxiom(p.get_alloc_type() == alloc_ty);
}
-
return expr::mkIf(allocated, p(), Pointer::mkNullPointer(*this)());
}

MODIFY
ir/memory.h
ir/memory.h
@@ -147,7 +147,8 @@ public:
// 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);
+ unsigned *bid_out = nullptr,
+ const smt::expr &precond = smt::expr(true));
void free(const smt::expr &ptr);

MODIFY
llvm_util/known_fns.cpp
llvm_util/known_fns.cpp
@@ -36,6 +36,8 @@ known_call(llvm::CallInst &i, const llvm::TargetLibraryInfo &TLI,
if (llvm::isMallocLikeFn(&i, &TLI, false)) {
bool isNonNull = i.getCalledFunction()->getName() != "malloc";
RETURN_KNOWN(make_unique<Malloc>(*ty, value_name(i), *args[0], isNonNull));
+ } else if (llvm::isCallocLikeFn(&i, &TLI, false)) {
+ RETURN_KNOWN(make_unique<Calloc>(*ty, value_name(i), *args[0], *args[1]));
} else if (llvm::isFreeCall(&i, &TLI)) {
RETURN_KNOWN(make_unique<Free>(*args[0]));
}

ADD
tests/alive-tv/memory/alloca-calloc.src.ll
+; target: 64 bits ptr addr
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define i8 @alloca_calloc() {
+ %ptr = call noalias i8* @calloc(i64 1, i64 1)
+ %i = ptrtoint i8* %ptr to i64
+ %cmp = icmp eq i64 %i, 0
+ br i1 %cmp, label %BB1, label %BB2
+BB1:
+ ret i8 0
+BB2:
+ store i8 20, i8* %ptr
+ %v = load i8, i8* %ptr
+ call void @free(i8* %ptr)
+ ret i8 %v
+}
+
+declare noalias i8* @calloc(i64, i64)
+declare void @free(i8*)

ADD
tests/alive-tv/memory/alloca-calloc.tgt.ll
+; target: 64 bits ptr addr
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define i8 @alloca_calloc() {
+ %ptr = alloca i8
+ store i8 20, i8* %ptr
+ %v = load i8, i8* %ptr
+ ret i8 %v
+}
+
+declare noalias i8* @calloc(i64, i64)
+declare void @free(i8*)

ADD
tests/alive-tv/memory/calloc-free-noub.src.ll
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define i8 @free_noub() {
+ %ptr = call noalias i8* @calloc(i64 4, i64 1)
+ call void @free(i8* %ptr)
+ ret i8 0
+}
+
+; ERROR: Value mismatch
+
+
+declare noalias i8* @calloc(i64, i64)
+declare void @free(i8*)

ADD
tests/alive-tv/memory/calloc-free-noub.tgt.ll
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define i8 @free_noub() {
+ %ptr = call noalias i8* @calloc(i64 4, i64 1)
+ call void @free(i8* %ptr)
+ ret i8 1
+}
+
+
+declare noalias i8* @calloc(i64, i64)
+declare void @free(i8*)

ADD
tests/alive-tv/memory/calloc-init.src.ll
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define i8 @calloc_init() {
+ %ptr = call noalias i8* @calloc(i64 1, i64 1)
+ %i = ptrtoint i8* %ptr to i64
+ %cmp = icmp eq i64 %i, 0
+ br i1 %cmp, label %BB1, label %BB2
+BB1:
+ ret i8 1
+BB2:
+ %v = load i8, i8* %ptr
+ call void @free(i8* %ptr)
+ ret i8 %v
+}
+
+; ERROR: Value mismatch
+
+declare noalias i8* @calloc(i64, i64)
+declare void @free(i8*)

ADD
tests/alive-tv/memory/calloc-init.tgt.ll
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define i8 @calloc_init() {
+ ret i8 2
+}
+
+declare noalias i8* @calloc(i64, i64)
+declare void @free(i8*)

ADD
tests/alive-tv/memory/calloc-nooverflow.src.ll
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define i8 @calloc_overflow() {
+ %ptr = call noalias i8* @calloc(i64 4, i64 40000000)
+ %i = ptrtoint i8* %ptr to i64
+ %cmp = icmp eq i64 %i, 0
+ br i1 %cmp, label %BB1, label %BB2
+BB1:
+ ret i8 0
+BB2:
+ ret i8 1
+}
+
+declare noalias i8* @calloc(i64, i64)
+declare void @free(i8*)

ADD
tests/alive-tv/memory/calloc-nooverflow.tgt.ll
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define i8 @calloc_overflow() {
+ ret i8 1
+}
+

ADD
tests/alive-tv/memory/calloc-overflow.src.ll
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define i8 @calloc_overflow(i64 %num) {
+ %ptr = call noalias i8* @calloc(i64 %num, i64 40000000)
+ %i = ptrtoint i8* %ptr to i64
+ %cmp = icmp eq i64 %i, 0
+ br i1 %cmp, label %BB1, label %BB2
+BB1:
+ ret i8 0
+BB2:
+ ret i8 1
+}
+
+; ERROR: Value mismatch
+
+declare noalias i8* @calloc(i64, i64)
+declare void @free(i8*)

ADD
tests/alive-tv/memory/calloc-overflow.tgt.ll
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define i8 @calloc_overflow(i64 %num) {
+ ret i8 1
+}
+

add support for calloc