Schedule Hot Cold Splitting pass after most optimization passes

[hiraditya]

Summary

In the new+old pass manager, hot cold splitting was schedule too early.
Thanks to Vedant for pointing this out.

[vsk]

Could you add a test for this similar to 'test/Other/opt-Os-pipeline.ll'?

[sebpop]

ok

[vsk]

Looks great, thanks!

[peter.smith]

It looks like the test is failing on some of the Arm buildbots. In particular some of them don't have the X86 backend: http://lab.llvm.org:8011/builders/clang-cmake-armv7-quick/builds/4611 so it looks like it is most likely missing a REQUIRES: x86. Can you take a look?

[vsk]

In D53437#1270521, @peter.smith wrote:

It looks like the test is failing on some of the Arm buildbots. In particular some of them don't have the X86 backend: http://lab.llvm.org:8011/builders/clang-cmake-armv7-quick/builds/4611 so it looks like it is most likely missing a REQUIRES: x86. Can you take a look?

@peter.smith @hiraditya r344919 should address this.

[tejohnson]

Note that this addresses in the old PM one issue I found when enabling splitting with ThinLTO, but exposes some related issues. In the old location, which was before the early return when PrepareForThinLTO==true around line 590, we were doing two rounds of splitting: one during the compile step, and a second later in the ThinLTO backends. I saw that we split an already split function (see below for more info). But I notice that there are still a couple issues:

1. In the old PM, we will still do splitting early (during the compile step) for regular LTO, which doesn't return early from this routine. You should presumably guard the adding of the hot cold split pass by "if (!PrepareForLTO)"
2. Once you've done 1), regular LTO will no longer perform any splitting, since its backend doesn't invoke populateModulePassManager. You can fix this by adding your hot cold splitting pass to an equivalent location in addLTOOptimizationPasses(), which is invoked only in the regular LTO backend.
3. In the new PM, the move of the hot cold splitting pass does not fix the issue for ThinLTO. The reason is that there is no early exit from buildModuleSimplificationPipeline. To fix, you can guard the hot cold split pass by "Phase != ThinLTOPhase::PreLink".
4. In the new PM, regular LTO invokes buildModuleSimplificationPipeline in the compile step, but without any extra info to indicate that it is an LTO compile. So something else will need to be done to suppress the hot cold splitting from happening early for regular LTO (e.g. pass down a new flag?).
5. Once 4) is done, regular LTO will no longer perform any splitting in the new PM since its backend doesn't invoke buildModuleSimplificationPipeline. To fix, you will want to add the hot cold split pass to an appropriate place in buildLTODefaultPipeline().

This all assumes that you want to only do splitting in the *LTO backends (i.e. after cross module inlining). What are the tradeoffs of doing the splitting before/after inlining? One advantage of doing the splitting earlier for ThinLTO, in the compile step, is that it would reduce the size of the functions during the import analysis, and we might import more hot (split) functions. But then the splitting would be happening before the cross-module inlining in the backends.

Regarding what I am currently seeing with two rounds of splitting with ThinLTO: I noticed that the second round of splitting in the ThinLTO backends was resplitting an already split function - specifically, the cold outlined function was getting split again, which doesn't make a lot of sense since presumably the edge weights were all cold. Note this is after r344558 (the fix for the issue of outlining the whole function). Why would that happen?

[vsk]

Thanks for your notes @tejohnson.

In D53437#1271156, @tejohnson wrote:

Note that this addresses in the old PM one issue I found when enabling splitting with ThinLTO, but exposes some related issues. In the old location, which was before the early return when PrepareForThinLTO==true around line 590, we were doing two rounds of splitting: one during the compile step, and a second later in the ThinLTO backends. I saw that we split an already split function (see below for more info). But I notice that there are still a couple issues:

1. In the old PM, we will still do splitting early (during the compile step) for regular LTO, which doesn't return early from this routine. You should presumably guard the adding of the hot cold split pass by "if (!PrepareForLTO)"
2. Once you've done 1), regular LTO will no longer perform any splitting, since its backend doesn't invoke populateModulePassManager. You can fix this by adding your hot cold splitting pass to an equivalent location in addLTOOptimizationPasses(), which is invoked only in the regular LTO backend.
3. In the new PM, the move of the hot cold splitting pass does not fix the issue for ThinLTO. The reason is that there is no early exit from buildModuleSimplificationPipeline. To fix, you can guard the hot cold split pass by "Phase != ThinLTOPhase::PreLink".
4. In the new PM, regular LTO invokes buildModuleSimplificationPipeline in the compile step, but without any extra info to indicate that it is an LTO compile. So something else will need to be done to suppress the hot cold splitting from happening early for regular LTO (e.g. pass down a new flag?).
5. Once 4) is done, regular LTO will no longer perform any splitting in the new PM since its backend doesn't invoke buildModuleSimplificationPipeline. To fix, you will want to add the hot cold split pass to an appropriate place in buildLTODefaultPipeline().

