[LLVMdev] llvm.loop metadata placement and critical edge splitting

[Tobias Grosser]

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