[llvm-dev] Verify that we only get loop metadata on latches
Hal Finkel via llvm-dev
llvm-dev at lists.llvm.org
Fri Jul 6 06:13:11 PDT 2018
On 07/06/2018 06:50 AM, Björn Pettersson A wrote:
> 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.
My reading of Loop::getLoopID() is that it would miss the llvm.loop
metadata in the loop above (because it checks whether the terminator has
a successor which is the loop header, and if for.cond is the loop
header, then that it's true for that conditional branch).
Looks to me like the LangRef is correct, in that it matches what the
backend actually recognizes, and the test is wrong.
-Hal
>
> /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
>
--
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/ccfe33f0/attachment.html>
More information about the llvm-dev
mailing list