This all assumes that you want to only do splitting in the *LTO backends (i.e. after cross module inlining). What are the tradeoffs of doing the splitting before/after inlining?

One advantage of doing splitting before inlining is, as you pointed out, that more inlining opportunities are created because hot functions become smaller. The downside is that outlining may be a barrier for intra-function optimizations which benefit from seeing both sides of a branch (hoisting/sinking, const prop, maybe jump threading?).

I think the right thing to do is to conservatively avoid introducing barriers by delaying splitting as much as possible. I'll work on gathering some pre/post-patch performance numbers on arm64.

One advantage of doing the splitting earlier for ThinLTO, in the compile step, is that it would reduce the size of the functions during the import analysis, and we might import more hot (split) functions. But then the splitting would be happening before the cross-module inlining in the backends.

Regarding what I am currently seeing with two rounds of splitting with ThinLTO: I noticed that the second round of splitting in the ThinLTO backends was resplitting an already split function - specifically, the cold outlined function was getting split again, which doesn't make a lot of sense since presumably the edge weights were all cold. Note this is after r344558 (the fix for the issue of outlining the whole function). Why would that happen?

[vsk]

In D53437#1271395, @vsk wrote:

Thanks for your notes @tejohnson.

In D53437#1271156, @tejohnson wrote:

Note that this addresses in the old PM one issue I found when enabling splitting with ThinLTO, but exposes some related issues. In the old location, which was before the early return when PrepareForThinLTO==true around line 590, we were doing two rounds of splitting: one during the compile step, and a second later in the ThinLTO backends. I saw that we split an already split function (see below for more info). But I notice that there are still a couple issues:

1. In the old PM, we will still do splitting early (during the compile step) for regular LTO, which doesn't return early from this routine. You should presumably guard the adding of the hot cold split pass by "if (!PrepareForLTO)"
2. Once you've done 1), regular LTO will no longer perform any splitting, since its backend doesn't invoke populateModulePassManager. You can fix this by adding your hot cold splitting pass to an equivalent location in addLTOOptimizationPasses(), which is invoked only in the regular LTO backend.
3. In the new PM, the move of the hot cold splitting pass does not fix the issue for ThinLTO. The reason is that there is no early exit from buildModuleSimplificationPipeline. To fix, you can guard the hot cold split pass by "Phase != ThinLTOPhase::PreLink".
4. In the new PM, regular LTO invokes buildModuleSimplificationPipeline in the compile step, but without any extra info to indicate that it is an LTO compile. So something else will need to be done to suppress the hot cold splitting from happening early for regular LTO (e.g. pass down a new flag?).
5. Once 4) is done, regular LTO will no longer perform any splitting in the new PM since its backend doesn't invoke buildModuleSimplificationPipeline. To fix, you will want to add the hot cold split pass to an appropriate place in buildLTODefaultPipeline().

This all assumes that you want to only do splitting in the *LTO backends (i.e. after cross module inlining). What are the tradeoffs of doing the splitting before/after inlining?

One advantage of doing splitting before inlining is, as you pointed out, that more inlining opportunities are created because hot functions become smaller. The downside is that outlining may be a barrier for intra-function optimizations which benefit from seeing both sides of a branch (hoisting/sinking, const prop, maybe jump threading?).

I think the right thing to do is to conservatively avoid introducing barriers by delaying splitting as much as possible. I'll work on gathering some pre/post-patch performance numbers on arm64.

One advantage of doing the splitting earlier for ThinLTO, in the compile step, is that it would reduce the size of the functions during the import analysis, and we might import more hot (split) functions. But then the splitting would be happening before the cross-module inlining in the backends.

Regarding what I am currently seeing with two rounds of splitting with ThinLTO: I noticed that the second round of splitting in the ThinLTO backends was resplitting an already split function - specifically, the cold outlined function was getting split again, which doesn't make a lot of sense since presumably the edge weights were all cold. Note this is after r344558 (the fix for the issue of outlining the whole function). Why would that happen?

I have some thoughts about @tejohnson's second question here about how a cold outlined function could be split twice.

