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

//===- MemorySSAUpdater.h - Memory SSA Updater-------------------*- 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
//
//===----------------------------------------------------------------------===//
//
// \file
// An automatic updater for MemorySSA that handles arbitrary insertion,
// deletion, and moves.  It performs phi insertion where necessary, and
// automatically updates the MemorySSA IR to be correct.
// While updating loads or removing instructions is often easy enough to not
// need this, updating stores should generally not be attemped outside this
// API.
//
// Basic API usage:
// Create the memory access you want for the instruction (this is mainly so
// we know where it is, without having to duplicate the entire set of create
// functions MemorySSA supports).
// Call insertDef or insertUse depending on whether it's a MemoryUse or a
// MemoryDef.
// That's it.
//
// For moving, first, move the instruction itself using the normal SSA
// instruction moving API, then just call moveBefore, moveAfter,or moveTo with
// the right arguments.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_MEMORYSSAUPDATER_H
#define LLVM_ANALYSIS_MEMORYSSAUPDATER_H

#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/IR/ValueMap.h"
#include "llvm/Support/CFGDiff.h"
#include <utility>

namespace llvm {

class BasicBlock;
class BranchInst;
class DominatorTree;
class Instruction;
class LoopBlocksRPO;

using ValueToValueMapTy = ValueMap<const Value *, WeakTrackingVH>;
using PhiToDefMap = SmallDenseMap<MemoryPhi *, MemoryAccess *>;
using CFGUpdate = cfg::Update<BasicBlock *>;
using GraphDiffInvBBPair =
    std::pair<const GraphDiff<BasicBlock *> *, Inverse<BasicBlock *>>;

class MemorySSAUpdater {
private:
  MemorySSA *MSSA;

/// We use WeakVH rather than a costly deletion to deal with dangling pointers.
  /// MemoryPhis are created eagerly and sometimes get zapped shortly afterwards.
  SmallVector<WeakVH, 16> InsertedPHIs;

SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
  SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis;

public:
  MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}

/// Insert a definition into the MemorySSA IR.  RenameUses will rename any use
  /// below the new def block (and any inserted phis).  RenameUses should be set
  /// to true if the definition may cause new aliases for loads below it.  This
  /// is not the case for hoisting or sinking or other forms of code *movement*.
  /// It *is* the case for straight code insertion.
  /// For example:
  /// store a
  /// if (foo) { }
  /// load a
  ///
  /// Moving the store into the if block, and calling insertDef, does not
  /// require RenameUses.
  /// However, changing it to:
  /// store a
  /// if (foo) { store b }
  /// load a
  /// Where a mayalias b, *does* require RenameUses be set to true.
  void insertDef(MemoryDef *Def, bool RenameUses = false);
  void insertUse(MemoryUse *Use, bool RenameUses = false);
  /// Update the MemoryPhi in `To` following an edge deletion between `From` and
  /// `To`. If `To` becomes unreachable, a call to removeBlocks should be made.
  void removeEdge(BasicBlock *From, BasicBlock *To);
  /// Update the MemoryPhi in `To` to have a single incoming edge from `From`,
  /// following a CFG change that replaced multiple edges (switch) with a direct
  /// branch.
  void removeDuplicatePhiEdgesBetween(const BasicBlock *From,
                                      const BasicBlock *To);
  /// Update MemorySSA when inserting a unique backedge block for a loop.
  void updatePhisWhenInsertingUniqueBackedgeBlock(BasicBlock *LoopHeader,
                                                  BasicBlock *LoopPreheader,
                                                  BasicBlock *BackedgeBlock);
  /// Update MemorySSA after a loop was cloned, given the blocks in RPO order,
  /// the exit blocks and a 1:1 mapping of all blocks and instructions
  /// cloned. This involves duplicating all defs and uses in the cloned blocks
  /// Updating phi nodes in exit block successors is done separately.
  void updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
                           ArrayRef<BasicBlock *> ExitBlocks,
                           const ValueToValueMapTy &VM,
                           bool IgnoreIncomingWithNoClones = false);
  // Block BB was fully or partially cloned into its predecessor P1. Map
  // contains the 1:1 mapping of instructions cloned and VM[BB]=P1.
  void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1,
                                    const ValueToValueMapTy &VM);
  /// Update phi nodes in exit block successors following cloning. Exit blocks
  /// that were not cloned don't have additional predecessors added.
  void updateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks,
                                     const ValueToValueMapTy &VMap,
                                     DominatorTree &DT);
  void updateExitBlocksForClonedLoop(
      ArrayRef<BasicBlock *> ExitBlocks,
      ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT);

