//===- IROutliner.cpp -- Outline Similar Regions ----------------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// /// \file // Implementation for the IROutliner which is used by the IROutliner Pass. // //===----------------------------------------------------------------------===// #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> #define DEBUG_TYPE … usingnamespacellvm; usingnamespaceIRSimilarity; // A command flag to be used for debugging to exclude branches from similarity // matching and outlining. namespace llvm { extern cl::opt<bool> DisableBranches; // A command flag to be used for debugging to indirect calls from similarity // matching and outlining. extern cl::opt<bool> DisableIndirectCalls; // A command flag to be used for debugging to exclude intrinsics from similarity // matching and outlining. extern cl::opt<bool> DisableIntrinsics; } // namespace llvm // Set to true if the user wants the ir outliner to run on linkonceodr linkage // functions. This is false by default because the linker can dedupe linkonceodr // functions. Since the outliner is confined to a single module (modulo LTO), // this is off by default. It should, however, be the default behavior in // LTO. static cl::opt<bool> EnableLinkOnceODRIROutlining( "enable-linkonceodr-ir-outlining", cl::Hidden, cl::desc("Enable the IR outliner on linkonceodr functions"), cl::init(false)); // This is a debug option to test small pieces of code to ensure that outlining // works correctly. 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")); /// 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. This information is used in the /// deduplication of extracted regions with the same structure. struct OutlinableGroup { … }; /// Move the contents of \p SourceBB to before the last instruction of \p /// TargetBB. /// \param SourceBB - the BasicBlock to pull Instructions from. /// \param TargetBB - the BasicBlock to put Instruction into. static void moveBBContents(BasicBlock &SourceBB, BasicBlock &TargetBB) { … } /// A function to sort the keys of \p Map, which must be a mapping of constant /// values to basic blocks and return it in \p SortedKeys /// /// \param SortedKeys - The vector the keys will be return in and sorted. /// \param Map - The DenseMap containing keys to sort. static void getSortedConstantKeys(std::vector<Value *> &SortedKeys, DenseMap<Value *, BasicBlock *> &Map) { … } Value *OutlinableRegion::findCorrespondingValueIn(const OutlinableRegion &Other, Value *V) { … } BasicBlock * OutlinableRegion::findCorrespondingBlockIn(const OutlinableRegion &Other, BasicBlock *BB) { … } /// Rewrite the BranchInsts in the incoming blocks to \p PHIBlock that are found /// in \p Included to branch to BasicBlock \p Replace if they currently branch /// to the BasicBlock \p Find. This is used to fix up the incoming basic blocks /// when PHINodes are included in outlined regions. /// /// \param PHIBlock - The BasicBlock containing the PHINodes that need to be /// checked. /// \param Find - The successor block to be replaced. /// \param Replace - The new succesor block to branch to. /// \param Included - The set of blocks about to be outlined. static void replaceTargetsFromPHINode(BasicBlock *PHIBlock, BasicBlock *Find, BasicBlock *Replace, DenseSet<BasicBlock *> &Included) { … } void OutlinableRegion::splitCandidate() { … } void OutlinableRegion::reattachCandidate() { … } /// Find whether \p V matches the Constants previously found for the \p GVN. /// /// \param V - The value to check for consistency. /// \param GVN - The global value number assigned to \p V. /// \param GVNToConstant - The mapping of global value number to Constants. /// \returns true if the Value matches the Constant mapped to by V and false if /// it \p V is a Constant but does not match. /// \returns std::nullopt if \p V is not a Constant. static std::optional<bool> constantMatches(Value *V, unsigned GVN, DenseMap<unsigned, Constant *> &GVNToConstant) { … } InstructionCost OutlinableRegion::getBenefit(TargetTransformInfo &TTI) { … } /// Check the \p OutputMappings structure for value \p 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. /// /// \param OutputMappings [in] - The mapping of values to their renamed value /// after being used as an output for an outlined region. /// \param Input [in] - The value to find the remapped value of, if it exists. /// \return The remapped value if it has been renamed, and the same value if has /// not. static Value *findOutputMapping(const DenseMap<Value *, Value *> OutputMappings, Value *Input) { … } /// Find whether \p Region matches the global value numbering to Constant /// mapping found so far. /// /// \param Region - The OutlinableRegion we are checking for constants /// \param GVNToConstant - The mapping of global value number to Constants. /// \param NotSame - The set of global value numbers that do not have the same /// constant in each region. /// \returns true if all Constants are the same in every use of a Constant in \p /// Region and false if not static bool collectRegionsConstants(OutlinableRegion &Region, DenseMap<unsigned, Constant *> &GVNToConstant, DenseSet<unsigned> &NotSame) { … } void OutlinableGroup::findSameConstants(DenseSet<unsigned> &NotSame) { … } void OutlinableGroup::collectGVNStoreSets(Module &M) { … } /// Get the subprogram if it exists for one of the outlined regions. /// /// \param [in] Group - The set of regions to find a subprogram for. /// \returns the subprogram if it exists, or nullptr. static DISubprogram *getSubprogramOrNull(OutlinableGroup &Group) { … } Function *IROutliner::createFunction(Module &M, OutlinableGroup &Group, unsigned FunctionNameSuffix) { … } /// Move each BasicBlock in \p Old to \p New. /// /// \param [in] Old - The function to move the basic blocks from. /// \param [in] New - The function to move the basic blocks to. /// \param [out] NewEnds - The return blocks of the new overall function. static void moveFunctionData(Function &Old, Function &New, DenseMap<Value *, BasicBlock *> &NewEnds) { … } /// Find the constants that will need to be lifted into arguments /// as they are not the same in each instance of the region. /// /// \param [in] C - The IRSimilarityCandidate containing the region we are /// analyzing. /// \param [in] NotSame - The set of global value numbers that do not have a /// single Constant across all OutlinableRegions similar to \p C. /// \param [out] Inputs - The list containing the global value numbers of the /// arguments needed for the region of code. static void findConstants(IRSimilarityCandidate &C, DenseSet<unsigned> &NotSame, std::vector<unsigned> &Inputs) { … } /// Find the GVN for the inputs that have been found by the CodeExtractor. /// /// \param [in] C - The IRSimilarityCandidate containing the region we are /// analyzing. /// \param [in] CurrentInputs - The set of inputs found by the /// CodeExtractor. /// \param [in] OutputMappings - The mapping of values that have been replaced /// by a new output value. /// \param [out] EndInputNumbers - The global value numbers for the extracted /// arguments. static void mapInputsToGVNs(IRSimilarityCandidate &C, SetVector<Value *> &CurrentInputs, const DenseMap<Value *, Value *> &OutputMappings, std::vector<unsigned> &EndInputNumbers) { … } /// Find the original value for the \p ArgInput values if any one of them was /// replaced during a previous extraction. /// /// \param [in] ArgInputs - The inputs to be extracted by the code extractor. /// \param [in] OutputMappings - The mapping of values that have been replaced /// by a new output value. /// \param [out] RemappedArgInputs - The remapped values according to /// \p OutputMappings that will be extracted. static void remapExtractedInputs(const ArrayRef<Value *> ArgInputs, const DenseMap<Value *, Value *> &OutputMappings, SetVector<Value *> &RemappedArgInputs) { … } /// 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 \p 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. /// /// \param [in,out] Region - The region of code to be analyzed. /// \param [out] InputGVNs - The global value numbers for the extracted /// arguments. /// \param [in] NotSame - The global value numbers in the region that do not /// have the same constant value in the regions structurally similar to /// \p Region. /// \param [in] OutputMappings - The mapping of values that have been replaced /// by a new output value after extraction. /// \param [out] ArgInputs - The values of the inputs to the extracted function. /// \param [out] Outputs - The set of values extracted by the CodeExtractor /// as outputs. static void getCodeExtractorArguments( OutlinableRegion &Region, std::vector<unsigned> &InputGVNs, DenseSet<unsigned> &NotSame, DenseMap<Value *, Value *> &OutputMappings, SetVector<Value *> &ArgInputs, SetVector<Value *> &Outputs) { … } /// 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. /// /// \param [in,out] Region - The region of code to be analyzed. /// \param [in] InputGVNs - The global value numbering of the input values /// collected. /// \param [in] ArgInputs - The values of the arguments to the extracted /// function. static void findExtractedInputToOverallInputMapping(OutlinableRegion &Region, std::vector<unsigned> &InputGVNs, SetVector<Value *> &ArgInputs) { … } /// Check if the \p V has any uses outside of the region other than \p PN. /// /// \param V [in] - The value to check. /// \param PHILoc [in] - The location in the PHINode of \p V. /// \param PN [in] - The PHINode using \p V. /// \param Exits [in] - The potential blocks we exit to from the outlined /// region. /// \param BlocksInRegion [in] - The basic blocks contained in the region. /// \returns true if \p V has any use soutside its region other than \p PN. static bool outputHasNonPHI(Value *V, unsigned PHILoc, PHINode &PN, SmallPtrSet<BasicBlock *, 1> &Exits, DenseSet<BasicBlock *> &BlocksInRegion) { … } /// Test whether \p 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. /// /// \param CurrentExitFromRegion [in] - The block to analyze. /// \param PotentialExitsFromRegion [in] - The potential exit blocks from the /// region. /// \param RegionBlocks [in] - The basic blocks in the region. /// \param Outputs [in, out] - The existing outputs for the region, we may add /// PHINodes to this as we find that they replace output values. /// \param OutputsReplacedByPHINode [out] - A set containing outputs that are /// totally replaced by a PHINode. /// \param OutputsWithNonPhiUses [out] - A set containing outputs that are used /// in PHINodes, but have other uses, and should still be considered outputs. static void analyzeExitPHIsForOutputUses( BasicBlock *CurrentExitFromRegion, SmallPtrSet<BasicBlock *, 1> &PotentialExitsFromRegion, DenseSet<BasicBlock *> &RegionBlocks, SetVector<Value *> &Outputs, DenseSet<Value *> &OutputsReplacedByPHINode, DenseSet<Value *> &OutputsWithNonPhiUses) { … } // Represents the type for the unsigned number denoting the output number for // phi node, along with the canonical number for the exit block. ArgLocWithBBCanon; // The list of canonical numbers for the incoming values to a PHINode. CanonList; // The pair type representing the set of canonical values being combined in the // PHINode, along with the location data for the PHINode. PHINodeData; /// Encode \p 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. /// /// \param PND - The data to hash. /// \returns The hash code of \p PND. static hash_code encodePHINodeData(PHINodeData &PND) { … } /// 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. /// /// \param Region - The region that \p PN is an output for. /// \param PN - The PHINode we are analyzing. /// \param Blocks - The blocks for the region we are analyzing. /// \param AggArgIdx - The argument \p PN will be stored into. /// \returns An optional holding the assigned canonical number, or std::nullopt /// if there is some attribute of the PHINode blocking it from being used. static std::optional<unsigned> getGVNForPHINode(OutlinableRegion &Region, PHINode *PN, DenseSet<BasicBlock *> &Blocks, unsigned AggArgIdx) { … } /// Create a mapping of the output arguments for the \p Region to the output /// arguments of the overall outlined function. /// /// \param [in,out] Region - The region of code to be analyzed. /// \param [in] Outputs - The values found by the code extractor. static void findExtractedOutputToOverallOutputMapping(Module &M, OutlinableRegion &Region, SetVector<Value *> &Outputs) { … } void IROutliner::findAddInputsOutputs(Module &M, OutlinableRegion &Region, DenseSet<unsigned> &NotSame) { … } /// 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. /// /// \param [in] M - The module to outline from. /// \param [in] Region - The regions of extracted code to be replaced with a new /// function. /// \returns a call instruction with the replaced function. CallInst *replaceCalledFunction(Module &M, OutlinableRegion &Region) { … } /// Find or create a BasicBlock in the outlined function containing PhiBlocks /// for \p RetVal. /// /// \param Group - The OutlinableGroup containing the information about the /// overall outlined function. /// \param RetVal - The return value or exit option that we are currently /// evaluating. /// \returns The found or newly created BasicBlock to contain the needed /// PHINodes to be used as outputs. static BasicBlock *findOrCreatePHIBlock(OutlinableGroup &Group, Value *RetVal) { … } /// For the function call now representing the \p Region, find the passed value /// to that call that represents Argument \p A at the call location if the /// call has already been replaced with a call to the overall, aggregate /// function. /// /// \param A - The Argument to get the passed value for. /// \param Region - The extracted Region corresponding to the outlined function. /// \returns The Value representing \p A at the call site. static Value * getPassedArgumentInAlreadyOutlinedFunction(const Argument *A, const OutlinableRegion &Region) { … } /// For the function call now representing the \p Region, find the passed value /// to that call that represents Argument \p A at the call location if the /// call has only been replaced by the call to the aggregate function. /// /// \param A - The Argument to get the passed value for. /// \param Region - The extracted Region corresponding to the outlined function. /// \returns The Value representing \p A at the call site. static Value * getPassedArgumentAndAdjustArgumentLocation(const Argument *A, const OutlinableRegion &Region) { … } /// Find the canonical numbering for the incoming Values into the PHINode \p PN. /// /// \param PN [in] - The PHINode that we are finding the canonical numbers for. /// \param Region [in] - The OutlinableRegion containing \p PN. /// \param OutputMappings [in] - The mapping of output values from outlined /// region to their original values. /// \param CanonNums [out] - The canonical numbering for the incoming values to /// \p PN paired with their incoming block. /// \param ReplacedWithOutlinedCall - A flag to use the extracted function call /// of \p Region rather than the overall function's call. static void findCanonNumsForPHI( PHINode *PN, OutlinableRegion &Region, const DenseMap<Value *, Value *> &OutputMappings, SmallVector<std::pair<unsigned, BasicBlock *>> &CanonNums, bool ReplacedWithOutlinedCall = true) { … } /// Find, or add PHINode \p PN to the combined PHINode Block \p OverallPHIBlock /// in order to condense the number of instructions added to the outlined /// function. /// /// \param PN [in] - The PHINode that we are finding the canonical numbers for. /// \param Region [in] - The OutlinableRegion containing \p PN. /// \param OverallPhiBlock [in] - The overall PHIBlock we are trying to find /// \p PN in. /// \param OutputMappings [in] - The mapping of output values from outlined /// region to their original values. /// \param UsedPHIs [in, out] - The PHINodes in the block that have already been /// matched. /// \return the newly found or created PHINode in \p OverallPhiBlock. static PHINode* findOrCreatePHIInBlock(PHINode &PN, OutlinableRegion &Region, BasicBlock *OverallPhiBlock, const DenseMap<Value *, Value *> &OutputMappings, DenseSet<PHINode *> &UsedPHIs) { … } // Within an extracted function, replace the argument uses of the extracted // region with the arguments of the function for an OutlinableGroup. // /// \param [in] Region - The region of extracted code to be changed. /// \param [in,out] OutputBBs - The BasicBlock for the output stores for this /// region. /// \param [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. static void replaceArgumentUses(OutlinableRegion &Region, DenseMap<Value *, BasicBlock *> &OutputBBs, const DenseMap<Value *, Value *> &OutputMappings, bool FirstFunction = false) { … } /// Within an extracted function, replace the constants that need to be lifted /// into arguments with the actual argument. /// /// \param Region [in] - The region of extracted code to be changed. void replaceConstants(OutlinableRegion &Region) { … } /// It is possible that there is a basic block that already performs the same /// stores. This returns a duplicate block, if it exists /// /// \param OutputBBs [in] the blocks we are looking for a duplicate of. /// \param OutputStoreBBs [in] The existing output blocks. /// \returns an optional value with the number output block if there is a match. std::optional<unsigned> findDuplicateOutputBlock( DenseMap<Value *, BasicBlock *> &OutputBBs, std::vector<DenseMap<Value *, BasicBlock *>> &OutputStoreBBs) { … } /// Remove empty output blocks from the outlined region. /// /// \param BlocksToPrune - Mapping of return values output blocks for the \p /// Region. /// \param Region - The OutlinableRegion we are analyzing. static bool analyzeAndPruneOutputBlocks(DenseMap<Value *, BasicBlock *> &BlocksToPrune, OutlinableRegion &Region) { … } /// 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. /// /// \param [in] OG - The OutlinableGroup of regions to be outlined. /// \param [in] Region - The OutlinableRegion that is being analyzed. /// \param [in,out] OutputBBs - the blocks that stores for this region will be /// placed in. /// \param [in] EndBBs - the final blocks of the extracted function. /// \param [in] OutputMappings - OutputMappings the mapping of values that have /// been replaced by a new output value. /// \param [in,out] OutputStoreBBs - The existing output blocks. 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) { … } /// Takes in a mapping, \p OldMap of ConstantValues to BasicBlocks, sorts keys, /// before creating a basic block for each \p NewMap, and inserting into the new /// block. Each BasicBlock is named with the scheme "<basename>_<key_idx>". /// /// \param OldMap [in] - The mapping to base the new mapping off of. /// \param NewMap [out] - The output mapping using the keys of \p OldMap. /// \param ParentFunc [in] - The function to put the new basic block in. /// \param BaseName [in] - The start of the BasicBlock names to be appended to /// by an index value. static void createAndInsertBasicBlocks(DenseMap<Value *, BasicBlock *> &OldMap, DenseMap<Value *, BasicBlock *> &NewMap, Function *ParentFunc, Twine BaseName) { … } /// 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. /// \param [in] M - The module we are outlining from. /// \param [in] OG - The group of regions to be outlined. /// \param [in] EndBBs - The final blocks of the extracted function. /// \param [in,out] OutputStoreBBs - The existing output blocks. void createSwitchStatement( Module &M, OutlinableGroup &OG, DenseMap<Value *, BasicBlock *> &EndBBs, std::vector<DenseMap<Value *, BasicBlock *>> &OutputStoreBBs) { … } /// 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. /// /// \param [in] M - The module we are outlining from. /// \param [in] CurrentGroup - The group of regions to be outlined. /// \param [in,out] OutputStoreBBs - The output blocks for each different /// set of stores needed for the different functions. /// \param [in,out] FuncsToRemove - Extracted functions to erase from module /// once outlining is complete. /// \param [in] OutputMappings - Extracted functions to erase from module /// once outlining is complete. static void fillOverallFunction( Module &M, OutlinableGroup &CurrentGroup, std::vector<DenseMap<Value *, BasicBlock *>> &OutputStoreBBs, std::vector<Function *> &FuncsToRemove, const DenseMap<Value *, Value *> &OutputMappings) { … } void IROutliner::deduplicateExtractedSections( Module &M, OutlinableGroup &CurrentGroup, std::vector<Function *> &FuncsToRemove, unsigned &OutlinedFunctionNum) { … } /// 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. /// /// \param ID - The IRInstructionData to check the next instruction of. /// \returns true if the InstructionDataList and actual instruction match. static bool nextIRInstructionDataMatchesNextInst(IRInstructionData &ID) { … } bool IROutliner::isCompatibleWithAlreadyOutlinedCode( const OutlinableRegion &Region) { … } void IROutliner::pruneIncompatibleRegions( std::vector<IRSimilarityCandidate> &CandidateVec, OutlinableGroup &CurrentGroup) { … } InstructionCost IROutliner::findBenefitFromAllRegions(OutlinableGroup &CurrentGroup) { … } /// For the \p 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. /// /// \param Region - The OutlinableRegion to get the Value from. /// \param OutputCanon - The canonical number to find the Value from. /// \returns The Value represented by a canonical number \p OutputCanon in \p /// Region. static Value *findOutputValueInRegion(OutlinableRegion &Region, unsigned OutputCanon) { … } InstructionCost IROutliner::findCostOutputReloads(OutlinableGroup &CurrentGroup) { … } /// Find the extra instructions needed to handle any output values for the /// region. /// /// \param [in] M - The Module to outline from. /// \param [in] CurrentGroup - The collection of OutlinableRegions to analyze. /// \param [in] TTI - The TargetTransformInfo used to collect information for /// new instruction costs. /// \returns the additional cost to handle the outputs. static InstructionCost findCostForOutputBlocks(Module &M, OutlinableGroup &CurrentGroup, TargetTransformInfo &TTI) { … } void IROutliner::findCostBenefit(Module &M, OutlinableGroup &CurrentGroup) { … } void IROutliner::updateOutputMapping(OutlinableRegion &Region, ArrayRef<Value *> Outputs, LoadInst *LI) { … } bool IROutliner::extractSection(OutlinableRegion &Region) { … } unsigned IROutliner::doOutline(Module &M) { … } bool IROutliner::run(Module &M) { … } PreservedAnalyses IROutlinerPass::run(Module &M, ModuleAnalysisManager &AM) { … }
Codebase Browser
llvm