Add a PhiValuesAnalysis pass to calculate the underlying values of phis

[john.brawn]

Summary

This pass is being added in order to make the information available to BasicAA, which can't do caching of this information itself, but possibly this information may be useful for other passes.

Incorporates code based on Daniel Berlin's implementation of Tarjan's algorithm.

[john.brawn]

This analysis (when enabled by D44564) is causing a bunch of assertion failures/segfaults in spec2000, so it looks like there's still more work for me to do here before this is ready.

[john.brawn]

After a lot of time spent trying to get it to work, I've decided that there's no way to get the analysis to handle all possible ways that the calculated values can be invalidated without ending up with something slower than if you jsut recalculate everything from scratch every time. The problems are:

• Using ValueHandles doesn't work because plenty of passes modify a phi's operands directly and ValueHandle doesn't notice that.
• Using pointers to the Use list of the phi can cope with that, but everything goes wrong if an operand is added to the phi as the use list gets reallocated.
• Just caching the set of phis that a phi depends on and examining all of those to figure out if any have had operands changed works, but it's slower than just traversing the phi from scratch.

So I've ended up with going back to the original idea I had of having an interface to the analysis that lets you explicitly invalidate things, and using it from MemoryDependenceAnalysis where we already get notified about things being invalidated.

[sebpop]

lib/Analysis/PhiValues.cpp

46

Why not using Danny's implementation of Tarjan's algorithm?
processPhi() would be findSCC()

In D44564#1040222, @dberlin wrote:

https://reviews.llvm.org/D28934 has a version of the SCC finder you can
borrow if you want (TarjanSCC class)

// Tarjan's algorithm with Nuutila's improvements
// Wish we could use SCCIterator, but graph traits makes it *very* hard to
// create induced subgraphs because it
// 1. only works on pointers, so i can't just create an intermediate struct
// 2. the functions are static, so i can't just override them in a subclass of
// graphtraits, or otherwise store state in the struct.

struct TarjanSCC {
  unsigned int DFSNum = 1;
  SmallPtrSet<Value *, 8> InComponent;
  DenseMap<Value *, unsigned int> Root;
  SmallPtrSet<Value *, 8> PHISet;
  SmallVector<Value *, 8> Stack;
  // Store the components as vector of ptr sets, because we need the topo order
  // of SCC's, but not individual member order
  SmallVector<SmallPtrSet<PHINode *, 8>, 8> Components;
  TarjanSCC(const SmallVectorImpl<PHINode *> &Phis)
      : PHISet(Phis.begin(), Phis.end()) {
    for (auto Phi : Phis)
      if (Root.lookup(Phi) == 0)
        FindSCC(Phi);
  }
  void FindSCC(PHINode *Phi) {
    Root[Phi] = ++DFSNum;
    // Store the DFS Number we had before it possibly gets incremented.
    unsigned int OurDFS = DFSNum;
    InComponent.erase(Phi);
    for (auto &PhiOp : Phi->operands()) {
      // Only inducing the subgraph of phis we got passed
      if (!PHISet.count(PhiOp))
        continue;
      if (Root.lookup(PhiOp) == 0)
        FindSCC(cast<PHINode>(PhiOp));
      if (!InComponent.count(PhiOp))
        Root[Phi] = std::min(Root.lookup(Phi), Root.lookup(PhiOp));
    }
    // See if we really were the root, by seeing if we still have our DFSNumber,
    // or something lower
    if (Root.lookup(Phi) == OurDFS) {
      Components.resize(Components.size() + 1);
      auto &Component = Components.back();
      Component.insert(Phi);
      DEBUG(dbgs() << "Component root is " << *Phi << "\n");
      InComponent.insert(Phi);
      while (!Stack.empty() && Root.lookup(Stack.back()) >= OurDFS) {
        DEBUG(dbgs() << "Component member is " << *Stack.back() << "\n");
        Component.insert(cast<PHINode>(Stack.back()));
        InComponent.insert(Stack.back());
        Stack.pop_back();
      }
    } else {
      // Part of a component, push to stack
      Stack.push_back(Phi);
    }
  }
};

72

This code is nested at loop depth 4.

76

Same.

[john.brawn]

lib/Analysis/PhiValues.cpp

46

Why not using Danny's implementation of Tarjan's algorithm?
processPhi() would be findSCC()

