LLVM  6.0.0svn
CodeExtractor.h
Go to the documentation of this file.
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  /// \brief 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  class CodeExtractor {
52 
53  // Various bits of state computed on construction.
54  DominatorTree *const DT;
55  const bool AggregateArgs;
56  BlockFrequencyInfo *BFI;
58 
59  // If true, varargs functions can be extracted.
60  bool AllowVarArgs;
61 
62  // Bits of intermediate state computed at various phases of extraction.
64  unsigned NumExitBlocks = std::numeric_limits<unsigned>::max();
65  Type *RetTy;
66 
67  public:
68  /// \brief 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.
77  bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr,
78  BranchProbabilityInfo *BPI = nullptr,
79  bool AllowVarArgs = false);
80 
81  /// \brief Create a code extractor for a loop body.
82  ///
83  /// Behaves just like the generic code sequence constructor, but uses the
84  /// block sequence of the loop.
85  CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false,
86  BlockFrequencyInfo *BFI = nullptr,
87  BranchProbabilityInfo *BPI = nullptr);
88 
89  /// \brief Check to see if a block is valid for extraction.
90  ///
91  /// Blocks containing EHPads, allocas and invokes are not valid. If
92  /// AllowVarArgs is true, blocks with vastart can be extracted. This is
93  /// safe, if all vararg handling code is extracted, including vastart.
94  static bool isBlockValidForExtraction(const BasicBlock &BB,
95  bool AllowVarArgs);
96 
97  /// \brief Perform the extraction, returning the new function.
98  ///
99  /// Returns zero when called on a CodeExtractor instance where isEligible
100  /// returns false.
102 
103  /// \brief Test whether this code extractor is eligible.
104  ///
105  /// Based on the blocks used when constructing the code extractor,
106  /// determine whether it is eligible for extraction.
107  bool isEligible() const { return !Blocks.empty(); }
108 
109  /// \brief Compute the set of input values and output values for the code.
110  ///
111  /// These can be used either when performing the extraction or to evaluate
112  /// the expected size of a call to the extracted function. Note that this
113  /// work cannot be cached between the two as once we decide to extract
114  /// a code sequence, that sequence is modified, including changing these
115  /// sets, before extraction occurs. These modifications won't have any
116  /// significant impact on the cost however.
117  void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,
118  const ValueSet &Allocas) const;
119 
120  /// Check if life time marker nodes can be hoisted/sunk into the outline
121  /// region.
122  ///
123  /// Returns true if it is safe to do the code motion.
124  bool isLegalToShrinkwrapLifetimeMarkers(Instruction *AllocaAddr) const;
125 
126  /// Find the set of allocas whose life ranges are contained within the
127  /// outlined region.
128  ///
129  /// Allocas which have life_time markers contained in the outlined region
130  /// should be pushed to the outlined function. The address bitcasts that
131  /// are used by the lifetime markers are also candidates for shrink-
132  /// wrapping. The instructions that need to be sunk are collected in
133  /// 'Allocas'.
134  void findAllocas(ValueSet &SinkCands, ValueSet &HoistCands,
135  BasicBlock *&ExitBlock) const;
136 
137  /// Find or create a block within the outline region for placing hoisted
138  /// code.
139  ///
140  /// CommonExitBlock is block outside the outline region. It is the common
141  /// successor of blocks inside the region. If there exists a single block
142  /// inside the region that is the predecessor of CommonExitBlock, that block
143  /// will be returned. Otherwise CommonExitBlock will be split and the
144  /// original block will be added to the outline region.
146 
147  private:
148  void severSplitPHINodes(BasicBlock *&Header);
149  void splitReturnBlocks();
150 
151  Function *constructFunction(const ValueSet &inputs,
152  const ValueSet &outputs,
153  BasicBlock *header,
154  BasicBlock *newRootNode, BasicBlock *newHeader,
155  Function *oldFunction, Module *M);
156 
157  void moveCodeToFunction(Function *newFunction);
158 
159  void calculateNewCallTerminatorWeights(
160  BasicBlock *CodeReplacer,
162  BranchProbabilityInfo *BPI);
163 
164  void emitCallAndSwitchStatement(Function *newFunction,
165  BasicBlock *newHeader,
166  ValueSet &inputs,
167  ValueSet &outputs);
168  };
169 
170 } // end namespace llvm
171 
172 #endif // LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H
Utility class for extracting code into a new function.
Definition: CodeExtractor.h:50
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Various leaf nodes.
Definition: ISDOpcodes.h:60
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs, const ValueSet &Allocas) const
Compute the set of input values and output values for the code.
CodeExtractor(ArrayRef< BasicBlock *> BBs, DominatorTree *DT=nullptr, bool AggregateArgs=false, BlockFrequencyInfo *BFI=nullptr, BranchProbabilityInfo *BPI=nullptr, bool AllowVarArgs=false)
Create a code extractor for a sequence of blocks.
Function * extractCodeRegion()
Perform the extraction, returning the new function.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
static bool isBlockValidForExtraction(const BasicBlock &BB, bool AllowVarArgs)
Check to see if a block is valid for extraction.
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:439
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:73
A vector that has set insertion semantics.
Definition: SetVector.h:41
void findAllocas(ValueSet &SinkCands, ValueSet &HoistCands, BasicBlock *&ExitBlock) const
Find the set of allocas whose life ranges are contained within the outlined region.