Index: include/llvm/Analysis/MemoryLocation.h
===================================================================
--- include/llvm/Analysis/MemoryLocation.h
+++ include/llvm/Analysis/MemoryLocation.h
@@ -118,6 +118,8 @@
   bool operator==(const MemoryLocation &Other) const {
     return Ptr == Other.Ptr && Size == Other.Size && AATags == Other.AATags;
   }
+
+  operator bool() const { return Ptr; }
 };
 
 // Specialize DenseMapInfo for MemoryLocation.
Index: include/llvm/InitializePasses.h
===================================================================
--- include/llvm/InitializePasses.h
+++ include/llvm/InitializePasses.h
@@ -265,6 +265,7 @@
 void initializeOptimizationRemarkEmitterWrapperPassPass(PassRegistry&);
 void initializeOptimizePHIsPass(PassRegistry&);
 void initializePAEvalPass(PassRegistry &);
+void initializePDSELegacyPassPass(PassRegistry &);
 void initializePEIPass(PassRegistry&);
 void initializePGOIndirectCallPromotionLegacyPassPass(PassRegistry&);
 void initializePGOInstrumentationGenLegacyPassPass(PassRegistry&);
Index: include/llvm/Transforms/Scalar/PDSE.h
===================================================================
--- /dev/null
+++ include/llvm/Transforms/Scalar/PDSE.h
@@ -0,0 +1,13 @@
+#ifndef LLVM_TRANSFORMS_SCALAR_PDSE_H
+#define LLVM_TRANSFORMS_SCALAR_PDSE_H
+
+#include "llvm/IR/Function.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+struct PDSEPass : public PassInfoMixin<PDSEPass> {
+  PreservedAnalyses run(Function &, FunctionAnalysisManager &);
+};
+}
+
+#endif // LLVM_TRANSFORMS_SCALAR_PDSE_H
Index: lib/Passes/PassBuilder.cpp
===================================================================
--- lib/Passes/PassBuilder.cpp
+++ lib/Passes/PassBuilder.cpp
@@ -120,6 +120,7 @@
 #include "llvm/Transforms/Scalar/NaryReassociate.h"
 #include "llvm/Transforms/Scalar/NewGVN.h"
 #include "llvm/Transforms/Scalar/PartiallyInlineLibCalls.h"
+#include "llvm/Transforms/Scalar/PDSE.h"
 #include "llvm/Transforms/Scalar/Reassociate.h"
 #include "llvm/Transforms/Scalar/SCCP.h"
 #include "llvm/Transforms/Scalar/SROA.h"
Index: lib/Passes/PassRegistry.def
===================================================================
--- lib/Passes/PassRegistry.def
+++ lib/Passes/PassRegistry.def
@@ -173,6 +173,7 @@
 FUNCTION_PASS("loop-load-elim", LoopLoadEliminationPass())
 FUNCTION_PASS("loop-distribute", LoopDistributePass())
 FUNCTION_PASS("loop-vectorize", LoopVectorizePass())
+FUNCTION_PASS("pdse", PDSEPass())
 FUNCTION_PASS("print", PrintFunctionPass(dbgs()))
 FUNCTION_PASS("print<assumptions>", AssumptionPrinterPass(dbgs()))
 FUNCTION_PASS("print<block-freq>", BlockFrequencyPrinterPass(dbgs()))
Index: lib/Transforms/Scalar/CMakeLists.txt
===================================================================
--- lib/Transforms/Scalar/CMakeLists.txt
+++ lib/Transforms/Scalar/CMakeLists.txt
@@ -46,6 +46,7 @@
   NaryReassociate.cpp
   NewGVN.cpp
   PartiallyInlineLibCalls.cpp
+  PDSE.cpp
   PlaceSafepoints.cpp
   Reassociate.cpp
   Reg2Mem.cpp
