Index: include/llvm/Analysis/PhiValues.h
===================================================================
--- /dev/null
+++ include/llvm/Analysis/PhiValues.h
@@ -0,0 +1,135 @@
+//===- PhiValues.h - Phi Value Analysis -------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the PhiValues class, and associated passes, which can be
+// used to find the underlying values of the phis in a function, i.e. the
+// non-phi values that can be found by traversing the phi graph.
+//
+// This information is computed lazily and cached, using value handles so that
+// it is automatically modified or invalidated if the function changes.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_PHIVALUES_H
+#define LLVM_ANALYSIS_PHIVALUES_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/IR/ValueHandle.h"
+#include "llvm/Pass.h"
+
+namespace llvm {
+
+class Value;
+class PHINode;
+class Function;
+
+/// Class for calculating and caching the underlying values of phis in a
+/// function.
+///
+/// Initially the PhiValues is empty, and gets incrementally populated whenever
+/// it is queried.
+class PhiValues {
+  /// Callback handle used for the keys in the value map, so that we can remove
+  /// entries from the map when the associated phi is deleted from the function.
+  class PhiValuesCallbackVH final : public CallbackVH {
+    PhiValues *PI;
+    void deleted() override;
+
+  public:
+    using DMI = DenseMapInfo<const Value *>;
+    PhiValuesCallbackVH(const Value *V, PhiValues *PI = nullptr)
+        : CallbackVH(const_cast<Value *>(V)), PI(PI) {}
+  };
+
+  /// The type used for mapping a phi to its values. The map value type uses
+  /// TrackingVH so that if any value in a phi is replaced with another the
+  /// map entry will be updated automatically.
+  using ValueMap =
+      DenseMap<PhiValuesCallbackVH, SmallVector<TrackingVH<Value>, 4>,
+               PhiValuesCallbackVH::DMI>;
+
+  /// The map of phis to their underlying values.
+  ValueMap PhiToUnderlyingValues;
+
+  /// The function that the PhiValues is for.
+  const Function &F;
+
+  /// Process a phi so that its entry in the value map is fully populated.
+  void processPhi(const PHINode *PN);
+
+public:
+  using ValueSet = SmallPtrSet<Value *, 4>;
+
+  /// Construct an empty PhiValues.
+  PhiValues(const Function &F) : F(F) {}
+
+  /// Get the underlying values of a phi.
+  ///
+  /// This returns the cached value if PN has previously been processed,
+  /// otherwise it processes it first.
+  ValueSet getUnderlyingPhiValues(const PHINode *PN);
+
+  /// Print out the values currently in the cache.
+  void print(raw_ostream &OS) const;
+
+  /// PhiValues is updated automatically, so never needs to be invalidated.
+  bool invalidate(Function &, const PreservedAnalyses &,
+                  FunctionAnalysisManager::Invalidator &) {
+    return false;
+  }
+};
+
+/// The analysis pass which yields a PhiValues
+///
+/// The analysis does nothing by itself, and just returns an empty PhiValues
+/// which will get filled in as it's used.
+class PhiValuesAnalysis : public AnalysisInfoMixin<PhiValuesAnalysis> {
+  friend AnalysisInfoMixin<PhiValuesAnalysis>;
+  static AnalysisKey Key;
+
+public:
+  using Result = PhiValues;
+  PhiValues run(Function &F, FunctionAnalysisManager &);
+};
+
+/// A pass for printing the PhiValues for a function.
+///
+/// This pass doesn't print whatever information the PhiValues happens to hold,
+/// but instead first uses the PhiValues to analyze all the phis in the function
+/// so the complete information is printed.
+class PhiValuesPrinterPass : public PassInfoMixin<PhiValuesPrinterPass> {
+  raw_ostream &OS;
+
+public:
+  explicit PhiValuesPrinterPass(raw_ostream &OS) : OS(OS) {}
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+
+/// Wrapper pass for the legacy pass manager
+class PhiValuesWrapperPass : public FunctionPass {
+  std::unique_ptr<PhiValues> Result;
+  virtual void anchor();
+
+public:
+  static char ID;
+  PhiValuesWrapperPass();
+
+  PhiValues &getResult() { return *Result; }
+  const PhiValues &getResult() const { return *Result; }
+
+  bool runOnFunction(Function &F) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+};
+
+} // namespace llvm
+
+#endif
Index: include/llvm/InitializePasses.h
===================================================================
--- include/llvm/InitializePasses.h
+++ include/llvm/InitializePasses.h
@@ -296,6 +296,7 @@
 void initializePartiallyInlineLibCallsLegacyPassPass(PassRegistry&);
 void initializePatchableFunctionPass(PassRegistry&);
 void initializePeepholeOptimizerPass(PassRegistry&);
+void initializePhiValuesWrapperPassPass(PassRegistry&);
 void initializePhysicalRegisterUsageInfoPass(PassRegistry&);
 void initializePlaceBackedgeSafepointsImplPass(PassRegistry&);
 void initializePlaceSafepointsPass(PassRegistry&);
Index: lib/Analysis/CMakeLists.txt
===================================================================
--- lib/Analysis/CMakeLists.txt
+++ lib/Analysis/CMakeLists.txt
@@ -65,6 +65,7 @@
   OptimizationRemarkEmitter.cpp
   OrderedBasicBlock.cpp
   PHITransAddr.cpp
+  PhiValues.cpp
   PostDominators.cpp
   ProfileSummaryInfo.cpp
   PtrUseVisitor.cpp
Index: lib/Analysis/PhiValues.cpp
===================================================================
--- /dev/null
+++ lib/Analysis/PhiValues.cpp
@@ -0,0 +1,170 @@
+//===- PhiValues.cpp - Phi Value Analysis ---------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/PhiValues.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/Instructions.h"
+
+using namespace llvm;
+
+void PhiValues::PhiValuesCallbackVH::deleted() {
+  auto It = PI->PhiToUnderlyingValues.find(getValPtr());
+  if (It != PI->PhiToUnderlyingValues.end())
+    PI->PhiToUnderlyingValues.erase(It);
+}
+
+// The general idea of processing a phi is to look at its operands, then repeat
+// for those operands if they themselves are phis, until we've visited all the
+// phis reachable from InitialPhi. We could just collect the non-phi values that
+// we obtain by doing this and set those as the value of InitialPhi, except that
+// finding the values of InitialPhi necessarily involves finding the values of
+// every phi reachable from it and we'd like to record those as well, and this
+// is where the difficulty comes in.
+//
+// The way we handle it is by keeping track of which phis depend on other phis.
+// When looking at a phi PN if it has a phi VPN as an operand then we mark PN
+// as depending on VPN, so then when we collect the non-phi operands of VPN we
+// set them as values of PN as well. In order to cope with transitive dependence
+// we actually mark all phis depending on PN as depending on VPN.
+//
+// For phi graphs without loops this would be enough, but for phi graphs with
+// loops there's an extra layer of difficulty as a phi A can have as an operand
+// a phi B that we've already visited, and B can have an operand C has been
+// visited and an operand D that has not been visited. The values of C will have
+// been collected as the values of B, so we can handle that by adding the values
+// of B to the values of A, but we also then need to mark A as depending on D.
+// Or in other words, instead of marking the phis that depend on A as depending
+// on B they need to depend on the phis that B depends on.
+void PhiValues::processPhi(const PHINode *InitialPhi) {
+  SmallVector<const PHINode *, 4> Worklist = {InitialPhi};
+  // A map of a phi to the phis that depend on it.
+  DenseMap<const PHINode *, SmallPtrSet<const PHINode *, 4>> PhiDependence;
+  do {
+    const PHINode *PN = Worklist.pop_back_val();
+    // If we already have a map entry for this phi then we've already visited
+    // it, so skip it.
+    if (PhiToUnderlyingValues.count(PN))
+      continue;
+    // Insert an entry for this phi into the map.
+    PhiToUnderlyingValues.insert(
+        {PhiValuesCallbackVH(PN, this), SmallVector<TrackingVH<Value>, 4>()});
+    // The loop below becomes simpler if we say a phi depends on itself.
+    PhiDependence[PN].insert(PN);
+    // Examine PN's incoming values.
+    for (Value *V : PN->incoming_values()) {
+      if (PHINode *VPN = dyn_cast<PHINode>(V)) {
+        // If we've already visited this phi then add its values to the phis
+        // that depend on PN, otherwise we add it to the worklist.
+        if (PhiToUnderlyingValues.count(VPN)) {
+          auto &Vals = PhiToUnderlyingValues[VPN];
+          for (const PHINode *D : PhiDependence[PN]) {
+            // We need to create new ValueHandles instead of copying the
+            // existing ones, due to how copying a ValueHandle interacts with
+            // the use list of the Value.
+            for (auto &VH : Vals)
+              PhiToUnderlyingValues[D].push_back((Value *)VH);
+            // Phis that depend on PN depend on the phis that VPN depends on.
+            for (auto &Pair : PhiDependence)
+              if (Pair.second.count(VPN))
+                Pair.second.insert(D);
+          }
+        } else {
+          Worklist.push_back(VPN);
+          // Phis that depend on PN depend on VPN.
+          for (const PHINode *D : PhiDependence[PN])
+            PhiDependence[VPN].insert(D);
+        }
+      } else {
+        // Add V to the underlying values of everything that depends on PN.
+        for (const PHINode *D : PhiDependence[PN])
+          PhiToUnderlyingValues[D].push_back(V);
+      }
+    }
+  } while (!Worklist.empty());
+}
+
+PhiValues::ValueSet PhiValues::getUnderlyingPhiValues(const PHINode *PN) {
+  if (!PhiToUnderlyingValues.count(PN))
+    processPhi(PN);
+  // We convert to a set to eliminate duplicate values.
+  ValueSet Ret;
+  for (auto VH : PhiToUnderlyingValues[PN])
+    Ret.insert(VH);
+  return Ret;
+}
+
+void PhiValues::print(raw_ostream &OS) const {
+  // Iterate through the phi nodes of the function rather than iterate through
+  // PhiToUnderlyingValues in order to get predictable ordering.
+  for (const BasicBlock &BB : F) {
+    for (const PHINode &PN : BB.phis()) {
+      OS << "PHI ";
+      PN.printAsOperand(OS, false);
+      OS << " has values:\n";
+      // Get the values and convert to a set. We can't do this by calling
+      // getUnderlyingPhiValues as that generates the values if not present,
+      // which we don't want, and it's also non-const.
+      auto It = PhiToUnderlyingValues.find_as(&PN);
+      if (It->first) {
+        ValueSet VS;
+        for (auto VH : It->second)
+          VS.insert(VH);
+        if (It->second.empty())
+          OS << "  NONE\n";
+        else
+          for (Value *V : VS) {
+            // Printing of an instruction prints two spaces at the start, so
+            // handle instructions and everything else slightly differently in
+            // order to get consistent indenting.
+            if (Instruction *I = dyn_cast<Instruction>(V))
+              OS << *I << "\n";
+            else
+              OS << "  " << *V << "\n";
+          }
+      } else {
+        OS << "  UNKNOWN\n";
+      }
+    }
+  }
+}
+
+AnalysisKey PhiValuesAnalysis::Key;
+PhiValues PhiValuesAnalysis::run(Function &F, FunctionAnalysisManager &) {
+  return PhiValues(F);
+}
+
+PreservedAnalyses PhiValuesPrinterPass::run(Function &F,
+                                            FunctionAnalysisManager &AM) {
+  OS << "PHI Values for function: " << F.getName() << "\n";
+  PhiValues &PI = AM.getResult<PhiValuesAnalysis>(F);
+  for (const BasicBlock &BB : F)
+    for (const PHINode &PN : BB.phis())
+      PI.getUnderlyingPhiValues(&PN);
+  PI.print(OS);
+  return PreservedAnalyses::all();
+}
+
+PhiValuesWrapperPass::PhiValuesWrapperPass() : FunctionPass(ID) {
+  initializePhiValuesWrapperPassPass(*PassRegistry::getPassRegistry());
+}
+
+bool PhiValuesWrapperPass::runOnFunction(Function &F) {
+  Result.reset(new PhiValues(F));
+  return false;
+}
+
+void PhiValuesWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+}
+
+INITIALIZE_PASS(PhiValuesWrapperPass, "phivalues", "Phi Values Analysis", false,
+                true)
+char PhiValuesWrapperPass::ID = 0;
+void PhiValuesWrapperPass::anchor() {}
Index: lib/Passes/PassBuilder.cpp
===================================================================
--- lib/Passes/PassBuilder.cpp
+++ lib/Passes/PassBuilder.cpp
@@ -41,6 +41,7 @@
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/ModuleSummaryAnalysis.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
+#include "llvm/Analysis/PhiValues.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/RegionInfo.h"
Index: lib/Passes/PassRegistry.def
===================================================================
--- lib/Passes/PassRegistry.def
+++ lib/Passes/PassRegistry.def
@@ -111,6 +111,7 @@
 FUNCTION_ANALYSIS("da", DependenceAnalysis())
 FUNCTION_ANALYSIS("memdep", MemoryDependenceAnalysis())
 FUNCTION_ANALYSIS("memoryssa", MemorySSAAnalysis())