/// Apply CFG updates, analogous with the DT edge updates.
  void applyUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT);
  /// Apply CFG insert updates, analogous with the DT edge updates.
  void applyInsertUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT);

void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
  void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where);
  void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
                   MemorySSA::InsertionPlace Where);
  /// `From` block was spliced into `From` and `To`. There is a CFG edge from
  /// `From` to `To`. Move all accesses from `From` to `To` starting at
  /// instruction `Start`. `To` is newly created BB, so empty of
  /// MemorySSA::MemoryAccesses. Edges are already updated, so successors of
  /// `To` with MPhi nodes need to update incoming block.
  /// |------|        |------|
  /// | From |        | From |
  /// |      |        |------|
  /// |      |           ||
  /// |      |   =>      \/
  /// |      |        |------|  <- Start
  /// |      |        |  To  |
  /// |------|        |------|
  void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To,
                                Instruction *Start);
  /// `From` block was merged into `To`. There is a CFG edge from `To` to
  /// `From`.`To` still branches to `From`, but all instructions were moved and
  /// `From` is now an empty block; `From` is about to be deleted. Move all
  /// accesses from `From` to `To` starting at instruction `Start`. `To` may
  /// have multiple successors, `From` has a single predecessor. `From` may have
  /// successors with MPhi nodes, replace their incoming block with `To`.
  /// |------|        |------|
  /// |  To  |        |  To  |
  /// |------|        |      |
  ///    ||      =>   |      |
  ///    \/           |      |
  /// |------|        |      |  <- Start
  /// | From |        |      |
  /// |------|        |------|
  void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,
                               Instruction *Start);
  /// A new empty BasicBlock (New) now branches directly to Old. Some of
  /// Old's predecessors (Preds) are now branching to New instead of Old.
  /// If New is the only predecessor, move Old's Phi, if present, to New.
  /// Otherwise, add a new Phi in New with appropriate incoming values, and
  /// update the incoming values in Old's Phi node too, if present.
  void wireOldPredecessorsToNewImmediatePredecessor(
      BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds,
      bool IdenticalEdgesWereMerged = true);
  // The below are utility functions. Other than creation of accesses to pass
  // to insertDef, and removeAccess to remove accesses, you should generally
  // not attempt to update memoryssa yourself. It is very non-trivial to get
  // the edge cases right, and the above calls already operate in near-optimal
  // time bounds.

/// Create a MemoryAccess in MemorySSA at a specified point in a block,
  /// with a specified clobbering definition.
  ///
  /// Returns the new MemoryAccess.
  /// This should be called when a memory instruction is created that is being
  /// used to replace an existing memory instruction. It will *not* create PHI
  /// nodes, or verify the clobbering definition. The insertion place is used
  /// solely to determine where in the memoryssa access lists the instruction
  /// will be placed. The caller is expected to keep ordering the same as
  /// instructions.
  /// It will return the new MemoryAccess.
  /// Note: If a MemoryAccess already exists for I, this function will make it
  /// inaccessible and it *must* have removeMemoryAccess called on it.
  MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition,
                                       const BasicBlock *BB,
                                       MemorySSA::InsertionPlace Point);

/// Create a MemoryAccess in MemorySSA before or after an existing
  /// MemoryAccess.
  ///
  /// Returns the new MemoryAccess.
  /// This should be called when a memory instruction is created that is being
  /// used to replace an existing memory instruction. It will *not* create PHI
  /// nodes, or verify the clobbering definition.
  ///
  /// Note: If a MemoryAccess already exists for I, this function will make it
  /// inaccessible and it *must* have removeMemoryAccess called on it.
  MemoryUseOrDef *createMemoryAccessBefore(Instruction *I,
                                           MemoryAccess *Definition,
                                           MemoryUseOrDef *InsertPt);
  MemoryUseOrDef *createMemoryAccessAfter(Instruction *I,
                                          MemoryAccess *Definition,
                                          MemoryAccess *InsertPt);

