llvm dev - Feb 2014 - [LLVMdev] RFC: GEP as canonical form for pointer addressing

On 02/17/2014 02:53 PM, Andrew Trick wrote:
> On Feb 17, 2014, at 2:31 AM, David Chisnall <David.Chisnall at
cl.cam.ac.uk> wrote:
>
>> On 15 Feb 2014, at 23:55, Andrew Trick <atrick at apple.com>
wrote:
>>
>>> On Feb 14, 2014, at 5:18 PM, Philip Reames <listmail at
philipreames.com> wrote:
>>>
>>>> RFC: GEP as canonical form for pointer addressing
>>>>
>>>> I would like to propose that we designate GEPs as the canonical
form for pointer addressing in LLVM IR before CodeGenPrepare.
>>>>
>>>> Corollaries
>>>> 1) It is legal for an optimizer to convert
inttoptr+arithmetic+inttoptr sequences to GEPs, but not vice versa.
>>>> 2) Input IR which does not contain inttoptr instructions will
never contain inttoptr instructions (before CodeGenPrepare.)
>>>>
>>>> I've spoken with Nick Lewycky & Owen Anderson offline
at the last social.  On first reflection, both were okay with the proposal, but
I'd like broader buy-in and discussion.  Nick & Owen, if I've
accidentally misrepresented our discussion or you've had second thoughts
since, please speak up.
>>> FWIW, I think it would be nice if standard optimization passes have
this property of being well behaved with respect to pointer types, and I don’t
see a good reason for canonical IR passes to lose pointer types. I also think
it’s the only way to mix the optimization of pointer values with precise GC. It
seems that you just want LLVM developers to generally agree that certain passes
will be well behaved (you can disable any others). It may just be a matter of
documenting those passes. Ideally we could formalize this by declaring a pass as
pointer-safe and verifying. Can we easily verify that no memory access is based
on inttoptr?
>> Not directly related, but our canonical form for loops involving
pointers[1] turns a loop that contains a GEP with the loop induction variable
into a GEP with the increment inside the loop.  This has two annoying properties
for code generation:
>>
>> - The GEP with the induction variable as the offset maps cleanly to CPU
addressing modes and so we generate better code if we don't do this
canonicalisation, and therefore end up trying to undo it in the back end (yuck).
>>
>> - If the source is the start of an object, then this behaviour is
GC-hostile because it means that IR that contains a pointer to an object start
now only contains a pointer to the middle, requiring the GC to deal with inner
pointers.
>>
>> It would be nice if we could have canonical forms such that if the
front end ensures that there are no inner pointers without pointers to the
object's start in the IR, the optimisers don't break this.
>>
>> David
>>
>> [1] Are canonical forms actually documented anywhere, or are they
simply undocumented implicit contracts?
> I would say whatever form is currently generated by IR passes is defined as
canonical. It’s not easy to specify. At some points in the pipeline (early and
late) it’s fine to permit multiple forms of the same expression as long as it’s
canonical-enough for the downstream analysis.
>
> If some pass is generating a suboptimal form, it’s good to question whether
it’s really necessary for any analysis. If not, we should change it. Without a
test case, I can’t say what issue you’re running into above.
David, do you happen to have a test case on hand?  I know I've seen this 
before, but my attempt to write out a quick example from memory failed.

Philip

On 18 Feb 2014, at 19:51, Philip Reames <listmail at philipreames.com>
wrote:
> 
> On 02/17/2014 02:53 PM, Andrew Trick wrote:
>> On Feb 17, 2014, at 2:31 AM, David Chisnall <David.Chisnall at
cl.cam.ac.uk> wrote:
>> 
>>> On 15 Feb 2014, at 23:55, Andrew Trick <atrick at apple.com>
wrote:
>>> 
>>>> On Feb 14, 2014, at 5:18 PM, Philip Reames <listmail at
philipreames.com> wrote:
>>>> 
>>>>> RFC: GEP as canonical form for pointer addressing
>>>>> 
>>>>> I would like to propose that we designate GEPs as the
canonical form for pointer addressing in LLVM IR before CodeGenPrepare.
>>>>> 
>>>>> Corollaries
>>>>> 1) It is legal for an optimizer to convert
inttoptr+arithmetic+inttoptr sequences to GEPs, but not vice versa.
>>>>> 2) Input IR which does not contain inttoptr instructions
will never contain inttoptr instructions (before CodeGenPrepare.)
>>>>> 
>>>>> I've spoken with Nick Lewycky & Owen Anderson
offline at the last social.  On first reflection, both were okay with the
proposal, but I'd like broader buy-in and discussion.  Nick & Owen, if
I've accidentally misrepresented our discussion or you've had second
thoughts since, please speak up.
>>>> FWIW, I think it would be nice if standard optimization passes
have this property of being well behaved with respect to pointer types, and I
don’t see a good reason for canonical IR passes to lose pointer types. I also
think it’s the only way to mix the optimization of pointer values with precise
GC. It seems that you just want LLVM developers to generally agree that certain
passes will be well behaved (you can disable any others). It may just be a
matter of documenting those passes. Ideally we could formalize this by declaring
a pass as pointer-safe and verifying. Can we easily verify that no memory access
is based on inttoptr?
>>> Not directly related, but our canonical form for loops involving
pointers[1] turns a loop that contains a GEP with the loop induction variable
into a GEP with the increment inside the loop.  This has two annoying properties
for code generation:
>>> 
>>> - The GEP with the induction variable as the offset maps cleanly to
CPU addressing modes and so we generate better code if we don't do this
canonicalisation, and therefore end up trying to undo it in the back end (yuck).
>>> 
>>> - If the source is the start of an object, then this behaviour is
GC-hostile because it means that IR that contains a pointer to an object start
now only contains a pointer to the middle, requiring the GC to deal with inner
pointers.
>>> 
>>> It would be nice if we could have canonical forms such that if the
front end ensures that there are no inner pointers without pointers to the
object's start in the IR, the optimisers don't break this.
>>> 
>>> David
>>> 
>>> [1] Are canonical forms actually documented anywhere, or are they
simply undocumented implicit contracts?
>> I would say whatever form is currently generated by IR passes is
defined as canonical. It’s not easy to specify. At some points in the pipeline
(early and late) it’s fine to permit multiple forms of the same expression as
long as it’s canonical-enough for the downstream analysis.
>> 
>> If some pass is generating a suboptimal form, it’s good to question
whether it’s really necessary for any analysis. If not, we should change it.
Without a test case, I can’t say what issue you’re running into above.
> David, do you happen to have a test case on hand?  I know I've seen
this before, but my attempt to write out a quick example from memory failed.
I don't have one to hand - it's something I see in things with fairly
complex loop structures.  I'll try to find one next time I'm chasing
performance issues.

