This is an archive of the discontinued LLVM Phabricator instance.

[LoopUnrollAndJam] Avoid repeated instructions for UAJ analysis
ClosedPublic

Authored by dancgr on Feb 24 2021, 11:54 AM.

Details

Summary

Avoid visiting repeated instructions for processHeaderPhiOperands as it can cause a scenario of endless loop. Test case is attached and can be ran with opt -basic-aa -tbaa -loop-unroll-and-jam -allow-unroll-and-jam -unroll-and-jam-count=4.

Diff Detail

Event Timeline

dancgr created this revision.Feb 24 2021, 11:54 AM
dancgr requested review of this revision.Feb 24 2021, 11:54 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 24 2021, 11:54 AM

Am I correct that the old code was accidentally O(2^n) :(

And this cuts that down to something much more reasonable?

llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
161

Formatting is a bit off here.

llvm/test/Transforms/LoopUnrollAndJam/unroll-and-jam-many-instr.ll
2

This needs RUN: lines and some basic CHECKS, maybe with a comment explaining the test for bonus points.

If it requires the aarch64 backend (which it might not) then it would need to be in llvm/test/Transforms/LoopUnrollAndJam/AArch64 directory, so it only runs when the compiler is built with aarch64 as a registered target. It can likely remove the aarch64 though, and rely on the datalayout and command line args.

It might be possible to clean this up quite a bit. My understanding is that for.cond13.preheader (the aft block) needs to contain a lot of instructions to show the timeout. The main() and attributes can often be removed.

@dmgreen I think so. The code is indeed exponential. Adding this check will avoid the exponential case, but we will be visiting each instruction both ways, we just avoid visiting repeated ones. IMO it won't affect the analysis result.

llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
161

Will fix that!

llvm/test/Transforms/LoopUnrollAndJam/unroll-and-jam-many-instr.ll
2

Yes, I will update this code. I doesn't necessarily needs to be for AArch64. I will also add a RUN line with some basic checks.

Good point, I will cleanup all the code that is not necessary for it.

dancgr updated this revision to Diff 335612.Apr 6 2021, 11:39 AM

Fixed formatting and add test run line

@dmgreen I fixed the issues that you pointed out. This patch prevents the test case from getting stuck on the exponential explosion of the algorithm. Could you review it? Thanks!

dmgreen accepted this revision.Apr 7 2021, 2:40 AM

LGTM, so long as the test is cleaned up a little

llvm/test/Transforms/LoopUnrollAndJam/unroll-and-jam-many-instr.ll
11

Can remove these Function Attrs comment.

22

Can remove dso_local and local_unnamed_addr #0

374

You can remove this main function.

379

Often a lot of these can be removed, so long as the tbaa metadata is also removed from the load/store instructions.

This revision is now accepted and ready to land.Apr 7 2021, 2:40 AM
dancgr updated this revision to Diff 337798.Apr 15 2021, 9:44 AM

Updated last comments.

This revision was landed with ongoing or failed builds.Apr 15 2021, 10:05 AM
This revision was automatically updated to reflect the committed changes.