First, I think the cache of outlined Function objects (see shouldOutlineFrom) may be wiped out before LTO begins. Second, CodeExtractor inserts a (useless?) "header" block with an unconditional jump in the outlined function, and I think this creates more work for the splitting pass.

I'll look into getting rid of the cache and teaching CodeExtractor to run MergeBasicBlockIntoOnlyPred on the outlined function. I also have an upcoming patch that should guarantee that cold regions are maximal & have a warm predecessor -- these two conditions should prevent outlined code from being split again.

[tejohnson]

In D53437#1271156, @tejohnson wrote:

Note that this addresses in the old PM one issue I found when enabling splitting with ThinLTO, but exposes some related issues. In the old location, which was before the early return when PrepareForThinLTO==true around line 590, we were doing two rounds of splitting: one during the compile step, and a second later in the ThinLTO backends. I saw that we split an already split function (see below for more info). But I notice that there are still a couple issues:

1. In the old PM, we will still do splitting early (during the compile step) for regular LTO, which doesn't return early from this routine. You should presumably guard the adding of the hot cold split pass by "if (!PrepareForLTO)"
2. Once you've done 1), regular LTO will no longer perform any splitting, since its backend doesn't invoke populateModulePassManager. You can fix this by adding your hot cold splitting pass to an equivalent location in addLTOOptimizationPasses(), which is invoked only in the regular LTO backend.
3. In the new PM, the move of the hot cold splitting pass does not fix the issue for ThinLTO. The reason is that there is no early exit from buildModuleSimplificationPipeline. To fix, you can guard the hot cold split pass by "Phase != ThinLTOPhase::PreLink".

I'm going to send a patch to fix #3 so that we no longer run hot cold splitting multiple times anywhere to unblock me.

4. In the new PM, regular LTO invokes buildModuleSimplificationPipeline in the compile step, but without any extra info to indicate that it is an LTO compile. So something else will need to be done to suppress the hot cold splitting from happening early for regular LTO (e.g. pass down a new flag?).
5. Once 4) is done, regular LTO will no longer perform any splitting in the new PM since its backend doesn't invoke buildModuleSimplificationPipeline. To fix, you will want to add the hot cold split pass to an appropriate place in buildLTODefaultPipeline().

This all assumes that you want to only do splitting in the *LTO backends (i.e. after cross module inlining). What are the tradeoffs of doing the splitting before/after inlining? One advantage of doing the splitting earlier for ThinLTO, in the compile step, is that it would reduce the size of the functions during the import analysis, and we might import more hot (split) functions. But then the splitting would be happening before the cross-module inlining in the backends.

Regarding what I am currently seeing with two rounds of splitting with ThinLTO: I noticed that the second round of splitting in the ThinLTO backends was resplitting an already split function - specifically, the cold outlined function was getting split again, which doesn't make a lot of sense since presumably the edge weights were all cold. Note this is after r344558 (the fix for the issue of outlining the whole function). Why would that happen?

lib/Passes/PassBuilder.cpp

       // We perform early indirect call promotion here, before globalopt.
       // This is important for the ThinLTO backend phase because otherwise
       // imported available_externally functions look unreferenced and are
       // removed.
       MPM.addPass(PGOIndirectCallPromotion(Phase == ThinLTOPhase::PostLink,
                                            true));
   }
 
-  if (EnableHotColdSplit)
-    MPM.addPass(HotColdSplittingPass());
-
   // Interprocedural constant propagation now that basic cleanup has occurred
   // and prior to optimizing globals.
   // FIXME: This position in the pipeline hasn't been carefully considered in
   // years, it should be re-analyzed.
   MPM.addPass(IPSCCPPass());
 
   // Attach metadata to indirect call sites indicating the set of functions
   // they may target at run-time. This should follow IPSCCP.

   if (Level == O3)
     MainCGPipeline.addPass(ArgumentPromotionPass());
 
   // Lastly, add the core function simplification pipeline nested inside the
   // CGSCC walk.
   MainCGPipeline.addPass(createCGSCCToFunctionPassAdaptor(
       buildFunctionSimplificationPipeline(Level, Phase, DebugLogging)));
 
+  if (EnableHotColdSplit)
+    MPM.addPass(HotColdSplittingPass());
+
   for (auto &C : CGSCCOptimizerLateEPCallbacks)
     C(MainCGPipeline, Level);
 
   // We wrap the CGSCC pipeline in a devirtualization repeater. This will try
   // to detect when we devirtualize indirect calls and iterate the SCC passes
   // in that case to try and catch knock-on inlining or function attrs
   // opportunities. Then we add it to the module pipeline by walking the SCCs
   // in postorder (or bottom-up).