/// Remove a MemoryAccess from MemorySSA, including updating all
  /// definitions and uses.
  /// This should be called when a memory instruction that has a MemoryAccess
  /// associated with it is erased from the program.  For example, if a store or
  /// load is simply erased (not replaced), removeMemoryAccess should be called
  /// on the MemoryAccess for that store/load.
  void removeMemoryAccess(MemoryAccess *, bool OptimizePhis = false);

/// Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
  /// This should be called when an instruction (load/store) is deleted from
  /// the program.
  void removeMemoryAccess(const Instruction *I, bool OptimizePhis = false) {
    if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
      removeMemoryAccess(MA, OptimizePhis);
  }

/// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
  /// Assumption we make here: all uses of deleted defs and phi must either
  /// occur in blocks about to be deleted (thus will be deleted as well), or
  /// they occur in phis that will simply lose an incoming value.
  /// Deleted blocks still have successor info, but their predecessor edges and
  /// Phi nodes may already be updated. Instructions in DeadBlocks should be
  /// deleted after this call.
  void removeBlocks(const SmallSetVector<BasicBlock *, 8> &DeadBlocks);

/// Instruction I will be changed to an unreachable. Remove all accesses in
  /// I's block that follow I (inclusive), and update the Phis in the blocks'
  /// successors.
  void changeToUnreachable(const Instruction *I);

/// Conditional branch BI is changed or replaced with an unconditional branch
  /// to `To`. Update Phis in BI's successors to remove BI's BB.
  void changeCondBranchToUnconditionalTo(const BranchInst *BI,
                                         const BasicBlock *To);

/// Get handle on MemorySSA.
  MemorySSA* getMemorySSA() const { return MSSA; }

private:
  // Move What before Where in the MemorySSA IR.
  template <class WhereType>
  void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where);
  // Move all memory accesses from `From` to `To` starting at `Start`.
  // Restrictions apply, see public wrappers of this method.
  void moveAllAccesses(BasicBlock *From, BasicBlock *To, Instruction *Start);
  MemoryAccess *getPreviousDef(MemoryAccess *);
  MemoryAccess *getPreviousDefInBlock(MemoryAccess *);
  MemoryAccess *
  getPreviousDefFromEnd(BasicBlock *,
                        DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &);
  MemoryAccess *
  getPreviousDefRecursive(BasicBlock *,
                          DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &);
  MemoryAccess *recursePhi(MemoryAccess *Phi);
  MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi);
  template <class RangeType>
  MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands);
  void tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs);
  void fixupDefs(const SmallVectorImpl<WeakVH> &);
  // Clone all uses and defs from BB to NewBB given a 1:1 map of all
  // instructions and blocks cloned, and a map of MemoryPhi : Definition
  // (MemoryAccess Phi or Def). VMap maps old instructions to cloned
  // instructions and old blocks to cloned blocks. MPhiMap, is created in the
  // caller of this private method, and maps existing MemoryPhis to new
  // definitions that new MemoryAccesses must point to. These definitions may
  // not necessarily be MemoryPhis themselves, they may be MemoryDefs. As such,
  // the map is between MemoryPhis and MemoryAccesses, where the MemoryAccesses
  // may be MemoryPhis or MemoryDefs and not MemoryUses.
  // If CloneWasSimplified = true, the clone was exact. Otherwise, assume that
  // the clone involved simplifications that may have: (1) turned a MemoryUse
  // into an instruction that MemorySSA has no representation for, or (2) turned
  // a MemoryDef into a MemoryUse or an instruction that MemorySSA has no
  // representation for. No other cases are supported.
  void cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
                        const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap,
                        bool CloneWasSimplified = false);
  template <typename Iter>
  void privateUpdateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks,
                                            Iter ValuesBegin, Iter ValuesEnd,
                                            DominatorTree &DT);
  void applyInsertUpdates(ArrayRef<CFGUpdate>, DominatorTree &DT,
                          const GraphDiff<BasicBlock *> *GD);
};
} // end namespace llvm

#endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H

003 File Manager

Editing: MemorySSAUpdater.h

Upload File

Create Folder