[SCCP] Calculate Null Pointer Comparisons

[njw45]

Summary

Loading from a null pointer is undefined; the SimplifyCfg pass correctly decides that any conditional branches that lead to a null pointer derefence can't be taken, and so replaces them with an unconditional branch. We can go further though; if the branch in question post-dominates the Value used to decide which branch to take, then we know exactly what constant that is everywhere in the function. If the Value is a cmp instruction, then we don't need to evaluate it any more - this patch replaces all uses of the comparison with the known constant and removes the unneeded instruction.

[• dberlin]

This looks generally good.

Do you have any numbers on how often it triggers/helps?
Same with compilation time cost.

It would be nice to know both. The first should be easy, just adding another Statistic to the top and looking at it.

[sanjoy]

I'm not sure that this is doing the right thing -- I don't think simply producing undef implies undefined behavior.

For instance, in

declare void @g()

define i1 @test_postdominate(i8* %mem) {
  %test = icmp eq i8* %mem, null
  br i1 %test, label %a, label %b
a:
  call void @g()
  br label %c
b:
  br label %c
c:
  %join = phi i8* [ %mem, %a ], [ null, %b ]
  %gep = getelementptr inbounds i8, i8* %join, i64 4
  ret i1 %test
}

if %mem is null, then we have to execute the call to @g, but this pass make the branch into a dead (so @f never calls @g). The fact that %gep is undef (or poison) does not make this program undefined. In fact, if inbounds GEP instructions could invoke UB, then we would not be able to hoist such instructions out of loops.

[njw45]

Change to SimplifyCFG, not SCCP

[njw45]

Does it make sense to make simplifycfg smarter instead of sccp?

Yes - that makes the code change much smaller (no need for a custom
visitor)! I've pushed a (completely) new version of the patch to
http://reviews.llvm.org/D9634 . Thanks -

Nick

[reames]

Please provide a real description of the change. You'll need a submission comment eventually, please write that and add it to the review. Also, please update the title. This is not specific to null checks.

lib/Transforms/Utils/SimplifyCFG.cpp

4632

This is wrong since the condition may not be in the same basic block as the branch we're reasoning about. You can replace dominated uses, but not all uses.

You might find these changes interesting:
http://reviews.llvm.org/D9312 - this ones directly analogous in JumpThreading.
http://reviews.llvm.org/D9763 - this prunes a lot of easy cases earlier in the pipeline, possibly removing a bunch of pass ordering problems

[njw45]

Ensure we only replace the conditional if we postdominate it (+test)

[njw45]

Please provide a real description of the change.

I've updated the review description - hope it's OK now!

You can replace dominated uses

