Page MenuHomePhabricator

Teach scalar evolution to handle inttoptr/ptrtoint
Needs ReviewPublic

Authored by davidxl on Sep 2 2017, 9:06 PM.

Details

Reviewers
wmi
sanjoy
anemet
Summary

This enhancement will enable loop vectorizations that are currently blocked due to noop inttoptr/ptrtoint operations.

The change itself is straightforward, but it exposes a few bugs in existing code. For instance, const_expr created by the expander can grow exponentially so some size limit needs to be applied. The expander also invalidates some of the SCEVs for some of the values (when noop cast is inserted) which can leads to inconsistent SCEVs with other cached values when recomputed (e.g, when scalar loop's header phi's init value is replaced by loop vectorizer). This patch also fixes those problems.

Diff Detail

Event Timeline

davidxl created this revision.Sep 2 2017, 9:06 PM

Before we go down this route, can you describe the class of inputs you're trying to handle? I ask because, at least historically, we've thought of inttoptr/ptrtoint as anti-canonical. We've held the line against teaching AA, SCEV, etc. about them. Taking a quick look at your LoopVectorizer tests, it looks like mostly cases where integer variables, that are really pointers is disguise, are being used as induction variables. Could we aggressively canonicalize inttoptr/ptrtoint toward i8* and GEPs instead (in InstCombine or similar)? If that's possible, I'd much rather we do that. This will also have the advantage that AA might understand what's going on (as will SCEV will no changes there), and will enable additional optimizations.

lib/Transforms/Scalar/AlignmentFromAssumptions.cpp
276 ↗(On Diff #113674)

I'm not sure that this is correct: How do we know that AAPtr is a pointer value? The idea here is that there's some expression that looks like ptrtoint(ptr) + e1 + e2 + ..., and we want to separate it into (ptr, e1 + e2 + ...). If we update SCEV to look through ptrtoint, we can't do this in the same way. I imagine we need to write a visitor to pull out the underlying pointer, or we need to not use SCEV for this task.

The class of inputs are usually generated by other optimizations such as SROA from C++ code -- the int/ptr conversions are usually not directly created by the user code. Logically speaking, handling of inttoptr/ptrtoint is no different from BitCast operation (ideally also implemented using BitCast op, but not doable due to IR spec), so there is no reason we should treat them as opaque while not doing so for BitCast.

Unless we can fully get rid of these operations, analysis passes will still have to deal with them. Missing handling those operations is simply a bug to be fixed independent of wether there is a pass to reduce/eliminate them.

davidxl added inline comments.Sep 3 2017, 12:14 AM
lib/Transforms/Scalar/AlignmentFromAssumptions.cpp
276 ↗(On Diff #113674)

Won't adding a pointer type check be enough ?

The class of inputs are usually generated by other optimizations such as SROA from C++ code -- the int/ptr conversions are usually not directly created by the user code.

SROA shouldn't be doing that. This is the last major problematic pass in the canonicalization part of the pipeline. It also hurts our ability to do AA on that code. Please just fix SROA. It should cast to i8* and use GEPs.

Logically speaking, handling of inttoptr/ptrtoint is no different from BitCast operation (ideally also implemented using BitCast op, but not doable due to IR spec), so there is no reason we should treat them as opaque while not doing so for BitCast.

We can't ever get rid of them completely, because the conversions are necessary for C/C++ lowering. That does not mean that we need to treat them as part of our canonical form. GEPs are much easier to deal with for AA and other kinds of simplification, and so we should canonicalize toward using pointer casts and GEPs. Especially in recent years, we've definitely been pushing in that direction. Having one canonical form in this regard keeps us from having to code many things twice (once for pointers and GEPs and once for ptrtoint/inttoptr + arithmetic).

Unless we can fully get rid of these operations, analysis passes will still have to deal with them. Missing handling those operations is simply a bug to be fixed independent of wether there is a pass to reduce/eliminate them.

I disagree. If we canonicalize away from them, then the only things left are things we really can't analyze anyway.

We might want some of the bug fixes from this patch regardless.

sanjoy requested changes to this revision.Sep 3 2017, 12:09 PM

Hi David,

Generally it is not safe to look through inttoptr and ptrtoint in SCEV. https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/ScalarEvolution.cpp#L6053 has a little bit of the rationale, but basically the problem is that in:

%i0 = ptrtoint i8* %p0 to i64
%i1 = ptrtoint i8* %p1 to i64
%i2 = add i32 %i0, %i1
%ptr = inttoptr i64 %i2 to i8*

%ptr can alias both %p0 and %p1. However, if you round-trip %ptr through SCEV and SCEVExpander, then nothing stops SCEVExpander from expanding the SCEV for %ptr to

%i0 = ptrtoint i8* %p0 to i64
%i1 = ptrtoint i8* %p1 to i64
%p0_ = inttoptr i64 %i0 to i8*
%ptr = getelementptr i8, i8* %p0_, i64 %p0

and %ptr no longer aliases %p1 (assume that we can prove %p0 no-alias %p1 in both the snippets).

In other words, ptrtoint and inttoptr are not the same as bitcast since the former two have aliasing implications while the latter does not.

We could fix this in SCEV with some representational changes, but before that I'd prefer exploring Hal's direction of avoiding generating ptrtoint and inttoptr altogether.

This revision now requires changes to proceed.Sep 3 2017, 12:09 PM
davidxl updated this revision to Diff 116068.Sep 20 2017, 2:11 PM
davidxl edited edge metadata.

Addressed review feedback.

In this version, more strict check is added such that int phis that feeds inttoptr whose result is actually used by load/store/getelemenptr operations are considered from this instruction combining. This is strictly not necessary for this particular transformation, but there is a concern that some latent bug may be exposed if not done.

Also added a negative test case.

Um -- updated the wrong patch. Please ignore.