The two are doing two different things:

• findSCC partitions the phi graph into a set of subgraphs where each subgraph is an SCC (each node has an edge to every other node)
• processPhi (implicitly) partitions the phi graph into a set of subgraphs where the underlying values reachable in a subgraph is the same

Taking the long_phi_chain.ll test as an example, findSCC gives us the components:

1. { phi1, phi2 }
2. { phi3, phi4, phi5 }
3. { phi6, phi7 }
4. { phi8, phi9, phi10 }
5. { phi11, phi12, phi13 }
6. { phi14 }
7. { phi15 }

which then form an SCC graph 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1.

processPhi however needs to find that all of these phis have the same set of underlying values, and I don't see a way to do this other than looking through the SCC graph in a way very similar to how processPhi looks through the phi graph (though the SCC graph will be simpler than the phi graph).

It may be possible though to do something similar to findSCC in order to explicitly construct a 'set of phis that have the same underlying values' partitioning, i.e. numbering nodes and building up stack then stacked nodes with the same number are in the same set, but I don't know if it will be simpler/faster than what I have here. I'll give it a try though.

[john.brawn]

lib/Analysis/PhiValues.cpp

46

It may be possible though to do something similar to findSCC in order to explicitly construct a 'set of phis that have the same underlying values' partitioning, i.e. numbering nodes and building up stack then stacked nodes with the same number are in the same set, but I don't know if it will be simpler/faster than what I have here. I'll give it a try though.

Because Tarjan's algorithm completes SSCs in bottom-up order, and the SCC graph is guaranteed to have no cycles, this turns out to be fairly straighforward. I'll rework this to do that.

[john.brawn]

Use Tarjan's algorithm in processPhi.

[sebpop]

Looks good to me. Thanks.

include/llvm/Analysis/PhiValues.h

+//===- 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. If new phis are added to the
+// function they are handled correctly, but if an existing phi has its operands
+// modified PhiValues has to be notified by calling invalidateValue.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_PHIVALUES_H
+#define LLVM_ANALYSIS_PHIVALUES_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.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 Use;
+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 {
+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.
+  const ValueSet &getValuesForPhi(const PHINode *PN);
+
+  /// Notify PhiValues that the cached information using V is no longer valid
+  ///
+  /// Whenever a phi has its operands modified the cached values for that phi
+  /// (and the phis that use that phi) become invalid. A user of PhiValues has
+  /// to notify it of this by calling invalidateValue on either the operand or
+  /// the phi, which will then clear the relevant cached information.
+  void invalidateValue(const Value *V);
+
+  /// Free the memory used by this class.
+  void releaseMemory();
+
+  /// Print out the values currently in the cache.
+  void print(raw_ostream &OS) const;
+
+  /// Handle invalidation events in the new pass manager.
+  bool invalidate(Function &, const PreservedAnalyses &,
+                  FunctionAnalysisManager::Invalidator &);
+
+private:
+  using PhiSet = SmallPtrSet<const PHINode *, 4>;
+
+  /// A map of phis to the phis that depend on it.
+  DenseMap<const PHINode *, PhiSet> PhiDependenceMap;
+
+  /// A map of phis to the underlying values of those phis.
+  DenseMap<const PHINode *, ValueSet> PhiValueMap;
+
+  /// 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);
+};
+
+/// 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;
+
+public:
+  static char ID;
+  PhiValuesWrapperPass();
+
+  PhiValues &getResult() { return *Result; }
+  const PhiValues &getResult() const { return *Result; }
+
+  bool runOnFunction(Function &F) override;
+  void releaseMemory() override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+};
+
+} // namespace llvm
+
+#endif

include/llvm/InitializePasses.h

 void initializePGOInstrumentationGenLegacyPassPass(PassRegistry&);
 void initializePGOInstrumentationUseLegacyPassPass(PassRegistry&);
 void initializePGOMemOPSizeOptLegacyPassPass(PassRegistry&);
 void initializePHIEliminationPass(PassRegistry&);
 void initializePartialInlinerLegacyPassPass(PassRegistry&);
 void initializePartiallyInlineLibCallsLegacyPassPass(PassRegistry&);
 void initializePatchableFunctionPass(PassRegistry&);
 void initializePeepholeOptimizerPass(PassRegistry&);