Ah yes, I've carried that functionality forward from the SCCP version
of the patch. Unfortunately the SimplifyCFG pass has been updated to
use the new pass manager, but the post-dominator tree analysis hasn't,
so this patch now converts it to too (so it's now +250 -157). I've
also added another unit test to prove that it doesn't do the
optimisation when the branch doesn't post-dominate the test.

Thanks -

Nick

[njw45]

remove trailing whitespace from test

[reames]

To my knowledge, post-dominance information is not currently used within LLVM's existing passes. As a result, you'd need to justify the cost of the post-dom-tree computation.

I strongly request that you implement the trivial post dominance case (i.e. in same basic block as per the linked patch) to start with. If you then want to propose using post-dominance information more widely, I'm open to that discussion. I just don't want to couple of the optimization at hand with a broader (and harder to justify) discussion.

Once the optimizations in, we could either enhance it by pursuing the post-dominance information or by using the replaceDominatesUses mechanism from GVN and (soon) EarlyCSE.

p.s. You haven't updated any of the existing transforms to keep the post dominance info up to date. As a result, the code as currently structured is really, really wrong.

p.p.s. Your description mentions icmps. I don't get why you're making the restriction. Regardless of the source, you know the value of the Value. Your actual code doesn't seem to have this restriction.

lib/Transforms/Scalar/SampleProfile.cpp

100

I think you've mixed patches here?

[reames]

Removing myself as review from an aparently abandoned review. Feel free to readd me as a reviewer for new updates. I'm only removing so that I don't see this in my list of pending reviews.

include/llvm/Analysis/PostDominators.h

 
 #ifndef LLVM_ANALYSIS_POSTDOMINATORS_H
 #define LLVM_ANALYSIS_POSTDOMINATORS_H
 
 #include "llvm/IR/Dominators.h"
 
 namespace llvm {
 
-/// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
-/// compute the post-dominator tree.
-///
-struct PostDominatorTree : public FunctionPass {
-  static char ID; // Pass identification, replacement for typeid
-  DominatorTreeBase<BasicBlock>* DT;
-
-  PostDominatorTree() : FunctionPass(ID) {
-    initializePostDominatorTreePass(*PassRegistry::getPassRegistry());
-    DT = new DominatorTreeBase<BasicBlock>(true);
-  }
-
-  ~PostDominatorTree() override;
-
-  bool runOnFunction(Function &F) override;
-
-  void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.setPreservesAll();
+/// PostDominatorTree Class - Concrete subclass of DominatorTreeBase that is
+/// used to compute the post-dominator tree.
+struct PostDominatorTree : public DominatorTreeBase<BasicBlock> {
+public:
+  typedef DominatorTreeBase<BasicBlock> Base;
+
+  PostDominatorTree() : DominatorTreeBase<BasicBlock>(true) {}
+
+  PostDominatorTree(PostDominatorTree &&Arg)
+      : Base(std::move(static_cast<Base &>(Arg))) {}
+  PostDominatorTree &operator=(PostDominatorTree &&RHS) {
+    Base::operator=(std::move(static_cast<Base &>(RHS)));
+    return *this;
   }
+};
 
-  inline const std::vector<BasicBlock*> &getRoots() const {
-    return DT->getRoots();
-  }
+FunctionPass *createPostDomTree();
 
-  inline DomTreeNode *getRootNode() const {
+template <>
+struct GraphTraits<PostDominatorTree *> : public GraphTraits<DomTreeNode *> {
+  static NodeType *getEntryNode(PostDominatorTree *DT) {
     return DT->getRootNode();
   }
 
-  inline DomTreeNode *operator[](BasicBlock *BB) const {
-    return DT->getNode(BB);
-  }
-
-  inline DomTreeNode *getNode(BasicBlock *BB) const {
-    return DT->getNode(BB);
+  static nodes_iterator nodes_begin(PostDominatorTree *N) {
+    if (getEntryNode(N))
+      return df_begin(getEntryNode(N));
+    else
+      return df_end(getEntryNode(N));
   }
 
-  inline bool dominates(DomTreeNode* A, DomTreeNode* B) const {
-    return DT->dominates(A, B);
+  static nodes_iterator nodes_end(PostDominatorTree *N) {
+    return df_end(getEntryNode(N));
   }
+};
 
-  inline bool dominates(const BasicBlock* A, const BasicBlock* B) const {
-    return DT->dominates(A, B);
-  }
+/// \brief Analysis pass which computes a \c PostDominatorTree.
+class PostDominatorTreeAnalysis {
+public:
+  /// \brief Provide the result typedef for this analysis pass.
+  typedef PostDominatorTree Result;
+
+  /// \brief Opaque, unique identifier for this analysis pass.
+  static void *ID() { return (void *)&PassID; }
+
+  /// \brief Run the analysis pass over a function and produce a post-dominator
+  /// tree.
+  PostDominatorTree run(Function &F);
 
-  inline bool properlyDominates(const DomTreeNode* A, DomTreeNode* B) const {
-    return DT->properlyDominates(A, B);
-  }
+  /// \brief Provide access to a name for this pass for debugging purposes.
+  static StringRef name() { return "PostDominatorTreeAnalysis"; }
 
-  inline bool properlyDominates(BasicBlock* A, BasicBlock* B) const {
-    return DT->properlyDominates(A, B);
-  }
-
-  inline BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B) {
-    return DT->findNearestCommonDominator(A, B);
-  }
+private:
+  static char PassID;
+};
 
-  inline const BasicBlock *findNearestCommonDominator(const BasicBlock *A,
-                                                      const BasicBlock *B) {
-    return DT->findNearestCommonDominator(A, B);
-  }
+/// \brief Legacy analysis pass which computes a \c PostDominatorTree.
+class PostDominatorTreePass : public FunctionPass {
+  PostDominatorTree PDT;
 
-  /// Get all nodes post-dominated by R, including R itself.
-  void getDescendants(BasicBlock *R,
-                      SmallVectorImpl<BasicBlock *> &Result) const {
-    DT->getDescendants(R, Result);
-  }
+public:
+  static char ID;
 
-  void releaseMemory() override {
-    DT->releaseMemory();
+  PostDominatorTreePass() : FunctionPass(ID) {
+    initializePostDominatorTreePassPass(*PassRegistry::getPassRegistry());
   }
 
-  void print(raw_ostream &OS, const Module*) const override;
-};
+  PostDominatorTree &getDomTree() { return PDT; }
+  const PostDominatorTree &getDomTree() const { return PDT; }
 
-FunctionPass* createPostDomTree();
+  bool runOnFunction(Function &F) override;
 
-template <> struct GraphTraits<PostDominatorTree*>
-  : public GraphTraits<DomTreeNode*> {
-  static NodeType *getEntryNode(PostDominatorTree *DT) {
-    return DT->getRootNode();
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
   }
 
-  static nodes_iterator nodes_begin(PostDominatorTree *N) {
-    if (getEntryNode(N))
-      return df_begin(getEntryNode(N));
-    else
-      return df_end(getEntryNode(N));
-  }
+  void releaseMemory() override { PDT.releaseMemory(); }
 
-  static nodes_iterator nodes_end(PostDominatorTree *N) {
-    return df_end(getEntryNode(N));
-  }
+  void print(raw_ostream &OS, const Module *) const override;
 };
 
 } // End llvm namespace
 
 #endif

include/llvm/InitializePasses.h

 void initializePEIPass(PassRegistry&);
 void initializePHIEliminationPass(PassRegistry&);
 void initializePartialInlinerPass(PassRegistry&);
 void initializePeepholeOptimizerPass(PassRegistry&);
 void initializePostDomOnlyPrinterPass(PassRegistry&);
 void initializePostDomOnlyViewerPass(PassRegistry&);
 void initializePostDomPrinterPass(PassRegistry&);
 void initializePostDomViewerPass(PassRegistry&);
-void initializePostDominatorTreePass(PassRegistry&);
+void initializePostDominatorTreePassPass(PassRegistry &);
 void initializePostRASchedulerPass(PassRegistry&);
 void initializePostMachineSchedulerPass(PassRegistry&);
 void initializePrintFunctionPassWrapperPass(PassRegistry&);
 void initializePrintModulePassWrapperPass(PassRegistry&);
 void initializePrintBasicBlockPassPass(PassRegistry&);
 void initializeProcessImplicitDefsPass(PassRegistry&);
 void initializePromotePassPass(PassRegistry&);
 void initializePruneEHPass(PassRegistry&);

include/llvm/Transforms/Utils/Local.h

 // This family of functions perform various local transformations to the
 // program.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_LOCAL_H
 #define LLVM_TRANSFORMS_UTILS_LOCAL_H
 
+#include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Operator.h"
 
 namespace llvm {
 
 class User;

 
 /// SimplifyCFG - This function is used to do simplification of a CFG.  For
 /// example, it adjusts branches to branches to eliminate the extra hop, it
 /// eliminates unreachable basic blocks, and does other "peephole" optimization
 /// of the CFG.  It returns true if a modification was made, possibly deleting
 /// the basic block that was pointed to.
 ///
 bool SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
-                 unsigned BonusInstThreshold, AssumptionCache *AC = nullptr);
+                 unsigned BonusInstThreshold, AssumptionCache *AC = nullptr,
+                 PostDominatorTree *PDT = nullptr);
 
 /// FlatternCFG - This function is used to flatten a CFG.  For
 /// example, it uses parallel-and and parallel-or mode to collapse
 //  if-conditions and merge if-regions with identical statements.
 ///
 bool FlattenCFG(BasicBlock *BB, AliasAnalysis *AA = nullptr);
 
 /// FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch,

lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeLazyValueInfoPass(Registry);
   initializeLibCallAliasAnalysisPass(Registry);
   initializeLintPass(Registry);
   initializeLoopInfoWrapperPassPass(Registry);
   initializeMemDepPrinterPass(Registry);
   initializeMemDerefPrinterPass(Registry);
   initializeMemoryDependenceAnalysisPass(Registry);
   initializeModuleDebugInfoPrinterPass(Registry);
-  initializePostDominatorTreePass(Registry);
+  initializePostDominatorTreePassPass(Registry);
   initializeRegionInfoPassPass(Registry);
   initializeRegionViewerPass(Registry);
   initializeRegionPrinterPass(Registry);
   initializeRegionOnlyViewerPass(Registry);
   initializeRegionOnlyPrinterPass(Registry);
   initializeScalarEvolutionPass(Registry);
   initializeScalarEvolutionAliasAnalysisPass(Registry);
   initializeTargetTransformInfoWrapperPassPass(Registry);

lib/Analysis/DivergenceAnalysis.cpp

public:
   static char ID;
 
   DivergenceAnalysis() : FunctionPass(ID) {
     initializeDivergenceAnalysisPass(*PassRegistry::getPassRegistry());
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<DominatorTreeWrapperPass>();
-    AU.addRequired<PostDominatorTree>();
+    AU.addRequired<PostDominatorTreePass>();
     AU.setPreservesAll();
   }
 
   bool runOnFunction(Function &F) override;
 
   // Print all divergent branches in the function.
   void print(raw_ostream &OS, const Module *) const override;
 
   // Returns true if V is divergent.
   bool isDivergent(const Value *V) const { return DivergentValues.count(V); }
   // Returns true if V is uniform/non-divergent.
   bool isUniform(const Value *V) const { return !isDivergent(V); }
 
 private:
   // Stores all divergent values.
   DenseSet<const Value *> DivergentValues;
 };
 } // End of anonymous namespace
 
 // Register this pass.
 char DivergenceAnalysis::ID = 0;
 INITIALIZE_PASS_BEGIN(DivergenceAnalysis, "divergence", "Divergence Analysis",
                       false, true)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
+INITIALIZE_PASS_DEPENDENCY(PostDominatorTreePass)
 INITIALIZE_PASS_END(DivergenceAnalysis, "divergence", "Divergence Analysis",
                     false, true)
 
 namespace {
 
 class DivergencePropagator {
 public:
   DivergencePropagator(Function &F, TargetTransformInfo &TTI,
bool DivergenceAnalysis::runOnFunction(Function &F) {
 
   TargetTransformInfo &TTI = TTIWP->getTTI(F);
   // Fast path: if the target does not have branch divergence, we do not mark
   // any branch as divergent.
   if (!TTI.hasBranchDivergence())
     return false;
 
   DivergentValues.clear();
-  DivergencePropagator DP(F, TTI,
-                          getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
-                          getAnalysis<PostDominatorTree>(), DivergentValues);
+  DivergencePropagator DP(
+      F, TTI, getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
+      getAnalysis<PostDominatorTreePass>().getDomTree(), DivergentValues);
   DP.populateWithSourcesOfDivergence();
   DP.propagate();
   return false;
 }
 
 void DivergenceAnalysis::print(raw_ostream &OS, const Module *) const {
   if (DivergentValues.empty())
     return;

lib/Analysis/DomPrinter.cpp

 
 namespace {
 struct DominatorTreeWrapperPassAnalysisGraphTraits {
   static DominatorTree *getGraph(DominatorTreeWrapperPass *DTWP) {
     return &DTWP->getDomTree();
   }
 };
 
+struct PostDominatorTreePassAnalysisGraphTraits {
+  static PostDominatorTree *getGraph(PostDominatorTreePass *PDTP) {
+    return &PDTP->getDomTree();
+  }
+};
+
 struct DomViewer : public DOTGraphTraitsViewer<
                        DominatorTreeWrapperPass, false, DominatorTree *,
                        DominatorTreeWrapperPassAnalysisGraphTraits> {
   static char ID;
   DomViewer()
       : DOTGraphTraitsViewer<DominatorTreeWrapperPass, false, DominatorTree *,
                              DominatorTreeWrapperPassAnalysisGraphTraits>(
             "dom", ID) {
     initializeDomViewerPass(*PassRegistry::getPassRegistry());
   }
 };
 
 struct DomOnlyViewer : public DOTGraphTraitsViewer<
                            DominatorTreeWrapperPass, true, DominatorTree *,
                            DominatorTreeWrapperPassAnalysisGraphTraits> {
   static char ID;
   DomOnlyViewer()
       : DOTGraphTraitsViewer<DominatorTreeWrapperPass, true, DominatorTree *,
                              DominatorTreeWrapperPassAnalysisGraphTraits>(
             "domonly", ID) {
     initializeDomOnlyViewerPass(*PassRegistry::getPassRegistry());
   }
 };
 
-struct PostDomViewer
-  : public DOTGraphTraitsViewer<PostDominatorTree, false> {
+struct PostDomViewer : public DOTGraphTraitsViewer<
+                           PostDominatorTreePass, false, PostDominatorTree *,
+                           PostDominatorTreePassAnalysisGraphTraits> {
   static char ID;
-  PostDomViewer() :
-    DOTGraphTraitsViewer<PostDominatorTree, false>("postdom", ID){
+  PostDomViewer()
+      : DOTGraphTraitsViewer<PostDominatorTreePass, false, PostDominatorTree *,
+                             PostDominatorTreePassAnalysisGraphTraits>(
+            "postdom", ID) {
       initializePostDomViewerPass(*PassRegistry::getPassRegistry());
     }
 };
 
-struct PostDomOnlyViewer
-  : public DOTGraphTraitsViewer<PostDominatorTree, true> {
+struct PostDomOnlyViewer : public DOTGraphTraitsViewer<
+                               PostDominatorTreePass, true, PostDominatorTree *,
+                               PostDominatorTreePassAnalysisGraphTraits> {
   static char ID;
-  PostDomOnlyViewer() :
-    DOTGraphTraitsViewer<PostDominatorTree, true>("postdomonly", ID){
-      initializePostDomOnlyViewerPass(*PassRegistry::getPassRegistry());
-    }
+  PostDomOnlyViewer()
+      : DOTGraphTraitsViewer<PostDominatorTreePass, true, PostDominatorTree *,
+                             PostDominatorTreePassAnalysisGraphTraits>(
+            "postdomonly", ID) {
 };
 } // end anonymous namespace
 
 char DomViewer::ID = 0;
 INITIALIZE_PASS(DomViewer, "view-dom",
                 "View dominance tree of function", false, false)
 
 char DomOnlyViewer::ID = 0;
struct DomOnlyPrinter : public DOTGraphTraitsPrinter<
   DomOnlyPrinter()
       : DOTGraphTraitsPrinter<DominatorTreeWrapperPass, true, DominatorTree *,
                               DominatorTreeWrapperPassAnalysisGraphTraits>(
             "domonly", ID) {
     initializeDomOnlyPrinterPass(*PassRegistry::getPassRegistry());
   }
 };
 
-struct PostDomPrinter
-  : public DOTGraphTraitsPrinter<PostDominatorTree, false> {
+struct PostDomPrinter : public DOTGraphTraitsPrinter<
+                            PostDominatorTreePass, false, PostDominatorTree *,
+                            PostDominatorTreePassAnalysisGraphTraits> {
   static char ID;
-  PostDomPrinter() :
-    DOTGraphTraitsPrinter<PostDominatorTree, false>("postdom", ID) {
+  PostDomPrinter()
+      : DOTGraphTraitsPrinter<PostDominatorTreePass, false, PostDominatorTree *,
+                              PostDominatorTreePassAnalysisGraphTraits>(
+            "postdom", ID) {
       initializePostDomPrinterPass(*PassRegistry::getPassRegistry());
     }
 };
 
 struct PostDomOnlyPrinter
-  : public DOTGraphTraitsPrinter<PostDominatorTree, true> {
+    : public DOTGraphTraitsPrinter<PostDominatorTreePass, true,
+                                   PostDominatorTree *,
+                                   PostDominatorTreePassAnalysisGraphTraits> {
   static char ID;
-  PostDomOnlyPrinter() :
-    DOTGraphTraitsPrinter<PostDominatorTree, true>("postdomonly", ID) {
+  PostDomOnlyPrinter()
+      : DOTGraphTraitsPrinter<PostDominatorTreePass, true, PostDominatorTree *,
+                              PostDominatorTreePassAnalysisGraphTraits>(
+            "postdomonly", ID) {
       initializePostDomOnlyPrinterPass(*PassRegistry::getPassRegistry());
     }
 };
 } // end anonymous namespace
 
 
 
 char DomPrinter::ID = 0;

lib/Analysis/PostDominators.cpp

 using namespace llvm;
 
 #define DEBUG_TYPE "postdomtree"
 
 //===----------------------------------------------------------------------===//
 //  PostDominatorTree Implementation
 //===----------------------------------------------------------------------===//
 
-char PostDominatorTree::ID = 0;
-INITIALIZE_PASS(PostDominatorTree, "postdomtree",
+char PostDominatorTreePass::ID = 0;
+INITIALIZE_PASS(PostDominatorTreePass, "postdomtree",
                 "Post-Dominator Tree Construction", true, true)
 
-bool PostDominatorTree::runOnFunction(Function &F) {
-  DT->recalculate(F);
+bool PostDominatorTreePass::runOnFunction(Function &F) {
+  PDT.recalculate(F);
   return false;
 }
 
-PostDominatorTree::~PostDominatorTree() {
-  delete DT;
+void PostDominatorTreePass::print(raw_ostream &OS, const Module *) const {
+  PDT.print(OS);
 }
 
-void PostDominatorTree::print(raw_ostream &OS, const Module *) const {
-  DT->print(OS);
-}
+FunctionPass *llvm::createPostDomTree() { return new PostDominatorTreePass(); }
 
+//===----------------------------------------------------------------------===//
+//  PostDominatorTreeAnalysis Implementation
+//===----------------------------------------------------------------------===//
 
-FunctionPass* llvm::createPostDomTree() {
-  return new PostDominatorTree();
+PostDominatorTree PostDominatorTreeAnalysis::run(Function &F) {
+  PostDominatorTree PDT;
+  PDT.recalculate(F);
+  return PDT;
 }
 
+char PostDominatorTreeAnalysis::PassID;

lib/Analysis/RegionInfo.cpp

 RegionInfoPass::~RegionInfoPass() {
 
 }
 
 bool RegionInfoPass::runOnFunction(Function &F) {
   releaseMemory();
 
   auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-  auto PDT = &getAnalysis<PostDominatorTree>();
+  auto PDT = &getAnalysis<PostDominatorTreePass>().getDomTree();
   auto DF = &getAnalysis<DominanceFrontier>();
 
   RI.recalculate(F, DT, PDT, DF);
   return false;
 }
 
 void RegionInfoPass::releaseMemory() {
   RI.releaseMemory();
 }
 
 void RegionInfoPass::verifyAnalysis() const {
     RI.verifyAnalysis();
 }
 
 void RegionInfoPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequiredTransitive<DominatorTreeWrapperPass>();
-  AU.addRequired<PostDominatorTree>();
+  AU.addRequired<PostDominatorTreePass>();
   AU.addRequired<DominanceFrontier>();
 }
 
 void RegionInfoPass::print(raw_ostream &OS, const Module *) const {
   RI.print(OS);
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 void RegionInfoPass::dump() const {
   RI.dump();
 }
 #endif
 
 char RegionInfoPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(RegionInfoPass, "regions",
                 "Detect single entry single exit regions", true, true)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
+INITIALIZE_PASS_DEPENDENCY(PostDominatorTreePass)
 INITIALIZE_PASS_DEPENDENCY(DominanceFrontier)
 INITIALIZE_PASS_END(RegionInfoPass, "regions",
                 "Detect single entry single exit regions", true, true)
 
 // Create methods available outside of this file, to use them
 // "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by
 // the link time optimization.
 
 namespace llvm {
   FunctionPass *createRegionInfoPass() {
     return new RegionInfoPass();
   }
 }
 

lib/CodeGen/MachineRegionInfo.cpp

void MachineRegionInfoPass::verifyAnalysis() const {
   // a regionpass (marked PreservedAll) finish.
   if (MachineRegionInfo::VerifyRegionInfo)
     RI.verifyAnalysis();
 }
 
 void MachineRegionInfoPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequiredTransitive<DominatorTreeWrapperPass>();
-  AU.addRequired<PostDominatorTree>();
+  AU.addRequired<PostDominatorTreePass>();
   AU.addRequired<DominanceFrontier>();
 }
 
 void MachineRegionInfoPass::print(raw_ostream &OS, const Module *) const {
   RI.print(OS);
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

lib/Passes/PassBuilder.cpp

 ///
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Passes/PassBuilder.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Target/TargetMachine.h"

lib/Passes/PassRegistry.def

 CGSCC_PASS("no-op-cgscc", NoOpCGSCCPass())
 #undef CGSCC_PASS
 
 #ifndef FUNCTION_ANALYSIS
 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)
 #endif
 FUNCTION_ANALYSIS("assumptions", AssumptionAnalysis())
 FUNCTION_ANALYSIS("domtree", DominatorTreeAnalysis())
+FUNCTION_ANALYSIS("postdomtree", PostDominatorTreeAnalysis())
 FUNCTION_ANALYSIS("loops", LoopAnalysis())
 FUNCTION_ANALYSIS("no-op-function", NoOpFunctionAnalysis())
 FUNCTION_ANALYSIS("targetlibinfo", TargetLibraryAnalysis())
 FUNCTION_ANALYSIS("targetir",
                   TM ? TM->getTargetIRAnalysis() : TargetIRAnalysis())
 #undef FUNCTION_ANALYSIS
 
 #ifndef FUNCTION_PASS

lib/Transforms/Scalar/SampleProfile.cpp

public:
   const char *getPassName() const override { return "Sample profile pass"; }
 
   bool runOnFunction(Function &F) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<LoopInfoWrapperPass>();
     AU.addRequired<DominatorTreeWrapperPass>();
-    AU.addRequired<PostDominatorTree>();
+    AU.addRequired<PostDominatorTreePass>();
   }
 
 protected:
   unsigned getFunctionLoc(Function &F);
   bool emitAnnotations(Function &F);
   unsigned getInstWeight(Instruction &I);
   unsigned getBlockWeight(BasicBlock *BB);
   void printEdgeWeight(raw_ostream &OS, Edge E);
for (auto &BB : F) {
     // 2- BB2 post-dominates BB1.
     // 3- BB1 and BB2 are in the same loop nest.
     //
     // If all those conditions hold, it means that BB2 is executed
     // as many times as BB1, so they are placed in the same equivalence
     // class by making BB2's equivalence class be BB1.
     DominatedBBs.clear();
     DT->getDescendants(BB1, DominatedBBs);
-    findEquivalencesFor(BB1, DominatedBBs, PDT->DT);
+    findEquivalencesFor(BB1, DominatedBBs, PDT);
 
     // Repeat the same logic for all the blocks post-dominated by BB1.
     // We are looking for every basic block BB2 such that:
     //
     // 1- BB1 post-dominates BB2.
     // 2- BB2 dominates BB1.
     // 3- BB1 and BB2 are in the same loop nest.
     //
bool SampleProfileLoader::emitAnnotations(Function &F) {
 
   return Changed;
 }
 
 char SampleProfileLoader::ID = 0;
 INITIALIZE_PASS_BEGIN(SampleProfileLoader, "sample-profile",
                       "Sample Profile loader", false, false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
+INITIALIZE_PASS_DEPENDENCY(PostDominatorTreePass)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AddDiscriminators)
 INITIALIZE_PASS_END(SampleProfileLoader, "sample-profile",
                     "Sample Profile loader", false, false)
 
 bool SampleProfileLoader::doInitialization(Module &M) {
   auto ReaderOrErr = SampleProfileReader::create(Filename, M.getContext());
   if (std::error_code EC = ReaderOrErr.getError()) {
FunctionPass *llvm::createSampleProfileLoaderPass(StringRef Name) {
   return new SampleProfileLoader(Name);
 }
 
 bool SampleProfileLoader::runOnFunction(Function &F) {
   if (!ProfileIsValid)
     return false;
 
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-  PDT = &getAnalysis<PostDominatorTree>();
+  PDT = &getAnalysis<PostDominatorTreePass>().getDomTree();
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   Ctx = &F.getParent()->getContext();
   Samples = Reader->getSamplesFor(F);
   if (!Samples->empty())
     return emitAnnotations(F);
   return false;
 }

lib/Transforms/Scalar/SimplifyCFGPass.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/SimplifyCFG.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Pass.h"
static bool mergeEmptyReturnBlocks(Function &F) {
   }
 
   return Changed;
 }
 
 /// iterativelySimplifyCFG - Call SimplifyCFG on all the blocks in the function,
 /// iterating until no more changes are made.
 static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
-                                   AssumptionCache *AC,
+                                   AssumptionCache *AC, PostDominatorTree *PDT,
                                    unsigned BonusInstThreshold) {
   bool Changed = false;
   bool LocalChange = true;
   while (LocalChange) {
     LocalChange = false;
 
     // Loop over all of the basic blocks and remove them if they are unneeded...
     //
     for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
-      if (SimplifyCFG(BBIt++, TTI, BonusInstThreshold, AC)) {
+      if (SimplifyCFG(BBIt++, TTI, BonusInstThreshold, AC, PDT)) {
         LocalChange = true;
         ++NumSimpl;
       }
     }
     Changed |= LocalChange;
   }
   return Changed;
 }
 
 static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI,
-                                AssumptionCache *AC, int BonusInstThreshold) {
+                                AssumptionCache *AC, PostDominatorTree *PDT,
+                                int BonusInstThreshold) {
   bool EverChanged = removeUnreachableBlocks(F);
   EverChanged |= mergeEmptyReturnBlocks(F);
-  EverChanged |= iterativelySimplifyCFG(F, TTI, AC, BonusInstThreshold);
+  EverChanged |= iterativelySimplifyCFG(F, TTI, AC, PDT, BonusInstThreshold);
 
   // If neither pass changed anything, we're done.
   if (!EverChanged) return false;
 
   // iterativelySimplifyCFG can (rarely) make some loops dead.  If this happens,
   // removeUnreachableBlocks is needed to nuke them, which means we should
   // iterate between the two optimizations.  We structure the code like this to
   // avoid reruning iterativelySimplifyCFG if the second pass of
   // removeUnreachableBlocks doesn't do anything.
   if (!removeUnreachableBlocks(F))
     return true;
 
   do {
-    EverChanged = iterativelySimplifyCFG(F, TTI, AC, BonusInstThreshold);
+    EverChanged = iterativelySimplifyCFG(F, TTI, AC, PDT, BonusInstThreshold);
     EverChanged |= removeUnreachableBlocks(F);
   } while (EverChanged);
 
   return true;
 }
 
 SimplifyCFGPass::SimplifyCFGPass()
     : BonusInstThreshold(UserBonusInstThreshold) {}
 
 SimplifyCFGPass::SimplifyCFGPass(int BonusInstThreshold)
     : BonusInstThreshold(BonusInstThreshold) {}
 
 PreservedAnalyses SimplifyCFGPass::run(Function &F,
                                        AnalysisManager<Function> *AM) {
   auto &TTI = AM->getResult<TargetIRAnalysis>(F);
   auto &AC = AM->getResult<AssumptionAnalysis>(F);
+  auto &PDT = AM->getResult<PostDominatorTreeAnalysis>(F);
 
-  if (!simplifyFunctionCFG(F, TTI, &AC, BonusInstThreshold))
+  if (!simplifyFunctionCFG(F, TTI, &AC, &PDT, BonusInstThreshold))
     return PreservedAnalyses::none();
 
   return PreservedAnalyses::all();
 }
 
 namespace {
 struct CFGSimplifyPass : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
   unsigned BonusInstThreshold;
   CFGSimplifyPass(int T = -1) : FunctionPass(ID) {
     BonusInstThreshold = (T == -1) ? UserBonusInstThreshold : unsigned(T);
     initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
   }
   bool runOnFunction(Function &F) override {
     if (skipOptnoneFunction(F))
       return false;
 
     AssumptionCache *AC =
         &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     const TargetTransformInfo &TTI =
         getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
-    return simplifyFunctionCFG(F, TTI, AC, BonusInstThreshold);
+    PostDominatorTree *PDT = &getAnalysis<PostDominatorTreePass>().getDomTree();
+    return simplifyFunctionCFG(F, TTI, AC, PDT, BonusInstThreshold);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
+    AU.addRequired<PostDominatorTreePass>();
   }
 };
 }
 
 char CFGSimplifyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
+INITIALIZE_PASS_DEPENDENCY(PostDominatorTreePass)
 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
                     false)
 
 // Public interface to the CFGSimplification pass
 FunctionPass *llvm::createCFGSimplificationPass(int Threshold) {
   return new CFGSimplifyPass(Threshold);
 }
 

lib/Transforms/Utils/SimplifyCFG.cpp

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/GlobalVariable.h"

 
 STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps");
 STATISTIC(NumLinearMaps, "Number of switch instructions turned into linear mapping");
 STATISTIC(NumLookupTables, "Number of switch instructions turned into lookup tables");
 STATISTIC(NumLookupTablesHoles, "Number of switch instructions turned into lookup tables (holes checked)");
 STATISTIC(NumTableCmpReuses, "Number of reused switch table lookup compares");
 STATISTIC(NumSinkCommons, "Number of common instructions sunk down to the end block");
 STATISTIC(NumSpeculations, "Number of speculative executed instructions");
+STATISTIC(NumCmpReplaced, "Number of comparison instructions replaced");
 
 namespace {
   // The first field contains the value that the switch produces when a certain
   // case group is selected, and the second field is a vector containing the cases
   // composing the case group.
   typedef SmallVector<std::pair<Constant *, SmallVector<ConstantInt *, 4>>, 2>
     SwitchCaseResultVectorTy;
   // The first field contains the phi node that generates a result of the switch
struct ValueEqualityComparisonCase {
     bool operator==(BasicBlock *RHSDest) const { return Dest == RHSDest; }
   };
 
 class SimplifyCFGOpt {
   const TargetTransformInfo &TTI;
   const DataLayout &DL;
   unsigned BonusInstThreshold;
   AssumptionCache *AC;
+  PostDominatorTree *PDT;
   Value *isValueEqualityComparison(TerminatorInst *TI);
   BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI,
                                std::vector<ValueEqualityComparisonCase> &Cases);
   bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
                                                      BasicBlock *Pred,
                                                      IRBuilder<> &Builder);
   bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
                                            IRBuilder<> &Builder);
 
   bool SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder);
   bool SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder);
   bool SimplifyUnreachable(UnreachableInst *UI);
   bool SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder);
   bool SimplifyIndirectBr(IndirectBrInst *IBI);
   bool SimplifyUncondBranch(BranchInst *BI, IRBuilder <> &Builder);
   bool SimplifyCondBranch(BranchInst *BI, IRBuilder <>&Builder);
 
 public:
   SimplifyCFGOpt(const TargetTransformInfo &TTI, const DataLayout &DL,
-                 unsigned BonusInstThreshold, AssumptionCache *AC)
-      : TTI(TTI), DL(DL), BonusInstThreshold(BonusInstThreshold), AC(AC) {}
+                 unsigned BonusInstThreshold, AssumptionCache *AC,
+                 PostDominatorTree *PDT)
+      : TTI(TTI), DL(DL), BonusInstThreshold(BonusInstThreshold), AC(AC),
+        PDT(PDT) {}
   bool run(BasicBlock *BB);
 };
 }
 
 /// SafeToMergeTerminators - Return true if it is safe to merge these two
 /// terminator instructions together.
 ///
 static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) {

 /// end:
 ///   ... = phi i1 [ true, %entry ], [ %tmp, %DEFAULT ], [ true, %entry ]
 ///
 /// We prefer to split the edge to 'end' so that there is a true/false entry to
 /// the PHI, merging the third icmp into the switch.
 static bool TryToSimplifyUncondBranchWithICmpInIt(
     ICmpInst *ICI, IRBuilder<> &Builder, const DataLayout &DL,
     const TargetTransformInfo &TTI, unsigned BonusInstThreshold,
-    AssumptionCache *AC) {
+    AssumptionCache *AC, PostDominatorTree *PDT) {
   BasicBlock *BB = ICI->getParent();
 
   // If the block has any PHIs in it or the icmp has multiple uses, it is too
   // complex.
   if (isa<PHINode>(BB->begin()) || !ICI->hasOneUse()) return false;
 
   Value *V = ICI->getOperand(0);
   ConstantInt *Cst = cast<ConstantInt>(ICI->getOperand(1));
if (SI->getDefaultDest() != BB) {
     assert(VVal && "Should have a unique destination value");
     ICI->setOperand(0, VVal);
 
     if (Value *V = SimplifyInstruction(ICI, DL)) {
       ICI->replaceAllUsesWith(V);
       ICI->eraseFromParent();
     }
     // BB is now empty, so it is likely to simplify away.
-    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
   }
 
   // Ok, the block is reachable from the default dest.  If the constant we're
   // comparing exists in one of the other edges, then we can constant fold ICI
   // and zap it.
   if (SI->findCaseValue(Cst) != SI->case_default()) {
     Value *V;
     if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
       V = ConstantInt::getFalse(BB->getContext());
     else
       V = ConstantInt::getTrue(BB->getContext());
 
     ICI->replaceAllUsesWith(V);
     ICI->eraseFromParent();
     // BB is now empty, so it is likely to simplify away.
-    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
   }
 
   // The use of the icmp has to be in the 'end' block, by the only PHI node in
   // the block.
   BasicBlock *SuccBlock = BB->getTerminator()->getSuccessor(0);
   PHINode *PHIUse = dyn_cast<PHINode>(ICI->user_back());
   if (PHIUse == nullptr || PHIUse != &SuccBlock->front() ||
       isa<PHINode>(++BasicBlock::iterator(PHIUse)))

 bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
   BasicBlock *BB = SI->getParent();
 
   if (isValueEqualityComparison(SI)) {
     // If we only have one predecessor, and if it is a branch on this value,
     // see if that predecessor totally determines the outcome of this switch.
     if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
       if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
-        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
 
     Value *Cond = SI->getCondition();
     if (SelectInst *Select = dyn_cast<SelectInst>(Cond))
       if (SimplifySwitchOnSelect(SI, Select))
-        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
 
     // If the block only contains the switch, see if we can fold the block
     // away into any preds.
     BasicBlock::iterator BBI = BB->begin();
     // Ignore dbg intrinsics.
     while (isa<DbgInfoIntrinsic>(BBI))
       ++BBI;
     if (SI == &*BBI)
       if (FoldValueComparisonIntoPredecessors(SI, Builder))
-        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
   }
 
   // Try to transform the switch into an icmp and a branch.
   if (TurnSwitchRangeIntoICmp(SI, Builder))
-    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
 
   // Remove unreachable cases.
   if (EliminateDeadSwitchCases(SI, AC, DL))
-    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
 
   if (SwitchToSelect(SI, Builder, AC, DL))
-    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
 
   if (ForwardSwitchConditionToPHI(SI))
-    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
 
   if (SwitchToLookupTable(SI, Builder, DL, TTI))
-    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
 
   return false;
 }
 
 bool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) {
   BasicBlock *BB = IBI->getParent();
   bool Changed = false;
 
if (IBI->getNumDestinations() == 1) {
     // If the indirectbr has one successor, change it to a direct branch.
     BranchInst::Create(IBI->getDestination(0), IBI);
     EraseTerminatorInstAndDCECond(IBI);
     return true;
   }
 
   if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) {
     if (SimplifyIndirectBrOnSelect(IBI, SI))
-      return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+      return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
   }
   return Changed;
 }
 
 /// Given an block with only a single landing pad and a unconditional branch
 /// try to find another basic block which this one can be merged with.  This
 /// handles cases where we have multiple invokes with unique landing pads, but
 /// a shared handler.
bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder){
   // If the only instruction in the block is a seteq/setne comparison
   // against a constant, try to simplify the block.
   if (ICmpInst *ICI = dyn_cast<ICmpInst>(I))
     if (ICI->isEquality() && isa<ConstantInt>(ICI->getOperand(1))) {
       for (++I; isa<DbgInfoIntrinsic>(I); ++I)
         ;
       if (I->isTerminator() &&
           TryToSimplifyUncondBranchWithICmpInIt(ICI, Builder, DL, TTI,
-                                                BonusInstThreshold, AC))
+                                                BonusInstThreshold, AC, PDT))
         return true;
     }
 
   // See if we can merge an empty landing pad block with another which is
   // equivalent.
   if (LandingPadInst *LPad = dyn_cast<LandingPadInst>(I)) {
     for (++I; isa<DbgInfoIntrinsic>(I); ++I) {}
     if (I->isTerminator() &&
         TryToMergeLandingPad(LPad, BI, BB))
       return true;
   }
 
   // If this basic block is ONLY a compare and a branch, and if a predecessor
   // branches to us and our successor, fold the comparison into the
   // predecessor and use logical operations to update the incoming value
   // for PHI nodes in common successor.
   if (FoldBranchToCommonDest(BI, BonusInstThreshold))
-    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
   return false;
 }
 
 
 bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) {
   BasicBlock *BB = BI->getParent();
 
   // Conditional branch
   if (isValueEqualityComparison(BI)) {
     // If we only have one predecessor, and if it is a branch on this value,
     // see if that predecessor totally determines the outcome of this
     // switch.
     if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
       if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
-        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
 
     // This block must be empty, except for the setcond inst, if it exists.
     // Ignore dbg intrinsics.
     BasicBlock::iterator I = BB->begin();
     // Ignore dbg intrinsics.
     while (isa<DbgInfoIntrinsic>(I))
       ++I;
     if (&*I == BI) {
       if (FoldValueComparisonIntoPredecessors(BI, Builder))
-        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
     } else if (&*I == cast<Instruction>(BI->getCondition())){
       ++I;
       // Ignore dbg intrinsics.
       while (isa<DbgInfoIntrinsic>(I))
         ++I;
       if (&*I == BI && FoldValueComparisonIntoPredecessors(BI, Builder))
-        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
     }
   }
 
   // Try to turn "br (X == 0 | X == 1), T, F" into a switch instruction.
   if (SimplifyBranchOnICmpChain(BI, Builder, DL))
     return true;
 
   // If this basic block is ONLY a compare and a branch, and if a predecessor
   // branches to us and one of our successors, fold the comparison into the
   // predecessor and use logical operations to pick the right destination.
   if (FoldBranchToCommonDest(BI, BonusInstThreshold))
-    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
 
   // We have a conditional branch to two blocks that are only reachable
   // from BI.  We know that the condbr dominates the two blocks, so see if
   // there is any identical code in the "then" and "else" blocks.  If so, we
   // can hoist it up to the branching block.
   if (BI->getSuccessor(0)->getSinglePredecessor()) {
     if (BI->getSuccessor(1)->getSinglePredecessor()) {
       if (HoistThenElseCodeToIf(BI, TTI))
-        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
     } else {
       // If Successor #1 has multiple preds, we may be able to conditionally
       // execute Successor #0 if it branches to Successor #1.
       TerminatorInst *Succ0TI = BI->getSuccessor(0)->getTerminator();
       if (Succ0TI->getNumSuccessors() == 1 &&
           Succ0TI->getSuccessor(0) == BI->getSuccessor(1))
         if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0), TTI))
