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
25namespace 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.
29namespace sroa {
30class AllocaSliceRewriter;
31class AllocaSlices;
32class Partition;
33class 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.
54class 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
101public:
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
109private:
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
130