Mark InstCombine as not preserving CFG

[yrouban]

Summary

A fix for the bug 46098 "PostDominatorTree is different than a freshly computed one!" with opt -branch-prob -instcombine -block-freq -verify-dom-info

InstCombine invalidates PostDomTree.
See the example in the new test llvm/test/Transforms/InstCombine/infinite-loop-postdom.ll

In general InstCombine swapping successors violates the 2nd rule of PreserveCFG: do not change block terminators in any way. Doing so InstCombine also invalidates DFS numbering, which is a part of DomTree.

This patch reflects these by reporting not preserving CFG.

[lebedev.ri]

Which fold is at fault here?
Can it be simply taught to update domtree?

[nikic]

This seems pretty fishy to me. InstCombine is CFG-preserving by design, so it really shouldn't be invalidating any domtrees.

[davide]

I really think this is wrong. If InstCombine doesn't preserve PostDOM, it should be fixed to fix it.

[kuhar]

As a quick fix, maybe we could try to detect changes in reverse-unreachable code and update postdominators when that's detected? Not sure how much overhead that would be; InstCombine is already very expensive w.r.t. compilation times.

A couple of questions I'm asking myself:

1. How is CFG preservation actually defined? Can we have a verification pass that checks if passes lie about preserving CFG? A similar issue was a source of many bugs in machine IR that we fixed last Fall.
2. Making root finding insensitive to the order of successors would eliminate some needles recalculations that happen in other places too, provided the alternative ordering is cheap to compute. How can we canonicalize the order of successors? Sorting by BB names doesn't seem like the best idea to me.

I think that whatever the fix ends up being, we should make sure the compilation times are not noticeably regressed before committing changes.

[asbirlea]

I don't think the solution is to not preserve PDom either.
I think your suggestion from the description is spot-on though: "A better fix would be to improve PostDomTree to be insensitive to the order of successors in post-dom unreachable subgraphs." This is indeed an issue with the order of basic blocks when dealing with infinite loops.

[yrouban]

In D81089#2071195, @lebedev.ri wrote:

Which fold is at fault here?
Can it be simply taught to update domtree?

There is no way to update for successors switch. It would be a noop for the updater.

[lebedev.ri]

In D81089#2084784, @yrouban wrote:

In D81089#2071195, @lebedev.ri wrote:

Which fold is at fault here?
Can it be simply taught to update domtree?

There is no way to update for successors switch. It would be a noop for the updater.

Then i'd agree with @asbirlea

In D81089#2072329, @asbirlea wrote:

I don't think the solution is to not preserve PDom either.
I think your suggestion from the description is spot-on though: "A better fix would be to improve PostDomTree to be insensitive to the order of successors in post-dom unreachable subgraphs." This is indeed an issue with the order of basic blocks when dealing with infinite loops.

[efriedma]

Even if we agree the way the PostDominatorTree computes roots in cases involving infinite loops shouldn't depend on the ordering of successors, I'm not sure it's correct to say that instcombine "preserves the CFG". Even for the regular DominatorTree, I think reordering the successors invalidates DFS numbering (in the sense that it changes the result of getDFSNumIn()).

In terms of how the PostDominatorTree should decide what a "root" is, I'm not sure there's any good way to make that decision. Given an SCC which doesn't have any natural parent, you can pick any node in that SCC as the "fake root", and there isn't any natural reason to favor one node over another.

Really, the natural choice is to just follow the standard dominator algorithm and say the nodes are unreachable. Then for passes which want it, we can add a transform to mutate the CFG to introduce fake roots.

[yrouban]

In D81089#2086290, @efriedma wrote:

Even if we agree the way the PostDominatorTree computes roots in cases involving infinite loops shouldn't depend on the ordering of successors, I'm not sure it's correct to say that instcombine "preserves the CFG". Even for the regular DominatorTree, I think reordering the successors invalidates DFS numbering (in the sense that it changes the result of getDFSNumIn()).

In terms of how the PostDominatorTree should decide what a "root" is, I'm not sure there's any good way to make that decision. Given an SCC which doesn't have any natural parent, you can pick any node in that SCC as the "fake root", and there isn't any natural reason to favor one node over another.

