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

45 ↗

(On Diff #150360)

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

71 ↗

(On Diff #150360)

This code is nested at loop depth 4.

75 ↗

(On Diff #150360)

Same.

[john.brawn]

lib/Analysis/PhiValues.cpp

45 ↗

(On Diff #150360)

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

45 ↗

(On Diff #150360)

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.

llvm/trunk/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>;
+  using ConstValueSet = SmallPtrSet<const Value *, 4>;
+
+  /// The next depth number to be used by processPhi.
+  unsigned int NextDepthNumber = 1;
+
+  /// Depth numbers of phis. Phis with the same depth number are part of the
+  /// same strongly connected component.
+  DenseMap<const PHINode *, unsigned int> DepthMap;
+
+  /// Non-phi values reachable from each component.
+  DenseMap<unsigned int, ValueSet> NonPhiReachableMap;
+
+  /// All values reachable from each component.
+  DenseMap<unsigned int, ConstValueSet> ReachableMap;
+
+  /// The function that the PhiValues is for.
+  const Function &F;
+
+  /// Process a phi so that its entries in the depth and reachable maps are
+  /// fully populated.
+  void processPhi(const PHINode *PN, SmallVector<const PHINode *, 8> &Stack);
+};
+
+/// 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

llvm/trunk/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&);

llvm/trunk/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);

llvm/trunk/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

llvm/trunk/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 goal here is to find all of the non-phi values reachable from this phi,
+// and to do the same for all of the phis reachable from this phi, as doing so
+// is necessary anyway in order to get the values for this phi. We do this using
+// Tarjan's algorithm with Nuutila's improvements to find the strongly connected
+// components of the phi graph rooted in this phi:
+//  * All phis in a strongly connected component will have the same reachable
+//    non-phi values. The SCC may not be the maximal subgraph for that set of
+//    reachable values, but finding out that isn't really necessary (it would
+//    only reduce the amount of memory needed to store the values).
+//  * Tarjan's algorithm completes components in a bottom-up manner, i.e. it
+//    never completes a component before the components reachable from it have
+//    been completed. This means that when we complete a component we have
+//    everything we need to collect the values reachable from that component.
+//  * We collect both the non-phi values reachable from each SCC, as that's what
+//    we're ultimately interested in, and all of the reachable values, i.e.
+//    including phis, as that makes invalidateValue easier.
+void PhiValues::processPhi(const PHINode *Phi,
+                           SmallVector<const PHINode *, 8> &Stack) {
+  // Initialize the phi with the next depth number.
+  assert(DepthMap.lookup(Phi) == 0);
+  assert(NextDepthNumber != UINT_MAX);
+  unsigned int DepthNumber = ++NextDepthNumber;
+  DepthMap[Phi] = DepthNumber;
+
+  // Recursively process the incoming phis of this phi.
+  for (Value *PhiOp : Phi->incoming_values()) {
+    if (PHINode *PhiPhiOp = dyn_cast<PHINode>(PhiOp)) {
+      // Recurse if the phi has not yet been visited.
+      if (DepthMap.lookup(PhiPhiOp) == 0)
+        processPhi(PhiPhiOp, Stack);
+      assert(DepthMap.lookup(PhiPhiOp) != 0);
+      // If the phi did not become part of a component then this phi and that
+      // phi are part of the same component, so adjust the depth number.
+      if (!ReachableMap.count(DepthMap[PhiPhiOp]))
+        DepthMap[Phi] = std::min(DepthMap[Phi], DepthMap[PhiPhiOp]);
+    }
+  }
+
+  // Now that incoming phis have been handled, push this phi to the stack.
+  Stack.push_back(Phi);
+
+  // If the depth number has not changed then we've finished collecting the phis
+  // of a strongly connected component.
+  if (DepthMap[Phi] == DepthNumber) {
+    // Collect the reachable values for this component. The phis of this
+    // component will be those on top of the depth stach with the same or
+    // greater depth number.
+    ConstValueSet Reachable;
+    while (!Stack.empty() && DepthMap[Stack.back()] >= DepthNumber) {
+      const PHINode *ComponentPhi = Stack.pop_back_val();
+      Reachable.insert(ComponentPhi);
+      DepthMap[ComponentPhi] = DepthNumber;
+      for (Value *Op : ComponentPhi->incoming_values()) {
+        if (PHINode *PhiOp = dyn_cast<PHINode>(Op)) {
+          // If this phi is not part of the same component then that component
+          // is guaranteed to have been completed before this one. Therefore we
+          // can just add its reachable values to the reachable values of this
+          // component.
+          auto It = ReachableMap.find(DepthMap[PhiOp]);
+          if (It != ReachableMap.end())
+            Reachable.insert(It->second.begin(), It->second.end());
+        } else {
+          Reachable.insert(Op);
+        }
+      }
+    }
+    ReachableMap.insert({DepthNumber,Reachable});
+
+    // Filter out phis to get the non-phi reachable values.
+    ValueSet NonPhi;
+    for (const Value *V : Reachable)
+      if (!isa<PHINode>(V))
+        NonPhi.insert(const_cast<Value*>(V));
+    NonPhiReachableMap.insert({DepthNumber,NonPhi});
+  }
+}
+
+const PhiValues::ValueSet &PhiValues::getValuesForPhi(const PHINode *PN) {
+  if (DepthMap.count(PN) == 0) {
+    SmallVector<const PHINode *, 8> Stack;
+    processPhi(PN, Stack);
+    assert(Stack.empty());
+  }
+  assert(DepthMap.lookup(PN) != 0);
+  return NonPhiReachableMap[DepthMap[PN]];
+}
+
+void PhiValues::invalidateValue(const Value *V) {
+  // Components that can reach V are invalid.
+  SmallVector<unsigned int, 8> InvalidComponents;
+  for (auto &Pair : ReachableMap)
+    if (Pair.second.count(V))
+      InvalidComponents.push_back(Pair.first);
+
+  for (unsigned int N : InvalidComponents) {
+    for (const Value *V : ReachableMap[N])
+      if (const PHINode *PN = dyn_cast<PHINode>(V))
+        DepthMap.erase(PN);
+    NonPhiReachableMap.erase(N);
+    ReachableMap.erase(N);
+  }
+}
+
+void PhiValues::releaseMemory() {
+  DepthMap.clear();
+  NonPhiReachableMap.clear();
+  ReachableMap.clear();
+}
+
+void PhiValues::print(raw_ostream &OS) const {
+  // Iterate through the phi nodes of the function rather than iterating through
+  // DepthMap 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";
+      unsigned int N = DepthMap.lookup(&PN);
+      auto It = NonPhiReachableMap.find(N);
+      if (It == NonPhiReachableMap.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)

llvm/trunk/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"

llvm/trunk/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())

llvm/trunk/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
+}

llvm/trunk/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
+}

llvm/trunk/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
+}

llvm/trunk/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
   )

llvm/trunk/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));
+}