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 : // \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_TRANSFORMS_UTILS_MEMORYSSAUPDATER_H
33 : #define LLVM_TRANSFORMS_UTILS_MEMORYSSAUPDATER_H
34 :
35 : #include "llvm/ADT/SmallPtrSet.h"
36 : #include "llvm/ADT/SmallVector.h"
37 : #include "llvm/IR/BasicBlock.h"
38 : #include "llvm/IR/Dominators.h"
39 : #include "llvm/IR/Module.h"
40 : #include "llvm/IR/OperandTraits.h"
41 : #include "llvm/IR/Type.h"
42 : #include "llvm/IR/Use.h"
43 : #include "llvm/IR/User.h"
44 : #include "llvm/IR/Value.h"
45 : #include "llvm/Pass.h"
46 : #include "llvm/Support/Casting.h"
47 : #include "llvm/Support/ErrorHandling.h"
48 : #include "llvm/Transforms/Utils/MemorySSA.h"
49 :
50 : namespace llvm {
51 :
52 : class Function;
53 : class Instruction;
54 : class MemoryAccess;
55 : class LLVMContext;
56 : class raw_ostream;
57 :
58 445551 : class MemorySSAUpdater {
59 : private:
60 : MemorySSA *MSSA;
61 : SmallVector<MemoryPhi *, 8> InsertedPHIs;
62 : SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
63 :
64 : public:
65 445551 : 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_TRANSFORMS_UTILS_MEMORYSSAUPDATER_H
|