LLVM  9.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 BasicBlock;
26 class BlockFrequency;
27 class BlockFrequencyInfo;
28 class BranchProbabilityInfo;
29 class AssumptionCache;
30 class CallInst;
31 class DominatorTree;
32 class Function;
33 class Instruction;
34 class Loop;
35 class Module;
36 class Type;
37 class Value;
38 
39  /// Utility class for extracting code into a new function.
40  ///
41  /// This utility provides a simple interface for extracting some sequence of
42  /// code into its own function, replacing it with a call to that function. It
43  /// also provides various methods to query about the nature and result of
44  /// such a transformation.
45  ///
46  /// The rough algorithm used is:
47  /// 1) Find both the inputs and outputs for the extracted region.
48  /// 2) Pass the inputs as arguments, remapping them within the extracted
49  /// function to arguments.
50  /// 3) Add allocas for any scalar outputs, adding all of the outputs' allocas
51  /// as arguments, and inserting stores to the arguments for any scalars.
52  class CodeExtractor {
54 
55  // Various bits of state computed on construction.
56  DominatorTree *const DT;
57  const bool AggregateArgs;
58  BlockFrequencyInfo *BFI;
60  AssumptionCache *AC;
61 
62  // If true, varargs functions can be extracted.
63  bool AllowVarArgs;
64 
65  // Bits of intermediate state computed at various phases of extraction.
67  unsigned NumExitBlocks = std::numeric_limits<unsigned>::max();
68  Type *RetTy;
69 
70  // Suffix to use when creating extracted function (appended to the original
71  // function name + "."). If empty, the default is to use the entry block
72  // label, if non-empty, otherwise "extracted".
73  std::string Suffix;
74 
75  public:
76  /// Create a code extractor for a sequence of blocks.
77  ///
78  /// Given a sequence of basic blocks where the first block in the sequence
79  /// dominates the rest, prepare a code extractor object for pulling this
80  /// sequence out into its new function. When a DominatorTree is also given,
81  /// extra checking and transformations are enabled. If AllowVarArgs is true,
82  /// vararg functions can be extracted. This is safe, if all vararg handling
83  /// code is extracted, including vastart. If AllowAlloca is true, then
84  /// extraction of blocks containing alloca instructions would be possible,
85  /// however code extractor won't validate whether extraction is legal.
87  bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr,
88  BranchProbabilityInfo *BPI = nullptr,
89  AssumptionCache *AC = nullptr,
90  bool AllowVarArgs = false, bool AllowAlloca = false,
91  std::string Suffix = "");
92 
93  /// Create a code extractor for a loop body.
94  ///
95  /// Behaves just like the generic code sequence constructor, but uses the
96  /// block sequence of the loop.
97  CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false,
98  BlockFrequencyInfo *BFI = nullptr,
99  BranchProbabilityInfo *BPI = nullptr,
100  AssumptionCache *AC = nullptr,
101  std::string Suffix = "");
102 
103  /// Perform the extraction, returning the new function.
104  ///
105  /// Returns zero when called on a CodeExtractor instance where isEligible
106  /// returns false.
108 
109  /// Test whether this code extractor is eligible.
110  ///
111  /// Based on the blocks used when constructing the code extractor,
112  /// determine whether it is eligible for extraction.
113  bool isEligible() const { return !Blocks.empty(); }
114 
115  /// Compute the set of input values and output values for the code.
116  ///
117  /// These can be used either when performing the extraction or to evaluate
118  /// the expected size of a call to the extracted function. Note that this
119  /// work cannot be cached between the two as once we decide to extract
120  /// a code sequence, that sequence is modified, including changing these
121  /// sets, before extraction occurs. These modifications won't have any
122  /// significant impact on the cost however.
123  void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,
124  const ValueSet &Allocas) const;
125 
126  /// Check if life time marker nodes can be hoisted/sunk into the outline
127  /// region.
128  ///
129  /// Returns true if it is safe to do the code motion.
130  bool isLegalToShrinkwrapLifetimeMarkers(Instruction *AllocaAddr) const;
131 
132  /// Find the set of allocas whose life ranges are contained within the
133  /// outlined region.
134  ///
135  /// Allocas which have life_time markers contained in the outlined region
136  /// should be pushed to the outlined function. The address bitcasts that
137  /// are used by the lifetime markers are also candidates for shrink-
138  /// wrapping. The instructions that need to be sunk are collected in
139  /// 'Allocas'.
140  void findAllocas(ValueSet &SinkCands, ValueSet &HoistCands,
141  BasicBlock *&ExitBlock) const;
142 
143  /// Find or create a block within the outline region for placing hoisted
144  /// code.
145  ///
146  /// CommonExitBlock is block outside the outline region. It is the common
147  /// successor of blocks inside the region. If there exists a single block
148  /// inside the region that is the predecessor of CommonExitBlock, that block
149  /// will be returned. Otherwise CommonExitBlock will be split and the
150  /// original block will be added to the outline region.
152 
153  private:
154  void severSplitPHINodesOfEntry(BasicBlock *&Header);
155  void severSplitPHINodesOfExits(const SmallPtrSetImpl<BasicBlock *> &Exits);
156  void splitReturnBlocks();
157 
158  Function *constructFunction(const ValueSet &inputs,
159  const ValueSet &outputs,
160  BasicBlock *header,
161  BasicBlock *newRootNode, BasicBlock *newHeader,
162  Function *oldFunction, Module *M);
163 
164  void moveCodeToFunction(Function *newFunction);
165 
166  void calculateNewCallTerminatorWeights(
167  BasicBlock *CodeReplacer,
169  BranchProbabilityInfo *BPI);
170 
171  CallInst *emitCallAndSwitchStatement(Function *newFunction,
172  BasicBlock *newHeader,
173  ValueSet &inputs, ValueSet &outputs);
174  };
175 
176 } // end namespace llvm
177 
178 #endif // LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H
Utility class for extracting code into a new function.
Definition: CodeExtractor.h:52
Type
MessagePack types as defined in the standard, with the exception of Integer being divided into a sign...
Definition: MsgPackReader.h:48
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
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
void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs, const ValueSet &Allocas) const
Compute the set of input values and output values for the code.
This class represents a function call, abstracting a target machine&#39;s calling convention.
A cache of @llvm.assume calls within a function.
Function * extractCodeRegion()
Perform the extraction, returning the new function.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
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:45
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.
bool isEligible() const
Test whether this code extractor is eligible.
bool isLegalToShrinkwrapLifetimeMarkers(Instruction *AllocaAddr) const
Check if life time marker nodes can be hoisted/sunk into the outline region.
BasicBlock * findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock)
Find or create a block within the outline region for placing hoisted code.
Analysis providing branch probability information.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:464
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
A vector that has set insertion semantics.
Definition: SetVector.h:40
void findAllocas(ValueSet &SinkCands, ValueSet &HoistCands, BasicBlock *&ExitBlock) const
Find the set of allocas whose life ranges are contained within the outlined region.