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: DDG.cpp

//===- DDG.cpp - Data Dependence Graph -------------------------------------==//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// The implementation for the data dependence graph.
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/DDG.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Support/CommandLine.h"

using namespace llvm;

static cl::opt<bool> SimplifyDDG(
    "ddg-simplify", cl::init(true), cl::Hidden, cl::ZeroOrMore,
    cl::desc(
        "Simplify DDG by merging nodes that have less interesting edges."));

static cl::opt<bool>
    CreatePiBlocks("ddg-pi-blocks", cl::init(true), cl::Hidden, cl::ZeroOrMore,
                   cl::desc("Create pi-block nodes."));

#define DEBUG_TYPE "ddg"

template class llvm::DGEdge<DDGNode, DDGEdge>;
template class llvm::DGNode<DDGNode, DDGEdge>;
template class llvm::DirectedGraph<DDGNode, DDGEdge>;

//===--------------------------------------------------------------------===//
// DDGNode implementation
//===--------------------------------------------------------------------===//
DDGNode::~DDGNode() {}

bool DDGNode::collectInstructions(
    llvm::function_ref<bool(Instruction *)> const &Pred,
    InstructionListType &IList) const {
  assert(IList.empty() && "Expected the IList to be empty on entry.");
  if (isa<SimpleDDGNode>(this)) {
    for (Instruction *I : cast<const SimpleDDGNode>(this)->getInstructions())
      if (Pred(I))
        IList.push_back(I);
  } else if (isa<PiBlockDDGNode>(this)) {
    for (const DDGNode *PN : cast<const PiBlockDDGNode>(this)->getNodes()) {
      assert(!isa<PiBlockDDGNode>(PN) && "Nested PiBlocks are not supported.");
      SmallVector<Instruction *, 8> TmpIList;
      PN->collectInstructions(Pred, TmpIList);
      IList.insert(IList.end(), TmpIList.begin(), TmpIList.end());
    }
  } else
    llvm_unreachable("unimplemented type of node");
  return !IList.empty();
}

raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode::NodeKind K) {
  const char *Out;
  switch (K) {
  case DDGNode::NodeKind::SingleInstruction:
    Out = "single-instruction";
    break;
  case DDGNode::NodeKind::MultiInstruction:
    Out = "multi-instruction";
    break;
  case DDGNode::NodeKind::PiBlock:
    Out = "pi-block";
    break;
  case DDGNode::NodeKind::Root:
    Out = "root";
    break;
  case DDGNode::NodeKind::Unknown:
    Out = "?? (error)";
    break;
  }
  OS << Out;
  return OS;
}

raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode &N) {
  OS << "Node Address:" << &N << ":" << N.getKind() << "\n";
  if (isa<SimpleDDGNode>(N)) {
    OS << " Instructions:\n";
    for (const Instruction *I : cast<const SimpleDDGNode>(N).getInstructions())
      OS.indent(2) << *I << "\n";
  } else if (isa<PiBlockDDGNode>(&N)) {
    OS << "--- start of nodes in pi-block ---\n";
    auto &Nodes = cast<const PiBlockDDGNode>(&N)->getNodes();
    unsigned Count = 0;
    for (const DDGNode *N : Nodes)
      OS << *N << (++Count == Nodes.size() ? "" : "\n");
    OS << "--- end of nodes in pi-block ---\n";
  } else if (!isa<RootDDGNode>(N))
    llvm_unreachable("unimplemented type of node");

OS << (N.getEdges().empty() ? " Edges:none!\n" : " Edges:\n");
  for (auto &E : N.getEdges())
    OS.indent(2) << *E;
  return OS;
}

//===--------------------------------------------------------------------===//
// SimpleDDGNode implementation
//===--------------------------------------------------------------------===//

SimpleDDGNode::SimpleDDGNode(Instruction &I)
  : DDGNode(NodeKind::SingleInstruction), InstList() {
  assert(InstList.empty() && "Expected empty list.");
  InstList.push_back(&I);
}

