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.

-Andy

From: "Andrew Trick" <atrick@apple.com>
To: "llvmdev@cs.uiuc.edu Dev" <llvmdev@cs.uiuc.edu>
Cc: doerfert@cs.uni-saarland.de, "zinovy nis" <zinovy.nis@gmail.com>, "Hal Finkel" <hfinkel@anl.gov>, "Arnold
Schwaighofer" <aschwaighofer@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).

-Hal

@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

Making the metadata more stable sounds good to me.

No objections from my side.

> >> 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 ?

Best,
Hadi

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