further work on alloc attributes
MODIFY
ir/attrs.cpp
ir/attrs.cpp
@@ -169,6 +169,14 @@ uint64_t ParamAttrs::getDerefBytes() const {
return bytes;
}
+void ParamAttrs::merge(const ParamAttrs &other) {
+ bits |= other.bits;
+ derefBytes = max(derefBytes, other.derefBytes);
+ derefOrNullBytes = max(derefOrNullBytes, other.derefOrNullBytes);
+ blockSize = max(blockSize, other.blockSize);
+ align = max(align, other.align);
+}
+
static expr
encodePtrAttrs(State &s, const expr &ptrvalue, uint64_t derefBytes,
uint64_t derefOrNullBytes, uint64_t align, bool nonnull,

MODIFY
ir/attrs.h
ir/attrs.h
@@ -46,6 +46,8 @@ public:
uint64_t getDerefBytes() const;
+ void merge(const ParamAttrs &other);
+
friend std::ostream& operator<<(std::ostream &os, const ParamAttrs &attr);
// Encodes the semantics of attributes using UB and poison.

MODIFY
ir/globals.cpp
ir/globals.cpp
@@ -30,15 +30,12 @@ unsigned strlen_unroll_cnt;
unsigned memcmp_unroll_cnt;
bool little_endian;
bool observes_addresses;
-bool has_malloc;
-bool has_free;
bool has_alloca;
bool has_fncall;
bool has_write_fncall;
bool has_nocapture;
bool has_noread;
bool has_nowrite;
-bool has_dead_allocas;
bool has_null_block;
bool null_is_dereferenceable;
bool does_int_mem_access;

MODIFY
ir/globals.h
ir/globals.h
@@ -59,9 +59,6 @@ extern bool little_endian;
/// Whether pointer addresses are observed
extern bool observes_addresses;
-/// Whether malloc or free/delete is used in either function
-extern bool has_malloc;
-extern bool has_free;
/// Whether there is an alloca
extern bool has_alloca;
@@ -75,9 +72,6 @@ extern bool has_nocapture;
extern bool has_noread;
extern bool has_nowrite;
-/// Whether there are allocas that are initially dead (need start_lifetime)
-extern bool has_dead_allocas;
-
/// Whether there null pointers appear in the program
extern bool has_null_pointer;

MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -2020,18 +2020,17 @@ uint64_t FnCall::getMaxAccessSize() const {
}
FnCall::ByteAccessInfo FnCall::getByteAccessInfo() const {
- /* TODO: update to consider alloc function. e.g. old code:
- DEFINE_AS_EMPTYACCESS(Malloc);
+ if (attrs.has(AllocKind::Uninitialized) || attrs.has(AllocKind::Free))
+ return {};
- Calloc::ByteAccessInfo Calloc::getByteAccessInfo() const {
+ // calloc style
+ if (attrs.has(AllocKind::Zeroed)) {
auto info = ByteAccessInfo::intOnly(1);
- if (auto n = getInt(*num))
- if (auto sz = getInt(*size)) {
- info.byteSize = gcd(getAlign(), *n * *sz);
- }
+ auto [alloc, align] = getMaxAllocSize();
+ if (alloc)
+ info.byteSize = gcd(alloc, align);
return info;
}
- */
// If bytesize is zero, this call does not participate in byte encoding.
uint64_t bytesize = 0;
@@ -2051,11 +2050,11 @@ FnCall::ByteAccessInfo FnCall::getByteAccessInfo() const {
auto &retattr = getAttributes();
UPDATE(retattr);
- for (auto &arg : args) {
- if (!arg.first->getType().isPtrType())
+ for (auto &[arg, attrs] : args) {
+ if (!arg->getType().isPtrType())
continue;
- UPDATE(arg.second);
+ UPDATE(attrs);
// Pointer arguments without dereferenceable attr don't contribute to the
// byte size.
// call f(* dereferenceable(n) align m %p, * %q) is equivalent to a dummy

MODIFY
ir/memory.cpp
ir/memory.cpp
@@ -1667,7 +1667,7 @@ void Memory::startLifetime(const expr &ptr_local) {
}
void Memory::free(const expr &ptr, bool unconstrained) {
- assert(!memory_unused() && (has_free || has_dead_allocas));
+ assert(!memory_unused());
Pointer p(*this, ptr);
expr isnnull = p.isNull();

MODIFY
ir/value.cpp
ir/value.cpp
@@ -248,6 +248,11 @@ StateValue Input::toSMT(State &s) const {
return mkInput(s, getType(), 0);
}
+void Input::merge(const ParamAttrs &other) {
+ attrs.merge(other);
+ setName(attr_str(attrs) + smt_name);
+}
+
expr Input::getUndefVar(const Type &ty, unsigned child) const {
if (config::disable_undef_input || attrs.undefImpliesUB())
return {};

MODIFY
ir/value.h
ir/value.h
@@ -116,12 +116,12 @@ class Input final : public Value {
std::string getSMTName(unsigned child) const;
StateValue mkInput(State &s, const Type &ty, unsigned child) const;
public:
- Input(Type &type, std::string &&name,
- ParamAttrs &&attrs = ParamAttrs::None);
+ Input(Type &type, std::string &&name, ParamAttrs &&attrs = ParamAttrs::None);
void copySMTName(const Input &other);
void print(std::ostream &os) const override;
bool hasAttribute(ParamAttrs::Attribute a) const { return attrs.has(a); }
const ParamAttrs &getAttributes() const { return attrs; }
+ void merge(const ParamAttrs &other);
StateValue toSMT(State &s) const override;
smt::expr getUndefVar(const Type &ty, unsigned child) const;

MODIFY
llvm_util/known_fns.cpp
llvm_util/known_fns.cpp
using namespace IR;
using namespace std;
-namespace llvm_util {
-
#define RETURN_EXACT() return false
#define RETURN_APPROX() return true
-bool implict_attrs_(llvm::LibFunc libfn, FnAttrs &attrs,
+static bool implict_attrs_(llvm::LibFunc libfn, FnAttrs &attrs,
vector<ParamAttrs> &param_attrs, bool is_void,
- unsigned num_args) {
+ const vector<Value*> &args) {
auto set_param = [&](unsigned i, ParamAttrs::Attribute attr) {
if (param_attrs.size() <= i)
param_attrs.resize(i+1);
@@ -35,24 +33,30 @@ bool implict_attrs_(llvm::LibFunc libfn, FnAttrs &attrs,
auto ret_and_args_no_undef = [&]() {
if (!is_void)
attrs.set(FnAttrs::NoUndef);
- for (unsigned i = 0; i < num_args; ++i) {
+ for (unsigned i = 0, e = args.size(); i < e; ++i) {
set_param(i, ParamAttrs::NoUndef);
}
};
- auto alloc_fns = [&]() {
+ auto alloc_fns = [&](unsigned idx1, unsigned idx2 = -1u) {
ret_and_args_no_undef();
attrs.set(FnAttrs::InaccessibleMemOnly);
attrs.set(FnAttrs::NoAlias);
attrs.set(FnAttrs::NoThrow);
attrs.set(FnAttrs::WillReturn);
attrs.set(FnAttrs::AllocSize);
- attrs.allocsize_0 = 0;
+ attrs.allocsize_0 = idx1;
+ attrs.allocsize_1 = idx2;
+ attrs.derefOrNullBytes = getIntOr(*args[idx1], 0);
+ if (idx2 != -1u)
+ attrs.derefOrNullBytes *= getIntOr(*args[idx2], 0);
+ if (attrs.derefOrNullBytes > 0)
+ attrs.set(FnAttrs::DereferenceableOrNull);
};
switch (libfn) {
case llvm::LibFunc_malloc:
- alloc_fns();
+ alloc_fns(0);
attrs.set(FnAttrs::NoFree);
attrs.allocfamily = "malloc";
attrs.add(AllocKind::Alloc);
@@ -60,16 +64,15 @@ bool implict_attrs_(llvm::LibFunc libfn, FnAttrs &attrs,
RETURN_EXACT();
case llvm::LibFunc_calloc:
- alloc_fns();
+ alloc_fns(0, 1);
attrs.set(FnAttrs::NoFree);
- attrs.allocsize_1 = 1;
attrs.allocfamily = "malloc";
attrs.add(AllocKind::Alloc);
attrs.add(AllocKind::Zeroed);
RETURN_EXACT();
case llvm::LibFunc_realloc:
- alloc_fns();
+ alloc_fns(0);
attrs.allocfamily = "malloc";
attrs.add(AllocKind::Realloc);
attrs.add(AllocKind::Uninitialized);
@@ -87,7 +90,7 @@ bool implict_attrs_(llvm::LibFunc libfn, FnAttrs &attrs,
RETURN_EXACT();
case llvm::LibFunc_Znwm:
- alloc_fns();
+ alloc_fns(0);
attrs.set(FnAttrs::NoFree);
attrs.allocfamily = "_Znwm";
attrs.add(AllocKind::Alloc);
@@ -423,13 +426,16 @@ bool implict_attrs_(llvm::LibFunc libfn, FnAttrs &attrs,
}
}
+namespace llvm_util {
+
bool llvm_implict_attrs(llvm::Function &f, const llvm::TargetLibraryInfo &TLI,
- FnAttrs &attrs, vector<ParamAttrs> &param_attrs) {
+ FnAttrs &attrs, vector<ParamAttrs> &param_attrs,
+ const vector<Value*> &args) {
llvm::LibFunc libfn;
if (!TLI.getLibFunc(f, libfn) || !TLI.has(libfn))
return false;
return implict_attrs_(libfn, attrs, param_attrs,
- f.getReturnType()->isVoidTy(), f.arg_size());
+ f.getReturnType()->isVoidTy(), args);
}
#undef RETURN_EXACT
@@ -552,16 +558,18 @@ known_call(llvm::CallInst &i, const llvm::TargetLibraryInfo &TLI,
// (void)fwrite(const void *ptr, 1, 1, FILE *stream) ->
// (void)fputc(int c, FILE *stream))
if (bytes == 1 && i.use_empty() && TLI.has(llvm::LibFunc_fputc)) {
- (void)implict_attrs_(llvm::LibFunc_fputc, attrs, param_attrs, false, 2);
auto &byteTy = get_int_type(8); // FIXME
auto &i32 = get_int_type(32);
- auto call
- = make_unique<FnCall>(i32, value_name(i), "@fputc", std::move(attrs));
auto load
= make_unique<Load>(byteTy, value_name(i) + "#load", *args[0], 1);
auto load_zext
= make_unique<ConversionOp>(i32, value_name(i) + "#zext", *load,
ConversionOp::ZExt);
+
+ ENSURE(!implict_attrs_(llvm::LibFunc_fputc, attrs, param_attrs, false,
+ {load_zext.get(), args[3]}));
+ auto call
+ = make_unique<FnCall>(i32, value_name(i), "@fputc", std::move(attrs));
call->addArg(*load_zext, std::move(param_attrs[0]));
call->addArg(*args[3], std::move(param_attrs[1]));
BB.addInstr(std::move(load));
@@ -575,7 +583,7 @@ known_call(llvm::CallInst &i, const llvm::TargetLibraryInfo &TLI,
break;
}
- return { nullptr, llvm_implict_attrs(*decl, TLI, attrs, param_attrs) };
+ return { nullptr, llvm_implict_attrs(*decl, TLI, attrs, param_attrs, args) };
}
}

MODIFY
llvm_util/known_fns.h
llvm_util/known_fns.h
@@ -25,7 +25,8 @@ namespace llvm_util {
// returns true if it's a known function call
bool llvm_implict_attrs(llvm::Function &f, const llvm::TargetLibraryInfo &TLI,
IR::FnAttrs &attrs,
- std::vector<IR::ParamAttrs> &param_attrs);
+ std::vector<IR::ParamAttrs> &param_attrs,
+ const std::vector<IR::Value*> &args);
// returns true if it's a known function call
std::pair<std::unique_ptr<IR::Instr>, bool>

MODIFY
llvm_util/llvm2alive.cpp
llvm_util/llvm2alive.cpp
@@ -1489,8 +1489,6 @@ public:
auto &attrs = Fn.getFnAttrs();
vector<ParamAttrs> param_attrs;
- (void)llvm_implict_attrs(f, TLI, attrs, param_attrs);
-
llvm::AttributeList attrlist = f.getAttributes();
for (unsigned idx = 0; idx < f.arg_size(); ++idx) {
@@ -1499,8 +1497,7 @@ public:
attrlist.getAttributes(llvm::AttributeList::FirstArgIndex + idx);
auto ty = llvm_type2alive(arg.getType());
- ParamAttrs attrs = idx < param_attrs.size() ? param_attrs[idx]
- : ParamAttrs();
+ ParamAttrs attrs;
if (!ty || !handleParamAttrs(argattr, attrs, false))
return {};
auto val = make_unique<Input>(*ty, value_name(arg), std::move(attrs));
@@ -1513,7 +1510,20 @@ public:
}
Fn.addInput(std::move(val));
}
+ {
+ vector<Value*> args;
+ for (auto &in : Fn.getInputs()) {
+ args.emplace_back(const_cast<Value*>(&in));
+ }
+ vector<ParamAttrs> param_attrs;
+ (void)llvm_implict_attrs(f, TLI, attrs, param_attrs, args);
+ // merge param attrs computed above
+ unsigned idx = 0;
+ for (auto *in : args) {
+ static_cast<Input*>(in)->merge(param_attrs[idx++]);
+ }
+ }
const auto &ridx = llvm::AttributeList::ReturnIndex;
const auto &fnidx = llvm::AttributeList::FunctionIndex;
handleRetAttrs(attrlist.getAttributes(ridx), attrs);

MODIFY
tools/transform.cpp
tools/transform.cpp
@@ -579,10 +579,7 @@ static bool returns_local(const Value &v) {
if (auto call = dynamic_cast<const FnCall*>(&v))
return call->getAttributes().has(FnAttrs::NoAlias);
-// FIXME
- return dynamic_cast<const Alloc*>(&v) /*||
- dynamic_cast<const Malloc*>(&v) ||
- dynamic_cast<const Calloc*>(&v)*/;
+ return dynamic_cast<const Alloc*>(&v);
}
static Value *get_base_ptr(Value *ptr) {
@@ -822,9 +819,6 @@ static void calculateAndInitConstants(Transform &t) {
bool has_int2ptr = false;
bool has_ptr2int = false;
has_alloca = false;
- has_dead_allocas = false;
- has_malloc = false;
- has_free = false;
has_fncall = false;
has_write_fncall = false;
has_null_block = false;
@@ -918,7 +912,6 @@ static void calculateAndInitConstants(Transform &t) {
aligned_alloc_size(alloc, align));
max_access_size = max(max_access_size, mi->getMaxAccessSize());
cur_max_gep = add_saturate(cur_max_gep, mi->getMaxGEPOffset());
- has_free |= mi->canFree();
auto info = mi->getByteAccessInfo();
has_ptr_load |= info.doesPtrLoad;
@@ -931,14 +924,7 @@ static void calculateAndInitConstants(Transform &t) {
!info.doesPtrLoad && !info.doesPtrStore)
does_any_byte_access = true;
- if (auto alloc = dynamic_cast<const Alloc*>(&i)) {
- has_alloca = true;
- has_dead_allocas |= alloc->initDead();
- } else {
- // FIXME
- // has_malloc |= dynamic_cast<const Malloc*>(&i) != nullptr ||
- // dynamic_cast<const Calloc*>(&i) != nullptr;
- }
+ has_alloca |= dynamic_cast<const Alloc*>(&i) != nullptr;
} else if (isCast(ConversionOp::Int2Ptr, i) ||
isCast(ConversionOp::Ptr2Int, i)) {
@@ -983,7 +969,7 @@ static void calculateAndInitConstants(Transform &t) {
// check if null block is needed
// Global variables cannot be null pointers
- has_null_block = num_null_ptrinputs > 0 || has_null_pointer || has_malloc ||
+ has_null_block = num_null_ptrinputs > 0 || has_null_pointer ||
has_ptr_load || has_fncall || has_int2ptr;
num_nonlocals_src = num_globals_src + num_ptrinputs + num_nonlocals_inst_src +
@@ -1091,8 +1077,6 @@ static void calculateAndInitConstants(Transform &t) {
<< "\nlittle_endian: " << little_endian
<< "\nnullptr_is_used: " << has_null_pointer
<< "\nobserves_addresses: " << observes_addresses
- << "\nhas_malloc: " << has_malloc
- << "\nhas_free: " << has_free
<< "\nhas_null_block: " << has_null_block
<< "\ndoes_ptr_store: " << does_ptr_store
<< "\ndoes_mem_access: " << does_mem_access
@@ -1401,8 +1385,16 @@ static void optimize_ptrcmp(Function &f) {
if (auto *gep = dynamic_cast<const GEP*>(&v))
return gep->isInBounds();
- // noalias functions aren't required to return an inbounds ptr
- return returns_local(v) && !dynamic_cast<const FnCall*>(&v);
+ if (!returns_local(v))
+ return false;
+
+ if (auto *call = dynamic_cast<const FnCall*>(&v)) {
+ auto &attrs = call->getAttributes();
+ if (attrs.derefBytes > 0 || attrs.derefOrNullBytes > 0)
+ return true;
+ return false;
+ }
+ return true;
};
for (auto &i : f.instrs()) {

further work on alloc attributes