Index: llvm/trunk/include/llvm/Analysis/PhiValues.h =================================================================== --- llvm/trunk/include/llvm/Analysis/PhiValues.h +++ llvm/trunk/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; + + /// 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; + using ConstValueSet = SmallPtrSet; + + /// 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 DepthMap; + + /// Non-phi values reachable from each component. + DenseMap NonPhiReachableMap; + + /// All values reachable from each component. + DenseMap 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 &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 { + friend AnalysisInfoMixin; + 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 { + 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 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 Index: llvm/trunk/include/llvm/InitializePasses.h =================================================================== --- llvm/trunk/include/llvm/InitializePasses.h +++ llvm/trunk/include/llvm/InitializePasses.h @@ -296,6 +296,7 @@ void initializePartiallyInlineLibCallsLegacyPassPass(PassRegistry&); void initializePatchableFunctionPass(PassRegistry&); void initializePeepholeOptimizerPass(PassRegistry&); +void initializePhiValuesWrapperPassPass(PassRegistry&); void initializePhysicalRegisterUsageInfoPass(PassRegistry&); void initializePlaceBackedgeSafepointsImplPass(PassRegistry&); void initializePlaceSafepointsPass(PassRegistry&); Index: llvm/trunk/lib/Analysis/Analysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/Analysis.cpp +++ llvm/trunk/lib/Analysis/Analysis.cpp @@ -68,6 +68,7 @@ initializeMustExecutePrinterPass(Registry); initializeObjCARCAAWrapperPassPass(Registry); initializeOptimizationRemarkEmitterWrapperPassPass(Registry); + initializePhiValuesWrapperPassPass(Registry); initializePostDominatorTreeWrapperPassPass(Registry); initializeRegionInfoPassPass(Registry); initializeRegionViewerPass(Registry); Index: llvm/trunk/lib/Analysis/CMakeLists.txt =================================================================== --- llvm/trunk/lib/Analysis/CMakeLists.txt +++ llvm/trunk/lib/Analysis/CMakeLists.txt @@ -65,6 +65,7 @@ OptimizationRemarkEmitter.cpp OrderedBasicBlock.cpp PHITransAddr.cpp + PhiValues.cpp PostDominators.cpp ProfileSummaryInfo.cpp PtrUseVisitor.cpp Index: llvm/trunk/lib/Analysis/PhiValues.cpp =================================================================== --- llvm/trunk/lib/Analysis/PhiValues.cpp +++ llvm/trunk/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(); + return !(PAC.preserved() || PAC.preservedSet>()); +} + +// 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 &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(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(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(V)) + NonPhi.insert(const_cast(V)); + NonPhiReachableMap.insert({DepthNumber,NonPhi}); + } +} + +const PhiValues::ValueSet &PhiValues::getValuesForPhi(const PHINode *PN) { + if (DepthMap.count(PN) == 0) { + SmallVector 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 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(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(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(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) Index: llvm/trunk/lib/Passes/PassBuilder.cpp =================================================================== --- llvm/trunk/lib/Passes/PassBuilder.cpp +++ llvm/trunk/lib/Passes/PassBuilder.cpp @@ -41,6 +41,7 @@ #include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/ModuleSummaryAnalysis.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" +#include "llvm/Analysis/PhiValues.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/ProfileSummaryInfo.h" #include "llvm/Analysis/RegionInfo.h" Index: llvm/trunk/lib/Passes/PassRegistry.def =================================================================== --- llvm/trunk/lib/Passes/PassRegistry.def +++ llvm/trunk/lib/Passes/PassRegistry.def @@ -111,6 +111,7 @@ FUNCTION_ANALYSIS("da", DependenceAnalysis()) FUNCTION_ANALYSIS("memdep", MemoryDependenceAnalysis()) FUNCTION_ANALYSIS("memoryssa", MemorySSAAnalysis()) +FUNCTION_ANALYSIS("phi-values", PhiValuesAnalysis()) FUNCTION_ANALYSIS("regions", RegionInfoAnalysis()) FUNCTION_ANALYSIS("no-op-function", NoOpFunctionAnalysis()) FUNCTION_ANALYSIS("opt-remark-emit", OptimizationRemarkEmitterAnalysis()) @@ -194,6 +195,7 @@ FUNCTION_PASS("print", DominanceFrontierPrinterPass(dbgs())) FUNCTION_PASS("print", LoopPrinterPass(dbgs())) FUNCTION_PASS("print", MemorySSAPrinterPass(dbgs())) +FUNCTION_PASS("print", PhiValuesPrinterPass(dbgs())) FUNCTION_PASS("print", RegionInfoPrinterPass(dbgs())) FUNCTION_PASS("print", ScalarEvolutionPrinterPass(dbgs())) FUNCTION_PASS("reassociate", ReassociatePass()) Index: llvm/trunk/test/Analysis/PhiValues/basic.ll =================================================================== --- llvm/trunk/test/Analysis/PhiValues/basic.ll +++ llvm/trunk/test/Analysis/PhiValues/basic.ll @@ -0,0 +1,282 @@ +; RUN: opt < %s -passes='print' -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 +} Index: llvm/trunk/test/Analysis/PhiValues/big_phi.ll =================================================================== --- llvm/trunk/test/Analysis/PhiValues/big_phi.ll +++ llvm/trunk/test/Analysis/PhiValues/big_phi.ll @@ -0,0 +1,78 @@ +; RUN: opt < %s -passes='print' -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 +} Index: llvm/trunk/test/Analysis/PhiValues/long_phi_chain.ll =================================================================== --- llvm/trunk/test/Analysis/PhiValues/long_phi_chain.ll +++ llvm/trunk/test/Analysis/PhiValues/long_phi_chain.ll @@ -0,0 +1,142 @@ +; RUN: opt < %s -passes='print' -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 +} Index: llvm/trunk/unittests/Analysis/CMakeLists.txt =================================================================== --- llvm/trunk/unittests/Analysis/CMakeLists.txt +++ llvm/trunk/unittests/Analysis/CMakeLists.txt @@ -20,6 +20,7 @@ MemoryBuiltinsTest.cpp MemorySSA.cpp OrderedBasicBlockTest.cpp + PhiValuesTest.cpp ProfileSummaryInfoTest.cpp ScalarEvolutionTest.cpp SparsePropagation.cpp Index: llvm/trunk/unittests/Analysis/PhiValuesTest.cpp =================================================================== --- llvm/trunk/unittests/Analysis/PhiValuesTest.cpp +++ llvm/trunk/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(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(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)); +}