[Phase Ordering] Don't speculate in SimplifyCFG before PGO annotation

[tejohnson]

Summary

SimplifyCFG contains a number of transformations that perform
speculation, and will use profile data if it exists in the IR.
However, the first invocations of SimplifyCFG are before both
instrumented and sample PGO annotation. We found cases where
unprofitable speculation was performed in these early invocations, when
subsequent PGO profile data would have prevented it.

Disable the SpeculateBlocks flag before PGO annotation, in compiles
where PGO is provided.

This change resulted in noticeable and significant performance
improvements in multiple large internal codes.

Finally, remove an old test that had a difference with this change
(clang/test/CodeGen/pgo-sample-preparation.c), however, was testing
a pipeline configuration that no longer exists in the same way as when
the test was added. The code change being checked does not seem
indicative of a performance issue as the critical path remains the same,
and I could not find any description of a performance issue with the
original commit.

[aeubanks]

the pipeline change and simplifycfg change should be split into two changes

llvm/lib/Passes/PassBuilderPipelines.cpp

277

can we just drop the flag and make this change?

llvm/test/Transforms/SimplifyCFG/fold-branch-to-common-dest.ll

3 ↗

(On Diff #543071)

these checks won't work for a update_test_checks.py test. should add tests like the one added in https://reviews.llvm.org/D153391

llvm/test/Transforms/SimplifyCFG/pipeline-delay-speculation-pgo.ll

1 ↗

(On Diff #543071)

do you have a phase ordering test instead?

[tejohnson]

llvm/lib/Passes/PassBuilderPipelines.cpp

277

Ok, I will remove.

llvm/test/Transforms/SimplifyCFG/fold-branch-to-common-dest.ll

3 ↗

(On Diff #543071)

Can you clarify - are you saying remove the changes from this test and add a new test for this change like llvm/test/Transforms/SimplifyCFG/speculate-blocks.ll, or change the checks here?

llvm/test/Transforms/SimplifyCFG/pipeline-delay-speculation-pgo.ll

1 ↗

(On Diff #543071)

Can you clarify what you are referring to?

[aeubanks]

llvm/test/Transforms/SimplifyCFG/fold-branch-to-common-dest.ll

3 ↗

(On Diff #543071)

revert the changes here (update_test_checks.py tests shouldn't have manually added CHECK lines) and add new function(s) to llvm/test/Transforms/SimplifyCFG/speculate-blocks.ll that show the difference between speculate-blocks and no-speculate-blocks

llvm/test/Transforms/SimplifyCFG/pipeline-delay-speculation-pgo.ll

1 ↗

(On Diff #543071)

llvm/test/Transforms/PhaseOrdering has IR tests that get run through an entire pipeline (e.g. thinlto-pre-link<O3>) to verify some property of the entire pipeline. ideally you can get some somewhat-reduced IR that exhibits the problem you were seeing before the change and show that it improves with the pipeline change. you'll need a profile as part of that test I suppose

[tejohnson]

In D155997#4529861, @aeubanks wrote:

the pipeline change and simplifycfg change should be split into two changes

SimplifyCFG change split into D156194.

[tejohnson]

Address comments

[aeubanks]

llvm/test/Transforms/PhaseOrdering/simplifycfg-speculate-blocks.ll

1

hmm typically these phase ordering tests use llvm/utils/update_test_checks.py, but that doesn't support the llvm-profdata RUN line. I think a non-update_test_checks test is probably fine for this, @nikic does that make sense?

22

lto-pre-link

83

the debug info is necessary for sample profile to work I presume?

I think some of this can still be simplified, like PIC Level, etc

[nikic]

I'm not a fan of the PGO conditional behavior here. I'd prefer to disable speculation unconditionally if that is feasible. This is basically what D153392 did. While the specific test case there was addressed in a different way, if we take it in conjunction with this one, I think we have enough motivation to do the change.

Another piece of motivation would be that the EarlyFPM change would allow us to move LowerExpectIntrinsic to the end of EarlyFPM again, which would make expect intrinsics work in Rust again. The pass was moved earlier to make the first SimplifyCFG run take them into account, but that would no longer be a problem if we disable speculation.

And another piece of motivation would be that we could move SimplifyCFG after SROA, where it can be much more effective (but doing so with speculation breaks IPSCCP too much). I think doing that needs some further changes, but it's a move in the right direction.

So I think the EarlyFPM change at least seems like something we should pretty clearly do independently of PGO. The addPGOInstrPasses() change is of course PGO specific anyway. I think only the GlobalCleanupPM change may not be completely clear cut.

llvm/test/Transforms/PhaseOrdering/simplifycfg-speculate-blocks.ll

1

I thought UTC supports unrecognized commands (by just executing them)... If not, a non-UTC test is fine.

[tejohnson]

In D155997#4543156, @nikic wrote:

I'm not a fan of the PGO conditional behavior here. I'd prefer to disable speculation unconditionally if that is feasible. This is basically what D153392 did. While the specific test case there was addressed in a different way, if we take it in conjunction with this one, I think we have enough motivation to do the change.

It looks like D153392 does roughly the same disabling in practice, but you are right it doesn't gate on whether we will eventually feed back profile info. For the issue I was trying to solve, it was because of the PGO based profitability checks in SimplifyCFG speculation, but if it makes sense in other cases to disable it until later, then that works for me. BTW doesn't look like that patch disables speculation in addPGOInstrPasses, which we need for the issue I'm trying to solve.

Another piece of motivation would be that the EarlyFPM change would allow us to move LowerExpectIntrinsic to the end of EarlyFPM again, which would make expect intrinsics work in Rust again. The pass was moved earlier to make the first SimplifyCFG run take them into account, but that would no longer be a problem if we disable speculation.

And another piece of motivation would be that we could move SimplifyCFG after SROA, where it can be much more effective (but doing so with speculation breaks IPSCCP too much). I think doing that needs some further changes, but it's a move in the right direction.

So I think the EarlyFPM change at least seems like something we should pretty clearly do independently of PGO. The addPGOInstrPasses() change is of course PGO specific anyway. I think only the GlobalCleanupPM change may not be completely clear cut.

For the case I was looking at, with instrumentation PGO, any of the pre-feedback SimplifyCFG speculation passes would do the wrong thing without that PGO data.

[tejohnson]

llvm/test/Transforms/PhaseOrdering/simplifycfg-speculate-blocks.ll

83

Right, that's need for SamplePGO. Removed the other stuff that wasn't necessary.

[tejohnson]

Address test comments

[tejohnson]

ping

[aeubanks]

can we try not gating this on PGO as suggested? minimizing differences between pipelines is nice, and as mentioned it'll help with other cases

llvm/test/Transforms/PhaseOrdering/simplifycfg-speculate-blocks.ll

1

update_test_checks.py doesn't handle %t (maybe that's an improvement we could make to the script)

[tejohnson]

In D155997#4570562, @aeubanks wrote:

can we try not gating this on PGO as suggested? minimizing differences between pipelines is nice, and as mentioned it'll help with other cases

Sorry for the delay, was OOO for a bit and this ended up being a bit more complicated. Since I added a change to guard branch folding with the simplifyBlocks flag in D156194, there were additional tests that had differences that I have been trying to analyze and mitigate, with partial but not complete success (i.e. additional to what was seen when @aeubanks tried this in D153392):

1. llvm/test/CodeGen/Hexagon/loop-idiom/pmpy-mod.ll

The Hexagon loop idiom recognition pass is a little rigid in the detected code sequences, which were different because once we did the branch folding in a later SimplifyCFG invocation, followed by InstCombine, there was no EarlyCSE before the hexagon passes to do the cleanup required to get the old sequence. I can fix this by adding an invocation of EarlyCSE after those passes in buildFunctionSimplificationPipeline. There were no test changes from that fix, other than some tests that check the order of passes in each pipeline.

2. llvm/test/Transforms/PhaseOrdering/X86/vector-reductions-logical.ll

Not all function in this test are affected, but several are affected due to the phase ordering, specifically we stopped doing some of the branch folding completely which blocked some of the vectorization handling. In one of the functions I examined I found this was due to the fact that an EarlyCSE pass before we reran SimplifyCFG with speculation enabled did some commoning that blocked branch folding due to a limitation in the handling there. Specifically, the one added in https://reviews.llvm.org/rG909cba969981032c5740774ca84a34b7f76b909b. Undoing that does make the branch folding kick in more in this test, but isn't correct in general (it sounds like that patch was submitted to address a problem that was difficult to solve more optimally). In fact, that change had some similar affects on this test to my change, but there have been quite a few changes impacting this test over the past few years.

3. clang/test/Headers/__clang_hip_math.hip

Some fairly superficial diffs that don't appear important to the test.

Thoughts on how should I proceed? I can send the simple change I did for 1) above separately, since it doesn't seem to do any harm and presumably EarlyCSE is cheap. For 2) however, I'm not sure how much effort I should invest to get the test to behave exactly the same as before. There is clearly a limitation with SimplifyCFG that has been looked at before but isn't easy to solve.

llvm/test/Transforms/PhaseOrdering/simplifycfg-speculate-blocks.ll

1

I'm not sure what the alternative is here to using %t - do we need make the test support update_test_checks.py?

clang/test/CodeGen/pgo-sample-preparation.c

-// Test if PGO sample use preparation passes are executed correctly.
-//
-// Ensure that instcombine is executed after simplifycfg and sroa so that
-// "a < 255" will not be converted to a * 256 < 255 * 256.
-// RUN: %clang_cc1 -O2 -fprofile-sample-use=%S/Inputs/pgo-sample.prof %s -emit-llvm -o - 2>&1 | FileCheck %s
-
-void bar(int);
-void foo(int x, int y, int z) {
-  int m;
-  for (m = 0; m < x ; m++) {
-    int a = (((y >> 8) & 0xff) * z) / 256;
-    bar(a < 255 ? a : 255);
-  }
-}
-
-// CHECK-NOT: icmp slt i32 %mul, 65280

llvm/lib/Passes/PassBuilderPipelines.cpp

cl::values(clEnumValN(AttributorRunOption::ALL, "all",
                           "enable call graph SCC attributor runs"),
                clEnumValN(AttributorRunOption::NONE, "none",
                           "disable attributor runs")));
 
 cl::opt<bool> EnableMemProfContextDisambiguation(
     "enable-memprof-context-disambiguation", cl::init(false), cl::Hidden,
     cl::ZeroOrMore, cl::desc("Enable MemProf context disambiguation"));
 
 PipelineTuningOptions::PipelineTuningOptions() {
   LoopInterleaving = true;
   LoopVectorization = true;
   SLPVectorization = false;
   LoopUnrolling = true;
   ForgetAllSCEVInLoopUnroll = ForgetSCEVInLoopUnroll;
   LicmMssaOptCap = SetLicmMssaOptCap;
   LicmMssaNoAccForPromotionCap = SetLicmMssaNoAccForPromotionCap;
   CallGraphProfile = true;
if (!IsCS && !DisablePreInliner) {
     ModuleInlinerWrapperPass MIWP(
         IP, /* MandatoryFirst */ true,
         InlineContext{LTOPhase, InlinePass::EarlyInliner});
     CGSCCPassManager &CGPipeline = MIWP.getPM();
 
     FunctionPassManager FPM;
     FPM.addPass(SROAPass(SROAOptions::ModifyCFG));
     FPM.addPass(EarlyCSEPass()); // Catch trivial redundancies.
-    FPM.addPass(SimplifyCFGPass(SimplifyCFGOptions().convertSwitchRangeToICmp(
-        true)));                    // Merge & remove basic blocks.
+    FPM.addPass(SimplifyCFGPass(
+        SimplifyCFGOptions()
+            .convertSwitchRangeToICmp(true) // Merge & remove basic blocks.
+            // Don't enable speculation before PGO annotation since later
+            // invocations will utilize the profile for speculation decisions.
+            .speculateBlocks(false)));
     FPM.addPass(InstCombinePass()); // Combine silly sequences.
     invokePeepholeEPCallbacks(FPM, Level);
 
     CGPipeline.addPass(createCGSCCToFunctionPassAdaptor(
         std::move(FPM), PTO.EagerlyInvalidateAnalyses));
 
     MPM.addPass(std::move(MIWP));
 
PassBuilder::buildModuleSimplificationPipeline(OptimizationLevel Level,
 
   // In ThinLTO mode, when flattened profile is used, all the available
   // profile information will be annotated in PreLink phase so there is
   // no need to load the profile again in PostLink.
   bool LoadSampleProfile =
       HasSampleProfile &&
       !(FlattenedProfileUsed && Phase == ThinOrFullLTOPhase::ThinLTOPostLink);
 
+  bool LoadFirstSampleProfile =
+      HasSampleProfile && Phase != ThinOrFullLTOPhase::ThinLTOPostLink;
+
+  bool DoPGOInstr = PGOOpt && Phase != ThinOrFullLTOPhase::ThinLTOPostLink &&
+                    (PGOOpt->Action == PGOOptions::IRInstr ||
+                     PGOOpt->Action == PGOOptions::IRUse);
+
   // During the ThinLTO backend phase we perform early indirect call promotion
   // here, before globalopt. Otherwise imported available_externally functions
   // look unreferenced and are removed. If we are going to load the sample
   // profile then defer until later.
   // TODO: See if we can move later and consolidate with the location where
   // we perform ICP when we are loading a sample profile.
   // TODO: We pass HasSampleProfile (whether there was a sample profile file
   // passed to the compile) to the SamplePGO flag of ICP. This is used to
if (Phase != ThinOrFullLTOPhase::ThinLTOPostLink) {
     MPM.addPass(InferFunctionAttrsPass());
     MPM.addPass(CoroEarlyPass());
 
     FunctionPassManager EarlyFPM;
     // Lower llvm.expect to metadata before attempting transforms.
     // Compare/branch metadata may alter the behavior of passes like
     // SimplifyCFG.
     EarlyFPM.addPass(LowerExpectIntrinsicPass());
-    EarlyFPM.addPass(SimplifyCFGPass());
+    // Don't enable speculation before PGO annotation, since later invocations
+    // will utilize the profile for speculation decisions.
+    EarlyFPM.addPass(SimplifyCFGPass(SimplifyCFGOptions().speculateBlocks(
+        !DoPGOInstr && !LoadFirstSampleProfile)));
     EarlyFPM.addPass(SROAPass(SROAOptions::ModifyCFG));
     EarlyFPM.addPass(EarlyCSEPass());
     if (Level == OptimizationLevel::O3)
       EarlyFPM.addPass(CallSiteSplittingPass());
     MPM.addPass(createModuleToFunctionPassAdaptor(
         std::move(EarlyFPM), PTO.EagerlyInvalidateAnalyses));
   }
 
PassBuilder::buildModuleSimplificationPipeline(OptimizationLevel Level,
 
   // Create a small function pass pipeline to cleanup after all the global
   // optimizations.
   FunctionPassManager GlobalCleanupPM;
   // FIXME: Should this instead by a run of SROA?
   GlobalCleanupPM.addPass(PromotePass());
   GlobalCleanupPM.addPass(InstCombinePass());
   invokePeepholeEPCallbacks(GlobalCleanupPM, Level);
-  GlobalCleanupPM.addPass(
-      SimplifyCFGPass(SimplifyCFGOptions().convertSwitchRangeToICmp(true)));
+  // Don't enable speculation before PGO annotation, since later invocations
+  // will utilize the profile for speculation decisions. At this point SamplePGO
+  // annotation is done, so we don't need to disable it in that case.
+  GlobalCleanupPM.addPass(SimplifyCFGPass(
+      SimplifyCFGOptions().convertSwitchRangeToICmp(true).speculateBlocks(
+          !DoPGOInstr)));
   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(GlobalCleanupPM),
                                                 PTO.EagerlyInvalidateAnalyses));
 
   // Add all the requested passes for instrumentation PGO, if requested.
   if (PGOOpt && Phase != ThinOrFullLTOPhase::ThinLTOPostLink &&
       (PGOOpt->Action == PGOOptions::IRInstr ||
        PGOOpt->Action == PGOOptions::IRUse)) {
     addPGOInstrPasses(MPM, Level,

llvm/test/Transforms/PhaseOrdering/Inputs/simplifycfg-speculate-blocks.proftext

+# IR level Instrumentation Flag
+:ir
+:entry_first
+fold_two_entry_phi
+# Func Hash:
+784007059655560962
+# Num Counters:
+2
+# Counter Values:
+5000
+0
+
+fold_branch_to_common_dest
+# Func Hash:
+238984484714566715
+# Num Counters:
+3
+# Counter Values:
+5000
+0
+0

llvm/test/Transforms/PhaseOrdering/Inputs/simplifycfg-speculate-blocks.sampleprof

+fold_two_entry_phi:15000:5000
+ 1: 5000
+ 2: 0
+ 3: 5000
+ 4: 5000
+fold_branch_to_common_dest:10000:5000
+ 1: 5000
+ 2: 0
+ 3: 0
+ 4: 5000

llvm/test/Transforms/PhaseOrdering/simplifycfg-speculate-blocks.ll

+;; Check that SimplifyCFG does not attempt speculation until after PGO is
+;; annotated in the IR, and then does not perform it when unprofitable.
+
+;; No PGO: SimplifyCFG should speculate.
+; RUN: opt < %s -passes='default<O2>' -S | FileCheck %s --check-prefix=YES
+; RUN: opt < %s -passes='thinlto-pre-link<O2>' -S | FileCheck %s --check-prefix=YES
+; RUN: opt < %s -passes='lto-pre-link<O2>' -S | FileCheck %s --check-prefix=YES
+
+;; Instrumentation PGO: SimplifyCFG should only attempt speculation after PGO
+;; annotation, and in the below cases should not speculate given the branch
+;; biases.
+; RUN: llvm-profdata merge %S/Inputs/simplifycfg-speculate-blocks.proftext -o %t.profdata
+; RUN: opt < %s -passes='default<O2>' -pgo-kind=pgo-instr-use-pipeline -profile-file=%t.profdata -S | FileCheck %s --check-prefixes=NO,INSTR
+; RUN: opt < %s -passes='thinlto-pre-link<O2>' -pgo-kind=pgo-instr-use-pipeline -profile-file=%t.profdata -S | FileCheck %s --check-prefixes=NO,INSTR
+; RUN: opt < %s -passes='lto-pre-link<O2>' -pgo-kind=pgo-instr-use-pipeline -profile-file=%t.profdata -S | FileCheck %s --check-prefixes=NO,INSTR --implicit-check-not=select
+
+;; Sample PGO: SimplifyCFG should only attempt speculation after PGO
+;; annotation, and in the below cases should not speculate given the branch
+;; biases.
+; RUN: opt < %s -passes='default<O2>' -pgo-kind=pgo-sample-use-pipeline -profile-file=%S/Inputs/simplifycfg-speculate-blocks.sampleprof -S | FileCheck %s --check-prefixes=NO,SAMPLE
+; RUN: opt < %s -passes='thinlto-pre-link<O2>' -pgo-kind=pgo-sample-use-pipeline -profile-file=%S/Inputs/simplifycfg-speculate-blocks.sampleprof -S | FileCheck %s --check-prefixes=NO,SAMPLE
+; RUN: opt < %s -passes='thinlto-pre-link<O2>' -pgo-kind=pgo-sample-use-pipeline -profile-file=%S/Inputs/simplifycfg-speculate-blocks.sampleprof -S | FileCheck %s --check-prefixes=NO,SAMPLE
+
+%structx = type { [23 x i8], [0 x i8], i8 }
+define ptr @fold_two_entry_phi(ptr noundef nonnull align 8 dereferenceable(24) %v0) #0 !dbg !12 {
+; YES-LABEL: define ptr @fold_two_entry_phi
+; NO-LABEL: define ptr @fold_two_entry_phi
+  %1 = getelementptr inbounds %structx, ptr %v0, i64 0, i32 2
+  %2 = load i8, ptr %1, align 1
+  %3 = icmp slt i8 %2, 0
+  br i1 %3, label %truelabel, label %falselabel, !dbg !15
+; YES:    select
+; INSTR: br i1 {{.*}} !prof ![[PROF:[0-9]+]]
+; SAMPLE: br i1 {{.*}} !prof ![[PROF1:[0-9]+]]
+truelabel:
+  %4 = load ptr, ptr %v0, align 8, !dbg !16
+  br label %retlabel, !dbg !16
+falselabel:
+  br label %retlabel, !dbg !17
+retlabel:
+  %5 = phi ptr [ %4, %truelabel ], [ %v0, %falselabel ], !dbg !18
+  ret ptr %5, !dbg !18
+}
+
+define void @fold_branch_to_common_dest(i8 %v0, i8 %v1) #0 !dbg !19 {
+; YES-LABEL: define void @fold_branch_to_common_dest
+; NO-LABEL: define void @fold_branch_to_common_dest
+pred:
+  %c0 = icmp eq i8 %v0, 0
+  br i1 %c0, label %dispatch, label %final_right, !dbg !20
+; YES:    select
+; INSTR: br i1 %c0, label %dispatch, label %final_right, !dbg {{.*}}, !prof ![[PROF]]
+; SAMPLE: br i1 %c0, label %dispatch, label %final_right, !dbg {{.*}}, !prof ![[PROF2:[0-9]+]]
+dispatch:
+  %c1 = icmp eq i8 %v1, 0, !dbg !21
+  br i1 %c1, label %final_left, label %final_right, !dbg !21
+final_left:
+  call void @sideeffect0(), !dbg !22
+  ret void, !dbg !22
+final_right:
+  call void @sideeffect1(), !dbg !23
+  ret void, !dbg !23
+}
+
+declare void @sideeffect0()
+declare void @sideeffect1()
+
+; INSTR: ![[PROF]] = !{!"branch_weights", i32 0, i32 5000}
+; SAMPLE: ![[PROF1]] = !{!"branch_weights", i32 1, i32 5002}
+; SAMPLE: ![[PROF2]] = !{!"branch_weights", i32 1, i32 5001}
+
+attributes #0 = { "use-sample-profile" }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!2, !3, !4, !5, !6, !7, !8}
+!llvm.ident = !{!11}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, producer: "clang version 17.0.0 ([e-mail]:llvm/llvm-project.git 180a8148f95d2d5ed96c670fc322292fa0df876c)", isOptimized: true, runtimeVersion: 0, emissionKind: LineTablesOnly, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "simplifycfg-speculate-blocks.cc", directory: ".", checksumkind: CSK_MD5, checksum: "89bb3bed72c5e9634aa5f0653fc7a01b")
+!2 = !{i32 7, !"Dwarf Version", i32 5}
+!3 = !{i32 2, !"Debug Info Version", i32 3}
+!4 = !{i32 1, !"wchar_size", i32 4}
+!5 = !{i32 8, !"PIC Level", i32 2}
+!6 = !{i32 7, !"PIE Level", i32 2}
+!7 = !{i32 7, !"uwtable", i32 2}
+!8 = !{i32 7, !"frame-pointer", i32 2}
+!11 = !{!"clang version 17.0.0 ([e-mail]:llvm/llvm-project.git 180a8148f95d2d5ed96c670fc322292fa0df876c)"}
+!12 = distinct !DISubprogram(name: "fold_two_entry_phi", scope: !1, file: !1, line: 1, type: !13, scopeLine: 1, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0)
+!13 = !DISubroutineType(types: !14)
+!14 = !{}
+!15 = !DILocation(line: 2, column: 11, scope: !12)
+!16 = !DILocation(line: 3, column: 11, scope: !12)
+!17 = !DILocation(line: 4, column: 11, scope: !12)
+!18 = !DILocation(line: 5, column: 11, scope: !12)
+!19 = distinct !DISubprogram(name: "fold_branch_to_common_dest", scope: !1, file: !1, line: 10, type: !13, scopeLine: 10, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0)
+!20 = !DILocation(line: 11, column: 11, scope: !19)
+!21 = !DILocation(line: 12, column: 11, scope: !19)
+!22 = !DILocation(line: 13, column: 11, scope: !19)
+!23 = !DILocation(line: 14, column: 11, scope: !19)