Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- 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<unsigned, unsigned> ExtractedArgToAgg;

  DenseMap<unsigned, unsigned> 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<Value *, Value *> 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<Value *, BasicBlock *> 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<unsigned, Constant *> 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<unsigned, 4> 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<TargetTransformInfo &(Function &)> GTTI,

             function_ref<IRSimilarityIdentifier &(Module &)> GIRSI,

             function_ref<OptimizationRemarkEmitter &(Function &)> GORE)

      : getTTI(GTTI), getIRSI(GIRSI), getORE(GORE) {

    // Check that the DenseMap implementation has not changed.

    assert(DenseMapInfo<unsigned>::getEmptyKey() == (unsigned)-1 &&

           "DenseMapInfo<unsigned>'s empty key isn't -1!");

    assert(DenseMapInfo<unsigned>::getTombstoneKey() == (unsigned)-2 &&

           "DenseMapInfo<unsigned>'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<IRSimilarityCandidate> &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<unsigned> &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<Value *> 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<Function *> &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<unsigned> Outlined;

  /// TargetTransformInfo lambda for target specific information.

  function_ref<TargetTransformInfo &(Function &)> 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<Value *, Value *> OutputMappings;

  /// IRSimilarityIdentifier lambda to retrieve IRSimilarityIdentifier.

  function_ref<IRSimilarityIdentifier &(Module &)> getIRSI;

  /// The optimization remark emitter for the pass.

  function_ref<OptimizationRemarkEmitter &(Function &)> getORE;

  /// The memory allocator used to allocate the CodeExtractors.

  SpecificBumpPtrAllocator<CodeExtractor> ExtractorAllocator;

  /// The memory allocator used to allocate the OutlinableRegions.

  SpecificBumpPtrAllocator<OutlinableRegion> RegionAllocator;

  /// The memory allocator used to allocate new IRInstructionData.

  SpecificBumpPtrAllocator<IRInstructionData> 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, bool> {

    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<IROutlinerPass> {

public:

  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);

};

} // end namespace llvm

#endif // LLVM_TRANSFORMS_IPO_IROUTLINER_H