optimize icmp to only compare offsets of two pointers if they are inbounds
MODIFY
ir/instr.cpp
ir/instr.cpp
@@ -1904,8 +1904,11 @@ void ICmp::print(ostream &os) const {
case Any: condtxt = ""; break;
}
os << getName() << " = icmp " << condtxt << *a << ", " << b->getName();
- if (use_provenance)
- os << ", use_provenance";
+ switch (pcmode) {
+ case INTEGRAL: break;
+ case PROVENANCE: os << ", use_provenance"; break;
+ case OFFSETONLY: os << ", offsetonly"; break;
+ }
}
static expr build_icmp_chain(const expr &var,
@@ -1949,11 +1952,16 @@ StateValue ICmp::toSMT(State &s) const {
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) {
+ switch (pcmode) {
+ case INTEGRAL:
+ return fn(lhs.getAddress(), rhs.getAddress(), cond);
+ case PROVENANCE:
assert(cond == EQ || cond == NE);
return cond == EQ ? lhs == rhs : lhs != rhs;
+ case OFFSETONLY:
+ return fn(lhs.getOffset(), rhs.getOffset(), cond);
}
- return fn(lhs.getAddress(), rhs.getAddress(), cond);
+ UNREACHABLE();
};
}

MODIFY
ir/instr.h
ir/instr.h
@@ -228,21 +228,26 @@ public:
class ICmp final : public Instr {
public:
enum Cond { EQ, NE, SLE, SLT, SGE, SGT, ULE, ULT, UGE, UGT, Any };
+ enum PtrCmpMode {
+ INTEGRAL,
+ PROVENANCE, // compare pointer provenance & offsets
+ OFFSETONLY // cmp ofs only. meaningful only when ptrs are based on same obj
+ };
private:
Value *a, *b;
std::string cond_name;
Cond cond;
bool defined;
- bool use_provenance = false;
+ PtrCmpMode pcmode = INTEGRAL;
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; }
+ PtrCmpMode getPtrCmpMode() const { return pcmode; }
+ void setPtrCmpMode(PtrCmpMode mode) { pcmode = mode; }
Cond getCond() const { return cond; }
std::vector<Value*> operands() const override;

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

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

MODIFY
tests/alive-tv/undef/opt-noundef.ident.ll
tests/alive-tv/undef/opt-noundef.ident.ll
; TEST-ARGS: -se-verbose
-declare void @f(i32 noundef)
+declare void @g(i32 noundef)
define i32 @f(i32 %x) {
- call void @f(i32 %x)
+ call void @g(i32 %x)
ret i32 %x
}

MODIFY
tests/lit/lit/formats/alive2test.py
tests/lit/lit/formats/alive2test.py
@@ -64,7 +64,8 @@ class Alive2Test(TestFormat):
not os.path.isdir(filepath) and \
(filename.endswith('.opt') or filename.endswith('.src.ll') or
filename.endswith('.srctgt.ll') or filename.endswith('.c') or
- filename.endswith('.cpp') or filename.endswith('.opt.ll')):
+ filename.endswith('.cpp') or filename.endswith('.opt.ll') or
+ filename.endswith('.ident.ll')):
yield lit.Test.Test(testSuite, path_in_suite + (filename,), localConfig)

MODIFY
tools/transform.cpp
tools/transform.cpp
@@ -538,6 +538,48 @@ static bool returns_local(const Value &v) {
// TODO: add noalias fn
}
+static Value *get_base_ptr(Value *ptr) {
+ vector<Value*> todo = { ptr };
+ Value *base_ptr = nullptr;
+ set<Value*> seen;
+ do {
+ ptr = todo.back();
+ todo.pop_back();
+ if (!seen.insert(ptr).second)
+ continue;
+
+ if (auto gep = dynamic_cast<GEP*>(ptr)) {
+ todo.emplace_back(&gep->getPtr());
+ continue;
+ }
+
+ if (auto c = isNoOp(*ptr)) {
+ todo.emplace_back(c);
+ continue;
+ }
+
+ if (auto phi = dynamic_cast<Phi*>(ptr)) {
+ auto ops = phi->operands();
+ todo.insert(todo.end(), ops.begin(), ops.end());
+ continue;
+ }
+
+ if (auto s = dynamic_cast<Select*>(ptr)) {
+ todo.emplace_back(s->getTrueValue());
+ todo.emplace_back(s->getFalseValue());
+ continue;
+ }
+
+ if (base_ptr && base_ptr != ptr)
+ return nullptr;
+
+ base_ptr = ptr;
+
+ } while (!todo.empty());
+
+ return base_ptr;
+}
+
static bool may_be_nonlocal(Value *ptr) {
vector<Value*> todo = { ptr };
set<Value*> seen;
@@ -828,7 +870,8 @@ 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() && !ic->usesProvenance();
+ has_ptr2int |= ic->isPtrCmp() &&
+ (ic->getPtrCmpMode() == ICmp::INTEGRAL);
}
}
}
@@ -1236,13 +1279,17 @@ static void optimize_ptrcmp(Function &f) {
((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);
+ const_cast<ICmp*>(icmp)->setPtrCmpMode(ICmp::PROVENANCE);
}
- 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);
+ auto base0 = get_base_ptr(op0);
+ auto base1 = get_base_ptr(op1);
+ if (base0 && base0 == base1) {
+ if (is_eq)
+ const_cast<ICmp*>(icmp)->setPtrCmpMode(ICmp::PROVENANCE);
+ else if (is_inbounds(*op0) && is_inbounds(*op1))
+ const_cast<ICmp*>(icmp)->setPtrCmpMode(ICmp::OFFSETONLY);
+ }
}
}

optimize icmp to only compare offsets of two pointers if they are inbounds (#718)