[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 04:07:06 PDT 2018
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>
More information about the llvm-dev
mailing list