Line data Source code
1 : //===- Transform/Utils/CodeExtractor.h - Code extraction util ---*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // A utility to support extracting code from one function into its own
11 : // stand-alone function.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #ifndef LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H
16 : #define LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H
17 :
18 : #include "llvm/ADT/ArrayRef.h"
19 : #include "llvm/ADT/DenseMap.h"
20 : #include "llvm/ADT/SetVector.h"
21 : #include <limits>
22 :
23 : namespace llvm {
24 :
25 : class BasicBlock;
26 : class BlockFrequency;
27 : class BlockFrequencyInfo;
28 : class BranchProbabilityInfo;
29 : class DominatorTree;
30 : class Function;
31 : class Instruction;
32 : class Loop;
33 : class Module;
34 : class Type;
35 : class Value;
36 :
37 : /// Utility class for extracting code into a new function.
38 : ///
39 : /// This utility provides a simple interface for extracting some sequence of
40 : /// code into its own function, replacing it with a call to that function. It
41 : /// also provides various methods to query about the nature and result of
42 : /// such a transformation.
43 : ///
44 : /// The rough algorithm used is:
45 : /// 1) Find both the inputs and outputs for the extracted region.
46 : /// 2) Pass the inputs as arguments, remapping them within the extracted
47 : /// function to arguments.
48 : /// 3) Add allocas for any scalar outputs, adding all of the outputs' allocas
49 : /// as arguments, and inserting stores to the arguments for any scalars.
50 113 : class CodeExtractor {
51 : using ValueSet = SetVector<Value *>;
52 :
53 : // Various bits of state computed on construction.
54 : DominatorTree *const DT;
55 : const bool AggregateArgs;
56 : BlockFrequencyInfo *BFI;
57 : BranchProbabilityInfo *BPI;
58 :
59 : // If true, varargs functions can be extracted.
60 : bool AllowVarArgs;
61 :
62 : // Bits of intermediate state computed at various phases of extraction.
63 : SetVector<BasicBlock *> Blocks;
64 : unsigned NumExitBlocks = std::numeric_limits<unsigned>::max();
65 : Type *RetTy;
66 :
67 : public:
68 : /// Create a code extractor for a sequence of blocks.
69 : ///
70 : /// Given a sequence of basic blocks where the first block in the sequence
71 : /// dominates the rest, prepare a code extractor object for pulling this
72 : /// sequence out into its new function. When a DominatorTree is also given,
73 : /// extra checking and transformations are enabled. If AllowVarArgs is true,
74 : /// vararg functions can be extracted. This is safe, if all vararg handling
75 : /// code is extracted, including vastart. If AllowAlloca is true, then
76 : /// extraction of blocks containing alloca instructions would be possible,
77 : /// however code extractor won't validate whether extraction is legal.
78 : CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = nullptr,
79 : bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr,
80 : BranchProbabilityInfo *BPI = nullptr,
81 : bool AllowVarArgs = false, bool AllowAlloca = false);
82 :
83 : /// Create a code extractor for a loop body.
84 : ///
85 : /// Behaves just like the generic code sequence constructor, but uses the
86 : /// block sequence of the loop.
87 : CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false,
88 : BlockFrequencyInfo *BFI = nullptr,
89 : BranchProbabilityInfo *BPI = nullptr);
90 :
91 : /// Perform the extraction, returning the new function.
92 : ///
93 : /// Returns zero when called on a CodeExtractor instance where isEligible
94 : /// returns false.
95 : Function *extractCodeRegion();
96 :
97 : /// Test whether this code extractor is eligible.
98 : ///
99 : /// Based on the blocks used when constructing the code extractor,
100 : /// determine whether it is eligible for extraction.
101 1 : bool isEligible() const { return !Blocks.empty(); }
102 :
103 : /// Compute the set of input values and output values for the code.
104 : ///
105 : /// These can be used either when performing the extraction or to evaluate
106 : /// the expected size of a call to the extracted function. Note that this
107 : /// work cannot be cached between the two as once we decide to extract
108 : /// a code sequence, that sequence is modified, including changing these
109 : /// sets, before extraction occurs. These modifications won't have any
110 : /// significant impact on the cost however.
111 : void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,
112 : const ValueSet &Allocas) const;
113 :
114 : /// Check if life time marker nodes can be hoisted/sunk into the outline
115 : /// region.
116 : ///
117 : /// Returns true if it is safe to do the code motion.
118 : bool isLegalToShrinkwrapLifetimeMarkers(Instruction *AllocaAddr) const;
119 :
120 : /// Find the set of allocas whose life ranges are contained within the
121 : /// outlined region.
122 : ///
123 : /// Allocas which have life_time markers contained in the outlined region
124 : /// should be pushed to the outlined function. The address bitcasts that
125 : /// are used by the lifetime markers are also candidates for shrink-
126 : /// wrapping. The instructions that need to be sunk are collected in
127 : /// 'Allocas'.
128 : void findAllocas(ValueSet &SinkCands, ValueSet &HoistCands,
129 : BasicBlock *&ExitBlock) const;
130 :
131 : /// Find or create a block within the outline region for placing hoisted
132 : /// code.
133 : ///
134 : /// CommonExitBlock is block outside the outline region. It is the common
135 : /// successor of blocks inside the region. If there exists a single block
136 : /// inside the region that is the predecessor of CommonExitBlock, that block
137 : /// will be returned. Otherwise CommonExitBlock will be split and the
138 : /// original block will be added to the outline region.
139 : BasicBlock *findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock);
140 :
141 : private:
142 : void severSplitPHINodes(BasicBlock *&Header);
143 : void splitReturnBlocks();
144 :
145 : Function *constructFunction(const ValueSet &inputs,
146 : const ValueSet &outputs,
147 : BasicBlock *header,
148 : BasicBlock *newRootNode, BasicBlock *newHeader,
149 : Function *oldFunction, Module *M);
150 :
151 : void moveCodeToFunction(Function *newFunction);
152 :
153 : void calculateNewCallTerminatorWeights(
154 : BasicBlock *CodeReplacer,
155 : DenseMap<BasicBlock *, BlockFrequency> &ExitWeights,
156 : BranchProbabilityInfo *BPI);
157 :
158 : void emitCallAndSwitchStatement(Function *newFunction,
159 : BasicBlock *newHeader,
160 : ValueSet &inputs,
161 : ValueSet &outputs);
162 : };
163 :
164 : } // end namespace llvm
165 :
166 : #endif // LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H
|
