llvm2alive: add support for the dereferenceable attribute
MODIFY
ir/attrs.cpp
ir/attrs.cpp
@@ -17,6 +17,8 @@ ostream& operator<<(ostream &os, const ParamAttrs &attr) {
os << "readonly ";
if (attr.has(ParamAttrs::ReadNone))
os << "readnone ";
+ if (attr.has(ParamAttrs::Dereferenceable))
+ os << "dereferenceable(" << attr.derefBytes << ") ";
return os;
}

MODIFY
ir/attrs.h
ir/attrs.h
@@ -9,15 +9,18 @@ namespace IR {
class ParamAttrs final {
unsigned bits;
+ uint64_t derefBytes;
public:
enum Attribute { None = 0, NonNull = 1<<0, ByVal = 1<<1, NoCapture = 1<<2,
- ReadOnly = 1<<3, ReadNone = 1<<4 };
+ ReadOnly = 1<<3, ReadNone = 1<<4, Dereferenceable = 1<<5 };
ParamAttrs(unsigned bits = None) : bits(bits) {}
bool has(Attribute a) const { return (bits & a) != 0; }
void set(Attribute a) { bits |= (unsigned)a; }
+ uint64_t getDerefBytes() const { return derefBytes; }
+ void setDerefBytes(uint64_t bytes) { derefBytes = bytes; }
friend std::ostream& operator<<(std::ostream &os, const ParamAttrs &attr);
};

MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -1334,6 +1334,11 @@ static void unpack_inputs(State&s, Type &ty, const ParamAttrs &argflag,
if (ty.isPtrType()) {
Pointer p(s.getMemory(), value.value);
p.stripAttrs();
+ if (argflag.has(ParamAttrs::Dereferenceable)) {
+ s.addUB(value.non_poison);
+ s.addUB(
+ p.isDereferenceable(argflag.getDerefBytes(), bits_byte / 8, false));
+ }
ptr_inputs.emplace_back(StateValue(p.release(), expr(value.non_poison)),
argflag.has(ParamAttrs::ByVal));
} else {

MODIFY
ir/state.h
ir/state.h
@@ -130,6 +130,7 @@ public:
const BasicBlock &dst_false);
void addReturn(const StateValue &val);
+ void addAxiom(smt::AndExpr &&ands) { axioms.add(std::move(ands)); }
void addAxiom(smt::expr &&axiom) { axioms.add(std::move(axiom)); }
void addPre(smt::expr &&cond, bool forApprox = false)
{ (forApprox ? preconditionForApprox : precondition).add(std::move(cond)); }

MODIFY
ir/value.cpp
ir/value.cpp
@@ -190,7 +190,8 @@ StateValue Input::toSMT(State &s) const {
val = getType().mkInput(s, smt_name.c_str(), attrs);
}
- if (!config::disable_undef_input) {
+ const bool has_deref = hasAttribute(ParamAttrs::Dereferenceable);
+ if (!config::disable_undef_input && !has_deref) {
auto [undef, vars] = getType().mkUndefInput(s, attrs);
for (auto &v : vars) {
s.addUndefVar(move(v));
@@ -198,11 +199,17 @@ StateValue Input::toSMT(State &s) const {
val = expr::mkIf(type.extract(0, 0) == 0, val, undef);
}
+ if (has_deref) {
+ Pointer p(s.getMemory(), val);
+ s.addAxiom(
+ p.isDereferenceable(attrs.getDerefBytes(), bits_byte / 8, false));
+ }
+
expr poison = getType().getDummyValue(false).non_poison;
expr non_poison = getType().getDummyValue(true).non_poison;
return { move(val),
- config::disable_poison_input
+ config::disable_poison_input || has_deref
? move(non_poison)
: expr::mkIf(type.extract(1, 1) == 0, non_poison, poison) };
}

MODIFY
ir/value.h
ir/value.h
@@ -117,6 +117,7 @@ public:
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; }
StateValue toSMT(State &s) const override;
smt::expr getTyVar() const;
};

MODIFY
llvm_util/llvm2alive.cpp
llvm_util/llvm2alive.cpp
@@ -272,14 +272,33 @@ public:
make_unique<FnCall>(*ty, value_name(i), move(fn_name), move(attrs),
!known);
unique_ptr<Instr> ret_val;
- auto argI = fn->arg_begin(), argE = fn->arg_end();
- for (auto &arg : args) {
+
+ for (uint64_t argidx = 0, nargs = i.arg_size(); argidx < nargs; ++argidx) {
+ auto *arg = args[argidx];
ParamAttrs attr;
- if (argI != argE) {
- // Check whether arg itr finished early because it was var arg
- if (argI->hasByValAttr())
+ // TODO: Once attributes at a call site are fully supported, we should
+ // call handleAttributes().
+
+ if (i.paramHasAttr(argidx, llvm::Attribute::Dereferenceable)) {
+ attr.set(ParamAttrs::Dereferenceable);
+
+ uint64_t derefb = 0;
+ // dereferenceable at caller
+ if (i.getAttributes()
+ .hasParamAttr(argidx, llvm::Attribute::Dereferenceable))
+ derefb = i.getParamAttr(argidx, llvm::Attribute::Dereferenceable)
+ .getDereferenceableBytes();
+ if (argidx < i.getCalledFunction()->arg_size())
+ derefb = max(derefb,
+ i.getCalledFunction()->getParamDereferenceableBytes(argidx));
+ assert(derefb);
+ attr.setDerefBytes(derefb);
+ }
+
+ if (i.paramHasAttr(argidx, llvm::Attribute::ByVal))
attr.set(ParamAttrs::ByVal);
- else if (argI->hasReturnedAttr()) {
+
+ if (i.paramHasAttr(argidx, llvm::Attribute::Returned)) {
auto call2
= make_unique<FnCall>(Type::voidTy, "", string(call->getFnName()),
FnAttrs(call->getAttributes()), !known);
@@ -291,15 +310,13 @@ public:
// fn may have different type than argument. LLVM assumes there's
// an implicit bitcast
assert(!ret_val);
- if (argI->getType() == i.getType())
+ if (i.getArgOperand(argidx)->getType() == i.getType())
ret_val = make_unique<UnaryOp>(*ty, value_name(i), *arg,
UnaryOp::Copy);
else
ret_val = make_unique<ConversionOp>(*ty, value_name(i), *arg,
ConversionOp::BitCast);
}
- ++argI;
- }
call->addArg(*arg, move(attr));
}
if (ret_val) {
@@ -850,6 +867,11 @@ public:
attrs.set(ParamAttrs::ReadNone);
continue;
+ case llvm::Attribute::Dereferenceable:
+ attrs.set(ParamAttrs::Dereferenceable);
+ attrs.setDerefBytes(aset.getDereferenceableBytes());
+ continue;
+
default:
*out << "ERROR: Unsupported attribute: " << attr.getAsString() << '\n';
return nullopt;

ADD
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]
+ 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
+ ret i32 %val
+}
+
+declare void @f(i32* dereferenceable(2) %ptr)

ADD
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]
+ 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
+ ret i32 %val
+}
+
+declare void @f(i32* %ptr)

