File Manager

003 File Manager

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

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

📁 ..
📄 AliasAnalysis.h(51.98 KB)
📄 AliasAnalysisEvaluator.h(2.7 KB)
📄 AliasSetTracker.h(15.42 KB)
📄 AssumeBundleQueries.h(6.66 KB)
📄 AssumptionCache.h(8.39 KB)
📄 BasicAliasAnalysis.h(10.2 KB)
📄 BlockFrequencyInfo.h(5.59 KB)
📄 BlockFrequencyInfoImpl.h(56.46 KB)
📄 BranchProbabilityInfo.h(10.1 KB)
📄 CFG.h(7.76 KB)
📄 CFGPrinter.h(9.31 KB)
📄 CFLAliasAnalysisUtils.h(1.66 KB)
📄 CFLAndersAliasAnalysis.h(3.97 KB)
📄 CFLSteensAliasAnalysis.h(4.58 KB)
📄 CGSCCPassManager.h(41.2 KB)
📄 CallGraph.h(18.88 KB)
📄 CallGraphSCCPass.h(5.01 KB)
📄 CallPrinter.h(799 B)
📄 CaptureTracking.h(4.78 KB)
📄 CmpInstAnalysis.h(2.57 KB)
📄 CodeMetrics.h(3.15 KB)
📄 ConstantFolding.h(8.01 KB)
📄 DDG.h(19.15 KB)
📄 DOTGraphTraitsPass.h(5.5 KB)
📄 DemandedBits.h(4.07 KB)
📄 DependenceAnalysis.h(41.83 KB)
📄 DependenceGraphBuilder.h(7.74 KB)
📄 DivergenceAnalysis.h(7.38 KB)
📄 DomPrinter.h(1.04 KB)
📄 DomTreeUpdater.h(13.2 KB)
📄 DominanceFrontier.h(6.63 KB)
📄 DominanceFrontierImpl.h(7.12 KB)
📄 EHPersonalities.h(3.22 KB)
📄 GlobalsModRef.h(5.96 KB)
📄 GuardUtils.h(2.11 KB)
📄 HeatUtils.h(1.16 KB)
📄 IVDescriptors.h(14.56 KB)
📄 IVUsers.h(6.07 KB)
📄 IndirectCallPromotionAnalysis.h(2.61 KB)
📄 IndirectCallVisitor.h(1.16 KB)
📄 InlineAdvisor.h(8.71 KB)
📄 InlineCost.h(11.33 KB)
📄 InlineFeaturesAnalysis.h(1.5 KB)
📄 InlineModelFeatureMaps.h(3.41 KB)
📄 InlineSizeEstimatorAnalysis.h(1.07 KB)
📄 InstructionPrecedenceTracking.h(5.9 KB)
📄 InstructionSimplify.h(13.36 KB)
📄 Interval.h(4.84 KB)
📄 IntervalIterator.h(10.64 KB)
📄 IntervalPartition.h(4.05 KB)
📄 IteratedDominanceFrontier.h(2.62 KB)
📄 LazyBlockFrequencyInfo.h(4.34 KB)
📄 LazyBranchProbabilityInfo.h(4.21 KB)
📄 LazyCallGraph.h(50.13 KB)
📄 LazyValueInfo.h(5.4 KB)
📄 LegacyDivergenceAnalysis.h(2.53 KB)
📄 Lint.h(1.35 KB)
📄 Loads.h(7.86 KB)
📄 LoopAccessAnalysis.h(29.75 KB)
📄 LoopAnalysisManager.h(5.83 KB)
📄 LoopCacheAnalysis.h(11.91 KB)
📄 LoopInfo.h(48.27 KB)
📄 LoopInfoImpl.h(27.14 KB)
📄 LoopIterator.h(8.83 KB)
📄 LoopNestAnalysis.h(5.61 KB)
📄 LoopPass.h(4.29 KB)
📄 LoopUnrollAnalyzer.h(3.42 KB)
📄 MLInlineAdvisor.h(3.48 KB)
📄 MLModelRunner.h(1.16 KB)
📄 MemoryBuiltins.h(13.42 KB)
📄 MemoryDependenceAnalysis.h(20.82 KB)
📄 MemoryLocation.h(10.99 KB)
📄 MemorySSA.h(45.92 KB)
📄 MemorySSAUpdater.h(14.55 KB)
📄 ModuleSummaryAnalysis.h(3.44 KB)
📄 MustExecute.h(20.2 KB)
📄 ObjCARCAliasAnalysis.h(3.35 KB)
📄 ObjCARCAnalysisUtils.h(10.22 KB)
📄 ObjCARCInstKind.h(4.87 KB)
📄 OptimizationRemarkEmitter.h(5.93 KB)
📄 PHITransAddr.h(4.77 KB)
📄 Passes.h(3.88 KB)
📄 PhiValues.h(5.25 KB)
📄 PostDominators.h(3.41 KB)
📄 ProfileSummaryInfo.h(9.3 KB)
📄 PtrUseVisitor.h(9.96 KB)
📄 RegionInfo.h(35.23 KB)
📄 RegionInfoImpl.h(25.16 KB)
📄 RegionIterator.h(14.07 KB)
📄 RegionPass.h(4.05 KB)
📄 RegionPrinter.h(2.25 KB)
📄 ScalarEvolution.h(89.21 KB)
📄 ScalarEvolutionAliasAnalysis.h(2.09 KB)
📄 ScalarEvolutionDivision.h(2.48 KB)
📄 ScalarEvolutionExpressions.h(28.61 KB)
📄 ScalarEvolutionNormalization.h(2.47 KB)
📄 ScopedNoAliasAA.h(2.83 KB)
📄 SparsePropagation.h(19.43 KB)
📄 StackLifetime.h(6.16 KB)
📄 StackSafetyAnalysis.h(4.91 KB)
📄 SyncDependenceAnalysis.h(2.85 KB)
📄 SyntheticCountsUtils.h(1.85 KB)
📄 TargetFolder.h(11.04 KB)
📄 TargetLibraryInfo.def(55.35 KB)
📄 TargetLibraryInfo.h(16.86 KB)
📄 TargetTransformInfo.h(96.51 KB)
📄 TargetTransformInfoImpl.h(37.63 KB)
📄 Trace.h(4.1 KB)
📄 TypeBasedAliasAnalysis.h(3.05 KB)
📄 TypeMetadataUtils.h(1.94 KB)
📁 Utils
📄 ValueLattice.h(15.14 KB)
📄 ValueLatticeUtils.h(1.66 KB)
📄 ValueTracking.h(35.82 KB)
📄 VecFuncs.def(10.94 KB)
📄 VectorUtils.h(37.26 KB)