-          return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+          return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
     }
   } else if (BI->getSuccessor(1)->getSinglePredecessor()) {
     // If Successor #0 has multiple preds, we may be able to conditionally
     // execute Successor #1 if it branches to Successor #0.
     TerminatorInst *Succ1TI = BI->getSuccessor(1)->getTerminator();
     if (Succ1TI->getNumSuccessors() == 1 &&
         Succ1TI->getSuccessor(0) == BI->getSuccessor(0))
       if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1), TTI))
-        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
   }
 
   // If this is a branch on a phi node in the current block, thread control
   // through this block if any PHI node entries are constants.
   if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition()))
     if (PN->getParent() == BI->getParent())
       if (FoldCondBranchOnPHI(BI, DL))
-        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
 
   // Scan predecessor blocks for conditional branches.
   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
     if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
       if (PBI != BI && PBI->isConditional())
         if (SimplifyCondBranchToCondBranch(PBI, BI))
-          return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+          return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true;
 
   return false;
 }
 
 /// Check if passing a value to an instruction will cause undefined behavior.
 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) {
   Constant *C = dyn_cast<Constant>(V);
   if (!C)
if (StoreInst *SI = dyn_cast<StoreInst>(Use))
       if (!SI->isVolatile())
         return SI->getPointerAddressSpace() == 0 && SI->getPointerOperand() == I;
   }
   return false;
 }
 
 /// If BB has an incoming value that will always trigger undefined behavior
 /// (eg. null pointer dereference), remove the branch leading here.
