Björn Pettersson A via llvm-dev
2018-Jul-06 08:57 UTC
[llvm-dev] Verify that we only get loop metadata on latches
In https://bugs.llvm.org/show_bug.cgi?id=38011 (see also
https://reviews.llvm.org/D48721) a problem was revealed related to llvm.loop
metadata.
The fault was that clang added the !llvm.loop metadata to branches outside of
the loop (not only the loop latch). That was not handled properly by some opt
passes (simplifying cfg) since it ended up merging branch instructions with
different !llvm.loop annotations (and then it kept the wrong metadata on the
branch):
```
!2 = distinct !{!2, !3}
!3 = !{!"llvm.loop.unroll.count", i32 3}
!8 = distinct !{!8, !9}
!9 = !{!"llvm.loop.unroll.count", i32 5}
*** IR Dump After Combine redundant instructions ***
; Function Attrs: nounwind
define i32 @test(i32* %a, i32 %n) {
entry:
br label %do.body, !llvm.loop !2
do.body: ; preds = %do.body, %entry
...
br i1 %cmp, label %do.body, label %do.end, !llvm.loop !2
do.end: ; preds = %do.body
br label %do.body6, !llvm.loop !8
do.body6: ; preds = %do.body6, %do.end
...
br i1 %cmp17, label %do.body6, label %do.end18, !llvm.loop !8
do.end18: ; preds = %do.body6
ret i32 %add14
}
*** IR Dump After Simplify the CFG ***
; Function Attrs: nounwind
define i32 @test(i32* %a, i32 %n) local_unnamed_addr #0 {
entry:
br label %do.body, !llvm.loop !2
do.body: ; preds = %do.body, %entry
...
br i1 %cmp, label %do.body, label %do.body6, !llvm.loop !8
do.body6: ; preds = %do.body, %do.body6
%i.1 = phi i32 [ %inc15, %do.body6 ], [ 0, %do.body ]
...
br i1 %cmp17, label %do.body6, label %do.end18, !llvm.loop !8
do.end18: ; preds = %do.body6
ret i32 %add14
}
```
As seen above, when do.end is eliminated the metadata on the backward branch in
do.body is changed from !2 to !8 due to the misplaced metadata on the branch in
do.end.
D48721 is solving the current problem in clang, but I was thinking that it would
be nice to do some improvements in opt as well. Getting the wrong metadata on a
loop is probably bad.
I assume the idea of having the loop metadata on latches is that a latch
can't be shared between different loops (right?).
Wouldn't it be nice to simply forbid having loop metadata on branches that
aren't latches, by adding such checks in the Verifier?
I played around a little bit with teaching the IR Verifier in opt to check that
!llvm.loop only is put in loop latches.
Something like this might do the trick, when added to Verifier::visitInstruction
in lib/IR/Verifier.cpp:
```
#include "llvm/Analysis/LoopInfo.h"
if (I.getMetadata(LLVMContext::MD_loop)) {
// FIXME: Is SwitchInst also allowed?
Assert(isa<BranchInst>(I), "llvm.loop only expected on
branches", &I);
LoopInfo LI;
LI.analyze(DT);
Loop* L = LI.getLoopFor(BB);
Assert(L, "llvm.loop not in a loop", &I);
Assert(L->isLoopLatch(BB), "llvm.loop not in a latch", &I);
}
```
Note that the above just was a simple test. For example, we do not want to
reinitialize LoopInfo for each found occurence of !llvm.loop if doing this
properly.
Also note that the above only checks that the branch is in a latch block, not
that the branch itself is the latch.
Another problem is that the Verifier is used by lots of tools that currently do
not link with LoopInfo from the Analysis code module.
My question are:
* Is it a good idea to detect misplaced llvm.loop metadata or should we
protect us from faulty rewrites in some other way?
* Is the Verifier a good place for this kind of checks, or is there a better
place (such as the LoopVerifier pass, but I guess that is not always run before
CFG simplification etc)?
* Would it be correct to use LoopInfo, or can we do the checks in some other
way?
/Björn
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180706/34d52ecf/attachment.html>
Hal Finkel via llvm-dev
2018-Jul-06 11:07 UTC
[llvm-dev] Verify that we only get loop metadata on latches
On 07/06/2018 03:57 AM, Björn Pettersson A via llvm-dev wrote:> > In https://bugs.llvm.org/show_bug.cgi?id=38011 > <https://bugs.llvm.org/show_bug.cgi?id=38011> (see also > https://reviews.llvm.org/D48721) a problem was revealed related to > llvm.loop metadata. > > > > The fault was that clang added the !llvm.loop metadata to branches > outside of the loop (not only the loop latch). That was not handled > properly by some opt passes (simplifying cfg) since it ended up > merging branch instructions with different !llvm.loop annotations (and > then it kept the wrong metadata on the branch): > > > > ``` > > !2 = distinct !{!2, !3} > > !3 = !{!"llvm.loop.unroll.count", i32 3} > > !8 = distinct !{!8, !9} > > !9 = !{!"llvm.loop.unroll.count", i32 5} > > *** IR Dump After Combine redundant instructions *** > > ; Function Attrs: nounwind > > define i32 @test(i32* %a, i32 %n) { > > entry: > > br label %do.body, !llvm.loop !2 > > > > do.body: ; preds = %do.body, > %entry > > … > > br i1 %cmp, label %do.body, label %do.end, !llvm.loop !2 > > > > do.end: ; preds = %do.body > > br label %do.body6, !llvm.loop !8 > > > > do.body6: ; preds = %do.body6, > %do.end > > … > > br i1 %cmp17, label %do.body6, label %do.end18, !llvm.loop !8 > > > > do.end18: ; preds = %do.body6 > > ret i32 %add14 > > } > > *** IR Dump After Simplify the CFG *** > > ; Function Attrs: nounwind > > define i32 @test(i32* %a, i32 %n) local_unnamed_addr #0 { > > entry: > > br label %do.body, !llvm.loop !2 > > > > do.body: ; preds = %do.body, > %entry > > … > > br i1 %cmp, label %do.body, label %do.body6, !llvm.loop !8 > > > > do.body6: ; preds = %do.body, > %do.body6 > > %i.1 = phi i32 [ %inc15, %do.body6 ], [ 0, %do.body ] > > … > > br i1 %cmp17, label %do.body6, label %do.end18, !llvm.loop !8 > > > > do.end18: ; preds = %do.body6 > > ret i32 %add14 > > } > > ``` > > > > As seen above, when do.end is eliminated the metadata on the backward > branch in do.body is changed from !2 to !8 due to the misplaced > metadata on the branch in do.end. > > > > D48721 is solving the current problem in clang, but I was thinking > that it would be nice to do some improvements in opt as well. Getting > the wrong metadata on a loop is probably bad. > > I assume the idea of having the loop metadata on latches is that a > latch can’t be shared between different loops (right?). > > Wouldn’t it be nice to simply forbid having loop metadata on branches > that aren’t latches, by adding such checks in the Verifier? >I don't know. The existing rationale for not checking this, as I recall, is to allow for non-loop-aware CFG restructuring operations to operate on loops without worrying about what to do with this metadata. This is consistent with our general philosophy of allowing non-loop-aware CFG restructuring in general (although I'll point out that SimplifyCFG, for example, has been made effectively loop aware in order to avoid disturbing canonical loop forms). I can certainly see an argument for not allowing this, and that is that, like for instructions, if a pass moves or changes an instruction then it must clear all metadata it does not know to still be valid, and for a transformation changing the CFG, that would apply to the branch instructions it modified. I'll note, however, that it's possible to change a latch block for a canonical loop into one for a non-canonical loop without touching the latch itself. Imagine a transformation that examined a block with many predecessors (this happens to be a loop header and the predecessors are the pre-header and several different latch blocks, but it doesn't know that), and introduces a new block and inserts it into the CFG in between this block and most, but not all, of its predecessors. Thus, I don't think that you can use LoopInfo to verify the metadata. You'll need to collect backedges and verify that the metadata is on such an edge. We have a function, FindFunctionBackedges, for this purpose (this is what is used by SimplifyCFGPass to find backedges for its pseudo-loop-awareness). -Hal> > > I played around a little bit with teaching the IR Verifier in opt to > check that !llvm.loop only is put in loop latches. > > Something like this might do the trick, when added to > Verifier::visitInstruction in lib/IR/Verifier.cpp: > > > > ``` > > #include "llvm/Analysis/LoopInfo.h" > > > > if (I.getMetadata(LLVMContext::MD_loop)) { > > // FIXME: Is SwitchInst also allowed? > > Assert(isa<BranchInst>(I), "llvm.loop only expected on branches", &I); > > LoopInfo LI; > > LI.analyze(DT); > > Loop* L = LI.getLoopFor(BB); > > Assert(L, "llvm.loop not in a loop", &I); > > Assert(L->isLoopLatch(BB), "llvm.loop not in a latch", &I); > > } > > ``` > > > > Note that the above just was a simple test. For example, we do not > want to reinitialize LoopInfo for each found occurence of !llvm.loop > if doing this properly. > > Also note that the above only checks that the branch is in a latch > block, not that the branch itself is the latch. > > Another problem is that the Verifier is used by lots of tools that > currently do not link with LoopInfo from the Analysis code module. > > > > My question are: > > * Is it a good idea to detect misplaced llvm.loop metadata or should > we protect us from faulty rewrites in some other way? > * Is the Verifier a good place for this kind of checks, or is there > a better place (such as the LoopVerifier pass, but I guess that is > not always run before CFG simplification etc)? > * Would it be correct to use LoopInfo, or can we do the checks in > some other way? > > > > /Björn > > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-- Hal Finkel Lead, Compiler Technology and Programming Languages Leadership Computing Facility Argonne National Laboratory -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180706/7bf7f8e6/attachment-0001.html>
Björn Pettersson A via llvm-dev
2018-Jul-06 11:50 UTC
[llvm-dev] Verify that we only get loop metadata on latches
I tried using FindFunctionBackedges first, before using LoopInfo.
But then the verifier would complain when having a for-loop like this:
define void @_Z28loop_with_vectorize_metadatav() {
entry:
%i = alloca i32, align 4
store i32 0, i32* %i, align 4
br label %for.cond
for.cond: ; preds = %for.inc, %entry
%0 = load i32, i32* %i, align 4
%cmp = icmp slt i32 %0, 16
br i1 %cmp, label %for.body, label %for.end, !llvm.loop !0
for.body: ; preds = %for.cond
br label %for.inc
for.inc: ; preds = %for.body
%1 = load i32, i32* %i, align 4
%inc = add nsw i32 %1, 1
store i32 %inc, i32* %i, align 4
br label %for.cond
for.end: ; preds = %for.cond
ret void
}
The metadata is on the branch in the latch (the for.cond block), while the
backedge is the branch in the for.inc block.
The LangRef says "Currently, loop metadata is implemented as metadata
attached to the branch instruction in the loop latch block.",
but when I tried generating code from a for-loop with latest clang on trunk the
metadata is put on the backedge. So maybe it is a fault in the LangRef?
The code above is from test/Bitcode/upgrade-loop-metadata.ll.bc. But if the
LangRef is wrong, then I assume test case is wrong.
/Björn
From: Hal Finkel <hfinkel at anl.gov>
Sent: den 6 juli 2018 13:07
To: Björn Pettersson A <bjorn.a.pettersson at ericsson.com>; llvm-dev at
lists.llvm.org
Cc: deepak2427 at gmail.com
Subject: Re: [llvm-dev] Verify that we only get loop metadata on latches
On 07/06/2018 03:57 AM, Björn Pettersson A via llvm-dev wrote:
In https://bugs.llvm.org/show_bug.cgi?id=38011 (see also
https://reviews.llvm.org/D48721) a problem was revealed related to llvm.loop
metadata.
The fault was that clang added the !llvm.loop metadata to branches outside of
the loop (not only the loop latch). That was not handled properly by some opt
passes (simplifying cfg) since it ended up merging branch instructions with
different !llvm.loop annotations (and then it kept the wrong metadata on the
branch):
```
!2 = distinct !{!2, !3}
!3 = !{!"llvm.loop.unroll.count", i32 3}
!8 = distinct !{!8, !9}
!9 = !{!"llvm.loop.unroll.count", i32 5}
*** IR Dump After Combine redundant instructions ***
; Function Attrs: nounwind
define i32 @test(i32* %a, i32 %n) {
entry:
br label %do.body, !llvm.loop !2
do.body: ; preds = %do.body, %entry
...
br i1 %cmp, label %do.body, label %do.end, !llvm.loop !2
do.end: ; preds = %do.body
br label %do.body6, !llvm.loop !8
do.body6: ; preds = %do.body6, %do.end
...
br i1 %cmp17, label %do.body6, label %do.end18, !llvm.loop !8
do.end18: ; preds = %do.body6
ret i32 %add14
}
*** IR Dump After Simplify the CFG ***
; Function Attrs: nounwind
define i32 @test(i32* %a, i32 %n) local_unnamed_addr #0 {
entry:
br label %do.body, !llvm.loop !2
do.body: ; preds = %do.body, %entry
...
br i1 %cmp, label %do.body, label %do.body6, !llvm.loop !8
do.body6: ; preds = %do.body, %do.body6
%i.1 = phi i32 [ %inc15, %do.body6 ], [ 0, %do.body ]
...
br i1 %cmp17, label %do.body6, label %do.end18, !llvm.loop !8
do.end18: ; preds = %do.body6
ret i32 %add14
}
```
As seen above, when do.end is eliminated the metadata on the backward branch in
do.body is changed from !2 to !8 due to the misplaced metadata on the branch in
do.end.
D48721 is solving the current problem in clang, but I was thinking that it would
be nice to do some improvements in opt as well. Getting the wrong metadata on a
loop is probably bad.
I assume the idea of having the loop metadata on latches is that a latch
can't be shared between different loops (right?).
Wouldn't it be nice to simply forbid having loop metadata on branches that
aren't latches, by adding such checks in the Verifier?
I don't know. The existing rationale for not checking this, as I recall, is
to allow for non-loop-aware CFG restructuring operations to operate on loops
without worrying about what to do with this metadata. This is consistent with
our general philosophy of allowing non-loop-aware CFG restructuring in general
(although I'll point out that SimplifyCFG, for example, has been made
effectively loop aware in order to avoid disturbing canonical loop forms).
I can certainly see an argument for not allowing this, and that is that, like
for instructions, if a pass moves or changes an instruction then it must clear
all metadata it does not know to still be valid, and for a transformation
changing the CFG, that would apply to the branch instructions it modified.
I'll note, however, that it's possible to change a latch block for a
canonical loop into one for a non-canonical loop without touching the latch
itself. Imagine a transformation that examined a block with many predecessors
(this happens to be a loop header and the predecessors are the pre-header and
several different latch blocks, but it doesn't know that), and introduces a
new block and inserts it into the CFG in between this block and most, but not
all, of its predecessors. Thus, I don't think that you can use LoopInfo to
verify the metadata. You'll need to collect backedges and verify that the
metadata is on such an edge. We have a function, FindFunctionBackedges, for this
purpose (this is what is used by SimplifyCFGPass to find backedges for its
pseudo-loop-awareness).
-Hal
I played around a little bit with teaching the IR Verifier in opt to check that
!llvm.loop only is put in loop latches.
Something like this might do the trick, when added to Verifier::visitInstruction
in lib/IR/Verifier.cpp:
```
#include "llvm/Analysis/LoopInfo.h"
if (I.getMetadata(LLVMContext::MD_loop)) {
// FIXME: Is SwitchInst also allowed?
Assert(isa<BranchInst>(I), "llvm.loop only expected on
branches", &I);
LoopInfo LI;
LI.analyze(DT);
Loop* L = LI.getLoopFor(BB);
Assert(L, "llvm.loop not in a loop", &I);
Assert(L->isLoopLatch(BB), "llvm.loop not in a latch", &I);
}
```
Note that the above just was a simple test. For example, we do not want to
reinitialize LoopInfo for each found occurence of !llvm.loop if doing this
properly.
Also note that the above only checks that the branch is in a latch block, not
that the branch itself is the latch.
Another problem is that the Verifier is used by lots of tools that currently do
not link with LoopInfo from the Analysis code module.
My question are:
- Is it a good idea to detect misplaced llvm.loop metadata or should we
protect us from faulty rewrites in some other way?
- Is the Verifier a good place for this kind of checks, or is there a
better place (such as the LoopVerifier pass, but I guess that is not always run
before CFG simplification etc)?
- Would it be correct to use LoopInfo, or can we do the checks in some
other way?
/Björn
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180706/41578e63/attachment.html>