LCOV - code coverage report
Current view: top level - include/llvm/Analysis - MemorySSAUpdater.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 5 6 83.3 %
Date: 2018-09-23 13:06:45 Functions: 1 2 50.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- MemorySSAUpdater.h - Memory SSA Updater-------------------*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // \file
      11             : // An automatic updater for MemorySSA that handles arbitrary insertion,
      12             : // deletion, and moves.  It performs phi insertion where necessary, and
      13             : // automatically updates the MemorySSA IR to be correct.
      14             : // While updating loads or removing instructions is often easy enough to not
      15             : // need this, updating stores should generally not be attemped outside this
      16             : // API.
      17             : //
      18             : // Basic API usage:
      19             : // Create the memory access you want for the instruction (this is mainly so
      20             : // we know where it is, without having to duplicate the entire set of create
      21             : // functions MemorySSA supports).
      22             : // Call insertDef or insertUse depending on whether it's a MemoryUse or a
      23             : // MemoryDef.
      24             : // That's it.
      25             : //
      26             : // For moving, first, move the instruction itself using the normal SSA
      27             : // instruction moving API, then just call moveBefore, moveAfter,or moveTo with
      28             : // the right arguments.
      29             : //
      30             : //===----------------------------------------------------------------------===//
      31             : 
      32             : #ifndef LLVM_ANALYSIS_MEMORYSSAUPDATER_H
      33             : #define LLVM_ANALYSIS_MEMORYSSAUPDATER_H
      34             : 
      35             : #include "llvm/ADT/SmallPtrSet.h"
      36             : #include "llvm/ADT/SmallSet.h"
      37             : #include "llvm/ADT/SmallVector.h"
      38             : #include "llvm/Analysis/LoopIterator.h"
      39             : #include "llvm/Analysis/MemorySSA.h"
      40             : #include "llvm/IR/BasicBlock.h"
      41             : #include "llvm/IR/CFGDiff.h"
      42             : #include "llvm/IR/Dominators.h"
      43             : #include "llvm/IR/Module.h"
      44             : #include "llvm/IR/OperandTraits.h"
      45             : #include "llvm/IR/Type.h"
      46             : #include "llvm/IR/Use.h"
      47             : #include "llvm/IR/User.h"
      48             : #include "llvm/IR/Value.h"
      49             : #include "llvm/IR/ValueHandle.h"
      50             : #include "llvm/IR/ValueMap.h"
      51             : #include "llvm/Pass.h"
      52             : #include "llvm/Support/Casting.h"
      53             : #include "llvm/Support/ErrorHandling.h"
      54             : 
      55             : namespace llvm {
      56             : 
      57             : class Function;
      58             : class Instruction;
      59             : class MemoryAccess;
      60             : class LLVMContext;
      61             : class raw_ostream;
      62             : 
      63             : using ValueToValueMapTy = ValueMap<const Value *, WeakTrackingVH>;
      64             : using PhiToDefMap = SmallDenseMap<MemoryPhi *, MemoryAccess *>;
      65             : using CFGUpdate = cfg::Update<BasicBlock *>;
      66             : using GraphDiffInvBBPair =
      67             :     std::pair<const GraphDiff<BasicBlock *> *, Inverse<BasicBlock *>>;
      68             : 
      69             : class MemorySSAUpdater {
      70             : private:
      71             :   MemorySSA *MSSA;
      72             : 
      73             :   /// We use WeakVH rather than a costly deletion to deal with dangling pointers.
      74             :   /// MemoryPhis are created eagerly and sometimes get zapped shortly afterwards.
      75             :   SmallVector<WeakVH, 16> InsertedPHIs;
      76             : 
      77             :   SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
      78             :   SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis;
      79             : 
      80             : public:
      81          25 :   MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
      82             : 
      83             :   /// Insert a definition into the MemorySSA IR.  RenameUses will rename any use
      84             :   /// below the new def block (and any inserted phis).  RenameUses should be set
      85             :   /// to true if the definition may cause new aliases for loads below it.  This
      86             :   /// is not the case for hoisting or sinking or other forms of code *movement*.
      87             :   /// It *is* the case for straight code insertion.
      88             :   /// For example:
      89             :   /// store a
      90             :   /// if (foo) { }
      91             :   /// load a
      92             :   ///
      93             :   /// Moving the store into the if block, and calling insertDef, does not
      94             :   /// require RenameUses.
      95             :   /// However, changing it to:
      96             :   /// store a
      97             :   /// if (foo) { store b }
      98             :   /// load a
      99             :   /// Where a mayalias b, *does* require RenameUses be set to true.
     100             :   void insertDef(MemoryDef *Def, bool RenameUses = false);
     101             :   void insertUse(MemoryUse *Use);
     102             :   /// Update the MemoryPhi in `To` following an edge deletion between `From` and
     103             :   /// `To`. If `To` becomes unreachable, a call to removeBlocks should be made.
     104             :   void removeEdge(BasicBlock *From, BasicBlock *To);
     105             :   /// Update the MemoryPhi in `To` to have a single incoming edge from `From`,
     106             :   /// following a CFG change that replaced multiple edges (switch) with a direct
     107             :   /// branch.
     108             :   void removeDuplicatePhiEdgesBetween(BasicBlock *From, BasicBlock *To);
     109             :   /// Update MemorySSA after a loop was cloned, given the blocks in RPO order,
     110             :   /// the exit blocks and a 1:1 mapping of all blocks and instructions
     111             :   /// cloned. This involves duplicating all defs and uses in the cloned blocks
     112             :   /// Updating phi nodes in exit block successors is done separately.
     113             :   void updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
     114             :                            ArrayRef<BasicBlock *> ExitBlocks,
     115             :                            const ValueToValueMapTy &VM,
     116             :                            bool IgnoreIncomingWithNoClones = false);
     117             :   // Block BB was fully or partially cloned into its predecessor P1. Map
     118             :   // contains the 1:1 mapping of instructions cloned and VM[BB]=P1.
     119             :   void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1,
     120             :                                     const ValueToValueMapTy &VM);
     121             :   /// Update phi nodes in exit block successors following cloning. Exit blocks
     122             :   /// that were not cloned don't have additional predecessors added.
     123             :   void updateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks,
     124             :                                      const ValueToValueMapTy &VMap,
     125             :                                      DominatorTree &DT);
     126             :   void updateExitBlocksForClonedLoop(
     127             :       ArrayRef<BasicBlock *> ExitBlocks,
     128             :       ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT);
     129             : 
     130             :   /// Apply CFG updates, analogous with the DT edge updates.
     131             :   void applyUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT);
     132             :   /// Apply CFG insert updates, analogous with the DT edge updates.
     133             :   void applyInsertUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT);
     134             : 
     135             :   void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
     136             :   void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where);
     137             :   void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
     138             :                    MemorySSA::InsertionPlace Where);
     139             :   /// `From` block was spliced into `From` and `To`. There is a CFG edge from
     140             :   /// `From` to `To`. Move all accesses from `From` to `To` starting at
     141             :   /// instruction `Start`. `To` is newly created BB, so empty of
     142             :   /// MemorySSA::MemoryAccesses. Edges are already updated, so successors of
     143             :   /// `To` with MPhi nodes need to update incoming block.
     144             :   /// |------|        |------|
     145             :   /// | From |        | From |
     146             :   /// |      |        |------|
     147             :   /// |      |           ||
     148             :   /// |      |   =>      \/
     149             :   /// |      |        |------|  <- Start
     150             :   /// |      |        |  To  |
     151             :   /// |------|        |------|
     152             :   void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To,
     153             :                                 Instruction *Start);
     154             :   /// `From` block was merged into `To`. There is a CFG edge from `To` to
     155             :   /// `From`.`To` still branches to `From`, but all instructions were moved and
     156             :   /// `From` is now an empty block; `From` is about to be deleted. Move all
     157             :   /// accesses from `From` to `To` starting at instruction `Start`. `To` may
     158             :   /// have multiple successors, `From` has a single predecessor. `From` may have
     159             :   /// successors with MPhi nodes, replace their incoming block with `To`.
     160             :   /// |------|        |------|
     161             :   /// |  To  |        |  To  |
     162             :   /// |------|        |      |
     163             :   ///    ||      =>   |      |
     164             :   ///    \/           |      |
     165             :   /// |------|        |      |  <- Start
     166             :   /// | From |        |      |
     167             :   /// |------|        |------|
     168             :   void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,
     169             :                                Instruction *Start);
     170             :   /// A new empty BasicBlock (New) now branches directly to Old. Some of
     171             :   /// Old's predecessors (Preds) are now branching to New instead of Old.
     172             :   /// If New is the only predecessor, move Old's Phi, if present, to New.
     173             :   /// Otherwise, add a new Phi in New with appropriate incoming values, and
     174             :   /// update the incoming values in Old's Phi node too, if present.
     175             :   void wireOldPredecessorsToNewImmediatePredecessor(
     176             :       BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds,
     177             :       bool IdenticalEdgesWereMerged = true);
     178             :   // The below are utility functions. Other than creation of accesses to pass
     179             :   // to insertDef, and removeAccess to remove accesses, you should generally
     180             :   // not attempt to update memoryssa yourself. It is very non-trivial to get
     181             :   // the edge cases right, and the above calls already operate in near-optimal
     182             :   // time bounds.
     183             : 
     184             :   /// Create a MemoryAccess in MemorySSA at a specified point in a block,
     185             :   /// with a specified clobbering definition.
     186             :   ///
     187             :   /// Returns the new MemoryAccess.
     188             :   /// This should be called when a memory instruction is created that is being
     189             :   /// used to replace an existing memory instruction. It will *not* create PHI
     190             :   /// nodes, or verify the clobbering definition. The insertion place is used
     191             :   /// solely to determine where in the memoryssa access lists the instruction
     192             :   /// will be placed. The caller is expected to keep ordering the same as
     193             :   /// instructions.
     194             :   /// It will return the new MemoryAccess.
     195             :   /// Note: If a MemoryAccess already exists for I, this function will make it
     196             :   /// inaccessible and it *must* have removeMemoryAccess called on it.
     197             :   MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition,
     198             :                                        const BasicBlock *BB,
     199             :                                        MemorySSA::InsertionPlace Point);
     200             : 
     201             :   /// Create a MemoryAccess in MemorySSA before or after an existing
     202             :   /// MemoryAccess.
     203             :   ///
     204             :   /// Returns the new MemoryAccess.
     205             :   /// This should be called when a memory instruction is created that is being
     206             :   /// used to replace an existing memory instruction. It will *not* create PHI
     207             :   /// nodes, or verify the clobbering definition.
     208             :   ///
     209             :   /// Note: If a MemoryAccess already exists for I, this function will make it
     210             :   /// inaccessible and it *must* have removeMemoryAccess called on it.
     211             :   MemoryUseOrDef *createMemoryAccessBefore(Instruction *I,
     212             :                                            MemoryAccess *Definition,
     213             :                                            MemoryUseOrDef *InsertPt);
     214             :   MemoryUseOrDef *createMemoryAccessAfter(Instruction *I,
     215             :                                           MemoryAccess *Definition,
     216             :                                           MemoryAccess *InsertPt);
     217             : 
     218             :   /// Remove a MemoryAccess from MemorySSA, including updating all
     219             :   /// definitions and uses.
     220             :   /// This should be called when a memory instruction that has a MemoryAccess
     221             :   /// associated with it is erased from the program.  For example, if a store or
     222             :   /// load is simply erased (not replaced), removeMemoryAccess should be called
     223             :   /// on the MemoryAccess for that store/load.
     224             :   void removeMemoryAccess(MemoryAccess *);
     225             : 
     226             :   /// Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
     227             :   /// This should be called when an instruction (load/store) is deleted from
     228             :   /// the program.
     229          27 :   void removeMemoryAccess(const Instruction *I) {
     230          27 :     if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
     231           6 :       removeMemoryAccess(MA);
     232          27 :   }
     233             : 
     234             :   /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
     235             :   /// Assumption we make here: all uses of deleted defs and phi must either
     236             :   /// occur in blocks about to be deleted (thus will be deleted as well), or
     237             :   /// they occur in phis that will simply lose an incoming value.
     238             :   /// Deleted blocks still have successor info, but their predecessor edges and
     239             :   /// Phi nodes may already be updated. Instructions in DeadBlocks should be
     240             :   /// deleted after this call.
     241             :   void removeBlocks(const SmallPtrSetImpl<BasicBlock *> &DeadBlocks);
     242             : 
     243             :   /// Get handle on MemorySSA.
     244           0 :   MemorySSA* getMemorySSA() const { return MSSA; }
     245             : 
     246             : private:
     247             :   // Move What before Where in the MemorySSA IR.
     248             :   template <class WhereType>
     249             :   void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where);
     250             :   // Move all memory accesses from `From` to `To` starting at `Start`.
     251             :   // Restrictions apply, see public wrappers of this method.
     252             :   void moveAllAccesses(BasicBlock *From, BasicBlock *To, Instruction *Start);
     253             :   MemoryAccess *getPreviousDef(MemoryAccess *);
     254             :   MemoryAccess *getPreviousDefInBlock(MemoryAccess *);
     255             :   MemoryAccess *
     256             :   getPreviousDefFromEnd(BasicBlock *,
     257             :                         DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &);
     258             :   MemoryAccess *
     259             :   getPreviousDefRecursive(BasicBlock *,
     260             :                           DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &);
     261             :   MemoryAccess *recursePhi(MemoryAccess *Phi);
     262             :   template <class RangeType>
     263             :   MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands);
     264             :   void fixupDefs(const SmallVectorImpl<WeakVH> &);
     265             :   // Clone all uses and defs from BB to NewBB given a 1:1 map of all
     266             :   // instructions and blocks cloned, and a map of MemoryPhi : Definition
     267             :   // (MemoryAccess Phi or Def). VMap maps old instructions to cloned
     268             :   // instructions and old blocks to cloned blocks. MPhiMap, is created in the
     269             :   // caller of this private method, and maps existing MemoryPhis to new
     270             :   // definitions that new MemoryAccesses must point to. These definitions may
     271             :   // not necessarily be MemoryPhis themselves, they may be MemoryDefs. As such,
     272             :   // the map is between MemoryPhis and MemoryAccesses, where the MemoryAccesses
     273             :   // may be MemoryPhis or MemoryDefs and not MemoryUses.
     274             :   void cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
     275             :                         const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap);
     276             :   template <typename Iter>
     277             :   void privateUpdateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks,
     278             :                                             Iter ValuesBegin, Iter ValuesEnd,
     279             :                                             DominatorTree &DT);
     280             :   void applyInsertUpdates(ArrayRef<CFGUpdate>, DominatorTree &DT,
     281             :                           const GraphDiff<BasicBlock *> *GD);
     282             : };
     283             : } // end namespace llvm
     284             : 
     285             : #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H

Generated by: LCOV version 1.13