CodeExtractor.h revision 239310
1239310Sdim//===-- Transform/Utils/CodeExtractor.h - Code extraction util --*- C++ -*-===// 2239310Sdim// 3239310Sdim// The LLVM Compiler Infrastructure 4239310Sdim// 5239310Sdim// This file is distributed under the University of Illinois Open Source 6239310Sdim// License. See LICENSE.TXT for details. 7239310Sdim// 8239310Sdim//===----------------------------------------------------------------------===// 9239310Sdim// 10239310Sdim// A utility to support extracting code from one function into its own 11239310Sdim// stand-alone function. 12239310Sdim// 13239310Sdim//===----------------------------------------------------------------------===// 14239310Sdim 15239310Sdim#ifndef LLVM_TRANSFORMS_UTILS_CODE_EXTRACTOR_H 16239310Sdim#define LLVM_TRANSFORMS_UTILS_CODE_EXTRACTOR_H 17239310Sdim 18239310Sdim#include "llvm/ADT/ArrayRef.h" 19239310Sdim#include "llvm/ADT/SetVector.h" 20239310Sdim 21239310Sdimnamespace llvm { 22239310Sdim class BasicBlock; 23239310Sdim class DominatorTree; 24239310Sdim class Function; 25239310Sdim class Loop; 26239310Sdim class Module; 27239310Sdim class RegionNode; 28239310Sdim class Type; 29239310Sdim class Value; 30239310Sdim 31239310Sdim /// \brief Utility class for extracting code into a new function. 32239310Sdim /// 33239310Sdim /// This utility provides a simple interface for extracting some sequence of 34239310Sdim /// code into its own function, replacing it with a call to that function. It 35239310Sdim /// also provides various methods to query about the nature and result of 36239310Sdim /// such a transformation. 37239310Sdim /// 38239310Sdim /// The rough algorithm used is: 39239310Sdim /// 1) Find both the inputs and outputs for the extracted region. 40239310Sdim /// 2) Pass the inputs as arguments, remapping them within the extracted 41239310Sdim /// function to arguments. 42239310Sdim /// 3) Add allocas for any scalar outputs, adding all of the outputs' allocas 43239310Sdim /// as arguments, and inserting stores to the arguments for any scalars. 44239310Sdim class CodeExtractor { 45239310Sdim typedef SetVector<Value *> ValueSet; 46239310Sdim 47239310Sdim // Various bits of state computed on construction. 48239310Sdim DominatorTree *const DT; 49239310Sdim const bool AggregateArgs; 50239310Sdim 51239310Sdim // Bits of intermediate state computed at various phases of extraction. 52239310Sdim SetVector<BasicBlock *> Blocks; 53239310Sdim unsigned NumExitBlocks; 54239310Sdim Type *RetTy; 55239310Sdim 56239310Sdim public: 57239310Sdim /// \brief Create a code extractor for a single basic block. 58239310Sdim /// 59239310Sdim /// In this formation, we don't require a dominator tree. The given basic 60239310Sdim /// block is set up for extraction. 61239310Sdim CodeExtractor(BasicBlock *BB, bool AggregateArgs = false); 62239310Sdim 63239310Sdim /// \brief Create a code extractor for a sequence of blocks. 64239310Sdim /// 65239310Sdim /// Given a sequence of basic blocks where the first block in the sequence 66239310Sdim /// dominates the rest, prepare a code extractor object for pulling this 67239310Sdim /// sequence out into its new function. When a DominatorTree is also given, 68239310Sdim /// extra checking and transformations are enabled. 69239310Sdim CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = 0, 70239310Sdim bool AggregateArgs = false); 71239310Sdim 72239310Sdim /// \brief Create a code extractor for a loop body. 73239310Sdim /// 74239310Sdim /// Behaves just like the generic code sequence constructor, but uses the 75239310Sdim /// block sequence of the loop. 76239310Sdim CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false); 77239310Sdim 78239310Sdim /// \brief Create a code extractor for a region node. 79239310Sdim /// 80239310Sdim /// Behaves just like the generic code sequence constructor, but uses the 81239310Sdim /// block sequence of the region node passed in. 82239310Sdim CodeExtractor(DominatorTree &DT, const RegionNode &RN, 83239310Sdim bool AggregateArgs = false); 84239310Sdim 85239310Sdim /// \brief Perform the extraction, returning the new function. 86239310Sdim /// 87239310Sdim /// Returns zero when called on a CodeExtractor instance where isEligible 88239310Sdim /// returns false. 89239310Sdim Function *extractCodeRegion(); 90239310Sdim 91239310Sdim /// \brief Test whether this code extractor is eligible. 92239310Sdim /// 93239310Sdim /// Based on the blocks used when constructing the code extractor, 94239310Sdim /// determine whether it is eligible for extraction. 95239310Sdim bool isEligible() const { return !Blocks.empty(); } 96239310Sdim 97239310Sdim /// \brief Compute the set of input values and output values for the code. 98239310Sdim /// 99239310Sdim /// These can be used either when performing the extraction or to evaluate 100239310Sdim /// the expected size of a call to the extracted function. Note that this 101239310Sdim /// work cannot be cached between the two as once we decide to extract 102239310Sdim /// a code sequence, that sequence is modified, including changing these 103239310Sdim /// sets, before extraction occurs. These modifications won't have any 104239310Sdim /// significant impact on the cost however. 105239310Sdim void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs) const; 106239310Sdim 107239310Sdim private: 108239310Sdim void severSplitPHINodes(BasicBlock *&Header); 109239310Sdim void splitReturnBlocks(); 110239310Sdim 111239310Sdim Function *constructFunction(const ValueSet &inputs, 112239310Sdim const ValueSet &outputs, 113239310Sdim BasicBlock *header, 114239310Sdim BasicBlock *newRootNode, BasicBlock *newHeader, 115239310Sdim Function *oldFunction, Module *M); 116239310Sdim 117239310Sdim void moveCodeToFunction(Function *newFunction); 118239310Sdim 119239310Sdim void emitCallAndSwitchStatement(Function *newFunction, 120239310Sdim BasicBlock *newHeader, 121239310Sdim ValueSet &inputs, 122239310Sdim ValueSet &outputs); 123239310Sdim 124239310Sdim }; 125239310Sdim} 126239310Sdim 127239310Sdim#endif 128