poison analysis: propagate poison through operands
MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -90,8 +90,9 @@ uint64_t getGlobalVarSize(const IR::Value *V) {
namespace IR {
-expr Instr::eqType(const Instr &i) const {
- return getType() == i.getType();
+bool Instr::propagatesPoison() const {
+ // be on the safe side
+ return false;
}
expr Instr::getTypeConstraints() const {
@@ -184,6 +185,10 @@ vector<Value*> BinOp::operands() const {
return { lhs, rhs };
}
+bool BinOp::propagatesPoison() const {
+ return true;
+}
+
void BinOp::rauw(const Value &what, Value &with) {
RAUW(lhs);
RAUW(rhs);
@@ -763,6 +768,10 @@ vector<Value*> UnaryOp::operands() const {
return { val };
}
+bool UnaryOp::propagatesPoison() const {
+ return true;
+}
+
void UnaryOp::rauw(const Value &what, Value &with) {
RAUW(val);
}
@@ -867,6 +876,10 @@ vector<Value*> UnaryReductionOp::operands() const {
return { val };
}
+bool UnaryReductionOp::propagatesPoison() const {
+ return true;
+}
+
void UnaryReductionOp::rauw(const Value &what, Value &with) {
RAUW(val);
}
@@ -960,6 +973,10 @@ vector<Value*> TernaryOp::operands() const {
return { a, b, c };
}
+bool TernaryOp::propagatesPoison() const {
+ return true;
+}
+
void TernaryOp::rauw(const Value &what, Value &with) {
RAUW(a);
RAUW(b);
@@ -1054,6 +1071,10 @@ vector<Value*> ConversionOp::operands() const {
return { val };
}
+bool ConversionOp::propagatesPoison() const {
+ return true;
+}
+
void ConversionOp::rauw(const Value &what, Value &with) {
RAUW(val);
}
@@ -1703,6 +1724,10 @@ vector<Value*> ICmp::operands() const {
return { a, b };
}
+bool ICmp::propagatesPoison() const {
+ return true;
+}
+
void ICmp::rauw(const Value &what, Value &with) {
RAUW(a);
RAUW(b);
@@ -2072,9 +2097,8 @@ void Branch::print(ostream &os) const {
StateValue Branch::toSMT(State &s) const {
if (cond) {
- auto &c = s[*cond];
+ auto &c = s.getAndAddPoisonUB(*cond);
auto [cond_val, not_undef] = strip_undef(s, *cond, c.value);
- s.addUB(c.non_poison);
s.addUB(move(not_undef));
s.addCondJump(cond_val, dst_true, *dst_false);
} else {
@@ -2126,11 +2150,10 @@ void Switch::print(ostream &os) const {
}
StateValue Switch::toSMT(State &s) const {
- auto &val = s[*value];
+ auto &val = s.getAndAddPoisonUB(*value);
expr default_cond(true);
auto [cond_val, not_undef] = strip_undef(s, *value, val.value);
- s.addUB(val.non_poison);
s.addUB(move(not_undef));
for (auto &[value_cond, bb] : targets) {
@@ -2522,8 +2545,7 @@ void StartLifetime::print(std::ostream &os) const {
}
StateValue StartLifetime::toSMT(State &s) const {
- auto &[p, np] = s[*ptr];
- s.addUB(np);
+ auto &p = s.getAndAddPoisonUB(*ptr).value;
s.getMemory().startLifetime(p);
return {};
}
@@ -2873,9 +2895,8 @@ 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, np_bytes] = s[*bytes];
+ auto &vbytes = s.getAndAddPoisonUB(*bytes).value;
s.addUB((vbytes != 0).implies(np_dst && np_src));
- s.addUB(np_bytes);
if (vbytes.bits() > bits_size_t)
s.addUB(
@@ -2926,9 +2947,8 @@ void Memcmp::print(ostream &os) const {
StateValue Memcmp::toSMT(State &s) const {
auto &[vptr1, np1] = s[*ptr1];
auto &[vptr2, np2] = s[*ptr2];
- auto &[vnum, npn] = s[*num];
+ auto &vnum = s.getAndAddPoisonUB(*num).value;
s.addUB((vnum != 0).implies(np1 && np2));
- s.addUB(npn);
Pointer p1(s.getMemory(), vptr1), p2(s.getMemory(), vptr2);
// memcmp can be optimized to load & icmps, and it requires this

MODIFY
ir/instr.h
ir/instr.h
@@ -19,8 +19,8 @@ protected:
public:
virtual std::vector<Value*> operands() const = 0;
+ virtual bool propagatesPoison() const;
virtual void rauw(const Value &what, Value &with) = 0;
- virtual smt::expr eqType(const Instr &i) const;
smt::expr getTypeConstraints() const override;
virtual smt::expr getTypeConstraints(const Function &f) const = 0;
virtual std::unique_ptr<Instr> dup(const std::string &suffix) const = 0;
@@ -62,6 +62,7 @@ public:
unsigned flags = 0, FastMathFlags fmath = {});
std::vector<Value*> operands() const override;
+ bool propagatesPoison() const override;
void rauw(const Value &what, Value &with) override;
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
@@ -89,6 +90,7 @@ public:
Op getOp() const { return op; }
Value& getValue() const { return *val; }
std::vector<Value*> operands() const override;
+ bool propagatesPoison() const override;
void rauw(const Value &what, Value &with) override;
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
@@ -113,6 +115,7 @@ public:
: Instr(type, std::move(name)), val(&val), op(op) {}
std::vector<Value*> operands() const override;
+ bool propagatesPoison() const override;
void rauw(const Value &what, Value &with) override;
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
@@ -135,6 +138,7 @@ public:
FastMathFlags fmath = {});
std::vector<Value*> operands() const override;
+ bool propagatesPoison() const override;
void rauw(const Value &what, Value &with) override;
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
@@ -159,6 +163,7 @@ public:
Op getOp() const { return op; }
Value& getValue() const { return *val; }
std::vector<Value*> operands() const override;
+ bool propagatesPoison() const override;
void rauw(const Value &what, Value &with) override;
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;
@@ -260,6 +265,7 @@ public:
ICmp(Type &type, std::string &&name, Cond cond, Value &a, Value &b);
std::vector<Value*> operands() const override;
+ bool propagatesPoison() const override;
void rauw(const Value &what, Value &with) override;
void print(std::ostream &os) const override;
StateValue toSMT(State &s) const override;

MODIFY
ir/state.cpp
ir/state.cpp
@@ -128,6 +128,25 @@ const StateValue& State::getAndAddPoisonUB(const Value &val) {
if (!analysis.non_poison_vals.insert(&val).second)
return v;
+ // mark all operands of val as non-poison if they propagate poison
+ vector<Value*> todo;
+ if (auto i = dynamic_cast<const Instr*>(&val)) {
+ if (i->propagatesPoison())
+ todo = i->operands();
+ }
+ while (!todo.empty()) {
+ auto v = todo.back();
+ todo.pop_back();
+ if (!analysis.non_poison_vals.insert(v).second)
+ continue;
+ if (auto i = dynamic_cast<const Instr*>(v)) {
+ if (i->propagatesPoison()) {
+ auto ops = i->operands();
+ todo.insert(todo.end(), ops.begin(), ops.end());
+ }
+ }
+ }
+
// If val is an aggregate, all elements should be non-poison
addUB(v.non_poison.isBool() ? v.non_poison : v.non_poison == 0);
assert(i_tmp_values < tmp_values.size());

MODIFY
tools/transform.cpp
tools/transform.cpp
@@ -937,7 +937,7 @@ TypingAssignments TransformVerify::getTypings() const {
if (check_each_var) {
for (auto &i : t.src.instrs()) {
if (!i.isVoid())
- c &= i.eqType(*tgt_instrs.at(i.getName()));
+ c &= i.getType() == tgt_instrs.at(i.getName())->getType();
}
}
return { move(c) };

poison analysis: propagate poison through operands