[SimplifyCFG] If provided, preserve Dominator Tree

[lebedev.ri]

Summary

SimplifyCFG is an utility pass, and the fact that it does not preserve DomTree's,
forces it's users to somehow workaround that, likely by not preserving DomTrees's themselves.

Indeed, simplifycfg pass didn't know how to preserve dominator tree,
it took me just under a month (starting with e1133179587dd895962a2fe4d6eb0cb1e63b5ee2)
do rectify that, now it fully knows how to, there's likely some problems with that still,
but i've dealt with everything i can spot so far.

I think we now can flip the switch.

Note that this is functionally an NFC change, since this doesn't change the users
to pass in the DomTree, that is a separate question.

[kuhar]

Wow, this is fantastic. When I first started working on the domtree updater back in 2017, SimplifyGFG seemed like one of the most difficult passes to handle, and I wasn't sure if we ever get there. Very impressive work, @lebedev.ri!

[mkazantsev]

This is awesome. And scary. This is scarily awesome. :)

llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp

263

Why remove that? It looks useful to have (maybe over-paranoid) checks that DT is correct at least for the first time. I'd rather keep them for a while unless there is a reason to drop them now.

[nikic]

I'm somewhat skeptical about this change. The motivation seems a bit weak given the costs involved. The costs are:

• Compile-time cost. Your best case estimate puts this at a 0.5% compile-time regression. This is for the case where SimplifyCFG simplify preserves DT, without using it. Once the DT is used, the DTU may be flushed many times while SimplifyCFG iterates. This will drive the average-case cost up, and likely introduce pathological cases as well.
• Code complexity: At least watching from afar, your path to preserving DT in SimplifyCFG involved quite a few subtle issues, where the first implementation of DT preservation for a given transformation later turned out not to be entirely correct. Given the large number of very different transforms that SimplifyCFG performs, this adds a code complexity and maintenance cost.

The (listed) benefits are:

• Not processing unreachable blocks. I am doubtful that we'll want to use the DT for this purpose, because that would require flushing the DTU on each SimplifyCFG iteration. You'd probably be better off running removeUnreachableBlocks each time. Though it's not clear that this is even a problem that needs solving.
• Using DT in FoldBranchToCommonDest. This seems to be the real motivation here. I will have to dive deeper into the code to understand what the problem here is and whether it justifies the costs.

[xbolva00]

Code complexity

Was there any RFC or general agreement?

After many patches for this goal the pass is now more complex and harder to read.. it would be sad to revert month of work..

[lebedev.ri]

Wow. So much polarization here.

In D94827#2502435, @kuhar wrote:

Wow, this is fantastic. When I first started working on the domtree updater back in 2017, SimplifyGFG seemed like one of the most difficult passes to handle, and I wasn't sure if we ever get there. Very impressive work, @lebedev.ri!

In D94827#2504239, @mkazantsev wrote:

This is awesome. And scary. This is scarily awesome. :)

Why thank you.
It ended up being rather boringly trivial after all to me.
The hard part was coming up with the gradual roll-out part (the flag)

As for the rest of comments, let me split this up into parts.

1. Should SimplifyCFG know how to preserve {,Post}DominatorTree
2. Should SimplifyCFG make use of DominatorTree
3. Should SimplifyCFGPass require DominatorTree

As for 1., for the life of me i can not take that question seriously.
Let me point out that SimplifyCFG is an *Utility*, it can be called from other passes,
and as is painfully visible from the diff, both the DwarfEHPrepare
and AMDGPUUnifyDivergentExitNodes do that already.

By keeping SimplifyCFG illiterate about DomTrees, we force it's users
to also avoid DomTrees to some extent, be it either to just not preserve them,
or recompute them each time after calling SimplifyCFG.

Is that really what we want to be doing?
So if such a question is seriously being asked,
i'd personally suggest to take a step back and really think about it.

3 - ignoring the cost of domtree preservation, this is basically free.
As far as i can tell from the tests, it doesn't result in any new domtree creations,
we'd always already calculate domtree after the simplifycfg invocation,
now we'll just do that earlier.

2 - well, yeah, that is a question of the patch, isn't it? :)
Not sure why it's being met with such surprisingly-hostile comments.

In D94827#2505300, @nikic wrote:

I'm somewhat skeptical about this change. The motivation seems a bit weak given the costs involved. The costs are:

• Compile-time cost. Your best case estimate puts this at a 0.5% compile-time regression. This is for the case where SimplifyCFG simplify preserves DT, without using it. Once the DT is used, the DTU may be flushed many times while SimplifyCFG iterates. This will drive the average-case cost up, and likely introduce pathological cases as well.

Gentle reminder that i have already previously suggested to codify that
LLVM now prioritizes compile-time over everything.
Or something to that regard, about compile time.
I don't think that has happened yet, so i'm going to largely blatantly ignore this point.

• Code complexity: At least watching from afar, your path to preserving DT in SimplifyCFG involved quite a few subtle issues, where the first implementation of DT preservation for a given transformation later turned out not to be entirely correct. Given the large number of very different transforms that SimplifyCFG performs, this adds a code complexity and maintenance cost.

1. See above.
2. This is true for practically every change, to some extent, so i'm not sure what the point is here.
3. "Never attribute to malice that which is adequately explained by stupidity", or in this case, it's not that "later turned out not to be entirely correct", this was a *very* intentional roll-out approach, to weed out the cases that lacked test coverage.

The (listed) benefits are:

• Not processing unreachable blocks. I am doubtful that we'll want to use the DT for this purpose, because that would require flushing the DTU on each SimplifyCFG iteration. You'd probably be better off running removeUnreachableBlocks each time. Though it's not clear that this is even a problem that needs solving.

• Using DT in FoldBranchToCommonDest. This seems to be the real motivation here. I will have to dive deeper into the code to understand what the problem here is and whether it justifies the costs.

In the mean time, now that i'm done with the groundwork, i'll fix that the currently-preferred way.

llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp

263

Note that this checks that the DomTree *provided by the pass manager* is valid.
Do we actually want to check that here?

[nikic]

In D94827#2505431, @lebedev.ri wrote:

Wow. So much polarization here.

In D94827#2502435, @kuhar wrote:

Wow, this is fantastic. When I first started working on the domtree updater back in 2017, SimplifyGFG seemed like one of the most difficult passes to handle, and I wasn't sure if we ever get there. Very impressive work, @lebedev.ri!

In D94827#2504239, @mkazantsev wrote:

This is awesome. And scary. This is scarily awesome. :)

Why thank you.
It ended up being rather boringly trivial after all to me.
The hard part was coming up with the gradual roll-out part (the flag)

As for the rest of comments, let me split this up into parts.

1. Should SimplifyCFG know how to preserve {,Post}DominatorTree
2. Should SimplifyCFG make use of DominatorTree
3. Should SimplifyCFGPass require DominatorTree

As for 1., for the life of me i can not take that question seriously.
Let me point out that SimplifyCFG is an *Utility*, it can be called from other passes,
and as is painfully visible from the diff, both the DwarfEHPrepare
and AMDGPUUnifyDivergentExitNodes do that already.

