LLVM  10.0.0svn
CodeExtractor.h
Go to the documentation of this file.
1 //===- Transform/Utils/CodeExtractor.h - Code extraction util ---*- 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 // A utility to support extracting code from one function into its own
10 // stand-alone function.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H
15 #define LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H
16 
17 #include "llvm/ADT/ArrayRef.h"
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include <limits>
22 
23 namespace llvm {
24 
25 class AllocaInst;
26 class BasicBlock;
27 class BlockFrequency;
28 class BlockFrequencyInfo;
29 class BranchProbabilityInfo;
30 class AssumptionCache;
31 class CallInst;
32 class DominatorTree;
33 class Function;
34 class Instruction;
35 class Loop;
36 class Module;
37 class Type;
38 class Value;
39 
40 /// A cache for the CodeExtractor analysis. The operation \ref
41 /// CodeExtractor::extractCodeRegion is guaranteed not to invalidate this
42 /// object. This object should conservatively be considered invalid if any
43 /// other mutating operations on the IR occur.
44 ///
45 /// Constructing this object is O(n) in the size of the function.
47  /// The allocas in the function.
49 
50  /// Base memory addresses of load/store instructions, grouped by block.
52 
53  /// Blocks which contain instructions which may have unknown side-effects
54  /// on memory.
55  DenseSet<BasicBlock *> SideEffectingBlocks;
56 
57  void findSideEffectInfoForBlock(BasicBlock &BB);
58 
59 public:
61 
62  /// Get the allocas in the function at the time the analysis was created.
63  /// Note that some of these allocas may no longer be present in the function,
64  /// due to \ref CodeExtractor::extractCodeRegion.
65  ArrayRef<AllocaInst *> getAllocas() const { return Allocas; }
66 
67  /// Check whether \p BB contains an instruction thought to load from, store
68  /// to, or otherwise clobber the alloca \p Addr.
70 };
71 
72  /// Utility class for extracting code into a new function.
73  ///
74  /// This utility provides a simple interface for extracting some sequence of
75  /// code into its own function, replacing it with a call to that function. It
76  /// also provides various methods to query about the nature and result of
77  /// such a transformation.
78  ///
79  /// The rough algorithm used is:
80  /// 1) Find both the inputs and outputs for the extracted region.
81  /// 2) Pass the inputs as arguments, remapping them within the extracted
82  /// function to arguments.
83  /// 3) Add allocas for any scalar outputs, adding all of the outputs' allocas
84  /// as arguments, and inserting stores to the arguments for any scalars.
85  class CodeExtractor {
87 
88  // Various bits of state computed on construction.
89  DominatorTree *const DT;
90  const bool AggregateArgs;
93  AssumptionCache *AC;
94 
95  // If true, varargs functions can be extracted.
96  bool AllowVarArgs;
97 
98  // Bits of intermediate state computed at various phases of extraction.
100  unsigned NumExitBlocks = std::numeric_limits<unsigned>::max();
101  Type *RetTy;
102 
103  // Suffix to use when creating extracted function (appended to the original
104  // function name + "."). If empty, the default is to use the entry block
105  // label, if non-empty, otherwise "extracted".
106  std::string Suffix;
107 
108  public:
109  /// Create a code extractor for a sequence of blocks.
110  ///
111  /// Given a sequence of basic blocks where the first block in the sequence
112  /// dominates the rest, prepare a code extractor object for pulling this
113  /// sequence out into its new function. When a DominatorTree is also given,
114  /// extra checking and transformations are enabled. If AllowVarArgs is true,
115  /// vararg functions can be extracted. This is safe, if all vararg handling
116  /// code is extracted, including vastart. If AllowAlloca is true, then
117  /// extraction of blocks containing alloca instructions would be possible,
118  /// however code extractor won't validate whether extraction is legal.
120  bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr,
121  BranchProbabilityInfo *BPI = nullptr,
122  AssumptionCache *AC = nullptr,
123  bool AllowVarArgs = false, bool AllowAlloca = false,
124  std::string Suffix = "");
125 
126  /// Create a code extractor for a loop body.
127  ///
128  /// Behaves just like the generic code sequence constructor, but uses the
129  /// block sequence of the loop.
130  CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false,
131  BlockFrequencyInfo *BFI = nullptr,
132  BranchProbabilityInfo *BPI = nullptr,
133  AssumptionCache *AC = nullptr,
134  std::string Suffix = "");
135 
136  /// Perform the extraction, returning the new function.
137  ///
138  /// Returns zero when called on a CodeExtractor instance where isEligible
139  /// returns false.
140  Function *extractCodeRegion(const CodeExtractorAnalysisCache &CEAC);
141 
142  /// Verify that assumption cache isn't stale after a region is extracted.
143  /// Returns false when verifier finds errors. AssumptionCache is passed as
144  /// parameter to make this function stateless.
145  static bool verifyAssumptionCache(const Function& F, AssumptionCache *AC);
146 
147  /// Test whether this code extractor is eligible.
148  ///
149  /// Based on the blocks used when constructing the code extractor,
150  /// determine whether it is eligible for extraction.
151  ///
152  /// Checks that varargs handling (with vastart and vaend) is only done in
153  /// the outlined blocks.
154  bool isEligible() const;
155 
156  /// Compute the set of input values and output values for the code.
157  ///
158  /// These can be used either when performing the extraction or to evaluate
159  /// the expected size of a call to the extracted function. Note that this
160  /// work cannot be cached between the two as once we decide to extract
161  /// a code sequence, that sequence is modified, including changing these
162  /// sets, before extraction occurs. These modifications won't have any
163  /// significant impact on the cost however.
164  void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,
165  const ValueSet &Allocas) const;
166 
167  /// Check if life time marker nodes can be hoisted/sunk into the outline
168  /// region.
169  ///
170  /// Returns true if it is safe to do the code motion.
171  bool
172  isLegalToShrinkwrapLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC,
173  Instruction *AllocaAddr) const;
174 
175  /// Find the set of allocas whose life ranges are contained within the
176  /// outlined region.
177  ///
178  /// Allocas which have life_time markers contained in the outlined region
179  /// should be pushed to the outlined function. The address bitcasts that
180  /// are used by the lifetime markers are also candidates for shrink-
181  /// wrapping. The instructions that need to be sunk are collected in
182  /// 'Allocas'.
183  void findAllocas(const CodeExtractorAnalysisCache &CEAC,
184  ValueSet &SinkCands, ValueSet &HoistCands,
185  BasicBlock *&ExitBlock) const;
186 
187  /// Find or create a block within the outline region for placing hoisted
188  /// code.
189  ///
190  /// CommonExitBlock is block outside the outline region. It is the common
191  /// successor of blocks inside the region. If there exists a single block
192  /// inside the region that is the predecessor of CommonExitBlock, that block
193  /// will be returned. Otherwise CommonExitBlock will be split and the
194  /// original block will be added to the outline region.
195  BasicBlock *findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock);
196 
197  private:
198  struct LifetimeMarkerInfo {
199  bool SinkLifeStart = false;
200  bool HoistLifeEnd = false;
201  Instruction *LifeStart = nullptr;
202  Instruction *LifeEnd = nullptr;
203  };
204 
205  LifetimeMarkerInfo
206  getLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC,
207  Instruction *Addr, BasicBlock *ExitBlock) const;
208 
209  void severSplitPHINodesOfEntry(BasicBlock *&Header);
210  void severSplitPHINodesOfExits(const SmallPtrSetImpl<BasicBlock *> &Exits);
211  void splitReturnBlocks();
212 
213  Function *constructFunction(const ValueSet &inputs,
214  const ValueSet &outputs,
215  BasicBlock *header,
216  BasicBlock *newRootNode, BasicBlock *newHeader,
217  Function *oldFunction, Module *M);
218 
219  void moveCodeToFunction(Function *newFunction);
220 
221  void calculateNewCallTerminatorWeights(
222  BasicBlock *CodeReplacer,
224  BranchProbabilityInfo *BPI);
225 
226  CallInst *emitCallAndSwitchStatement(Function *newFunction,
227  BasicBlock *newHeader,
228  ValueSet &inputs, ValueSet &outputs);
229  };
230 
231 } // end namespace llvm
232 
233 #endif // LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H
Utility class for extracting code into a new function.
Definition: CodeExtractor.h:85
ArrayRef< AllocaInst * > getAllocas() const
Get the allocas in the function at the time the analysis was created.
Definition: CodeExtractor.h:65
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Various leaf nodes.
Definition: ISDOpcodes.h:59
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
This class represents a function call, abstracting a target machine&#39;s calling convention.
A cache of @llvm.assume calls within a function.
F(f)
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
bool doesBlockContainClobberOfAddr(BasicBlock &BB, AllocaInst *Addr) const
Check whether BB contains an instruction thought to load from, store to, or otherwise clobber the all...
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
A cache for the CodeExtractor analysis.
Definition: CodeExtractor.h:46
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:390
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Analysis providing branch probability information.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
A vector that has set insertion semantics.
Definition: SetVector.h:40
an instruction to allocate memory on the stack
Definition: Instructions.h:59