add realloc
MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -1800,39 +1800,77 @@ unique_ptr<Instr> Alloc::dup(const string &suffix) const {
vector<Value*> Malloc::operands() const {
+ if (!ptr)
return { size };
+ else
+ return { ptr, size };
}
void Malloc::rauw(const Value &what, Value &with) {
RAUW(size);
+ if (ptr)
+ RAUW(ptr);
}
void Malloc::print(std::ostream &os) const {
+ if (!ptr)
os << getName() << " = malloc " << *size;
+ else
+ os << getName() << " = realloc " << *ptr << ", " << *size;
}
StateValue Malloc::toSMT(State &s) const {
- auto &[sz, np] = s.getAndAddUndefs(*size);
+ auto &[sz, np_size] = s.getAndAddUndefs(*size);
// TODO: malloc's alignment is implementation defined.
expr nonnull = expr::mkBoolVar("malloc_never_fails");
- auto [p, allocated] = s.getMemory().alloc(sz, 8, Memory::HEAP, np, nonnull);
+ auto [p_new, allocated] = s.getMemory().alloc(sz, 8, Memory::HEAP, np_size,
+ nonnull);
+ if (!ptr) {
if (isNonNull) {
- // TODO: In C++ we need to throw an exception if the allocation fails, but
- // exception hasn't been modeled yet
+ // TODO: In C++ we need to throw an exception if the allocation fails,
+ // but exception hasn't been modeled yet
s.addPre(move(allocated));
}
- return { move(p), expr(np) };
+ return { move(p_new), expr(np_size) };
+ } else {
+ auto &[p, np_ptr] = s.getAndAddUndefs(*ptr);
+ s.addUB(np_ptr);
+
+ // If sz > p_sz, it is filled it with poison in malloc (local_block_val is
+ // initialized with poison).
+
+ Pointer ptr(s.getMemory(), p);
+ expr p_sz = ptr.block_size();
+ expr sz_zext = sz.zextOrTrunc(p_sz.bits());
+
+ expr memcpy_size = expr::mkIf(allocated,
+ expr::mkIf(p_sz.ule(sz_zext), p_sz, sz_zext),
+ expr::mkUInt(0, p_sz.bits()));
+
+ // If memcpy's size is zero, then both ptrs can be NULL.
+ s.getMemory().memcpy(p_new, p, memcpy_size, 1, 1, false);
+
+ // 1) realloc(ptr, 0) always free the ptr.
+ // 2) If allocation failed, we should not free previous ptr.
+ expr nullp = Pointer::mkNullPointer(s.getMemory())();
+ s.getMemory().free(expr::mkIf((sz == 0) || allocated, p, nullp), true);
+
+ return { move(p_new), expr(np_size) };
+ }
}
expr Malloc::getTypeConstraints(const Function &f) const {
return Value::getTypeConstraints() &&
getType().enforcePtrType() &&
- size->getType().enforceIntType();
+ size->getType().enforceIntType() &&
+ (ptr ? ptr->getType().enforcePtrType() : true);
}
unique_ptr<Instr> Malloc::dup(const string &suffix) const {
+ if (ptr)
+ return make_unique<Malloc>(getType(), getName() + suffix, *ptr, *size);
return make_unique<Malloc>(getType(), getName() + suffix, *size, isNonNull);
}

MODIFY
ir/instr.h
ir/instr.h
@@ -399,15 +399,20 @@ public:
class Malloc final : public Instr {
- Value *size;
+ Value *ptr = nullptr, *size;
// Is this malloc (or equivalent operation, like new()) never returning
// null?
- bool isNonNull;
+ bool isNonNull = false;
+
public:
Malloc(Type &type, std::string &&name, Value &size, bool isNonNull)
: Instr(type, std::move(name)), size(&size), isNonNull(isNonNull) {}
+ Malloc(Type &type, std::string &&name, Value &ptr, Value &size)
+ : Instr(type, std::move(name)), ptr(&ptr), size(&size) {}
+
Value& getSize() const { return *size; }
+ bool isRealloc() const { return ptr != nullptr; }
std::vector<Value*> operands() const override;
void rauw(const Value &what, Value &with) override;
void print(std::ostream &os) const override;

MODIFY
llvm_util/known_fns.cpp
llvm_util/known_fns.cpp
@@ -41,6 +41,8 @@ known_call(llvm::CallInst &i, const llvm::TargetLibraryInfo &TLI,
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::isReallocLikeFn(&i, &TLI, false)) {
+ RETURN_KNOWN(make_unique<Malloc>(*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/realloc-fail.src.ll
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define i8 @realloc-fail() {
+ %ptr = call noalias i8* @malloc(i64 4)
+ %cmp = icmp eq i8* %ptr, null
+ br i1 %cmp, label %BB1, label %BB2
+BB1:
+ ret i8 -1
+BB2:
+ store i8 5, i8* %ptr
+ %ptr2 = call noalias i8* @realloc(i8* %ptr, i64 100)
+ %cmp2 = icmp eq i8* %ptr2, null
+ br i1 %cmp2, label %BB3, label %BB4
+BB3:
+ %a = load i8, i8* %ptr
+ store i8 1, i8* %ptr
+ %b = load i8, i8* %ptr
+ %s = add i8 %a, %b
+ ret i8 %s
+BB4:
+ %a2 = load i8, i8* %ptr2
+ store i8 2, i8* %ptr2
+ %b2 = load i8, i8* %ptr2
+ %s2 = add i8 %a2, %b2
+ ret i8 %s2
+}
+
+declare noalias i8* @malloc(i64)
+declare noalias i8* @realloc(i8*, i64)
+
+; ERROR: Value mismatch

ADD
tests/alive-tv/memory/realloc-fail.tgt.ll
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define i8 @realloc-fail() {
+ %ptr = call noalias i8* @malloc(i64 4)
+ %cmp = icmp eq i8* %ptr, null
+ br i1 %cmp, label %BB1, label %BB2
+BB1:
+ ret i8 -1
+BB2:
+ store i8 5, i8* %ptr
+ %ptr2 = call noalias i8* @realloc(i8* %ptr, i64 100)
+ ret i8 6
+}
+
+declare noalias i8* @malloc(i64)
+declare noalias i8* @realloc(i8*, i64)

ADD
tests/alive-tv/memory/realloc-null.src.ll
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define i8 @realloc-null() {
+ %ptr = call noalias i8* @realloc(i8* null, i64 3)
+ store i8 5, i8* %ptr
+ %v = load i8, i8* %ptr
+ ret i8 %v
+}
+
+declare noalias i8* @realloc(i8*, i64)

ADD
tests/alive-tv/memory/realloc-null.tgt.ll
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define i8 @realloc-null() {
+ %ptr = call noalias i8* @malloc(i64 3)
+ store i8 5, i8* %ptr
+ %v = load i8, i8* %ptr
+ ret i8 %v
+}
+
+declare noalias i8* @malloc(i64)

ADD
tests/alive-tv/memory/realloc-zero.src.ll
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define i64 @realloc-check() {
+ %ptr = call noalias i8* @malloc(i64 4)
+ %ptr2 = call noalias i8* @realloc(i8* %ptr, i64 0)
+ %v = load i8, i8* %ptr
+ ret i64 0
+}
+
+declare noalias i8* @malloc(i64)
+declare noalias i8* @realloc(i8*, i64)

ADD
tests/alive-tv/memory/realloc-zero.tgt.ll
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define i64 @realloc-check() {
+ ret i64 -1
+}
+
+declare noalias i8* @malloc(i64)
+declare noalias i8* @realloc(i8*, i64)

ADD
tests/alive-tv/memory/realloc.src.ll
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define i8 @realloc-check() {
+ %ptr = call noalias i8* @malloc(i64 4)
+ %cmp = icmp eq i8* %ptr, null
+ br i1 %cmp, label %BB1, label %BB2
+BB1:
+ ret i8 -1
+BB2:
+ store i8 5, i8* %ptr
+ %ptr2 = call noalias i8* @realloc(i8* %ptr, i64 1)
+ %cmp2 = icmp eq i8* %ptr2, null
+ br i1 %cmp2, label %BB3, label %BB4
+BB3:
+ %a = load i8, i8* %ptr
+ store i8 1, i8* %ptr
+ %b = load i8, i8* %ptr
+ %s = add i8 %a, %b
+ ret i8 %s
+BB4:
+ %a2 = load i8, i8* %ptr2
+ store i8 2, i8* %ptr2
+ %b2 = load i8, i8* %ptr2
+ %s2 = add i8 %a2, %b2
+ ret i8 %s2
+}
+
+declare noalias i8* @malloc(i64)
+declare noalias i8* @realloc(i8*, i64)

ADD
tests/alive-tv/memory/realloc.tgt.ll
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define i8 @realloc-check() {
+ %ptr = call noalias i8* @malloc(i64 4)
+ %cmp = icmp eq i8* %ptr, null
+ br i1 %cmp, label %BB1, label %BB2
+BB1:
+ ret i8 -1
+BB2:
+ store i8 5, i8* %ptr
+ %ptr2 = call noalias i8* @realloc(i8* %ptr, i64 1)
+ %cmp2 = icmp eq i8* %ptr2, null
+ br i1 %cmp2, label %BB3, label %BB4
+BB3:
+ ret i8 6
+BB4:
+ ret i8 7
+}
+
+declare noalias i8* @malloc(i64)
+declare noalias i8* @realloc(i8*, i64)

MODIFY
tools/transform.cpp
tools/transform.cpp
@@ -687,7 +687,11 @@ static void calculateAndInitConstants(Transform &t) {
if (auto alloc = dynamic_cast<const Alloc*>(&I))
has_dead_allocas |= alloc->initDead();
- has_malloc |= dynamic_cast<const Malloc*>(&I) != nullptr;
+ if (auto alloc = dynamic_cast<const Malloc*>(&I)) {
+ has_malloc |= true;
+ has_free |= alloc->isRealloc();
+ }
+
has_malloc |= dynamic_cast<const Calloc*>(&I) != nullptr;
has_free |= dynamic_cast<const Free*>(&I) != nullptr;
has_load |= dynamic_cast<const Load*>(&I) != nullptr;

add realloc (#255)