[llvm-dev] Verify that we only get loop metadata on latches
Björn Pettersson A via llvm-dev
llvm-dev at lists.llvm.org
Fri Jul 6 04:50:46 PDT 2018
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>
More information about the llvm-dev
mailing list