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.
Details
Details
Diff Detail
Diff Detail
- Repository
- rG LLVM Github Monorepo
Unit Tests
Unit Tests
Event Timeline
Comment Actions
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 | ||
| 1 | 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. | |
Comment Actions
@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 | ||
| 1 | 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. | |
Comment Actions
@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!
Comment Actions
LGTM, so long as the test is cleaned up a little
| llvm/test/Transforms/LoopUnrollAndJam/unroll-and-jam-many-instr.ll | ||
|---|---|---|
| 12 | Can remove these Function Attrs comment. | |
| 23 | Can remove dso_local and local_unnamed_addr #0 | |
| 375 | You can remove this main function. | |
| 380 | Often a lot of these can be removed, so long as the tbaa metadata is also removed from the load/store instructions. | |
clang-format: please reformat the code