+void initializePhiValuesWrapperPassPass(PassRegistry&);
 void initializePhysicalRegisterUsageInfoPass(PassRegistry&);
 void initializePlaceBackedgeSafepointsImplPass(PassRegistry&);
 void initializePlaceSafepointsPass(PassRegistry&);
 void initializePostDomOnlyPrinterPass(PassRegistry&);
 void initializePostDomOnlyViewerPass(PassRegistry&);
 void initializePostDomPrinterPass(PassRegistry&);
 void initializePostDomViewerPass(PassRegistry&);
 void initializePostDominatorTreeWrapperPassPass(PassRegistry&);

lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeMemDepPrinterPass(Registry);
   initializeMemDerefPrinterPass(Registry);
   initializeMemoryDependenceWrapperPassPass(Registry);
   initializeModuleDebugInfoPrinterPass(Registry);
   initializeModuleSummaryIndexWrapperPassPass(Registry);
   initializeMustExecutePrinterPass(Registry);
   initializeObjCARCAAWrapperPassPass(Registry);
   initializeOptimizationRemarkEmitterWrapperPassPass(Registry);
+  initializePhiValuesWrapperPassPass(Registry);
   initializePostDominatorTreeWrapperPassPass(Registry);
   initializeRegionInfoPassPass(Registry);
   initializeRegionViewerPass(Registry);
   initializeRegionPrinterPass(Registry);
   initializeRegionOnlyViewerPass(Registry);
   initializeRegionOnlyPrinterPass(Registry);
   initializeSCEVAAWrapperPassPass(Registry);
   initializeScalarEvolutionWrapperPassPass(Registry);

lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   ModuleSummaryAnalysis.cpp
   MustExecute.cpp
   ObjCARCAliasAnalysis.cpp
   ObjCARCAnalysisUtils.cpp
   ObjCARCInstKind.cpp
   OptimizationRemarkEmitter.cpp
   OrderedBasicBlock.cpp
   PHITransAddr.cpp
+  PhiValues.cpp
   PostDominators.cpp
   ProfileSummaryInfo.cpp
   PtrUseVisitor.cpp
   RegionInfo.cpp
   RegionPass.cpp
   RegionPrinter.cpp
   ScalarEvolution.cpp
   ScalarEvolutionAliasAnalysis.cpp

lib/Analysis/PhiValues.cpp

