include/llvm/Transforms/Scalar/SROA.h

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