contrib/llvm/include/llvm/Analysis/MemorySSAUpdater.h

   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 // \brief 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/SmallVector.h"
  37 #include "llvm/Analysis/MemorySSA.h"
  38 #include "llvm/IR/BasicBlock.h"
  39 #include "llvm/IR/Dominators.h"
  40 #include "llvm/IR/Module.h"
  41 #include "llvm/IR/OperandTraits.h"
  42 #include "llvm/IR/Type.h"
  43 #include "llvm/IR/Use.h"
  44 #include "llvm/IR/User.h"
  45 #include "llvm/IR/Value.h"
  46 #include "llvm/Pass.h"
  47 #include "llvm/Support/Casting.h"
  48 #include "llvm/Support/ErrorHandling.h"
  49
  50 namespace llvm {
  51
  52 class Function;
  53 class Instruction;
  54 class MemoryAccess;
  55 class LLVMContext;
  56 class raw_ostream;
  57
  58 class MemorySSAUpdater {
  59 private:
  60   MemorySSA *MSSA;
  61   SmallVector<MemoryPhi *, 8> InsertedPHIs;
  62   SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
  63
  64 public:
  65   MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
  66   /// Insert a definition into the MemorySSA IR.  RenameUses will rename any use
  67   /// below the new def block (and any inserted phis).  RenameUses should be set
  68   /// to true if the definition may cause new aliases for loads below it.  This
  69   /// is not the case for hoisting or sinking or other forms of code *movement*.
  70   /// It *is* the case for straight code insertion.
  71   /// For example:
  72   /// store a
  73   /// if (foo) { }
  74   /// load a
  75   ///
  76   /// Moving the store into the if block, and calling insertDef, does not
  77   /// require RenameUses.
  78   /// However, changing it to:
  79   /// store a
  80   /// if (foo) { store b }
  81   /// load a
  82   /// Where a mayalias b, *does* require RenameUses be set to true.
  83   void insertDef(MemoryDef *Def, bool RenameUses = false);
  84   void insertUse(MemoryUse *Use);
  85   void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
  86   void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where);
  87   void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
  88                    MemorySSA::InsertionPlace Where);
  89
  90   // The below are utility functions. Other than creation of accesses to pass
  91   // to insertDef, and removeAccess to remove accesses, you should generally
  92   // not attempt to update memoryssa yourself. It is very non-trivial to get
  93   // the edge cases right, and the above calls already operate in near-optimal
  94   // time bounds.
  95
  96   /// \brief Create a MemoryAccess in MemorySSA at a specified point in a block,
  97   /// with a specified clobbering definition.
  98   ///
  99   /// Returns the new MemoryAccess.
 100   /// This should be called when a memory instruction is created that is being
 101   /// used to replace an existing memory instruction. It will *not* create PHI
 102   /// nodes, or verify the clobbering definition. The insertion place is used
 103   /// solely to determine where in the memoryssa access lists the instruction
 104   /// will be placed. The caller is expected to keep ordering the same as
 105   /// instructions.
 106   /// It will return the new MemoryAccess.
 107   /// Note: If a MemoryAccess already exists for I, this function will make it
 108   /// inaccessible and it *must* have removeMemoryAccess called on it.
 109   MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition,
 110                                        const BasicBlock *BB,
 111                                        MemorySSA::InsertionPlace Point);
 112
 113   /// \brief Create a MemoryAccess in MemorySSA before or after an existing
 114   /// MemoryAccess.
 115   ///
 116   /// Returns the new MemoryAccess.
 117   /// This should be called when a memory instruction is created that is being
 118   /// used to replace an existing memory instruction. It will *not* create PHI
 119   /// nodes, or verify the clobbering definition.
 120   ///
 121   /// Note: If a MemoryAccess already exists for I, this function will make it
 122   /// inaccessible and it *must* have removeMemoryAccess called on it.
 123   MemoryUseOrDef *createMemoryAccessBefore(Instruction *I,
 124                                            MemoryAccess *Definition,
 125                                            MemoryUseOrDef *InsertPt);
 126   MemoryUseOrDef *createMemoryAccessAfter(Instruction *I,
 127                                           MemoryAccess *Definition,
 128                                           MemoryAccess *InsertPt);
 129
 130   /// \brief Remove a MemoryAccess from MemorySSA, including updating all
 131   /// definitions and uses.
 132   /// This should be called when a memory instruction that has a MemoryAccess
 133   /// associated with it is erased from the program.  For example, if a store or
 134   /// load is simply erased (not replaced), removeMemoryAccess should be called
 135   /// on the MemoryAccess for that store/load.
 136   void removeMemoryAccess(MemoryAccess *);
 137
 138 private:
 139   // Move What before Where in the MemorySSA IR.
 140   template <class WhereType>
 141   void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where);
 142   MemoryAccess *getPreviousDef(MemoryAccess *);
 143   MemoryAccess *getPreviousDefInBlock(MemoryAccess *);
 144   MemoryAccess *getPreviousDefFromEnd(BasicBlock *);
 145   MemoryAccess *getPreviousDefRecursive(BasicBlock *);
 146   MemoryAccess *recursePhi(MemoryAccess *Phi);
 147   template <class RangeType>
 148   MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands);
 149   void fixupDefs(const SmallVectorImpl<MemoryAccess *> &);
 150 };
 151 } // end namespace llvm
 152
 153 #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H