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: AliasSetTracker.h

//===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- 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 two classes: AliasSetTracker and AliasSet. These interfaces
// are used to classify a collection of pointer references into a maximal number
// of disjoint sets. Each AliasSet object constructed by the AliasSetTracker
// object refers to memory disjoint from the other sets.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H
#define LLVM_ANALYSIS_ALIASSETTRACKER_H

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/ilist.h"
#include "llvm/ADT/ilist_node.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/Casting.h"
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <vector>

namespace llvm {

class AliasSetTracker;
class BasicBlock;
class LoadInst;
class Loop;
class MemorySSA;
class AnyMemSetInst;
class AnyMemTransferInst;
class raw_ostream;
class StoreInst;
class VAArgInst;
class Value;

class AliasSet : public ilist_node<AliasSet> {
  friend class AliasSetTracker;

class PointerRec {
    Value *Val;  // The pointer this record corresponds to.
    PointerRec **PrevInList = nullptr;
    PointerRec *NextInList = nullptr;
    AliasSet *AS = nullptr;
    LocationSize Size = LocationSize::mapEmpty();
    AAMDNodes AAInfo;

// Whether the size for this record has been set at all. This makes no
    // guarantees about the size being known.
    bool isSizeSet() const { return Size != LocationSize::mapEmpty(); }

public:
    PointerRec(Value *V)
      : Val(V), AAInfo(DenseMapInfo<AAMDNodes>::getEmptyKey()) {}

Value *getValue() const { return Val; }

PointerRec *getNext() const { return NextInList; }
    bool hasAliasSet() const { return AS != nullptr; }

PointerRec** setPrevInList(PointerRec **PIL) {
      PrevInList = PIL;
      return &NextInList;
    }

bool updateSizeAndAAInfo(LocationSize NewSize, const AAMDNodes &NewAAInfo) {
      bool SizeChanged = false;
      if (NewSize != Size) {
        LocationSize OldSize = Size;
        Size = isSizeSet() ? Size.unionWith(NewSize) : NewSize;
        SizeChanged = OldSize != Size;
      }

if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey())
        // We don't have a AAInfo yet. Set it to NewAAInfo.
        AAInfo = NewAAInfo;
      else {
        AAMDNodes Intersection(AAInfo.intersect(NewAAInfo));
        SizeChanged |= Intersection != AAInfo;
        AAInfo = Intersection;
      }
      return SizeChanged;
    }

LocationSize getSize() const {
      assert(isSizeSet() && "Getting an unset size!");
      return Size;
    }

/// Return the AAInfo, or null if there is no information or conflicting
    /// information.
    AAMDNodes getAAInfo() const {
      // If we have missing or conflicting AAInfo, return null.
      if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey() ||
          AAInfo == DenseMapInfo<AAMDNodes>::getTombstoneKey())
        return AAMDNodes();
      return AAInfo;
    }

AliasSet *getAliasSet(AliasSetTracker &AST) {
      assert(AS && "No AliasSet yet!");
      if (AS->Forward) {
        AliasSet *OldAS = AS;
        AS = OldAS->getForwardedTarget(AST);
        AS->addRef();
        OldAS->dropRef(AST);
      }
      return AS;
    }

void setAliasSet(AliasSet *as) {
      assert(!AS && "Already have an alias set!");
      AS = as;
    }

void eraseFromList() {
      if (NextInList) NextInList->PrevInList = PrevInList;
      *PrevInList = NextInList;
      if (AS->PtrListEnd == &NextInList) {
        AS->PtrListEnd = PrevInList;
        assert(*AS->PtrListEnd == nullptr && "List not terminated right!");
      }
      delete this;
    }
  };

// Doubly linked list of nodes.
  PointerRec *PtrList = nullptr;
  PointerRec **PtrListEnd;
  // Forwarding pointer.
  AliasSet *Forward = nullptr;

/// All instructions without a specific address in this alias set.
  /// In rare cases this vector can have a null'ed out WeakVH
  /// instances (can happen if some other loop pass deletes an
  /// instruction in this list).
  std::vector<WeakVH> UnknownInsts;

/// Number of nodes pointing to this AliasSet plus the number of AliasSets
  /// forwarding to it.
  unsigned RefCount : 27;

// Signifies that this set should be considered to alias any pointer.
  // Use when the tracker holding this set is saturated.
  unsigned AliasAny : 1;

/// The kinds of access this alias set models.
  ///
  /// We keep track of whether this alias set merely refers to the locations of
  /// memory (and not any particular access), whether it modifies or references
  /// the memory, or whether it does both. The lattice goes from "NoAccess" to
  /// either RefAccess or ModAccess, then to ModRefAccess as necessary.
  enum AccessLattice {
    NoAccess = 0,
    RefAccess = 1,
    ModAccess = 2,
    ModRefAccess = RefAccess | ModAccess
  };
  unsigned Access : 2;

