add support for memset_pattern
MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -2031,7 +2031,7 @@ uint64_t FnCall::getMaxAccessSize() const {
return sz;
}
-FnCall::ByteAccessInfo FnCall::getByteAccessInfo() const {
+MemInstr::ByteAccessInfo FnCall::getByteAccessInfo() const {
if (attrs.has(AllocKind::Uninitialized) || attrs.has(AllocKind::Free))
return {};
@@ -3443,7 +3443,7 @@ uint64_t Load::getMaxAccessSize() const {
return Memory::getStoreByteSize(getType());
}
-Load::ByteAccessInfo Load::getByteAccessInfo() const {
+MemInstr::ByteAccessInfo Load::getByteAccessInfo() const {
return ByteAccessInfo::get(getType(), false, align);
}
@@ -3485,7 +3485,7 @@ uint64_t Store::getMaxAccessSize() const {
return Memory::getStoreByteSize(val->getType());
}
-Store::ByteAccessInfo Store::getByteAccessInfo() const {
+MemInstr::ByteAccessInfo Store::getByteAccessInfo() const {
return ByteAccessInfo::get(val->getType(), true, align);
}
@@ -3534,7 +3534,7 @@ uint64_t Memset::getMaxAccessSize() const {
return getIntOr(*bytes, UINT64_MAX);
}
-Memset::ByteAccessInfo Memset::getByteAccessInfo() const {
+MemInstr::ByteAccessInfo Memset::getByteAccessInfo() const {
unsigned byteSize = 1;
if (auto bs = getInt(*bytes))
byteSize = gcd(align, *bs);
@@ -3588,6 +3588,61 @@ unique_ptr<Instr> Memset::dup(Function &f, const string &suffix) const {
}
+DEFINE_AS_RETZEROALIGN(MemsetPattern, getMaxAllocSize);
+DEFINE_AS_RETZERO(MemsetPattern, getMaxGEPOffset);
+
+MemsetPattern::MemsetPattern(Value &ptr, Value &pattern, Value &bytes,
+ unsigned pattern_length)
+ : MemInstr(Type::voidTy, "memset_pattern" + to_string(pattern_length)),
+ ptr(&ptr), pattern(&pattern), bytes(&bytes),
+ pattern_length(pattern_length) {}
+
+uint64_t MemsetPattern::getMaxAccessSize() const {
+ return getIntOr(*bytes, UINT64_MAX);
+}
+
+MemInstr::ByteAccessInfo MemsetPattern::getByteAccessInfo() const {
+ unsigned byteSize = 1;
+ if (auto bs = getInt(*bytes))
+ byteSize = *bs;
+ return ByteAccessInfo::intOnly(byteSize);
+}
+
+vector<Value*> MemsetPattern::operands() const {
+ return { ptr, pattern, bytes };
+}
+
+void MemsetPattern::rauw(const Value &what, Value &with) {
+ RAUW(ptr);
+ RAUW(pattern);
+ RAUW(bytes);
+}
+
+void MemsetPattern::print(ostream &os) const {
+ os << getName() << ' ' << *ptr << ", " << *pattern << ", " << *bytes;
+}
+
+StateValue MemsetPattern::toSMT(State &s) const {
+ auto &vptr = s.getAndAddPoisonUB(*ptr, false).value;
+ auto &vpattern = s.getAndAddPoisonUB(*pattern, false).value;
+ auto &vbytes = s.getAndAddPoisonUB(*bytes, true).value;
+ check_can_store(s, vptr);
+ check_can_load(s, vpattern);
+ s.getMemory().memset_pattern(vptr, vpattern, vbytes, pattern_length);
+ return {};
+}
+
+expr MemsetPattern::getTypeConstraints(const Function &f) const {
+ return ptr->getType().enforcePtrType() &&
+ pattern->getType().enforcePtrType() &&
+ bytes->getType().enforceIntType();
+}
+
+unique_ptr<Instr> MemsetPattern::dup(Function &f, const string &suffix) const {
+ return make_unique<MemsetPattern>(*ptr, *pattern, *bytes, pattern_length);
+}
+
+
DEFINE_AS_RETZEROALIGN(FillPoison, getMaxAllocSize);
DEFINE_AS_RETZERO(FillPoison, getMaxGEPOffset);
@@ -3595,7 +3650,7 @@ uint64_t FillPoison::getMaxAccessSize() const {
return getGlobalVarSize(ptr);
}
-FillPoison::ByteAccessInfo FillPoison::getByteAccessInfo() const {
+MemInstr::ByteAccessInfo FillPoison::getByteAccessInfo() const {
return ByteAccessInfo::intOnly(1);
}
@@ -3634,7 +3689,7 @@ uint64_t Memcpy::getMaxAccessSize() const {
return getIntOr(*bytes, UINT64_MAX);
}
-Memcpy::ByteAccessInfo Memcpy::getByteAccessInfo() const {
+MemInstr::ByteAccessInfo Memcpy::getByteAccessInfo() const {
#if 0
if (auto bytes = get_int(i->getBytes()))
byteSize = gcd(gcd(i->getSrcAlign(), i->getDstAlign()), *bytes);
@@ -3716,7 +3771,7 @@ uint64_t Memcmp::getMaxAccessSize() const {
return getIntOr(*num, UINT64_MAX);
}
-Memcmp::ByteAccessInfo Memcmp::getByteAccessInfo() const {
+MemInstr::ByteAccessInfo Memcmp::getByteAccessInfo() const {
auto info = ByteAccessInfo::anyType(1);
info.observesAddresses = true;
return info;

MODIFY
ir/instr.h
ir/instr.h
@@ -795,6 +795,28 @@ public:
};
+class MemsetPattern final : public MemInstr {
+ Value *ptr, *pattern, *bytes;
+ unsigned pattern_length;
+public:
+ MemsetPattern(Value &ptr, Value &pattern, Value &bytes,
+ unsigned pattern_length);
+
+ std::pair<uint64_t, uint64_t> getMaxAllocSize() const override;
+ uint64_t getMaxAccessSize() const override;
+ uint64_t getMaxGEPOffset() const override;
+ ByteAccessInfo getByteAccessInfo() const override;
+
+ 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(Function &f, const std::string &suffix) const override;
+};
+
+
class FillPoison final : public MemInstr {
Value *ptr;
public:

MODIFY
ir/memory.cpp
ir/memory.cpp
@@ -1010,22 +1010,30 @@ void Memory::store(const Pointer &ptr,
}
void Memory::storeLambda(const Pointer &ptr, const expr &offset,
- const expr &bytes, const expr &val,
+ const expr &bytes,
+ const vector<pair<unsigned, expr>> &data,
const set<expr> &undef, uint64_t align) {
assert(!state->isInitializationPhase());
// offset in [ptr, ptr+sz)
auto offset_cond = offset.uge(ptr.getShortOffset()) &&
offset.ult((ptr + bytes).getShortOffset());
- bool val_no_offset = !val.vars().count(offset);
- auto stored_ty = data_type({{ 0, val }}, false);
+ bool val_no_offset = data.size() == 1 && !data[0].second.vars().count(offset);
+ auto stored_ty = data_type(data, false);
+
+ expr val = data.back().second;
+ expr mod = expr::mkUInt(data.size(), offset);
+ for (auto I = next(data.rbegin()), E = data.rend(); I != E; ++I) {
+ val = expr::mkIf(offset.urem(mod) == I->first, I->second, val);
+ }
auto fn = [&](MemBlock &blk, unsigned bid, bool local, expr &&cond) {
// optimization: full rewrite
if (bytes.eq(Pointer(*this, bid, local).blockSize())) {
- blk.val = val_no_offset
+ blk.val = val_no_offset && data.size() == 1
? expr::mkIf(cond, expr::mkConstArray(offset, val), blk.val)
: expr::mkLambda(offset, expr::mkIf(cond, val, blk.val.load(offset)));
+
if (cond.isTrue()) {
blk.undef.clear();
blk.type = stored_ty;
@@ -1857,7 +1865,39 @@ void Memory::memset(const expr &p, const StateValue &val, const expr &bytesize,
} else {
expr offset
= expr::mkFreshVar("#off", expr::mkUInt(0, Pointer::bitsShortOffset()));
- storeLambda(ptr, offset, bytesize, raw_byte, undef_vars, align);
+ storeLambda(ptr, offset, bytesize, {{0, raw_byte}}, undef_vars, align);
+ }
+}
+
+void Memory::memset_pattern(const expr &ptr0, const expr &pattern0,
+ const expr &bytesize, unsigned pattern_length) {
+ assert(!memory_unused());
+ unsigned bytesz = bits_byte / 8;
+ Pointer ptr(*this, ptr0);
+ state->addUB(ptr.isDereferenceable(bytesize, 1, true));
+
+ Pointer pattern(*this, pattern0);
+ expr length = bytesize.umin(expr::mkUInt(pattern_length, bytesize));
+ state->addUB(pattern.isDereferenceable(length, 1, false));
+
+ set<expr> undef_vars;
+ auto bytes
+ = load(pattern, pattern_length, undef_vars, 1, little_endian, DATA_ANY);
+
+ vector<pair<unsigned, expr>> to_store;
+ uint64_t n;
+ if (bytesize.isUInt(n) && (n / bytesz) <= 4) {
+ for (unsigned i = 0; i < n; i += bytesz) {
+ to_store.emplace_back(i, std::move(bytes[i/bytesz])());
+ }
+ store(ptr, to_store, undef_vars, 1);
+ } else {
+ for (unsigned i = 0; i < pattern_length; ++i) {
+ to_store.emplace_back(i * bytesz, std::move(bytes[i])());
+ }
+ expr offset
+ = expr::mkFreshVar("#off", expr::mkUInt(0, Pointer::bitsShortOffset()));
+ storeLambda(ptr, offset, bytesize, to_store, undef_vars, 1);
}
}
@@ -1891,7 +1931,8 @@ void Memory::memcpy(const expr &d, const expr &s, const expr &bytesize,
Pointer ptr_src = src + (offset - dst.getShortOffset());
set<expr> undef;
auto val = raw_load(ptr_src, undef);
- storeLambda(dst, offset, bytesize, std::move(val)(), undef, align_dst);
+ storeLambda(dst, offset, bytesize, {{0, std::move(val)()}}, undef,
+ align_dst);
}
}

MODIFY
ir/memory.h
ir/memory.h
@@ -193,7 +193,8 @@ class Memory {
std::vector<std::pair<unsigned, smt::expr>> &data);
void storeLambda(const Pointer &ptr, const smt::expr &offset,
- const smt::expr &bytes, const smt::expr &val,
+ const smt::expr &bytes,
+ const std::vector<std::pair<unsigned, smt::expr>> &data,
const std::set<smt::expr> &undef, uint64_t align);
smt::expr blockValRefined(const Memory &other, unsigned bid, bool local,
@@ -310,6 +311,10 @@ public:
void memset(const smt::expr &ptr, const StateValue &val,
const smt::expr &bytesize, uint64_t align,
const std::set<smt::expr> &undef_vars, bool deref_check = true);
+
+ void memset_pattern(const smt::expr &ptr, const smt::expr &pattern,
+ const smt::expr &bytesize, unsigned pattern_length);
+
void memcpy(const smt::expr &dst, const smt::expr &src,
const smt::expr &bytesize, uint64_t align_dst, uint64_t align_src,
bool move);

MODIFY
llvm_util/known_fns.cpp
llvm_util/known_fns.cpp
@@ -528,6 +528,14 @@ known_call(llvm::CallInst &i, const llvm::TargetLibraryInfo &TLI,
BB.addInstr(make_unique<Memset>(*args[0], *args[1], *args[2], 1));
RETURN_VAL(make_unique<UnaryOp>(*ty, value_name(i), *args[0],
UnaryOp::Copy));
+
+ // void memset_pattern4(void *ptr, void *pattern, size_t bytes)
+ case llvm::LibFunc_memset_pattern4:
+ RETURN_VAL(make_unique<MemsetPattern>(*args[0], *args[1], *args[2], 4));
+ case llvm::LibFunc_memset_pattern8:
+ RETURN_VAL(make_unique<MemsetPattern>(*args[0], *args[1], *args[2], 8));
+ case llvm::LibFunc_memset_pattern16:
+ RETURN_VAL(make_unique<MemsetPattern>(*args[0], *args[1], *args[2], 16));
case llvm::LibFunc_strlen:
RETURN_VAL(make_unique<Strlen>(*ty, value_name(i), *args[0]));
case llvm::LibFunc_memcmp:

add support for memset_pattern