Really, the natural choice is to just follow the standard dominator algorithm and say the nodes are unreachable. Then for passes which want it, we can add a transform to mutate the CFG to introduce fake roots.

Good point! In other words, if DFSNum was a separate CFG base analysis (and it is as a part of DomTree), it must be invalidated.
@lebedev.ri This shows that making the PostDomTree better will not help.
I will stick to invalidating all CFG analyses in InstCombine only if successors are reordered. I believe we should do this to fix the bug. A better solution can be implemented later on.

[yrouban]

• Made legacy InstCombine pass to unconditionally report changing CFG
• New Pass Manager's InstCombine is changed to report changing CFG only if branches were swapped at least once
• Updated tests accordingly

[nikic]

If we define that changing successor order constitutes a CFG change, then these optimizations need to be dropped from InstCombine, and moved into SimplifyCFG.

As said before, InstCombine is supposed to be CFG-preserving -- if it isn't because the definition of what "CFG-preserving" means was unclear, then we need to fix InstCombine to be in line with we new definition.

As the pipeline diffs show, not preserving CFG has a very real cost (five new domtree calculations at least). We should try to avoid that :)

[kuhar]

In D81089#2086290, @efriedma wrote:

Even if we agree the way the PostDominatorTree computes roots in cases involving infinite loops shouldn't depend on the ordering of successors, I'm not sure it's correct to say that instcombine "preserves the CFG". Even for the regular DominatorTree, I think reordering the successors invalidates DFS numbering (in the sense that it changes the result of getDFSNumIn()).

You can always preserve domtrees by marking dfsnumbers as invalid.

In terms of how the PostDominatorTree should decide what a "root" is, I'm not sure there's any good way to make that decision. Given an SCC which doesn't have any natural parent, you can pick any node in that SCC as the "fake root", and there isn't any natural reason to favor one node over another.

Really, the natural choice is to just follow the standard dominator algorithm and say the nodes are unreachable. Then for passes which want it, we can add a transform to mutate the CFG to introduce fake roots.

Daniel B., Tobias G., and myself had a very long discussion about discovering reverse-unreachable nodes or not in postdominators a few years ago. Infinite loops are fairly rare, but can cause very long path that lead to them to be reverse-unreachable as well. This is rather surprising and introduces corner cases in analyzes/optimizations, which can be avoided by shifting this complexity to postdominator construction, while not breaking algorithm that assume the textbook definition of postdominators. As a consequence, you have to chose some arbitrary way of selecting a fake-entry node from nodes in an scc. Right now this order is whatever children or inverse_children return, but could be based on the order of blocks in a function instead.

The issue I see with introducing fake exits is that postdominators is an analysis used by other analyses, and it would be probably complicated to schedule a transformation in front of any analysis that uses postdominators. Even if an analysis doesn't need postdominance info for reverse-unreachable code, it would see a postdominators analysis results for reverse-reachable nodes if a pass running before it introduced them. Note that this would affect all IR-like things that use postdominators, e.g., llvm ir, clang cfg, machine ir, callgraphs, and third-party ir, including irs outside of the monorepo.

[kuhar]

In D81089#2086985, @nikic wrote:

If we define that changing successor order constitutes a CFG change, then these optimizations need to be dropped from InstCombine, and moved into SimplifyCFG.

As said before, InstCombine is supposed to be CFG-preserving -- if it isn't because the definition of what "CFG-preserving" means was unclear, then we need to fix InstCombine to be in line with we new definition.

As the pipeline diffs show, not preserving CFG has a very real cost (five new domtree calculations at least). We should try to avoid that :)

+1

[efriedma]

As the pipeline diffs show, not preserving CFG has a very real cost (five new domtree calculations at least). We should try to avoid that :)

You can always preserve domtrees by marking dfsnumbers as invalid.

I wasn't trying to imply that instcombine couldn't keep the domtree up-to-date; we can easily do that even if instcombine says it doesn't preserve the CFG.