-static bool removeUndefIntroducingPredecessor(BasicBlock *BB) {
+static bool removeUndefIntroducingPredecessor(BasicBlock *BB,
+                                              PostDominatorTree *PDT) {
   for (BasicBlock::iterator i = BB->begin();
        PHINode *PHI = dyn_cast<PHINode>(i); ++i)
     for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
       if (passingValueIsAlwaysUndefined(PHI->getIncomingValue(i), PHI)) {
         TerminatorInst *T = PHI->getIncomingBlock(i)->getTerminator();
         IRBuilder<> Builder(T);
         if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
           BB->removePredecessor(PHI->getIncomingBlock(i));
-          // Turn uncoditional branches into unreachables and remove the dead
+          // Turn unconditional branches into unreachables and remove the dead
           // destination from conditional branches.
           if (BI->isUnconditional())
             Builder.CreateUnreachable();
-          else
-            Builder.CreateBr(BI->getSuccessor(0) == BB ? BI->getSuccessor(1) :
-                                                         BI->getSuccessor(0));
+          else {
+            bool PickFirst = BI->getSuccessor(1) == BB;
+            Builder.CreateBr(PickFirst ? BI->getSuccessor(0)
+                                       : BI->getSuccessor(1));
+            if (PDT) {
+              auto Cond = dyn_cast<Instruction>(BI->getCondition());
+              if (PDT->dominates(BB, Cond->getParent())) {
+                // Inline the result of the conditional check downstream as a
+                // constant, and then get rid of it if possible.
+                Value *Const = ConstantInt::get(Cond->getType(), PickFirst);
+                Cond->replaceAllUsesWith(Const);
+                RecursivelyDeleteTriviallyDeadInstructions(Cond);
+                NumCmpReplaced++;
+              }
+            }
+          }
           BI->eraseFromParent();
           return true;
         }
         // TODO: SwitchInst.
       }
 
   return false;
 }
