• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/MemorySSA.h"
39 #include "llvm/IR/BasicBlock.h"
40 #include "llvm/IR/Dominators.h"
41 #include "llvm/IR/Module.h"
42 #include "llvm/IR/OperandTraits.h"
43 #include "llvm/IR/Type.h"
44 #include "llvm/IR/Use.h"
45 #include "llvm/IR/User.h"
46 #include "llvm/IR/Value.h"
47 #include "llvm/IR/ValueHandle.h"
48 #include "llvm/Pass.h"
49 #include "llvm/Support/Casting.h"
50 #include "llvm/Support/ErrorHandling.h"
51 
52 namespace llvm {
53 
54 class Function;
55 class Instruction;
56 class MemoryAccess;
57 class LLVMContext;
58 class raw_ostream;
59 
60 class MemorySSAUpdater {
61 private:
62   MemorySSA *MSSA;
63 
64   /// We use WeakVH rather than a costly deletion to deal with dangling pointers.
65   /// MemoryPhis are created eagerly and sometimes get zapped shortly afterwards.
66   SmallVector<WeakVH, 16> InsertedPHIs;
67 
68   SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
69   SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis;
70 
71 public:
MemorySSAUpdater(MemorySSA * MSSA)72   MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
73   /// Insert a definition into the MemorySSA IR.  RenameUses will rename any use
74   /// below the new def block (and any inserted phis).  RenameUses should be set
75   /// to true if the definition may cause new aliases for loads below it.  This
76   /// is not the case for hoisting or sinking or other forms of code *movement*.
77   /// It *is* the case for straight code insertion.
78   /// For example:
79   /// store a
80   /// if (foo) { }
81   /// load a
82   ///
83   /// Moving the store into the if block, and calling insertDef, does not
84   /// require RenameUses.
85   /// However, changing it to:
86   /// store a
87   /// if (foo) { store b }
88   /// load a
89   /// Where a mayalias b, *does* require RenameUses be set to true.
90   void insertDef(MemoryDef *Def, bool RenameUses = false);
91   void insertUse(MemoryUse *Use);
92   void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
93   void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where);
94   void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
95                    MemorySSA::InsertionPlace Where);
96   /// `From` block was spliced into `From` and `To`.
97   /// Move all accesses from `From` to `To` starting at instruction `Start`.
98   /// `To` is newly created BB, so empty of MemorySSA::MemoryAccesses.
99   /// Edges are already updated, so successors of `To` with MPhi nodes need to
100   /// update incoming block.
101   /// |------|        |------|
102   /// | From |        | From |
103   /// |      |        |------|
104   /// |      |           ||
105   /// |      |   =>      \/
106   /// |      |        |------|  <- Start
107   /// |      |        |  To  |
108   /// |------|        |------|
109   void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To,
110                                 Instruction *Start);
111   /// `From` block was merged into `To`. All instructions were moved and
112   /// `From` is an empty block with successor edges; `From` is about to be
113   /// deleted. Move all accesses from `From` to `To` starting at instruction
114   /// `Start`. `To` may have multiple successors, `From` has a single
115   /// predecessor. `From` may have successors with MPhi nodes, replace their
116   /// incoming block with `To`.
117   /// |------|        |------|
118   /// |  To  |        |  To  |
119   /// |------|        |      |
120   ///    ||      =>   |      |
121   ///    \/           |      |
122   /// |------|        |      |  <- Start
123   /// | From |        |      |
124   /// |------|        |------|
125   void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,
126                                Instruction *Start);
127   /// BasicBlock Old had New, an empty BasicBlock, added directly before it,
128   /// and the predecessors in Preds that used to point to Old, now point to
129   /// New. If New is the only predecessor, move Old's Phi, if present, to New.
130   /// Otherwise, add a new Phi in New with appropriate incoming values, and
131   /// update the incoming values in Old's Phi node too, if present.
132   void
133   wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New,
134                                                ArrayRef<BasicBlock *> Preds);
135 
136   // The below are utility functions. Other than creation of accesses to pass
137   // to insertDef, and removeAccess to remove accesses, you should generally
138   // not attempt to update memoryssa yourself. It is very non-trivial to get
139   // the edge cases right, and the above calls already operate in near-optimal
140   // time bounds.
141 
142   /// Create a MemoryAccess in MemorySSA at a specified point in a block,
143   /// with a specified clobbering definition.
144   ///
145   /// Returns the new MemoryAccess.
146   /// This should be called when a memory instruction is created that is being
147   /// used to replace an existing memory instruction. It will *not* create PHI
148   /// nodes, or verify the clobbering definition. The insertion place is used
149   /// solely to determine where in the memoryssa access lists the instruction
150   /// will be placed. The caller is expected to keep ordering the same as
151   /// instructions.
152   /// It will return the new MemoryAccess.
153   /// Note: If a MemoryAccess already exists for I, this function will make it
154   /// inaccessible and it *must* have removeMemoryAccess called on it.
155   MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition,
156                                        const BasicBlock *BB,
157                                        MemorySSA::InsertionPlace Point);
158 
159   /// Create a MemoryAccess in MemorySSA before or after an existing
160   /// MemoryAccess.
161   ///
162   /// Returns the new MemoryAccess.
163   /// This should be called when a memory instruction is created that is being
164   /// used to replace an existing memory instruction. It will *not* create PHI
165   /// nodes, or verify the clobbering definition.
166   ///
167   /// Note: If a MemoryAccess already exists for I, this function will make it
168   /// inaccessible and it *must* have removeMemoryAccess called on it.
169   MemoryUseOrDef *createMemoryAccessBefore(Instruction *I,
170                                            MemoryAccess *Definition,
171                                            MemoryUseOrDef *InsertPt);
172   MemoryUseOrDef *createMemoryAccessAfter(Instruction *I,
173                                           MemoryAccess *Definition,
174                                           MemoryAccess *InsertPt);
175 
176   /// Remove a MemoryAccess from MemorySSA, including updating all
177   /// definitions and uses.
178   /// This should be called when a memory instruction that has a MemoryAccess
179   /// associated with it is erased from the program.  For example, if a store or
180   /// load is simply erased (not replaced), removeMemoryAccess should be called
181   /// on the MemoryAccess for that store/load.
182   void removeMemoryAccess(MemoryAccess *);
183 
184   /// Remove MemoryAccess for a given instruction, if a MemoryAccess exists.
185   /// This should be called when an instruction (load/store) is deleted from
186   /// the program.
removeMemoryAccess(const Instruction * I)187   void removeMemoryAccess(const Instruction *I) {
188     if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
189       removeMemoryAccess(MA);
190   }
191 
192   /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
193   /// Assumption we make here: all uses of deleted defs and phi must either
194   /// occur in blocks about to be deleted (thus will be deleted as well), or
195   /// they occur in phis that will simply lose an incoming value.
196   /// Deleted blocks still have successor info, but their predecessor edges and
197   /// Phi nodes may already be updated. Instructions in DeadBlocks should be
198   /// deleted after this call.
199   void removeBlocks(const SmallPtrSetImpl<BasicBlock *> &DeadBlocks);
200 
201   /// Get handle on MemorySSA.
getMemorySSA()202   MemorySSA* getMemorySSA() const { return MSSA; }
203 
204 private:
205   // Move What before Where in the MemorySSA IR.
206   template <class WhereType>
207   void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where);
208   // Move all memory accesses from `From` to `To` starting at `Start`.
209   // Restrictions apply, see public wrappers of this method.
210   void moveAllAccesses(BasicBlock *From, BasicBlock *To, Instruction *Start);
211   MemoryAccess *getPreviousDef(MemoryAccess *);
212   MemoryAccess *getPreviousDefInBlock(MemoryAccess *);
213   MemoryAccess *
214   getPreviousDefFromEnd(BasicBlock *,
215                         DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &);
216   MemoryAccess *
217   getPreviousDefRecursive(BasicBlock *,
218                           DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &);
219   MemoryAccess *recursePhi(MemoryAccess *Phi);
220   template <class RangeType>
221   MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands);
222   void fixupDefs(const SmallVectorImpl<WeakVH> &);
223 };
224 } // end namespace llvm
225 
226 #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H
227