Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Transforms/Utils/CodeExtractor.h
Line
Count
Source
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 {
53
    using ValueSet = SetVector<Value *>;
54
55
    // Various bits of state computed on construction.
56
    DominatorTree *const DT;
57
    const bool AggregateArgs;
58
    BlockFrequencyInfo *BFI;
59
    BranchProbabilityInfo *BPI;
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.
66
    SetVector<BasicBlock *> Blocks;
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.
86
    CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = nullptr,
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.
107
    Function *extractCodeRegion();
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
168
    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.
151
    BasicBlock *findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock);
152
153
  private:
154
    struct LifetimeMarkerInfo {
155
      bool SinkLifeStart = false;
156
      bool HoistLifeEnd = false;
157
      Instruction *LifeStart = nullptr;
158
      Instruction *LifeEnd = nullptr;
159
    };
160
161
    LifetimeMarkerInfo getLifetimeMarkers(Instruction *Addr,
162
                                          BasicBlock *ExitBlock) const;
163
164
    void severSplitPHINodesOfEntry(BasicBlock *&Header);
165
    void severSplitPHINodesOfExits(const SmallPtrSetImpl<BasicBlock *> &Exits);
166
    void splitReturnBlocks();
167
168
    Function *constructFunction(const ValueSet &inputs,
169
                                const ValueSet &outputs,
170
                                BasicBlock *header,
171
                                BasicBlock *newRootNode, BasicBlock *newHeader,
172
                                Function *oldFunction, Module *M);
173
174
    void moveCodeToFunction(Function *newFunction);
175
176
    void calculateNewCallTerminatorWeights(
177
        BasicBlock *CodeReplacer,
178
        DenseMap<BasicBlock *, BlockFrequency> &ExitWeights,
179
        BranchProbabilityInfo *BPI);
180
181
    CallInst *emitCallAndSwitchStatement(Function *newFunction,
182
                                         BasicBlock *newHeader,
183
                                         ValueSet &inputs, ValueSet &outputs);
184
  };
185
186
} // end namespace llvm
187
188
#endif // LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H