|
LLVM 20.0.0git
|
#include "llvm/Transforms/IPO/IROutliner.h"#include "llvm/Analysis/IRSimilarityIdentifier.h"#include "llvm/Analysis/OptimizationRemarkEmitter.h"#include "llvm/Analysis/TargetTransformInfo.h"#include "llvm/IR/Attributes.h"#include "llvm/IR/DIBuilder.h"#include "llvm/IR/DebugInfo.h"#include "llvm/IR/DebugInfoMetadata.h"#include "llvm/IR/Dominators.h"#include "llvm/IR/Mangler.h"#include "llvm/IR/PassManager.h"#include "llvm/Support/CommandLine.h"#include "llvm/Transforms/IPO.h"#include <optional>#include <vector>Go to the source code of this file.
Classes | |
| struct | OutlinableGroup |
| The OutlinableGroup holds all the overarching information for outlining a set of regions that are structurally similar to one another, such as the types of the overall function, the output blocks, the sets of stores needed and a list of the different regions. More... | |
Namespaces | |
| namespace | llvm |
| This is an optimization pass for GlobalISel generic memory operations. | |
Macros | |
| #define | DEBUG_TYPE "iroutliner" |
Typedefs | |
| using | ArgLocWithBBCanon = std::pair< unsigned, unsigned > |
| using | CanonList = SmallVector< unsigned, 2 > |
| using | PHINodeData = std::pair< ArgLocWithBBCanon, CanonList > |
Functions | |
| static void | moveBBContents (BasicBlock &SourceBB, BasicBlock &TargetBB) |
Move the contents of SourceBB to before the last instruction of TargetBB. | |
| static void | getSortedConstantKeys (std::vector< Value * > &SortedKeys, DenseMap< Value *, BasicBlock * > &Map) |
A function to sort the keys of Map, which must be a mapping of constant values to basic blocks and return it in SortedKeys. | |
| static void | replaceTargetsFromPHINode (BasicBlock *PHIBlock, BasicBlock *Find, BasicBlock *Replace, DenseSet< BasicBlock * > &Included) |
Rewrite the BranchInsts in the incoming blocks to PHIBlock that are found in Included to branch to BasicBlock Replace if they currently branch to the BasicBlock Find. | |
| static std::optional< bool > | constantMatches (Value *V, unsigned GVN, DenseMap< unsigned, Constant * > &GVNToConstant) |
Find whether V matches the Constants previously found for the GVN. | |
| static Value * | findOutputMapping (const DenseMap< Value *, Value * > OutputMappings, Value *Input) |
Check the OutputMappings structure for value Input, if it exists it has been used as an output for outlining, and has been renamed, and we return the new value, otherwise, we return the same value. | |
| static bool | collectRegionsConstants (OutlinableRegion &Region, DenseMap< unsigned, Constant * > &GVNToConstant, DenseSet< unsigned > &NotSame) |
Find whether Region matches the global value numbering to Constant mapping found so far. | |
| static DISubprogram * | getSubprogramOrNull (OutlinableGroup &Group) |
| Get the subprogram if it exists for one of the outlined regions. | |
| static void | moveFunctionData (Function &Old, Function &New, DenseMap< Value *, BasicBlock * > &NewEnds) |
Move each BasicBlock in Old to New. | |
| static void | findConstants (IRSimilarityCandidate &C, DenseSet< unsigned > &NotSame, std::vector< unsigned > &Inputs) |
| Find the constants that will need to be lifted into arguments as they are not the same in each instance of the region. | |
| static void | mapInputsToGVNs (IRSimilarityCandidate &C, SetVector< Value * > &CurrentInputs, const DenseMap< Value *, Value * > &OutputMappings, std::vector< unsigned > &EndInputNumbers) |
| Find the GVN for the inputs that have been found by the CodeExtractor. | |
| static void | remapExtractedInputs (const ArrayRef< Value * > ArgInputs, const DenseMap< Value *, Value * > &OutputMappings, SetVector< Value * > &RemappedArgInputs) |
Find the original value for the ArgInput values if any one of them was replaced during a previous extraction. | |
| static void | getCodeExtractorArguments (OutlinableRegion &Region, std::vector< unsigned > &InputGVNs, DenseSet< unsigned > &NotSame, DenseMap< Value *, Value * > &OutputMappings, SetVector< Value * > &ArgInputs, SetVector< Value * > &Outputs) |
| Find the input GVNs and the output values for a region of Instructions. | |
| static void | findExtractedInputToOverallInputMapping (OutlinableRegion &Region, std::vector< unsigned > &InputGVNs, SetVector< Value * > &ArgInputs) |
| Look over the inputs and map each input argument to an argument in the overall function for the OutlinableRegions. | |
| static bool | outputHasNonPHI (Value *V, unsigned PHILoc, PHINode &PN, SmallPtrSet< BasicBlock *, 1 > &Exits, DenseSet< BasicBlock * > &BlocksInRegion) |
Check if the V has any uses outside of the region other than PN. | |
| static void | analyzeExitPHIsForOutputUses (BasicBlock *CurrentExitFromRegion, SmallPtrSet< BasicBlock *, 1 > &PotentialExitsFromRegion, DenseSet< BasicBlock * > &RegionBlocks, SetVector< Value * > &Outputs, DenseSet< Value * > &OutputsReplacedByPHINode, DenseSet< Value * > &OutputsWithNonPhiUses) |
Test whether CurrentExitFromRegion contains any PhiNodes that should be considered outputs. | |
| static hash_code | encodePHINodeData (PHINodeData &PND) |
Encode PND as an integer for easy lookup based on the argument location, the parent BasicBlock canonical numbering, and the canonical numbering of the values stored in the PHINode. | |
| static std::optional< unsigned > | getGVNForPHINode (OutlinableRegion &Region, PHINode *PN, DenseSet< BasicBlock * > &Blocks, unsigned AggArgIdx) |
| Create a special GVN for PHINodes that will be used outside of the region. | |
| static void | findExtractedOutputToOverallOutputMapping (Module &M, OutlinableRegion &Region, SetVector< Value * > &Outputs) |
Create a mapping of the output arguments for the Region to the output arguments of the overall outlined function. | |
| CallInst * | replaceCalledFunction (Module &M, OutlinableRegion &Region) |
| Replace the extracted function in the Region with a call to the overall function constructed from the deduplicated similar regions, replacing and remapping the values passed to the extracted function as arguments to the new arguments of the overall function. | |
| static BasicBlock * | findOrCreatePHIBlock (OutlinableGroup &Group, Value *RetVal) |
Find or create a BasicBlock in the outlined function containing PhiBlocks for RetVal. | |
| static Value * | getPassedArgumentInAlreadyOutlinedFunction (const Argument *A, const OutlinableRegion &Region) |
For the function call now representing the Region, find the passed value to that call that represents Argument A at the call location if the call has already been replaced with a call to the overall, aggregate function. | |
| static Value * | getPassedArgumentAndAdjustArgumentLocation (const Argument *A, const OutlinableRegion &Region) |
For the function call now representing the Region, find the passed value to that call that represents Argument A at the call location if the call has only been replaced by the call to the aggregate function. | |
| static void | findCanonNumsForPHI (PHINode *PN, OutlinableRegion &Region, const DenseMap< Value *, Value * > &OutputMappings, SmallVector< std::pair< unsigned, BasicBlock * > > &CanonNums, bool ReplacedWithOutlinedCall=true) |
Find the canonical numbering for the incoming Values into the PHINode PN. | |
| static PHINode * | findOrCreatePHIInBlock (PHINode &PN, OutlinableRegion &Region, BasicBlock *OverallPhiBlock, const DenseMap< Value *, Value * > &OutputMappings, DenseSet< PHINode * > &UsedPHIs) |
Find, or add PHINode PN to the combined PHINode Block OverallPHIBlock in order to condense the number of instructions added to the outlined function. | |
| static void | replaceArgumentUses (OutlinableRegion &Region, DenseMap< Value *, BasicBlock * > &OutputBBs, const DenseMap< Value *, Value * > &OutputMappings, bool FirstFunction=false) |
| void | replaceConstants (OutlinableRegion &Region) |
| Within an extracted function, replace the constants that need to be lifted into arguments with the actual argument. | |
| std::optional< unsigned > | findDuplicateOutputBlock (DenseMap< Value *, BasicBlock * > &OutputBBs, std::vector< DenseMap< Value *, BasicBlock * > > &OutputStoreBBs) |
| It is possible that there is a basic block that already performs the same stores. | |
| static bool | analyzeAndPruneOutputBlocks (DenseMap< Value *, BasicBlock * > &BlocksToPrune, OutlinableRegion &Region) |
| Remove empty output blocks from the outlined region. | |
| static void | alignOutputBlockWithAggFunc (OutlinableGroup &OG, OutlinableRegion &Region, DenseMap< Value *, BasicBlock * > &OutputBBs, DenseMap< Value *, BasicBlock * > &EndBBs, const DenseMap< Value *, Value * > &OutputMappings, std::vector< DenseMap< Value *, BasicBlock * > > &OutputStoreBBs) |
| For the outlined section, move needed the StoreInsts for the output registers into their own block. | |
| static void | createAndInsertBasicBlocks (DenseMap< Value *, BasicBlock * > &OldMap, DenseMap< Value *, BasicBlock * > &NewMap, Function *ParentFunc, Twine BaseName) |
Takes in a mapping, OldMap of ConstantValues to BasicBlocks, sorts keys, before creating a basic block for each NewMap, and inserting into the new block. | |
| void | createSwitchStatement (Module &M, OutlinableGroup &OG, DenseMap< Value *, BasicBlock * > &EndBBs, std::vector< DenseMap< Value *, BasicBlock * > > &OutputStoreBBs) |
| Create the switch statement for outlined function to differentiate between all the output blocks. | |
| static void | fillOverallFunction (Module &M, OutlinableGroup &CurrentGroup, std::vector< DenseMap< Value *, BasicBlock * > > &OutputStoreBBs, std::vector< Function * > &FuncsToRemove, const DenseMap< Value *, Value * > &OutputMappings) |
| Fill the new function that will serve as the replacement function for all of the extracted regions of a certain structure from the first region in the list of regions. | |
| static bool | nextIRInstructionDataMatchesNextInst (IRInstructionData &ID) |
| Checks that the next instruction in the InstructionDataList matches the next instruction in the module. | |
| static Value * | findOutputValueInRegion (OutlinableRegion &Region, unsigned OutputCanon) |
For the OutputCanon number passed in find the value represented by this canonical number. | |
| static InstructionCost | findCostForOutputBlocks (Module &M, OutlinableGroup &CurrentGroup, TargetTransformInfo &TTI) |
| Find the extra instructions needed to handle any output values for the region. | |
Variables | |
| static cl::opt< bool > | EnableLinkOnceODRIROutlining ("enable-linkonceodr-ir-outlining", cl::Hidden, cl::desc("Enable the IR outliner on linkonceodr functions"), cl::init(false)) |
| static cl::opt< bool > | NoCostModel ("ir-outlining-no-cost", cl::init(false), cl::ReallyHidden, cl::desc("Debug option to outline greedily, without restriction that " "calculated benefit outweighs cost")) |
| #define DEBUG_TYPE "iroutliner" |
Definition at line 30 of file IROutliner.cpp.
| using ArgLocWithBBCanon = std::pair<unsigned, unsigned> |
Definition at line 1143 of file IROutliner.cpp.
| using CanonList = SmallVector<unsigned, 2> |
Definition at line 1145 of file IROutliner.cpp.
| using PHINodeData = std::pair<ArgLocWithBBCanon, CanonList> |
Definition at line 1148 of file IROutliner.cpp.
|
static |
For the outlined section, move needed the StoreInsts for the output registers into their own block.
Then, determine if there is a duplicate output block already created.
| [in] | OG | - The OutlinableGroup of regions to be outlined. |
| [in] | Region | - The OutlinableRegion that is being analyzed. |
| [in,out] | OutputBBs | - the blocks that stores for this region will be placed in. |
| [in] | EndBBs | - the final blocks of the extracted function. |
| [in] | OutputMappings | - OutputMappings the mapping of values that have been replaced by a new output value. |
| [in,out] | OutputStoreBBs | - The existing output blocks. |
Definition at line 2072 of file IROutliner.cpp.
References analyzeAndPruneOutputBlocks(), llvm::BranchInst::Create(), llvm::dbgs(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), findDuplicateOutputBlock(), and LLVM_DEBUG.
|
static |
Remove empty output blocks from the outlined region.
| BlocksToPrune | - Mapping of return values output blocks for the Region. |
| Region | - The OutlinableRegion we are analyzing. |
Definition at line 2025 of file IROutliner.cpp.
References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::erase(), llvm::BasicBlock::eraseFromParent(), llvm::BasicBlock::size(), and ToRemove.
Referenced by alignOutputBlockWithAggFunc(), and fillOverallFunction().
|
static |
Test whether CurrentExitFromRegion contains any PhiNodes that should be considered outputs.
A PHINodes is an output when more than one incoming value has been marked by the CodeExtractor as an output.
| CurrentExitFromRegion | [in] - The block to analyze. |
| PotentialExitsFromRegion | [in] - The potential exit blocks from the region. |
| RegionBlocks | [in] - The basic blocks in the region. |
| Outputs | [in, out] - The existing outputs for the region, we may add PHINodes to this as we find that they replace output values. |
| OutputsReplacedByPHINode | [out] - A set containing outputs that are totally replaced by a PHINode. |
| OutputsWithNonPhiUses | [out] - A set containing outputs that are used in PHINodes, but have other uses, and should still be considered outputs. |
Definition at line 1095 of file IROutliner.cpp.
References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::erase(), I, Idx, llvm::SetVector< T, Vector, Set, N >::insert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), outputHasNonPHI(), llvm::BasicBlock::phis(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::SmallVectorBase< Size_T >::size().
Referenced by findExtractedOutputToOverallOutputMapping().
|
static |
Find whether Region matches the global value numbering to Constant mapping found so far.
| Region | - The OutlinableRegion we are checking for constants |
| GVNToConstant | - The mapping of global value number to Constants. |
| NotSame | - The set of global value numbers that do not have the same constant in each region. |
Region and false if not Definition at line 549 of file IROutliner.cpp.
References assert(), llvm::CallingConv::C, constantMatches(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::contains(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), and llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert().
Referenced by OutlinableGroup::findSameConstants().
|
static |
Find whether V matches the Constants previously found for the GVN.
| V | - The value to check for consistency. |
| GVN | - The global value number assigned to V. |
| GVNToConstant | - The mapping of global value number to Constants. |
V is a Constant but does not match. V is not a Constant. Definition at line 463 of file IROutliner.cpp.
References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().
Referenced by collectRegionsConstants().
|
static |
Takes in a mapping, OldMap of ConstantValues to BasicBlocks, sorts keys, before creating a basic block for each NewMap, and inserting into the new block.
Each BasicBlock is named with the scheme "<basename>_<key_idx>".
| OldMap | [in] - The mapping to base the new mapping off of. |
| NewMap | [out] - The output mapping using the keys of OldMap. |
| ParentFunc | [in] - The function to put the new basic block in. |
| BaseName | [in] - The start of the BasicBlock names to be appended to by an index value. |
Definition at line 2127 of file IROutliner.cpp.
References llvm::BasicBlock::Create(), llvm::Function::getContext(), getSortedConstantKeys(), Idx, and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().
Referenced by createSwitchStatement(), and fillOverallFunction().
| void createSwitchStatement | ( | Module & | M, |
| OutlinableGroup & | OG, | ||
| DenseMap< Value *, BasicBlock * > & | EndBBs, | ||
| std::vector< DenseMap< Value *, BasicBlock * > > & | OutputStoreBBs | ||
| ) |
Create the switch statement for outlined function to differentiate between all the output blocks.
For the outlined section, determine if an outlined block already exists that matches the needed stores for the extracted section.
| [in] | M | - The module we are outlining from. |
| [in] | OG | - The group of regions to be outlined. |
| [in] | EndBBs | - The final blocks of the extracted function. |
| [in,out] | OutputStoreBBs | - The existing output blocks. |
Definition at line 2153 of file IROutliner.cpp.
References llvm::SwitchInst::addCase(), llvm::Function::arg_size(), assert(), llvm::SwitchInst::Create(), createAndInsertBasicBlocks(), llvm::dbgs(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::BasicBlock::end(), OutlinableGroup::EndBBs, llvm::BasicBlock::eraseFromParent(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::Function::getArg(), llvm::Type::getInt32Ty(), llvm::BasicBlock::getTerminator(), Idx, LLVM_DEBUG, moveBBContents(), OutlinableGroup::OutlinedFunction, OutlinableGroup::OutputGVNCombinations, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::size(), llvm::BasicBlock::size(), and llvm::Function::size().
|
static |
Encode PND as an integer for easy lookup based on the argument location, the parent BasicBlock canonical numbering, and the canonical numbering of the values stored in the PHINode.
| PND | - The data to hash. |
PND. Definition at line 1156 of file IROutliner.cpp.
References llvm::hash_combine(), llvm::hash_combine_range(), and llvm::hash_value().
Referenced by getGVNForPHINode().
|
static |
Fill the new function that will serve as the replacement function for all of the extracted regions of a certain structure from the first region in the list of regions.
Replace this first region's extracted function with the new overall function.
| [in] | M | - The module we are outlining from. |
| [in] | CurrentGroup | - The group of regions to be outlined. |
| [in,out] | OutputStoreBBs | - The output blocks for each different set of stores needed for the different functions. |
| [in,out] | FuncsToRemove | - Extracted functions to erase from module once outlining is complete. |
| [in] | OutputMappings | - Extracted functions to erase from module once outlining is complete. |
Definition at line 2246 of file IROutliner.cpp.
References A, llvm::Function::addFnAttr(), analyzeAndPruneOutputBlocks(), llvm::OutlinableRegion::Call, llvm::BranchInst::Create(), createAndInsertBasicBlocks(), llvm::dbgs(), OutlinableGroup::EndBBs, llvm::OutlinableRegion::ExtractedFunction, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::Function::getAttributes(), llvm::AttributeList::getFnAttrs(), LLVM_DEBUG, moveFunctionData(), OutlinableGroup::OutlinedFunction, llvm::OutlinableRegion::OutputBlockNum, OutlinableGroup::Regions, replaceArgumentUses(), replaceCalledFunction(), and replaceConstants().
|
static |
Find the canonical numbering for the incoming Values into the PHINode PN.
| PN | [in] - The PHINode that we are finding the canonical numbers for. |
| Region | [in] - The OutlinableRegion containing PN. |
| OutputMappings | [in] - The mapping of output values from outlined region to their original values. |
| CanonNums | [out] - The canonical numbering for the incoming values to PN paired with their incoming block. |
| ReplacedWithOutlinedCall | - A flag to use the extracted function call of Region rather than the overall function's call. |
Definition at line 1637 of file IROutliner.cpp.
References A, assert(), findOutputMapping(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), getPassedArgumentAndAdjustArgumentLocation(), getPassedArgumentInAlreadyOutlinedFunction(), and Idx.
Referenced by findOrCreatePHIInBlock().
|
static |
Find the constants that will need to be lifted into arguments as they are not the same in each instance of the region.
| [in] | C | - The IRSimilarityCandidate containing the region we are analyzing. |
| [in] | NotSame | - The set of global value numbers that do not have a single Constant across all OutlinableRegions similar to C. |
| [out] | Inputs | - The list containing the global value numbers of the arguments needed for the region of code. |
Definition at line 780 of file IROutliner.cpp.
References llvm::CallingConv::C, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), and llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert().
Referenced by getCodeExtractorArguments().
|
static |
Find the extra instructions needed to handle any output values for the region.
| [in] | M | - The Module to outline from. |
| [in] | CurrentGroup | - The collection of OutlinableRegions to analyze. |
| [in] | TTI | - The TargetTransformInfo used to collect information for new instruction costs. |
Definition at line 2559 of file IROutliner.cpp.
References llvm::CmpInst::BAD_ICMP_PREDICATE, OutlinableGroup::BranchesToOutside, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), llvm::dbgs(), findOutputValueInRegion(), llvm::IRSimilarity::IRSimilarityCandidate::getBasicBlocks(), llvm::TargetTransformInfo::getCFInstrCost(), llvm::TargetTransformInfo::getCmpSelInstrCost(), llvm::Type::getInt32Ty(), llvm::TargetTransformInfo::getMemoryOpCost(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), LLVM_DEBUG, OutlinableGroup::OutputGVNCombinations, OutlinableGroup::Regions, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::size(), and llvm::TargetTransformInfo::TCK_CodeSize.
| std::optional< unsigned > findDuplicateOutputBlock | ( | DenseMap< Value *, BasicBlock * > & | OutputBBs, |
| std::vector< DenseMap< Value *, BasicBlock * > > & | OutputStoreBBs | ||
| ) |
It is possible that there is a basic block that already performs the same stores.
This returns a duplicate block, if it exists
| OutputBBs | [in] the blocks we are looking for a duplicate of. |
| OutputStoreBBs | [in] The existing output blocks. |
Definition at line 1970 of file IROutliner.cpp.
References llvm::BasicBlock::begin(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), I, and llvm::BasicBlock::size().
Referenced by alignOutputBlockWithAggFunc().
|
static |
Look over the inputs and map each input argument to an argument in the overall function for the OutlinableRegions.
This creates a way to replace the arguments of the extracted function with the arguments of the new overall function.
| [in,out] | Region | - The region of code to be analyzed. |
| [in] | InputGVNs | - The global value numbering of the input values collected. |
| [in] | ArgInputs | - The values of the arguments to the extracted function. |
Definition at line 936 of file IROutliner.cpp.
References OutlinableGroup::ArgumentTypes, assert(), llvm::CallingConv::C, OutlinableGroup::CanonicalNumberToAggArg, llvm::SetVector< T, Vector, Set, N >::count(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::Value::getType(), OutlinableGroup::InputTypesSet, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::Value::isSwiftError(), OutlinableGroup::NumAggregateInputs, and OutlinableGroup::SwiftErrorArgument.
|
static |
Create a mapping of the output arguments for the Region to the output arguments of the overall outlined function.
| [in,out] | Region | - The region of code to be analyzed. |
| [in] | Outputs | - The values found by the code extractor. |
Definition at line 1278 of file IROutliner.cpp.
References analyzeExitPHIsForOutputUses(), OutlinableGroup::ArgumentTypes, llvm::Block, llvm::CallingConv::C, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), llvm::PointerType::get(), getGVNForPHINode(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), OutlinableGroup::NumAggregateInputs, llvm::stable_sort(), and llvm::successors().
|
static |
Find or create a BasicBlock in the outlined function containing PhiBlocks for RetVal.
| Group | - The OutlinableGroup containing the information about the overall outlined function. |
| RetVal | - The return value or exit option that we are currently evaluating. |
Definition at line 1543 of file IROutliner.cpp.
References assert(), llvm::BranchInst::Create(), llvm::BasicBlock::Create(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), End, OutlinableGroup::EndBBs, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::BasicBlock::getContext(), llvm::BasicBlock::getParent(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), OutlinableGroup::PHIBlocks, llvm::predecessors(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().
Referenced by replaceArgumentUses().
|
static |
Find, or add PHINode PN to the combined PHINode Block OverallPHIBlock in order to condense the number of instructions added to the outlined function.
| PN | [in] - The PHINode that we are finding the canonical numbers for. |
| Region | [in] - The OutlinableRegion containing PN. |
| OverallPhiBlock | [in] - The overall PHIBlock we are trying to find PN in. |
| OutputMappings | [in] - The mapping of output values from outlined region to their original values. |
| UsedPHIs | [in, out] - The PHINodes in the block that have already been matched. |
OverallPhiBlock. Definition at line 1681 of file IROutliner.cpp.
References A, assert(), llvm::BasicBlock::begin(), llvm::SmallVectorImpl< T >::clear(), llvm::Instruction::clone(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), findCanonNumsForPHI(), findOutputMapping(), llvm::Function::getArg(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), Idx, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::Instruction::insertBefore(), OutlinableGroup::OutlinedFunction, llvm::BasicBlock::phis(), OutlinableGroup::Regions, llvm::OutlinableRegion::RemappedArguments, llvm::PHINode::setIncomingBlock(), llvm::PHINode::setIncomingValue(), and llvm::SmallVectorBase< Size_T >::size().
Referenced by replaceArgumentUses().
|
static |
Check the OutputMappings structure for value Input, if it exists it has been used as an output for outlining, and has been renamed, and we return the new value, otherwise, we return the same value.
| OutputMappings | [in] - The mapping of values to their renamed value after being used as an output for an outlined region. |
| Input | [in] - The value to find the remapped value of, if it exists. |
Definition at line 530 of file IROutliner.cpp.
References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find().
Referenced by findCanonNumsForPHI(), and findOrCreatePHIInBlock().
|
static |
For the OutputCanon number passed in find the value represented by this canonical number.
If it is from a PHINode, we pick the first incoming value and return that Value instead.
| Region | - The OutlinableRegion to get the Value from. |
| OutputCanon | - The canonical number to find the Value from. |
OutputCanon in Region. Definition at line 2507 of file IROutliner.cpp.
References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), OutlinableGroup::PHINodeGVNToGVNs, and OutlinableGroup::PHINodeGVNTracker.
Referenced by findCostForOutputBlocks().
|
static |
Find the input GVNs and the output values for a region of Instructions.
Using the code extractor, we collect the inputs to the extracted function.
The Region can be identified as needing to be ignored in this function. It should be checked whether it should be ignored after a call to this function.
| [in,out] | Region | - The region of code to be analyzed. |
| [out] | InputGVNs | - The global value numbers for the extracted arguments. |
| [in] | NotSame | - The global value numbers in the region that do not have the same constant value in the regions structurally similar to Region. |
| [in] | OutputMappings | - The mapping of values that have been replaced by a new output value after extraction. |
| [out] | ArgInputs | - The values of the inputs to the extracted function. |
| [out] | Outputs | - The set of values extracted by the CodeExtractor as outputs. |
Definition at line 865 of file IROutliner.cpp.
References assert(), llvm::CallingConv::C, findConstants(), llvm::SetVector< T, Vector, Set, N >::getArrayRef(), llvm::RegionBase< Tr >::getParent(), mapInputsToGVNs(), remapExtractedInputs(), llvm::SetVector< T, Vector, Set, N >::size(), and llvm::stable_sort().
|
static |
Create a special GVN for PHINodes that will be used outside of the region.
We create a hash code based on the Canonical number of the parent BasicBlock, the canonical numbering of the values stored in the PHINode and the aggregate argument location. This is used to find whether this PHINode type has been given a canonical numbering already. If not, we assign it a value and store it for later use. The value is returned to identify different output schemes for the set of regions.
| Region | - The region that PN is an output for. |
| PN | - The PHINode we are analyzing. |
| Blocks | - The blocks for the region we are analyzing. |
| AggArgIdx | - The argument PN will be stored into. |
Definition at line 1176 of file IROutliner.cpp.
References assert(), Blocks, encodePHINodeData(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::IRSimilarity::IRSimilarityCandidate::getCanonicalNum(), llvm::IRSimilarity::IRSimilarityCandidate::getGVN(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::IRSimilarity::IRSimilarityCandidate::getStartBB(), OutlinableGroup::GVNsToPHINodeGVN, Idx, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), OutlinableGroup::PHINodeGVNToGVNs, OutlinableGroup::PHINodeGVNTracker, llvm::predecessors(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().
Referenced by findExtractedOutputToOverallOutputMapping().
|
static |
For the function call now representing the Region, find the passed value to that call that represents Argument A at the call location if the call has only been replaced by the call to the aggregate function.
| A | - The Argument to get the passed value for. |
| Region | - The extracted Region corresponding to the outlined function. |
A at the call site. Definition at line 1612 of file IROutliner.cpp.
References A.
Referenced by findCanonNumsForPHI().
|
static |
For the function call now representing the Region, find the passed value to that call that represents Argument A at the call location if the call has already been replaced with a call to the overall, aggregate function.
| A | - The Argument to get the passed value for. |
| Region | - The extracted Region corresponding to the outlined function. |
A at the call site. Definition at line 1596 of file IROutliner.cpp.
References A.
Referenced by findCanonNumsForPHI().
|
static |
A function to sort the keys of Map, which must be a mapping of constant values to basic blocks and return it in SortedKeys.
| SortedKeys | - The vector the keys will be return in and sorted. |
| Map | - The DenseMap containing keys to sort. |
Definition at line 165 of file IROutliner.cpp.
References assert(), llvm::ConstantInt::getLimitedValue(), LHS, RHS, and llvm::stable_sort().
Referenced by createAndInsertBasicBlocks().
|
static |
Get the subprogram if it exists for one of the outlined regions.
| [in] | Group | - The set of regions to find a subprogram for. |
Definition at line 620 of file IROutliner.cpp.
References F, OS, and OutlinableGroup::Regions.
|
static |
Find the GVN for the inputs that have been found by the CodeExtractor.
| [in] | C | - The IRSimilarityCandidate containing the region we are analyzing. |
| [in] | CurrentInputs | - The set of inputs found by the CodeExtractor. |
| [in] | OutputMappings | - The mapping of values that have been replaced by a new output value. |
| [out] | EndInputNumbers | - The global value numbers for the extracted arguments. |
Definition at line 810 of file IROutliner.cpp.
References assert(), llvm::CallingConv::C, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::contains(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find().
Referenced by getCodeExtractorArguments().
|
static |
Move the contents of SourceBB to before the last instruction of TargetBB.
| SourceBB | - the BasicBlock to pull Instructions from. |
| TargetBB | - the BasicBlock to put Instruction into. |
Definition at line 156 of file IROutliner.cpp.
References llvm::BasicBlock::end(), and llvm::BasicBlock::splice().
Referenced by createSwitchStatement(), and llvm::OutlinableRegion::reattachCandidate().
|
static |
Move each BasicBlock in Old to New.
| [in] | Old | - The function to move the basic blocks from. |
| [in] | New | - The function to move the basic blocks to. |
| [out] | NewEnds | - The return blocks of the new overall function. |
Definition at line 708 of file IROutliner.cpp.
References llvm::MDNode::get(), I, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::make_early_inc_range(), and llvm::updateLoopMetadataDebugLocations().
Referenced by fillOverallFunction().
|
static |
Checks that the next instruction in the InstructionDataList matches the next instruction in the module.
If they do not, there could be the possibility that extra code has been inserted, and we must ignore it.
| ID | - The IRInstructionData to check the next instruction of. |
Definition at line 2340 of file IROutliner.cpp.
References llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent().
|
static |
Check if the V has any uses outside of the region other than PN.
| V | [in] - The value to check. |
| PHILoc | [in] - The location in the PHINode of V. |
| PN | [in] - The PHINode using V. |
| Exits | [in] - The potential blocks we exit to from the outlined region. |
| BlocksInRegion | [in] - The basic blocks contained in the region. |
V has any use soutside its region other than PN. Definition at line 1038 of file IROutliner.cpp.
References llvm::any_of(), llvm::PHINode::getNumIncomingValues(), and Idx.
Referenced by analyzeExitPHIsForOutputUses().
|
static |
Find the original value for the ArgInput values if any one of them was replaced during a previous extraction.
| [in] | ArgInputs | - The inputs to be extracted by the code extractor. |
| [in] | OutputMappings | - The mapping of values that have been replaced by a new output value. |
| [out] | RemappedArgInputs | - The remapped values according to OutputMappings that will be extracted. |
Definition at line 835 of file IROutliner.cpp.
References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::contains(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and llvm::SetVector< T, Vector, Set, N >::insert().
Referenced by getCodeExtractorArguments().
|
static |
| [in] | Region | - The region of extracted code to be changed. |
| [in,out] | OutputBBs | - The BasicBlock for the output stores for this region. |
| [in] | FirstFunction | - A flag to indicate whether we are using this function to define the overall outlined function for all the regions, or if we are operating on one of the following regions. |
Definition at line 1803 of file IROutliner.cpp.
References assert(), llvm::RegionBase< Tr >::contains(), llvm::dbgs(), llvm::DominatorTreeBase< NodeT, IsPostDom >::deleteEdge(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::BasicBlock::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), findOrCreatePHIBlock(), findOrCreatePHIInBlock(), llvm::Function::getArg(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getDescendants(), llvm::Function::getEntryBlock(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::ReturnInst::getReturnValue(), llvm::Value::hasOneUse(), I, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::DominatorTreeBase< NodeT, IsPostDom >::insertEdge(), llvm::Instruction::insertInto(), LLVM_DEBUG, OutlinableGroup::OutlinedFunction, OutlinableGroup::PHIBlocks, OutlinableGroup::Regions, llvm::Value::replaceAllUsesWith(), llvm::Instruction::setDebugLoc(), llvm::User::setOperand(), llvm::SmallVectorBase< Size_T >::size(), and llvm::Value::user_back().
Referenced by fillOverallFunction().
| CallInst * replaceCalledFunction | ( | Module & | M, |
| OutlinableRegion & | Region | ||
| ) |
Replace the extracted function in the Region with a call to the overall function constructed from the deduplicated similar regions, replacing and remapping the values passed to the extracted function as arguments to the new arguments of the overall function.
| [in] | M | - The module to outline from. |
| [in] | Region | - The regions of extracted code to be replaced with a new function. |
Definition at line 1432 of file IROutliner.cpp.
References llvm::Function::arg_size(), assert(), llvm::RegionBase< Tr >::contains(), llvm::CallInst::Create(), llvm::dbgs(), llvm::RegionBase< Tr >::end(), llvm::Instruction::eraseFromParent(), llvm::ConstantPointerNull::get(), llvm::Function::getArg(), llvm::Function::getFunctionType(), llvm::Type::getInt32Ty(), llvm::Value::getType(), LLVM_DEBUG, OutlinableGroup::OutlinedFunction, OutlinableGroup::OutputGVNCombinations, llvm::Value::replaceAllUsesWith(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::size(), and OutlinableGroup::SwiftErrorArgument.
Referenced by fillOverallFunction().
| void replaceConstants | ( | OutlinableRegion & | Region | ) |
Within an extracted function, replace the constants that need to be lifted into arguments with the actual argument.
| Region | [in] - The region of extracted code to be changed. |
Definition at line 1937 of file IROutliner.cpp.
References assert(), llvm::dbgs(), llvm::Function::getArg(), I, LLVM_DEBUG, OutlinableGroup::OutlinedFunction, and llvm::Value::replaceUsesWithIf().
Referenced by fillOverallFunction().
|
static |
Rewrite the BranchInsts in the incoming blocks to PHIBlock that are found in Included to branch to BasicBlock Replace if they currently branch to the BasicBlock Find.
This is used to fix up the incoming basic blocks when PHINodes are included in outlined regions.
| PHIBlock | - The BasicBlock containing the PHINodes that need to be checked. |
| Find | - The successor block to be replaced. |
| Replace | - The new succesor block to branch to. |
| Included | - The set of blocks about to be outlined. |
Definition at line 220 of file IROutliner.cpp.
References assert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), End, Find(), llvm::BranchInst::getNumSuccessors(), llvm::BranchInst::getSuccessor(), Idx, llvm::BasicBlock::phis(), and llvm::BranchInst::setSuccessor().
Referenced by llvm::OutlinableRegion::reattachCandidate(), and llvm::OutlinableRegion::splitCandidate().
|
static |
Referenced by llvm::IROutliner::run().
|
static |
Referenced by llvm::IROutliner::run().
1.9.6