[PM] Introduce an analysis set used to preserve all analyses over a function's CFG when that CFG is unchanged.

[chandlerc]

Summary

This allows transformation passes to simply claim they preserve the CFG
and analysis passes to check for the CFG being preserved to remove the
fanout of all analyses being listed in all passes.

I've gone through and removed or cleaned up as many of the comments
reminding us to do this as I could.

The name for this set is ... *TERRIBLE* though. And so is the name for the
static helper function that builds one of these. I'd really lik suggestions on
better names here as I drew a complete blank. Especially if they'll be
consistent and pattern nicely with the other examples we have. These are
especially easy for me to rename.

[davide]

I'm so glad to see this happening =)
First round of comments.

lib/Transforms/InstCombine/InstructionCombining.cpp

3180–3181 ↗

(On Diff #84182)

The fact that we preserve now GlobalsAA and AAManager is an unrelated change, I guess? (can be committed separately).

lib/Transforms/Scalar/DCE.cpp

127–128 ↗

(On Diff #84182)

this comment is too trivial to be useful.

lib/Transforms/Scalar/IndVarSimplify.cpp

2497 ↗

(On Diff #84182)

Why std::move() here?

lib/Transforms/Scalar/LoopRotation.cpp

637 ↗

(On Diff #84182)

Unrelated?

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

72 ↗

(On Diff #84182)

Unrelated?

lib/Transforms/Scalar/LoopUnrollPass.cpp

1133 ↗

(On Diff #84182)

Unrelated?

lib/Transforms/Scalar/NaryReassociate.cpp

168–169 ↗

(On Diff #84182)

Remove the FIXME.

[davide]

lib/Transforms/Scalar/GuardWidening.cpp

662–663 ↗

(On Diff #84182)

hmm, this doesn't seem to have a FIXME but it's supposed to preserve the CFG analyses, so good that you caught it (here and elsewhere).

[davide]

lib/Analysis/BlockFrequencyInfo.cpp

135–143 ↗

(On Diff #84182)

The class of invalidate functions share a decent amount of code, maybe we can factor it out somehow?

[jlebar]

include/llvm/IR/PassManager.h

98 ↗

(On Diff #84182)

This analysis set doesn't really "represent the CFG of a function". It's like AllAnalysesOn above; it "represents analyses that only look at functions' control flow graphs (and therefore are preserved if the CFG is unchanged)".

105 ↗

(On Diff #84182)

Can you clarify what you mean by "mutating a basic block"? I would think that adding (say) an add instruction to a BB does not affect the CFG, but does "mutate" the BB.

106 ↗

(On Diff #84182)

You could call it CFGAnalyses? If at some point we wanted to preserve the CFG plus call graph in every function in a module, we could call that "GlobalCFGAnalyses" and I don't think that would be particularly strange.

I don't think we need to keep with the AllAnalysesOnFoo idiom. It makes sense for AllAnalysesOn<IRUnitT> (although if you wanted to drop the "All" I'd be ok with that), but that's mainly because of the position of the template parameter.

170 ↗

(On Diff #84182)

I actually think we should get rid of these two helpers and make the code more verbose, on the theory that there should be One Way to Do It. Otherwise every time we add a new analysis set, we have to ask whether it belongs as a static function in here, and in any case our code is going to be inconsistent, with half using the one way and half using the other... Also seeing the helper makes me ask the question, "is this different somehow than the trivial implementation I expected?"

lib/Analysis/BlockFrequencyInfo.cpp

135–143 ↗

(On Diff #84182)

The way I think of it, this here is how we list the things that preserve BlockFrequencyInfo. "Factoring out" the code somehow would mean we changed the invalidator API somehow.

When I did an earlier review, I suggested not even calling invalidate() if we know a priori that the pass is preserved (I guess that would correspond to PAC.preserved() || PAC.preservedSet<AllAnalysesOn<IRUnitT>>())). Chandler explained at the time why this wouldn't work. I don't quite remember, but IIRC the problem isn't with analyses but with transformation passes, which want to do work inside invalidate(). I think it's a decent simplification if we keep the analysis and transformation invalidate functions close together, even if it means we have to write a bit more boilerplate.

[davide]

lib/Analysis/BlockFrequencyInfo.cpp

135–143 ↗

(On Diff #84182)

Fair enough.

[chandlerc]

Update based on review comments including moving to the newly suggested name.

[davide]

There are still a bunch of unrelated newline/whitespace changes in Loop passes. Revert them, and this looks good to me. Thanks for your patience!

[chandlerc]

One more comment update that I missed.

[chandlerc]

Thanks for all of the great review comments! Patch is updated, see responses below.

include/llvm/IR/PassManager.h

98 ↗

(On Diff #84182)

Tried to reword, lemme know if you like.

105 ↗

(On Diff #84182)

Sorry, I meant mutating the *set* of BBs. IE, adding or removing BBs. I also made the branch mutation comment much more accurate and precise (I hope).

106 ↗

(On Diff #84182)

Done, and thanks!

lib/Analysis/BlockFrequencyInfo.cpp

135–143 ↗

(On Diff #84182)

The reason just not calling these functions doesn't work is that we need to call these functions to handle dependencies between analyses.

I agree however that this is essentially the listing of dependencies and sets. If there is a more concise and simple way of writing the code however, I'm all for it.

I tried several variations to get a single method call on PreservedAnalyses, but they weren't actually easier to read.

lib/Transforms/InstCombine/InstructionCombining.cpp

3180–3181 ↗

(On Diff #84182)

Yeah, I just noticed when reading the code. I'll pull this into a separate commit as there is also a FIXME above that would be good to resolve at the same time.

lib/Transforms/Scalar/GuardWidening.cpp

662–663 ↗

(On Diff #84182)

I tried to audit all passes which have a setPreservesCFG for the legacy PM and a run function definition for the new PM, and add this to them.

lib/Transforms/Scalar/IndVarSimplify.cpp

2497 ↗

(On Diff #84182)

Because i didn't remove it before mailing. Gone now.

lib/Transforms/Scalar/LoopRotation.cpp

637 ↗

(On Diff #84182)

I was just making all of these look the same. I'm happy to split it into a separate patch if you want, but didn't seem worthwhile..

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

72 ↗

(On Diff #84182)

See above. Will follow whatever pattern you want.

lib/Transforms/Scalar/LoopUnrollPass.cpp

1133 ↗

(On Diff #84182)

See above.

[davide]

Sorry, phab was slow and I didn't get your last mail. I think it's not worth splitting the newline changes separately, now that I understand your intention. LGTM, again.

[jlebar]

I like it!

include/llvm/IR/PassManager.h

105 ↗

(On Diff #84182)

Yes, this comment is much better now.

[silvas]

I couldn't come up with a good name for this either. I described a design in my log here: https://docs.google.com/document/d/1-nrq2y_hTiZhrsJDmH8TzFjFEeApfccs6wwGyaXjSkg/edit#heading=h.ut7bc0x07mmh

There the naming in my sketch there was super crazy verbose. E.g. the analysis key object for each "set" would be called AnalysesThatOnlyDependOnTheCFG and I guess what I was thinking was to have a convention of accessing the raw keys through simple wrapper functions called invalidateMeIfIAmAnAnalysisThat... (which allowed for sets to easily "inherit" from each other; I didn't record any really compelling use case for this so I'm not sure what the value is).

[silvas]

It would be good to build up some verification machinery here at some point in the future.

lib/Transforms/InstCombine/InstructionCombining.cpp

3180 ↗

(On Diff #84471)

Is this actually true? I've seen InstCombine rewrite a switch. I know we *want* it to be true, but I'm not sure if it is right now.

[chandlerc]

I also imagined using very verbose / explicit names. But I'm happy (enough) with Justin's nice, short name. I don't think it'll ever become really ambiguous and it needs to be short given how much it gets used.

lib/Transforms/InstCombine/InstructionCombining.cpp

3180 ↗

(On Diff #84471)

The question is whether it preserves the edge relationships and the set of BBs.

It can fold constants into branch conditions and otherwise restructure the *values* in a switch all it wants.

But more importantly perhaps, this matches exactly what the legacy PM does. So if there are bugs here, they exactly match existing bugs. =] I don't want the new PM to diverge here.

[chandlerc]

(FYI, going ahead and landing this as both Justin and Davide are happy. I'm more than happy to continue discussing any concerns around instcombine though)

llvm/trunk/include/llvm/Analysis/BlockFrequencyInfo.h

public:
   BlockFrequencyInfo(const Function &F, const BranchProbabilityInfo &BPI,
                      const LoopInfo &LI);
   BlockFrequencyInfo(BlockFrequencyInfo &&Arg);
 
   BlockFrequencyInfo &operator=(BlockFrequencyInfo &&RHS);
 
   ~BlockFrequencyInfo();
 
+  /// Handle invalidation explicitly.
+  bool invalidate(Function &F, const PreservedAnalyses &PA,
+                  FunctionAnalysisManager::Invalidator &);
+
   const Function *getFunction() const;
   const BranchProbabilityInfo *getBPI() const;
   void view() const;
 
   /// getblockFreq - Return block frequency. Return 0 if we don't have the
   /// information. Please note that initial frequency is equal to ENTRY_FREQ. It
   /// means that we should not rely on the value itself, but only on the
   /// comparison to the other block frequencies. We do this to avoid using of

llvm/trunk/include/llvm/Analysis/DominanceFrontier.h

 
 class DominanceFrontier : public ForwardDominanceFrontierBase<BasicBlock> {
 public:
   typedef DominatorTreeBase<BasicBlock> DomTreeT;
   typedef DomTreeNodeBase<BasicBlock> DomTreeNodeT;
   typedef DominanceFrontierBase<BasicBlock>::DomSetType DomSetType;
   typedef DominanceFrontierBase<BasicBlock>::iterator iterator;
   typedef DominanceFrontierBase<BasicBlock>::const_iterator const_iterator;
+
+  /// Handle invalidation explicitly.
+  bool invalidate(Function &F, const PreservedAnalyses &PA,
+                  FunctionAnalysisManager::Invalidator &);
 };
 
 class DominanceFrontierWrapperPass : public FunctionPass {
   DominanceFrontier DF;
 public:
   static char ID; // Pass ID, replacement for typeid
 
   DominanceFrontierWrapperPass();

llvm/trunk/include/llvm/Analysis/LoopInfo.h

public:
   explicit LoopInfo(const DominatorTreeBase<BasicBlock> &DomTree);
 
   LoopInfo(LoopInfo &&Arg) : BaseT(std::move(static_cast<BaseT &>(Arg))) {}
   LoopInfo &operator=(LoopInfo &&RHS) {
     BaseT::operator=(std::move(static_cast<BaseT &>(RHS)));
     return *this;
   }
 
+  /// Handle invalidation explicitly.
+  bool invalidate(Function &F, const PreservedAnalyses &PA,
+                  FunctionAnalysisManager::Invalidator &);
+
   // Most of the public interface is provided via LoopInfoBase.
 
   /// Update LoopInfo after removing the last backedge from a loop. This updates
   /// the loop forest and parent loops for each block so that \c L is no longer
   /// referenced, but does not actually delete \c L immediately. The pointer
   /// will remain valid until this LoopInfo's memory is released.
   void markAsRemoved(Loop *L);
 

llvm/trunk/include/llvm/Analysis/PostDominators.h

 
 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
 /// compute the post-dominator tree.
 ///
 struct PostDominatorTree : public DominatorTreeBase<BasicBlock> {
   typedef DominatorTreeBase<BasicBlock> Base;
 
   PostDominatorTree() : DominatorTreeBase<BasicBlock>(true) {}
+
+  /// Handle invalidation explicitly.
+  bool invalidate(Function &F, const PreservedAnalyses &PA,
+                  FunctionAnalysisManager::Invalidator &);
 };
 
 /// \brief Analysis pass which computes a \c PostDominatorTree.
 class PostDominatorTreeAnalysis
     : public AnalysisInfoMixin<PostDominatorTreeAnalysis> {
   friend AnalysisInfoMixin<PostDominatorTreeAnalysis>;
   static AnalysisKey Key;
 

llvm/trunk/include/llvm/Analysis/RegionInfo.h

public:
 
   RegionInfo(RegionInfo &&Arg)
     : Base(std::move(static_cast<Base &>(Arg))) {}
   RegionInfo &operator=(RegionInfo &&RHS) {
     Base::operator=(std::move(static_cast<Base &>(RHS)));
     return *this;
   }
 
+  /// Handle invalidation explicitly.
+  bool invalidate(Function &F, const PreservedAnalyses &PA,
+                  FunctionAnalysisManager::Invalidator &);
+
   // updateStatistics - Update statistic about created regions.
   void updateStatistics(Region *R) final;
 
   void recalculate(Function &F, DominatorTree *DT, PostDominatorTree *PDT,
                    DominanceFrontier *DF);
 
 #ifndef NDEBUG
   /// @brief Opens a viewer to show the GraphViz visualization of the regions.

llvm/trunk/include/llvm/IR/Dominators.h

 public:
   typedef DominatorTreeBase<BasicBlock> Base;
 
   DominatorTree() : DominatorTreeBase<BasicBlock>(false) {}
   explicit DominatorTree(Function &F) : DominatorTreeBase<BasicBlock>(false) {
     recalculate(F);
   }
 
+  /// Handle invalidation explicitly.
+  bool invalidate(Function &F, const PreservedAnalyses &PA,
+                  FunctionAnalysisManager::Invalidator &);
+
   /// \brief Returns *false* if the other dominator tree matches this dominator
   /// tree.
   inline bool compare(const DominatorTree &Other) const {
     const DomTreeNode *R = getRootNode();
     const DomTreeNode *OtherR = Other.getRootNode();
 
     if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
       return true;

llvm/trunk/include/llvm/IR/PassManager.h

 /// preserved.
 ///
 /// For example, a transformation can indicate that it preserves the CFG of a
 /// function by preserving the appropriate AnalysisSetKey.  An analysis that
 /// depends only on the CFG can then check if that AnalysisSetKey is preserved;
 /// if it is, the analysis knows that it itself is preserved.
 struct alignas(8) AnalysisSetKey {};
 
+/// This templated class represents "all analyses that operate over \<a
+/// particular IR unit\>" (e.g. a Function or a Module) in instances of
+/// PreservedAnalysis.
+///
+/// This lets a transformation say e.g. "I preserved all function analyses".
+///
+/// Note that you must provide an explicit instantiation declaration and
+/// definition for this template in order to get the correct behavior on
+/// Windows. Otherwise, the address of SetKey will not be stable.
+template <typename IRUnitT> class AllAnalysesOn {
+public:
+  static AnalysisSetKey *ID() { return &SetKey; }
+
+private:
+  static AnalysisSetKey SetKey;
+};
+
+template <typename IRUnitT> AnalysisSetKey AllAnalysesOn<IRUnitT>::SetKey;
+
+extern template class AllAnalysesOn<Module>;
+extern template class AllAnalysesOn<Function>;
+
+/// Represents analyses that only rely on functions' control flow.
+///
+/// This can be used with \c PreservedAnalyses to mark the CFG as preserved and
+/// to query whether it has been preserved.
+///
+/// The CFG of a function is defined as the set of basic blocks and the edges
+/// between them. Changing the set of basic blocks in a function is enough to
+/// mutate the CFG. Mutating the condition of a branch or argument of an
+/// invoked function does not mutate the CFG, but changing the successor labels
+/// of those instructions does.
+class CFGAnalyses {
+public:
+  static AnalysisSetKey *ID() { return &SetKey; }
+
+private:
+  static AnalysisSetKey SetKey;
+};
+
 /// A set of analyses that are preserved following a run of a transformation
 /// pass.
 ///
 /// Transformation passes build and return these objects to communicate which
 /// analyses are still valid after the transformation. For most passes this is
 /// fairly simple: if they don't change anything all analyses are preserved,
 /// otherwise only a short list of analyses that have been explicitly updated
 /// are preserved.
struct AnalysisInfoMixin : PassInfoMixin<DerivedT> {
   /// is that some compilers cannot correctly unique a templated static variable
   /// so it has the same addresses in each instantiation. The only currently
   /// known platform with this limitation is Windows DLL builds, specifically
   /// building each part of LLVM as a DLL. If we ever remove that build
   /// configuration, this mixin can provide the static key as well.
   static AnalysisKey *ID() { return &DerivedT::Key; }
 };
 
-/// This templated class represents "all analyses that operate over \<a
-/// particular IR unit\>" (e.g. a Function or a Module) in instances of
-/// PreservedAnalysis.
-///
-/// This lets a transformation say e.g. "I preserved all function analyses".
-///
-/// Note that you must provide an explicit instantiation declaration and
-/// definition for this template in order to get the correct behavior on
-/// Windows. Otherwise, the address of SetKey will not be stable.
-template <typename IRUnitT>
-class AllAnalysesOn {
-public:
-  static AnalysisSetKey *ID() { return &SetKey; }
-
-private:
-  static AnalysisSetKey SetKey;
-};
-
-template <typename IRUnitT> AnalysisSetKey AllAnalysesOn<IRUnitT>::SetKey;
-
-extern template class AllAnalysesOn<Module>;
-extern template class AllAnalysesOn<Function>;
-
 /// \brief Manages a sequence of passes over a particular unit of IR.
 ///
 /// A pass manager contains a sequence of passes to run over a particular unit
 /// of IR (e.g. Functions, Modules). It is itself a valid pass over that unit of
 /// IR, and when run over some given IR will run each of its contained passes in
 /// sequence. Pass managers are the primary and most basic building block of a
 /// pass pipeline.
 ///

llvm/trunk/lib/Analysis/BlockFrequencyInfo.cpp

 }
 
 // Explicitly define the default constructor otherwise it would be implicitly
 // defined at the first ODR-use which is the BFI member in the
 // LazyBlockFrequencyInfo header.  The dtor needs the BlockFrequencyInfoImpl
 // template instantiated which is not available in the header.
 BlockFrequencyInfo::~BlockFrequencyInfo() {}
 
+bool BlockFrequencyInfo::invalidate(Function &F, const PreservedAnalyses &PA,
+                                    FunctionAnalysisManager::Invalidator &) {
+  // Check whether the analysis, all analyses on functions, or the function's
+  // CFG have been preserved.
+  auto PAC = PA.getChecker<BlockFrequencyAnalysis>();
+  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
+           PAC.preservedSet<CFGAnalyses>());
+}
+
 void BlockFrequencyInfo::calculate(const Function &F,
                                    const BranchProbabilityInfo &BPI,
                                    const LoopInfo &LI) {
   if (!BFI)
     BFI.reset(new ImplType);
   BFI->calculate(F, BPI, LI);
 #ifndef NDEBUG
   if (ViewBlockFreqPropagationDAG != GVDT_None &&

llvm/trunk/lib/Analysis/DominanceFrontier.cpp

 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void DominanceFrontierWrapperPass::dump() const {
   print(dbgs());
 }
 #endif
 
+/// Handle invalidation explicitly.
+bool DominanceFrontier::invalidate(Function &F, const PreservedAnalyses &PA,
+                                   FunctionAnalysisManager::Invalidator &) {
+  // Check whether the analysis, all analyses on functions, or the function's
+  // CFG have been preserved.
+  auto PAC = PA.getChecker<DominanceFrontierAnalysis>();
+  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
+           PAC.preservedSet<CFGAnalyses>());
+}
+
 AnalysisKey DominanceFrontierAnalysis::Key;
 
 DominanceFrontier DominanceFrontierAnalysis::run(Function &F,
                                                  FunctionAnalysisManager &AM) {
   DominanceFrontier DF;
   DF.analyze(AM.getResult<DominatorTreeAnalysis>(F));
   return DF;
 }

llvm/trunk/lib/Analysis/LoopInfo.cpp

Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
   }
   return NearLoop;
 }
 
 LoopInfo::LoopInfo(const DominatorTreeBase<BasicBlock> &DomTree) {
   analyze(DomTree);
 }
 
+bool LoopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
+                          FunctionAnalysisManager::Invalidator &) {
+  // Check whether the analysis, all analyses on functions, or the function's
+  // CFG have been preserved.
+  auto PAC = PA.getChecker<LoopAnalysis>();
+  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
+           PAC.preservedSet<CFGAnalyses>());
+}
+
 void LoopInfo::markAsRemoved(Loop *Unloop) {
   assert(!Unloop->isInvalid() && "Loop has already been removed");
   Unloop->invalidate();
   RemovedLoops.push_back(Unloop);
 
   // First handle the special case of no parent loop to simplify the algorithm.
   if (!Unloop->getParentLoop()) {
     // Since BBLoop had no parent, Unloop blocks are no longer in a loop.

llvm/trunk/lib/Analysis/PostDominators.cpp

 //===----------------------------------------------------------------------===//
 //  PostDominatorTree Implementation
 //===----------------------------------------------------------------------===//
 
 char PostDominatorTreeWrapperPass::ID = 0;
 INITIALIZE_PASS(PostDominatorTreeWrapperPass, "postdomtree",
                 "Post-Dominator Tree Construction", true, true)
 
+bool PostDominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
+                                   FunctionAnalysisManager::Invalidator &) {
+  // Check whether the analysis, all analyses on functions, or the function's
+  // CFG have been preserved.
+  auto PAC = PA.getChecker<PostDominatorTreeAnalysis>();
+  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
+           PAC.preservedSet<CFGAnalyses>());
+}
+
 bool PostDominatorTreeWrapperPass::runOnFunction(Function &F) {
   DT.recalculate(F);
   return false;
 }
 
 void PostDominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
   DT.print(OS);
 }

llvm/trunk/lib/Analysis/RegionInfo.cpp

RegionInfo::RegionInfo() :
   RegionInfoBase<RegionTraits<Function>>() {
 
 }
 
 RegionInfo::~RegionInfo() {
 
 }
 
+bool RegionInfo::invalidate(Function &F, const PreservedAnalyses &PA,
+                            FunctionAnalysisManager::Invalidator &) {
+  // Check whether the analysis, all analyses on functions, or the function's
+  // CFG have been preserved.
+  auto PAC = PA.getChecker<RegionInfoAnalysis>();
+  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
+           PAC.preservedSet<CFGAnalyses>());
+}
+
 void RegionInfo::updateStatistics(Region *R) {
   ++numRegions;
 
   // TODO: Slow. Should only be enabled if -stats is used.
   if (R->isSimple())
     ++numSimpleRegions;
 }
 

llvm/trunk/lib/IR/Dominators.cpp

DominatorTreeBase<
         typename std::remove_pointer<GraphTraits<BasicBlock *>::NodeRef>::type>
         &DT,
     Function &F);
 template void llvm::Calculate<Function, Inverse<BasicBlock *>>(
     DominatorTreeBase<typename std::remove_pointer<
         GraphTraits<Inverse<BasicBlock *>>::NodeRef>::type> &DT,
     Function &F);
 
+bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,
+                               FunctionAnalysisManager::Invalidator &) {
+  // Check whether the analysis, all analyses on functions, or the function's
+  // CFG have been preserved.
+  auto PAC = PA.getChecker<DominatorTreeAnalysis>();
+  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
+           PAC.preservedSet<CFGAnalyses>());
+}
+
 // dominates - Return true if Def dominates a use in User. This performs
 // the special checks necessary if Def and User are in the same basic block.
 // Note that Def doesn't dominate a use in Def itself!
 bool DominatorTree::dominates(const Instruction *Def,
                               const Instruction *User) const {
   const BasicBlock *UseBB = User->getParent();
   const BasicBlock *DefBB = Def->getParent();
 

llvm/trunk/lib/IR/PassManager.cpp

if (!AreFunctionAnalysesPreserved)
       InnerAM->invalidate(F, PA);
   }
 
   // Return false to indicate that this result is still a valid proxy.
   return false;
 }
 }
 
+AnalysisSetKey CFGAnalyses::SetKey;
+
 AnalysisSetKey PreservedAnalyses::AllAnalysesKey;

llvm/trunk/lib/Transforms/InstCombine/InstructionCombining.cpp

PreservedAnalyses InstCombinePass::run(Function &F,
 
   // FIXME: The AliasAnalysis is not yet supported in the new pass manager
   if (!combineInstructionsOverFunction(F, Worklist, nullptr, AC, TLI, DT,
                                        ExpensiveCombines, LI))
     // No changes, all analyses are preserved.
     return PreservedAnalyses::all();
 
   // Mark all the analyses that instcombine updates as preserved.
-  // FIXME: This should also 'preserve the CFG'.
   PreservedAnalyses PA;
+  PA.preserveSet<CFGAnalyses>();
   PA.preserve<AAManager>();
-  PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<GlobalsAA>();
   return PA;
 }
 
 void InstructionCombiningPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesCFG();
   AU.addRequired<AAResultsWrapperPass>();
   AU.addRequired<AssumptionCacheTracker>();

llvm/trunk/lib/Transforms/Scalar/ADCE.cpp

 // Pass Manager integration code
 //
 //===----------------------------------------------------------------------===//
 PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) {
   auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F);
   if (!AggressiveDeadCodeElimination(F, PDT).performDeadCodeElimination())
     return PreservedAnalyses::all();
 
-  // FIXME: This should also 'preserve the CFG'.
-  auto PA = PreservedAnalyses();
+  PreservedAnalyses PA;
+  PA.preserveSet<CFGAnalyses>();
   PA.preserve<GlobalsAA>();
   return PA;
 }
 
 namespace {
 struct ADCELegacyPass : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
   ADCELegacyPass() : FunctionPass(ID) {

llvm/trunk/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp

AlignmentFromAssumptionsPass::run(Function &F, FunctionAnalysisManager &AM) {
   bool Changed = runImpl(F, AC, &SE, &DT);
 
   // FIXME: We need to invalidate this to avoid PR28400. Is there a better
   // solution?
   AM.invalidate<ScalarEvolutionAnalysis>(F);
 
   if (!Changed)
     return PreservedAnalyses::all();
+
   PreservedAnalyses PA;
+  PA.preserveSet<CFGAnalyses>();
   PA.preserve<AAManager>();
   PA.preserve<ScalarEvolutionAnalysis>();
   PA.preserve<GlobalsAA>();
-  PA.preserve<LoopAnalysis>();
-  PA.preserve<DominatorTreeAnalysis>();
   return PA;
 }

llvm/trunk/lib/Transforms/Scalar/BDCE.cpp

static bool bitTrackingDCE(Function &F, DemandedBits &DB) {
   return Changed;
 }
 
 PreservedAnalyses BDCEPass::run(Function &F, FunctionAnalysisManager &AM) {
   auto &DB = AM.getResult<DemandedBitsAnalysis>(F);
   if (!bitTrackingDCE(F, DB))
     return PreservedAnalyses::all();
 
-  // FIXME: This should also 'preserve the CFG'.
-  auto PA = PreservedAnalyses();
+  PreservedAnalyses PA;
+  PA.preserveSet<CFGAnalyses>();
   PA.preserve<GlobalsAA>();
   return PA;
 }
 
 namespace {
 struct BDCELegacyPass : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
   BDCELegacyPass() : FunctionPass(ID) {

llvm/trunk/lib/Transforms/Scalar/ConstantHoisting.cpp

 
 PreservedAnalyses ConstantHoistingPass::run(Function &F,
                                             FunctionAnalysisManager &AM) {
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
   if (!runImpl(F, TTI, DT, F.getEntryBlock()))
     return PreservedAnalyses::all();
 
-  // FIXME: This should also 'preserve the CFG'.
-  return PreservedAnalyses::none();
+  PreservedAnalyses PA;
+  PA.preserveSet<CFGAnalyses>();
+  return PA;
 }

llvm/trunk/lib/Transforms/Scalar/DCE.cpp

static bool eliminateDeadCode(Function &F, TargetLibraryInfo *TLI) {
   while (!WorkList.empty()) {
     Instruction *I = WorkList.pop_back_val();
     MadeChange |= DCEInstruction(I, WorkList, TLI);
   }
   return MadeChange;
 }
 
 PreservedAnalyses DCEPass::run(Function &F, FunctionAnalysisManager &AM) {
-  if (eliminateDeadCode(F, AM.getCachedResult<TargetLibraryAnalysis>(F)))
-    return PreservedAnalyses::none();
+  if (!eliminateDeadCode(F, AM.getCachedResult<TargetLibraryAnalysis>(F)))
     return PreservedAnalyses::all();
+
+  PreservedAnalyses PA;
+  PA.preserveSet<CFGAnalyses>();
+  return PA;
 }
 
 namespace {
 struct DCELegacyPass : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
   DCELegacyPass() : FunctionPass(ID) {
     initializeDCELegacyPassPass(*PassRegistry::getPassRegistry());
   }

llvm/trunk/lib/Transforms/Scalar/DeadStoreElimination.cpp

 PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) {
   AliasAnalysis *AA = &AM.getResult<AAManager>(F);
   DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F);
   MemoryDependenceResults *MD = &AM.getResult<MemoryDependenceAnalysis>(F);
   const TargetLibraryInfo *TLI = &AM.getResult<TargetLibraryAnalysis>(F);
 
   if (!eliminateDeadStores(F, AA, MD, DT, TLI))
     return PreservedAnalyses::all();
+
   PreservedAnalyses PA;
-  PA.preserve<DominatorTreeAnalysis>();
+  PA.preserveSet<CFGAnalyses>();
   PA.preserve<GlobalsAA>();
   PA.preserve<MemoryDependenceAnalysis>();
   return PA;
 }
 
 namespace {
 /// A legacy pass for the legacy pass manager that wraps \c DSEPass.
 class DSELegacyPass : public FunctionPass {

llvm/trunk/lib/Transforms/Scalar/EarlyCSE.cpp

PreservedAnalyses EarlyCSEPass::run(Function &F,
   auto *MSSA =
       UseMemorySSA ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA() : nullptr;
 
   EarlyCSE CSE(TLI, TTI, DT, AC, MSSA);
 
   if (!CSE.run())
     return PreservedAnalyses::all();
 
-  // CSE preserves the dominator tree because it doesn't mutate the CFG.
-  // FIXME: Bundle this with other CFG-preservation.
   PreservedAnalyses PA;
-  PA.preserve<DominatorTreeAnalysis>();
+  PA.preserveSet<CFGAnalyses>();
   PA.preserve<GlobalsAA>();
   if (UseMemorySSA)
     PA.preserve<MemorySSAAnalysis>();
   return PA;
 }
 
 namespace {
 /// \brief A simple and fast domtree-based CSE pass.

llvm/trunk/lib/Transforms/Scalar/Float2Int.cpp

 }
 
 namespace llvm {
 FunctionPass *createFloat2IntPass() { return new Float2IntLegacyPass(); }
 
 PreservedAnalyses Float2IntPass::run(Function &F, FunctionAnalysisManager &) {
   if (!runImpl(F))
     return PreservedAnalyses::all();
-  else {
-    // FIXME: This should also 'preserve the CFG'.
-    PreservedAnalyses PA;
-    PA.preserve<GlobalsAA>();
-    return PA;
-  }
-}
+
+  PA.preserveSet<CFGAnalyses>();
 } // End namespace llvm

llvm/trunk/lib/Transforms/Scalar/GuardWidening.cpp

bool GuardWideningImpl::combineRangeChecks(
   return RangeChecksOut.size() != OldCount;
 }
 
 PreservedAnalyses GuardWideningPass::run(Function &F,
                                          FunctionAnalysisManager &AM) {
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &LI = AM.getResult<LoopAnalysis>(F);
   auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
-  bool Changed = GuardWideningImpl(DT, PDT, LI).run();
-  return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
+  if (!GuardWideningImpl(DT, PDT, LI).run())
+    return PreservedAnalyses::all();
+
+  PreservedAnalyses PA;
+  PA.preserveSet<CFGAnalyses>();
+  return PA;
 }
 
 StringRef GuardWideningImpl::scoreTypeToString(WideningScore WS) {
   switch (WS) {
   case WS_IllegalOrNegative:
     return "IllegalOrNegative";
   case WS_Neutral:
     return "Neutral";

llvm/trunk/lib/Transforms/Scalar/IndVarSimplify.cpp

PreservedAnalyses IndVarSimplifyPass::run(Loop &L, LoopAnalysisManager &AM,
                                           LPMUpdater &) {
   Function *F = L.getHeader()->getParent();
   const DataLayout &DL = F->getParent()->getDataLayout();
 
   IndVarSimplify IVS(&AR.LI, &AR.SE, &AR.DT, DL, &AR.TLI, &AR.TTI);
   if (!IVS.run(&L))
     return PreservedAnalyses::all();
 
-  // FIXME: This should also 'preserve the CFG'.
-  return getLoopPassPreservedAnalyses();
+  auto PA = getLoopPassPreservedAnalyses();
+  PA.preserveSet<CFGAnalyses>();
+  return PA;
 }
 
 namespace {
 struct IndVarSimplifyLegacyPass : public LoopPass {
   static char ID; // Pass identification, replacement for typeid
   IndVarSimplifyLegacyPass() : LoopPass(ID) {
     initializeIndVarSimplifyLegacyPassPass(*PassRegistry::getPassRegistry());
   }

llvm/trunk/lib/Transforms/Scalar/LICM.cpp

PreservedAnalyses LICMPass::run(Loop &L, LoopAnalysisManager &AM,
   if (!ORE)
     report_fatal_error("LICM: OptimizationRemarkEmitterAnalysis not "
                        "cached at a higher level");
 
   LoopInvariantCodeMotion LICM;
   if (!LICM.runOnLoop(&L, &AR.AA, &AR.LI, &AR.DT, &AR.TLI, &AR.SE, ORE, true))
     return PreservedAnalyses::all();
 
-  // FIXME: There is no setPreservesCFG in the new PM. When that becomes
-  // available, it should be used here.
-  return getLoopPassPreservedAnalyses();
+  auto PA = getLoopPassPreservedAnalyses();
+  PA.preserveSet<CFGAnalyses>();
+  return PA;
 }
 
 char LegacyLICMPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LegacyLICMPass, "licm", "Loop Invariant Code Motion",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_END(LegacyLICMPass, "licm", "Loop Invariant Code Motion", false,

llvm/trunk/lib/Transforms/Scalar/LoopInstSimplify.cpp

 }
 
 PreservedAnalyses LoopInstSimplifyPass::run(Loop &L, LoopAnalysisManager &AM,
                                             LoopStandardAnalysisResults &AR,
                                             LPMUpdater &) {
   if (!SimplifyLoopInst(&L, &AR.DT, &AR.LI, &AR.AC, &AR.TLI))
     return PreservedAnalyses::all();
 
-  return getLoopPassPreservedAnalyses();
+  auto PA = getLoopPassPreservedAnalyses();
+  PA.preserveSet<CFGAnalyses>();
+  return PA;
 }
 
 char LoopInstSimplifyLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopInstSimplifyLegacyPass, "loop-instsimplify",
                       "Simplify instructions in loops", false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_END(LoopInstSimplifyLegacyPass, "loop-instsimplify",
                     "Simplify instructions in loops", false, false)
 
 Pass *llvm::createLoopInstSimplifyPass() {
   return new LoopInstSimplifyLegacyPass();
 }

llvm/trunk/lib/Transforms/Scalar/LoopRotation.cpp

PreservedAnalyses LoopRotatePass::run(Loop &L, LoopAnalysisManager &AM,
                                       LoopStandardAnalysisResults &AR,
                                       LPMUpdater &) {
   int Threshold = EnableHeaderDuplication ? DefaultRotationThreshold : 0;
   LoopRotate LR(Threshold, &AR.LI, &AR.TTI, &AR.AC, &AR.DT, &AR.SE);
 
   bool Changed = LR.processLoop(&L);
   if (!Changed)
     return PreservedAnalyses::all();
+
   return getLoopPassPreservedAnalyses();
 }
 
 namespace {
 
 class LoopRotateLegacyPass : public LoopPass {
   unsigned MaxHeaderSize;
 

llvm/trunk/lib/Transforms/Scalar/LoopSimplifyCFG.cpp

static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI) {
   return Changed;
 }
 
 PreservedAnalyses LoopSimplifyCFGPass::run(Loop &L, LoopAnalysisManager &AM,
                                            LoopStandardAnalysisResults &AR,
                                            LPMUpdater &) {
   if (!simplifyLoopCFG(L, AR.DT, AR.LI))
     return PreservedAnalyses::all();
+
   return getLoopPassPreservedAnalyses();
 }
 
 namespace {
 class LoopSimplifyCFGLegacyPass : public LoopPass {
 public:
   static char ID; // Pass ID, replacement for typeid
   LoopSimplifyCFGLegacyPass() : LoopPass(ID) {

llvm/trunk/lib/Transforms/Scalar/LoopUnrollPass.cpp

PreservedAnalyses LoopUnrollPass::run(Loop &L, LoopAnalysisManager &AM,
   if (!ORE)
     report_fatal_error("LoopUnrollPass: OptimizationRemarkEmitterAnalysis not "
                        "cached at a higher level");
 
   bool Changed = tryToUnrollLoop(&L, AR.DT, &AR.LI, &AR.SE, AR.TTI, AR.AC, *ORE,
                                  /*PreserveLCSSA*/ true, ProvidedCount,
                                  ProvidedThreshold, ProvidedAllowPartial,
                                  ProvidedRuntime, ProvidedUpperBound);
-
   if (!Changed)
     return PreservedAnalyses::all();
+
   return getLoopPassPreservedAnalyses();
 }

llvm/trunk/lib/Transforms/Scalar/MemCpyOptimizer.cpp

PreservedAnalyses MemCpyOptPass::run(Function &F, FunctionAnalysisManager &AM) {
   auto LookupDomTree = [&]() -> DominatorTree & {
     return AM.getResult<DominatorTreeAnalysis>(F);
   };
 
   bool MadeChange = runImpl(F, &MD, &TLI, LookupAliasAnalysis,
                             LookupAssumptionCache, LookupDomTree);
   if (!MadeChange)
     return PreservedAnalyses::all();
+
   PreservedAnalyses PA;
+  PA.preserveSet<CFGAnalyses>();
   PA.preserve<GlobalsAA>();
   PA.preserve<MemoryDependenceAnalysis>();
   return PA;
 }
 
 bool MemCpyOptPass::runImpl(
     Function &F, MemoryDependenceResults *MD_, TargetLibraryInfo *TLI_,
     std::function<AliasAnalysis &()> LookupAliasAnalysis_,

llvm/trunk/lib/Transforms/Scalar/MergedLoadStoreMotion.cpp

 PreservedAnalyses
 MergedLoadStoreMotionPass::run(Function &F, FunctionAnalysisManager &AM) {
   MergedLoadStoreMotion Impl;
   auto *MD = AM.getCachedResult<MemoryDependenceAnalysis>(F);
   auto &AA = AM.getResult<AAManager>(F);
   if (!Impl.run(F, MD, AA))
     return PreservedAnalyses::all();
 
-  // FIXME: This should also 'preserve the CFG'.
   PreservedAnalyses PA;
+  PA.preserveSet<CFGAnalyses>();
   PA.preserve<GlobalsAA>();
   PA.preserve<MemoryDependenceAnalysis>();
   return PA;
 }

llvm/trunk/lib/Transforms/Scalar/NaryReassociate.cpp

PreservedAnalyses NaryReassociatePass::run(Function &F,
 
   // FIXME: We need to invalidate this to avoid PR28400. Is there a better
   // solution?
   AM.invalidate<ScalarEvolutionAnalysis>(F);
 
   if (!Changed)
     return PreservedAnalyses::all();
 
-  // FIXME: This should also 'preserve the CFG'.
   PreservedAnalyses PA;
-  PA.preserve<DominatorTreeAnalysis>();
+  PA.preserveSet<CFGAnalyses>();
   PA.preserve<ScalarEvolutionAnalysis>();
-  PA.preserve<TargetLibraryAnalysis>();
   return PA;
 }
 
 bool NaryReassociatePass::runImpl(Function &F, AssumptionCache *AC_,
                                   DominatorTree *DT_, ScalarEvolution *SE_,
                                   TargetLibraryInfo *TLI_,
                                   TargetTransformInfo *TTI_) {
   AC = AC_;

llvm/trunk/lib/Transforms/Scalar/Reassociate.cpp

for (BasicBlock *BI : RPOT) {
     }
   }
 
   // We are done with the rank map.
   RankMap.clear();
   ValueRankMap.clear();
 
   if (MadeChange) {
-    // FIXME: This should also 'preserve the CFG'.
-    auto PA = PreservedAnalyses();
+    PreservedAnalyses PA;
+    PA.preserveSet<CFGAnalyses>();
     PA.preserve<GlobalsAA>();
     return PA;
   }
 
   return PreservedAnalyses::all();
 }
 
 namespace {

llvm/trunk/lib/Transforms/Scalar/SROA.cpp

do {
 
     Worklist = PostPromotionWorklist;
     PostPromotionWorklist.clear();
   } while (!Worklist.empty());
 
   if (!Changed)
     return PreservedAnalyses::all();
 
-  // FIXME: Even when promoting allocas we should preserve some abstract set of
-  // CFG-specific analyses.
   PreservedAnalyses PA;
+  PA.preserveSet<CFGAnalyses>();
   PA.preserve<GlobalsAA>();
   return PA;
 }
 
 PreservedAnalyses SROA::run(Function &F, FunctionAnalysisManager &AM) {
   return runImpl(F, AM.getResult<DominatorTreeAnalysis>(F),
                  AM.getResult<AssumptionAnalysis>(F));
 }

llvm/trunk/lib/Transforms/Scalar/Sink.cpp

 PreservedAnalyses SinkingPass::run(Function &F, FunctionAnalysisManager &AM) {
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &LI = AM.getResult<LoopAnalysis>(F);
   auto &AA = AM.getResult<AAManager>(F);
 
   if (!iterativelySinkInstructions(F, DT, LI, AA))
     return PreservedAnalyses::all();
 
-  auto PA = PreservedAnalyses();
-  PA.preserve<DominatorTreeAnalysis>();
-  PA.preserve<LoopAnalysis>();
+  PreservedAnalyses PA;
+  PA.preserveSet<CFGAnalyses>();
   return PA;
 }
 
 namespace {
   class SinkingLegacyPass : public FunctionPass {
   public:
     static char ID; // Pass identification
     SinkingLegacyPass() : FunctionPass(ID) {

llvm/trunk/lib/Transforms/Utils/LCSSA.cpp

 
 PreservedAnalyses LCSSAPass::run(Function &F, FunctionAnalysisManager &AM) {
   auto &LI = AM.getResult<LoopAnalysis>(F);
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto *SE = AM.getCachedResult<ScalarEvolutionAnalysis>(F);
   if (!formLCSSAOnAllLoops(&LI, DT, SE))
     return PreservedAnalyses::all();
 
-  // FIXME: This should also 'preserve the CFG'.
   PreservedAnalyses PA;
+  PA.preserveSet<CFGAnalyses>();
   PA.preserve<BasicAA>();
   PA.preserve<GlobalsAA>();
   PA.preserve<SCEVAA>();
   PA.preserve<ScalarEvolutionAnalysis>();
   return PA;
 }

llvm/trunk/lib/Transforms/Utils/Mem2Reg.cpp

 }
 
 PreservedAnalyses PromotePass::run(Function &F, FunctionAnalysisManager &AM) {
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   if (!promoteMemoryToRegister(F, DT, AC))
     return PreservedAnalyses::all();
 
-  // FIXME: This should also 'preserve the CFG'.
-  return PreservedAnalyses::none();
+  PreservedAnalyses PA;
+  PA.preserveSet<CFGAnalyses>();
+  return PA;
 }
 
 namespace {
 struct PromoteLegacyPass : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
   PromoteLegacyPass() : FunctionPass(ID) {
     initializePromoteLegacyPassPass(*PassRegistry::getPassRegistry());
   }

llvm/trunk/lib/Transforms/Utils/SimplifyInstructions.cpp

 PreservedAnalyses InstSimplifierPass::run(Function &F,
                                       FunctionAnalysisManager &AM) {
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   bool Changed = runImpl(F, &DT, &TLI, &AC);
   if (!Changed)
     return PreservedAnalyses::all();
-  // FIXME: This should also 'preserve the CFG'.
-  return PreservedAnalyses::none();
+
+  PreservedAnalyses PA;
+  PA.preserveSet<CFGAnalyses>();
+  return PA;
 }

llvm/trunk/lib/Transforms/Vectorize/SLPVectorizer.cpp

PreservedAnalyses SLPVectorizerPass::run(Function &F, FunctionAnalysisManager &AM) {
   auto *LI = &AM.getResult<LoopAnalysis>(F);
   auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
   auto *AC = &AM.getResult<AssumptionAnalysis>(F);
   auto *DB = &AM.getResult<DemandedBitsAnalysis>(F);
 
   bool Changed = runImpl(F, SE, TTI, TLI, AA, LI, DT, AC, DB);
   if (!Changed)
     return PreservedAnalyses::all();
+
   PreservedAnalyses PA;
-  PA.preserve<LoopAnalysis>();
-  PA.preserve<DominatorTreeAnalysis>();
+  PA.preserveSet<CFGAnalyses>();
   PA.preserve<AAManager>();
   PA.preserve<GlobalsAA>();
   return PA;
 }
 
 bool SLPVectorizerPass::runImpl(Function &F, ScalarEvolution *SE_,
                                 TargetTransformInfo *TTI_,
                                 TargetLibraryInfo *TLI_, AliasAnalysis *AA_,