llvm dev - Oct 2014 - [LLVMdev] llvm.loop metadata placement and critical edge splitting

On 06/10/2014 23:56, Hal Finkel wrote:
> ----- Original Message -----
>> From: "Andrew Trick" <atrick at apple.com>
>> To: "llvmdev at cs.uiuc.edu Dev" <llvmdev at
cs.uiuc.edu>
>> Cc: doerfert at cs.uni-saarland.de, "zinovy nis"
<zinovy.nis at gmail.com>, "Hal Finkel" <hfinkel at
anl.gov>, "Arnold
>> Schwaighofer" <aschwaighofer at apple.com>
>> Sent: Monday, October 6, 2014 12:55:11 PM
>> Subject: llvm.loop metadata placement and critical edge splitting
>>
>> While reviewing a fix for maintaining loop metadata
>> (http://reviews.llvm.org/D5539) I noticed that we make a strict
>> assumption about the metadata being attached to the branch that is
>> an immediate predecessor of the loop header. This does not work well
>> with LLVM's approach of lazy critical edge splitting. I've
proposed
>> working around this with heroics inside the critical edges splitting
>> utility, but feel that the workaround is really unnecessary because
>> the design could be fixed more easily. I was not involved in the
>> original design discussion for llvm.loop metadata, so I want to get
>> feedback before proposing a direction.
>>
>> My question is: Why can't we define requirements of loop metadata
>> such that *critical edge splitting does not invalidate loop
>> metadata*.
>>
>> I think fixing this may be an easy change to LoopInfo get/setLoopID.
>> The rule would be simple, if the loop back branch is unconditional,
>> and it has a single predecessor, the metadata is expected on the
>> predecessaor's conditional branch:
>>
>> loop.body:
>>    ...
>>    br i1 %c, label %loop.tail, label %exit, !llvm.loop
>>
>> loop.tail:
>>    ...
>>    br label %loop.body
>>
>> exit:
>>    ret
>>
>> If the loop tail does not have a single predecessor (complex control
>> flow occurs after the loop test), then the metadata can still be
>> placed on the unconditional branch. Either way, we don't need to
>> worry about edge splitting. Only a signficant loop restructuring
>> will invalidate the metadata.
>>
>> I don't think any change is necessary when clang emits a loop with
an
>> unconditional backedge, but someone will want to verify with some
>> test cases. If a change is needed it should also be easy.
>>
>> With that design change we can remove any current workarounds from
>> SplitCriticalEdge and simply preserve loop metadata, which remains
>> valid by definition.
>
> I think this makes sense. cc'ing the folks who did the OpenMP codegen
work in case they have an opinion. Also, maybe the polly and/or POCL folks have
an opinion (not sure exactly who to ask for those).
 From my side, this makes a lot of sense.

@Johannes, what do you think?

Cheers,
Tobias

I'm happy with any representation that works for optimizer. I can prepare a
patch for clang to update the 'omp simd' and 'clang loop'
CodeGen.
We do not use LoopInfo in front-end, but it's no problem to go to the
block's single predecessor and attach the metadata there.

Regards,
Alexander

-----Original Message-----
From: Tobias Grosser [mailto:tobias at grosser.es] 
Sent: Tuesday, October 07, 2014 11:22 AM
To: Hal Finkel; Andrew Trick
Cc: doerfert at cs.uni-saarland.de; zinovy nis; Arnold Schwaighofer; llvmdev at
cs.uiuc.edu Dev; Bataev, Alexey; Musman, Alexander; Erik Schnetter
Subject: Re: llvm.loop metadata placement and critical edge splitting

On 06/10/2014 23:56, Hal Finkel wrote:
> ----- Original Message -----
>> From: "Andrew Trick" <atrick at apple.com>
>> To: "llvmdev at cs.uiuc.edu Dev" <llvmdev at
cs.uiuc.edu>
>> Cc: doerfert at cs.uni-saarland.de, "zinovy nis"
<zinovy.nis at gmail.com>,
>> "Hal Finkel" <hfinkel at anl.gov>, "Arnold
Schwaighofer"
>> <aschwaighofer at apple.com>
>> Sent: Monday, October 6, 2014 12:55:11 PM
>> Subject: llvm.loop metadata placement and critical edge splitting
>>
>> While reviewing a fix for maintaining loop metadata
>> (http://reviews.llvm.org/D5539) I noticed that we make a strict 
>> assumption about the metadata being attached to the branch that is an 
>> immediate predecessor of the loop header. This does not work well 
>> with LLVM's approach of lazy critical edge splitting. I've
proposed
>> working around this with heroics inside the critical edges splitting 
>> utility, but feel that the workaround is really unnecessary because 
>> the design could be fixed more easily. I was not involved in the 
>> original design discussion for llvm.loop metadata, so I want to get 
>> feedback before proposing a direction.
>>
>> My question is: Why can't we define requirements of loop metadata 
>> such that *critical edge splitting does not invalidate loop 
>> metadata*.
>>
>> I think fixing this may be an easy change to LoopInfo get/setLoopID.
>> The rule would be simple, if the loop back branch is unconditional, 
>> and it has a single predecessor, the metadata is expected on the 
>> predecessaor's conditional branch:
>>
>> loop.body:
>>    ...
>>    br i1 %c, label %loop.tail, label %exit, !llvm.loop
>>
>> loop.tail:
>>    ...
>>    br label %loop.body
>>
>> exit:
>>    ret
>>
>> If the loop tail does not have a single predecessor (complex control 
>> flow occurs after the loop test), then the metadata can still be 
>> placed on the unconditional branch. Either way, we don't need to 
>> worry about edge splitting. Only a signficant loop restructuring will 
>> invalidate the metadata.
>>
>> I don't think any change is necessary when clang emits a loop with
an
>> unconditional backedge, but someone will want to verify with some 
>> test cases. If a change is needed it should also be easy.
>>
>> With that design change we can remove any current workarounds from 
>> SplitCriticalEdge and simply preserve loop metadata, which remains 
>> valid by definition.
>
> I think this makes sense. cc'ing the folks who did the OpenMP codegen
work in case they have an opinion. Also, maybe the polly and/or POCL folks have
an opinion (not sure exactly who to ask for those).
 From my side, this makes a lot of sense.

@Johannes, what do you think?

Cheers,
Tobias

--------------------------------------------------------------------
Closed Joint Stock Company Intel A/O
Registered legal address: Krylatsky Hills Business Park, 
17 Krylatskaya Str., Bldg 4, Moscow 121614, 
Russian Federation

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.

Making the metadata more stable sounds good to me.

No objections from my side.

On 10/07, Musman, Alexander wrote:
> I'm happy with any representation that works for optimizer. I can
prepare a patch for clang to update the 'omp simd' and 'clang
loop' CodeGen.
> We do not use LoopInfo in front-end, but it's no problem to go to the
block's single predecessor and attach the metadata there.
> 
> Regards,
> Alexander
> 
> -----Original Message-----
> From: Tobias Grosser [mailto:tobias at grosser.es] 
> Sent: Tuesday, October 07, 2014 11:22 AM
> To: Hal Finkel; Andrew Trick
> Cc: doerfert at cs.uni-saarland.de; zinovy nis; Arnold Schwaighofer;
llvmdev at cs.uiuc.edu Dev; Bataev, Alexey; Musman, Alexander; Erik Schnetter
> Subject: Re: llvm.loop metadata placement and critical edge splitting
> 
> On 06/10/2014 23:56, Hal Finkel wrote:
> > ----- Original Message -----
> >> From: "Andrew Trick" <atrick at apple.com>
> >> To: "llvmdev at cs.uiuc.edu Dev" <llvmdev at
cs.uiuc.edu>
> >> Cc: doerfert at cs.uni-saarland.de, "zinovy nis"
<zinovy.nis at gmail.com>,
> >> "Hal Finkel" <hfinkel at anl.gov>, "Arnold
Schwaighofer"
> >> <aschwaighofer at apple.com>
> >> Sent: Monday, October 6, 2014 12:55:11 PM
> >> Subject: llvm.loop metadata placement and critical edge splitting
> >>
> >> While reviewing a fix for maintaining loop metadata
> >> (http://reviews.llvm.org/D5539) I noticed that we make a strict 
> >> assumption about the metadata being attached to the branch that is
an
> >> immediate predecessor of the loop header. This does not work well 
> >> with LLVM's approach of lazy critical edge splitting. I've
proposed
> >> working around this with heroics inside the critical edges
splitting
> >> utility, but feel that the workaround is really unnecessary
because
> >> the design could be fixed more easily. I was not involved in the 
> >> original design discussion for llvm.loop metadata, so I want to
get
> >> feedback before proposing a direction.
> >>
> >> My question is: Why can't we define requirements of loop
metadata
> >> such that *critical edge splitting does not invalidate loop 
> >> metadata*.
> >>
> >> I think fixing this may be an easy change to LoopInfo
get/setLoopID.
> >> The rule would be simple, if the loop back branch is
unconditional,
> >> and it has a single predecessor, the metadata is expected on the 
> >> predecessaor's conditional branch:
> >>
> >> loop.body:
> >>    ...
> >>    br i1 %c, label %loop.tail, label %exit, !llvm.loop
> >>
> >> loop.tail:
> >>    ...
> >>    br label %loop.body
> >>
> >> exit:
> >>    ret
> >>
> >> If the loop tail does not have a single predecessor (complex
control
> >> flow occurs after the loop test), then the metadata can still be 
> >> placed on the unconditional branch. Either way, we don't need
to
> >> worry about edge splitting. Only a signficant loop restructuring
will
> >> invalidate the metadata.
> >>
> >> I don't think any change is necessary when clang emits a loop
with an
> >> unconditional backedge, but someone will want to verify with some 
> >> test cases. If a change is needed it should also be easy.
> >>
> >> With that design change we can remove any current workarounds from
> >> SplitCriticalEdge and simply preserve loop metadata, which remains
> >> valid by definition.
> >
> > I think this makes sense. cc'ing the folks who did the OpenMP
codegen work in case they have an opinion. Also, maybe the polly and/or POCL
folks have an opinion (not sure exactly who to ask for those).
> 
>  From my side, this makes a lot of sense.
> 
> @Johannes, what do you think?
> 
> Cheers,
> Tobias
> 
> --------------------------------------------------------------------
> Closed Joint Stock Company Intel A/O
> Registered legal address: Krylatsky Hills Business Park, 
> 17 Krylatskaya Str., Bldg 4, Moscow 121614, 
> Russian Federation
> 
> This e-mail and any attachments may contain confidential material for
> the sole use of the intended recipient(s). Any review or distribution
> by others is strictly prohibited. If you are not the intended
> recipient, please contact the sender and delete all copies.
-- 

Johannes Doerfert
Researcher / PhD Student

Compiler Design Lab (Prof. Hack)
Saarland University, Computer Science
Building E1.3, Room 4.26

Tel. +49 (0)681 302-57521 : doerfert at cs.uni-saarland.de
Fax. +49 (0)681 302-3065  : http://www.cdl.uni-saarland.de/people/doerfert
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 213 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20141007/60b9e215/attachment.sig>