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