+//===- 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;
+
+bool PhiValues::invalidate(Function &, const PreservedAnalyses &PA,
+                           FunctionAnalysisManager::Invalidator &) {
+  // PhiValues is invalidated if it isn't preserved.
+  auto PAC = PA.getChecker<PhiValuesAnalysis>();
+  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>());
+}
+
+// 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};
+  do {
+    const PHINode *PN = Worklist.pop_back_val();
+    // Insert PN into the map, and if we already had an entry skip it as we've
+    // already visited it.
+    if (!PhiValueMap.insert({PN, ValueSet()}).second)
+      continue;
+    // The loop below becomes simpler if we say a phi depends on itself.
+    PhiDependenceMap[PN].insert(PN);
+    // Examine PN's incoming values.
+    for (Value *V : PN->incoming_values()) {
+      // PN already depends on itself, so skip it if it is also an incoming
+      // value (which also avoids problems with modifying PhiValueMap while
+      // iterating over it).
+      if (V == PN)
+        continue;
+      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 (PhiValueMap.count(VPN)) {
+          auto &Vals = PhiValueMap[VPN];
+          for (const PHINode *D : PhiDependenceMap[PN]) {
+            // Don't add a phi's values to itself
+            if (D == VPN)
+              continue;
+            PhiValueMap[D].insert(Vals.begin(), Vals.end());
+            // Phis that depend on PN depend on the phis that VPN depends on.
+            for (auto &Pair : PhiDependenceMap)
+              if (Pair.second.count(VPN))
+                Pair.second.insert(D);
+          }
+        } else {
+          Worklist.push_back(VPN);
+          // Phis that depend on PN depend on VPN. Make sure to insert VPN into
+          // PhiDependence before we start iterating through the dependencies of
+          // PN, as inserting the key can move the location of PN's mapped
+          // value.
+          auto &VPNDeps = PhiDependenceMap[VPN];
+          for (const PHINode *D : PhiDependenceMap[PN])
+            VPNDeps.insert(D);
+        }
+      } else {
+        // Add V to the underlying values of everything that depends on PN.
+        for (const PHINode *D : PhiDependenceMap[PN])
+          PhiValueMap[D].insert(V);
+      }
+    }
+  } while (!Worklist.empty());
+}
+
+const PhiValues::ValueSet &PhiValues::getValuesForPhi(const PHINode *PN) {
+  if (!PhiValueMap.count(PN))
+    processPhi(PN);
+  return PhiValueMap[PN];
+}
+
+void PhiValues::invalidateValue(const Value *V) {
+  PhiSet PhisToErase;
+  if (const PHINode *PN = dyn_cast<PHINode>(V)) {
+    // Phis that depend on V are invalid.
+    for (const PHINode *D : PhiDependenceMap[PN])
+      PhisToErase.insert(D);
+  } else {
+    // Phis that use V, or which depend on Phis that use V, are invalid.
+    for (auto It : PhiValueMap)
+      if (It.second.count(V))
+        for (const PHINode *D : PhiDependenceMap[It.first])
+          PhisToErase.insert(D);
+  }
+  for (const PHINode *PN : PhisToErase) {
+    PhiValueMap.erase(PN);
+    PhiDependenceMap.erase(PN);
+  }
+}
+
+void PhiValues::releaseMemory() {
+  PhiValueMap.clear();
+  PhiDependenceMap.clear();
+}
+
+void PhiValues::print(raw_ostream &OS) const {
+  // Iterate through the phi nodes of the function rather than iterate through
+  // ProcessedPhis 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";
+      auto It = PhiValueMap.find(&PN);
+      if (It == PhiValueMap.end())
+        OS << "  UNKNOWN\n";
+      else if (It->second.empty())
+        OS << "  NONE\n";
+      else
+        for (Value *V : It->second)
+          // 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";
+    }
+  }
+}
+
+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.getValuesForPhi(&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::releaseMemory() {
+  Result->releaseMemory();
+}
+
+void PhiValuesWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+}
+
+char PhiValuesWrapperPass::ID = 0;
+
+INITIALIZE_PASS(PhiValuesWrapperPass, "phi-values", "Phi Values Analysis", false,
+                true)

lib/Passes/PassBuilder.cpp

 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #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"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/ScopedNoAliasAA.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"

lib/Passes/PassRegistry.def

 FUNCTION_ANALYSIS("postdomtree", PostDominatorTreeAnalysis())
 FUNCTION_ANALYSIS("demanded-bits", DemandedBitsAnalysis())
 FUNCTION_ANALYSIS("domfrontier", DominanceFrontierAnalysis())
 FUNCTION_ANALYSIS("loops", LoopAnalysis())
 FUNCTION_ANALYSIS("lazy-value-info", LazyValueAnalysis())
 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())
 FUNCTION_ANALYSIS("scalar-evolution", ScalarEvolutionAnalysis())
 FUNCTION_ANALYSIS("targetlibinfo", TargetLibraryAnalysis())
 FUNCTION_ANALYSIS("targetir",
                   TM ? TM->getTargetIRAnalysis() : TargetIRAnalysis())
 FUNCTION_ANALYSIS("verify", VerifierAnalysis())

 FUNCTION_PASS("print<block-freq>", BlockFrequencyPrinterPass(dbgs()))
 FUNCTION_PASS("print<branch-prob>", BranchProbabilityPrinterPass(dbgs()))
 FUNCTION_PASS("print<domtree>", DominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<postdomtree>", PostDominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<demanded-bits>", DemandedBitsPrinterPass(dbgs()))
 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())
 FUNCTION_PASS("sccp", SCCPPass())
 FUNCTION_PASS("simplify-cfg", SimplifyCFGPass())
 FUNCTION_PASS("sink", SinkingPass())
 FUNCTION_PASS("slp-vectorizer", SLPVectorizerPass())
 FUNCTION_PASS("speculative-execution", SpeculativeExecutionPass())

test/Analysis/PhiValues/basic.ll

+; 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
+}

test/Analysis/PhiValues/big_phi.ll