SimpleDDGNode::SimpleDDGNode(const SimpleDDGNode &N)
    : DDGNode(N), InstList(N.InstList) {
  assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
          (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
         "constructing from invalid simple node.");
}

SimpleDDGNode::SimpleDDGNode(SimpleDDGNode &&N)
    : DDGNode(std::move(N)), InstList(std::move(N.InstList)) {
  assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
          (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
         "constructing from invalid simple node.");
}

SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); }

//===--------------------------------------------------------------------===//
// PiBlockDDGNode implementation
//===--------------------------------------------------------------------===//

PiBlockDDGNode::PiBlockDDGNode(const PiNodeList &List)
    : DDGNode(NodeKind::PiBlock), NodeList(List) {
  assert(!NodeList.empty() && "pi-block node constructed with an empty list.");
}

PiBlockDDGNode::PiBlockDDGNode(const PiBlockDDGNode &N)
    : DDGNode(N), NodeList(N.NodeList) {
  assert(getKind() == NodeKind::PiBlock && !NodeList.empty() &&
         "constructing from invalid pi-block node.");
}

PiBlockDDGNode::PiBlockDDGNode(PiBlockDDGNode &&N)
    : DDGNode(std::move(N)), NodeList(std::move(N.NodeList)) {
  assert(getKind() == NodeKind::PiBlock && !NodeList.empty() &&
         "constructing from invalid pi-block node.");
}

PiBlockDDGNode::~PiBlockDDGNode() { NodeList.clear(); }

//===--------------------------------------------------------------------===//
// DDGEdge implementation
//===--------------------------------------------------------------------===//

raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K) {
  const char *Out;
  switch (K) {
  case DDGEdge::EdgeKind::RegisterDefUse:
    Out = "def-use";
    break;
  case DDGEdge::EdgeKind::MemoryDependence:
    Out = "memory";
    break;
  case DDGEdge::EdgeKind::Rooted:
    Out = "rooted";
    break;
  case DDGEdge::EdgeKind::Unknown:
    Out = "?? (error)";
    break;
  }
  OS << Out;
  return OS;
}

raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge &E) {
  OS << "[" << E.getKind() << "] to " << &E.getTargetNode() << "\n";
  return OS;
}

//===--------------------------------------------------------------------===//
// DataDependenceGraph implementation
//===--------------------------------------------------------------------===//
using BasicBlockListType = SmallVector<BasicBlock *, 8>;

DataDependenceGraph::DataDependenceGraph(Function &F, DependenceInfo &D)
    : DependenceGraphInfo(F.getName().str(), D) {
  // Put the basic blocks in program order for correct dependence
  // directions.
  BasicBlockListType BBList;
  for (auto &SCC : make_range(scc_begin(&F), scc_end(&F)))
    for (BasicBlock * BB : SCC)
      BBList.push_back(BB);
  std::reverse(BBList.begin(), BBList.end());
  DDGBuilder(*this, D, BBList).populate();
}

DataDependenceGraph::DataDependenceGraph(Loop &L, LoopInfo &LI,
                                         DependenceInfo &D)
    : DependenceGraphInfo(Twine(L.getHeader()->getParent()->getName() + "." +
                                L.getHeader()->getName())
                              .str(),
                          D) {
  // Put the basic blocks in program order for correct dependence
  // directions.
  LoopBlocksDFS DFS(&L);
  DFS.perform(&LI);
  BasicBlockListType BBList;
  for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO()))
    BBList.push_back(BB);
  DDGBuilder(*this, D, BBList).populate();
}

DataDependenceGraph::~DataDependenceGraph() {
  for (auto *N : Nodes) {
    for (auto *E : *N)
      delete E;
    delete N;
  }
}

