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

[Andrew Trick]

> On Oct 7, 2014, at 5:39 AM, hadi sadeghi <hasadegh at elis.ugent.be> wrote:
> 
> 
>>>>> 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.
>>>>> 
> 
> I have couple of questions regarding this proposal, does not it change
> llvm's standard Loop structure ? I guess some optimizations working around 
> standard loop structure. another issue could be that simplify-cfg might
> optimize out such an unconditional branch (I am not sure about it). 
> I was working around preserving loop metadata for while, our proposal was to
> attach loop metadata to both, back-edge and loop's phi nodes (phi nodes at
> the start of loop Header), since in SSA from, a loop can be identified by
> its phi nodes. this solution worked for us, but our benchmarks were limited
> to MPEG and H264. do you think this could be considered as a general solution ?

The proposal is that passes can convert a loop between these two canonical forms:

(1)
loop.body:
  ...
  br i1 %c, label %loop.tail, label %exit, !llvm.loop

exit:
  ret

(2)
loop.body:
  ...
  br i1 %c, label %loop.tail, label %exit, !llvm.loop

loop.tail:
  ; split critical edge
  br label %loop.body

exit:
  ret

without affecting loop metadata.

SplitCriticalEdges transforms from 1->2. SimplifyCFG transforms from 2->1.

It doesn’t change the form of the loop that any pass sees, just changes where a the pass needs to look for the metadata if the loop is already in form 2.

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