David

On Feb 18, 2014, at 12:58 PM, David Chisnall <David.Chisnall at
cl.cam.ac.uk> wrote:
> On 18 Feb 2014, at 19:51, Philip Reames <listmail at
philipreames.com> wrote:
> 
>> 
>> On 02/17/2014 02:53 PM, Andrew Trick wrote:
>>> On Feb 17, 2014, at 2:31 AM, David Chisnall <David.Chisnall at
cl.cam.ac.uk> wrote:
>>> 
>>>> On 15 Feb 2014, at 23:55, Andrew Trick <atrick at
apple.com> wrote:
>>>> 
>>>>> On Feb 14, 2014, at 5:18 PM, Philip Reames <listmail at
philipreames.com> wrote:
>>>>> 
>>>>>> RFC: GEP as canonical form for pointer addressing
>>>>>> 
>>>>>> I would like to propose that we designate GEPs as the
canonical form for pointer addressing in LLVM IR before CodeGenPrepare.
>>>>>> 
>>>>>> Corollaries
>>>>>> 1) It is legal for an optimizer to convert
inttoptr+arithmetic+inttoptr sequences to GEPs, but not vice versa.
>>>>>> 2) Input IR which does not contain inttoptr
instructions will never contain inttoptr instructions (before CodeGenPrepare.)
>>>>>> 
>>>>>> I've spoken with Nick Lewycky & Owen Anderson
offline at the last social.  On first reflection, both were okay with the
proposal, but I'd like broader buy-in and discussion.  Nick & Owen, if
I've accidentally misrepresented our discussion or you've had second
thoughts since, please speak up.
>>>>> FWIW, I think it would be nice if standard optimization
passes have this property of being well behaved with respect to pointer types,
and I don’t see a good reason for canonical IR passes to lose pointer types. I
also think it’s the only way to mix the optimization of pointer values with
precise GC. It seems that you just want LLVM developers to generally agree that
certain passes will be well behaved (you can disable any others). It may just be
a matter of documenting those passes. Ideally we could formalize this by
declaring a pass as pointer-safe and verifying. Can we easily verify that no
memory access is based on inttoptr?
>>>> Not directly related, but our canonical form for loops
involving pointers[1] turns a loop that contains a GEP with the loop induction
variable into a GEP with the increment inside the loop.  This has two annoying
properties for code generation:
>>>> 
>>>> - The GEP with the induction variable as the offset maps
cleanly to CPU addressing modes and so we generate better code if we don't
do this canonicalisation, and therefore end up trying to undo it in the back end
(yuck).
>>>> 
>>>> - If the source is the start of an object, then this behaviour
is GC-hostile because it means that IR that contains a pointer to an object
start now only contains a pointer to the middle, requiring the GC to deal with
inner pointers.
>>>> 
>>>> It would be nice if we could have canonical forms such that if
the front end ensures that there are no inner pointers without pointers to the
object's start in the IR, the optimisers don't break this.
>>>> 
>>>> David
>>>> 
>>>> [1] Are canonical forms actually documented anywhere, or are
they simply undocumented implicit contracts?
>>> I would say whatever form is currently generated by IR passes is
defined as canonical. It’s not easy to specify. At some points in the pipeline
(early and late) it’s fine to permit multiple forms of the same expression as
long as it’s canonical-enough for the downstream analysis.
>>> 
>>> If some pass is generating a suboptimal form, it’s good to question
whether it’s really necessary for any analysis. If not, we should change it.
Without a test case, I can’t say what issue you’re running into above.
>> David, do you happen to have a test case on hand?  I know I've seen
this before, but my attempt to write out a quick example from memory failed.
> 
> I don't have one to hand - it's something I see in things with
fairly complex loop structures.  I'll try to find one next time I'm
chasing performance issues.
If you’re running LSR, all bets are off. When Philip says he wants canonical IR
before CodeGenPrepare, I take that to mean anything scheduled in
TargetPassConfig::addIRPasses, including LSR, constant hoisting, etc.

-Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140218/ebeb13a0/attachment.html>