199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth//===-- Transform/Utils/CodeExtractor.h - Code extraction util --*- C++ -*-===// 299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth// 399650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth// The LLVM Compiler Infrastructure 499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth// 599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth// This file is distributed under the University of Illinois Open Source 699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth// License. See LICENSE.TXT for details. 799650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth// 899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth//===----------------------------------------------------------------------===// 999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth// 1099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth// A utility to support extracting code from one function into its own 1199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth// stand-alone function. 1299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth// 1399650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth//===----------------------------------------------------------------------===// 1499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 1599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth#ifndef LLVM_TRANSFORMS_UTILS_CODE_EXTRACTOR_H 1699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth#define LLVM_TRANSFORMS_UTILS_CODE_EXTRACTOR_H 1799650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 1899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth#include "llvm/ADT/ArrayRef.h" 1999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth#include "llvm/ADT/SetVector.h" 2099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 2199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruthnamespace llvm { 2299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth class BasicBlock; 2399650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth class DominatorTree; 2499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth class Function; 2599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth class Loop; 2699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth class Module; 2730ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth class RegionNode; 2899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth class Type; 2999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth class Value; 3099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 3199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// \brief Utility class for extracting code into a new function. 3299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// 3399650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// This utility provides a simple interface for extracting some sequence of 3499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// code into its own function, replacing it with a call to that function. It 3599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// also provides various methods to query about the nature and result of 3699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// such a transformation. 3799650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// 3899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// The rough algorithm used is: 3999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// 1) Find both the inputs and outputs for the extracted region. 4099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// 2) Pass the inputs as arguments, remapping them within the extracted 4199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// function to arguments. 4299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// 3) Add allocas for any scalar outputs, adding all of the outputs' allocas 4399650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// as arguments, and inserting stores to the arguments for any scalars. 4499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth class CodeExtractor { 4599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth typedef SetVector<Value *> ValueSet; 4699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 4799650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth // Various bits of state computed on construction. 4899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth DominatorTree *const DT; 4999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth const bool AggregateArgs; 5099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 5199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth // Bits of intermediate state computed at various phases of extraction. 5299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth SetVector<BasicBlock *> Blocks; 5399650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth unsigned NumExitBlocks; 5499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth Type *RetTy; 5599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 5699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth public: 5799650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// \brief Create a code extractor for a single basic block. 5899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// 5999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// In this formation, we don't require a dominator tree. The given basic 6099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// block is set up for extraction. 6199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth CodeExtractor(BasicBlock *BB, bool AggregateArgs = false); 6299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 6399650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// \brief Create a code extractor for a sequence of blocks. 6499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// 6599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// Given a sequence of basic blocks where the first block in the sequence 6699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// dominates the rest, prepare a code extractor object for pulling this 6799650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// sequence out into its new function. When a DominatorTree is also given, 6899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// extra checking and transformations are enabled. 6999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = 0, 7099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth bool AggregateArgs = false); 7199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 7299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// \brief Create a code extractor for a loop body. 7399650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// 7499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// Behaves just like the generic code sequence constructor, but uses the 7599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// block sequence of the loop. 7699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false); 7799650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 7830ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth /// \brief Create a code extractor for a region node. 7930ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth /// 8030ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth /// Behaves just like the generic code sequence constructor, but uses the 8130ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth /// block sequence of the region node passed in. 8230ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth CodeExtractor(DominatorTree &DT, const RegionNode &RN, 8330ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth bool AggregateArgs = false); 8430ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth 8599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// \brief Perform the extraction, returning the new function. 8699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// 8799650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// Returns zero when called on a CodeExtractor instance where isEligible 8899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// returns false. 8999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth Function *extractCodeRegion(); 9099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 9199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// \brief Test whether this code extractor is eligible. 9299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// 9399650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// Based on the blocks used when constructing the code extractor, 9499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth /// determine whether it is eligible for extraction. 9522b291abd855ccf013381a9d6939d918181b0e0eEric Christopher bool isEligible() const { return !Blocks.empty(); } 9690cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth 9790cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth /// \brief Compute the set of input values and output values for the code. 9890cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth /// 9990cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth /// These can be used either when performing the extraction or to evaluate 10090cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth /// the expected size of a call to the extracted function. Note that this 10190cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth /// work cannot be cached between the two as once we decide to extract 10290cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth /// a code sequence, that sequence is modified, including changing these 10390cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth /// sets, before extraction occurs. These modifications won't have any 10490cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth /// significant impact on the cost however. 10590cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs) const; 10699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 10799650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth private: 10899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth void severSplitPHINodes(BasicBlock *&Header); 10999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth void splitReturnBlocks(); 11099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 11199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth Function *constructFunction(const ValueSet &inputs, 11299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth const ValueSet &outputs, 11399650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth BasicBlock *header, 11499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth BasicBlock *newRootNode, BasicBlock *newHeader, 11599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth Function *oldFunction, Module *M); 11699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 11799650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth void moveCodeToFunction(Function *newFunction); 11899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 11999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth void emitCallAndSwitchStatement(Function *newFunction, 12099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth BasicBlock *newHeader, 12199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth ValueSet &inputs, 12299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth ValueSet &outputs); 12399650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 12499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth }; 12599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth} 12699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 12799650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth#endif 128