By keeping SimplifyCFG illiterate about DomTrees, we force it's users
to also avoid DomTrees to some extent, be it either to just not preserve them,
or recompute them each time after calling SimplifyCFG.

Is that really what we want to be doing?
So if such a question is seriously being asked,
i'd personally suggest to take a step back and really think about it.

3 - ignoring the cost of domtree preservation, this is basically free.
As far as i can tell from the tests, it doesn't result in any new domtree creations,
we'd always already calculate domtree after the simplifycfg invocation,
now we'll just do that earlier.

2 - well, yeah, that is a question of the patch, isn't it? :)
Not sure why it's being met with such surprisingly-hostile comments.

I'm not sure why my comment was taken to be hostile. All I want to say is that there's a tradeoff here, and I haven't been convinced that it's a good one yet.

I think your point that SimplifyCFG is a utility and may be used in passes that want to preserve DT is a good one. I can see an argument for supporting DT-preservation in SimplifyCFG, while not requiring it in SimplifyCFGPass and not allowing use inside SimplifyCFG itself. Do I understand correctly that DwarfEHPrepare may currently use an outdated dominator tree because SimplifyCFG does not preserve it? If that is the case, then that should certainly be addressed in some way.

In D94827#2505300, @nikic wrote:

I'm somewhat skeptical about this change. The motivation seems a bit weak given the costs involved. The costs are:

• Compile-time cost. Your best case estimate puts this at a 0.5% compile-time regression. This is for the case where SimplifyCFG simplify preserves DT, without using it. Once the DT is used, the DTU may be flushed many times while SimplifyCFG iterates. This will drive the average-case cost up, and likely introduce pathological cases as well.

Gentle reminder that i have already previously suggested to codify that
LLVM now prioritizes compile-time over everything.
Or something to that regard, about compile time.
I don't think that has happened yet, so i'm going to largely blatantly ignore this point.

LLVM does not prioritize compile-time over everything. Compile-time regressions are fine as long as they are justified.

I have already stated my concern above. Preserving the DT is one thing, and a 0.5% compile-time regression is not overly problematic. However, the intention behind this change is clearly to also make use of DT inside SimplifyCFG, and that's where things become very problematic. I did a quick try of fetching the DT (and thus requiring a DTU flush) on every SimplifyCFG iteration (which is what would happen if we implemented your idea regarding unreachable blocks), and here's the result I got: https://llvm-compile-time-tracker.com/compare.php?from=22b68440e1647e16b5ee24b924986207173c02d1&to=879bffddcb45b02f3c819e542a327a5539999ea2&stat=instructions Now we go from 0.5% regression to 2.5%. consumer-typeset sees a 5% regression. The regressions are larger on individual files, e.g. libclamav_pe.c sees as >30% regression. This isn't peanuts. And these are still "average case" regressions on relatively benign benchmarks. You can bet that if you do this, you're going to see pathologically large regressions on generated code.

I feel like this is a valid concern to have, and I don't like the way you're just brushing this off completely. While it seems like common sense to me, I will look into updating our developer policy to make explicit mention of compile-time regressions, next to performance and correctness regressions.

• Code complexity: At least watching from afar, your path to preserving DT in SimplifyCFG involved quite a few subtle issues, where the first implementation of DT preservation for a given transformation later turned out not to be entirely correct. Given the large number of very different transforms that SimplifyCFG performs, this adds a code complexity and maintenance cost.

1. See above.
2. This is true for practically every change, to some extent, so i'm not sure what the point is here.
3. "Never attribute to malice that which is adequately explained by stupidity", or in this case, it's not that "later turned out not to be entirely correct", this was a *very* intentional roll-out approach, to weed out the cases that lacked test coverage.

Oh, sorry, looks like I misunderstood what was going on there. It didn't cross my mind that you would intentionally write incorrect DTU code in order to fix it later.

[mkazantsev]

llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp

263

This assert is meant to check that we actually pass it a DomTree immediately from the pass manager, and not some previously modified dom tree. It's up to you, but I'm a little bit paranoid when it comes to validation of analysis structures. It's never too late to remove redundant assertions.

[lebedev.ri]

Let me resell this. This patch is fully NFC,
it just signifies that SimplifyCFG is now DomTree-aware,
and preserves it if it is provided.

Here, i'm only looking for a congratulatory LGTM.
I'm sure some edgecases will pop up

[nikic]

LGTM

[lebedev.ri]

@kuhar @mkazantsev wanna get in on the hype train?

[kuhar]

Choo choo

clang/test/CodeGen/thinlto-distributed-newpm.ll

 ; CHECK-O: Running analysis: ProfileSummaryAnalysis
 ; CHECK-O: Running analysis: InnerAnalysisManagerProxy
 ; CHECK-O: Running analysis: OptimizationRemarkEmitterAnalysis on main
 ; CHECK-O: Running pass: InferFunctionAttrsPass
 ; CHECK-O: Starting {{.*}}Function pass manager run.
 ; CHECK-O: Running pass: SimplifyCFGPass on main
 ; CHECK-O: Running analysis: TargetIRAnalysis on main
 ; CHECK-O: Running analysis: AssumptionAnalysis on main
-; CHECK-O: Running pass: SROA on main
 ; CHECK-O: Running analysis: DominatorTreeAnalysis on main
+; CHECK-O: Running pass: SROA on main
 ; CHECK-O: Running pass: EarlyCSEPass on main
 ; CHECK-O: Running analysis: TargetLibraryAnalysis on main
 ; CHECK-O: Running pass: LowerExpectIntrinsicPass on main
 ; CHECK-O3: Running pass: CallSiteSplittingPass on main
 ; CHECK-O: Finished {{.*}}Function pass manager run.
 ; CHECK-O: Running pass: LowerTypeTestsPass
 ; CHECK-O: Running pass: IPSCCPPass
 ; CHECK-O: Running pass: CalledValuePropagationPass

llvm/lib/CodeGen/DwarfEHPrepare.cpp

bool DwarfEHPrepare::InsertUnwindResumeCalls() {
 
   if (DTU && RequireAndPreserveDomTree)
     DTU->applyUpdates(Updates);
 
   return true;
 }
 
 bool DwarfEHPrepare::run() {
-  assert(((OptLevel == CodeGenOpt::None || !RequireAndPreserveDomTree) ||
-          (DTU &&
-           DTU->getDomTree().verify(DominatorTree::VerificationLevel::Full))) &&
-         "Original domtree is invalid?");
-
   bool Changed = InsertUnwindResumeCalls();
 
-  assert(((OptLevel == CodeGenOpt::None || !RequireAndPreserveDomTree) ||
-          (DTU &&
-           DTU->getDomTree().verify(DominatorTree::VerificationLevel::Full))) &&
-         "Original domtree is invalid?");
-
   return Changed;
 }
 
 static bool prepareDwarfEH(CodeGenOpt::Level OptLevel,
                            FunctionCallee &RewindFunction, Function &F,
                            const TargetLowering &TLI, DominatorTree *DT,
                            const TargetTransformInfo *TTI) {
-  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
 
   return DwarfEHPrepare(OptLevel, RewindFunction, F, TLI, DT ? &DTU : nullptr,
                         TTI)
       .run();
 }
 
 namespace {
 

llvm/lib/Target/AMDGPU/AMDGPUUnifyDivergentExitNodes.cpp

if (!ReturningBlocks.empty()) {
       // actually reached here.
       ReturnInst::Create(F.getContext(), RetVal, UnreachableBlock);
       ReturningBlocks.push_back(UnreachableBlock);
       Changed = true;
     }
   }
 
   // FIXME: add PDT here once simplifycfg is ready.