bool SimplifyCFGOpt::run(BasicBlock *BB) {
   // Check to see if we can constant propagate this terminator instruction
   // away...
   Changed |= ConstantFoldTerminator(BB, true);
 
   // Check for and eliminate duplicate PHI nodes in this block.
   Changed |= EliminateDuplicatePHINodes(BB);
 
   // Check for and remove branches that will always cause undefined behavior.
-  Changed |= removeUndefIntroducingPredecessor(BB);
+  Changed |= removeUndefIntroducingPredecessor(BB, PDT);
 
   // Merge basic blocks into their predecessor if there is only one distinct
   // pred, and if there is only one distinct successor of the predecessor, and
   // if there are no PHI nodes.
   //
   if (MergeBlockIntoPredecessor(BB))
     return true;
 

 }
 
 /// SimplifyCFG - This function is used to do simplification of a CFG.  For
 /// example, it adjusts branches to branches to eliminate the extra hop, it
 /// eliminates unreachable basic blocks, and does other "peephole" optimization
 /// of the CFG.  It returns true if a modification was made.
 ///
 bool llvm::SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
-                       unsigned BonusInstThreshold, AssumptionCache *AC) {
+                       unsigned BonusInstThreshold, AssumptionCache *AC,
+                       PostDominatorTree *PDT) {
   return SimplifyCFGOpt(TTI, BB->getModule()->getDataLayout(),
-                        BonusInstThreshold, AC).run(BB);
+                        BonusInstThreshold, AC, PDT).run(BB);
 }

