227 lines · cpp
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-exception6//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 so35// is necessary anyway in order to get the values for this phi. We do this using36// Tarjan's algorithm with Nuutila's improvements to find the strongly connected37// components of the phi graph rooted in this phi:38// * All phis in a strongly connected component will have the same reachable39// non-phi values. The SCC may not be the maximal subgraph for that set of40// reachable values, but finding out that isn't really necessary (it would41// only reduce the amount of memory needed to store the values).42// * Tarjan's algorithm completes components in a bottom-up manner, i.e. it43// never completes a component before the components reachable from it have44// been completed. This means that when we complete a component we have45// 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 what47// 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 that69 // phi are part of the same component, so adjust the depth number.70 if (!ReachableMap.count(OpDepthNumber)) {71 unsigned &Depth = DepthMap[Phi];72 Depth = std::min(Depth, OpDepthNumber);73 }74 } else {75 TrackedValues.insert(PhiValuesCallbackVH(PhiOp, this));76 }77 }78 79 // Now that incoming phis have been handled, push this phi to the stack.80 Stack.push_back(Phi);81 82 // If the depth number has not changed then we've finished collecting the phis83 // of a strongly connected component.84 if (DepthMap[Phi] == RootDepthNumber) {85 // Collect the reachable values for this component. The phis of this86 // component will be those on top of the depth stack with the same or87 // greater depth number.88 ConstValueSet &Reachable = ReachableMap[RootDepthNumber];89 while (true) {90 const PHINode *ComponentPhi = Stack.pop_back_val();91 Reachable.insert(ComponentPhi);92 93 for (Value *Op : ComponentPhi->incoming_values()) {94 if (PHINode *PhiOp = dyn_cast<PHINode>(Op)) {95 // If this phi is not part of the same component then that component96 // is guaranteed to have been completed before this one. Therefore we97 // can just add its reachable values to the reachable values of this98 // component.99 unsigned int OpDepthNumber = DepthMap[PhiOp];100 if (OpDepthNumber != RootDepthNumber) {101 auto It = ReachableMap.find(OpDepthNumber);102 if (It != ReachableMap.end())103 Reachable.insert_range(It->second);104 }105 } else106 Reachable.insert(Op);107 }108 109 if (Stack.empty())110 break;111 112 unsigned int &ComponentDepthNumber = DepthMap[Stack.back()];113 if (ComponentDepthNumber < RootDepthNumber)114 break;115 116 ComponentDepthNumber = RootDepthNumber;117 }118 119 // Filter out phis to get the non-phi reachable values.120 ValueSet &NonPhi = NonPhiReachableMap[RootDepthNumber];121 for (const Value *V : Reachable)122 if (!isa<PHINode>(V))123 NonPhi.insert(const_cast<Value *>(V));124 }125}126 127const PhiValues::ValueSet &PhiValues::getValuesForPhi(const PHINode *PN) {128 unsigned int DepthNumber = DepthMap.lookup(PN);129 if (DepthNumber == 0) {130 SmallVector<const PHINode *, 8> Stack;131 processPhi(PN, Stack);132 DepthNumber = DepthMap.lookup(PN);133 assert(Stack.empty());134 assert(DepthNumber != 0);135 }136 return NonPhiReachableMap[DepthNumber];137}138 139void PhiValues::invalidateValue(const Value *V) {140 // Components that can reach V are invalid.141 SmallVector<unsigned int, 8> InvalidComponents;142 for (auto &Pair : ReachableMap)143 if (Pair.second.count(V))144 InvalidComponents.push_back(Pair.first);145 146 for (unsigned int N : InvalidComponents) {147 for (const Value *V : ReachableMap[N])148 if (const PHINode *PN = dyn_cast<PHINode>(V))149 DepthMap.erase(PN);150 NonPhiReachableMap.erase(N);151 ReachableMap.erase(N);152 }153 // This value is no longer tracked154 auto It = TrackedValues.find_as(V);155 if (It != TrackedValues.end())156 TrackedValues.erase(It);157}158 159void PhiValues::releaseMemory() {160 DepthMap.clear();161 NonPhiReachableMap.clear();162 ReachableMap.clear();163}164 165void PhiValues::print(raw_ostream &OS) const {166 // Iterate through the phi nodes of the function rather than iterating through167 // DepthMap in order to get predictable ordering.168 for (const BasicBlock &BB : F) {169 for (const PHINode &PN : BB.phis()) {170 OS << "PHI ";171 PN.printAsOperand(OS, false);172 OS << " has values:\n";173 unsigned int N = DepthMap.lookup(&PN);174 auto It = NonPhiReachableMap.find(N);175 if (It == NonPhiReachableMap.end())176 OS << " UNKNOWN\n";177 else if (It->second.empty())178 OS << " NONE\n";179 else180 for (Value *V : It->second)181 // Printing of an instruction prints two spaces at the start, so182 // handle instructions and everything else slightly differently in183 // order to get consistent indenting.184 if (Instruction *I = dyn_cast<Instruction>(V))185 OS << *I << "\n";186 else187 OS << " " << *V << "\n";188 }189 }190}191 192AnalysisKey PhiValuesAnalysis::Key;193PhiValues PhiValuesAnalysis::run(Function &F, FunctionAnalysisManager &) {194 return PhiValues(F);195}196 197PreservedAnalyses PhiValuesPrinterPass::run(Function &F,198 FunctionAnalysisManager &AM) {199 OS << "PHI Values for function: " << F.getName() << "\n";200 PhiValues &PI = AM.getResult<PhiValuesAnalysis>(F);201 for (const BasicBlock &BB : F)202 for (const PHINode &PN : BB.phis())203 PI.getValuesForPhi(&PN);204 PI.print(OS);205 return PreservedAnalyses::all();206}207 208PhiValuesWrapperPass::PhiValuesWrapperPass() : FunctionPass(ID) {}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