File Manager

003 File Manager

Current Path: /usr/src/contrib/llvm-project/llvm/lib/Analysis

usr / src / contrib / llvm-project / llvm / lib / Analysis /

📁 ..
📄 AliasAnalysis.cpp(33.55 KB)
📄 AliasAnalysisEvaluator.cpp(15.64 KB)
📄 AliasAnalysisSummary.cpp(3.49 KB)
📄 AliasAnalysisSummary.h(10.17 KB)
📄 AliasSetTracker.cpp(25.86 KB)
📄 Analysis.cpp(5.29 KB)
📄 AssumeBundleQueries.cpp(7.96 KB)
📄 AssumptionCache.cpp(10.94 KB)
📄 BasicAliasAnalysis.cpp(85.81 KB)
📄 BlockFrequencyInfo.cpp(12.39 KB)
📄 BlockFrequencyInfoImpl.cpp(28.6 KB)
📄 BranchProbabilityInfo.cpp(43.48 KB)
📄 CFG.cpp(9.9 KB)
📄 CFGPrinter.cpp(11.2 KB)
📄 CFLAndersAliasAnalysis.cpp(33.01 KB)
📄 CFLGraph.h(21.23 KB)
📄 CFLSteensAliasAnalysis.cpp(13.24 KB)
📄 CGSCCPassManager.cpp(31.2 KB)
📄 CallGraph.cpp(12.86 KB)
📄 CallGraphSCCPass.cpp(26.31 KB)
📄 CallPrinter.cpp(9.48 KB)
📄 CaptureTracking.cpp(15.38 KB)
📄 CmpInstAnalysis.cpp(4.63 KB)
📄 CodeMetrics.cpp(6.99 KB)
📄 ConstantFolding.cpp(105.15 KB)
📄 CostModel.cpp(3.87 KB)
📄 DDG.cpp(11.29 KB)
📄 Delinearization.cpp(4.49 KB)
📄 DemandedBits.cpp(16.27 KB)
📄 DependenceAnalysis.cpp(150.78 KB)
📄 DependenceGraphBuilder.cpp(19.24 KB)
📄 DivergenceAnalysis.cpp(15.59 KB)
📄 DomPrinter.cpp(9.67 KB)
📄 DomTreeUpdater.cpp(15.21 KB)
📄 DominanceFrontier.cpp(3.2 KB)
📄 EHPersonalities.cpp(5.89 KB)
📄 GlobalsModRef.cpp(41 KB)
📄 GuardUtils.cpp(3.27 KB)
📄 HeatUtils.cpp(2.85 KB)
📄 IVDescriptors.cpp(42.28 KB)
📄 IVUsers.cpp(16.12 KB)
📄 IndirectCallPromotionAnalysis.cpp(4.33 KB)
📄 InlineAdvisor.cpp(15.28 KB)
📄 InlineCost.cpp(99.47 KB)
📄 InlineFeaturesAnalysis.cpp(1.59 KB)
📄 InlineSizeEstimatorAnalysis.cpp(10.95 KB)
📄 InstCount.cpp(2.45 KB)
📄 InstructionPrecedenceTracking.cpp(4.8 KB)
📄 InstructionSimplify.cpp(216.91 KB)
📄 Interval.cpp(1.78 KB)
📄 IntervalPartition.cpp(4.5 KB)
📄 LazyBlockFrequencyInfo.cpp(2.81 KB)
📄 LazyBranchProbabilityInfo.cpp(2.96 KB)
📄 LazyCallGraph.cpp(67.33 KB)
📄 LazyValueInfo.cpp(76.38 KB)
📄 LegacyDivergenceAnalysis.cpp(14.82 KB)
📄 Lint.cpp(29.07 KB)
📄 Loads.cpp(20.6 KB)
📄 LoopAccessAnalysis.cpp(88.02 KB)
📄 LoopAnalysisManager.cpp(6.6 KB)
📄 LoopCacheAnalysis.cpp(23.53 KB)
📄 LoopInfo.cpp(37.15 KB)
📄 LoopNestAnalysis.cpp(10.62 KB)
📄 LoopPass.cpp(12.89 KB)
📄 LoopUnrollAnalyzer.cpp(7.26 KB)
📄 MLInlineAdvisor.cpp(11.36 KB)
📄 MemDepPrinter.cpp(5.13 KB)
📄 MemDerefPrinter.cpp(2.53 KB)
📄 MemoryBuiltins.cpp(41.14 KB)
📄 MemoryDependenceAnalysis.cpp(69.89 KB)
📄 MemoryLocation.cpp(7.92 KB)
📄 MemorySSA.cpp(90.16 KB)
📄 MemorySSAUpdater.cpp(57.9 KB)
📄 ModuleDebugInfoPrinter.cpp(4.02 KB)
📄 ModuleSummaryAnalysis.cpp(38.13 KB)
📄 MustExecute.cpp(31.18 KB)
📄 ObjCARCAliasAnalysis.cpp(5.81 KB)
📄 ObjCARCAnalysisUtils.cpp(1.07 KB)
📄 ObjCARCInstKind.cpp(23.15 KB)
📄 OptimizationRemarkEmitter.cpp(4.23 KB)
📄 PHITransAddr.cpp(16.05 KB)
📄 PhiValues.cpp(8.4 KB)
📄 PostDominators.cpp(3.59 KB)
📄 ProfileSummaryInfo.cpp(18.07 KB)
📄 PtrUseVisitor.cpp(1.28 KB)
📄 RegionInfo.cpp(6.5 KB)
📄 RegionPass.cpp(9.23 KB)
📄 RegionPrinter.cpp(8.61 KB)
📄 ReleaseModeModelRunner.cpp(2.83 KB)
📄 ScalarEvolution.cpp(475.26 KB)
📄 ScalarEvolutionAliasAnalysis.cpp(5.96 KB)
📄 ScalarEvolutionDivision.cpp(7.51 KB)
📄 ScalarEvolutionNormalization.cpp(4.59 KB)
📄 ScopedNoAliasAA.cpp(7.38 KB)
📄 StackLifetime.cpp(12.22 KB)
📄 StackSafetyAnalysis.cpp(31.81 KB)
📄 StratifiedSets.h(18.67 KB)
📄 SyncDependenceAnalysis.cpp(12.97 KB)
📄 SyntheticCountsUtils.cpp(3.81 KB)
📄 TFUtils.cpp(8.99 KB)
📄 TargetLibraryInfo.cpp(58.98 KB)
📄 TargetTransformInfo.cpp(48.15 KB)
📄 Trace.cpp(1.8 KB)
📄 TypeBasedAliasAnalysis.cpp(26.04 KB)
📄 TypeMetadataUtils.cpp(5.93 KB)
📄 VFABIDemangling.cpp(16.46 KB)
📄 ValueLattice.cpp(1.19 KB)
📄 ValueLatticeUtils.cpp(1.53 KB)
📄 ValueTracking.cpp(243.08 KB)
📄 VectorUtils.cpp(48.57 KB)
📁 models

