include/llvm/Transforms/Utils/SSAUpdater.h

   1 //===- SSAUpdater.h - Unstructured SSA Update Tool --------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file declares the SSAUpdater class.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATER_H
  14 #define LLVM_TRANSFORMS_UTILS_SSAUPDATER_H
  15
  16 #include "llvm/ADT/ArrayRef.h"
  17 #include "llvm/ADT/StringRef.h"
  18 #include <string>
  19
  20 namespace llvm {
  21
  22 class BasicBlock;
  23 class Instruction;
  24 class LoadInst;
  25 class PHINode;
  26 template <typename T> class SmallVectorImpl;
  27 template <typename T> class SSAUpdaterTraits;
  28 class Type;
  29 class Use;
  30 class Value;
  31
  32 /// Helper class for SSA formation on a set of values defined in
  33 /// multiple blocks.
  34 ///
  35 /// This is used when code duplication or another unstructured
  36 /// transformation wants to rewrite a set of uses of one value with uses of a
  37 /// set of values.
  38 class SSAUpdater {
  39   friend class SSAUpdaterTraits<SSAUpdater>;
  40
  41 private:
  42   /// This keeps track of which value to use on a per-block basis. When we
  43   /// insert PHI nodes, we keep track of them here.
  44   void *AV = nullptr;
  45
  46   /// ProtoType holds the type of the values being rewritten.
  47   Type *ProtoType = nullptr;
  48
  49   /// PHI nodes are given a name based on ProtoName.
  50   std::string ProtoName;
  51
  52   /// If this is non-null, the SSAUpdater adds all PHI nodes that it creates to
  53   /// the vector.
  54   SmallVectorImpl<PHINode *> *InsertedPHIs;
  55
  56 public:
  57   /// If InsertedPHIs is specified, it will be filled
  58   /// in with all PHI Nodes created by rewriting.
  59   explicit SSAUpdater(SmallVectorImpl<PHINode *> *InsertedPHIs = nullptr);
  60   SSAUpdater(const SSAUpdater &) = delete;
  61   SSAUpdater &operator=(const SSAUpdater &) = delete;
  62   ~SSAUpdater();
  63
  64   /// Reset this object to get ready for a new set of SSA updates with
  65   /// type 'Ty'.
  66   ///
  67   /// PHI nodes get a name based on 'Name'.
  68   void Initialize(Type *Ty, StringRef Name);
  69
  70   /// Indicate that a rewritten value is available in the specified block
  71   /// with the specified value.
  72   void AddAvailableValue(BasicBlock *BB, Value *V);
  73
  74   /// Return true if the SSAUpdater already has a value for the specified
  75   /// block.
  76   bool HasValueForBlock(BasicBlock *BB) const;
  77
  78   /// Return the value for the specified block if the SSAUpdater has one,
  79   /// otherwise return nullptr.
  80   Value *FindValueForBlock(BasicBlock *BB) const;
  81
  82   /// Construct SSA form, materializing a value that is live at the end
  83   /// of the specified block.
  84   Value *GetValueAtEndOfBlock(BasicBlock *BB);
  85
  86   /// Construct SSA form, materializing a value that is live in the
  87   /// middle of the specified block.
  88   ///
  89   /// \c GetValueInMiddleOfBlock is the same as \c GetValueAtEndOfBlock except
  90   /// in one important case: if there is a definition of the rewritten value
  91   /// after the 'use' in BB.  Consider code like this:
  92   ///
  93   /// \code
  94   ///      X1 = ...
  95   ///   SomeBB:
  96   ///      use(X)
  97   ///      X2 = ...
  98   ///      br Cond, SomeBB, OutBB
  99   /// \endcode
 100   ///
 101   /// In this case, there are two values (X1 and X2) added to the AvailableVals
 102   /// set by the client of the rewriter, and those values are both live out of
 103   /// their respective blocks.  However, the use of X happens in the *middle* of
 104   /// a block.  Because of this, we need to insert a new PHI node in SomeBB to
 105   /// merge the appropriate values, and this value isn't live out of the block.
 106   Value *GetValueInMiddleOfBlock(BasicBlock *BB);
 107
 108   /// Rewrite a use of the symbolic value.
 109   ///
 110   /// This handles PHI nodes, which use their value in the corresponding
 111   /// predecessor. Note that this will not work if the use is supposed to be
 112   /// rewritten to a value defined in the same block as the use, but above it.
 113   /// Any 'AddAvailableValue's added for the use's block will be considered to
 114   /// be below it.
 115   void RewriteUse(Use &U);
 116
 117   /// Rewrite a use like \c RewriteUse but handling in-block definitions.
 118   ///
 119   /// This version of the method can rewrite uses in the same block as
 120   /// a definition, because it assumes that all uses of a value are below any
 121   /// inserted values.
 122   void RewriteUseAfterInsertions(Use &U);
 123
 124 private:
 125   Value *GetValueAtEndOfBlockInternal(BasicBlock *BB);
 126 };
 127
 128 /// Helper class for promoting a collection of loads and stores into SSA
 129 /// Form using the SSAUpdater.
 130 ///
 131 /// This handles complexities that SSAUpdater doesn't, such as multiple loads
 132 /// and stores in one block.
 133 ///
 134 /// Clients of this class are expected to subclass this and implement the
 135 /// virtual methods.
 136 class LoadAndStorePromoter {
 137 protected:
 138   SSAUpdater &SSA;
 139
 140 public:
 141   LoadAndStorePromoter(ArrayRef<const Instruction *> Insts,
 142                        SSAUpdater &S, StringRef Name = StringRef());
 143   virtual ~LoadAndStorePromoter() = default;
 144
 145   /// This does the promotion.
 146   ///
 147   /// Insts is a list of loads and stores to promote, and Name is the basename
 148   /// for the PHIs to insert. After this is complete, the loads and stores are
 149   /// removed from the code.
 150   void run(const SmallVectorImpl<Instruction *> &Insts);
 151
 152   /// Return true if the specified instruction is in the Inst list.
 153   ///
 154   /// The Insts list is the one passed into the constructor. Clients should
 155   /// implement this with a more efficient version if possible.
 156   virtual bool isInstInList(Instruction *I,
 157                             const SmallVectorImpl<Instruction *> &Insts) const;
 158
 159   /// This hook is invoked after all the stores are found and inserted as
 160   /// available values.
 161   virtual void doExtraRewritesBeforeFinalDeletion() {}
 162
 163   /// Clients can choose to implement this to get notified right before
 164   /// a load is RAUW'd another value.
 165   virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const {}
 166
 167   /// Called before each instruction is deleted.
 168   virtual void instructionDeleted(Instruction *I) const {}
 169
 170   /// Called to update debug info associated with the instruction.
 171   virtual void updateDebugInfo(Instruction *I) const {}
 172 };
 173
 174 } // end namespace llvm
 175
 176 #endif // LLVM_TRANSFORMS_UTILS_SSAUPDATER_H