/// The kind of alias relationship between pointers of the set.
  ///
  /// These represent conservatively correct alias results between any members
  /// of the set. We represent these independently of the values of alias
  /// results in order to pack it into a single bit. Lattice goes from
  /// MustAlias to MayAlias.
  enum AliasLattice {
    SetMustAlias = 0, SetMayAlias = 1
  };
  unsigned Alias : 1;

unsigned SetSize = 0;

void addRef() { ++RefCount; }

void dropRef(AliasSetTracker &AST) {
    assert(RefCount >= 1 && "Invalid reference count detected!");
    if (--RefCount == 0)
      removeFromTracker(AST);
  }

Instruction *getUnknownInst(unsigned i) const {
    assert(i < UnknownInsts.size());
    return cast_or_null<Instruction>(UnknownInsts[i]);
  }

public:
  AliasSet(const AliasSet &) = delete;
  AliasSet &operator=(const AliasSet &) = delete;

/// Accessors...
  bool isRef() const { return Access & RefAccess; }
  bool isMod() const { return Access & ModAccess; }
  bool isMustAlias() const { return Alias == SetMustAlias; }
  bool isMayAlias()  const { return Alias == SetMayAlias; }

/// Return true if this alias set should be ignored as part of the
  /// AliasSetTracker object.
  bool isForwardingAliasSet() const { return Forward; }

/// Merge the specified alias set into this alias set.
  void mergeSetIn(AliasSet &AS, AliasSetTracker &AST);

// Alias Set iteration - Allow access to all of the pointers which are part of
  // this alias set.
  class iterator;
  iterator begin() const { return iterator(PtrList); }
  iterator end()   const { return iterator(); }
  bool empty() const { return PtrList == nullptr; }

// Unfortunately, ilist::size() is linear, so we have to add code to keep
  // track of the list's exact size.
  unsigned size() { return SetSize; }

/// If this alias set is known to contain a single instruction and *only* a
  /// single unique instruction, return it.  Otherwise, return nullptr.
  Instruction* getUniqueInstruction();

void print(raw_ostream &OS) const;
  void dump() const;

/// Define an iterator for alias sets... this is just a forward iterator.
  class iterator : public std::iterator<std::forward_iterator_tag,
                                        PointerRec, ptrdiff_t> {
    PointerRec *CurNode;

public:
    explicit iterator(PointerRec *CN = nullptr) : CurNode(CN) {}

bool operator==(const iterator& x) const {
      return CurNode == x.CurNode;
    }
    bool operator!=(const iterator& x) const { return !operator==(x); }

value_type &operator*() const {
      assert(CurNode && "Dereferencing AliasSet.end()!");
      return *CurNode;
    }
    value_type *operator->() const { return &operator*(); }

Value *getPointer() const { return CurNode->getValue(); }
    LocationSize getSize() const { return CurNode->getSize(); }
    AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); }

iterator& operator++() {                // Preincrement
      assert(CurNode && "Advancing past AliasSet.end()!");
      CurNode = CurNode->getNext();
      return *this;
    }
    iterator operator++(int) { // Postincrement
      iterator tmp = *this; ++*this; return tmp;
    }
  };

private:
  // Can only be created by AliasSetTracker.
  AliasSet()
      : PtrListEnd(&PtrList), RefCount(0),  AliasAny(false), Access(NoAccess),
        Alias(SetMustAlias) {}

PointerRec *getSomePointer() const {
    return PtrList;
  }

/// Return the real alias set this represents. If this has been merged with
  /// another set and is forwarding, return the ultimate destination set. This
  /// also implements the union-find collapsing as well.
  AliasSet *getForwardedTarget(AliasSetTracker &AST) {
    if (!Forward) return this;

AliasSet *Dest = Forward->getForwardedTarget(AST);
    if (Dest != Forward) {
      Dest->addRef();
      Forward->dropRef(AST);
      Forward = Dest;
    }
    return Dest;
  }

void removeFromTracker(AliasSetTracker &AST);

void addPointer(AliasSetTracker &AST, PointerRec &Entry, LocationSize Size,
                  const AAMDNodes &AAInfo, bool KnownMustAlias = false,
                  bool SkipSizeUpdate = false);
  void addUnknownInst(Instruction *I, AliasAnalysis &AA);

void removeUnknownInst(AliasSetTracker &AST, Instruction *I) {
    bool WasEmpty = UnknownInsts.empty();
    for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i)
      if (UnknownInsts[i] == I) {
        UnknownInsts[i] = UnknownInsts.back();
        UnknownInsts.pop_back();
        --i; --e;  // Revisit the moved entry.
      }
    if (!WasEmpty && UnknownInsts.empty())
      dropRef(AST);
  }

public:
  /// If the specified pointer "may" (or must) alias one of the members in the
  /// set return the appropriate AliasResult. Otherwise return NoAlias.
  AliasResult aliasesPointer(const Value *Ptr, LocationSize Size,
                             const AAMDNodes &AAInfo, AliasAnalysis &AA) const;
  bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const;
};

inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) {
  AS.print(OS);
  return OS;
}