+; RUN: opt < %s -passes='print<phi-values>' -disable-output 2>&1 | FileCheck %s
+
+; This test has a phi with a large number of incoming values that are all the
+; same phi, and that phi depends on this phi. This is to check that phi values
+; analysis doesn't repeatedly add a phis values to itself until it segfaults.
+
+; CHECK-LABEL: PHI Values for function: fn
+define void @fn(i8* %arg) {
+entry:
+  br label %for.body
+
+for.body:
+; CHECK: PHI %phi1 has values:
+; CHECK-DAG: i8* %arg
+; CHECK-DAG: i8* undef
+  %phi1 = phi i8* [ %arg, %entry ], [ %phi2, %end ]
+  switch i32 undef, label %end [
+    i32 1, label %bb1
+    i32 2, label %bb2
+    i32 3, label %bb3
+    i32 4, label %bb4
+    i32 5, label %bb5
+    i32 6, label %bb6
+    i32 7, label %bb7
+    i32 8, label %bb8
+    i32 9, label %bb9
+    i32 10, label %bb10
+    i32 11, label %bb11
+    i32 12, label %bb12
+    i32 13, label %bb13
+  ]
+
+bb1:
+  br label %end
+
+bb2:
+  br label %end
+
+bb3:
+  br label %end
+
+bb4:
+  br label %end
+
+bb5:
+  br label %end
+
+bb6:
+  br label %end
+
+bb7:
+  br label %end
+
+bb8:
+  br label %end
+
+bb9:
+  br label %end
+
+bb10:
+  br label %end
+
+bb11:
+  br label %end
+
+bb12:
+  br label %end
+
+bb13:
+  br label %end
+
+end:
+; CHECK: PHI %phi2 has values:
+; CHECK-DAG: i8* %arg
+; CHECK-DAG: i8* undef
+  %phi2 = phi i8* [ %phi1, %for.body ], [ %phi1, %bb1 ], [ %phi1, %bb2 ], [ %phi1, %bb3 ], [ %phi1, %bb4 ], [ %phi1, %bb5 ], [ %phi1, %bb6 ], [ %phi1, %bb7 ], [ undef, %bb8 ], [ %phi1, %bb9 ], [ %phi1, %bb10 ], [ %phi1, %bb11 ], [ %phi1, %bb12 ], [ %phi1, %bb13 ]
+  br label %for.body
+}

test/Analysis/PhiValues/long_phi_chain.ll

