summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/include/llvm/Analysis/PhiValues.h143
-rw-r--r--llvm/include/llvm/InitializePasses.h1
-rw-r--r--llvm/lib/Analysis/Analysis.cpp1
-rw-r--r--llvm/lib/Analysis/CMakeLists.txt1
-rw-r--r--llvm/lib/Analysis/PhiValues.cpp196
-rw-r--r--llvm/lib/Passes/PassBuilder.cpp1
-rw-r--r--llvm/lib/Passes/PassRegistry.def2
-rw-r--r--llvm/test/Analysis/PhiValues/basic.ll282
-rw-r--r--llvm/test/Analysis/PhiValues/big_phi.ll78
-rw-r--r--llvm/test/Analysis/PhiValues/long_phi_chain.ll142
-rw-r--r--llvm/unittests/Analysis/CMakeLists.txt1
-rw-r--r--llvm/unittests/Analysis/PhiValuesTest.cpp208
12 files changed, 1056 insertions, 0 deletions
diff --git a/llvm/include/llvm/Analysis/PhiValues.h b/llvm/include/llvm/Analysis/PhiValues.h
new file mode 100644
index 00000000000..6607b329c04
--- /dev/null
+++ b/llvm/include/llvm/Analysis/PhiValues.h
@@ -0,0 +1,143 @@
+//===- 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
diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h
index 55132d38c20..58ccb0ad7f0 100644
--- a/llvm/include/llvm/InitializePasses.h
+++ b/llvm/include/llvm/InitializePasses.h
@@ -296,6 +296,7 @@ void initializePartialInlinerLegacyPassPass(PassRegistry&);
void initializePartiallyInlineLibCallsLegacyPassPass(PassRegistry&);
void initializePatchableFunctionPass(PassRegistry&);
void initializePeepholeOptimizerPass(PassRegistry&);
+void initializePhiValuesWrapperPassPass(PassRegistry&);
void initializePhysicalRegisterUsageInfoPass(PassRegistry&);
void initializePlaceBackedgeSafepointsImplPass(PassRegistry&);
void initializePlaceSafepointsPass(PassRegistry&);
diff --git a/llvm/lib/Analysis/Analysis.cpp b/llvm/lib/Analysis/Analysis.cpp
index 401ce7a25a7..30576cf1ae1 100644
--- a/llvm/lib/Analysis/Analysis.cpp
+++ b/llvm/lib/Analysis/Analysis.cpp
@@ -68,6 +68,7 @@ void llvm::initializeAnalysis(PassRegistry &Registry) {
initializeMustExecutePrinterPass(Registry);
initializeObjCARCAAWrapperPassPass(Registry);
initializeOptimizationRemarkEmitterWrapperPassPass(Registry);
+ initializePhiValuesWrapperPassPass(Registry);
initializePostDominatorTreeWrapperPassPass(Registry);
initializeRegionInfoPassPass(Registry);
initializeRegionViewerPass(Registry);
diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt
index 8b4bb36c6ae..8e8535abd05 100644
--- a/llvm/lib/Analysis/CMakeLists.txt
+++ b/llvm/lib/Analysis/CMakeLists.txt
@@ -65,6 +65,7 @@ add_llvm_library(LLVMAnalysis
OptimizationRemarkEmitter.cpp
OrderedBasicBlock.cpp
PHITransAddr.cpp
+ PhiValues.cpp
PostDominators.cpp
ProfileSummaryInfo.cpp
PtrUseVisitor.cpp
diff --git a/llvm/lib/Analysis/PhiValues.cpp b/llvm/lib/Analysis/PhiValues.cpp
new file mode 100644
index 00000000000..ef121815d2c
--- /dev/null
+++ b/llvm/lib/Analysis/PhiValues.cpp
@@ -0,0 +1,196 @@
+//===- 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)
diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp
index 9fdcbc5a234..0cdd6476155 100644
--- a/llvm/lib/Passes/PassBuilder.cpp
+++ b/llvm/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"
diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def
index 97e7ca8f0d8..0a8d40a5ba9 100644
--- a/llvm/lib/Passes/PassRegistry.def
+++ b/llvm/lib/Passes/PassRegistry.def
@@ -111,6 +111,7 @@ 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())
@@ -194,6 +195,7 @@ 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())
diff --git a/llvm/test/Analysis/PhiValues/basic.ll b/llvm/test/Analysis/PhiValues/basic.ll
new file mode 100644
index 00000000000..ca013828368
--- /dev/null
+++ b/llvm/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
+}
diff --git a/llvm/test/Analysis/PhiValues/big_phi.ll b/llvm/test/Analysis/PhiValues/big_phi.ll
new file mode 100644
index 00000000000..6f13098db60
--- /dev/null
+++ b/llvm/test/Analysis/PhiValues/big_phi.ll
@@ -0,0 +1,78 @@
+; 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
+}
diff --git a/llvm/test/Analysis/PhiValues/long_phi_chain.ll b/llvm/test/Analysis/PhiValues/long_phi_chain.ll
new file mode 100644
index 00000000000..850c4f1d51e
--- /dev/null
+++ b/llvm/test/Analysis/PhiValues/long_phi_chain.ll
@@ -0,0 +1,142 @@
+; 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
+}
diff --git a/llvm/unittests/Analysis/CMakeLists.txt b/llvm/unittests/Analysis/CMakeLists.txt
index 65f2aeda418..f6ff29064be 100644
--- a/llvm/unittests/Analysis/CMakeLists.txt
+++ b/llvm/unittests/Analysis/CMakeLists.txt
@@ -20,6 +20,7 @@ add_llvm_unittest(AnalysisTests
MemoryBuiltinsTest.cpp
MemorySSA.cpp
OrderedBasicBlockTest.cpp
+ PhiValuesTest.cpp
ProfileSummaryInfoTest.cpp
ScalarEvolutionTest.cpp
SparsePropagation.cpp
diff --git a/llvm/unittests/Analysis/PhiValuesTest.cpp b/llvm/unittests/Analysis/PhiValuesTest.cpp
new file mode 100644
index 00000000000..9a1b5d7ec6c
--- /dev/null
+++ b/llvm/unittests/Analysis/PhiValuesTest.cpp
@@ -0,0 +1,208 @@
+//===- 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));
+}
OpenPOWER on IntegriCloud