LLVM  15.0.0git
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 <limits>
21 
22 namespace llvm {
23 
24 template <typename PtrType> class SmallPtrSetImpl;
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;
91  BlockFrequencyInfo *BFI;
93  AssumptionCache *AC;
94 
95  // A block outside of the extraction set where any intermediate
96  // allocations will be placed inside. If this is null, allocations
97  // will be placed in the entry block of the function.
98  BasicBlock *AllocationBlock;
99 
100  // If true, varargs functions can be extracted.
101  bool AllowVarArgs;
102 
103  // Bits of intermediate state computed at various phases of extraction.
105  unsigned NumExitBlocks = std::numeric_limits<unsigned>::max();
106  Type *RetTy;
107 
108  // Mapping from the original exit blocks, to the new blocks inside
109  // the function.
110  SmallVector<BasicBlock *, 4> OldTargets;
111 
112  // Suffix to use when creating extracted function (appended to the original
113  // function name + "."). If empty, the default is to use the entry block
114  // label, if non-empty, otherwise "extracted".
115  std::string Suffix;
116 
117  public:
118  /// Create a code extractor for a sequence of blocks.
119  ///
120  /// Given a sequence of basic blocks where the first block in the sequence
121  /// dominates the rest, prepare a code extractor object for pulling this
122  /// sequence out into its new function. When a DominatorTree is also given,
123  /// extra checking and transformations are enabled. If AllowVarArgs is true,
124  /// vararg functions can be extracted. This is safe, if all vararg handling
125  /// code is extracted, including vastart. If AllowAlloca is true, then
126  /// extraction of blocks containing alloca instructions would be possible,
127  /// however code extractor won't validate whether extraction is legal.
128  /// Any new allocations will be placed in the AllocationBlock, unless
129  /// it is null, in which case it will be placed in the entry block of
130  /// the function from which the code is being extracted.
132  bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr,
133  BranchProbabilityInfo *BPI = nullptr,
134  AssumptionCache *AC = nullptr, bool AllowVarArgs = false,
135  bool AllowAlloca = false,
136  BasicBlock *AllocationBlock = nullptr,
137  std::string Suffix = "");
138 
139  /// Create a code extractor for a loop body.
140  ///
141  /// Behaves just like the generic code sequence constructor, but uses the
142  /// block sequence of the loop.
143  CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false,
144  BlockFrequencyInfo *BFI = nullptr,
145  BranchProbabilityInfo *BPI = nullptr,
146  AssumptionCache *AC = nullptr,
147  std::string Suffix = "");
148 
149  /// Perform the extraction, returning the new function.
150  ///
151  /// Returns zero when called on a CodeExtractor instance where isEligible
152  /// returns false.
154 
155  /// Perform the extraction, returning the new function and providing an
156  /// interface to see what was categorized as inputs and outputs.
157  ///
158  /// \param CEAC - Cache to speed up operations for the CodeExtractor when
159  /// hoisting, and extracting lifetime values and assumes.
160  /// \param Inputs [out] - filled with values marked as inputs to the
161  /// newly outlined function.
162  /// \param Outputs [out] - filled with values marked as outputs to the
163  /// newly outlined function.
164  /// \returns zero when called on a CodeExtractor instance where isEligible
165  /// returns false.
167  ValueSet &Inputs, ValueSet &Outputs);
168 
169  /// Verify that assumption cache isn't stale after a region is extracted.
170  /// Returns true when verifier finds errors. AssumptionCache is passed as
171  /// parameter to make this function stateless.
172  static bool verifyAssumptionCache(const Function &OldFunc,
173  const Function &NewFunc,
174  AssumptionCache *AC);
175 
176  /// Test whether this code extractor is eligible.
177  ///
178  /// Based on the blocks used when constructing the code extractor,
179  /// determine whether it is eligible for extraction.
180  ///
181  /// Checks that varargs handling (with vastart and vaend) is only done in
182  /// the outlined blocks.
183  bool isEligible() const;
184 
185  /// Compute the set of input values and output values for the code.
186  ///
187  /// These can be used either when performing the extraction or to evaluate
188  /// the expected size of a call to the extracted function. Note that this
189  /// work cannot be cached between the two as once we decide to extract
190  /// a code sequence, that sequence is modified, including changing these
191  /// sets, before extraction occurs. These modifications won't have any
192  /// significant impact on the cost however.
193  void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,
194  const ValueSet &Allocas) const;
195 
196  /// Check if life time marker nodes can be hoisted/sunk into the outline
197  /// region.
198  ///
199  /// Returns true if it is safe to do the code motion.
200  bool
202  Instruction *AllocaAddr) const;
203 
204  /// Find the set of allocas whose life ranges are contained within the
205  /// outlined region.
206  ///
207  /// Allocas which have life_time markers contained in the outlined region
208  /// should be pushed to the outlined function. The address bitcasts that
209  /// are used by the lifetime markers are also candidates for shrink-
210  /// wrapping. The instructions that need to be sunk are collected in
211  /// 'Allocas'.
212  void findAllocas(const CodeExtractorAnalysisCache &CEAC,
213  ValueSet &SinkCands, ValueSet &HoistCands,
214  BasicBlock *&ExitBlock) const;
215 
216  /// Find or create a block within the outline region for placing hoisted
217  /// code.
218  ///
219  /// CommonExitBlock is block outside the outline region. It is the common
220  /// successor of blocks inside the region. If there exists a single block
221  /// inside the region that is the predecessor of CommonExitBlock, that block
222  /// will be returned. Otherwise CommonExitBlock will be split and the
223  /// original block will be added to the outline region.
225 
226  /// Exclude a value from aggregate argument passing when extracting a code
227  /// region, passing it instead as a scalar.
229 
230  private:
231  struct LifetimeMarkerInfo {
232  bool SinkLifeStart = false;
233  bool HoistLifeEnd = false;
234  Instruction *LifeStart = nullptr;
235  Instruction *LifeEnd = nullptr;
236  };
237 
238  ValueSet ExcludeArgsFromAggregate;
239 
240  LifetimeMarkerInfo
241  getLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC,
242  Instruction *Addr, BasicBlock *ExitBlock) const;
243 
244  void severSplitPHINodesOfEntry(BasicBlock *&Header);
245  void severSplitPHINodesOfExits(const SmallPtrSetImpl<BasicBlock *> &Exits);
246  void splitReturnBlocks();
247 
248  Function *constructFunction(const ValueSet &inputs,
249  const ValueSet &outputs,
250  BasicBlock *header,
251  BasicBlock *newRootNode, BasicBlock *newHeader,
252  Function *oldFunction, Module *M);
253 
254  void moveCodeToFunction(Function *newFunction);
255 
256  void calculateNewCallTerminatorWeights(
257  BasicBlock *CodeReplacer,
259  BranchProbabilityInfo *BPI);
260 
261  CallInst *emitCallAndSwitchStatement(Function *newFunction,
262  BasicBlock *newHeader,
263  ValueSet &inputs, ValueSet &outputs);
264  };
265 
266 } // end namespace llvm
267 
268 #endif // LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::CodeExtractorAnalysisCache::doesBlockContainClobberOfAddr
bool doesBlockContainClobberOfAddr(BasicBlock &BB, AllocaInst *Addr) const
Check whether BB contains an instruction thought to load from, store to, or otherwise clobber the all...
Definition: CodeExtractor.cpp:363
llvm::CodeExtractor::findAllocas
void findAllocas(const CodeExtractorAnalysisCache &CEAC, ValueSet &SinkCands, ValueSet &HoistCands, BasicBlock *&ExitBlock) const
Find the set of allocas whose life ranges are contained within the outlined region.
Definition: CodeExtractor.cpp:494
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
llvm::CodeExtractor::extractCodeRegion
Function * extractCodeRegion(const CodeExtractorAnalysisCache &CEAC)
Perform the extraction, returning the new function.
Definition: CodeExtractor.cpp:1626
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::CodeExtractorAnalysisCache::getAllocas
ArrayRef< AllocaInst * > getAllocas() const
Get the allocas in the function at the time the analysis was created.
Definition: CodeExtractor.h:65
llvm::CodeExtractor::CodeExtractor
CodeExtractor(ArrayRef< BasicBlock * > BBs, DominatorTree *DT=nullptr, bool AggregateArgs=false, BlockFrequencyInfo *BFI=nullptr, BranchProbabilityInfo *BPI=nullptr, AssumptionCache *AC=nullptr, bool AllowVarArgs=false, bool AllowAlloca=false, BasicBlock *AllocationBlock=nullptr, std::string Suffix="")
Create a code extractor for a sequence of blocks.
Definition: CodeExtractor.cpp:245
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::CodeExtractorAnalysisCache::CodeExtractorAnalysisCache
CodeExtractorAnalysisCache(Function &F)
Definition: CodeExtractor.cpp:310
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:186
llvm::BlockFrequencyInfo
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Definition: BlockFrequencyInfo.h:37
llvm::BranchProbabilityInfo
Analysis providing branch probability information.
Definition: BranchProbabilityInfo.h:113
llvm::CodeExtractor::findInputsOutputs
void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs, const ValueSet &Allocas) const
Compute the set of input values and output values for the code.
Definition: CodeExtractor.cpp:646
llvm::Instruction
Definition: Instruction.h:42
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:78
llvm::DenseMap
Definition: DenseMap.h:716
ArrayRef.h
TemplateParamKind::Type
@ Type
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::CodeExtractor::excludeArgFromAggregate
void excludeArgFromAggregate(Value *Arg)
Exclude a value from aggregate argument passing when extracting a code region, passing it instead as ...
Definition: CodeExtractor.cpp:1881
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::CodeExtractor
Utility class for extracting code into a new function.
Definition: CodeExtractor.h:85
Module
Machine Check Debug Module
Definition: MachineCheckDebugify.cpp:122
llvm::CodeExtractor::findOrCreateBlockForHoisting
BasicBlock * findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock)
Find or create a block within the outline region for placing hoisted code.
Definition: CodeExtractor.cpp:387
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::CodeExtractor::verifyAssumptionCache
static bool verifyAssumptionCache(const Function &OldFunc, const Function &NewFunc, AssumptionCache *AC)
Verify that assumption cache isn't stale after a region is extracted.
Definition: CodeExtractor.cpp:1852
llvm::CodeExtractorAnalysisCache
A cache for the CodeExtractor analysis.
Definition: CodeExtractor.h:46
llvm::CodeExtractor::isEligible
bool isEligible() const
Test whether this code extractor is eligible.
Definition: CodeExtractor.cpp:619
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1461
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::CodeExtractor::isLegalToShrinkwrapLifetimeMarkers
bool isLegalToShrinkwrapLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC, Instruction *AllocaAddr) const
Check if life time marker nodes can be hoisted/sunk into the outline region.
Definition: CodeExtractor.cpp:373
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:58
llvm::SetVector< Value * >
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::codeview::PublicSymFlags::Function
@ Function
SetVector.h