//===- IROutliner.h - Extract similar IR regions into functions --*- 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 // The interface file for the IROutliner which is used by the IROutliner Pass. // // The outliner uses the IRSimilarityIdentifier to identify the similar regions // of code. It evaluates each set of IRSimilarityCandidates with an estimate of // whether it will provide code size reduction. Each region is extracted using // the code extractor. These extracted functions are consolidated into a single // function and called from the extracted call site. // // For example: // \code // %1 = add i32 %a, %b // %2 = add i32 %b, %a // %3 = add i32 %b, %a // %4 = add i32 %a, %b // \endcode // would become function // \code // define internal void outlined_ir_function(i32 %0, i32 %1) { // %1 = add i32 %0, %1 // %2 = add i32 %1, %0 // ret void // } // \endcode // with calls: // \code // call void outlined_ir_function(i32 %a, i32 %b) // call void outlined_ir_function(i32 %b, i32 %a) // \endcode // //===----------------------------------------------------------------------===// #ifndef LLVM_TRANSFORMS_IPO_IROUTLINER_H #define LLVM_TRANSFORMS_IPO_IROUTLINER_H #include "llvm/Analysis/IRSimilarityIdentifier.h" #include "llvm/IR/PassManager.h" #include "llvm/Support/InstructionCost.h" #include "llvm/Transforms/Utils/CodeExtractor.h" struct OutlinableGroup; namespace llvm { using namespace CallingConv; using namespace IRSimilarity; class Module; class TargetTransformInfo; class OptimizationRemarkEmitter; /// The OutlinableRegion holds all the information for a specific region, or /// sequence of instructions. This includes what values need to be hoisted to /// arguments from the extracted function, inputs and outputs to the region, and /// mapping from the extracted function arguments to overall function arguments. struct OutlinableRegion { /// Describes the region of code. IRSimilarityCandidate *Candidate = nullptr; /// If this region is outlined, the front and back IRInstructionData could /// potentially become invalidated if the only new instruction is a call. /// This ensures that we replace in the instruction in the IRInstructionData. IRInstructionData *NewFront = nullptr; IRInstructionData *NewBack = nullptr; /// The number of extracted inputs from the CodeExtractor. unsigned NumExtractedInputs = 0; /// The corresponding BasicBlock with the appropriate stores for this /// OutlinableRegion in the overall function. unsigned OutputBlockNum = -1; /// Mapping the extracted argument number to the argument number in the /// overall function. Since there will be inputs, such as elevated constants /// that are not the same in each region in a SimilarityGroup, or values that /// cannot be sunk into the extracted section in every region, we must keep /// track of which extracted argument maps to which overall argument. DenseMap ExtractedArgToAgg; DenseMap AggArgToExtracted; /// Values in the outlined functions will often be replaced by arguments. When /// finding corresponding values from one region to another, the found value /// will be the value the argument previously replaced. This structure maps /// any replaced values for the region to the aggregate aggregate argument /// in the overall function. DenseMap RemappedArguments; /// Marks whether we need to change the order of the arguments when mapping /// the old extracted function call to the new aggregate outlined function /// call. bool ChangedArgOrder = false; /// Marks whether this region ends in a branch, there is special handling /// required for the following basic blocks in this case. bool EndsInBranch = false; /// The PHIBlocks with their corresponding return block based on the return /// value as the key. DenseMap PHIBlocks; /// Mapping of the argument number in the deduplicated function /// to a given constant, which is used when creating the arguments to the call /// to the newly created deduplicated function. This is handled separately /// since the CodeExtractor does not recognize constants. DenseMap AggArgToConstant; /// The global value numbers that are used as outputs for this section. Once /// extracted, each output will be stored to an output register. This /// documents the global value numbers that are used in this pattern. SmallVector GVNStores; /// Used to create an outlined function. CodeExtractor *CE = nullptr; /// The call site of the extracted region. CallInst *Call = nullptr; /// The function for the extracted region. Function *ExtractedFunction = nullptr; /// Flag for whether we have split out the IRSimilarityCanidate. That is, /// make the region contained the IRSimilarityCandidate its own BasicBlock. bool CandidateSplit = false; /// Flag for whether we should not consider this region for extraction. bool IgnoreRegion = false; /// The BasicBlock that is before the start of the region BasicBlock, /// only defined when the region has been split. BasicBlock *PrevBB = nullptr; /// The BasicBlock that contains the starting instruction of the region. BasicBlock *StartBB = nullptr; /// The BasicBlock that contains the ending instruction of the region. BasicBlock *EndBB = nullptr; /// The BasicBlock that is after the start of the region BasicBlock, /// only defined when the region has been split. BasicBlock *FollowBB = nullptr; /// The Outlinable Group that contains this region and structurally similar /// regions to this region. OutlinableGroup *Parent = nullptr; OutlinableRegion(IRSimilarityCandidate &C, OutlinableGroup &Group) : Candidate(&C), Parent(&Group) { StartBB = C.getStartBB(); EndBB = C.getEndBB(); } /// For the contained region, split the parent BasicBlock at the starting and /// ending instructions of the contained IRSimilarityCandidate. void splitCandidate(); /// For the contained region, reattach the BasicBlock at the starting and /// ending instructions of the contained IRSimilarityCandidate, or if the /// function has been extracted, the start and end of the BasicBlock /// containing the called function. void reattachCandidate(); /// Find a corresponding value for \p V in similar OutlinableRegion \p Other. /// /// \param Other [in] - The OutlinableRegion to find the corresponding Value /// in. /// \param V [in] - The Value to look for in the other region. /// \return The corresponding Value to \p V if it exists, otherwise nullptr. Value *findCorrespondingValueIn(const OutlinableRegion &Other, Value *V); /// Find a corresponding BasicBlock for \p BB in similar OutlinableRegion \p Other. /// /// \param Other [in] - The OutlinableRegion to find the corresponding /// BasicBlock in. /// \param BB [in] - The BasicBlock to look for in the other region. /// \return The corresponding Value to \p V if it exists, otherwise nullptr. BasicBlock *findCorrespondingBlockIn(const OutlinableRegion &Other, BasicBlock *BB); /// Get the size of the code removed from the region. /// /// \param [in] TTI - The TargetTransformInfo for the parent function. /// \returns the code size of the region InstructionCost getBenefit(TargetTransformInfo &TTI); }; /// This class is a pass that identifies similarity in a Module, extracts /// instances of the similarity, and then consolidating the similar regions /// in an effort to reduce code size. It uses the IRSimilarityIdentifier pass /// to identify the similar regions of code, and then extracts the similar /// sections into a single function. See the above for an example as to /// how code is extracted and consolidated into a single function. class IROutliner { public: IROutliner(function_ref GTTI, function_ref GIRSI, function_ref GORE) : getTTI(GTTI), getIRSI(GIRSI), getORE(GORE) { // Check that the DenseMap implementation has not changed. assert(DenseMapInfo::getEmptyKey() == (unsigned)-1 && "DenseMapInfo's empty key isn't -1!"); assert(DenseMapInfo::getTombstoneKey() == (unsigned)-2 && "DenseMapInfo's tombstone key isn't -2!"); } bool run(Module &M); private: /// Find repeated similar code sequences in \p M and outline them into new /// Functions. /// /// \param [in] M - The module to outline from. /// \returns The number of Functions created. unsigned doOutline(Module &M); /// Check whether an OutlinableRegion is incompatible with code already /// outlined. OutlinableRegions are incomptaible when there are overlapping /// instructions, or code that has not been recorded has been added to the /// instructions. /// /// \param [in] Region - The OutlinableRegion to check for conflicts with /// already outlined code. /// \returns whether the region can safely be outlined. bool isCompatibleWithAlreadyOutlinedCode(const OutlinableRegion &Region); /// Remove all the IRSimilarityCandidates from \p CandidateVec that have /// instructions contained in a previously outlined region and put the /// remaining regions in \p CurrentGroup. /// /// \param [in] CandidateVec - List of similarity candidates for regions with /// the same similarity structure. /// \param [in,out] CurrentGroup - Contains the potential sections to /// be outlined. void pruneIncompatibleRegions(std::vector &CandidateVec, OutlinableGroup &CurrentGroup); /// Create the function based on the overall types found in the current /// regions being outlined. /// /// \param M - The module to outline from. /// \param [in,out] CG - The OutlinableGroup for the regions to be outlined. /// \param [in] FunctionNameSuffix - How many functions have we previously /// created. /// \returns the newly created function. Function *createFunction(Module &M, OutlinableGroup &CG, unsigned FunctionNameSuffix); /// Identify the needed extracted inputs in a section, and add to the overall /// function if needed. /// /// \param [in] M - The module to outline from. /// \param [in,out] Region - The region to be extracted. /// \param [in] NotSame - The global value numbers of the Values in the region /// that do not have the same Constant in each strucutrally similar region. void findAddInputsOutputs(Module &M, OutlinableRegion &Region, DenseSet &NotSame); /// Find the number of instructions that will be removed by extracting the /// OutlinableRegions in \p CurrentGroup. /// /// \param [in] CurrentGroup - The collection of OutlinableRegions to be /// analyzed. /// \returns the number of outlined instructions across all regions. InstructionCost findBenefitFromAllRegions(OutlinableGroup &CurrentGroup); /// Find the number of instructions that will be added by reloading arguments. /// /// \param [in] CurrentGroup - The collection of OutlinableRegions to be /// analyzed. /// \returns the number of added reload instructions across all regions. InstructionCost findCostOutputReloads(OutlinableGroup &CurrentGroup); /// Find the cost and the benefit of \p CurrentGroup and save it back to /// \p CurrentGroup. /// /// \param [in] M - The module being analyzed /// \param [in,out] CurrentGroup - The overall outlined section void findCostBenefit(Module &M, OutlinableGroup &CurrentGroup); /// Update the output mapping based on the load instruction, and the outputs /// of the extracted function. /// /// \param Region - The region extracted /// \param Outputs - The outputs from the extracted function. /// \param LI - The load instruction used to update the mapping. void updateOutputMapping(OutlinableRegion &Region, ArrayRef Outputs, LoadInst *LI); /// Extract \p Region into its own function. /// /// \param [in] Region - The region to be extracted into its own function. /// \returns True if it was successfully outlined. bool extractSection(OutlinableRegion &Region); /// For the similarities found, and the extracted sections, create a single /// outlined function with appropriate output blocks as necessary. /// /// \param [in] M - The module to outline from /// \param [in] CurrentGroup - The set of extracted sections to consolidate. /// \param [in,out] FuncsToRemove - List of functions to remove from the /// module after outlining is completed. /// \param [in,out] OutlinedFunctionNum - the number of new outlined /// functions. void deduplicateExtractedSections(Module &M, OutlinableGroup &CurrentGroup, std::vector &FuncsToRemove, unsigned &OutlinedFunctionNum); /// If true, enables us to outline from functions that have LinkOnceFromODR /// linkages. bool OutlineFromLinkODRs = false; /// If false, we do not worry if the cost is greater than the benefit. This /// is for debugging and testing, so that we can test small cases to ensure /// that the outlining is being done correctly. bool CostModel = true; /// The set of outlined Instructions, identified by their location in the /// sequential ordering of instructions in a Module. DenseSet Outlined; /// TargetTransformInfo lambda for target specific information. function_ref getTTI; /// A mapping from newly created reloaded output values to the original value. /// If an value is replace by an output from an outlined region, this maps /// that Value, back to its original Value. DenseMap OutputMappings; /// IRSimilarityIdentifier lambda to retrieve IRSimilarityIdentifier. function_ref getIRSI; /// The optimization remark emitter for the pass. function_ref getORE; /// The memory allocator used to allocate the CodeExtractors. SpecificBumpPtrAllocator ExtractorAllocator; /// The memory allocator used to allocate the OutlinableRegions. SpecificBumpPtrAllocator RegionAllocator; /// The memory allocator used to allocate new IRInstructionData. SpecificBumpPtrAllocator InstDataAllocator; /// Custom InstVisitor to classify different instructions for whether it can /// be analyzed for similarity. This is needed as there may be instruction we /// can identify as having similarity, but are more complicated to outline. struct InstructionAllowed : public InstVisitor { InstructionAllowed() = default; bool visitBranchInst(BranchInst &BI) { return EnableBranches; } bool visitPHINode(PHINode &PN) { return EnableBranches; } // TODO: Handle allocas. bool visitAllocaInst(AllocaInst &AI) { return false; } // VAArg instructions are not allowed since this could cause difficulty when // differentiating between different sets of variable instructions in // the deduplicated outlined regions. bool visitVAArgInst(VAArgInst &VI) { return false; } // We exclude all exception handling cases since they are so context // dependent. bool visitLandingPadInst(LandingPadInst &LPI) { return false; } bool visitFuncletPadInst(FuncletPadInst &FPI) { return false; } // DebugInfo should be included in the regions, but should not be // analyzed for similarity as it has no bearing on the outcome of the // program. bool visitDbgInfoIntrinsic(DbgInfoIntrinsic &DII) { return true; } // TODO: Handle specific intrinsics individually from those that can be // handled. bool IntrinsicInst(IntrinsicInst &II) { return EnableIntrinsics; } // We only handle CallInsts that are not indirect, since we cannot guarantee // that they have a name in these cases. bool visitCallInst(CallInst &CI) { Function *F = CI.getCalledFunction(); bool IsIndirectCall = CI.isIndirectCall(); if (IsIndirectCall && !EnableIndirectCalls) return false; if (!F && !IsIndirectCall) return false; // Returning twice can cause issues with the state of the function call // that were not expected when the function was used, so we do not include // the call in outlined functions. if (CI.canReturnTwice()) return false; // TODO: Update the outliner to capture whether the outlined function // needs these extra attributes. // Functions marked with the swifttailcc and tailcc calling conventions // require special handling when outlining musttail functions. The // calling convention must be passed down to the outlined function as // well. Further, there is special handling for musttail calls as well, // requiring a return call directly after. For now, the outliner does not // support this. bool IsTailCC = CI.getCallingConv() == CallingConv::SwiftTail || CI.getCallingConv() == CallingConv::Tail; if (IsTailCC && !EnableMustTailCalls) return false; if (CI.isMustTailCall() && !EnableMustTailCalls) return false; // The outliner can only handle musttail items if it is also accompanied // by the tailcc or swifttailcc calling convention. if (CI.isMustTailCall() && !IsTailCC) return false; return true; } // TODO: Handle FreezeInsts. Since a frozen value could be frozen inside // the outlined region, and then returned as an output, this will have to be // handled differently. bool visitFreezeInst(FreezeInst &CI) { return false; } // TODO: We do not current handle similarity that changes the control flow. bool visitInvokeInst(InvokeInst &II) { return false; } // TODO: We do not current handle similarity that changes the control flow. bool visitCallBrInst(CallBrInst &CBI) { return false; } // TODO: Handle interblock similarity. bool visitTerminator(Instruction &I) { return false; } bool visitInstruction(Instruction &I) { return true; } // The flag variable that marks whether we should allow branch instructions // to be outlined. bool EnableBranches = false; // The flag variable that marks whether we should allow indirect calls // to be outlined. bool EnableIndirectCalls = true; // The flag variable that marks whether we should allow intrinsics // instructions to be outlined. bool EnableIntrinsics = false; // The flag variable that marks whether we should allow musttail calls. bool EnableMustTailCalls = false; }; /// A InstVisitor used to exclude certain instructions from being outlined. InstructionAllowed InstructionClassifier; }; /// Pass to outline similar regions. class IROutlinerPass : public PassInfoMixin { public: PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); }; } // end namespace llvm #endif // LLVM_TRANSFORMS_IPO_IROUTLINER_H