LLVM  13.0.0git
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 //===----------------------------------------------------------------------===//
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>
23 namespace llvm {
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;
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.
50  /// Base memory addresses of load/store instructions, grouped by block.
53  /// Blocks which contain instructions which may have unknown side-effects
54  /// on memory.
55  DenseSet<BasicBlock *> SideEffectingBlocks;
57  void findSideEffectInfoForBlock(BasicBlock &BB);
59 public:
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; }
67  /// Check whether \p BB contains an instruction thought to load from, store
68  /// to, or otherwise clobber the alloca \p Addr.
70 };
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 {
88  // Various bits of state computed on construction.
89  DominatorTree *const DT;
90  const bool AggregateArgs;
91  BlockFrequencyInfo *BFI;
93  AssumptionCache *AC;
95  // If true, varargs functions can be extracted.
96  bool AllowVarArgs;
98  // Bits of intermediate state computed at various phases of extraction.
100  unsigned NumExitBlocks = std::numeric_limits<unsigned>::max();
101  Type *RetTy;
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;
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 = "");
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 = "");
136  /// Perform the extraction, returning the new function.
137  ///
138  /// Returns zero when called on a CodeExtractor instance where isEligible
139  /// returns false.
142  /// Verify that assumption cache isn't stale after a region is extracted.
143  /// Returns true when verifier finds errors. AssumptionCache is passed as
144  /// parameter to make this function stateless.
145  static bool verifyAssumptionCache(const Function &OldFunc,
146  const Function &NewFunc,
147  AssumptionCache *AC);
149  /// Test whether this code extractor is eligible.
150  ///
151  /// Based on the blocks used when constructing the code extractor,
152  /// determine whether it is eligible for extraction.
153  ///
154  /// Checks that varargs handling (with vastart and vaend) is only done in
155  /// the outlined blocks.
156  bool isEligible() const;
158  /// Compute the set of input values and output values for the code.
159  ///
160  /// These can be used either when performing the extraction or to evaluate
161  /// the expected size of a call to the extracted function. Note that this
162  /// work cannot be cached between the two as once we decide to extract
163  /// a code sequence, that sequence is modified, including changing these
164  /// sets, before extraction occurs. These modifications won't have any
165  /// significant impact on the cost however.
166  void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,
167  const ValueSet &Allocas) const;
169  /// Check if life time marker nodes can be hoisted/sunk into the outline
170  /// region.
171  ///
172  /// Returns true if it is safe to do the code motion.
173  bool
175  Instruction *AllocaAddr) const;
177  /// Find the set of allocas whose life ranges are contained within the
178  /// outlined region.
179  ///
180  /// Allocas which have life_time markers contained in the outlined region
181  /// should be pushed to the outlined function. The address bitcasts that
182  /// are used by the lifetime markers are also candidates for shrink-
183  /// wrapping. The instructions that need to be sunk are collected in
184  /// 'Allocas'.
185  void findAllocas(const CodeExtractorAnalysisCache &CEAC,
186  ValueSet &SinkCands, ValueSet &HoistCands,
187  BasicBlock *&ExitBlock) const;
189  /// Find or create a block within the outline region for placing hoisted
190  /// code.
191  ///
192  /// CommonExitBlock is block outside the outline region. It is the common
193  /// successor of blocks inside the region. If there exists a single block
194  /// inside the region that is the predecessor of CommonExitBlock, that block
195  /// will be returned. Otherwise CommonExitBlock will be split and the
196  /// original block will be added to the outline region.
199  private:
200  struct LifetimeMarkerInfo {
201  bool SinkLifeStart = false;
202  bool HoistLifeEnd = false;
203  Instruction *LifeStart = nullptr;
204  Instruction *LifeEnd = nullptr;
205  };
207  LifetimeMarkerInfo
208  getLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC,
209  Instruction *Addr, BasicBlock *ExitBlock) const;
211  void severSplitPHINodesOfEntry(BasicBlock *&Header);
212  void severSplitPHINodesOfExits(const SmallPtrSetImpl<BasicBlock *> &Exits);
213  void splitReturnBlocks();
215  Function *constructFunction(const ValueSet &inputs,
216  const ValueSet &outputs,
217  BasicBlock *header,
218  BasicBlock *newRootNode, BasicBlock *newHeader,
219  Function *oldFunction, Module *M);
221  void moveCodeToFunction(Function *newFunction);
223  void calculateNewCallTerminatorWeights(
224  BasicBlock *CodeReplacer,
226  BranchProbabilityInfo *BPI);
228  CallInst *emitCallAndSwitchStatement(Function *newFunction,
229  BasicBlock *newHeader,
230  ValueSet &inputs, ValueSet &outputs);
231  };
233 } // end namespace llvm
Definition: AllocatorList.h:23
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
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:364
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
Definition: Function.h:61
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
Function * extractCodeRegion(const CodeExtractorAnalysisCache &CEAC)
Perform the extraction, returning the new function.
Definition: CodeExtractor.cpp:1570
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
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, std::string Suffix="")
Create a code extractor for a sequence of blocks.
Definition: CodeExtractor.cpp:247
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
ArrayRef< AllocaInst * > getAllocas() const
Get the allocas in the function at the time the analysis was created.
Definition: CodeExtractor.h:65
#define F(x, y, z)
Definition: MD5.cpp:56
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
CodeExtractorAnalysisCache(Function &F)
Definition: CodeExtractor.cpp:311
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Definition: BlockFrequencyInfo.h:37
Analysis providing branch probability information.
Definition: BranchProbabilityInfo.h:115
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
Definition: Instruction.h:45
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
uint64_t Addr
Definition: ELFObjHandler.cpp:80
Definition: DenseMap.h:714
@ Type
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:64
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
Utility class for extracting code into a new function.
Definition: CodeExtractor.h:85
Machine Check Debug Module
Definition: MachineCheckDebugify.cpp:122
BasicBlock * findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock)
Find or create a block within the outline region for placing hoisted code.
Definition: CodeExtractor.cpp:388
Definition: TargetFrameLowering.h:27
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:1782
A cache for the CodeExtractor analysis.
Definition: CodeExtractor.h:46
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
bool isEligible() const
Test whether this code extractor is eligible.
Definition: CodeExtractor.cpp:619
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1478
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
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:374
an instruction to allocate memory on the stack
Definition: Instructions.h:61
llvm::SetVector< Value * >
@ Function