llvm dev - Jun 2017 - LoopVectorize fails to vectorize loops with induction variables with PtrToInt/IntToPtr conversions

On 06/20/2017 03:26 AM, Hal Finkel wrote:
> Hi, Adrien,
Hello Hal!

Thanks for your answer!
> Thanks for reporting this. I recommend that you file a bug report at
> https://bugs.llvm.org/
Will do!
> Whenever I see reports of missed optimization opportunities in the face
> of ptrtoint/inttoptr, my first question is: why are these instructions
> present in the first place? At the IR level, use of inttoptr is highly
> discouraged. Our aliasing analysis, for example, does not look through
> them, and so you'll generally see a lot of missed optimizations when
> they're around.
> In this case, inttoptr seems to be introduced by SROA. SROA should not
> be introducing inttoptr, but rather should be using GEPs on i8* (at
> least), to avoid introducing pointers that our AA can't analyze.
It looks so indeed!
> Beyond that, if we need to handle inttoptr/ptrtoint in SCEV, then maybe
> there's a way to make it smarter about the expressions with which it
can
> deal.
One of the solution I was thinking of was making SCEV "understand"
inttoptr(ptrtoint()), as this is clearly a no-op (and what is happening
here), but it seems not that straightforward to do (hence this
discussion to discuss what should be done :)).
> I'm actually not sure to what "aliasing rules" the comment
you
> quote below is referring. I can certainly understand not being able to
> place "inbounds" on some generated GEPs, but otherwise this seems
> non-obvious to me (i.e. either the expander can identify a base pointer
> from which to generate the GEP, or it can't, in which case it needs to
> generate a inttoptr).
The way I understand it is that, for a pointer to a fixed-size array P,
by using I=ptrtoint(P)/arithmetic operations(I)/inttoptr(I) we can
potentially end-up with a pointer which is not in the original values
that could be computed from the original array (like an out-of-bound
pointer), and thus not "reconstruct" a GEP from it. That's why
SCEV
wouldn't consider them. IIRC, I tried to add ptrtoint/inttoptr as
"no-op" in SCEV, but then the cost-model seemed to be broken (a very
high value was given at some point), and thus vectorization still didn't
happen.

I was also thinking: even if SROA is fixed, nothing prevents another
pass from introducing such constructions in the future, so maybe the
solution is to have a pass (like the one I wrote) that try and cleanup
before any usage of SCEV? (or done by InstCombine for instance, as this
basically removes the inttoptr(ptrtoint()) combination).
Or having the "inttoptr(ptrtoint())" composition understood by SCEV as
a
no-op might also be a cleaner "long-term" solution...

What do you think?

On 06/20/2017 08:41 PM, Adrien Guinet via llvm-dev
wrote:
> On 06/20/2017 03:26 AM, Hal Finkel wrote:
>> Hi, Adrien,
> 
> Hello Hal!
> 
> Thanks for your answer!
> 
>> Thanks for reporting this. I recommend that you file a bug report at
>> https://bugs.llvm.org/
> 
> Will do!
FTR, the bug report is here: https://bugs.llvm.org/show_bug.cgi?id=33532
. Maybe discussions should be continued there!

