This is an archive of the discontinued LLVM Phabricator instance.

[WIP][ScalarEvolution] Strictly enforce pointer/int type rules.
AbandonedPublic

Authored by efriedma on Jun 17 2021, 6:10 PM.

Details

Summary

Rules for determining if a SCEV expression is pointer-typed:

  1. SCEVUnknown is a pointer if and only if the LLVM IR value is a pointer.
  2. SCEVPtrToInt is never a pointer.
  3. If any other SCEV expression has no pointer operands, the result is an integer.
  4. If a SCEVAddExpr has exactly one pointer operand, the result is a pointer.
  5. If a SCEVAddRecExpr's first operand is a pointer, and it has no other pointer operands, the result is a pointer.
  6. If a SCEVMinMaxExpr has all pointer operands, the result is a pointer.
  7. Otherwise, the SCEV expression is invalid.

I'm not sure how useful rule 6 is in practice. If we exclude it, we can
guarantee that ScalarEvolution::getPointerBase always returns a
SCEVUnknown, which might be a helpful property. Anyway, I'll leave that
for a followup.

Currently has some regression test failures related to LSR; the
generated code is changing. scev-custom-dl.ll currently crashes because
getPointerDiff() can return SCEVCouldNotCompute for exotic pointers.
Otherwise passes regression tests.

Open questions:

  1. Is it worth keeping getPointerDiff separate from getMinusSCEV? It's an extra SCEV entry point which is in some sense redundant. But one advantage is that the new API lets us land the changes to various transforms incrementally.
  2. How do we want to deal with ScalarEvolution::isImpliedCond? Currently, I have a few targeted bailouts for pointers, but we could just ptrtoint all the operands.
  3. What do we do about exotic pointers? None of the places that use getPointerDiff have any handling for failure.
  4. What do we do about LSR? CollectFixupsAndInitialFormulae() subtracts two pointers to model an icmp; using getPointerDiff here is correct, but wrecks a bunch of the heuristics because "ptrtoint %x" is not the same SCEV expression as "%x". And LSR is really fragile; touching almost anything to try to address that will affect other tests. Not sure what to do here.

Diff Detail

Event Timeline

efriedma created this revision.Jun 17 2021, 6:10 PM
efriedma requested review of this revision.Jun 17 2021, 6:10 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 17 2021, 6:10 PM

Are pointer SCEVConstants disallowed? If so, why?

Are pointer SCEVConstants disallowed? If so, why?

It's currently impossible to create such a constant, even without this patch; the API forces the type to an integer type. I don't see any reason to change that. Normal code doesn't do math on pointers with a known integer value.

SCEVUnknown supports pointer-typed constants.

bmahjour removed a subscriber: bmahjour.Jun 21 2021, 9:20 AM
efriedma edited the summary of this revision. (Show Details)Jun 21 2021, 1:00 PM

This patch will probably end up getting split, so the most important bits I'm looking for feedback on are the following:

  1. Is this worth doing?
  2. Does the getPointerDiff() API make sense?
reames added a comment.EditedJun 22 2021, 4:14 PM

Eli,

I'm not really clear on this yet. I keep debating between this and adding pointer subtraction as a first class concept. I was planning on prototyping the later this week, but ended up busy with something else. Could you give me a week or so to get back to you? If you want to discuss, brainstorming this offline could be really helpful. I keep feeling like I don't have my mind around all of the implications just yet.

The major use cases I've got right now are:

  1. backedge taken computation implementation - can definitely be done without
  2. SCEV-AA
  3. Vectorizer aliasing checks - I think I've convinced myself we only need pointer min/max and not subtract for this.
  4. LSR - may be able to dodge issue

Edit...

The interesting case is when we have p - q, and it turns out that q is based on the same object as p. This is the case where p-q has a well defined* difference for two arbitrary pointers. If we read p and q at different moments (e.g. use ptrtoint) for non-integral pointers we can get two unrelated values which hide the true diff between the pointers which maintain the based on relationship. Basically, we need a way to read both p and q at the same "moment".

  • By analogy to the current icmp semantics, if p and q were based on different objects, the result would be indeterminate, but must preserve the fact the objects can't overlap. e.g. A pointer 10 bytes under the start of one allocation, can't be less than 90 bytes from the beginning of another 100 byte allocation. There's also an interaction with when p and q are poison due to the "inbounds" rules for GEPs.)

I'm not sure I understand what the difference would be between ptrtoint(a) - ptrtoint(b) and ptrsubtract(a, b) would be. I guess the idea is that ptrsubtract() would somehow be allowed with non-integral pointers, where ptrtoint wouldn't be legal? So the question is whether we can get away without adding ptrsubtract(), without significantly regressing non-integral pointer handling?

There are some number of places which actually only care whether the difference between two pointers is a constant. We actually have a dedicated method computeConstantDifference() for that, but it's currently weaker than just writing isa<SCEVConstant>(SE.getMinusSCEV(a, b)) or whatever. I experimented with fixing that, but I think we'd need a completely different implementation strategy.

We could improve computeConstantDifference(), and use it various places to reduce the number of places that want a real pointer diff. Along those lines, there are also a few places that want to compute a constant range for the distance between two pointers; we could also add a method for that.

