optimize pointer comparison when comparing equality with null or same origin
MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -1904,6 +1904,8 @@ void ICmp::print(ostream &os) const {
case Any: condtxt = ""; break;
}
os << getName() << " = icmp " << condtxt << *a << ", " << b->getName();
+ if (use_provenance)
+ os << ", use_provenance";
}
static expr build_icmp_chain(const expr &var,
@@ -1944,9 +1946,13 @@ StateValue ICmp::toSMT(State &s) const {
};
if (isPtrCmp()) {
- fn = [&s, fn](const expr &av, const expr &bv, Cond cond) {
+ fn = [this, &s, fn](const expr &av, const expr &bv, Cond cond) {
Pointer lhs(s.getMemory(), av);
Pointer rhs(s.getMemory(), bv);
+ if (use_provenance) {
+ assert(cond == EQ || cond == NE);
+ return cond == EQ ? lhs == rhs : lhs != rhs;
+ }
return fn(lhs.getAddress(), rhs.getAddress(), cond);
};
}

MODIFY
ir/instr.h
ir/instr.h
@@ -234,12 +234,17 @@ private:
std::string cond_name;
Cond cond;
bool defined;
+ bool use_provenance = false;
smt::expr cond_var() const;
public:
ICmp(Type &type, std::string &&name, Cond cond, Value &a, Value &b);
bool isPtrCmp() const;
+ bool usesProvenance() const { return use_provenance; }
+ void setUseProvenance(bool flag) { use_provenance = flag; }
+ Cond getCond() const { return cond; }
+
std::vector<Value*> operands() const override;
bool propagatesPoison() const override;
void rauw(const Value &what, Value &with) override;
@@ -610,6 +615,7 @@ public:
void addIdx(uint64_t obj_size, Value &idx);
Value& getPtr() const { return *ptr; }
auto& getIdxs() const { return idxs; }
+ bool isInBounds() const { return inbounds; }
uint64_t getMaxAllocSize() const override;
uint64_t getMaxAccessSize() const override;

ADD
tests/alive-tv/opt-memory/ptrcmp-null.ident.ll
+; TEST-ARGS: -dbg
+define i1 @f(i8* %p) {
+ %p2 = getelementptr inbounds i8, i8* %p, i64 0
+ %c = icmp eq i8* %p2, null
+ ret i1 %c
+}
+
+; CHECK: use_provenance
+; CHECK: has_ptr2int: 0

ADD
tests/alive-tv/opt-memory/ptrcmp-null2.ident.ll
+; TEST-ARGS: -dbg
+define i1 @f(i8* %p) {
+ %p2 = getelementptr inbounds i8, i8* %p, i64 0
+ %c = icmp eq i8* null, %p2
+ ret i1 %c
+}
+
+; CHECK: use_provenance
+; CHECK: has_ptr2int: 0

ADD
tests/alive-tv/opt-memory/ptrcmp-sameorigin.ident.ll
+; TEST-ARGS: -dbg
+define i1 @f(i8* %p) {
+ %p2 = getelementptr inbounds i8, i8* %p, i64 0
+ %p3 = getelementptr inbounds i8, i8* %p, i64 1
+ %c = icmp eq i8* %p2, %p3
+ ret i1 %c
+}
+
+; CHECK: use_provenance
+; CHECK: has_ptr2int: 0

ADD
tests/alive-tv/opt-memory/ptrcmp-sameorigin2.ident.ll
+; TEST-ARGS: -dbg
+define i1 @f(i8* %p) {
+ %p2 = getelementptr i8, i8* %p, i64 0
+ %p3 = getelementptr i8, i8* %p, i64 1
+ %c = icmp eq i8* %p2, %p3
+ ret i1 %c
+}
+
+; CHECK: use_provenance
+; CHECK: has_ptr2int: 0

MODIFY
tests/lit/lit/formats/alive2test.py
tests/lit/lit/formats/alive2test.py
@@ -138,8 +138,10 @@ class Alive2Test(TestFormat):
if is_timeout(output):
return lit.Test.PASS, ''
- chk = self.regex_check.search(input)
- if chk != None and output.find(chk.group(1).strip()) == -1:
+ # allow multiple 'CHECK: ..'
+ chks = self.regex_check.findall(input)
+ for chk in chks:
+ if output.find(chk.strip()) == -1:
return lit.Test.FAIL, output
chk_not = self.regex_check_not.search(input)
@@ -152,7 +154,8 @@ class Alive2Test(TestFormat):
return lit.Test.FAIL, output
expect_err = self.regex_errs.search(input)
- if expect_err is None and xfail is None and chk is None and chk_not is None:
+ if expect_err is None and xfail is None and len(chks) == 0 and \
+ chk_not is None:
# If there's no other test, correctness of the transformation should be
# checked.
if exitCode == 0 and output.find(ok_string) != -1 and \

MODIFY
tools/transform.cpp
tools/transform.cpp
@@ -828,7 +828,7 @@ static void calculateAndInitConstants(Transform &t) {
min_access_size = gcd(min_access_size, getCommonAccessSize(t));
} else if (auto *ic = dynamic_cast<const ICmp*>(&i)) {
- has_ptr2int |= ic->isPtrCmp();
+ has_ptr2int |= ic->isPtrCmp() && !ic->usesProvenance();
}
}
}
@@ -1214,6 +1214,38 @@ static void remove_unreachable_bbs(Function &f) {
}
}
+static void optimize_ptrcmp(Function &f) {
+ auto is_inbounds = [](const Value &v) {
+ if (auto *gep = dynamic_cast<const GEP*>(&v))
+ return gep->isInBounds();
+
+ return returns_local(v);
+ };
+
+ for (auto &i : f.instrs()) {
+ auto *icmp = dynamic_cast<const ICmp*>(&i);
+ if (!icmp)
+ continue;
+
+ auto cond = icmp->getCond();
+ bool is_eq = cond == ICmp::EQ || cond == ICmp::NE;
+
+ Value *op0 = const_cast<Value *>(icmp->operands()[0]);
+ Value *op1 = const_cast<Value *>(icmp->operands()[1]);
+ if (is_eq &&
+ ((is_inbounds(*op0) && dynamic_cast<NullPointerValue*>(op1)) ||
+ (is_inbounds(*op1) && dynamic_cast<NullPointerValue*>(op0)))) {
+ // (gep inbounds p, ofs) == null
+ const_cast<ICmp*>(icmp)->setUseProvenance(true);
+ }
+
+ auto base_and_ofs0 = collect_gep_offsets(*op0);
+ auto base_and_ofs1 = collect_gep_offsets(*op1);
+ if (is_eq && base_and_ofs0.first == base_and_ofs1.first)
+ const_cast<ICmp*>(icmp)->setUseProvenance(true);
+ }
+}
+
void Transform::preprocess() {
remove_unreachable_bbs(src);
remove_unreachable_bbs(tgt);
@@ -1239,6 +1271,10 @@ void Transform::preprocess() {
tgt.getFirstBB().delInstr(itgt);
}
+ // optimize pointer comparisons
+ optimize_ptrcmp(src);
+ optimize_ptrcmp(tgt);
+
// remove side-effect free instructions without users
vector<Instr*> to_remove;
for (auto fn : { &src, &tgt }) {

optimize pointer comparison when comparing equality with null or same origin (#715)