Index: lib/Transforms/Scalar/PDSE.cpp
===================================================================
--- /dev/null
+++ lib/Transforms/Scalar/PDSE.cpp
@@ -0,0 +1,113 @@
+// The pass implemented in this file performs partial dead store elimination as
+// described in:
+//
+//   Register Promotion Sparse Partial Redundancy Elimination of Loads and Store
+//   https://doi.org/10.1145/277650.277659
+//
+// "Partial" refers to the ability to transform partial store redundancies into
+// full redundancies by inserting stores at appropriate split points. For
+// instance:
+//
+// bb0:
+//   store i8 undef, i8* %x
+//   br i1 undef label %true, label %false
+// true:
+//   store i8 undef, i8* %x
+//   br label %exit
+// false:
+//   br label %exit
+// exit:
+//   ret void
+//
+// The store in bb0 can be made fully redundant by inserting a copy into the
+// false block.
+//
+// For a gentler introduction to PRE, see:
+//
+//   Partial Redundancy Elimination in SSA Form
+//   https://doi.org/10.1145/319301.319348
+
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Pass.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Scalar/PDSE.h"
+
+#define DEBUG_TYPE "pdse"
+
+// TODO: Require BreakCriticalEdges
+
+using namespace llvm;
+
+static cl::opt<bool>
+    PrintFRG("print-pdse", cl::init(false), cl::Hidden,
+             cl::desc("Print the factored redundancy graph of stores."));
+
+namespace {
+bool runPDSE(Function &F, AliasAnalysis &AA, const PostDominatorTree &PDT,
+             const TargetLibraryInfo &TLI) {
+  if (PrintFRG) {
+    DEBUG(dbgs() << "TODO: Print factored redundancy graph.\n");
+    return false;
+  } else {
+    DEBUG(dbgs() << "Dummy PDSE pass.\n");
+  }
+  return false;
+}
+
+class PDSELegacyPass : public FunctionPass {
+public:
+  PDSELegacyPass() : FunctionPass(ID) {
+    initializePDSELegacyPassPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F) override {
+    if (skipFunction(F))
+      return false;
+
+    return runPDSE(F, getAnalysis<AAResultsWrapperPass>().getAAResults(),
+                   getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree(),
+                   getAnalysis<TargetLibraryInfoWrapperPass>().getTLI());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<PostDominatorTreeWrapperPass>();
+    AU.addRequired<AAResultsWrapperPass>();
+    AU.addRequired<TargetLibraryInfoWrapperPass>();
+
+    AU.setPreservesCFG();
+    AU.addPreserved<PostDominatorTreeWrapperPass>();
+    AU.addPreserved<GlobalsAAWrapperPass>();
+  }
+
+  static char ID; // Pass identification, replacement for typeid
+};
+} // end anonymous namespace
+
+char PDSELegacyPass::ID = 0;
+
+INITIALIZE_PASS_BEGIN(PDSELegacyPass, "pdse", "Partial Dead Store Elimination",
+                      false, false)
+INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
+INITIALIZE_PASS_END(PDSELegacyPass, "pdse", "Partial Dead Store Elimination",
+                    false, false)
+
+namespace llvm {
+PreservedAnalyses PDSEPass::run(Function &F, FunctionAnalysisManager &AM) {
+  if (!runPDSE(F, AM.getResult<AAManager>(F),
+               AM.getResult<PostDominatorTreeAnalysis>(F),
+               AM.getResult<TargetLibraryAnalysis>(F)))
+    return PreservedAnalyses::all();
+
+  PreservedAnalyses PA;
+  PA.preserveSet<CFGAnalyses>();
+  PA.preserve<PostDominatorTreeAnalysis>();
+  PA.preserve<GlobalsAA>();
+  return PA;
+}
+} // end namespace llvm
Index: lib/Transforms/Scalar/Scalar.cpp
===================================================================
--- lib/Transforms/Scalar/Scalar.cpp
+++ lib/Transforms/Scalar/Scalar.cpp
@@ -74,6 +74,7 @@
   initializeMergedLoadStoreMotionLegacyPassPass(Registry);
   initializeNaryReassociateLegacyPassPass(Registry);
   initializePartiallyInlineLibCallsLegacyPassPass(Registry);
+  initializePDSELegacyPassPass(Registry);
   initializeReassociateLegacyPassPass(Registry);
   initializeRegToMemPass(Registry);
   initializeRewriteStatepointsForGCPass(Registry);