bool DataDependenceGraph::addNode(DDGNode &N) {
  if (!DDGBase::addNode(N))
    return false;

// In general, if the root node is already created and linked, it is not safe
  // to add new nodes since they may be unreachable by the root. However,
  // pi-block nodes need to be added after the root node is linked, and they are
  // always reachable by the root, because they represent components that are
  // already reachable by root.
  auto *Pi = dyn_cast<PiBlockDDGNode>(&N);
  assert((!Root || Pi) &&
         "Root node is already added. No more nodes can be added.");

if (isa<RootDDGNode>(N))
    Root = &N;

if (Pi)
    for (DDGNode *NI : Pi->getNodes())
      PiBlockMap.insert(std::make_pair(NI, Pi));

return true;
}

const PiBlockDDGNode *DataDependenceGraph::getPiBlock(const NodeType &N) const {
  if (PiBlockMap.find(&N) == PiBlockMap.end())
    return nullptr;
  auto *Pi = PiBlockMap.find(&N)->second;
  assert(PiBlockMap.find(Pi) == PiBlockMap.end() &&
         "Nested pi-blocks detected.");
  return Pi;
}

raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) {
  for (DDGNode *Node : G)
    // Avoid printing nodes that are part of a pi-block twice. They will get
    // printed when the pi-block is printed.
    if (!G.getPiBlock(*Node))
      OS << *Node << "\n";
  OS << "\n";
  return OS;
}

//===--------------------------------------------------------------------===//
// DDGBuilder implementation
//===--------------------------------------------------------------------===//

bool DDGBuilder::areNodesMergeable(const DDGNode &Src,
                                   const DDGNode &Tgt) const {
  // Only merge two nodes if they are both simple nodes and the consecutive
  // instructions after merging belong to the same BB.
  const auto *SimpleSrc = dyn_cast<const SimpleDDGNode>(&Src);
  const auto *SimpleTgt = dyn_cast<const SimpleDDGNode>(&Tgt);
  if (!SimpleSrc || !SimpleTgt)
    return false;

return SimpleSrc->getLastInstruction()->getParent() ==
         SimpleTgt->getFirstInstruction()->getParent();
}

void DDGBuilder::mergeNodes(DDGNode &A, DDGNode &B) {
  DDGEdge &EdgeToFold = A.back();
  assert(A.getEdges().size() == 1 && EdgeToFold.getTargetNode() == B &&
         "Expected A to have a single edge to B.");
  assert(isa<SimpleDDGNode>(&A) && isa<SimpleDDGNode>(&B) &&
         "Expected simple nodes");

// Copy instructions from B to the end of A.
  cast<SimpleDDGNode>(&A)->appendInstructions(*cast<SimpleDDGNode>(&B));

// Move to A any outgoing edges from B.
  for (DDGEdge *BE : B)
    Graph.connect(A, BE->getTargetNode(), *BE);

A.removeEdge(EdgeToFold);
  destroyEdge(EdgeToFold);
  Graph.removeNode(B);
  destroyNode(B);
}

bool DDGBuilder::shouldSimplify() const { return SimplifyDDG; }

bool DDGBuilder::shouldCreatePiBlocks() const { return CreatePiBlocks; }

//===--------------------------------------------------------------------===//
// DDG Analysis Passes
//===--------------------------------------------------------------------===//

/// DDG as a loop pass.
DDGAnalysis::Result DDGAnalysis::run(Loop &L, LoopAnalysisManager &AM,
                                     LoopStandardAnalysisResults &AR) {
  Function *F = L.getHeader()->getParent();
  DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
  return std::make_unique<DataDependenceGraph>(L, AR.LI, DI);
}
AnalysisKey DDGAnalysis::Key;

PreservedAnalyses DDGAnalysisPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
                                              LoopStandardAnalysisResults &AR,
                                              LPMUpdater &U) {
  OS << "'DDG' for loop '" << L.getHeader()->getName() << "':\n";
  OS << *AM.getResult<DDGAnalysis>(L, AR);
  return PreservedAnalyses::all();
}

003 File Manager

Editing: DDG.cpp

Upload File

Create Folder