Editing: DependenceGraphBuilder.h

//===- llvm/Analysis/DependenceGraphBuilder.h -------------------*- C++ -*-===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This file defines a builder interface that can be used to populate dependence
// graphs such as DDG and PDG.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H
#define LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/SmallVector.h"

namespace llvm {

class BasicBlock;
class DependenceInfo;
class Instruction;

/// This abstract builder class defines a set of high-level steps for creating
/// DDG-like graphs. The client code is expected to inherit from this class and
/// define concrete implementation for each of the pure virtual functions used
/// in the high-level algorithm.
template <class GraphType> class AbstractDependenceGraphBuilder {
protected:
  using BasicBlockListType = SmallVectorImpl<BasicBlock *>;

private:
  using NodeType = typename GraphType::NodeType;
  using EdgeType = typename GraphType::EdgeType;

public:
  using ClassesType = EquivalenceClasses<BasicBlock *>;
  using NodeListType = SmallVector<NodeType *, 4>;

AbstractDependenceGraphBuilder(GraphType &G, DependenceInfo &D,
                                 const BasicBlockListType &BBs)
      : Graph(G), DI(D), BBList(BBs) {}
  virtual ~AbstractDependenceGraphBuilder() {}

/// The main entry to the graph construction algorithm. It starts by
  /// creating nodes in increasing order of granularity and then
  /// adds def-use and memory edges. As one of the final stages, it
  /// also creates pi-block nodes to facilitate codegen in transformations
  /// that use dependence graphs.
  ///
  /// The algorithmic complexity of this implementation is O(V^2 * I^2), where V
  /// is the number of vertecies (nodes) and I is the number of instructions in
  /// each node. The total number of instructions, N, is equal to V * I,
  /// therefore the worst-case time complexity is O(N^2). The average time
  /// complexity is O((N^2)/2).
  void populate() {
    computeInstructionOrdinals();
    createFineGrainedNodes();
    createDefUseEdges();
    createMemoryDependencyEdges();
    simplify();
    createAndConnectRootNode();
    createPiBlocks();
    sortNodesTopologically();
  }

/// Compute ordinal numbers for each instruction and store them in a map for
  /// future look up. These ordinals are used to compute node ordinals which are
  /// in turn used to order nodes that are part of a cycle.
  /// Instruction ordinals are assigned based on lexical program order.
  void computeInstructionOrdinals();

/// Create fine grained nodes. These are typically atomic nodes that
  /// consist of a single instruction.
  void createFineGrainedNodes();

/// Analyze the def-use chains and create edges from the nodes containing
  /// definitions to the nodes containing the uses.
  void createDefUseEdges();

/// Analyze data dependencies that exist between memory loads or stores,
  /// in the graph nodes and create edges between them.
  void createMemoryDependencyEdges();

/// Create a root node and add edges such that each node in the graph is
  /// reachable from the root.
  void createAndConnectRootNode();

/// Apply graph abstraction to groups of nodes that belong to a strongly
  /// connected component of the graph to create larger compound nodes
  /// called pi-blocks. The purpose of this abstraction is to isolate sets of
  /// program elements that need to stay together during codegen and turn
  /// the dependence graph into an acyclic graph.
  void createPiBlocks();

/// Go through all the nodes in the graph and collapse any two nodes
  /// 'a' and 'b' if all of the following are true:
  ///   - the only edge from 'a' is a def-use edge to 'b' and
  ///   - the only edge to 'b' is a def-use edge from 'a' and
  ///   - there is no cyclic edge from 'b' to 'a' and
  ///   - all instructions in 'a' and 'b' belong to the same basic block and
  ///   - both 'a' and 'b' are simple (single or multi instruction) nodes.
  void simplify();

/// Topologically sort the graph nodes.
  void sortNodesTopologically();

protected:
  /// Create the root node of the graph.
  virtual NodeType &createRootNode() = 0;

/// Create an atomic node in the graph given a single instruction.
  virtual NodeType &createFineGrainedNode(Instruction &I) = 0;

/// Create a pi-block node in the graph representing a group of nodes in an
  /// SCC of the graph.
  virtual NodeType &createPiBlock(const NodeListType &L) = 0;

/// Create a def-use edge going from \p Src to \p Tgt.
  virtual EdgeType &createDefUseEdge(NodeType &Src, NodeType &Tgt) = 0;

/// Create a memory dependence edge going from \p Src to \p Tgt.
  virtual EdgeType &createMemoryEdge(NodeType &Src, NodeType &Tgt) = 0;

/// Create a rooted edge going from \p Src to \p Tgt .
  virtual EdgeType &createRootedEdge(NodeType &Src, NodeType &Tgt) = 0;

/// Given a pi-block node, return a vector of all the nodes contained within
  /// it.
  virtual const NodeListType &getNodesInPiBlock(const NodeType &N) = 0;

/// Deallocate memory of edge \p E.
  virtual void destroyEdge(EdgeType &E) { delete &E; }

/// Deallocate memory of node \p N.
  virtual void destroyNode(NodeType &N) { delete &N; }

/// Return true if creation of pi-blocks are supported and desired,
  /// and false otherwise.
  virtual bool shouldCreatePiBlocks() const { return true; }

/// Return true if graph simplification step is requested, and false
  /// otherwise.
  virtual bool shouldSimplify() const { return true; }

/// Return true if it's safe to merge the two nodes.
  virtual bool areNodesMergeable(const NodeType &A,
                                 const NodeType &B) const = 0;

/// Append the content of node \p B into node \p A and remove \p B and
  /// the edge between \p A and \p B from the graph.
  virtual void mergeNodes(NodeType &A, NodeType &B) = 0;

/// Given an instruction \p I return its associated ordinal number.
  size_t getOrdinal(Instruction &I) {
    assert(InstOrdinalMap.find(&I) != InstOrdinalMap.end() &&
           "No ordinal computed for this instruction.");
    return InstOrdinalMap[&I];
  }

/// Given a node \p N return its associated ordinal number.
  size_t getOrdinal(NodeType &N) {
    assert(NodeOrdinalMap.find(&N) != NodeOrdinalMap.end() &&
           "No ordinal computed for this node.");
    return NodeOrdinalMap[&N];
  }

/// Map types to map instructions to nodes used when populating the graph.
  using InstToNodeMap = DenseMap<Instruction *, NodeType *>;

/// Map Types to map instruction/nodes to an ordinal number.
  using InstToOrdinalMap = DenseMap<Instruction *, size_t>;
  using NodeToOrdinalMap = DenseMap<NodeType *, size_t>;

/// Reference to the graph that gets built by a concrete implementation of
  /// this builder.
  GraphType &Graph;

/// Dependence information used to create memory dependence edges in the
  /// graph.
  DependenceInfo &DI;

/// The list of basic blocks to consider when building the graph.
  const BasicBlockListType &BBList;

/// A mapping from instructions to the corresponding nodes in the graph.
  InstToNodeMap IMap;

/// A mapping from each instruction to an ordinal number. This map is used to
  /// populate the \p NodeOrdinalMap.
  InstToOrdinalMap InstOrdinalMap;

/// A mapping from nodes to an ordinal number. This map is used to sort nodes
  /// in a pi-block based on program order.
  NodeToOrdinalMap NodeOrdinalMap;
};

} // namespace llvm

#endif // LLVM_ANALYSIS_DEPENDENCE_GRAPH_BUILDER_H

003 File Manager

Editing: DependenceGraphBuilder.h

Upload File

Create Folder