Add undef analysis
MODIFY
ir/attrs.cpp
ir/attrs.cpp
// Distributed under the MIT license that can be found in the LICENSE file.
#include "ir/attrs.h"
+#include <cassert>
using namespace std;
@@ -49,4 +50,16 @@ ostream& operator<<(ostream &os, const FnAttrs &attr) {
return os;
}
+bool ParamAttrs::undefImpliesUB() const {
+ bool ub = has(NoUndef);
+ assert(!ub || poisonImpliesUB());
+ return ub;
+}
+
+bool FnAttrs::undefImpliesUB() const {
+ bool ub = has(NoUndef);
+ assert(!ub || poisonImpliesUB());
+ return ub;
+}
+
}

MODIFY
ir/attrs.h
ir/attrs.h
@@ -29,8 +29,7 @@ public:
{ return has(NonNull) || has(Dereferenceable) || has(NoUndef) || has(ByVal); }
// Returns true if it is UB for the argument to be (partially) undef.
- bool undefImpliesUB() const
- { return has(NoUndef); }
+ bool undefImpliesUB() const;
friend std::ostream& operator<<(std::ostream &os, const ParamAttrs &attr);
};
@@ -58,8 +57,7 @@ public:
{ return has(NonNull) || has(Dereferenceable) || has(NoUndef); }
// Returns true if returning (partially) undef is UB
- bool undefImpliesUB() const
- { return has(NoUndef); }
+ bool undefImpliesUB() const;
friend std::ostream& operator<<(std::ostream &os, const FnAttrs &attr);
};

MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -1587,79 +1587,6 @@ void FnCall::print(ostream &os) const {
os << "\t; WARNING: unknown known function";
}
-static expr eq_except_padding(const Type &ty, const expr &e1, const expr &e2) {
- const auto *aty = ty.getAsAggregateType();
- if (!aty)
- return e1 == e2;
-
- StateValue sv1{expr(e1), expr()};
- StateValue sv2{expr(e2), expr()};
- expr result = true;
-
- for (unsigned i = 0; i < aty->numElementsConst(); ++i) {
- if (aty->isPadding(i))
- continue;
-
- result &= eq_except_padding(aty->getChild(i), aty->extract(sv1, i).value,
- aty->extract(sv2, i).value);
- }
- return result;
-}
-
-static bool isUndefMask(const expr &e, const expr &var) {
- auto ty_name = e.fn_name();
- auto var_name = var.fn_name();
- return string_view(ty_name).substr(0, 8) == "isundef_" &&
- string_view(ty_name).substr(8, var_name.size()) == var_name;
-}
-
-static pair<expr,expr> // <extracted value, not_undef>
-strip_undef(State &s, const Value &val, const expr &e) {
- if (s.isUndef(e))
- return { expr::mkUInt(0, e), false };
-
- auto is_undef_cond = [](const expr &e, const expr &var) {
- expr lhs, rhs;
- // (= #b0 isundef_%var)
- if (e.isEq(lhs, rhs)) {
- return (lhs.isZero() && isUndefMask(rhs, var)) ||
- (rhs.isZero() && isUndefMask(lhs, var));
- }
- return false;
- };
-
- auto is_if_undef = [&](const expr &e, expr &val, expr &not_undef) {
- expr undef;
- // (ite (= #b0 isundef_%var) %var undef)
- return e.isIf(not_undef, val, undef) && s.isUndef(undef) &&
- is_undef_cond(not_undef, val);
- };
-
- expr c, a, b, lhs, rhs;
-
- // two variants
- // 1) boolean
- if (is_if_undef(e, a, b))
- return { move(a), move(b) };
-
- // (ite (= const (ite (= #b0 isundef_%var) %var undef)) #b1 #b0)
- // TODO: generalize to other undef-generating functions other than ==
- if (e.isIf(c, a, b) && a.isConst() && b.isConst()) {
- if (c.isEq(lhs, rhs)) {
- expr val, not_undef;
- if (is_if_undef(lhs, val, not_undef))
- return { expr::mkIf(val == rhs, a, b), move(not_undef) };
- if (is_if_undef(rhs, val, not_undef))
- return { expr::mkIf(lhs == val, a, b), move(not_undef) };
- }
- }
-
- // 2) (or (and |isundef_%var| undef) (and %var (not |isundef_%var|)))
- // TODO
-
- return { e, eq_except_padding(val.getType(), e, s[val].value) };
-}
-
static void unpack_inputs(State &s, Value &argv, Type &ty,
const ParamAttrs &argflag,
StateValue value, vector<StateValue> &inputs,
@@ -1670,12 +1597,6 @@ static void unpack_inputs(State &s, Value &argv, Type &ty,
inputs, ptr_inputs);
}
} else {
- if (argflag.undefImpliesUB()) {
- auto [val, not_undef] = strip_undef(s, argv, value.value);
- value.value = move(val);
- s.addUB(move(not_undef));
- }
-
if (ty.isPtrType()) {
Pointer p(s.getMemory(), move(value.value));
p.stripAttrs();
@@ -1755,7 +1676,7 @@ StateValue FnCall::toSMT(State &s) const {
for (auto &[arg, flags] : args) {
StateValue sv;
if (flags.poisonImpliesUB())
- sv = s.getAndAddPoisonUB(*arg);
+ sv = s.getAndAddPoisonUB(*arg, flags.undefImpliesUB());
else
sv = s[*arg];
@@ -2184,10 +2105,8 @@ void Branch::print(ostream &os) const {
StateValue Branch::toSMT(State &s) const {
if (cond) {
- auto &c = s.getAndAddPoisonUB(*cond);
- auto [cond_val, not_undef] = strip_undef(s, *cond, c.value);
- s.addUB(move(not_undef));
- s.addCondJump(cond_val, dst_true, *dst_false);
+ auto &c = s.getAndAddPoisonUB(*cond, true);
+ s.addCondJump(c.value, dst_true, *dst_false);
} else {
s.addJump(dst_true);
}
@@ -2237,16 +2156,13 @@ void Switch::print(ostream &os) const {
}
StateValue Switch::toSMT(State &s) const {
- auto &val = s.getAndAddPoisonUB(*value);
+ auto &val = s.getAndAddPoisonUB(*value, true);
expr default_cond(true);
- auto [cond_val, not_undef] = strip_undef(s, *value, val.value);
- s.addUB(move(not_undef));
-
for (auto &[value_cond, bb] : targets) {
auto &target = s[*value_cond];
assert(target.non_poison.isTrue());
- expr cmp = cond_val == target.value;
+ expr cmp = val.value == target.value;
default_cond &= !cmp;
s.addJump(move(cmp), bb);
}
@@ -2309,7 +2225,7 @@ StateValue Return::toSMT(State &s) const {
auto &attrs = s.getFn().getFnAttrs();
if (attrs.poisonImpliesUB())
- retval = s.getAndAddPoisonUB(*val);
+ retval = s.getAndAddPoisonUB(*val, attrs.undefImpliesUB());
else
retval = s[*val];
@@ -2318,13 +2234,6 @@ StateValue Return::toSMT(State &s) const {
bool isDeref = attrs.has(FnAttrs::Dereferenceable);
bool isNonNull = attrs.has(FnAttrs::NonNull);
-
- if (attrs.undefImpliesUB()) {
- auto [value, not_undef] = strip_undef(s, *val, retval.value);
- retval.value = move(value);
- s.addUB(move(not_undef));
- }
-
if (isDeref || isNonNull) {
assert(val->getType().isPtrType());
Pointer p(s.getMemory(), retval.value);
@@ -2860,7 +2769,10 @@ void Load::print(std::ostream &os) const {
}
StateValue Load::toSMT(State &s) const {
- auto &p = s.getAndAddPoisonUB(*ptr).value;
+ // NOTE: We neeed clarification whether loading a partially undefined pointer
+ // is UB. Memory sanitizer has an option (detecting a partially undef pointer)
+ // for this, so worth discussing it.
+ auto &p = s.getAndAddPoisonUB(*ptr, true).value;
auto [sv, ub] = s.getMemory().load(p, getType(), align);
s.addUB(move(ub));
return sv;
@@ -2902,7 +2814,10 @@ void Store::print(std::ostream &os) const {
}
StateValue Store::toSMT(State &s) const {
- auto &p = s.getAndAddPoisonUB(*ptr).value;
+ // NOTE: We neeed clarification whether store to a partially undefined pointer
+ // is UB. Memory sanitizer has an option (detecting a partially undef pointer)
+ // for this, so worth discussing it.
+ auto &p = s.getAndAddPoisonUB(*ptr, true).value;
auto &v = s[*val];
s.getMemory().store(p, v, val->getType(), align, s.getUndefVars());
return {};
@@ -3006,7 +2921,7 @@ void Memcpy::print(ostream &os) const {
StateValue Memcpy::toSMT(State &s) const {
auto &[vdst, np_dst] = s[*dst];
auto &[vsrc, np_src] = s[*src];
- auto &vbytes = s.getAndAddPoisonUB(*bytes).value;
+ auto &vbytes = s.getAndAddPoisonUB(*bytes, true).value;
s.addUB((vbytes != 0).implies(np_dst && np_src));
if (vbytes.bits() > bits_size_t)

MODIFY
ir/state.cpp
ir/state.cpp
@@ -32,16 +32,22 @@ expr State::DomainPreds::operator()() const {
return path() && *UB();
}
-void State::ValueAnalysis::intersect(const State::ValueAnalysis &other) {
- set<const Value*> results;
- set_intersection(non_poison_vals.begin(), non_poison_vals.end(),
- other.non_poison_vals.begin(), other.non_poison_vals.end(),
+template<class T>
+static T intersect_set(const T &a, const T &b) {
+ T results;
+ set_intersection(a.begin(), a.end(), b.begin(), b.end(),
inserter(results, results.begin()));
- non_poison_vals = move(results);
+ return results;
+}
+
+void State::ValueAnalysis::intersect(const State::ValueAnalysis &other) {
+ non_poison_vals = intersect_set(non_poison_vals, other.non_poison_vals);
+ non_undef_vals = intersect_set(non_undef_vals, other.non_undef_vals);
}
void State::ValueAnalysis::reset() {
non_poison_vals.clear();
+ non_undef_vals.clear();
}
@@ -67,24 +73,113 @@ const StateValue& State::exec(const Value &v) {
return get<1>(values.back()).first;
}
+static expr eq_except_padding(const Type &ty, const expr &e1, const expr &e2) {
+ const auto *aty = ty.getAsAggregateType();
+ if (!aty)
+ return e1 == e2;
+
+ StateValue sv1{expr(e1), expr()};
+ StateValue sv2{expr(e2), expr()};
+ expr result = true;
+
+ for (unsigned i = 0; i < aty->numElementsConst(); ++i) {
+ if (aty->isPadding(i))
+ continue;
+
+ result &= eq_except_padding(aty->getChild(i), aty->extract(sv1, i).value,
+ aty->extract(sv2, i).value);
+ }
+ return result;
+}
+
+static expr strip_undef_and_add_ub(State &s, const Value &val, const expr &e) {
+ if (s.isUndef(e, &val)) {
+ s.addUB(expr(false));
+ return expr::mkUInt(0, e);
+ }
+
+ auto is_undef_cond = [](const expr &e, const expr &var) {
+ expr lhs, rhs;
+ // (= #b0 isundef_%var)
+ if (e.isEq(lhs, rhs)) {
+ return (lhs.isZero() && Input::isUndefMask(rhs, var)) ||
+ (rhs.isZero() && Input::isUndefMask(lhs, var));
+ }
+ return false;
+ };
+
+ auto is_if_undef = [&](const expr &e, expr &var, expr &not_undef) {
+ expr undef;
+ // (ite (= #b0 isundef_%var) %var undef)
+ return e.isIf(not_undef, var, undef) &&
+ s.isUndef(undef) &&
+ is_undef_cond(not_undef, var);
+ };
+
+ expr c, a, b, lhs, rhs;
+
+ // two variants
+ // 1) boolean
+ if (is_if_undef(e, a, b)) {
+ s.addUB(move(b));
+ return a;
+ }
+
+ // (ite (= const (ite (= #b0 isundef_%var) %var undef)) #b1 #b0)
+ // TODO: generalize to other undef-generating functions other than ==
+ if (e.isIf(c, a, b) && a.isConst() && b.isConst()) {
+ if (c.isEq(lhs, rhs)) {
+ expr val, not_undef;
+ if (is_if_undef(lhs, val, not_undef)) {
+ s.addUB(move(not_undef));
+ return expr::mkIf(val == rhs, a, b);
+ }
+ if (is_if_undef(rhs, val, not_undef)) {
+ s.addUB(move(not_undef));
+ return expr::mkIf(lhs == val, a, b);
+ }
+ }
+ }
+
+ // 2) (or (and |isundef_%var| undef) (and %var (not |isundef_%var|)))
+ // TODO
+
+ s.addUB(eq_except_padding(val.getType(), e, s[val].value));
+ return e;
+}
+
const StateValue& State::operator[](const Value &val) {
auto &[var, val_uvars, used] = values[values_map.at(&val)];
auto &[sval, uvars] = val_uvars;
(void)var;
- auto simplify = [&](StateValue &sv, bool use_new_slot) -> StateValue& {
+ auto simplify = [&](StateValue &sv0, bool use_new_slot) -> StateValue&{
+ StateValue *sv = &sv0;
if (analysis.non_poison_vals.count(&val)) {
if (use_new_slot) {
assert(i_tmp_values < tmp_values.size());
- tmp_values[i_tmp_values++] = sv;
+ tmp_values[i_tmp_values++] = *sv;
+ use_new_slot = false;
}
assert(i_tmp_values > 0);
StateValue &sv_new = tmp_values[i_tmp_values - 1];
const expr &np = sv_new.non_poison;
sv_new.non_poison = np.isBool() ? true : expr::mkUInt(0, np.bits());
- return sv_new;
+ sv = &sv_new;
}
- return sv;
+
+ auto undef_itr = analysis.non_undef_vals.find(&val);
+ if (undef_itr != analysis.non_undef_vals.end()) {
+ if (use_new_slot) {
+ assert(i_tmp_values < tmp_values.size());
+ tmp_values[i_tmp_values++] = *sv;
+ }
+ assert(i_tmp_values > 0);
+ StateValue &sv_new = tmp_values[i_tmp_values - 1];
+ sv_new.value = undef_itr->second;
+ sv = &sv_new;
+ }
+ return *sv;
};
if (uvars.empty() || !used || disable_undef_rewrite) {
@@ -143,11 +238,27 @@ static expr not_poison_except_padding(const Type &ty, const expr &np) {
return result;
}
-const StateValue& State::getAndAddPoisonUB(const Value &val) {
- auto &v = (*this)[val];
- if (!analysis.non_poison_vals.insert(&val).second)
- return v;
+const StateValue&
+State::getAndAddPoisonUB(const Value &val, bool undef_ub_too) {
+ auto &sv = (*this)[val];
+
+ bool poison_already_added = !analysis.non_poison_vals.insert(&val).second;
+ if (poison_already_added && !undef_ub_too)
+ return sv;
+ expr v = sv.value;
+
+ if (undef_ub_too) {
+ auto I = analysis.non_undef_vals.find(&val);
+ if (I != analysis.non_undef_vals.end()) {
+ v = I->second;
+ } else {
+ v = strip_undef_and_add_ub(*this, val, v);
+ analysis.non_undef_vals.emplace(&val, v);
+ }
+ }
+
+ if (!poison_already_added) {
// mark all operands of val as non-poison if they propagate poison
vector<Value*> todo;
if (auto i = dynamic_cast<const Instr*>(&val)) {
@@ -168,10 +279,11 @@ const StateValue& State::getAndAddPoisonUB(const Value &val) {
}
// If val is an aggregate, all elements should be non-poison
- addUB(not_poison_except_padding(val.getType(), v.non_poison));
+ addUB(not_poison_except_padding(val.getType(), sv.non_poison));
+ }
assert(i_tmp_values < tmp_values.size());
- return tmp_values[i_tmp_values++] = { expr(v.value),
- v.non_poison.isBool() ? true : expr::mkUInt(0, v.non_poison.bits()) };
+ return tmp_values[i_tmp_values++] = { move(v),
+ sv.non_poison.isBool() ? true : expr::mkUInt(0, sv.non_poison.bits()) };
}
const State::ValTy& State::at(const Value &val) const {
@@ -184,7 +296,9 @@ const OrExpr* State::jumpCondFrom(const BasicBlock &bb) const {
return I == pres.end() ? nullptr : &I->second.domain.path;
}
-bool State::isUndef(const expr &e) const {
+bool State::isUndef(const expr &e, const Value *used_by) const {
+ if (used_by)
+ return at(*used_by).second.count(e) != 0;
return undef_vars.count(e) != 0;
}

MODIFY
ir/state.h
ir/state.h
@@ -49,6 +49,8 @@ private:
struct ValueAnalysis {
std::set<const Value *> non_poison_vals; // vars that are not poison
+ // vars that are not undef (partially undefs are not allowed too)
+ std::map<const Value *, smt::expr> non_undef_vals;
void intersect(const ValueAnalysis &other);
void reset();
@@ -130,10 +132,12 @@ public:
const StateValue& exec(const Value &v);
const StateValue& operator[](const Value &val);
const StateValue& getAndAddUndefs(const Value &val);
- const StateValue& getAndAddPoisonUB(const Value &val);
+ // If undef_ub is true, UB is also added when val was undef
+ const StateValue& getAndAddPoisonUB(const Value &val, bool undef_ub = false);
+
const ValTy& at(const Value &val) const;
const smt::OrExpr* jumpCondFrom(const BasicBlock &bb) const;
- bool isUndef(const smt::expr &e) const;
+ bool isUndef(const smt::expr &e, const Value *used_by = nullptr) const;
bool startBB(const BasicBlock &bb);
void addJump(const BasicBlock &dst);

MODIFY
ir/value.cpp
ir/value.cpp
@@ -231,6 +231,13 @@ StateValue Input::mkInput(State &s, const Type &ty, unsigned child) const {
return { move(val), never_poison ? true : expr::mkBoolVar(np_name.c_str()) };
}
+bool Input::isUndefMask(const expr &e, const expr &var) {
+ auto ty_name = e.fn_name();
+ auto var_name = var.fn_name();
+ return string_view(ty_name).substr(0, 8) == "isundef_" &&
+ string_view(ty_name).substr(8, var_name.size()) == var_name;
+}
+
StateValue Input::toSMT(State &s) const {
return mkInput(s, getType(), 0);
}

MODIFY
ir/value.h
ir/value.h
@@ -122,6 +122,8 @@ public:
const ParamAttrs &getAttributes() const { return attrs; }
StateValue toSMT(State &s) const override;
smt::expr getUndefVar(const Type &ty, unsigned child) const;
+
+ static bool isUndefMask(const smt::expr &e, const smt::expr &var);
};
}

ADD
tests/alive-tv/undef/opt-noundef.srctgt.ll
+; TEST-ARGS: -se-verbose
+declare void @f(i32 noundef)
+
+define i32 @src(i32 %x) {
+ call void @f(i32 %x)
+ ret i32 %x
+}
+
+define i32 @tgt(i32 %x) {
+ call void @f(i32 %x)
+ ret i32 %x
+}
+
+; CHECK: return = %x / true

Add undef analysis (#487)