ADD
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]
+ 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)

ADD
tests/alive-tv/attrs/dereferenceable-fail.srctgt.ll
+define i32 @src(i1 %c, i32* dereferenceable(3) %p) {
+ENTRY:
+ 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* dereferenceable(3) %p) {
+ %v1 = load i32, i32* %p
+ %val = select i1 %c, i32 %v1, i32 0
+ ret i32 %val
+}
+
+; ERROR: Source is more defined than target

ADD
tests/alive-tv/attrs/dereferenceable.srctgt.ll
+define i32 @src(i1 %c, i32* dereferenceable(4) %p) {
+ENTRY:
+ 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* dereferenceable(4) %p) {
+ %v1 = load i32, i32* %p
+ %val = select i1 %c, i32 %v1, i32 0
+ ret i32 %val
+}

ADD
tests/alive-tv/opt-memory/dereferenceable.srctgt.ll
+; TEST-ARGS: -dbg
+
+define i32 @src(i32* dereferenceable(2) %p) {
+ %v1 = load i32, i32* %p
+ ret i32 %v1
+}
+
+define i32 @tgt(i32* dereferenceable(2) %p) {
+ %v1 = load i32, i32* %p
+ ret i32 %v1
+}
+
+
+; CHECK: min_access_size: 2

MODIFY
tools/transform.cpp
tools/transform.cpp
@@ -516,6 +516,15 @@ static void calculateAndInitConstants(Transform &t) {
unsigned &cur_num_locals = fn == &t.src ? num_locals_src : num_locals_tgt;
uint64_t &cur_max_gep = fn == &t.src ? max_gep_src : max_gep_tgt;
+ for (auto &v : fn->getInputs()) {
+ auto *i = dynamic_cast<const Input *>(&v);
+ if (i && i->hasAttribute(ParamAttrs::Dereferenceable)) {
+ does_mem_access = true;
+ min_access_size = gcd(min_access_size,
+ i->getAttributes().getDerefBytes());
+ }
+ }
+
for (auto BB : fn->getBBs()) {
for (auto &i : BB->instrs()) {
if (returns_local(i))

llvm2alive: add support for the dereferenceable attribute (#377)