llvm/llvm/include/llvm/Analysis/DependenceAnalysis.h

//===-- llvm/Analysis/DependenceAnalysis.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
//
//===----------------------------------------------------------------------===//
//
// DependenceAnalysis is an LLVM pass that analyses dependences between memory
// accesses. Currently, it is an implementation of the approach described in
//
//            Practical Dependence Testing
//            Goff, Kennedy, Tseng
//            PLDI 1991
//
// There's a single entry point that analyzes the dependence between a pair
// of memory references in a function, returning either NULL, for no dependence,
// or a more-or-less detailed description of the dependence between them.
//
// This pass exists to support the DependenceGraph pass. There are two separate
// passes because there's a useful separation of concerns. A dependence exists
// if two conditions are met:
//
//    1) Two instructions reference the same memory location, and
//    2) There is a flow of control leading from one instruction to the other.
//
// DependenceAnalysis attacks the first condition; DependenceGraph will attack
// the second (it's not yet ready).
//
// Please note that this is work in progress and the interface is subject to
// change.
//
// Plausible changes:
//    Return a set of more precise dependences instead of just one dependence
//    summarizing all.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_DEPENDENCEANALYSIS_H
#define LLVM_ANALYSIS_DEPENDENCEANALYSIS_H

#include "llvm/ADT/SmallBitVector.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Pass.h"

namespace llvm {
  class AAResults;
  template <typename T> class ArrayRef;
  class Loop;
  class LoopInfo;
  class ScalarEvolution;
  class SCEV;
  class SCEVConstant;
  class raw_ostream;

  /// Dependence - This class represents a dependence between two memory
  /// memory references in a function. It contains minimal information and
  /// is used in the very common situation where the compiler is unable to
  /// determine anything beyond the existence of a dependence; that is, it
  /// represents a confused dependence (see also FullDependence). In most
  /// cases (for output, flow, and anti dependences), the dependence implies
  /// an ordering, where the source must precede the destination; in contrast,
  /// input dependences are unordered.
  ///
  /// When a dependence graph is built, each Dependence will be a member of
  /// the set of predecessor edges for its destination instruction and a set
  /// if successor edges for its source instruction. These sets are represented
  /// as singly-linked lists, with the "next" fields stored in the dependence
  /// itelf.
  class Dependence { … };

  /// FullDependence - This class represents a dependence between two memory
  /// references in a function. It contains detailed information about the
  /// dependence (direction vectors, etc.) and is used when the compiler is
  /// able to accurately analyze the interaction of the references; that is,
  /// it is not a confused dependence (see Dependence). In most cases
  /// (for output, flow, and anti dependences), the dependence implies an
  /// ordering, where the source must precede the destination; in contrast,
  /// input dependences are unordered.
  class FullDependence final : public Dependence { … };

  /// DependenceInfo - This class is the main dependence-analysis driver.
  ///
  class DependenceInfo { … }; // class DependenceInfo

  /// AnalysisPass to compute dependence information in a function
  class DependenceAnalysis : public AnalysisInfoMixin<DependenceAnalysis> { … }; // class DependenceAnalysis

  /// Printer pass to dump DA results.
  struct DependenceAnalysisPrinterPass
      : public PassInfoMixin<DependenceAnalysisPrinterPass> { … }; // class DependenceAnalysisPrinterPass

  /// Legacy pass manager pass to access dependence information
  class DependenceAnalysisWrapperPass : public FunctionPass { … }; // class DependenceAnalysisWrapperPass

  /// createDependenceAnalysisPass - This creates an instance of the
  /// DependenceAnalysis wrapper pass.
  FunctionPass *createDependenceAnalysisWrapperPass();

} // namespace llvm

#endif