Editing: PhiValues.cpp

//===- PhiValues.cpp - Phi Value Analysis ---------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/PhiValues.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/Instructions.h"
#include "llvm/InitializePasses.h"

using namespace llvm;

void PhiValues::PhiValuesCallbackVH::deleted() {
  PV->invalidateValue(getValPtr());
}

void PhiValues::PhiValuesCallbackVH::allUsesReplacedWith(Value *) {
  // We could potentially update the cached values we have with the new value,
  // but it's simpler to just treat the old value as invalidated.
  PV->invalidateValue(getValPtr());
}

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,
                           SmallVectorImpl<const PHINode *> &Stack) {
  // Initialize the phi with the next depth number.
  assert(DepthMap.lookup(Phi) == 0);
  assert(NextDepthNumber != UINT_MAX);
  unsigned int RootDepthNumber = ++NextDepthNumber;
  DepthMap[Phi] = RootDepthNumber;

// Recursively process the incoming phis of this phi.
  TrackedValues.insert(PhiValuesCallbackVH(const_cast<PHINode *>(Phi), this));
  for (Value *PhiOp : Phi->incoming_values()) {
    if (PHINode *PhiPhiOp = dyn_cast<PHINode>(PhiOp)) {
      // Recurse if the phi has not yet been visited.
      unsigned int OpDepthNumber = DepthMap.lookup(PhiPhiOp);
      if (OpDepthNumber == 0) {
        processPhi(PhiPhiOp, Stack);
        OpDepthNumber = DepthMap.lookup(PhiPhiOp);
        assert(OpDepthNumber != 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(OpDepthNumber))
        DepthMap[Phi] = std::min(DepthMap[Phi], OpDepthNumber);
    } else {
      TrackedValues.insert(PhiValuesCallbackVH(PhiOp, this));
    }
  }

// 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] == RootDepthNumber) {
    // Collect the reachable values for this component. The phis of this
    // component will be those on top of the depth stack with the same or
    // greater depth number.
    ConstValueSet &Reachable = ReachableMap[RootDepthNumber];
    while (true) {
      const PHINode *ComponentPhi = Stack.pop_back_val();
      Reachable.insert(ComponentPhi);

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.
          unsigned int OpDepthNumber = DepthMap[PhiOp];
          if (OpDepthNumber != RootDepthNumber) {
            auto It = ReachableMap.find(OpDepthNumber);
            if (It != ReachableMap.end())
              Reachable.insert(It->second.begin(), It->second.end());
          }
        } else
          Reachable.insert(Op);
      }

if (Stack.empty())
        break;

unsigned int &ComponentDepthNumber = DepthMap[Stack.back()];
      if (ComponentDepthNumber < RootDepthNumber)
        break;

ComponentDepthNumber = RootDepthNumber;
    }

// Filter out phis to get the non-phi reachable values.
    ValueSet &NonPhi = NonPhiReachableMap[RootDepthNumber];
    for (const Value *V : Reachable)
      if (!isa<PHINode>(V))
        NonPhi.insert(const_cast<Value *>(V));
  }
}

const PhiValues::ValueSet &PhiValues::getValuesForPhi(const PHINode *PN) {
  unsigned int DepthNumber = DepthMap.lookup(PN);
  if (DepthNumber == 0) {
    SmallVector<const PHINode *, 8> Stack;
    processPhi(PN, Stack);
    DepthNumber = DepthMap.lookup(PN);
    assert(Stack.empty());
    assert(DepthNumber != 0);
  }
  return NonPhiReachableMap[DepthNumber];
}

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);
  }
  // This value is no longer tracked
  auto It = TrackedValues.find_as(V);
  if (It != TrackedValues.end())
    TrackedValues.erase(It);
}

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)

003 File Manager

Editing: PhiValues.cpp

Upload File

Create Folder