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_CODE_EXTRACTOR_H
16#define LLVM_TRANSFORMS_UTILS_CODE_EXTRACTOR_H
17
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/SetVector.h"
20
21namespace llvm {
22  class BasicBlock;
23  class DominatorTree;
24  class Function;
25  class Loop;
26  class Module;
27  class RegionNode;
28  class Type;
29  class Value;
30
31  /// \brief Utility class for extracting code into a new function.
32  ///
33  /// This utility provides a simple interface for extracting some sequence of
34  /// code into its own function, replacing it with a call to that function. It
35  /// also provides various methods to query about the nature and result of
36  /// such a transformation.
37  ///
38  /// The rough algorithm used is:
39  /// 1) Find both the inputs and outputs for the extracted region.
40  /// 2) Pass the inputs as arguments, remapping them within the extracted
41  ///    function to arguments.
42  /// 3) Add allocas for any scalar outputs, adding all of the outputs' allocas
43  ///    as arguments, and inserting stores to the arguments for any scalars.
44  class CodeExtractor {
45    typedef SetVector<Value *> ValueSet;
46
47    // Various bits of state computed on construction.
48    DominatorTree *const DT;
49    const bool AggregateArgs;
50
51    // Bits of intermediate state computed at various phases of extraction.
52    SetVector<BasicBlock *> Blocks;
53    unsigned NumExitBlocks;
54    Type *RetTy;
55
56  public:
57    /// \brief Create a code extractor for a single basic block.
58    ///
59    /// In this formation, we don't require a dominator tree. The given basic
60    /// block is set up for extraction.
61    CodeExtractor(BasicBlock *BB, bool AggregateArgs = false);
62
63    /// \brief Create a code extractor for a sequence of blocks.
64    ///
65    /// Given a sequence of basic blocks where the first block in the sequence
66    /// dominates the rest, prepare a code extractor object for pulling this
67    /// sequence out into its new function. When a DominatorTree is also given,
68    /// extra checking and transformations are enabled.
69    CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = nullptr,
70                  bool AggregateArgs = false);
71
72    /// \brief Create a code extractor for a loop body.
73    ///
74    /// Behaves just like the generic code sequence constructor, but uses the
75    /// block sequence of the loop.
76    CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false);
77
78    /// \brief Create a code extractor for a region node.
79    ///
80    /// Behaves just like the generic code sequence constructor, but uses the
81    /// block sequence of the region node passed in.
82    CodeExtractor(DominatorTree &DT, const RegionNode &RN,
83                  bool AggregateArgs = false);
84
85    /// \brief Perform the extraction, returning the new function.
86    ///
87    /// Returns zero when called on a CodeExtractor instance where isEligible
88    /// returns false.
89    Function *extractCodeRegion();
90
91    /// \brief Test whether this code extractor is eligible.
92    ///
93    /// Based on the blocks used when constructing the code extractor,
94    /// determine whether it is eligible for extraction.
95    bool isEligible() const { return !Blocks.empty(); }
96
97    /// \brief Compute the set of input values and output values for the code.
98    ///
99    /// These can be used either when performing the extraction or to evaluate
100    /// the expected size of a call to the extracted function. Note that this
101    /// work cannot be cached between the two as once we decide to extract
102    /// a code sequence, that sequence is modified, including changing these
103    /// sets, before extraction occurs. These modifications won't have any
104    /// significant impact on the cost however.
105    void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs) const;
106
107  private:
108    void severSplitPHINodes(BasicBlock *&Header);
109    void splitReturnBlocks();
110
111    Function *constructFunction(const ValueSet &inputs,
112                                const ValueSet &outputs,
113                                BasicBlock *header,
114                                BasicBlock *newRootNode, BasicBlock *newHeader,
115                                Function *oldFunction, Module *M);
116
117    void moveCodeToFunction(Function *newFunction);
118
119    void emitCallAndSwitchStatement(Function *newFunction,
120                                    BasicBlock *newHeader,
121                                    ValueSet &inputs,
122                                    ValueSet &outputs);
123  };
124}
125
126#endif
127