-  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
   if (RequireAndPreserveDomTree)
     DTU.applyUpdates(Updates);
   Updates.clear();
 
   // Now handle return blocks.
   if (ReturningBlocks.empty())
     return Changed; // No blocks return
 

llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp

while (LocalChange) {
     Changed |= LocalChange;
   }
   return Changed;
 }
 
 static bool simplifyFunctionCFGImpl(Function &F, const TargetTransformInfo &TTI,
                                     DominatorTree *DT,
                                     const SimplifyCFGOptions &Options) {
-  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
 
   bool EverChanged = removeUnreachableBlocks(F, DT ? &DTU : nullptr);
   EverChanged |= mergeEmptyReturnBlocks(F, DT ? &DTU : nullptr);
   EverChanged |= iterativelySimplifyCFG(F, TTI, DT ? &DTU : nullptr, Options);
 
   // If neither pass changed anything, we're done.
   if (!EverChanged) return false;
 
static bool simplifyFunctionCFGImpl(Function &F, const TargetTransformInfo &TTI,
   } while (EverChanged);
 
   return true;
 }
 
 static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI,
                                 DominatorTree *DT,
                                 const SimplifyCFGOptions &Options) {
-  assert((!RequireAndPreserveDomTree ||
-          (DT && DT->verify(DominatorTree::VerificationLevel::Full))) &&
-         "Original domtree is invalid?");
-
   bool Changed = simplifyFunctionCFGImpl(F, TTI, DT, Options);
 
-  assert((!RequireAndPreserveDomTree ||
-          (DT && DT->verify(DominatorTree::VerificationLevel::Full))) &&
-         "Failed to maintain validity of domtree!");
-
   return Changed;
 }
 
 // Command-line settings override compile-time settings.
 static void applyCommandLineOverridesToOptions(SimplifyCFGOptions &Options) {
   if (UserBonusInstThreshold.getNumOccurrences())
     Options.BonusInstThreshold = UserBonusInstThreshold;
   if (UserForwardSwitchCond.getNumOccurrences())

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

 
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "simplifycfg"
 
 cl::opt<bool> llvm::RequireAndPreserveDomTree(
     "simplifycfg-require-and-preserve-domtree", cl::Hidden, cl::ZeroOrMore,
-    cl::init(false),
+    cl::init(true),
     cl::desc("Temorary development switch used to gradually uplift SimplifyCFG "
              "into preserving DomTree,"));
 
 // Chosen as 2 so as to be cheap, but still to have enough power to fold
 // a select, so the "clamp" idiom (of a min followed by a max) will be caught.
 // To catch this, we need to fold a compare and a select, hence '2' being the
 // minimum reasonable default.
 static cl::opt<unsigned> PHINodeFoldingThreshold(
bool SimplifyCFGOpt::simplifyOnceImpl(BasicBlock *BB) {
   }
 
   return Changed;
 }
 
 bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
   bool Changed = simplifyOnceImpl(BB);
 
-  assert((!RequireAndPreserveDomTree ||
-          (DTU &&
-           DTU->getDomTree().verify(DominatorTree::VerificationLevel::Full))) &&
-         "Failed to maintain validity of domtree!");
-
   return Changed;
 }
 
 bool SimplifyCFGOpt::run(BasicBlock *BB) {
-  assert((!RequireAndPreserveDomTree ||
-          (DTU &&
-           DTU->getDomTree().verify(DominatorTree::VerificationLevel::Full))) &&
-         "Original domtree is invalid?");
-
   bool Changed = false;
 
   // Repeated simplify BB as long as resimplification is requested.
   do {
     Resimplify = false;
 
     // Perform one round of simplifcation. Resimplify flag will be set if
     // another iteration is requested.

llvm/test/CodeGen/AArch64/O3-pipeline.ll

 ; CHECK-NEXT:   ModulePass Manager
 ; CHECK-NEXT:     Pre-ISel Intrinsic Lowering
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Expand Atomic instructions
 ; CHECK-NEXT:     SVE intrinsics optimizations
 ; CHECK-NEXT:       FunctionPass Manager
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:     FunctionPass Manager
-; CHECK-NEXT:       Simplify the CFG
 ; CHECK-NEXT:       Dominator Tree Construction
+; CHECK-NEXT:       Simplify the CFG
 ; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Scalar Evolution Analysis
 ; CHECK-NEXT:       Loop Data Prefetch
 ; CHECK-NEXT:       Falkor HW Prefetch Fix
 ; CHECK-NEXT:       Module Verifier

llvm/test/CodeGen/AMDGPU/opt-pipeline.ll

 ; GCN-O1-NEXT:   FunctionPass Manager
 ; GCN-O1-NEXT:     Early propagate attributes from kernels to functions
 ; GCN-O1-NEXT:     Replace builtin math calls with that native versions.
 ; GCN-O1-NEXT:     Dominator Tree Construction
 ; GCN-O1-NEXT:     Basic Alias Analysis (stateless AA impl)
 ; GCN-O1-NEXT:     Function Alias Analysis Results
 ; GCN-O1-NEXT:     Simplify well-known AMD library calls
 ; GCN-O1-NEXT:     Instrument function entry/exit with calls to e.g. mcount() (pre inlining)
-; GCN-O1-NEXT:     Simplify the CFG
 ; GCN-O1-NEXT:     Dominator Tree Construction
+; GCN-O1-NEXT:     Simplify the CFG
 ; GCN-O1-NEXT:     SROA
 ; GCN-O1-NEXT:     Early CSE
 ; GCN-O1-NEXT:     Lower 'expect' Intrinsics
 
 ; GCN-O1-NEXT: Pass Arguments:
 ; GCN-O1-NEXT: Target Library Information
 ; GCN-O1-NEXT: Target Transform Information
 ; GCN-O1-NEXT: Target Pass Configuration

 ; GCN-O1-NEXT:       AMDGPU Promote Alloca to vector
 ; GCN-O1-NEXT:       Dominator Tree Construction
 ; GCN-O1-NEXT:       SROA
 ; GCN-O1-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O1-NEXT:       Function Alias Analysis Results
 ; GCN-O1-NEXT:       Memory SSA
 ; GCN-O1-NEXT:       Early CSE w/ MemorySSA
 ; GCN-O1-NEXT:       Simplify the CFG
-; GCN-O1-NEXT:       Dominator Tree Construction
 ; GCN-O1-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O1-NEXT:       Function Alias Analysis Results
 ; GCN-O1-NEXT:       Natural Loop Information
 ; GCN-O1-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O1-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O1-NEXT:       Optimization Remark Emitter
 ; GCN-O1-NEXT:       Combine redundant instructions
 ; GCN-O1-NEXT:       Conditionally eliminate dead library calls
 ; GCN-O1-NEXT:       Natural Loop Information
 ; GCN-O1-NEXT:       Post-Dominator Tree Construction
 ; GCN-O1-NEXT:       Branch Probability Analysis
 ; GCN-O1-NEXT:       Block Frequency Analysis
 ; GCN-O1-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O1-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O1-NEXT:       Optimization Remark Emitter
 ; GCN-O1-NEXT:       PGOMemOPSize
 ; GCN-O1-NEXT:       Simplify the CFG
 ; GCN-O1-NEXT:       Reassociate expressions
-; GCN-O1-NEXT:       Dominator Tree Construction
 ; GCN-O1-NEXT:       Natural Loop Information
 ; GCN-O1-NEXT:       Canonicalize natural loops
 ; GCN-O1-NEXT:       LCSSA Verifier
 ; GCN-O1-NEXT:       Loop-Closed SSA Form Pass
 ; GCN-O1-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O1-NEXT:       Function Alias Analysis Results
 ; GCN-O1-NEXT:       Scalar Evolution Analysis
 ; GCN-O1-NEXT:       Loop Pass Manager
 ; GCN-O1-NEXT:         Rotate Loops
 ; GCN-O1-NEXT:       Memory SSA
 ; GCN-O1-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O1-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O1-NEXT:       Loop Pass Manager
 ; GCN-O1-NEXT:         Loop Invariant Code Motion
 ; GCN-O1-NEXT:       Post-Dominator Tree Construction
 ; GCN-O1-NEXT:       Legacy Divergence Analysis
 ; GCN-O1-NEXT:       Loop Pass Manager
 ; GCN-O1-NEXT:         Unswitch loops
 ; GCN-O1-NEXT:       Simplify the CFG
-; GCN-O1-NEXT:       Dominator Tree Construction
 ; GCN-O1-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O1-NEXT:       Function Alias Analysis Results
 ; GCN-O1-NEXT:       Natural Loop Information
 ; GCN-O1-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O1-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O1-NEXT:       Optimization Remark Emitter
 ; GCN-O1-NEXT:       Combine redundant instructions
 ; GCN-O1-NEXT:       Canonicalize natural loops

 ; GCN-O1-NEXT:       Function Alias Analysis Results
 ; GCN-O1-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O1-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O1-NEXT:       Optimization Remark Emitter
 ; GCN-O1-NEXT:       Combine redundant instructions
 ; GCN-O1-NEXT:       Post-Dominator Tree Construction
 ; GCN-O1-NEXT:       Aggressive Dead Code Elimination
 ; GCN-O1-NEXT:       Simplify the CFG
-; GCN-O1-NEXT:       Dominator Tree Construction
 ; GCN-O1-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O1-NEXT:       Function Alias Analysis Results
 ; GCN-O1-NEXT:       Natural Loop Information
 ; GCN-O1-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O1-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O1-NEXT:       Optimization Remark Emitter
 ; GCN-O1-NEXT:       Combine redundant instructions
 ; GCN-O1-NEXT:     A No-Op Barrier Pass

 ; GCN-O1-NEXT:       Loop Load Elimination
 ; GCN-O1-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O1-NEXT:       Function Alias Analysis Results
 ; GCN-O1-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O1-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O1-NEXT:       Optimization Remark Emitter
 ; GCN-O1-NEXT:       Combine redundant instructions
 ; GCN-O1-NEXT:       Simplify the CFG
-; GCN-O1-NEXT:       Dominator Tree Construction
 ; GCN-O1-NEXT:       Optimize scalar/vector ops
 ; GCN-O1-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O1-NEXT:       Function Alias Analysis Results
 ; GCN-O1-NEXT:       Natural Loop Information
 ; GCN-O1-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O1-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O1-NEXT:       Optimization Remark Emitter
 ; GCN-O1-NEXT:       Combine redundant instructions

 ; GCN-O2-NEXT:   FunctionPass Manager
 ; GCN-O2-NEXT:     Early propagate attributes from kernels to functions
 ; GCN-O2-NEXT:     Replace builtin math calls with that native versions.
 ; GCN-O2-NEXT:     Dominator Tree Construction
 ; GCN-O2-NEXT:     Basic Alias Analysis (stateless AA impl)
 ; GCN-O2-NEXT:     Function Alias Analysis Results
 ; GCN-O2-NEXT:     Simplify well-known AMD library calls
 ; GCN-O2-NEXT:     Instrument function entry/exit with calls to e.g. mcount() (pre inlining)
-; GCN-O2-NEXT:     Simplify the CFG
 ; GCN-O2-NEXT:     Dominator Tree Construction
+; GCN-O2-NEXT:     Simplify the CFG
 ; GCN-O2-NEXT:     SROA
 ; GCN-O2-NEXT:     Early CSE
 ; GCN-O2-NEXT:     Lower 'expect' Intrinsics
 
 ; GCN-O2-NEXT: Pass Arguments:
 ; GCN-O2-NEXT: Target Library Information
 ; GCN-O2-NEXT: Target Transform Information
 ; GCN-O2-NEXT: Target Pass Configuration

 ; GCN-O2-NEXT:       Memory SSA
 ; GCN-O2-NEXT:       Early CSE w/ MemorySSA
 ; GCN-O2-NEXT:       Speculatively execute instructions if target has divergent branches
 ; GCN-O2-NEXT:       Function Alias Analysis Results
 ; GCN-O2-NEXT:       Lazy Value Information Analysis
 ; GCN-O2-NEXT:       Jump Threading
 ; GCN-O2-NEXT:       Value Propagation
 ; GCN-O2-NEXT:       Simplify the CFG
-; GCN-O2-NEXT:       Dominator Tree Construction
 ; GCN-O2-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O2-NEXT:       Function Alias Analysis Results
 ; GCN-O2-NEXT:       Natural Loop Information
 ; GCN-O2-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O2-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O2-NEXT:       Optimization Remark Emitter
 ; GCN-O2-NEXT:       Combine redundant instructions
 ; GCN-O2-NEXT:       Conditionally eliminate dead library calls

 ; GCN-O2-NEXT:       Function Alias Analysis Results
 ; GCN-O2-NEXT:       Natural Loop Information
 ; GCN-O2-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O2-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O2-NEXT:       Optimization Remark Emitter
 ; GCN-O2-NEXT:       Tail Call Elimination
 ; GCN-O2-NEXT:       Simplify the CFG
 ; GCN-O2-NEXT:       Reassociate expressions
-; GCN-O2-NEXT:       Dominator Tree Construction
 ; GCN-O2-NEXT:       Natural Loop Information
 ; GCN-O2-NEXT:       Canonicalize natural loops
 ; GCN-O2-NEXT:       LCSSA Verifier
 ; GCN-O2-NEXT:       Loop-Closed SSA Form Pass
 ; GCN-O2-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O2-NEXT:       Function Alias Analysis Results
 ; GCN-O2-NEXT:       Scalar Evolution Analysis
 ; GCN-O2-NEXT:       Loop Pass Manager
 ; GCN-O2-NEXT:         Rotate Loops
 ; GCN-O2-NEXT:       Memory SSA
 ; GCN-O2-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O2-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O2-NEXT:       Loop Pass Manager
 ; GCN-O2-NEXT:         Loop Invariant Code Motion
 ; GCN-O2-NEXT:       Post-Dominator Tree Construction
 ; GCN-O2-NEXT:       Legacy Divergence Analysis
 ; GCN-O2-NEXT:       Loop Pass Manager
 ; GCN-O2-NEXT:         Unswitch loops
 ; GCN-O2-NEXT:       Simplify the CFG
-; GCN-O2-NEXT:       Dominator Tree Construction
 ; GCN-O2-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O2-NEXT:       Function Alias Analysis Results
 ; GCN-O2-NEXT:       Natural Loop Information
 ; GCN-O2-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O2-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O2-NEXT:       Optimization Remark Emitter
 ; GCN-O2-NEXT:       Combine redundant instructions
 ; GCN-O2-NEXT:       Canonicalize natural loops

 ; GCN-O2-NEXT:       Loop-Closed SSA Form Pass
 ; GCN-O2-NEXT:       Function Alias Analysis Results
 ; GCN-O2-NEXT:       Scalar Evolution Analysis
 ; GCN-O2-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O2-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O2-NEXT:       Loop Pass Manager
 ; GCN-O2-NEXT:         Loop Invariant Code Motion
 ; GCN-O2-NEXT:       Simplify the CFG
-; GCN-O2-NEXT:       Dominator Tree Construction
 ; GCN-O2-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O2-NEXT:       Function Alias Analysis Results
 ; GCN-O2-NEXT:       Natural Loop Information
 ; GCN-O2-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O2-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O2-NEXT:       Optimization Remark Emitter
 ; GCN-O2-NEXT:       Combine redundant instructions
 ; GCN-O2-NEXT:     A No-Op Barrier Pass

 ; GCN-O2-NEXT:       Loop Load Elimination
 ; GCN-O2-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O2-NEXT:       Function Alias Analysis Results
 ; GCN-O2-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O2-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O2-NEXT:       Optimization Remark Emitter
 ; GCN-O2-NEXT:       Combine redundant instructions
 ; GCN-O2-NEXT:       Simplify the CFG
-; GCN-O2-NEXT:       Dominator Tree Construction
 ; GCN-O2-NEXT:       Natural Loop Information
 ; GCN-O2-NEXT:       Scalar Evolution Analysis
 ; GCN-O2-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O2-NEXT:       Function Alias Analysis Results
 ; GCN-O2-NEXT:       Demanded bits analysis
 ; GCN-O2-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O2-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O2-NEXT:       Optimization Remark Emitter

 ; GCN-O3-NEXT:   FunctionPass Manager
 ; GCN-O3-NEXT:     Early propagate attributes from kernels to functions
 ; GCN-O3-NEXT:     Replace builtin math calls with that native versions.
 ; GCN-O3-NEXT:     Dominator Tree Construction
 ; GCN-O3-NEXT:     Basic Alias Analysis (stateless AA impl)
 ; GCN-O3-NEXT:     Function Alias Analysis Results
 ; GCN-O3-NEXT:     Simplify well-known AMD library calls
 ; GCN-O3-NEXT:     Instrument function entry/exit with calls to e.g. mcount() (pre inlining)
-; GCN-O3-NEXT:     Simplify the CFG
 ; GCN-O3-NEXT:     Dominator Tree Construction
+; GCN-O3-NEXT:     Simplify the CFG
 ; GCN-O3-NEXT:     SROA
 ; GCN-O3-NEXT:     Early CSE
 ; GCN-O3-NEXT:     Lower 'expect' Intrinsics
 
 ; GCN-O3-NEXT: Pass Arguments:
 ; GCN-O3-NEXT: Target Library Information
 ; GCN-O3-NEXT: Target Transform Information
 ; GCN-O3-NEXT: Target Pass Configuration

 ; GCN-O3-NEXT:       Memory SSA
 ; GCN-O3-NEXT:       Early CSE w/ MemorySSA
 ; GCN-O3-NEXT:       Speculatively execute instructions if target has divergent branches
 ; GCN-O3-NEXT:       Function Alias Analysis Results
 ; GCN-O3-NEXT:       Lazy Value Information Analysis
 ; GCN-O3-NEXT:       Jump Threading
 ; GCN-O3-NEXT:       Value Propagation
 ; GCN-O3-NEXT:       Simplify the CFG
-; GCN-O3-NEXT:       Dominator Tree Construction
 ; GCN-O3-NEXT:       Combine pattern based expressions
 ; GCN-O3-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O3-NEXT:       Function Alias Analysis Results
 ; GCN-O3-NEXT:       Natural Loop Information
 ; GCN-O3-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O3-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O3-NEXT:       Optimization Remark Emitter
 ; GCN-O3-NEXT:       Combine redundant instructions

 ; GCN-O3-NEXT:       Function Alias Analysis Results
 ; GCN-O3-NEXT:       Natural Loop Information
 ; GCN-O3-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O3-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O3-NEXT:       Optimization Remark Emitter
 ; GCN-O3-NEXT:       Tail Call Elimination
 ; GCN-O3-NEXT:       Simplify the CFG
 ; GCN-O3-NEXT:       Reassociate expressions
-; GCN-O3-NEXT:       Dominator Tree Construction
 ; GCN-O3-NEXT:       Natural Loop Information
 ; GCN-O3-NEXT:       Canonicalize natural loops
 ; GCN-O3-NEXT:       LCSSA Verifier
 ; GCN-O3-NEXT:       Loop-Closed SSA Form Pass
 ; GCN-O3-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O3-NEXT:       Function Alias Analysis Results
 ; GCN-O3-NEXT:       Scalar Evolution Analysis
 ; GCN-O3-NEXT:       Loop Pass Manager
 ; GCN-O3-NEXT:         Rotate Loops
 ; GCN-O3-NEXT:       Memory SSA
 ; GCN-O3-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O3-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O3-NEXT:       Loop Pass Manager
 ; GCN-O3-NEXT:         Loop Invariant Code Motion
 ; GCN-O3-NEXT:       Post-Dominator Tree Construction
 ; GCN-O3-NEXT:       Legacy Divergence Analysis
 ; GCN-O3-NEXT:       Loop Pass Manager
 ; GCN-O3-NEXT:         Unswitch loops
 ; GCN-O3-NEXT:       Simplify the CFG
-; GCN-O3-NEXT:       Dominator Tree Construction
 ; GCN-O3-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O3-NEXT:       Function Alias Analysis Results
 ; GCN-O3-NEXT:       Natural Loop Information
 ; GCN-O3-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O3-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O3-NEXT:       Optimization Remark Emitter
 ; GCN-O3-NEXT:       Combine redundant instructions
 ; GCN-O3-NEXT:       Canonicalize natural loops

 ; GCN-O3-NEXT:       Loop-Closed SSA Form Pass
 ; GCN-O3-NEXT:       Function Alias Analysis Results
 ; GCN-O3-NEXT:       Scalar Evolution Analysis
 ; GCN-O3-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O3-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O3-NEXT:       Loop Pass Manager
 ; GCN-O3-NEXT:         Loop Invariant Code Motion
 ; GCN-O3-NEXT:       Simplify the CFG
-; GCN-O3-NEXT:       Dominator Tree Construction
 ; GCN-O3-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O3-NEXT:       Function Alias Analysis Results
 ; GCN-O3-NEXT:       Natural Loop Information
 ; GCN-O3-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O3-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O3-NEXT:       Optimization Remark Emitter
 ; GCN-O3-NEXT:       Combine redundant instructions
 ; GCN-O3-NEXT:     A No-Op Barrier Pass

 ; GCN-O3-NEXT:       Loop Load Elimination
 ; GCN-O3-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O3-NEXT:       Function Alias Analysis Results
 ; GCN-O3-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O3-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O3-NEXT:       Optimization Remark Emitter
 ; GCN-O3-NEXT:       Combine redundant instructions
 ; GCN-O3-NEXT:       Simplify the CFG
-; GCN-O3-NEXT:       Dominator Tree Construction
 ; GCN-O3-NEXT:       Natural Loop Information
 ; GCN-O3-NEXT:       Scalar Evolution Analysis
 ; GCN-O3-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O3-NEXT:       Function Alias Analysis Results
 ; GCN-O3-NEXT:       Demanded bits analysis
 ; GCN-O3-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O3-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O3-NEXT:       Optimization Remark Emitter

llvm/test/CodeGen/ARM/O3-pipeline.ll

 ; RUN: llc -mtriple=arm -O3 -debug-pass=Structure < %s -o /dev/null 2>&1 | grep -v "Verify generated machine code" | FileCheck %s
 
 ; REQUIRES: asserts
 
 ; CHECK:       ModulePass Manager
 ; CHECK-NEXT:    Pre-ISel Intrinsic Lowering
 ; CHECK-NEXT:    FunctionPass Manager
 ; CHECK-NEXT:      Expand Atomic instructions
-; CHECK-NEXT:      Simplify the CFG
 ; CHECK-NEXT:      Dominator Tree Construction
+; CHECK-NEXT:      Simplify the CFG
 ; CHECK-NEXT:      Natural Loop Information
 ; CHECK-NEXT:      MVE gather/scatter lowering
 ; CHECK-NEXT:      Module Verifier
 ; CHECK-NEXT:      Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:      Canonicalize natural loops
 ; CHECK-NEXT:      Scalar Evolution Analysis
 ; CHECK-NEXT:      Loop Pass Manager
 ; CHECK-NEXT:        Canonicalize Freeze Instructions in Loops

 ; CHECK-NEXT:      Dominator Tree Construction
 ; CHECK-NEXT:      Natural Loop Information
 ; CHECK-NEXT:      CodeGen Prepare
 ; CHECK-NEXT:    Rewrite Symbols
 ; CHECK-NEXT:    FunctionPass Manager
 ; CHECK-NEXT:      Dominator Tree Construction
 ; CHECK-NEXT:      Exception handling preparation
 ; CHECK-NEXT:      Merge internal globals
-; CHECK-NEXT:      Dominator Tree Construction
 ; CHECK-NEXT:      Natural Loop Information
 ; CHECK-NEXT:      Scalar Evolution Analysis
 ; CHECK-NEXT:      Lazy Branch Probability Analysis
 ; CHECK-NEXT:      Lazy Block Frequency Analysis
 ; CHECK-NEXT:      Optimization Remark Emitter
 ; CHECK-NEXT:      Hardware Loop Insertion
 ; CHECK-NEXT:      Scalar Evolution Analysis
 ; CHECK-NEXT:      Loop Pass Manager

llvm/test/Other/new-pm-defaults.ll

 ; CHECK-EP-PIPELINE-START-NEXT: Running pass: NoOpModulePass
 ; CHECK-O-NEXT: Running pass: InferFunctionAttrsPass
 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running analysis: TargetIRAnalysis
 ; CHECK-O-NEXT: Running analysis: AssumptionAnalysis
-; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running pass: EarlyCSEPass
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O-NEXT: Running pass: LowerExpectIntrinsicPass
 ; CHECK-O3-NEXT: Running pass: CallSiteSplittingPass
 ; CHECK-O-NEXT: Finished llvm::Function pass manager run.
 ; CHECK-EP-PIPELINE-EARLY-SIMPLIFICATION-NEXT: Running pass: NoOpModulePass
 ; CHECK-O-NEXT: Running pass: IPSCCPPass
 ; CHECK-O-NEXT: Running pass: CalledValuePropagationPass

llvm/test/Other/new-pm-thinlto-defaults.ll

 ; CHECK-POSTLINK-O-NEXT: Running analysis: OptimizationRemarkEmitterAnalysis
 ; CHECK-O-NEXT: Running pass: InferFunctionAttrsPass
 ; CHECK-PRELINK-O-NODIS-NEXT: Running analysis: InnerAnalysisManagerProxy
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running analysis: TargetIRAnalysis
 ; CHECK-O-NEXT: Running analysis: AssumptionAnalysis
-; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running pass: EarlyCSEPass
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O-NEXT: Running pass: LowerExpectIntrinsicPass
 ; CHECK-O3-NEXT: Running pass: CallSiteSplittingPass
 ; CHECK-O-NEXT: Finished llvm::Function pass manager run.
 ; CHECK-POSTLINK-O-NEXT: Running pass: LowerTypeTestsPass
 ; CHECK-O-NEXT: Running pass: IPSCCPPass
 ; CHECK-O-NEXT: Running pass: CalledValuePropagationPass

llvm/test/Other/new-pm-thinlto-postlink-pgo-defaults.ll

 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy
 ; CHECK-O-NEXT: Running analysis: OptimizationRemarkEmitterAnalysis
 ; CHECK-O-NEXT: Running pass: InferFunctionAttrsPass
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O-NEXT: Starting {{.*}}Function pass manager run.
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running analysis: TargetIRAnalysis
 ; CHECK-O-NEXT: Running analysis: AssumptionAnalysis
-; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running pass: EarlyCSEPass
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O-NEXT: Running pass: LowerExpectIntrinsicPass
 ; CHECK-O3-NEXT: Running pass: CallSiteSplittingPass
 ; CHECK-O-NEXT: Finished {{.*}}Function pass manager run.
 ; CHECK-O-NEXT: Running pass: LowerTypeTestsPass
 ; CHECK-O-NEXT: Running pass: IPSCCPPass
 ; CHECK-O-NEXT: Running pass: CalledValuePropagationPass

llvm/test/Other/new-pm-thinlto-postlink-samplepgo-defaults.ll

 ; CHECK-EP-PIPELINE-START-NEXT: Running pass: NoOpModulePass
 ; CHECK-O-NEXT: Running pass: InferFunctionAttrsPass
 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O-NEXT: Starting {{.*}}Function pass manager run.
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running analysis: TargetIRAnalysis
 ; CHECK-O-NEXT: Running analysis: AssumptionAnalysis
-; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running pass: EarlyCSEPass
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O-NEXT: Running pass: LowerExpectIntrinsicPass
 ; CHECK-O3-NEXT: Running pass: CallSiteSplittingPass
 ; CHECK-O-NEXT: Running pass: InstCombinePass on foo
 ; CHECK-O-NEXT: Running analysis: OptimizationRemarkEmitterAnalysis on foo
 ; CHECK-O-NEXT: Running analysis: AAManager on foo
 ; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy

llvm/test/Other/new-pm-thinlto-prelink-pgo-defaults.ll

 ; CHECK-EP-PIPELINE-START-NEXT: Running pass: NoOpModulePass
 ; CHECK-O-NEXT: Running pass: InferFunctionAttrsPass
 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O-NEXT: Starting {{.*}}Function pass manager run.
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running analysis: TargetIRAnalysis
 ; CHECK-O-NEXT: Running analysis: AssumptionAnalysis
-; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running pass: EarlyCSEPass
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O-NEXT: Running pass: LowerExpectIntrinsicPass
 ; CHECK-O3-NEXT: Running pass: CallSiteSplittingPass
 ; CHECK-O-NEXT: Finished {{.*}}Function pass manager run.
 ; CHECK-O-NEXT: Running pass: IPSCCPPass
 ; CHECK-O-NEXT: Running pass: CalledValuePropagationPass
 ; CHECK-O-NEXT: Running pass: GlobalOptPass

llvm/test/Other/new-pm-thinlto-prelink-samplepgo-defaults.ll

 ; CHECK-O-NEXT: Running pass: AddDiscriminatorsPass
 ; CHECK-EP-PIPELINE-START-NEXT: Running pass: NoOpModulePass
 ; CHECK-O-NEXT: Running pass: InferFunctionAttrsPass
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O-NEXT: Starting {{.*}}Function pass manager run.
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running analysis: TargetIRAnalysis
 ; CHECK-O-NEXT: Running analysis: AssumptionAnalysis
-; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running pass: EarlyCSEPass
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O-NEXT: Running pass: LowerExpectIntrinsicPass
 ; CHECK-O3-NEXT: Running pass: CallSiteSplittingPass
 ; CHECK-O-NEXT: Running pass: InstCombinePass on foo
 ; CHECK-O-NEXT: Running analysis: OptimizationRemarkEmitterAnalysis on foo
 ; CHECK-O-NEXT: Running analysis: AAManager on foo
 ; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy

llvm/test/Other/opt-LTO-pipeline.ll

 ; CHECK-NEXT:         Unroll loops
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Warn about non-applied transformations
 ; CHECK-NEXT:       Combine redundant instructions
 ; CHECK-NEXT:       Simplify the CFG
 ; CHECK-NEXT:       Sparse Conditional Constant Propagation
-; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
 ; CHECK-NEXT:       Demanded bits analysis
 ; CHECK-NEXT:       Bit-Tracking Dead Code Elimination
 ; CHECK-NEXT:       Optimize scalar/vector ops
 ; CHECK-NEXT:       Scalar Evolution Analysis
 ; CHECK-NEXT:       Alignment from assumptions
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
 ; CHECK-NEXT:       Lazy Value Information Analysis
 ; CHECK-NEXT:       Jump Threading
 ; CHECK-NEXT:     Cross-DSO CFI
 ; CHECK-NEXT:     Lower type metadata
 ; CHECK-NEXT:     Lower type metadata
 ; CHECK-NEXT:     FunctionPass Manager
+; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Simplify the CFG
 ; CHECK-NEXT:     Eliminate Available Externally Globals
 ; CHECK-NEXT:     Dead Global Elimination
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Annotation Remarks
 ; CHECK-NEXT:       Module Verifier
 ; CHECK-NEXT:     Bitcode Writer
 ; CHECK-NEXT: Pass Arguments:

llvm/test/Other/opt-O2-pipeline.ll

 ; RUN: opt -enable-new-pm=0 -mtriple=x86_64-- -O2 -debug-pass=Structure < %s -o /dev/null 2>&1 | FileCheck --check-prefixes=CHECK,%llvmcheckext %s
 
 ; REQUIRES: asserts
 
 ; CHECK-LABEL: Pass Arguments:
 ; CHECK-NEXT: Target Transform Information
 ; CHECK-NEXT: Type-Based Alias Analysis
 ; CHECK-NEXT: Scoped NoAlias Alias Analysis
 ; CHECK-NEXT: Assumption Cache Tracker
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Module Verifier
 ; CHECK-EXT:      Good Bye World Pass
 ; CHECK-NOEXT-NOT:      Good Bye World Pass
 ; CHECK-NEXT:     Instrument function entry/exit with calls to e.g. mcount() (pre inlining)
-; CHECK-NEXT:     Simplify the CFG
 ; CHECK-NEXT:     Dominator Tree Construction
+; CHECK-NEXT:     Simplify the CFG
 ; CHECK-NEXT:     SROA
 ; CHECK-NEXT:     Early CSE
 ; CHECK-NEXT:     Lower 'expect' Intrinsics
 ; CHECK-NEXT: Pass Arguments:
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT: Target Transform Information
 ;             Target Pass Configuration
 ; CHECK:      Type-Based Alias Analysis

 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Early CSE w/ MemorySSA
 ; CHECK-NEXT:         Speculatively execute instructions if target has divergent branches
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Lazy Value Information Analysis
 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Simplify the CFG
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
 ; CHECK-NEXT:         Conditionally eliminate dead library calls

 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Tail Call Elimination
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Reassociate expressions
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Rotate Loops
 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:           Unswitch loops
 ; CHECK-NEXT:         Simplify the CFG
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
 ; CHECK-NEXT:         Canonicalize natural loops

 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:         Simplify the CFG
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
 ; CHECK-NEXT:     A No-Op Barrier Pass

 ; CHECK-NEXT:       Loop Load Elimination
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
 ; CHECK-NEXT:       Simplify the CFG
-; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Scalar Evolution Analysis
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       Demanded bits analysis
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter

llvm/test/Other/opt-O3-pipeline-enable-matrix.ll

 ; RUN: opt -enable-new-pm=0 -O3 -enable-matrix -debug-pass=Structure < %s -o /dev/null 2>&1 | FileCheck %s
 
 ; REQUIRES: asserts
 
 ; CHECK-LABEL: Pass Arguments:
 ; CHECK-NEXT: Target Transform Information
 ; CHECK-NEXT: Type-Based Alias Analysis
 ; CHECK-NEXT: Scoped NoAlias Alias Analysis
 ; CHECK-NEXT: Assumption Cache Tracker
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Module Verifier
 ; CHECK-EXT:      Good Bye World Pass
 ; CHECK-NOEXT-NOT:      Good Bye World Pass
 ; CHECK-NEXT:     Instrument function entry/exit with calls to e.g. mcount() (pre inlining)
-; CHECK-NEXT:     Simplify the CFG
 ; CHECK-NEXT:     Dominator Tree Construction
+; CHECK-NEXT:     Simplify the CFG
 ; CHECK-NEXT:     SROA
 ; CHECK-NEXT:     Early CSE
 ; CHECK-NEXT:     Lower 'expect' Intrinsics
 ; CHECK-NEXT: Pass Arguments:
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT: Target Transform Information
 ;             Target Pass Configuration
 ; CHECK:      Type-Based Alias Analysis

 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Early CSE w/ MemorySSA
 ; CHECK-NEXT:         Speculatively execute instructions if target has divergent branches
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Lazy Value Information Analysis
 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Simplify the CFG
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Combine pattern based expressions
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions

 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Tail Call Elimination
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Reassociate expressions
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Rotate Loops
 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:           Unswitch loops
 ; CHECK-NEXT:         Simplify the CFG
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
 ; CHECK-NEXT:         Canonicalize natural loops

 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:         Simplify the CFG
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
 ; CHECK-NEXT:     A No-Op Barrier Pass

 ; CHECK-NEXT:       Loop Load Elimination
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
 ; CHECK-NEXT:       Simplify the CFG
-; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Scalar Evolution Analysis
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       Demanded bits analysis
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter

llvm/test/Other/opt-O3-pipeline.ll

 ; RUN: opt -enable-new-pm=0 -mtriple=x86_64-- -O3 -debug-pass=Structure < %s -o /dev/null 2>&1 | FileCheck --check-prefixes=CHECK,%llvmcheckext %s
 
 ; REQUIRES: asserts
 
 ; CHECK-LABEL: Pass Arguments:
 ; CHECK-NEXT: Target Transform Information
 ; CHECK-NEXT: Type-Based Alias Analysis
 ; CHECK-NEXT: Scoped NoAlias Alias Analysis
 ; CHECK-NEXT: Assumption Cache Tracker
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Module Verifier
 ; CHECK-EXT:      Good Bye World Pass
 ; CHECK-NOEXT-NOT:      Good Bye World Pass
 ; CHECK-NEXT:     Instrument function entry/exit with calls to e.g. mcount() (pre inlining)
-; CHECK-NEXT:     Simplify the CFG
 ; CHECK-NEXT:     Dominator Tree Construction
+; CHECK-NEXT:     Simplify the CFG
 ; CHECK-NEXT:     SROA
 ; CHECK-NEXT:     Early CSE
 ; CHECK-NEXT:     Lower 'expect' Intrinsics
 ; CHECK-NEXT: Pass Arguments:
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT: Target Transform Information
 ;             Target Pass Configuration
 ; CHECK:      Type-Based Alias Analysis

 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Early CSE w/ MemorySSA
 ; CHECK-NEXT:         Speculatively execute instructions if target has divergent branches
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Lazy Value Information Analysis
 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Simplify the CFG
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Combine pattern based expressions
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions

 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Tail Call Elimination
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Reassociate expressions
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Rotate Loops
 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:           Unswitch loops
 ; CHECK-NEXT:         Simplify the CFG
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
 ; CHECK-NEXT:         Canonicalize natural loops

 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:         Simplify the CFG
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
 ; CHECK-NEXT:     A No-Op Barrier Pass

 ; CHECK-NEXT:       Loop Load Elimination
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
 ; CHECK-NEXT:       Simplify the CFG
-; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Scalar Evolution Analysis
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       Demanded bits analysis
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter

llvm/test/Other/opt-Os-pipeline.ll

 ; RUN: opt -enable-new-pm=0 -mtriple=x86_64-- -Os -debug-pass=Structure < %s -o /dev/null 2>&1 | FileCheck --check-prefixes=CHECK,%llvmcheckext %s
 
 ; REQUIRES: asserts
 
 ; CHECK-LABEL: Pass Arguments:
 ; CHECK-NEXT: Target Transform Information
 ; CHECK-NEXT: Type-Based Alias Analysis
 ; CHECK-NEXT: Scoped NoAlias Alias Analysis
 ; CHECK-NEXT: Assumption Cache Tracker
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Module Verifier
 ; CHECK-EXT:      Good Bye World Pass
 ; CHECK-NOEXT-NOT:      Good Bye World Pass
 ; CHECK-NEXT:     Instrument function entry/exit with calls to e.g. mcount() (pre inlining)
-; CHECK-NEXT:     Simplify the CFG
 ; CHECK-NEXT:     Dominator Tree Construction
+; CHECK-NEXT:     Simplify the CFG
 ; CHECK-NEXT:     SROA
 ; CHECK-NEXT:     Early CSE
 ; CHECK-NEXT:     Lower 'expect' Intrinsics
 ; CHECK-NEXT: Pass Arguments:
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT: Target Transform Information
 ;             Target Pass Configuration
 ; CHECK:      Type-Based Alias Analysis

 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Early CSE w/ MemorySSA
 ; CHECK-NEXT:         Speculatively execute instructions if target has divergent branches
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Lazy Value Information Analysis
 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Simplify the CFG
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Tail Call Elimination
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Reassociate expressions
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Rotate Loops
 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:           Unswitch loops
 ; CHECK-NEXT:         Simplify the CFG
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
 ; CHECK-NEXT:         Canonicalize natural loops

 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:         Simplify the CFG
-; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
 ; CHECK-NEXT:     A No-Op Barrier Pass

 ; CHECK-NEXT:       Loop Load Elimination
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
 ; CHECK-NEXT:       Simplify the CFG
-; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Scalar Evolution Analysis
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       Demanded bits analysis
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter

llvm/test/Other/pm-pgo-preinline.ll

 ; RUN: opt -disable-verify -enable-new-pm=0 -pgo-kind=pgo-instr-gen-pipeline -mtriple=x86_64-- -Os -debug-pass=Structure < %s -o /dev/null 2>&1 | FileCheck %s --check-prefix=CHECK-Osz
 ; RUN: opt -disable-verify -enable-new-pm=0 -pgo-kind=pgo-instr-gen-pipeline -mtriple=x86_64-- -Oz -debug-pass=Structure < %s -o /dev/null 2>&1 | FileCheck %s --check-prefix=CHECK-Osz
 
 
 ; CHECK-Osz: CallGraph Construction
 ; CHECK-Osz-NEXT: Call Graph SCC Pass Manager
 ; CHECK-Osz-NEXT: Function Integration/Inlining
 ; CHECK-Osz-NEXT: FunctionPass Manager
 ; CHECK-Osz-NEXT: Dominator Tree Construction
 ; CHECK-Osz-NEXT: SROA
 ; CHECK-Osz-NEXT: Early CSE
 ; CHECK-Osz-NEXT: Simplify the CFG
-; CHECK-Osz-NEXT: Dominator Tree Construction
 ; CHECK-Osz-NEXT: Basic Alias Analysis (stateless AA impl)
 ; CHECK-Osz-NEXT: Function Alias Analysis Results
 ; CHECK-Osz-NEXT: Natural Loop Information
 ; CHECK-Osz-NEXT: Lazy Branch Probability Analysis
 ; CHECK-Osz-NEXT: Lazy Block Frequency Analysis
 ; CHECK-Osz-NEXT: Optimization Remark Emitter
 ; CHECK-Osz-NEXT: Combine redundant instructions
 
 define void @foo() {
   ret void
 }