The issue I see with introducing fake exits is that postdominators is an analysis used by other analyses, and it would be probably complicated to schedule a transformation in front of any analysis that uses postdominators. Even if an analysis doesn't need postdominance info for reverse-unreachable code, it would see a postdominators analysis results for reverse-reachable nodes if a pass running before it introduced them. Note that this would affect all IR-like things that use postdominators, e.g., llvm ir, clang cfg, machine ir, callgraphs, and third-party ir, including irs outside of the monorepo.

Yes, this is messy. Maybe it's just too terrible. I think we could come up with some sort of transition plan if necessary; for things that don't need to update the CFG, the downsides of the heuristics are probably less terrible.

In terms of keeping the existing post-dominators working, I guess the "mark the dfsnumbers invalid" API and domtree updates can also recompute the postdominator roots. Not sure how we make that fast, though.

[lebedev.ri]

Glad to see that D84763 is making it's way!

[yrouban]

See D84763.

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

public:
   /// A worklist of the instructions that need to be simplified.
   InstCombineWorklist &Worklist;
 
   /// An IRBuilder that automatically inserts new instructions into the
   /// worklist.
   using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
   BuilderTy &Builder;
 
+  enum Change {
+    // Fully ordered: std::max(Change1, Change2) results in the biggest change.
+    NoChange,
+    PreservedCFG,
+    ChangedCFG
+  };
+
 private:
   // Mode in which we are running the combiner.
   const bool MinimizeSize;
 
   AliasAnalysis *AA;
 
   // Required analyses.
   AssumptionCache &AC;
   TargetLibraryInfo &TLI;
   DominatorTree &DT;
   const DataLayout &DL;
   const SimplifyQuery SQ;
   OptimizationRemarkEmitter &ORE;
   BlockFrequencyInfo *BFI;
   ProfileSummaryInfo *PSI;
 
   // Optional analyses. When non-null, these can both be used to do better
   // combining and will be updated to reflect any changes.
   LoopInfo *LI;
 
-  bool MadeIRChange = false;
+  Change MadeIRChange = Change::NoChange;
 
 public:
   InstCombiner(InstCombineWorklist &Worklist, BuilderTy &Builder,
                bool MinimizeSize, AliasAnalysis *AA,
                AssumptionCache &AC, TargetLibraryInfo &TLI, DominatorTree &DT,
                OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI,
                ProfileSummaryInfo *PSI, const DataLayout &DL, LoopInfo *LI)
       : Worklist(Worklist), Builder(Builder), MinimizeSize(MinimizeSize),
         AA(AA), AC(AC), TLI(TLI), DT(DT),
         DL(DL), SQ(DL, &TLI, &DT, &AC), ORE(ORE), BFI(BFI), PSI(PSI), LI(LI) {}
 
   /// Run the combiner over the entire worklist until it is empty.
-  ///
-  /// \returns true if the IR is changed.
-  bool run();
+  Change run();
 
   AssumptionCache &getAssumptionCache() const { return AC; }
 
   const DataLayout &getDataLayout() const { return DL; }
 
   DominatorTree &getDominatorTree() const { return DT; }
 
   LoopInfo *getLoopInfo() const { return LI; }