There are also places that either statically know the two SCEVs they're subtracting have the same pointer base, or don't care about the result if the pointer bases are different; we could add a method for that.

If we had all that, I'm not sure we would need the full-power getPointerDiff() anywhere. At least, looking over my patch, all the cases this patch uses getPointerDiff would be covered, I think, except maybe LSR.

Spent some further time prototyping this. I mocked up a quick and dirty patch which simply made all calls to getMinusSCEV with two pointer arguments return CouldNotCompute. There were surprisingly few places which needed adjusted both based on failing tests, and some (quick) manual skimming. The end result is something which mostly doesn't crash on make check, but bails out of every pointer subtraction query.

Unfortunately, there's some *major* optimization impact. This is to be expected, but given it's the baseline which is being considered for non-integral pointers, we need to assess whether the impact is reasonable.

A few key points:

  1. We completely break dependency analysis as used by the vectorizer, fusion, and distribution passes.
  2. We weaken LSRs ability to fold together related expressions.
  3. We completely break SCEV-AA.

(1) is somewhat of a non-starter. Before we get to how to craw that back, a digression...

Thinking through what the existing code does for subtraction of non-integral pointers, I'm not sure it's even correct for the general case. When we can find a common base in the expressions, everything works out to an integer result, but in the case we can't, we seem (based on the code) to either crash or generate the ptrtoint after all. I'm going to try to find a test case for this, I haven't managed yet.

Given all of that, I think this is the right approach, but we're going to have to deal with the opt impact. One approach is to add specific folding rules for when the base pointer for the two expressions is the same. I think we can recover most of the impact, and suggest using the proxy of "how many test cases fail if I treat *all* pointers this way* as a reasonable metric. I expect we can drive this "close enough" to zero without too much effort.

Style wise, I really don't see the value in the getPointerDiff api. Most of the places which need to compute a diff work with both pointers and integers. I'd rather just have getMinusSCEV documented as being able to return CouldNotCompute when both operands are pointers.

I also want to preserve the existing "it's an error to query information about CouldNotCompute" structure. Given this, callers should bail before calling isKnownX and friends. We should strengthen asserts on access. A couple of the stack traces got surprisingly far into SCEV before we hit an access assert.

FYI, the quick and dirty patch I mentioned in the last comment can be found here: https://reviews.llvm.org/D104761

Ok, I remember why I can't create a case where we miss handle non-integral pointer subtraction. We never expand it. We use the subtract form for analysis, but generate the bounds conflict form (using icmps) in the transforms. There's an undocumented assumption that such subtracts aren't safe to expand. Fun. :)

(This comment is largely an aside, just recording a thought on a vaguely related topic. This has nothing to do with non-integral pointers directly.)

As a further aside, the overlap check we generate in e.g. loop-versioning-licm* is:

%scevgep = getelementptr i8, i8* %a, i64 4
%scevgep1 = getelementptr i8, i8* %b, i64 4
%bound0 = icmp ult i8* %a, %scevgep1
%bound1 = icmp ult i8* %b, %scevgep
%found.conflict = and i1 %bound0, %bound1

This does gets codegened as two distinct checks on x86.

If subtract of pointers was valid in IR, we could instead write:

%diff = sub i8* %a, %b ;; pretend result type is i64
%bound0 = icmp slt i64 %diff, 4
%bound1 = icmp sgt i64 %diff, -4
%found.conflict = and i1 %bound0, %bound1

Which reduces to:

%diff = sub i8* %a, %b ;; pretend result type is i64
%diff.off = add i64 %diff, 3
%1 = icmp ult i64 %diff.off, 7
  • This was the easiest example to exercise, from code structure the loop vectorizer does the same when versioning.

Style wise, I really don't see the value in the getPointerDiff api. Most of the places which need to compute a diff work with both pointers and integers. I'd rather just have getMinusSCEV documented as being able to return CouldNotCompute when both operands are pointers.

Do you mean getMinusSCEV would never generate PtrToInt expressions, or just that it wouldn't generate them for non-integral pointers? I mean, we could make it work either way, but it would probably be easier to support non-integral pointers if all pointers behave the same way.

I also want to preserve the existing "it's an error to query information about CouldNotCompute" structure. Given this, callers should bail before calling isKnownX and friends. We should strengthen asserts on access. A couple of the stack traces got surprisingly far into SCEV before we hit an access assert.

Makes sense.

Style wise, I really don't see the value in the getPointerDiff api. Most of the places which need to compute a diff work with both pointers and integers. I'd rather just have getMinusSCEV documented as being able to return CouldNotCompute when both operands are pointers.

Do you mean getMinusSCEV would never generate PtrToInt expressions, or just that it wouldn't generate them for non-integral pointers? I mean, we could make it work either way, but it would probably be easier to support non-integral pointers if all pointers behave the same way.

Conceptual cleanliness says to treat all pointers the same, but I think the code becomes a lot more complicated if we do. I think I would special case NI pointers for the moment.

Current plan:

  1. Change the semantics of getMinusSCEV(): D104806.
  2. Fix getMinusSCEV() implementation so it doesn't multiply pointers by -1.
  3. Land the small number of remaining changes together with the assertions.
efriedma abandoned this revision.Jul 6 2021, 1:10 PM

I'll post a fresh patch with the remaining changes.