+FUNCTION_ANALYSIS("phi-values", PhiValuesAnalysis())
 FUNCTION_ANALYSIS("regions", RegionInfoAnalysis())
 FUNCTION_ANALYSIS("no-op-function", NoOpFunctionAnalysis())
 FUNCTION_ANALYSIS("opt-remark-emit", OptimizationRemarkEmitterAnalysis())
@@ -194,6 +195,7 @@
 FUNCTION_PASS("print<domfrontier>", DominanceFrontierPrinterPass(dbgs()))
 FUNCTION_PASS("print<loops>", LoopPrinterPass(dbgs()))
 FUNCTION_PASS("print<memoryssa>", MemorySSAPrinterPass(dbgs()))
+FUNCTION_PASS("print<phi-values>", PhiValuesPrinterPass(dbgs()))
 FUNCTION_PASS("print<regions>", RegionInfoPrinterPass(dbgs()))
 FUNCTION_PASS("print<scalar-evolution>", ScalarEvolutionPrinterPass(dbgs()))
 FUNCTION_PASS("reassociate", ReassociatePass())
Index: test/Analysis/PhiValues/basic.ll
===================================================================
--- /dev/null
+++ test/Analysis/PhiValues/basic.ll
@@ -0,0 +1,282 @@
+; RUN: opt < %s -passes='print<phi-values>' -disable-output 2>&1 | FileCheck %s
+
+@X = common global i32 0
+
+; CHECK-LABEL: PHI Values for function: simple
+define void @simple(i32* %ptr) {
+entry:
+  br i1 undef, label %if, label %else
+
+if:
+  br label %end
+
+else:
+  br label %end
+
+end:
+; CHECK: PHI %phi1 has values:
+; CHECK-DAG: i32 0
+; CHECK-DAG: i32 1
+  %phi1 = phi i32 [ 0, %if ], [ 1, %else ]
+; CHECK: PHI %phi2 has values:
+; CHECK-DAG: @X
+; CHECK-DAG: %ptr
+  %phi2 = phi i32* [ @X, %if ], [ %ptr, %else ]
+  ret void
+}
+
+; CHECK-LABEL: PHI Values for function: chain
+define void @chain() {
+entry:
+  br i1 undef, label %if1, label %else1
+
+if1:
+  br label %middle
+
+else1:
+  br label %middle
+
+middle:
+; CHECK: PHI %phi1 has values:
+; CHECK-DAG: i32 0
+; CHECK-DAG: i32 1
+  %phi1 = phi i32 [ 0, %if1 ], [ 1, %else1 ]
+  br i1 undef, label %if2, label %else2
+
+if2:
+  br label %end
+
+else2:
+  br label %end
+
+end:
+; CHECK: PHI %phi2 has values:
+; CHECK-DAG: i32 0
+; CHECK-DAG: i32 1
+; CHECK-DAG: i32 2
+  %phi2 = phi i32 [ %phi1, %if2 ], [ 2, %else2 ]
+  ret void
+}
+
+; CHECK-LABEL: PHI Values for function: no_values
+define void @no_values() {
+entry:
+  ret void
+
+unreachable:
+; CHECK: PHI %phi has values:
+; CHECK-DAG: NONE
+  %phi = phi i32 [ %phi, %unreachable ]
+  br label %unreachable
+}
+
+; CHECK-LABEL: PHI Values for function: simple_loop
+define void @simple_loop() {
+entry:
+  br label %loop
+
+loop:
+; CHECK: PHI %phi has values:
+; CHECK-DAG: i32 0
+  %phi = phi i32 [ 0, %entry ], [ %phi, %loop ]
+  br i1 undef, label %loop, label %end
+
+end:
+  ret void
+}
+
+; CHECK-LABEL: PHI Values for function: complex_loop
+define void @complex_loop() {
+entry:
+  br i1 undef, label %loop, label %end
+
+loop:
+; CHECK: PHI %phi1 has values:
+; CHECK-DAG: i32 0
+; CHECK-DAG: i32 1
+  %phi1 = phi i32 [ 0, %entry ], [ %phi2, %then ]
+  br i1 undef, label %if, label %else
+
+if:
+  br label %then
+
+else:
+  br label %then
+
+then:
+; CHECK: PHI %phi2 has values:
+; CHECK-DAG: i32 0
+; CHECK-DAG: i32 1
+  %phi2 = phi i32 [ %phi1, %if ], [ 1, %else ]
+  br i1 undef, label %loop, label %end
+
+end:
+; CHECK: PHI %phi3 has values:
+; CHECK-DAG: i32 0
+; CHECK-DAG: i32 1
+; CHECK-DAG: i32 2
+  %phi3 = phi i32 [ 2, %entry ], [ %phi2, %then ]
+  ret void
+}
+
+; CHECK-LABEL: PHI Values for function: strange_loop
+define void @strange_loop() {
+entry:
+  br i1 undef, label %ifelse, label %inloop
+
+loop:
+; CHECK: PHI %phi1 has values:
+; CHECK-DAG: i32 0
+; CHECK-DAG: i32 1
+; CHECK-DAG: i32 2
+; CHECK-DAG: i32 3
+  %phi1 = phi i32 [ %phi3, %if ], [ 0, %else ], [ %phi2, %inloop ]
+  br i1 undef, label %inloop, label %end
+
+inloop:
+; CHECK: PHI %phi2 has values:
+; CHECK-DAG: i32 0
+; CHECK-DAG: i32 1
+; CHECK-DAG: i32 2
+; CHECK-DAG: i32 3
+  %phi2 = phi i32 [ %phi1, %loop ], [ 1, %entry ]
+  br i1 undef, label %ifelse, label %loop
+
+ifelse:
+; CHECK: PHI %phi3 has values:
+; CHECK-DAG: i32 2
+; CHECK-DAG: i32 3
+  %phi3 = phi i32 [ 2, %entry ], [ 3, %inloop ]
+  br i1 undef, label %if, label %else
+
+if:
+  br label %loop
+
+else:
+  br label %loop
+
+end:
+  ret void
+}
+
+; CHECK-LABEL: PHI Values for function: mutual_loops
+define void @mutual_loops() {
+entry:
+  br i1 undef, label %loop1, label %loop2
+
+loop1:
+; CHECK: PHI %phi1 has values:
+; CHECK-DAG: 0
+; CHECK-DAG: 1
+; CHECK-DAG: 2
+; CHECK-DAG: 3
+; CHECK-DAG: 4
+  %phi1 = phi i32 [ 0, %entry ], [ %phi2, %loop1.then ], [ %phi3, %loop2.if ]
+  br i1 undef, label %loop1.if, label %loop1.else
+
+loop1.if:
+  br i1 undef, label %loop1.then, label %loop2
+
+loop1.else:
+  br label %loop1.then
+
+loop1.then:
+; CHECK: PHI %phi2 has values:
+; CHECK-DAG: 0
+; CHECK-DAG: 1
+; CHECK-DAG: 2
+; CHECK-DAG: 3
+; CHECK-DAG: 4
+  %phi2 = phi i32 [ 1, %loop1.if ], [ %phi1, %loop1.else ]
+  br i1 undef, label %loop1, label %end
+
+loop2:
+; CHECK: PHI %phi3 has values:
+; CHECK-DAG: 2
+; CHECK-DAG: 3
+; CHECK-DAG: 4
+  %phi3 = phi i32 [ 2, %entry ], [ %phi4, %loop2.then ], [ 3, %loop1.if ]
+  br i1 undef, label %loop2.if, label %loop2.else
+
+loop2.if:
+  br i1 undef, label %loop2.then, label %loop1
+
+loop2.else:
+  br label %loop2.then
+
+loop2.then:
+; CHECK: PHI %phi4 has values:
+; CHECK-DAG: 2
+; CHECK-DAG: 3
+; CHECK-DAG: 4
+  %phi4 = phi i32 [ 4, %loop2.if ], [ %phi3, %loop2.else ]
+  br i1 undef, label %loop2, label %end
+
+end:
+; CHECK: PHI %phi5 has values:
+; CHECK-DAG: 0
+; CHECK-DAG: 1
+; CHECK-DAG: 2
+; CHECK-DAG: 3
+; CHECK-DAG: 4
+  %phi5 = phi i32 [ %phi2, %loop1.then ], [ %phi4, %loop2.then ]
+  ret void
+}
+
+; CHECK-LABEL: PHI Values for function: nested_loops_several_values
+define void @nested_loops_several_values() {
+entry:
+  br label %loop1
+
+loop1:
+; CHECK: PHI %phi1 has values:
+; CHECK-DAG: i32 0
+; CHECK-DAG: %add
+  %phi1 = phi i32 [ 0, %entry ], [ %phi2, %loop2 ]
+  br i1 undef, label %loop2, label %end
+
+loop2:
+; CHECK: PHI %phi2 has values:
+; CHECK-DAG: i32 0
+; CHECK-DAG: %add
+  %phi2 = phi i32 [ %phi1, %loop1 ], [ %phi3, %loop3 ]
+  br i1 undef, label %loop3, label %loop1
+
+loop3:
+; CHECK: PHI %phi3 has values:
+; CHECK-DAG: i32 0
+; CHECK-DAG: %add
+  %phi3 = phi i32 [ %add, %loop3 ], [ %phi2, %loop2 ]
+  %add = add i32 %phi3, 1
+  br i1 undef, label %loop3, label %loop2
+
+end:
+  ret void
+}
+
+; CHECK-LABEL: PHI Values for function: nested_loops_one_value
+define void @nested_loops_one_value() {
+entry:
+  br label %loop1
+
+loop1:
+; CHECK: PHI %phi1 has values:
+; CHECK-DAG: i32 0
+  %phi1 = phi i32 [ 0, %entry ], [ %phi2, %loop2 ]
+  br i1 undef, label %loop2, label %end
+
+loop2:
+; CHECK: PHI %phi2 has values:
+; CHECK-DAG: i32 0
+  %phi2 = phi i32 [ %phi1, %loop1 ], [ %phi3, %loop3 ]
+  br i1 undef, label %loop3, label %loop1
+
+loop3:
+; CHECK: PHI %phi3 has values:
+; CHECK-DAG: i32 0
+  %phi3 = phi i32 [ 0, %loop3 ], [ %phi2, %loop2 ]
+  br i1 undef, label %loop3, label %loop2
+
+end:
+  ret void
+}