+; RUN: opt < %s -passes='print<phi-values>' -disable-output 2>&1 | FileCheck %s
+
+; This test uses a long chain of phis that take themselves as an operand, which causes
+; phi values analysis to segfault if it's not careful about that kind of thing.
+
+; CHECK-LABEL: PHI Values for function: fn
+define void @fn(i32* %arg) {
+entry:
+  br label %while1.cond
+
+while1.cond:
+; CHECK: PHI %phi1 has values:
+; CHECK: i32* %arg
+  %phi1 = phi i32* [ %arg, %entry ], [ %phi2, %while1.then ]
+  br i1 undef, label %while1.end, label %while1.body
+
+while1.body:
+  br i1 undef, label %while1.then, label %while1.if
+
+while1.if:
+  br label %while1.then
+
+while1.then:
+; CHECK: PHI %phi2 has values:
+; CHECK: i32* %arg
+  %phi2 = phi i32* [ %arg, %while1.if ], [ %phi1, %while1.body ]
+  br label %while1.cond
+
+while1.end:
+  br label %while2.cond1
+
+while2.cond1:
+; CHECK: PHI %phi3 has values:
+; CHECK: i32* %arg
+  %phi3 = phi i32* [ %phi1, %while1.end ], [ %phi5, %while2.then ]
+  br i1 undef, label %while2.end, label %while2.body1
+
+while2.body1:
+  br i1 undef, label %while2.cond2, label %while2.then
+
+while2.cond2:
+; CHECK: PHI %phi4 has values:
+; CHECK: i32* %arg
+  %phi4 = phi i32* [ %phi3, %while2.body1 ], [ %phi4, %while2.if ]
+  br i1 undef, label %while2.then, label %while2.if
+
+while2.if:
+  br label %while2.cond2
+
+while2.then:
+; CHECK: PHI %phi5 has values:
+; CHECK: i32* %arg
+  %phi5 = phi i32* [ %phi3, %while2.body1 ], [ %phi4, %while2.cond2 ]
+  br label %while2.cond1
+
+while2.end:
+  br label %while3.cond1
+
+while3.cond1:
+; CHECK: PHI %phi6 has values:
+; CHECK: i32* %arg
+  %phi6 = phi i32* [ %phi3, %while2.end ], [ %phi7, %while3.cond2 ]
+  br i1 undef, label %while3.end, label %while3.cond2
+
+while3.cond2:
+; CHECK: PHI %phi7 has values:
+; CHECK: i32* %arg
+  %phi7 = phi i32* [ %phi6, %while3.cond1 ], [ %phi7, %while3.body ]
+  br i1 undef, label %while3.cond1, label %while3.body
+
+while3.body:
+  br label %while3.cond2
+
+while3.end:
+  br label %while4.cond1
+
+while4.cond1:
+; CHECK: PHI %phi8 has values:
+; CHECK: i32* %arg
+  %phi8 = phi i32* [ %phi6, %while3.end ], [ %phi10, %while4.then ]
+  br i1 undef, label %while4.end, label %while4.if
+
+while4.if:
+  br i1 undef, label %while4.cond2, label %while4.then
+
+while4.cond2:
+; CHECK: PHI %phi9 has values:
+; CHECK: i32* %arg
+  %phi9 = phi i32* [ %phi8, %while4.if ], [ %phi9, %while4.body ]
+  br i1 undef, label %while4.then, label %while4.body
+
+while4.body:
+  br label %while4.cond2
+
+while4.then:
+; CHECK: PHI %phi10 has values:
+; CHECK: i32* %arg
+  %phi10 = phi i32* [ %phi8, %while4.if ], [ %phi9, %while4.cond2 ]
+  br label %while4.cond1
+
+while4.end:
+  br label %while5.cond
+
+while5.cond:
+; CHECK: PHI %phi11 has values:
+; CHECK: i32* %arg
+  %phi11 = phi i32* [ %phi8, %while4.end ], [ %phi13, %while5.then ]
+  br i1 undef, label %while5.end, label %while5.body1
+
+while5.body1:
+  br i1 undef, label %while5.if, label %while5.then
+
+while5.if:
+; CHECK: PHI %phi12 has values:
+; CHECK: i32* %arg
+  %phi12 = phi i32* [ %phi11, %while5.body1 ], [ %phi12, %while5.body2 ]
+  br i1 undef, label %while5.then, label %while5.body2
+
+while5.body2:
+  br label %while5.if
+
+while5.then:
+; CHECK: PHI %phi13 has values:
+; CHECK: i32* %arg
+  %phi13 = phi i32* [ %phi11, %while5.body1 ], [ %phi12, %while5.if ]
+  br label %while5.cond
+
+while5.end:
+  br label %while6.cond1
+
+while6.cond1:
+; CHECK: PHI %phi14 has values:
+; CHECK: i32* %arg
+  %phi14 = phi i32* [ %phi11, %while5.end ], [ %phi14, %while6.cond1 ]
+  br i1 undef, label %while6.cond2, label %while6.cond1
+
+while6.cond2:
+; CHECK: PHI %phi15 has values:
+; CHECK: i32* %arg
+  %phi15 = phi i32* [ %phi14, %while6.cond1 ], [ %phi15, %while6.cond2 ]
+  br label %while6.cond2
+}

unittests/Analysis/CMakeLists.txt

add_llvm_unittest(AnalysisTests
   CGSCCPassManagerTest.cpp
   GlobalsModRefTest.cpp
   ValueLatticeTest.cpp
   LazyCallGraphTest.cpp
   LoopInfoTest.cpp
   MemoryBuiltinsTest.cpp
   MemorySSA.cpp
   OrderedBasicBlockTest.cpp
+  PhiValuesTest.cpp
   ProfileSummaryInfoTest.cpp
   ScalarEvolutionTest.cpp
   SparsePropagation.cpp
   TargetLibraryInfoTest.cpp
   TBAATest.cpp
   UnrollAnalyzer.cpp
   ValueTrackingTest.cpp
   )

unittests/Analysis/PhiValuesTest.cpp