test/Transforms/SimplifyCFG/load-means-not-null.ll

+; RUN: opt < %s -simplifycfg -S | FileCheck %s
+
+declare void @g(i8)
+
+; CHECK-LABEL: @test_postdominate
+; CHECK-NEXT: a:
+; CHECK-NEXT: call void @g(i8 0)
+; CHECK: ret i1 true
+define i1 @test_postdominate(i8* %mem) {
+  %test = icmp eq i8* %mem, null
+  br i1 %test, label %a, label %b
+a:
+  call void @g(i8 0)
+  br label %c
+b:
+  br label %c
+c:
+  %join = phi i8* [ %mem, %a ], [ null, %b ]
+  %gep = getelementptr i8, i8* %join, i64 4
+  %res = load i8, i8* %gep
+  ret i1 %test
+}
+
+; CHECK-LABEL: @test_doesnt_postdominate
+; CHECK: ret i1 %test
+define i1 @test_doesnt_postdominate(i8* %mem, i1 %bool) {
+  %test = icmp eq i8* %mem, null
+  br i1 %bool, label %start, label %return
+
+start:
+  br i1 %test, label %a, label %b
+a:
+  call void @g(i8 0)
+  br label %c
+b:
+  br label %c
+c:
+  %join = phi i8* [ %mem, %a ], [ null, %b ]
+  %gep = getelementptr i8, i8* %join, i64 4
+  %res = load i8, i8* %gep
+  br label %return
+
+return:
+  ret i1 %test
+}