On 06/20/2017 01:41 PM, Adrien Guinet wrote:
> On 06/20/2017 03:26 AM, Hal Finkel wrote:
>> Hi, Adrien,
> Hello Hal!
>
> Thanks for your answer!
>
>> Thanks for reporting this. I recommend that you file a bug report at
>> https://bugs.llvm.org/
> Will do!
>
>> Whenever I see reports of missed optimization opportunities in the face
>> of ptrtoint/inttoptr, my first question is: why are these instructions
>> present in the first place? At the IR level, use of inttoptr is highly
>> discouraged. Our aliasing analysis, for example, does not look through
>> them, and so you'll generally see a lot of missed optimizations
when
>> they're around.
>> In this case, inttoptr seems to be introduced by SROA. SROA should not
>> be introducing inttoptr, but rather should be using GEPs on i8* (at
>> least), to avoid introducing pointers that our AA can't analyze.
> It looks so indeed!
>
>> Beyond that, if we need to handle inttoptr/ptrtoint in SCEV, then maybe
>> there's a way to make it smarter about the expressions with which
it can
>> deal.
> One of the solution I was thinking of was making SCEV
"understand"
> inttoptr(ptrtoint()), as this is clearly a no-op (and what is happening
> here), but it seems not that straightforward to do (hence this
> discussion to discuss what should be done :)).
>
>> I'm actually not sure to what "aliasing rules" the
comment you
>> quote below is referring. I can certainly understand not being able to
>> place "inbounds" on some generated GEPs, but otherwise this
seems
>> non-obvious to me (i.e. either the expander can identify a base pointer
>> from which to generate the GEP, or it can't, in which case it needs
to
>> generate a inttoptr).
> The way I understand it is that, for a pointer to a fixed-size array P,
> by using I=ptrtoint(P)/arithmetic operations(I)/inttoptr(I) we can
> potentially end-up with a pointer which is not in the original values
> that could be computed from the original array (like an out-of-bound
> pointer), and thus not "reconstruct" a GEP from it. That's
why SCEV
> wouldn't consider them.
This is exactly what I meant by not being able to create "inbounds" 
GEPs. However, aside from that, I don't recall our semantics restricting 
the formation of "out of bounds" pointers (although there certainly
are
restrictions on the uses of such pointers).
>   IIRC, I tried to add ptrtoint/inttoptr as
> "no-op" in SCEV, but then the cost-model seemed to be broken (a
very
> high value was given at some point), and thus vectorization still
didn't
> happen.
>
> I was also thinking: even if SROA is fixed, nothing prevents another
> pass from introducing such constructions in the future, so maybe the
> solution is to have a pass (like the one I wrote) that try and cleanup
> before any usage of SCEV? (or done by InstCombine for instance, as this
> basically removes the inttoptr(ptrtoint()) combination).
> Or having the "inttoptr(ptrtoint())" composition understood by
SCEV as a
> no-op might also be a cleaner "long-term" solution...
>
> What do you think?
While it is true that nothing prevents it, technically, over time we've 
been removing code from LLVM that creates these in favor of code that 
uses GEPs. I think it would be counter productive to teach some parts of 
the optimizer about inttoptr/ptrtoint, and not BasicAA and all of the 
rest of it. There are certainly some language constructs that must be 
lowered using inttoptr/ptrtoint at the IR level, but usage should be 
limited to those contexts.

The right solution here is to fix SROA, and any other passes that are 
doing this, to use GEPs instead. Only if that's not possible, should we 
consider other solutions. The reason we've chosen this path is that the 
task of teaching the rest of the optimizer to handle inttoptr/ptrtoint 
as truly first-class pointer-manipulation constructs, along with GEPs, 
is highly non-trivial. If, on top of that, we need some canonicalization 
procedure which transforms uses of inttoptr/ptrtoint into GEP-based 
expressions, we can do that too.

  -Hal


-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

Hi,

On Tue, Jun 20, 2017 at 5:54 PM, Hal Finkel <hfinkel at anl.gov>
wrote:
>>> Whenever I see reports of missed optimization opportunities in the
face
>>> of ptrtoint/inttoptr, my first question is: why are these
instructions
>>> present in the first place? At the IR level, use of inttoptr is
highly
>>> discouraged. Our aliasing analysis, for example, does not look
through
>>> them, and so you'll generally see a lot of missed optimizations
when
>>> they're around.
+1
> This is exactly what I meant by not being able to create
"inbounds" GEPs.
> However, aside from that, I don't recall our semantics restricting the
> formation of "out of bounds" pointers (although there certainly
are
> restrictions on the uses of such pointers).
One problem is that there is a difference between (assume A and B are
distinct allocations):

A = i8* some_ptr
B = i8* some_ptr
C = inttoptr(ptrtoint(A) + ptrtoint(B))

and

A = i8* some_ptr
B = i8* some_ptr
C = gep(A, ptrtoint(B))

As far as I know, in the former case C aliases both A and B, where in
the latter case C aliases only A (and not B).

The comment in SCEV is very old, but I suspect it is trying to avoid
accidentally converting the former into the latter via a SCEV creation
-> SCEV expansion step.

-- Sanjoy