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/SetVector.h"
20 
21 namespace 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.
isEligible()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