LLVM 20.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
22namespace llvm {
23
24template <typename PtrType> class SmallPtrSetImpl;
25class AllocaInst;
26class BasicBlock;
27class BlockFrequency;
28class BlockFrequencyInfo;
29class BranchProbabilityInfo;
30class AssumptionCache;
31class CallInst;
32class DominatorTree;
33class Function;
34class Instruction;
35class Module;
36class Type;
37class Value;
38
39/// A cache for the CodeExtractor analysis. The operation \ref
40/// CodeExtractor::extractCodeRegion is guaranteed not to invalidate this
41/// object. This object should conservatively be considered invalid if any
42/// other mutating operations on the IR occur.
43///
44/// Constructing this object is O(n) in the size of the function.
46 /// The allocas in the function.
48
49 /// Base memory addresses of load/store instructions, grouped by block.
51
52 /// Blocks which contain instructions which may have unknown side-effects
53 /// on memory.
54 DenseSet<BasicBlock *> SideEffectingBlocks;
55
56 void findSideEffectInfoForBlock(BasicBlock &BB);
57
58public:
60
61 /// Get the allocas in the function at the time the analysis was created.
62 /// Note that some of these allocas may no longer be present in the function,
63 /// due to \ref CodeExtractor::extractCodeRegion.
64 ArrayRef<AllocaInst *> getAllocas() const { return Allocas; }
65
66 /// Check whether \p BB contains an instruction thought to load from, store
67 /// to, or otherwise clobber the alloca \p Addr.
69};
70
71 /// Utility class for extracting code into a new function.
72 ///
73 /// This utility provides a simple interface for extracting some sequence of
74 /// code into its own function, replacing it with a call to that function. It
75 /// also provides various methods to query about the nature and result of
76 /// such a transformation.
77 ///
78 /// The rough algorithm used is:
79 /// 1) Find both the inputs and outputs for the extracted region.
80 /// 2) Pass the inputs as arguments, remapping them within the extracted
81 /// function to arguments.
82 /// 3) Add allocas for any scalar outputs, adding all of the outputs' allocas
83 /// as arguments, and inserting stores to the arguments for any scalars.
86
87 // Various bits of state computed on construction.
88 DominatorTree *const DT;
89 const bool AggregateArgs;
93
94 // A block outside of the extraction set where any intermediate
95 // allocations will be placed inside. If this is null, allocations
96 // will be placed in the entry block of the function.
97 BasicBlock *AllocationBlock;
98
99 // If true, varargs functions can be extracted.
100 bool AllowVarArgs;
101
102 // Bits of intermediate state computed at various phases of extraction.
104 unsigned NumExitBlocks = std::numeric_limits<unsigned>::max();
105 Type *RetTy;
106
107 // Mapping from the original exit blocks, to the new blocks inside
108 // the function.
110
111 // Suffix to use when creating extracted function (appended to the original
112 // function name + "."). If empty, the default is to use the entry block
113 // label, if non-empty, otherwise "extracted".
114 std::string Suffix;
115
116 // If true, the outlined function has aggregate argument in zero address
117 // space.
118 bool ArgsInZeroAddressSpace;
119
120 public:
121 /// Create a code extractor for a sequence of blocks.
122 ///
123 /// Given a sequence of basic blocks where the first block in the sequence
124 /// dominates the rest, prepare a code extractor object for pulling this
125 /// sequence out into its new function. When a DominatorTree is also given,
126 /// extra checking and transformations are enabled. If AllowVarArgs is true,
127 /// vararg functions can be extracted. This is safe, if all vararg handling
128 /// code is extracted, including vastart. If AllowAlloca is true, then
129 /// extraction of blocks containing alloca instructions would be possible,
130 /// however code extractor won't validate whether extraction is legal.
131 /// Any new allocations will be placed in the AllocationBlock, unless
132 /// it is null, in which case it will be placed in the entry block of
133 /// the function from which the code is being extracted.
134 /// If ArgsInZeroAddressSpace param is set to true, then the aggregate
135 /// param pointer of the outlined function is declared in zero address
136 /// space.
138 bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr,
139 BranchProbabilityInfo *BPI = nullptr,
140 AssumptionCache *AC = nullptr, bool AllowVarArgs = false,
141 bool AllowAlloca = false,
142 BasicBlock *AllocationBlock = nullptr,
143 std::string Suffix = "", bool ArgsInZeroAddressSpace = false);
144
145 /// Perform the extraction, returning the new function.
146 ///
147 /// Returns zero when called on a CodeExtractor instance where isEligible
148 /// returns false.
150
151 /// Perform the extraction, returning the new function and providing an
152 /// interface to see what was categorized as inputs and outputs.
153 ///
154 /// \param CEAC - Cache to speed up operations for the CodeExtractor when
155 /// hoisting, and extracting lifetime values and assumes.
156 /// \param Inputs [out] - filled with values marked as inputs to the
157 /// newly outlined function.
158 /// \param Outputs [out] - filled with values marked as outputs to the
159 /// newly outlined function.
160 /// \returns zero when called on a CodeExtractor instance where isEligible
161 /// returns false.
163 ValueSet &Inputs, ValueSet &Outputs);
164
165 /// Verify that assumption cache isn't stale after a region is extracted.
166 /// Returns true when verifier finds errors. AssumptionCache is passed as
167 /// parameter to make this function stateless.
168 static bool verifyAssumptionCache(const Function &OldFunc,
169 const Function &NewFunc,
170 AssumptionCache *AC);
171
172 /// Test whether this code extractor is eligible.
173 ///
174 /// Based on the blocks used when constructing the code extractor,
175 /// determine whether it is eligible for extraction.
176 ///
177 /// Checks that varargs handling (with vastart and vaend) is only done in
178 /// the outlined blocks.
179 bool isEligible() const;
180
181 /// Compute the set of input values and output values for the code.
182 ///
183 /// These can be used either when performing the extraction or to evaluate
184 /// the expected size of a call to the extracted function. Note that this
185 /// work cannot be cached between the two as once we decide to extract
186 /// a code sequence, that sequence is modified, including changing these
187 /// sets, before extraction occurs. These modifications won't have any
188 /// significant impact on the cost however.
189 void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,
190 const ValueSet &Allocas) const;
191
192 /// Check if life time marker nodes can be hoisted/sunk into the outline
193 /// region.
194 ///
195 /// Returns true if it is safe to do the code motion.
196 bool
198 Instruction *AllocaAddr) const;
199
200 /// Find the set of allocas whose life ranges are contained within the
201 /// outlined region.
202 ///
203 /// Allocas which have life_time markers contained in the outlined region
204 /// should be pushed to the outlined function. The address bitcasts that
205 /// are used by the lifetime markers are also candidates for shrink-
206 /// wrapping. The instructions that need to be sunk are collected in
207 /// 'Allocas'.
209 ValueSet &SinkCands, ValueSet &HoistCands,
210 BasicBlock *&ExitBlock) const;
211
212 /// Find or create a block within the outline region for placing hoisted
213 /// code.
214 ///
215 /// CommonExitBlock is block outside the outline region. It is the common
216 /// successor of blocks inside the region. If there exists a single block
217 /// inside the region that is the predecessor of CommonExitBlock, that block
218 /// will be returned. Otherwise CommonExitBlock will be split and the
219 /// original block will be added to the outline region.
221
222 /// Exclude a value from aggregate argument passing when extracting a code
223 /// region, passing it instead as a scalar.
225
226 private:
227 struct LifetimeMarkerInfo {
228 bool SinkLifeStart = false;
229 bool HoistLifeEnd = false;
230 Instruction *LifeStart = nullptr;
231 Instruction *LifeEnd = nullptr;
232 };
233
234 ValueSet ExcludeArgsFromAggregate;
235
236 LifetimeMarkerInfo
237 getLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC,
238 Instruction *Addr, BasicBlock *ExitBlock) const;
239
240 void severSplitPHINodesOfEntry(BasicBlock *&Header);
241 void severSplitPHINodesOfExits(const SetVector<BasicBlock *> &Exits);
242 void splitReturnBlocks();
243
244 Function *constructFunction(const ValueSet &inputs,
245 const ValueSet &outputs,
246 BasicBlock *header,
247 BasicBlock *newRootNode, BasicBlock *newHeader,
248 Function *oldFunction, Module *M);
249
250 void moveCodeToFunction(Function *newFunction);
251
252 void calculateNewCallTerminatorWeights(
253 BasicBlock *CodeReplacer,
256
257 CallInst *emitCallAndSwitchStatement(Function *newFunction,
258 BasicBlock *newHeader,
259 ValueSet &inputs, ValueSet &outputs);
260 };
261
262} // end namespace llvm
263
264#endif // LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H
RelocType Type
Definition: COFFYAML.cpp:391
This file defines the DenseMap class.
uint64_t Addr
#define F(x, y, z)
Definition: MD5.cpp:55
Machine Check Debug Module
This file implements a set that has insertion order iteration characteristics.
an instruction to allocate memory on the stack
Definition: Instructions.h:61
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Analysis providing branch probability information.
This class represents a function call, abstracting a target machine's calling convention.
A cache for the CodeExtractor analysis.
Definition: CodeExtractor.h:45
ArrayRef< AllocaInst * > getAllocas() const
Get the allocas in the function at the time the analysis was created.
Definition: CodeExtractor.h:64
bool doesBlockContainClobberOfAddr(BasicBlock &BB, AllocaInst *Addr) const
Check whether BB contains an instruction thought to load from, store to, or otherwise clobber the all...
Utility class for extracting code into a new function.
Definition: CodeExtractor.h:84
BasicBlock * findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock)
Find or create a block within the outline region for placing hoisted code.
void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs, const ValueSet &Allocas) const
Compute the set of input values and output values for the code.
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.
Function * extractCodeRegion(const CodeExtractorAnalysisCache &CEAC)
Perform the extraction, returning the new function.
static bool verifyAssumptionCache(const Function &OldFunc, const Function &NewFunc, AssumptionCache *AC)
Verify that assumption cache isn't stale after a region is extracted.
bool isEligible() const
Test whether this code extractor is eligible.
void excludeArgFromAggregate(Value *Arg)
Exclude a value from aggregate argument passing when extracting a code region, passing it instead as ...
bool isLegalToShrinkwrapLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC, Instruction *AllocaAddr) const
Check if life time marker nodes can be hoisted/sunk into the outline region.
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
LLVM Value Representation.
Definition: Value.h:74
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18