include/llvm/Transforms/Scalar/SROA.h

   1 //===- SROA.h - Scalar Replacement Of Aggregates ----------------*- 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 /// \file
  10 /// This file provides the interface for LLVM's Scalar Replacement of
  11 /// Aggregates pass. This pass provides both aggregate splitting and the
  12 /// primary SSA formation used in the compiler.
  13 ///
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_TRANSFORMS_SCALAR_SROA_H
  17 #define LLVM_TRANSFORMS_SCALAR_SROA_H
  18
  19 #include "llvm/ADT/SetVector.h"
  20 #include "llvm/Analysis/AssumptionCache.h"
  21 #include "llvm/IR/Dominators.h"
  22 #include "llvm/IR/Function.h"
  23 #include "llvm/IR/PassManager.h"
  24
  25 namespace llvm {
  26
  27 /// A private "module" namespace for types and utilities used by SROA. These
  28 /// are implementation details and should not be used by clients.
  29 namespace sroa {
  30 class AllocaSliceRewriter;
  31 class AllocaSlices;
  32 class Partition;
  33 class SROALegacyPass;
  34 }
  35
  36 /// \brief An optimization pass providing Scalar Replacement of Aggregates.
  37 ///
  38 /// This pass takes allocations which can be completely analyzed (that is, they
  39 /// don't escape) and tries to turn them into scalar SSA values. There are
  40 /// a few steps to this process.
  41 ///
  42 /// 1) It takes allocations of aggregates and analyzes the ways in which they
  43 ///    are used to try to split them into smaller allocations, ideally of
  44 ///    a single scalar data type. It will split up memcpy and memset accesses
  45 ///    as necessary and try to isolate individual scalar accesses.
  46 /// 2) It will transform accesses into forms which are suitable for SSA value
  47 ///    promotion. This can be replacing a memset with a scalar store of an
  48 ///    integer value, or it can involve speculating operations on a PHI or
  49 ///    select to be a PHI or select of the results.
  50 /// 3) Finally, this will try to detect a pattern of accesses which map cleanly
  51 ///    onto insert and extract operations on a vector value, and convert them to
  52 ///    this form. By doing so, it will enable promotion of vector aggregates to
  53 ///    SSA vector values.
  54 class SROA {
  55   LLVMContext *C;
  56   DominatorTree *DT;
  57   AssumptionCache *AC;
  58
  59   /// \brief Worklist of alloca instructions to simplify.
  60   ///
  61   /// Each alloca in the function is added to this. Each new alloca formed gets
  62   /// added to it as well to recursively simplify unless that alloca can be
  63   /// directly promoted. Finally, each time we rewrite a use of an alloca other
  64   /// the one being actively rewritten, we add it back onto the list if not
  65   /// already present to ensure it is re-visited.
  66   SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> Worklist;
  67
  68   /// \brief A collection of instructions to delete.
  69   /// We try to batch deletions to simplify code and make things a bit more
  70   /// efficient.
  71   SetVector<Instruction *, SmallVector<Instruction *, 8>> DeadInsts;
  72
  73   /// \brief Post-promotion worklist.
  74   ///
  75   /// Sometimes we discover an alloca which has a high probability of becoming
  76   /// viable for SROA after a round of promotion takes place. In those cases,
  77   /// the alloca is enqueued here for re-processing.
  78   ///
  79   /// Note that we have to be very careful to clear allocas out of this list in
  80   /// the event they are deleted.
  81   SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> PostPromotionWorklist;
  82
  83   /// \brief A collection of alloca instructions we can directly promote.
  84   std::vector<AllocaInst *> PromotableAllocas;
  85
  86   /// \brief A worklist of PHIs to speculate prior to promoting allocas.
  87   ///
  88   /// All of these PHIs have been checked for the safety of speculation and by
  89   /// being speculated will allow promoting allocas currently in the promotable
  90   /// queue.
  91   SetVector<PHINode *, SmallVector<PHINode *, 2>> SpeculatablePHIs;
  92
  93   /// \brief A worklist of select instructions to speculate prior to promoting
  94   /// allocas.
  95   ///
  96   /// All of these select instructions have been checked for the safety of
  97   /// speculation and by being speculated will allow promoting allocas
  98   /// currently in the promotable queue.
  99   SetVector<SelectInst *, SmallVector<SelectInst *, 2>> SpeculatableSelects;
 100
 101 public:
 102   SROA() : C(nullptr), DT(nullptr), AC(nullptr) {}
 103
 104   static StringRef name() { return "SROA"; }
 105
 106   /// \brief Run the pass over the function.
 107   PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM);
 108
 109 private:
 110   friend class sroa::AllocaSliceRewriter;
 111   friend class sroa::SROALegacyPass;
 112
 113   /// Helper used by both the public run method and by the legacy pass.
 114   PreservedAnalyses runImpl(Function &F, DominatorTree &RunDT,
 115                             AssumptionCache &RunAC);
 116
 117   bool presplitLoadsAndStores(AllocaInst &AI, sroa::AllocaSlices &AS);
 118   AllocaInst *rewritePartition(AllocaInst &AI, sroa::AllocaSlices &AS,
 119                                sroa::Partition &P);
 120   bool splitAlloca(AllocaInst &AI, sroa::AllocaSlices &AS);
 121   bool runOnAlloca(AllocaInst &AI);
 122   void clobberUse(Use &U);
 123   void deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas);
 124   bool promoteAllocas(Function &F);
 125 };
 126
 127 }
 128
 129 #endif