Split large basic blocks

Hi all,

we have few examples where we have very large basic blocks that increase the compilation time due to the DAG we build for scheduling.
I saw that in the past there was a suggestion to split basic blocks but it was not pushed to master.
(⚙ D44814 [CodeGenPrepare] Split huge basic blocks for faster compilation.)
is there an intention to do so?
one can add hook to each target to set the size, default can be no split.


Adding arbitrary size thresholds is a kludge. Have all avenues for increasing the compile time of large blocks really been explored?

I think there is a long tail of superlinear algorithms in SelectionDAG ISel that will always reoccur as long as we stick with the current framework. I think it would be reasonable to add this functionality under a flag. It’s reasonable for LLVM to say that superlinear algorithms are bugs that should be fixed, but it’s impractical to argue against adding a workaround like this given how common these kinds of issues are.

I agree with @rnk.

I can see both sides in this: the pragmatism of a workaround option, but also the need to address the root cause. For the latter, would it make sense to add some large-basic-block test cases to http://llvm-compile-time-tracker.com? @nikic

llvm-compile-time-tracker uses programs from the CTMark directory in llvm-test-suite, so that would be the place to add additional test cases. I think it would make sense to add an umbrella program for “pathological” cases there, where we can add .c files for individual problematic inputs encountered in the wild, to ensure that these don’t regress (or don’t regress much) in the future.

As to the topic of the thread, I agree that splitting blocks is a pragmatic solution to the problem. I think it may not catch all cases though – I vaguely remember some bad cases involving stores to huge aggregates, which only get expanded into a large number of scalar stores in SDAGBuilder (and then go through store merging, which is one of the worst super-linearity offenders in SDAG).