LLVM 18.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 Loop;
36class Module;
37class Type;
38class 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
59public:
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.
87
88 // Various bits of state computed on construction.
89 DominatorTree *const DT;
90 const bool AggregateArgs;
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.
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'.
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,
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
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:58
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:56
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:46
ArrayRef< AllocaInst * > getAllocas() const
Get the allocas in the function at the time the analysis was created.
Definition: CodeExtractor.h:65
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:85
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:166
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:47
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:345
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
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