Instruction *eraseInstFromFunction(Instruction &I) {
     // Make sure that we reprocess all operands now that we reduced their
     // use counts.
     for (Use &Operand : I.operands())
       if (auto *Inst = dyn_cast<Instruction>(Operand))
         Worklist.add(Inst);
 
     Worklist.remove(&I);
     I.eraseFromParent();
-    MadeIRChange = true;
+    MadeIRChange = std::max(MadeIRChange, Change::PreservedCFG);
+
     return nullptr; // Don't do anything with FI
   }
 
   void computeKnownBits(const Value *V, KnownBits &Known,
                         unsigned Depth, const Instruction *CxtI) const {
     llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT);
   }
 

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

 
 Instruction *InstCombiner::visitBranchInst(BranchInst &BI) {
   // Change br (not X), label True, label False to: br X, label False, True
   Value *X = nullptr;
   if (match(&BI, m_Br(m_Not(m_Value(X)), m_BasicBlock(), m_BasicBlock())) &&
       !isa<Constant>(X)) {
     // Swap Destinations and condition...
     BI.swapSuccessors();
+    MadeIRChange = std::max(MadeIRChange, Change::ChangedCFG);
     return replaceOperand(BI, 0, X);
   }
 
   // If the condition is irrelevant, remove the use so that other
   // transforms on the condition become more effective.
   if (BI.isConditional() && !isa<ConstantInt>(BI.getCondition()) &&
       BI.getSuccessor(0) == BI.getSuccessor(1))
     return replaceOperand(
         BI, 0, ConstantInt::getFalse(BI.getCondition()->getType()));
 
   // Canonicalize, for example, icmp_ne -> icmp_eq or fcmp_one -> fcmp_oeq.
   CmpInst::Predicate Pred;
   if (match(&BI, m_Br(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())),
                       m_BasicBlock(), m_BasicBlock())) &&
       !isCanonicalPredicate(Pred)) {
     // Swap destinations and condition.
     CmpInst *Cond = cast<CmpInst>(BI.getCondition());
     Cond->setPredicate(CmpInst::getInversePredicate(Pred));
     BI.swapSuccessors();
+    MadeIRChange = std::max(MadeIRChange, Change::ChangedCFG);
     Worklist.push(Cond);
     return &BI;
   }
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) {
if (DII->getParent() == SrcBlock) {
         TmpUser[0]->insertBefore(DII);
         DII->moveBefore(&*InsertPos);
       }
     }
   }
   return true;
 }
 
-bool InstCombiner::run() {
+InstCombiner::Change InstCombiner::run() {
   while (!Worklist.isEmpty()) {
     // Walk deferred instructions in reverse order, and push them to the
     // worklist, which means they'll end up popped from the worklist in-order.
     while (Instruction *I = Worklist.popDeferred()) {
       // Check to see if we can DCE the instruction. We do this already here to
       // reduce the number of uses and thus allow other folds to trigger.
       // Note that eraseInstFromFunction() may push additional instructions on
       // the deferred worklist, so this will DCE whole instruction chains.
if (!I->use_empty() &&
         LLVM_DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: " << *I
                           << '\n');
 
         // Add operands to the worklist.
         replaceInstUsesWith(*I, C);
         ++NumConstProp;
         if (isInstructionTriviallyDead(I, &TLI))
           eraseInstFromFunction(*I);
-        MadeIRChange = true;
+        MadeIRChange = std::max(MadeIRChange, Change::PreservedCFG);
         continue;
       }
     }
 
     // See if we can trivially sink this instruction to its user if we can
     // prove that the successor is not executed more frequently than our block.
     if (EnableCodeSinking)
       if (Use *SingleUse = I->getSingleUndroppableUse()) {
if (EnableCodeSinking)
             ShouldSink = isa<ReturnInst>(Term) || isa<UnreachableInst>(Term);
           }
           if (ShouldSink) {
             assert(DT.dominates(BB, UserParent) &&
                    "Dominance relation broken?");
             // Okay, the CFG is simple enough, try to sink this instruction.
             if (TryToSinkInstruction(I, UserParent)) {
               LLVM_DEBUG(dbgs() << "IC: Sink: " << *I << '\n');
-              MadeIRChange = true;
+              MadeIRChange = std::max(MadeIRChange, Change::PreservedCFG);
               // We'll add uses of the sunk instruction below, but since sinking
               // can expose opportunities for it's *operands* add them to the
               // worklist
               for (Use &U : I->operands())
                 if (Instruction *OpI = dyn_cast<Instruction>(U.get()))
                   Worklist.push(OpI);
             }
           }
if (Instruction *Result = visit(*I)) {
         // if so, remove it.
         if (isInstructionTriviallyDead(I, &TLI)) {
           eraseInstFromFunction(*I);
         } else {
           Worklist.pushUsersToWorkList(*I);
           Worklist.push(I);
         }
       }
-      MadeIRChange = true;
+      MadeIRChange = std::max(MadeIRChange, Change::PreservedCFG);
     }
   }
 
   Worklist.zap();
   return MadeIRChange;
 }
 
 /// Populate the IC worklist from a function, by walking it in depth-first
for (Instruction *Inst : reverse(InstrsForInstCombineWorklist)) {
     }
 
     ICWorklist.push(Inst);
   }
 
   return MadeIRChange;
 }
 
