Index: include/llvm/Analysis/PhiValues.h =================================================================== --- /dev/null +++ include/llvm/Analysis/PhiValues.h @@ -0,0 +1,134 @@ +//===- 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; + + /// A map of phis to the phis that depend on it. + DenseMap PhiDependenceMap; + + /// A map of phis to the underlying values of those phis. + DenseMap PhiValueMap; + + /// The function that the PhiValues is for. + const Function &F; + + /// Process a phi so that its entry in the value map is fully populated. + void processPhi(const PHINode *PN); +}; + +/// The analysis pass which yields a PhiValues +/// +/// The analysis does nothing by itself, and just returns an empty PhiValues +/// which will get filled in as it's used. +class PhiValuesAnalysis : public AnalysisInfoMixin { + 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: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -296,6 +296,7 @@ void initializePartiallyInlineLibCallsLegacyPassPass(PassRegistry&); void initializePatchableFunctionPass(PassRegistry&); void initializePeepholeOptimizerPass(PassRegistry&); +void initializePhiValuesWrapperPassPass(PassRegistry&); void initializePhysicalRegisterUsageInfoPass(PassRegistry&); void initializePlaceBackedgeSafepointsImplPass(PassRegistry&); void initializePlaceSafepointsPass(PassRegistry&); Index: lib/Analysis/Analysis.cpp =================================================================== --- lib/Analysis/Analysis.cpp +++ lib/Analysis/Analysis.cpp @@ -68,6 +68,7 @@ initializeMustExecutePrinterPass(Registry); initializeObjCARCAAWrapperPassPass(Registry); initializeOptimizationRemarkEmitterWrapperPassPass(Registry); + initializePhiValuesWrapperPassPass(Registry); initializePostDominatorTreeWrapperPassPass(Registry); initializeRegionInfoPassPass(Registry); initializeRegionViewerPass(Registry); Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -65,6 +65,7 @@ OptimizationRemarkEmitter.cpp OrderedBasicBlock.cpp PHITransAddr.cpp + PhiValues.cpp PostDominators.cpp ProfileSummaryInfo.cpp PtrUseVisitor.cpp Index: lib/Analysis/PhiValues.cpp =================================================================== --- /dev/null +++ lib/Analysis/PhiValues.cpp @@ -0,0 +1,189 @@ +//===- 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 general idea of processing a phi is to look at its operands, then repeat +// for those operands if they themselves are phis, until we've visited all the +// phis reachable from InitialPhi. We could just collect the non-phi values that +// we obtain by doing this and set those as the value of InitialPhi, except that +// finding the values of InitialPhi necessarily involves finding the values of +// every phi reachable from it and we'd like to record those as well, and this +// is where the difficulty comes in. +// +// The way we handle it is by keeping track of which phis depend on other phis. +// When looking at a phi PN if it has a phi VPN as an operand then we mark PN +// as depending on VPN, so then when we collect the non-phi operands of VPN we +// set them as values of PN as well. In order to cope with transitive dependence +// we actually mark all phis depending on PN as depending on VPN. +// +// For phi graphs without loops this would be enough, but for phi graphs with +// loops there's an extra layer of difficulty as a phi A can have as an operand +// a phi B that we've already visited, and B can have an operand C has been +// visited and an operand D that has not been visited. The values of C will have +// been collected as the values of B, so we can handle that by adding the values +// of B to the values of A, but we also then need to mark A as depending on D. +// Or in other words, instead of marking the phis that depend on A as depending +// on B they need to depend on the phis that B depends on. +void PhiValues::processPhi(const PHINode *InitialPhi) { + SmallVector Worklist = {InitialPhi}; + do { + const PHINode *PN = Worklist.pop_back_val(); + // Insert PN into the map, and if we already had an entry skip it as we've + // already visited it. + if (!PhiValueMap.insert({PN, ValueSet()}).second) + continue; + // The loop below becomes simpler if we say a phi depends on itself. + PhiDependenceMap[PN].insert(PN); + // Examine PN's incoming values. + for (Value *V : PN->incoming_values()) { + // PN already depends on itself, so skip it if it is also an incoming + // value (which also avoids problems with modifying PhiValueMap while + // iterating over it). + if (V == PN) + continue; + if (PHINode *VPN = dyn_cast(V)) { + // If we've already visited this phi then add its values to the phis + // that depend on PN, otherwise we add it to the worklist. + if (PhiValueMap.count(VPN)) { + auto &Vals = PhiValueMap[VPN]; + for (const PHINode *D : PhiDependenceMap[PN]) { + // Don't add a phi's values to itself + if (D == VPN) + continue; + PhiValueMap[D].insert(Vals.begin(), Vals.end()); + // Phis that depend on PN depend on the phis that VPN depends on. + for (auto &Pair : PhiDependenceMap) + if (Pair.second.count(VPN)) + Pair.second.insert(D); + } + } else { + Worklist.push_back(VPN); + // Phis that depend on PN depend on VPN. Make sure to insert VPN into + // PhiDependence before we start iterating through the dependencies of + // PN, as inserting the key can move the location of PN's mapped + // value. + auto &VPNDeps = PhiDependenceMap[VPN]; + for (const PHINode *D : PhiDependenceMap[PN]) + VPNDeps.insert(D); + } + } else { + // Add V to the underlying values of everything that depends on PN. + for (const PHINode *D : PhiDependenceMap[PN]) + PhiValueMap[D].insert(V); + } + } + } while (!Worklist.empty()); +} + +const PhiValues::ValueSet &PhiValues::getValuesForPhi(const PHINode *PN) { + if (!PhiValueMap.count(PN)) + processPhi(PN); + return PhiValueMap[PN]; +} + +void PhiValues::invalidateValue(const Value *V) { + PhiSet PhisToErase; + if (const PHINode *PN = dyn_cast(V)) { + // Phis that depend on V are invalid. + for (const PHINode *D : PhiDependenceMap[PN]) + PhisToErase.insert(D); + } else { + // Phis that use V, or which depend on Phis that use V, are invalid. + for (auto It : PhiValueMap) + if (It.second.count(V)) + for (const PHINode *D : PhiDependenceMap[It.first]) + PhisToErase.insert(D); + } + for (const PHINode *PN : PhisToErase) { + PhiValueMap.erase(PN); + PhiDependenceMap.erase(PN); + } +} + +void PhiValues::releaseMemory() { + PhiValueMap.clear(); + PhiDependenceMap.clear(); +} + +void PhiValues::print(raw_ostream &OS) const { + // Iterate through the phi nodes of the function rather than iterate through + // ProcessedPhis in order to get predictable ordering. + for (const BasicBlock &BB : F) { + for (const PHINode &PN : BB.phis()) { + OS << "PHI "; + PN.printAsOperand(OS, false); + OS << " has values:\n"; + auto It = PhiValueMap.find(&PN); + if (It == PhiValueMap.end()) + OS << " UNKNOWN\n"; + else if (It->second.empty()) + OS << " NONE\n"; + else + for (Value *V : It->second) + // Printing of an instruction prints two spaces at the start, so + // handle instructions and everything else slightly differently in + // order to get consistent indenting. + if (Instruction *I = dyn_cast(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: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -41,6 +41,7 @@ #include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/ModuleSummaryAnalysis.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" +#include "llvm/Analysis/PhiValues.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/ProfileSummaryInfo.h" #include "llvm/Analysis/RegionInfo.h" Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ lib/Passes/PassRegistry.def @@ -111,6 +111,7 @@ FUNCTION_ANALYSIS("da", DependenceAnalysis()) FUNCTION_ANALYSIS("memdep", MemoryDependenceAnalysis()) FUNCTION_ANALYSIS("memoryssa", MemorySSAAnalysis()) +FUNCTION_ANALYSIS("phi-values", PhiValuesAnalysis()) FUNCTION_ANALYSIS("regions", RegionInfoAnalysis()) FUNCTION_ANALYSIS("no-op-function", NoOpFunctionAnalysis()) FUNCTION_ANALYSIS("opt-remark-emit", OptimizationRemarkEmitterAnalysis()) @@ -194,6 +195,7 @@ FUNCTION_PASS("print", 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: test/Analysis/PhiValues/basic.ll =================================================================== --- /dev/null +++ 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: test/Analysis/PhiValues/big_phi.ll =================================================================== --- /dev/null +++ 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: test/Analysis/PhiValues/long_phi_chain.ll =================================================================== --- /dev/null +++ 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: unittests/Analysis/CMakeLists.txt =================================================================== --- unittests/Analysis/CMakeLists.txt +++ unittests/Analysis/CMakeLists.txt @@ -20,6 +20,7 @@ MemoryBuiltinsTest.cpp MemorySSA.cpp OrderedBasicBlockTest.cpp + PhiValuesTest.cpp ProfileSummaryInfoTest.cpp ScalarEvolutionTest.cpp SparsePropagation.cpp Index: unittests/Analysis/PhiValuesTest.cpp =================================================================== --- /dev/null +++ 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)); +}