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