[SLP] Remove cap on schedule window size
authorPhilip Reames <listmail@philipreames.com>
Wed, 23 Feb 2022 04:00:43 +0000 (20:00 -0800)
committerPhilip Reames <listmail@philipreames.com>
Wed, 23 Feb 2022 16:27:45 +0000 (08:27 -0800)
commit6adf4b039e095224edbbecda5972e5e3353b53b6
treea82e04f76caacf1dca22a84483c4718ee94050d1
parent2f906683ed14668ceed1f85922789abffd8429fd
[SLP] Remove cap on schedule window size

This cap was first added in 848c1aa45 (back in 2015).  Per the original commit message, the purpose was to avoid a compile time explosion in long basic blocks.  The algorithmic problem in scheduling has now been fixed in 0539a26d.

In the meantime, the code has rotten fairly badly.  Some intermediate refactoring caused the size to only be incremented if *both* iterators advance in the window search.  This causes the size to be badly undercounted when near one end of a basic block.  We no longer have any test which exercises the logic in an intentional way; there's one test which differs with this change, but the changes appear fairly orthoganol to the purpose of the test file.

Unfortunately, we no longer have the original motivating example, so it's possible that it also hits some other issue.  I tested locally with a large example, but even at it's worst, that one doesn't demonstrate anything too extreme even without the algorithmic fix.  It's clearly faster with, but only by ~20% which doesn't seem in line with the original commit message.   If regressions with this patch are seen, please file a bug and I'll try to fix any other algorithmic problems which fall out.
llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
llvm/test/Transforms/SLPVectorizer/AArch64/gather-root.ll
llvm/test/Transforms/SLPVectorizer/X86/crash_exceed_scheduling.ll
llvm/test/Transforms/SLPVectorizer/X86/extract-shuffle-inseltpoison.ll
llvm/test/Transforms/SLPVectorizer/X86/extract-shuffle.ll
llvm/test/Transforms/SLPVectorizer/X86/schedule_budget.ll