10b57cec5SDimitry Andric //===- MemorySSAUpdater.h - Memory SSA Updater-------------------*- C++ -*-===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 90b57cec5SDimitry Andric // \file 100b57cec5SDimitry Andric // An automatic updater for MemorySSA that handles arbitrary insertion, 110b57cec5SDimitry Andric // deletion, and moves. It performs phi insertion where necessary, and 120b57cec5SDimitry Andric // automatically updates the MemorySSA IR to be correct. 130b57cec5SDimitry Andric // While updating loads or removing instructions is often easy enough to not 140b57cec5SDimitry Andric // need this, updating stores should generally not be attemped outside this 150b57cec5SDimitry Andric // API. 160b57cec5SDimitry Andric // 170b57cec5SDimitry Andric // Basic API usage: 180b57cec5SDimitry Andric // Create the memory access you want for the instruction (this is mainly so 190b57cec5SDimitry Andric // we know where it is, without having to duplicate the entire set of create 200b57cec5SDimitry Andric // functions MemorySSA supports). 210b57cec5SDimitry Andric // Call insertDef or insertUse depending on whether it's a MemoryUse or a 220b57cec5SDimitry Andric // MemoryDef. 230b57cec5SDimitry Andric // That's it. 240b57cec5SDimitry Andric // 250b57cec5SDimitry Andric // For moving, first, move the instruction itself using the normal SSA 260b57cec5SDimitry Andric // instruction moving API, then just call moveBefore, moveAfter,or moveTo with 270b57cec5SDimitry Andric // the right arguments. 280b57cec5SDimitry Andric // 290b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 300b57cec5SDimitry Andric 310b57cec5SDimitry Andric #ifndef LLVM_ANALYSIS_MEMORYSSAUPDATER_H 320b57cec5SDimitry Andric #define LLVM_ANALYSIS_MEMORYSSAUPDATER_H 330b57cec5SDimitry Andric 340b57cec5SDimitry Andric #include "llvm/ADT/SmallPtrSet.h" 350b57cec5SDimitry Andric #include "llvm/ADT/SmallSet.h" 360b57cec5SDimitry Andric #include "llvm/ADT/SmallVector.h" 370b57cec5SDimitry Andric #include "llvm/Analysis/MemorySSA.h" 380b57cec5SDimitry Andric #include "llvm/IR/ValueHandle.h" 390b57cec5SDimitry Andric #include "llvm/IR/ValueMap.h" 405ffd83dbSDimitry Andric #include "llvm/Support/CFGDiff.h" 410b57cec5SDimitry Andric 420b57cec5SDimitry Andric namespace llvm { 430b57cec5SDimitry Andric 445ffd83dbSDimitry Andric class BasicBlock; 455ffd83dbSDimitry Andric class DominatorTree; 460b57cec5SDimitry Andric class Instruction; 475ffd83dbSDimitry Andric class LoopBlocksRPO; 4881ad6265SDimitry Andric template <typename T, unsigned int N> class SmallSetVector; 490b57cec5SDimitry Andric 500b57cec5SDimitry Andric using ValueToValueMapTy = ValueMap<const Value *, WeakTrackingVH>; 510b57cec5SDimitry Andric using PhiToDefMap = SmallDenseMap<MemoryPhi *, MemoryAccess *>; 520b57cec5SDimitry Andric using CFGUpdate = cfg::Update<BasicBlock *>; 530b57cec5SDimitry Andric 540b57cec5SDimitry Andric class MemorySSAUpdater { 550b57cec5SDimitry Andric private: 560b57cec5SDimitry Andric MemorySSA *MSSA; 570b57cec5SDimitry Andric 580b57cec5SDimitry Andric /// We use WeakVH rather than a costly deletion to deal with dangling pointers. 590b57cec5SDimitry Andric /// MemoryPhis are created eagerly and sometimes get zapped shortly afterwards. 600b57cec5SDimitry Andric SmallVector<WeakVH, 16> InsertedPHIs; 610b57cec5SDimitry Andric 620b57cec5SDimitry Andric SmallPtrSet<BasicBlock *, 8> VisitedBlocks; 630b57cec5SDimitry Andric SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis; 640b57cec5SDimitry Andric 650b57cec5SDimitry Andric public: MemorySSAUpdater(MemorySSA * MSSA)660b57cec5SDimitry Andric MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {} 670b57cec5SDimitry Andric 680b57cec5SDimitry Andric /// Insert a definition into the MemorySSA IR. RenameUses will rename any use 690b57cec5SDimitry Andric /// below the new def block (and any inserted phis). RenameUses should be set 700b57cec5SDimitry Andric /// to true if the definition may cause new aliases for loads below it. This 710b57cec5SDimitry Andric /// is not the case for hoisting or sinking or other forms of code *movement*. 720b57cec5SDimitry Andric /// It *is* the case for straight code insertion. 730b57cec5SDimitry Andric /// For example: 740b57cec5SDimitry Andric /// store a 750b57cec5SDimitry Andric /// if (foo) { } 760b57cec5SDimitry Andric /// load a 770b57cec5SDimitry Andric /// 780b57cec5SDimitry Andric /// Moving the store into the if block, and calling insertDef, does not 790b57cec5SDimitry Andric /// require RenameUses. 800b57cec5SDimitry Andric /// However, changing it to: 810b57cec5SDimitry Andric /// store a 820b57cec5SDimitry Andric /// if (foo) { store b } 830b57cec5SDimitry Andric /// load a 840b57cec5SDimitry Andric /// Where a mayalias b, *does* require RenameUses be set to true. 850b57cec5SDimitry Andric void insertDef(MemoryDef *Def, bool RenameUses = false); 868bcb0991SDimitry Andric void insertUse(MemoryUse *Use, bool RenameUses = false); 870b57cec5SDimitry Andric /// Update the MemoryPhi in `To` following an edge deletion between `From` and 880b57cec5SDimitry Andric /// `To`. If `To` becomes unreachable, a call to removeBlocks should be made. 890b57cec5SDimitry Andric void removeEdge(BasicBlock *From, BasicBlock *To); 900b57cec5SDimitry Andric /// Update the MemoryPhi in `To` to have a single incoming edge from `From`, 910b57cec5SDimitry Andric /// following a CFG change that replaced multiple edges (switch) with a direct 920b57cec5SDimitry Andric /// branch. 930b57cec5SDimitry Andric void removeDuplicatePhiEdgesBetween(const BasicBlock *From, 940b57cec5SDimitry Andric const BasicBlock *To); 950b57cec5SDimitry Andric /// Update MemorySSA when inserting a unique backedge block for a loop. 960b57cec5SDimitry Andric void updatePhisWhenInsertingUniqueBackedgeBlock(BasicBlock *LoopHeader, 970b57cec5SDimitry Andric BasicBlock *LoopPreheader, 980b57cec5SDimitry Andric BasicBlock *BackedgeBlock); 990b57cec5SDimitry Andric /// Update MemorySSA after a loop was cloned, given the blocks in RPO order, 1000b57cec5SDimitry Andric /// the exit blocks and a 1:1 mapping of all blocks and instructions 1010b57cec5SDimitry Andric /// cloned. This involves duplicating all defs and uses in the cloned blocks 1020b57cec5SDimitry Andric /// Updating phi nodes in exit block successors is done separately. 1030b57cec5SDimitry Andric void updateForClonedLoop(const LoopBlocksRPO &LoopBlocks, 1040b57cec5SDimitry Andric ArrayRef<BasicBlock *> ExitBlocks, 1050b57cec5SDimitry Andric const ValueToValueMapTy &VM, 1060b57cec5SDimitry Andric bool IgnoreIncomingWithNoClones = false); 1070b57cec5SDimitry Andric // Block BB was fully or partially cloned into its predecessor P1. Map 1080b57cec5SDimitry Andric // contains the 1:1 mapping of instructions cloned and VM[BB]=P1. 1090b57cec5SDimitry Andric void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1, 1100b57cec5SDimitry Andric const ValueToValueMapTy &VM); 1110b57cec5SDimitry Andric /// Update phi nodes in exit block successors following cloning. Exit blocks 1120b57cec5SDimitry Andric /// that were not cloned don't have additional predecessors added. 1130b57cec5SDimitry Andric void updateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks, 1140b57cec5SDimitry Andric const ValueToValueMapTy &VMap, 1150b57cec5SDimitry Andric DominatorTree &DT); 1160b57cec5SDimitry Andric void updateExitBlocksForClonedLoop( 1170b57cec5SDimitry Andric ArrayRef<BasicBlock *> ExitBlocks, 1180b57cec5SDimitry Andric ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT); 1190b57cec5SDimitry Andric 120e8d8bef9SDimitry Andric /// Apply CFG updates, analogous with the DT edge updates. By default, the 121e8d8bef9SDimitry Andric /// DT is assumed to be already up to date. If UpdateDTFirst is true, first 122e8d8bef9SDimitry Andric /// update the DT with the same updates. 123e8d8bef9SDimitry Andric void applyUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT, 124e8d8bef9SDimitry Andric bool UpdateDTFirst = false); 1250b57cec5SDimitry Andric /// Apply CFG insert updates, analogous with the DT edge updates. 1260b57cec5SDimitry Andric void applyInsertUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT); 1270b57cec5SDimitry Andric 1280b57cec5SDimitry Andric void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where); 1290b57cec5SDimitry Andric void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where); 1300b57cec5SDimitry Andric void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, 1310b57cec5SDimitry Andric MemorySSA::InsertionPlace Where); 1320b57cec5SDimitry Andric /// `From` block was spliced into `From` and `To`. There is a CFG edge from 1330b57cec5SDimitry Andric /// `From` to `To`. Move all accesses from `From` to `To` starting at 1340b57cec5SDimitry Andric /// instruction `Start`. `To` is newly created BB, so empty of 1350b57cec5SDimitry Andric /// MemorySSA::MemoryAccesses. Edges are already updated, so successors of 1360b57cec5SDimitry Andric /// `To` with MPhi nodes need to update incoming block. 1370b57cec5SDimitry Andric /// |------| |------| 1380b57cec5SDimitry Andric /// | From | | From | 1390b57cec5SDimitry Andric /// | | |------| 1400b57cec5SDimitry Andric /// | | || 1410b57cec5SDimitry Andric /// | | => \/ 1420b57cec5SDimitry Andric /// | | |------| <- Start 1430b57cec5SDimitry Andric /// | | | To | 1440b57cec5SDimitry Andric /// |------| |------| 1450b57cec5SDimitry Andric void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, 1460b57cec5SDimitry Andric Instruction *Start); 1470b57cec5SDimitry Andric /// `From` block was merged into `To`. There is a CFG edge from `To` to 1480b57cec5SDimitry Andric /// `From`.`To` still branches to `From`, but all instructions were moved and 1490b57cec5SDimitry Andric /// `From` is now an empty block; `From` is about to be deleted. Move all 1500b57cec5SDimitry Andric /// accesses from `From` to `To` starting at instruction `Start`. `To` may 1510b57cec5SDimitry Andric /// have multiple successors, `From` has a single predecessor. `From` may have 1520b57cec5SDimitry Andric /// successors with MPhi nodes, replace their incoming block with `To`. 1530b57cec5SDimitry Andric /// |------| |------| 1540b57cec5SDimitry Andric /// | To | | To | 1550b57cec5SDimitry Andric /// |------| | | 1560b57cec5SDimitry Andric /// || => | | 1570b57cec5SDimitry Andric /// \/ | | 1580b57cec5SDimitry Andric /// |------| | | <- Start 1590b57cec5SDimitry Andric /// | From | | | 1600b57cec5SDimitry Andric /// |------| |------| 1610b57cec5SDimitry Andric void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, 1620b57cec5SDimitry Andric Instruction *Start); 1630b57cec5SDimitry Andric /// A new empty BasicBlock (New) now branches directly to Old. Some of 1640b57cec5SDimitry Andric /// Old's predecessors (Preds) are now branching to New instead of Old. 1650b57cec5SDimitry Andric /// If New is the only predecessor, move Old's Phi, if present, to New. 1660b57cec5SDimitry Andric /// Otherwise, add a new Phi in New with appropriate incoming values, and 1670b57cec5SDimitry Andric /// update the incoming values in Old's Phi node too, if present. 1680b57cec5SDimitry Andric void wireOldPredecessorsToNewImmediatePredecessor( 1690b57cec5SDimitry Andric BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds, 1700b57cec5SDimitry Andric bool IdenticalEdgesWereMerged = true); 1710b57cec5SDimitry Andric // The below are utility functions. Other than creation of accesses to pass 1720b57cec5SDimitry Andric // to insertDef, and removeAccess to remove accesses, you should generally 1730b57cec5SDimitry Andric // not attempt to update memoryssa yourself. It is very non-trivial to get 1740b57cec5SDimitry Andric // the edge cases right, and the above calls already operate in near-optimal 1750b57cec5SDimitry Andric // time bounds. 1760b57cec5SDimitry Andric 1775f757f3fSDimitry Andric /// Create a MemoryAccess in MemorySSA at a specified point in a block. 1780b57cec5SDimitry Andric /// 1795f757f3fSDimitry Andric /// When used by itself, this method will only insert the new MemoryAccess 1805f757f3fSDimitry Andric /// into the access list, but not make any other changes, such as inserting 1815f757f3fSDimitry Andric /// MemoryPHI nodes, or updating users to point to the new MemoryAccess. You 1825f757f3fSDimitry Andric /// must specify a correct Definition in this case. 1835f757f3fSDimitry Andric /// 1845f757f3fSDimitry Andric /// Usually, this API is instead combined with insertUse() or insertDef(), 1855f757f3fSDimitry Andric /// which will perform all the necessary MSSA updates. If these APIs are used, 1865f757f3fSDimitry Andric /// then nullptr can be used as Definition, as the correct defining access 1875f757f3fSDimitry Andric /// will be automatically determined. 1885f757f3fSDimitry Andric /// 1890b57cec5SDimitry Andric /// Note: If a MemoryAccess already exists for I, this function will make it 1900b57cec5SDimitry Andric /// inaccessible and it *must* have removeMemoryAccess called on it. 1910b57cec5SDimitry Andric MemoryAccess *createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, 1920b57cec5SDimitry Andric const BasicBlock *BB, 1930b57cec5SDimitry Andric MemorySSA::InsertionPlace Point); 1940b57cec5SDimitry Andric 1955f757f3fSDimitry Andric /// Create a MemoryAccess in MemorySSA before an existing MemoryAccess. 1960b57cec5SDimitry Andric /// 1975f757f3fSDimitry Andric /// See createMemoryAccessInBB() for usage details. 1980b57cec5SDimitry Andric MemoryUseOrDef *createMemoryAccessBefore(Instruction *I, 1990b57cec5SDimitry Andric MemoryAccess *Definition, 2000b57cec5SDimitry Andric MemoryUseOrDef *InsertPt); 2015f757f3fSDimitry Andric /// Create a MemoryAccess in MemorySSA after an existing MemoryAccess. 2025f757f3fSDimitry Andric /// 2035f757f3fSDimitry Andric /// See createMemoryAccessInBB() for usage details. 2040b57cec5SDimitry Andric MemoryUseOrDef *createMemoryAccessAfter(Instruction *I, 2050b57cec5SDimitry Andric MemoryAccess *Definition, 2060b57cec5SDimitry Andric MemoryAccess *InsertPt); 2070b57cec5SDimitry Andric 2080b57cec5SDimitry Andric /// Remove a MemoryAccess from MemorySSA, including updating all 2090b57cec5SDimitry Andric /// definitions and uses. 2100b57cec5SDimitry Andric /// This should be called when a memory instruction that has a MemoryAccess 2110b57cec5SDimitry Andric /// associated with it is erased from the program. For example, if a store or 2120b57cec5SDimitry Andric /// load is simply erased (not replaced), removeMemoryAccess should be called 2130b57cec5SDimitry Andric /// on the MemoryAccess for that store/load. 2140b57cec5SDimitry Andric void removeMemoryAccess(MemoryAccess *, bool OptimizePhis = false); 2150b57cec5SDimitry Andric 2160b57cec5SDimitry Andric /// Remove MemoryAccess for a given instruction, if a MemoryAccess exists. 2170b57cec5SDimitry Andric /// This should be called when an instruction (load/store) is deleted from 2180b57cec5SDimitry Andric /// the program. 2190b57cec5SDimitry Andric void removeMemoryAccess(const Instruction *I, bool OptimizePhis = false) { 2200b57cec5SDimitry Andric if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) 2210b57cec5SDimitry Andric removeMemoryAccess(MA, OptimizePhis); 2220b57cec5SDimitry Andric } 2230b57cec5SDimitry Andric 2240b57cec5SDimitry Andric /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted. 2250b57cec5SDimitry Andric /// Assumption we make here: all uses of deleted defs and phi must either 2260b57cec5SDimitry Andric /// occur in blocks about to be deleted (thus will be deleted as well), or 2270b57cec5SDimitry Andric /// they occur in phis that will simply lose an incoming value. 2280b57cec5SDimitry Andric /// Deleted blocks still have successor info, but their predecessor edges and 2290b57cec5SDimitry Andric /// Phi nodes may already be updated. Instructions in DeadBlocks should be 2300b57cec5SDimitry Andric /// deleted after this call. 2310b57cec5SDimitry Andric void removeBlocks(const SmallSetVector<BasicBlock *, 8> &DeadBlocks); 2320b57cec5SDimitry Andric 2330b57cec5SDimitry Andric /// Instruction I will be changed to an unreachable. Remove all accesses in 2340b57cec5SDimitry Andric /// I's block that follow I (inclusive), and update the Phis in the blocks' 2350b57cec5SDimitry Andric /// successors. 2360b57cec5SDimitry Andric void changeToUnreachable(const Instruction *I); 2370b57cec5SDimitry Andric 2380b57cec5SDimitry Andric /// Get handle on MemorySSA. getMemorySSA()2390b57cec5SDimitry Andric MemorySSA* getMemorySSA() const { return MSSA; } 2400b57cec5SDimitry Andric 2410b57cec5SDimitry Andric private: 2420b57cec5SDimitry Andric // Move What before Where in the MemorySSA IR. 2430b57cec5SDimitry Andric template <class WhereType> 2440b57cec5SDimitry Andric void moveTo(MemoryUseOrDef *What, BasicBlock *BB, WhereType Where); 2450b57cec5SDimitry Andric // Move all memory accesses from `From` to `To` starting at `Start`. 2460b57cec5SDimitry Andric // Restrictions apply, see public wrappers of this method. 2470b57cec5SDimitry Andric void moveAllAccesses(BasicBlock *From, BasicBlock *To, Instruction *Start); 2480b57cec5SDimitry Andric MemoryAccess *getPreviousDef(MemoryAccess *); 2490b57cec5SDimitry Andric MemoryAccess *getPreviousDefInBlock(MemoryAccess *); 2500b57cec5SDimitry Andric MemoryAccess * 2510b57cec5SDimitry Andric getPreviousDefFromEnd(BasicBlock *, 2520b57cec5SDimitry Andric DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &); 2530b57cec5SDimitry Andric MemoryAccess * 2540b57cec5SDimitry Andric getPreviousDefRecursive(BasicBlock *, 2550b57cec5SDimitry Andric DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &); 2560b57cec5SDimitry Andric MemoryAccess *recursePhi(MemoryAccess *Phi); 2578bcb0991SDimitry Andric MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi); 2580b57cec5SDimitry Andric template <class RangeType> 2590b57cec5SDimitry Andric MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands); 2600b57cec5SDimitry Andric void tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs); 2610b57cec5SDimitry Andric void fixupDefs(const SmallVectorImpl<WeakVH> &); 2620b57cec5SDimitry Andric // Clone all uses and defs from BB to NewBB given a 1:1 map of all 2630b57cec5SDimitry Andric // instructions and blocks cloned, and a map of MemoryPhi : Definition 2640b57cec5SDimitry Andric // (MemoryAccess Phi or Def). VMap maps old instructions to cloned 2650b57cec5SDimitry Andric // instructions and old blocks to cloned blocks. MPhiMap, is created in the 2660b57cec5SDimitry Andric // caller of this private method, and maps existing MemoryPhis to new 2670b57cec5SDimitry Andric // definitions that new MemoryAccesses must point to. These definitions may 2680b57cec5SDimitry Andric // not necessarily be MemoryPhis themselves, they may be MemoryDefs. As such, 2690b57cec5SDimitry Andric // the map is between MemoryPhis and MemoryAccesses, where the MemoryAccesses 2700b57cec5SDimitry Andric // may be MemoryPhis or MemoryDefs and not MemoryUses. 2710b57cec5SDimitry Andric // If CloneWasSimplified = true, the clone was exact. Otherwise, assume that 2720b57cec5SDimitry Andric // the clone involved simplifications that may have: (1) turned a MemoryUse 2730b57cec5SDimitry Andric // into an instruction that MemorySSA has no representation for, or (2) turned 2740b57cec5SDimitry Andric // a MemoryDef into a MemoryUse or an instruction that MemorySSA has no 2750b57cec5SDimitry Andric // representation for. No other cases are supported. 2760b57cec5SDimitry Andric void cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB, 2770b57cec5SDimitry Andric const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap, 2780b57cec5SDimitry Andric bool CloneWasSimplified = false); 2790b57cec5SDimitry Andric template <typename Iter> 2800b57cec5SDimitry Andric void privateUpdateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks, 2810b57cec5SDimitry Andric Iter ValuesBegin, Iter ValuesEnd, 2820b57cec5SDimitry Andric DominatorTree &DT); 2830b57cec5SDimitry Andric void applyInsertUpdates(ArrayRef<CFGUpdate>, DominatorTree &DT, 2840b57cec5SDimitry Andric const GraphDiff<BasicBlock *> *GD); 2850b57cec5SDimitry Andric }; 2860b57cec5SDimitry Andric } // end namespace llvm 2870b57cec5SDimitry Andric 2880b57cec5SDimitry Andric #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H 289