1//===- PhiValues.cpp - Phi Value Analysis ---------------------------------===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8 9#include "llvm/Analysis/PhiValues.h" 10#include "llvm/ADT/SmallVector.h" 11#include "llvm/IR/Instructions.h" 12#include "llvm/InitializePasses.h" 13 14using namespace llvm; 15 16void PhiValues::PhiValuesCallbackVH::deleted() { 17 PV->invalidateValue(getValPtr()); 18} 19 20void PhiValues::PhiValuesCallbackVH::allUsesReplacedWith(Value *) { 21 // We could potentially update the cached values we have with the new value, 22 // but it's simpler to just treat the old value as invalidated. 23 PV->invalidateValue(getValPtr()); 24} 25 26bool PhiValues::invalidate(Function &, const PreservedAnalyses &PA, 27 FunctionAnalysisManager::Invalidator &) { 28 // PhiValues is invalidated if it isn't preserved. 29 auto PAC = PA.getChecker<PhiValuesAnalysis>(); 30 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()); 31} 32 33// The goal here is to find all of the non-phi values reachable from this phi, 34// and to do the same for all of the phis reachable from this phi, as doing so 35// is necessary anyway in order to get the values for this phi. We do this using 36// Tarjan's algorithm with Nuutila's improvements to find the strongly connected 37// components of the phi graph rooted in this phi: 38// * All phis in a strongly connected component will have the same reachable 39// non-phi values. The SCC may not be the maximal subgraph for that set of 40// reachable values, but finding out that isn't really necessary (it would 41// only reduce the amount of memory needed to store the values). 42// * Tarjan's algorithm completes components in a bottom-up manner, i.e. it 43// never completes a component before the components reachable from it have 44// been completed. This means that when we complete a component we have 45// everything we need to collect the values reachable from that component. 46// * We collect both the non-phi values reachable from each SCC, as that's what 47// we're ultimately interested in, and all of the reachable values, i.e. 48// including phis, as that makes invalidateValue easier. 49void PhiValues::processPhi(const PHINode *Phi, 50 SmallVectorImpl<const PHINode *> &Stack) { 51 // Initialize the phi with the next depth number. 52 assert(DepthMap.lookup(Phi) == 0); 53 assert(NextDepthNumber != UINT_MAX); 54 unsigned int RootDepthNumber = ++NextDepthNumber; 55 DepthMap[Phi] = RootDepthNumber; 56 57 // Recursively process the incoming phis of this phi. 58 TrackedValues.insert(PhiValuesCallbackVH(const_cast<PHINode *>(Phi), this)); 59 for (Value *PhiOp : Phi->incoming_values()) { 60 if (PHINode *PhiPhiOp = dyn_cast<PHINode>(PhiOp)) { 61 // Recurse if the phi has not yet been visited. 62 unsigned int OpDepthNumber = DepthMap.lookup(PhiPhiOp); 63 if (OpDepthNumber == 0) { 64 processPhi(PhiPhiOp, Stack); 65 OpDepthNumber = DepthMap.lookup(PhiPhiOp); 66 assert(OpDepthNumber != 0); 67 } 68 // If the phi did not become part of a component then this phi and that 69 // phi are part of the same component, so adjust the depth number. 70 if (!ReachableMap.count(OpDepthNumber)) 71 DepthMap[Phi] = std::min(DepthMap[Phi], OpDepthNumber); 72 } else { 73 TrackedValues.insert(PhiValuesCallbackVH(PhiOp, this)); 74 } 75 } 76 77 // Now that incoming phis have been handled, push this phi to the stack. 78 Stack.push_back(Phi); 79 80 // If the depth number has not changed then we've finished collecting the phis 81 // of a strongly connected component. 82 if (DepthMap[Phi] == RootDepthNumber) { 83 // Collect the reachable values for this component. The phis of this 84 // component will be those on top of the depth stack with the same or 85 // greater depth number. 86 ConstValueSet &Reachable = ReachableMap[RootDepthNumber]; 87 while (true) { 88 const PHINode *ComponentPhi = Stack.pop_back_val(); 89 Reachable.insert(ComponentPhi); 90 91 for (Value *Op : ComponentPhi->incoming_values()) { 92 if (PHINode *PhiOp = dyn_cast<PHINode>(Op)) { 93 // If this phi is not part of the same component then that component 94 // is guaranteed to have been completed before this one. Therefore we 95 // can just add its reachable values to the reachable values of this 96 // component. 97 unsigned int OpDepthNumber = DepthMap[PhiOp]; 98 if (OpDepthNumber != RootDepthNumber) { 99 auto It = ReachableMap.find(OpDepthNumber); 100 if (It != ReachableMap.end()) 101 Reachable.insert(It->second.begin(), It->second.end()); 102 } 103 } else 104 Reachable.insert(Op); 105 } 106 107 if (Stack.empty()) 108 break; 109 110 unsigned int &ComponentDepthNumber = DepthMap[Stack.back()]; 111 if (ComponentDepthNumber < RootDepthNumber) 112 break; 113 114 ComponentDepthNumber = RootDepthNumber; 115 } 116 117 // Filter out phis to get the non-phi reachable values. 118 ValueSet &NonPhi = NonPhiReachableMap[RootDepthNumber]; 119 for (const Value *V : Reachable) 120 if (!isa<PHINode>(V)) 121 NonPhi.insert(const_cast<Value *>(V)); 122 } 123} 124 125const PhiValues::ValueSet &PhiValues::getValuesForPhi(const PHINode *PN) { 126 unsigned int DepthNumber = DepthMap.lookup(PN); 127 if (DepthNumber == 0) { 128 SmallVector<const PHINode *, 8> Stack; 129 processPhi(PN, Stack); 130 DepthNumber = DepthMap.lookup(PN); 131 assert(Stack.empty()); 132 assert(DepthNumber != 0); 133 } 134 return NonPhiReachableMap[DepthNumber]; 135} 136 137void PhiValues::invalidateValue(const Value *V) { 138 // Components that can reach V are invalid. 139 SmallVector<unsigned int, 8> InvalidComponents; 140 for (auto &Pair : ReachableMap) 141 if (Pair.second.count(V)) 142 InvalidComponents.push_back(Pair.first); 143 144 for (unsigned int N : InvalidComponents) { 145 for (const Value *V : ReachableMap[N]) 146 if (const PHINode *PN = dyn_cast<PHINode>(V)) 147 DepthMap.erase(PN); 148 NonPhiReachableMap.erase(N); 149 ReachableMap.erase(N); 150 } 151 // This value is no longer tracked 152 auto It = TrackedValues.find_as(V); 153 if (It != TrackedValues.end()) 154 TrackedValues.erase(It); 155} 156 157void PhiValues::releaseMemory() { 158 DepthMap.clear(); 159 NonPhiReachableMap.clear(); 160 ReachableMap.clear(); 161} 162 163void PhiValues::print(raw_ostream &OS) const { 164 // Iterate through the phi nodes of the function rather than iterating through 165 // DepthMap in order to get predictable ordering. 166 for (const BasicBlock &BB : F) { 167 for (const PHINode &PN : BB.phis()) { 168 OS << "PHI "; 169 PN.printAsOperand(OS, false); 170 OS << " has values:\n"; 171 unsigned int N = DepthMap.lookup(&PN); 172 auto It = NonPhiReachableMap.find(N); 173 if (It == NonPhiReachableMap.end()) 174 OS << " UNKNOWN\n"; 175 else if (It->second.empty()) 176 OS << " NONE\n"; 177 else 178 for (Value *V : It->second) 179 // Printing of an instruction prints two spaces at the start, so 180 // handle instructions and everything else slightly differently in 181 // order to get consistent indenting. 182 if (Instruction *I = dyn_cast<Instruction>(V)) 183 OS << *I << "\n"; 184 else 185 OS << " " << *V << "\n"; 186 } 187 } 188} 189 190AnalysisKey PhiValuesAnalysis::Key; 191PhiValues PhiValuesAnalysis::run(Function &F, FunctionAnalysisManager &) { 192 return PhiValues(F); 193} 194 195PreservedAnalyses PhiValuesPrinterPass::run(Function &F, 196 FunctionAnalysisManager &AM) { 197 OS << "PHI Values for function: " << F.getName() << "\n"; 198 PhiValues &PI = AM.getResult<PhiValuesAnalysis>(F); 199 for (const BasicBlock &BB : F) 200 for (const PHINode &PN : BB.phis()) 201 PI.getValuesForPhi(&PN); 202 PI.print(OS); 203 return PreservedAnalyses::all(); 204} 205 206PhiValuesWrapperPass::PhiValuesWrapperPass() : FunctionPass(ID) { 207 initializePhiValuesWrapperPassPass(*PassRegistry::getPassRegistry()); 208} 209 210bool PhiValuesWrapperPass::runOnFunction(Function &F) { 211 Result.reset(new PhiValues(F)); 212 return false; 213} 214 215void PhiValuesWrapperPass::releaseMemory() { 216 Result->releaseMemory(); 217} 218 219void PhiValuesWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 220 AU.setPreservesAll(); 221} 222 223char PhiValuesWrapperPass::ID = 0; 224 225INITIALIZE_PASS(PhiValuesWrapperPass, "phi-values", "Phi Values Analysis", false, 226 true) 227