test/Transforms/SimplifyCFG/phi-undef-loadstore.ll

if.then4:                                         ; preds = %if.else
   br label %if.end7
 
 if.end7:                                          ; preds = %if.else, %if.then4, %if.then
   %x.0 = phi i32* [ %a, %if.then ], [ %c, %if.then4 ], [ null, %if.else ]
   %tmp9 = load i32, i32* %x.0
   ret i32 %tmp9
 
 ; CHECK-LABEL: @test1(
-; CHECK: if.else:
-; CHECK: br label %if.end7
-
-; CHECK: phi i32* [ %a, %if.then ], [ %c, %if.else ]
+; CHECK: tail call void @bar()
+; CHECK: %c.a = select i1 %tobool, i32* %c, i32* %a
+; CHECK: %tmp9 = load i32, i32* %c.a
 }
 
 define i32 @test2(i32* %a, i32 %b, i32* %c, i32 %d) nounwind {
 entry:
   %tobool = icmp eq i32 %b, 0
   br i1 %tobool, label %if.else, label %if.then
 
 if.then:                                          ; preds = %entry
   tail call void @bar() nounwind
   br label %if.end7
 
 if.else:                                          ; preds = %entry
   %tobool3 = icmp eq i32 %d, 0
   br i1 %tobool3, label %if.end7, label %if.then4
 
 if.then4:                                         ; preds = %if.else
   tail call void @bar() nounwind
   br label %if.end7
 
 if.end7:                                          ; preds = %if.else, %if.then4, %if.then
   %x.0 = phi i32* [ %a, %if.then ], [ null, %if.then4 ], [ null, %if.else ]
   %tmp9 = load i32, i32* %x.0
   ret i32 %tmp9
 ; CHECK-LABEL: @test2(
-; CHECK: if.else:
-; CHECK: unreachable
-
+; CHECK: tail call void @bar()
+; CHECK: %tmp9 = load i32, i32* %a
 ; CHECK-NOT: phi
 }
 
 define i32 @test3(i32* %a, i32 %b, i32* %c, i32 %d) nounwind {
 entry:
   %tobool = icmp eq i32 %b, 0
   br i1 %tobool, label %if.else, label %if.then