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