class AliasSetTracker {
  /// A CallbackVH to arrange for AliasSetTracker to be notified whenever a
  /// Value is deleted.
  class ASTCallbackVH final : public CallbackVH {
    AliasSetTracker *AST;

void deleted() override;
    void allUsesReplacedWith(Value *) override;

public:
    ASTCallbackVH(Value *V, AliasSetTracker *AST = nullptr);

ASTCallbackVH &operator=(Value *V);
  };
  /// Traits to tell DenseMap that tell us how to compare and hash the value
  /// handle.
  struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {};

AliasAnalysis &AA;
  MemorySSA *MSSA = nullptr;
  Loop *L = nullptr;
  ilist<AliasSet> AliasSets;

using PointerMapType = DenseMap<ASTCallbackVH, AliasSet::PointerRec *,
                                  ASTCallbackVHDenseMapInfo>;

// Map from pointers to their node
  PointerMapType PointerMap;

public:
  /// Create an empty collection of AliasSets, and use the specified alias
  /// analysis object to disambiguate load and store addresses.
  explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
  explicit AliasSetTracker(AliasAnalysis &aa, MemorySSA *mssa, Loop *l)
      : AA(aa), MSSA(mssa), L(l) {}
  ~AliasSetTracker() { clear(); }

/// These methods are used to add different types of instructions to the alias
  /// sets. Adding a new instruction can result in one of three actions
  /// happening:
  ///
  ///   1. If the instruction doesn't alias any other sets, create a new set.
  ///   2. If the instruction aliases exactly one set, add it to the set
  ///   3. If the instruction aliases multiple sets, merge the sets, and add
  ///      the instruction to the result.
  ///
  /// These methods return true if inserting the instruction resulted in the
  /// addition of a new alias set (i.e., the pointer did not alias anything).
  ///
  void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo); // Add a loc
  void add(LoadInst *LI);
  void add(StoreInst *SI);
  void add(VAArgInst *VAAI);
  void add(AnyMemSetInst *MSI);
  void add(AnyMemTransferInst *MTI);
  void add(Instruction *I);       // Dispatch to one of the other add methods...
  void add(BasicBlock &BB);       // Add all instructions in basic block
  void add(const AliasSetTracker &AST); // Add alias relations from another AST
  void addUnknown(Instruction *I);
  void addAllInstructionsInLoopUsingMSSA();

void clear();

/// Return the alias sets that are active.
  const ilist<AliasSet> &getAliasSets() const { return AliasSets; }

/// Return the alias set which contains the specified memory location.  If
  /// the memory location aliases two or more existing alias sets, will have
  /// the effect of merging those alias sets before the single resulting alias
  /// set is returned.
  AliasSet &getAliasSetFor(const MemoryLocation &MemLoc);

/// Return the underlying alias analysis object used by this tracker.
  AliasAnalysis &getAliasAnalysis() const { return AA; }

/// This method is used to remove a pointer value from the AliasSetTracker
  /// entirely. It should be used when an instruction is deleted from the
  /// program to update the AST. If you don't use this, you would have dangling
  /// pointers to deleted instructions.
  void deleteValue(Value *PtrVal);

/// This method should be used whenever a preexisting value in the program is
  /// copied or cloned, introducing a new value.  Note that it is ok for clients
  /// that use this method to introduce the same value multiple times: if the
  /// tracker already knows about a value, it will ignore the request.
  void copyValue(Value *From, Value *To);

using iterator = ilist<AliasSet>::iterator;
  using const_iterator = ilist<AliasSet>::const_iterator;

const_iterator begin() const { return AliasSets.begin(); }
  const_iterator end()   const { return AliasSets.end(); }

iterator begin() { return AliasSets.begin(); }
  iterator end()   { return AliasSets.end(); }

void print(raw_ostream &OS) const;
  void dump() const;

private:
  friend class AliasSet;

// The total number of pointers contained in all "may" alias sets.
  unsigned TotalMayAliasSetSize = 0;

// A non-null value signifies this AST is saturated. A saturated AST lumps
  // all pointers into a single "May" set.
  AliasSet *AliasAnyAS = nullptr;

void removeAliasSet(AliasSet *AS);

/// Just like operator[] on the map, except that it creates an entry for the
  /// pointer if it doesn't already exist.
  AliasSet::PointerRec &getEntryFor(Value *V) {
    AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)];
    if (!Entry)
      Entry = new AliasSet::PointerRec(V);
    return *Entry;
  }

AliasSet &addPointer(MemoryLocation Loc, AliasSet::AccessLattice E);
  AliasSet *mergeAliasSetsForPointer(const Value *Ptr, LocationSize Size,
                                     const AAMDNodes &AAInfo,
                                     bool &MustAliasAll);

/// Merge all alias sets into a single set that is considered to alias any
  /// pointer.
  AliasSet &mergeAllAliasSets();

AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
};

inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) {
  AST.print(OS);
  return OS;
}

} // end namespace llvm

#endif // LLVM_ANALYSIS_ALIASSETTRACKER_H

003 File Manager

Editing: AliasSetTracker.h

Upload File

Create Folder