-static bool combineInstructionsOverFunction(
+static InstCombiner::Change combineInstructionsOverFunction(
     Function &F, InstCombineWorklist &Worklist, AliasAnalysis *AA,
     AssumptionCache &AC, TargetLibraryInfo &TLI, DominatorTree &DT,
     OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI,
     ProfileSummaryInfo *PSI, unsigned MaxIterations, LoopInfo *LI) {
   auto &DL = F.getParent()->getDataLayout();
   MaxIterations = std::min(MaxIterations, LimitMaxIterations.getValue());
 
   /// Builder - This is an IRBuilder that automatically inserts new
   /// instructions into the worklist when they are created.
   IRBuilder<TargetFolder, IRBuilderCallbackInserter> Builder(
       F.getContext(), TargetFolder(DL),
       IRBuilderCallbackInserter([&Worklist, &AC](Instruction *I) {
         Worklist.add(I);
         if (match(I, m_Intrinsic<Intrinsic::assume>()))
           AC.registerAssumption(cast<CallInst>(I));
       }));
 
   // Lower dbg.declare intrinsics otherwise their value may be clobbered
   // by instcombiner.
-  bool MadeIRChange = false;
+  InstCombiner::Change MadeIRChange = InstCombiner::Change::NoChange;
   if (ShouldLowerDbgDeclare)
-    MadeIRChange = LowerDbgDeclare(F);
+    if (LowerDbgDeclare(F))
+      MadeIRChange = InstCombiner::Change::PreservedCFG;
 
   // Iterate while there is work to do.
   unsigned Iteration = 0;
   while (true) {
     ++Iteration;
 
     if (Iteration > InfiniteLoopDetectionThreshold) {
       report_fatal_error(
           "Instruction Combining seems stuck in an infinite loop after " +
           Twine(InfiniteLoopDetectionThreshold) + " iterations.");
     }
 
     if (Iteration > MaxIterations) {
       LLVM_DEBUG(dbgs() << "\n\n[IC] Iteration limit #" << MaxIterations
                         << " on " << F.getName()
                         << " reached; stopping before reaching a fixpoint\n");
       break;
     }
 
     LLVM_DEBUG(dbgs() << "\n\nINSTCOMBINE ITERATION #" << Iteration << " on "
                       << F.getName() << "\n");
 
-    MadeIRChange |= prepareICWorklistFromFunction(F, DL, &TLI, Worklist);
+    if (prepareICWorklistFromFunction(F, DL, &TLI, Worklist))
+      MadeIRChange = std::max(MadeIRChange, InstCombiner::Change::PreservedCFG);
 
     InstCombiner IC(Worklist, Builder, F.hasMinSize(), AA,
                     AC, TLI, DT, ORE, BFI, PSI, DL, LI);
     IC.MaxArraySizeForCombine = MaxArraySize;
 
-    if (!IC.run())
+    InstCombiner::Change Changed = IC.run();
+    if (Changed == InstCombiner::Change::NoChange)
       break;
 
-    MadeIRChange = true;
+    MadeIRChange = std::max(MadeIRChange, Changed);
   }
 
   return MadeIRChange;
 }
 
 InstCombinePass::InstCombinePass() : MaxIterations(LimitMaxIterations) {}
 
 InstCombinePass::InstCombinePass(unsigned MaxIterations)
PreservedAnalyses InstCombinePass::run(Function &F,
 
   auto *AA = &AM.getResult<AAManager>(F);
   auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
   ProfileSummaryInfo *PSI =
       MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
   auto *BFI = (PSI && PSI->hasProfileSummary()) ?
       &AM.getResult<BlockFrequencyAnalysis>(F) : nullptr;
 
-  if (!combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, DT, ORE, BFI,
-                                       PSI, MaxIterations, LI))
+  InstCombiner::Change Changed = combineInstructionsOverFunction(
+      F, Worklist, AA, AC, TLI, DT, ORE, BFI, PSI, MaxIterations, LI);
+  if (Changed == InstCombiner::Change::NoChange)
     // No changes, all analyses are preserved.
     return PreservedAnalyses::all();
 
   // Mark all the analyses that instcombine updates as preserved.
   PreservedAnalyses PA;
+  if (Changed <= InstCombiner::Change::PreservedCFG)
     PA.preserveSet<CFGAnalyses>();
   PA.preserve<AAManager>();
   PA.preserve<BasicAA>();
   PA.preserve<GlobalsAA>();
   return PA;
 }
 
 void InstructionCombiningPass::getAnalysisUsage(AnalysisUsage &AU) const {
-  AU.setPreservesCFG();
   AU.addRequired<AAResultsWrapperPass>();
   AU.addRequired<AssumptionCacheTracker>();
   AU.addRequired<TargetLibraryInfoWrapperPass>();
   AU.addRequired<DominatorTreeWrapperPass>();
   AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
-  AU.addPreserved<DominatorTreeWrapperPass>();
   AU.addPreserved<AAResultsWrapperPass>();
   AU.addPreserved<BasicAAWrapperPass>();
   AU.addPreserved<GlobalsAAWrapperPass>();
   AU.addRequired<ProfileSummaryInfoWrapperPass>();
   LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU);
 }
 
 bool InstructionCombiningPass::runOnFunction(Function &F) {

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

 ; 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:         Dominator Tree Construction
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Post-Dominator Tree Construction
 ; CHECK-NEXT:         Branch Probability Analysis
 ; CHECK-NEXT:         Block Frequency Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         PGOMemOPSize

 ; 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:         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:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Induction Variable Simplification
 ; CHECK-NEXT:           Recognize loop idioms
 ; CHECK-NEXT:           Delete dead loops

 ; CHECK-NEXT:         Sparse Conditional Constant Propagation
 ; CHECK-NEXT:         Demanded bits analysis
 ; CHECK-NEXT:         Bit-Tracking Dead Code Elimination
 ; 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:         Dominator Tree Construction
 ; CHECK-NEXT:         Lazy Value Information Analysis
 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Phi Values Analysis
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         Dead Store Elimination

 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Inject TLI Mappings
 ; CHECK-NEXT:       SLP Vectorizer
 ; CHECK-NEXT:       Optimize scalar/vector ops
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
+; 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:       Scalar Evolution Analysis
 ; CHECK-NEXT:       Loop Pass Manager
 ; CHECK-NEXT:         Unroll loops
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
+; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Memory SSA
+; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Canonicalize natural loops
 ; CHECK-NEXT:       LCSSA Verifier
 ; CHECK-NEXT:       Loop-Closed SSA Form Pass
 ; CHECK-NEXT:       Scalar Evolution Analysis
 ; CHECK-NEXT:       Loop Pass Manager
 ; CHECK-NEXT:         Loop Invariant Code Motion
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis

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

 ; 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:         Dominator Tree Construction
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Post-Dominator Tree Construction
 ; CHECK-NEXT:         Branch Probability Analysis
 ; CHECK-NEXT:         Block Frequency Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         PGOMemOPSize

 ; 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:         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:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Induction Variable Simplification
 ; CHECK-NEXT:           Recognize loop idioms
 ; CHECK-NEXT:           Delete dead loops

 ; CHECK-NEXT:         Sparse Conditional Constant Propagation
 ; CHECK-NEXT:         Demanded bits analysis
 ; CHECK-NEXT:         Bit-Tracking Dead Code Elimination
 ; 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:         Dominator Tree Construction
 ; CHECK-NEXT:         Lazy Value Information Analysis
 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Phi Values Analysis
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         Dead Store Elimination

 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Inject TLI Mappings
 ; CHECK-NEXT:       SLP Vectorizer
 ; CHECK-NEXT:       Optimize scalar/vector ops
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
+; 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:       Scalar Evolution Analysis
 ; CHECK-NEXT:       Loop Pass Manager
 ; CHECK-NEXT:         Unroll loops
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
+; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Memory SSA
+; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Canonicalize natural loops
 ; CHECK-NEXT:       LCSSA Verifier
 ; CHECK-NEXT:       Loop-Closed SSA Form Pass
 ; CHECK-NEXT:       Scalar Evolution Analysis
 ; CHECK-NEXT:       Loop Pass Manager
 ; CHECK-NEXT:         Loop Invariant Code Motion
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis

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

 ; 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:         Dominator Tree Construction
+; 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:         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:         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:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Induction Variable Simplification
 ; CHECK-NEXT:           Recognize loop idioms
 ; CHECK-NEXT:           Delete dead loops

 ; CHECK-NEXT:         Sparse Conditional Constant Propagation
 ; CHECK-NEXT:         Demanded bits analysis
 ; CHECK-NEXT:         Bit-Tracking Dead Code Elimination
 ; 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:         Dominator Tree Construction
 ; CHECK-NEXT:         Lazy Value Information Analysis
 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Phi Values Analysis
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         Dead Store Elimination

 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Inject TLI Mappings
 ; CHECK-NEXT:       SLP Vectorizer
 ; CHECK-NEXT:       Optimize scalar/vector ops
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
+; 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:       Scalar Evolution Analysis
 ; CHECK-NEXT:       Loop Pass Manager
 ; CHECK-NEXT:         Unroll loops
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
+; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Memory SSA
+; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Canonicalize natural loops
 ; CHECK-NEXT:       LCSSA Verifier
 ; CHECK-NEXT:       Loop-Closed SSA Form Pass
 ; CHECK-NEXT:       Scalar Evolution Analysis
 ; CHECK-NEXT:       Loop Pass Manager
 ; CHECK-NEXT:         Loop Invariant Code Motion
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis

llvm/test/Other/optimization-remarks-invalidation.ll

 ; The purpose of this test is to check that the remark emission analysis result
 ; stays valid when it can and is invalidated otherwise. The code is just
 ; a minimal amount of code to exercise the pass.
 ;
 ; First make sure we emit remarks on this test case.
 ; RUN: opt %s -disable-output -aa-pipeline=basic-aa 2>&1 \
 ; RUN:     -passes='require<opt-remark-emit>,loop(licm)' \
 ; RUN:     -pass-remarks=licm -pass-remarks-with-hotness \
 ; RUN:     | FileCheck %s
 ;
 ; Check that passes which preserve BFI don't invalidate the emitter.
 ; RUN: opt %s -disable-output -aa-pipeline=basic-aa 2>&1 \
-; RUN:     -passes='require<opt-remark-emit>,instcombine,require<opt-remark-emit>,loop(licm)' -debug-pass-manager \
+; RUN:     -passes='require<opt-remark-emit>,instsimplify,require<opt-remark-emit>,loop(licm)' -debug-pass-manager \
 ; RUN:     -pass-remarks=licm -pass-remarks-with-hotness \
 ; RUN:     | FileCheck %s --check-prefixes=CHECK,CHECK-PM-PRESERVE
 ;
 ; Check that invalidating BFI computes a fresh emitter.
 ; RUN: opt %s -disable-output -aa-pipeline=basic-aa 2>&1 \
 ; RUN:     -passes='require<opt-remark-emit>,invalidate<block-freq>,require<opt-remark-emit>,loop(licm)' -debug-pass-manager \
 ; RUN:     -pass-remarks=licm -pass-remarks-with-hotness \
 ; RUN:     | FileCheck %s --check-prefixes=CHECK,CHECK-PM-INVALIDATE
 ;
 ; Check that invalidating BFI desn't compute a fresh emitter when we don't
 ; request hotness remarks.
 ; RUN: opt %s -disable-output -aa-pipeline=basic-aa 2>&1 \
 ; RUN:     -passes='require<opt-remark-emit>,invalidate<block-freq>,require<opt-remark-emit>,loop(licm)' -debug-pass-manager \
 ; RUN:     -pass-remarks=licm \
 ; RUN:     | FileCheck %s --check-prefixes=CHECK,CHECK-PM-NO-INVALIDATE
 
 target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128"
 
 define void @hoist(i32* %array, i32* noalias %p) {
 ; CHECK-PM-PRESERVE: Running analysis: OptimizationRemarkEmitterAnalysis
-; CHECK-PM-PRESERVE: Running pass: InstCombinePass
+; CHECK-PM-PRESERVE: Running pass: InstSimplifyPass
 ; CHECK-PM-PRESERVE-NOT: Invalidating analysis: OptimizationRemarkEmitterAnalysis
 ; CHECK-PM-PRESERVE-NOT: Running analysis: OptimizationRemarkEmitterAnalysis
 ; CHECK-PM-PRESERVE: Running pass: LICMPass
 ; CHECK-PM-INVALIDATE: Running analysis: OptimizationRemarkEmitterAnalysis
 ; CHECK-PM-INVALIDATE: Running pass: InvalidateAnalysisPass
 ; CHECK-PM-INVALIDATE: Invalidating analysis: OptimizationRemarkEmitterAnalysis
 ; CHECK-PM-INVALIDATE: Running analysis: OptimizationRemarkEmitterAnalysis
 ; CHECK-PM-INVALIDATE: Running pass: LICMPass
 ; CHECK-PM-NO-INVALIDATE: Running analysis: OptimizationRemarkEmitterAnalysis
 ; CHECK-PM-NO-INVALIDATE: Running pass: InvalidateAnalysisPass
 ; CHECK-PM-NO-INVALIDATE-NOT: Invalidating analysis: OptimizationRemarkEmitterAnalysis
 ; CHECK-PM-NO-INVALIDATE-NOT: Running analysis: OptimizationRemarkEmitterAnalysis
 ; CHECK-PM-NO-INVALIDATE: Running pass: LICMPass
 
 Entry:
   br label %Loop
 
 Loop:
   %j = phi i32 [ 0, %Entry ], [ %Next, %Loop ]
-  %addr = getelementptr i32, i32* %array, i32 %j
+  %arr = getelementptr i32, i32* %array, i32 0
+  %addr = getelementptr i32, i32* %arr, i32 %j
   %a = load i32, i32* %addr
 ; CHECK: remark: /tmp/kk.c:2:20: hoisting load
   %b = load i32, i32* %p, !dbg !8
   %a2 = add i32 %a, %b
   store i32 %a2, i32* %addr
   %Next = add i32 %j, 1
   %cond = icmp eq i32 %Next, 0
   br i1 %cond, label %Out, label %Loop

llvm/test/Transforms/InstCombine/infinite-loop-postdom.ll

+; RUN: opt < %s -postdomtree -analyze | FileCheck %s
+; RUN: opt < %s -passes='print<postdomtree>' 2>&1 | FileCheck %s
+; RUN: opt < %s -disable-output -branch-prob -instcombine -block-freq -verify-dom-info
+
+; Show that Predicate Canonicalization (InstCombine) invalidates PostDomTree
+; if the basic block is post-dom unreachable.
+;
+define void @test1(i24 %a, i24 %b) {
+entry:
+  br label %LOOP
+
+LOOP:
+  %f = icmp uge i24 %a, %b
+  br i1 %f, label %B1, label %B2
+
+B1:
+  br label %B2
+
+B2:
+  br label %LOOP
+}
+
+; The same as @test1 except the LOOP condition canonicalized (as by instcombine).
+define void @test2(i24 %a, i24 %b) {
+entry:
+  br label %LOOP
+
+LOOP:
+  %f = icmp ult i24 %a, %b
+  br i1 %f, label %B2, label %B1
+
+B1:
+  br label %B2
+
+B2:
+  br label %LOOP
+}
+
+; PostDomTrees are different.
+
+; CHECK-LABEL: test1
+; CHECK-NEXT: =============================--------------------------------
+; CHECK-NEXT: Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries.
+; CHECK-NEXT:   [1]  <<exit node>>
+; CHECK-NEXT:     [2] %B2
+; CHECK-NEXT:       [3] %LOOP
+; CHECK-NEXT:         [4] %entry
+; CHECK-NEXT:       [3] %B1
+; CHECK-NEXT: Roots: %B2
+
+; CHECK-LABEL: test2
+; CHECK-NEXT: =============================--------------------------------
+; CHECK-NEXT: Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries.
+; CHECK-NEXT:   [1]  <<exit node>>
+; CHECK-NEXT:     [2] %B1
+; CHECK-NEXT:       [3] %LOOP
+; CHECK-NEXT:         [4] %entry
+; CHECK-NEXT:         [4] %B2
+; CHECK-NEXT: Roots: %B1