+//===- PhiValuesTest.cpp - PhiValues unit tests ---------------------------===//
+//
+//                     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/IR/BasicBlock.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Type.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+TEST(PhiValuesTest, SimplePhi) {
+  LLVMContext C;
+  Module M("PhiValuesTest", C);
+
+  Type *VoidTy = Type::getVoidTy(C);
+  Type *I1Ty = Type::getInt1Ty(C);
+  Type *I32Ty = Type::getInt32Ty(C);
+  Type *I32PtrTy = Type::getInt32PtrTy(C);
+
+  // Create a function with phis that do not have other phis as incoming values
+  Function *F = cast<Function>(M.getOrInsertFunction("f", FunctionType::get(VoidTy, false)));
+
+  BasicBlock *Entry = BasicBlock::Create(C, "entry", F);
+  BasicBlock *If = BasicBlock::Create(C, "if", F);
+  BasicBlock *Else = BasicBlock::Create(C, "else", F);
+  BasicBlock *Then = BasicBlock::Create(C, "then", F);
+  BranchInst::Create(If, Else, UndefValue::get(I1Ty), Entry);
+  BranchInst::Create(Then, If);
+  BranchInst::Create(Then, Else);
+
+  Value *Val1 = new LoadInst(UndefValue::get(I32PtrTy), "val1", Entry);
+  Value *Val2 = new LoadInst(UndefValue::get(I32PtrTy), "val2", Entry);
+  Value *Val3 = new LoadInst(UndefValue::get(I32PtrTy), "val3", Entry);
+  Value *Val4 = new LoadInst(UndefValue::get(I32PtrTy), "val4", Entry);
+
+  PHINode *Phi1 = PHINode::Create(I32Ty, 2, "phi1", Then);
+  Phi1->addIncoming(Val1, If);
+  Phi1->addIncoming(Val2, Else);
+  PHINode *Phi2 = PHINode::Create(I32Ty, 2, "phi2", Then);
+  Phi2->addIncoming(Val1, If);
+  Phi2->addIncoming(Val3, Else);
+
+  PhiValues PV(*F);
+  PhiValues::ValueSet Vals;
+
+  // Check that simple usage works
+  Vals = PV.getValuesForPhi(Phi1);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val1));
+  EXPECT_TRUE(Vals.count(Val2));
+  Vals = PV.getValuesForPhi(Phi2);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val1));
+  EXPECT_TRUE(Vals.count(Val3));
+
+  // Check that values are updated when one value is replaced with another
+  Val1->replaceAllUsesWith(Val4);
+  PV.invalidateValue(Val1);
+  Vals = PV.getValuesForPhi(Phi1);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val4));
+  EXPECT_TRUE(Vals.count(Val2));
+  Vals = PV.getValuesForPhi(Phi2);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val4));
+  EXPECT_TRUE(Vals.count(Val3));
+
+  // Check that setting in incoming value directly updates the values
+  Phi1->setIncomingValue(0, Val1);
+  PV.invalidateValue(Phi1);
+  Vals = PV.getValuesForPhi(Phi1);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val1));
+  EXPECT_TRUE(Vals.count(Val2));
+}
+
+TEST(PhiValuesTest, DependentPhi) {
+  LLVMContext C;
+  Module M("PhiValuesTest", C);
+
+  Type *VoidTy = Type::getVoidTy(C);
+  Type *I1Ty = Type::getInt1Ty(C);
+  Type *I32Ty = Type::getInt32Ty(C);
+  Type *I32PtrTy = Type::getInt32PtrTy(C);
+
+  // Create a function with a phi that has another phi as an incoming value
+  Function *F = cast<Function>(M.getOrInsertFunction("f", FunctionType::get(VoidTy, false)));
+
+  BasicBlock *Entry = BasicBlock::Create(C, "entry", F);
+  BasicBlock *If1 = BasicBlock::Create(C, "if1", F);
+  BasicBlock *Else1 = BasicBlock::Create(C, "else1", F);
+  BasicBlock *Then = BasicBlock::Create(C, "then", F);
+  BasicBlock *If2 = BasicBlock::Create(C, "if2", F);
+  BasicBlock *Else2 = BasicBlock::Create(C, "else2", F);
+  BasicBlock *End = BasicBlock::Create(C, "then", F);
+  BranchInst::Create(If1, Else1, UndefValue::get(I1Ty), Entry);
+  BranchInst::Create(Then, If1);
+  BranchInst::Create(Then, Else1);
+  BranchInst::Create(If2, Else2, UndefValue::get(I1Ty), Then);
+  BranchInst::Create(End, If2);
+  BranchInst::Create(End, Else2);
+
+  Value *Val1 = new LoadInst(UndefValue::get(I32PtrTy), "val1", Entry);
+  Value *Val2 = new LoadInst(UndefValue::get(I32PtrTy), "val2", Entry);
+  Value *Val3 = new LoadInst(UndefValue::get(I32PtrTy), "val3", Entry);
+  Value *Val4 = new LoadInst(UndefValue::get(I32PtrTy), "val4", Entry);
+
+  PHINode *Phi1 = PHINode::Create(I32Ty, 2, "phi1", Then);
+  Phi1->addIncoming(Val1, If1);
+  Phi1->addIncoming(Val2, Else1);
+  PHINode *Phi2 = PHINode::Create(I32Ty, 2, "phi2", Then);
+  Phi2->addIncoming(Val2, If1);
+  Phi2->addIncoming(Val3, Else1);
+  PHINode *Phi3 = PHINode::Create(I32Ty, 2, "phi3", End);
+  Phi3->addIncoming(Phi1, If2);
+  Phi3->addIncoming(Val3, Else2);
+
+  PhiValues PV(*F);
+  PhiValues::ValueSet Vals;
+
+  // Check that simple usage works
+  Vals = PV.getValuesForPhi(Phi1);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val1));
+  EXPECT_TRUE(Vals.count(Val2));
+  Vals = PV.getValuesForPhi(Phi2);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val2));
+  EXPECT_TRUE(Vals.count(Val3));
+  Vals = PV.getValuesForPhi(Phi3);
+  EXPECT_EQ(Vals.size(), 3u);
+  EXPECT_TRUE(Vals.count(Val1));
+  EXPECT_TRUE(Vals.count(Val2));
+  EXPECT_TRUE(Vals.count(Val3));
+
+  // Check that changing an incoming value in the dependent phi changes the depending phi
+  Phi1->setIncomingValue(0, Val4);
+  PV.invalidateValue(Phi1);
+  Vals = PV.getValuesForPhi(Phi1);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val4));
+  EXPECT_TRUE(Vals.count(Val2));
+  Vals = PV.getValuesForPhi(Phi2);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val2));
+  EXPECT_TRUE(Vals.count(Val3));
+  Vals = PV.getValuesForPhi(Phi3);
+  EXPECT_EQ(Vals.size(), 3u);
+  EXPECT_TRUE(Vals.count(Val4));
+  EXPECT_TRUE(Vals.count(Val2));
+  EXPECT_TRUE(Vals.count(Val3));
+
+  // Check that replacing an incoming phi with a value works
+  Phi3->setIncomingValue(0, Val1);
+  PV.invalidateValue(Phi3);
+  Vals = PV.getValuesForPhi(Phi1);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val4));
+  EXPECT_TRUE(Vals.count(Val2));
+  Vals = PV.getValuesForPhi(Phi2);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val2));
+  EXPECT_TRUE(Vals.count(Val3));
+  Vals = PV.getValuesForPhi(Phi3);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val1));
+  EXPECT_TRUE(Vals.count(Val3));
+
+  // Check that adding a phi as an incoming value works
+  Phi3->setIncomingValue(1, Phi2);
+  PV.invalidateValue(Phi3);
+  Vals = PV.getValuesForPhi(Phi1);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val4));
+  EXPECT_TRUE(Vals.count(Val2));
+  Vals = PV.getValuesForPhi(Phi2);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val2));
+  EXPECT_TRUE(Vals.count(Val3));
+  Vals = PV.getValuesForPhi(Phi3);
+  EXPECT_EQ(Vals.size(), 3u);
+  EXPECT_TRUE(Vals.count(Val1));
+  EXPECT_TRUE(Vals.count(Val2));
+  EXPECT_TRUE(Vals.count(Val3));
+
+  // Check that replacing an incoming phi then deleting it works
+  Phi3->setIncomingValue(1, Val2);
+  Phi2->eraseFromParent();
+  PV.invalidateValue(Phi2);
+  PV.invalidateValue(Phi3);
+  Vals = PV.getValuesForPhi(Phi1);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val4));
+  EXPECT_TRUE(Vals.count(Val2));
+  Vals = PV.getValuesForPhi(Phi3);
+  EXPECT_EQ(Vals.size(), 2u);
+  EXPECT_TRUE(Vals.count(Val1));
+  EXPECT_TRUE(Vals.count(Val2));
+}