diff options
Diffstat (limited to 'clang-r353983/include/llvm/Transforms/IPO')
26 files changed, 1920 insertions, 0 deletions
diff --git a/clang-r353983/include/llvm/Transforms/IPO/AlwaysInliner.h b/clang-r353983/include/llvm/Transforms/IPO/AlwaysInliner.h new file mode 100644 index 00000000..64e25230 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/AlwaysInliner.h @@ -0,0 +1,45 @@ +//===-- AlwaysInliner.h - Pass to inline "always_inline" functions --------===// +// +// 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 +/// Provides passes to inlining "always_inline" functions. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_ALWAYSINLINER_H +#define LLVM_TRANSFORMS_IPO_ALWAYSINLINER_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Inlines functions marked as "always_inline". +/// +/// Note that this does not inline call sites marked as always_inline and does +/// not delete the functions even when all users are inlined. The normal +/// inliner should be used to handle call site inlining, this pass's goal is to +/// be the simplest possible pass to remove always_inline function definitions' +/// uses by inlining them. The \c GlobalDCE pass can be used to remove these +/// functions once all users are gone. +class AlwaysInlinerPass : public PassInfoMixin<AlwaysInlinerPass> { + bool InsertLifetime; + +public: + AlwaysInlinerPass(bool InsertLifetime = true) + : InsertLifetime(InsertLifetime) {} + + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); +}; + +/// Create a legacy pass manager instance of a pass to inline and remove +/// functions marked as "always_inline". +Pass *createAlwaysInlinerLegacyPass(bool InsertLifetime = true); + +} + +#endif // LLVM_TRANSFORMS_IPO_ALWAYSINLINER_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/ArgumentPromotion.h b/clang-r353983/include/llvm/Transforms/IPO/ArgumentPromotion.h new file mode 100644 index 00000000..c8afb7bd --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/ArgumentPromotion.h @@ -0,0 +1,35 @@ +//===- ArgumentPromotion.h - Promote by-reference arguments -----*- 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 +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_ARGUMENTPROMOTION_H +#define LLVM_TRANSFORMS_IPO_ARGUMENTPROMOTION_H + +#include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/Analysis/LazyCallGraph.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Argument promotion pass. +/// +/// This pass walks the functions in each SCC and for each one tries to +/// transform it and all of its callers to replace indirect arguments with +/// direct (by-value) arguments. +class ArgumentPromotionPass : public PassInfoMixin<ArgumentPromotionPass> { + unsigned MaxElements; + +public: + ArgumentPromotionPass(unsigned MaxElements = 3u) : MaxElements(MaxElements) {} + + PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, + LazyCallGraph &CG, CGSCCUpdateResult &UR); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_ARGUMENTPROMOTION_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/CalledValuePropagation.h b/clang-r353983/include/llvm/Transforms/IPO/CalledValuePropagation.h new file mode 100644 index 00000000..c2626d08 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/CalledValuePropagation.h @@ -0,0 +1,34 @@ +//===- CalledValuePropagation.h - Propagate called values -------*- 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 +// +//===----------------------------------------------------------------------===// +// +// This file implements a transformation that attaches !callees metadata to +// indirect call sites. For a given call site, the metadata, if present, +// indicates the set of functions the call site could possibly target at +// run-time. This metadata is added to indirect call sites when the set of +// possible targets can be determined by analysis and is known to be small. The +// analysis driving the transformation is similar to constant propagation and +// makes uses of the generic sparse propagation solver. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_CALLEDVALUEPROPAGATION_H +#define LLVM_TRANSFORMS_IPO_CALLEDVALUEPROPAGATION_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class CalledValuePropagationPass + : public PassInfoMixin<CalledValuePropagationPass> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); +}; +} // namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_CALLEDVALUEPROPAGATION_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/ConstantMerge.h b/clang-r353983/include/llvm/Transforms/IPO/ConstantMerge.h new file mode 100644 index 00000000..12d38b5f --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/ConstantMerge.h @@ -0,0 +1,36 @@ +//===- ConstantMerge.h - Merge duplicate global constants -------*- 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 +// +//===----------------------------------------------------------------------===// +// +// This file defines the interface to a pass that merges duplicate global +// constants together into a single constant that is shared. This is useful +// because some passes (ie TraceValues) insert a lot of string constants into +// the program, regardless of whether or not an existing string is available. +// +// Algorithm: ConstantMerge is designed to build up a map of available constants +// and eliminate duplicates when it is initialized. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_CONSTANTMERGE_H +#define LLVM_TRANSFORMS_IPO_CONSTANTMERGE_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class Module; + +/// A pass that merges duplicate global constants into a single constant. +class ConstantMergePass : public PassInfoMixin<ConstantMergePass> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_CONSTANTMERGE_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/CrossDSOCFI.h b/clang-r353983/include/llvm/Transforms/IPO/CrossDSOCFI.h new file mode 100644 index 00000000..8440df63 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/CrossDSOCFI.h @@ -0,0 +1,27 @@ +//===-- CrossDSOCFI.cpp - Externalize this module's CFI checks --*- 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 +// +//===----------------------------------------------------------------------===// +// +// This pass exports all llvm.bitset's found in the module in the form of a +// __cfi_check function, which can be used to verify cross-DSO call targets. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_CROSSDSOCFI_H +#define LLVM_TRANSFORMS_IPO_CROSSDSOCFI_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { +class CrossDSOCFIPass : public PassInfoMixin<CrossDSOCFIPass> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); +}; +} +#endif // LLVM_TRANSFORMS_IPO_CROSSDSOCFI_H + diff --git a/clang-r353983/include/llvm/Transforms/IPO/DeadArgumentElimination.h b/clang-r353983/include/llvm/Transforms/IPO/DeadArgumentElimination.h new file mode 100644 index 00000000..73797bc1 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/DeadArgumentElimination.h @@ -0,0 +1,143 @@ +//===- DeadArgumentElimination.h - Eliminate Dead Args ----------*- 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 +// +//===----------------------------------------------------------------------===// +// +// This pass deletes dead arguments from internal functions. Dead argument +// elimination removes arguments which are directly dead, as well as arguments +// only passed into function calls as dead arguments of other functions. This +// pass also deletes dead return values in a similar way. +// +// This pass is often useful as a cleanup pass to run after aggressive +// interprocedural passes, which add possibly-dead arguments or return values. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H +#define LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H + +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Twine.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" +#include <map> +#include <set> +#include <string> +#include <tuple> + +namespace llvm { + +class Module; +class Use; +class Value; + +/// Eliminate dead arguments (and return values) from functions. +class DeadArgumentEliminationPass + : public PassInfoMixin<DeadArgumentEliminationPass> { +public: + /// Struct that represents (part of) either a return value or a function + /// argument. Used so that arguments and return values can be used + /// interchangeably. + struct RetOrArg { + const Function *F; + unsigned Idx; + bool IsArg; + + RetOrArg(const Function *F, unsigned Idx, bool IsArg) + : F(F), Idx(Idx), IsArg(IsArg) {} + + /// Make RetOrArg comparable, so we can put it into a map. + bool operator<(const RetOrArg &O) const { + return std::tie(F, Idx, IsArg) < std::tie(O.F, O.Idx, O.IsArg); + } + + /// Make RetOrArg comparable, so we can easily iterate the multimap. + bool operator==(const RetOrArg &O) const { + return F == O.F && Idx == O.Idx && IsArg == O.IsArg; + } + + std::string getDescription() const { + return (Twine(IsArg ? "Argument #" : "Return value #") + Twine(Idx) + + " of function " + F->getName()) + .str(); + } + }; + + /// Liveness enum - During our initial pass over the program, we determine + /// that things are either alive or maybe alive. We don't mark anything + /// explicitly dead (even if we know they are), since anything not alive + /// with no registered uses (in Uses) will never be marked alive and will + /// thus become dead in the end. + enum Liveness { Live, MaybeLive }; + + DeadArgumentEliminationPass(bool ShouldHackArguments_ = false) + : ShouldHackArguments(ShouldHackArguments_) {} + + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); + + /// Convenience wrapper + RetOrArg CreateRet(const Function *F, unsigned Idx) { + return RetOrArg(F, Idx, false); + } + + /// Convenience wrapper + RetOrArg CreateArg(const Function *F, unsigned Idx) { + return RetOrArg(F, Idx, true); + } + + using UseMap = std::multimap<RetOrArg, RetOrArg>; + + /// This maps a return value or argument to any MaybeLive return values or + /// arguments it uses. This allows the MaybeLive values to be marked live + /// when any of its users is marked live. + /// For example (indices are left out for clarity): + /// - Uses[ret F] = ret G + /// This means that F calls G, and F returns the value returned by G. + /// - Uses[arg F] = ret G + /// This means that some function calls G and passes its result as an + /// argument to F. + /// - Uses[ret F] = arg F + /// This means that F returns one of its own arguments. + /// - Uses[arg F] = arg G + /// This means that G calls F and passes one of its own (G's) arguments + /// directly to F. + UseMap Uses; + + using LiveSet = std::set<RetOrArg>; + using LiveFuncSet = std::set<const Function *>; + + /// This set contains all values that have been determined to be live. + LiveSet LiveValues; + + /// This set contains all values that are cannot be changed in any way. + LiveFuncSet LiveFunctions; + + using UseVector = SmallVector<RetOrArg, 5>; + + /// This allows this pass to do double-duty as the dead arg hacking pass + /// (used only by bugpoint). + bool ShouldHackArguments = false; + +private: + Liveness MarkIfNotLive(RetOrArg Use, UseVector &MaybeLiveUses); + Liveness SurveyUse(const Use *U, UseVector &MaybeLiveUses, + unsigned RetValNum = -1U); + Liveness SurveyUses(const Value *V, UseVector &MaybeLiveUses); + + void SurveyFunction(const Function &F); + void MarkValue(const RetOrArg &RA, Liveness L, + const UseVector &MaybeLiveUses); + void MarkLive(const RetOrArg &RA); + void MarkLive(const Function &F); + void PropagateLiveness(const RetOrArg &RA); + bool RemoveDeadStuffFromFunction(Function *F); + bool DeleteDeadVarargs(Function &Fn); + bool RemoveDeadArgumentsFromCallers(Function &Fn); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_DEADARGUMENTELIMINATION_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/ElimAvailExtern.h b/clang-r353983/include/llvm/Transforms/IPO/ElimAvailExtern.h new file mode 100644 index 00000000..92c319b3 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/ElimAvailExtern.h @@ -0,0 +1,32 @@ +//===- ElimAvailExtern.h - Optimize Global Variables ------------*- 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 +// +//===----------------------------------------------------------------------===// +// +// This transform is designed to eliminate available external global +// definitions from the program, turning them into declarations. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_ELIMAVAILEXTERN_H +#define LLVM_TRANSFORMS_IPO_ELIMAVAILEXTERN_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class Module; + +/// A pass that transforms external global definitions into declarations. +class EliminateAvailableExternallyPass + : public PassInfoMixin<EliminateAvailableExternallyPass> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_ELIMAVAILEXTERN_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/ForceFunctionAttrs.h b/clang-r353983/include/llvm/Transforms/IPO/ForceFunctionAttrs.h new file mode 100644 index 00000000..7379009b --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/ForceFunctionAttrs.h @@ -0,0 +1,32 @@ +//===-- ForceFunctionAttrs.h - Force function attrs for debugging ---------===// +// +// 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 +/// Super simple passes to force specific function attrs from the commandline +/// into the IR for debugging purposes. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_FORCEFUNCTIONATTRS_H +#define LLVM_TRANSFORMS_IPO_FORCEFUNCTIONATTRS_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Pass which forces specific function attributes into the IR, primarily as +/// a debugging tool. +struct ForceFunctionAttrsPass : PassInfoMixin<ForceFunctionAttrsPass> { + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); +}; + +/// Create a legacy pass manager instance of a pass to force function attrs. +Pass *createForceFunctionAttrsLegacyPass(); + +} + +#endif // LLVM_TRANSFORMS_IPO_FORCEFUNCTIONATTRS_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/FunctionAttrs.h b/clang-r353983/include/llvm/Transforms/IPO/FunctionAttrs.h new file mode 100644 index 00000000..ce61eea0 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/FunctionAttrs.h @@ -0,0 +1,77 @@ +//===- FunctionAttrs.h - Compute function attributes ------------*- 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 +/// Provides passes for computing function attributes based on interprocedural +/// analyses. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H +#define LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H + +#include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/Analysis/LazyCallGraph.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class AAResults; +class Function; +class Module; +class Pass; + +/// The three kinds of memory access relevant to 'readonly' and +/// 'readnone' attributes. +enum MemoryAccessKind { + MAK_ReadNone = 0, + MAK_ReadOnly = 1, + MAK_MayWrite = 2, + MAK_WriteOnly = 3 +}; + +/// Returns the memory access properties of this copy of the function. +MemoryAccessKind computeFunctionBodyMemoryAccess(Function &F, AAResults &AAR); + +/// Computes function attributes in post-order over the call graph. +/// +/// By operating in post-order, this pass computes precise attributes for +/// called functions prior to processsing their callers. This "bottom-up" +/// approach allows powerful interprocedural inference of function attributes +/// like memory access patterns, etc. It can discover functions that do not +/// access memory, or only read memory, and give them the readnone/readonly +/// attribute. It also discovers function arguments that are not captured by +/// the function and marks them with the nocapture attribute. +struct PostOrderFunctionAttrsPass : PassInfoMixin<PostOrderFunctionAttrsPass> { + PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, + LazyCallGraph &CG, CGSCCUpdateResult &UR); +}; + +/// Create a legacy pass manager instance of a pass to compute function attrs +/// in post-order. +Pass *createPostOrderFunctionAttrsLegacyPass(); + +/// A pass to do RPO deduction and propagation of function attributes. +/// +/// This pass provides a general RPO or "top down" propagation of +/// function attributes. For a few (rare) cases, we can deduce significantly +/// more about function attributes by working in RPO, so this pass +/// provides the complement to the post-order pass above where the majority of +/// deduction is performed. +// FIXME: Currently there is no RPO CGSCC pass structure to slide into and so +// this is a boring module pass, but eventually it should be an RPO CGSCC pass +// when such infrastructure is available. +class ReversePostOrderFunctionAttrsPass + : public PassInfoMixin<ReversePostOrderFunctionAttrsPass> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/FunctionImport.h b/clang-r353983/include/llvm/Transforms/IPO/FunctionImport.h new file mode 100644 index 00000000..bbf270c4 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/FunctionImport.h @@ -0,0 +1,223 @@ +//===- llvm/Transforms/IPO/FunctionImport.h - ThinLTO importing -*- 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 +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_FUNCTIONIMPORT_H +#define LLVM_TRANSFORMS_IPO_FUNCTIONIMPORT_H + +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/StringMap.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/IR/GlobalValue.h" +#include "llvm/IR/ModuleSummaryIndex.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Support/Error.h" +#include <functional> +#include <map> +#include <memory> +#include <string> +#include <system_error> +#include <unordered_set> +#include <utility> + +namespace llvm { + +class Module; + +/// The function importer is automatically importing function from other modules +/// based on the provided summary informations. +class FunctionImporter { +public: + /// Set of functions to import from a source module. Each entry is a set + /// containing all the GUIDs of all functions to import for a source module. + using FunctionsToImportTy = std::unordered_set<GlobalValue::GUID>; + + /// The different reasons selectCallee will chose not to import a + /// candidate. + enum ImportFailureReason { + None, + // We can encounter a global variable instead of a function in rare + // situations with SamplePGO. See comments where this failure type is + // set for more details. + GlobalVar, + // Found to be globally dead, so we don't bother importing. + NotLive, + // Instruction count over the current threshold. + TooLarge, + // Don't import something with interposable linkage as we can't inline it + // anyway. + InterposableLinkage, + // Generally we won't end up failing due to this reason, as we expect + // to find at least one summary for the GUID that is global or a local + // in the referenced module for direct calls. + LocalLinkageNotInModule, + // This corresponds to the NotEligibleToImport being set on the summary, + // which can happen in a few different cases (e.g. local that can't be + // renamed or promoted because it is referenced on a llvm*.used variable). + NotEligible, + // This corresponds to NoInline being set on the function summary, + // which will happen if it is known that the inliner will not be able + // to inline the function (e.g. it is marked with a NoInline attribute). + NoInline + }; + + /// Information optionally tracked for candidates the importer decided + /// not to import. Used for optional stat printing. + struct ImportFailureInfo { + // The ValueInfo corresponding to the candidate. We save an index hash + // table lookup for each GUID by stashing this here. + ValueInfo VI; + // The maximum call edge hotness for all failed imports of this candidate. + CalleeInfo::HotnessType MaxHotness; + // most recent reason for failing to import (doesn't necessarily correspond + // to the attempt with the maximum hotness). + ImportFailureReason Reason; + // The number of times we tried to import candidate but failed. + unsigned Attempts; + ImportFailureInfo(ValueInfo VI, CalleeInfo::HotnessType MaxHotness, + ImportFailureReason Reason, unsigned Attempts) + : VI(VI), MaxHotness(MaxHotness), Reason(Reason), Attempts(Attempts) {} + }; + + /// Map of callee GUID considered for import into a given module to a pair + /// consisting of the largest threshold applied when deciding whether to + /// import it and, if we decided to import, a pointer to the summary instance + /// imported. If we decided not to import, the summary will be nullptr. + using ImportThresholdsTy = + DenseMap<GlobalValue::GUID, + std::tuple<unsigned, const GlobalValueSummary *, + std::unique_ptr<ImportFailureInfo>>>; + + /// The map contains an entry for every module to import from, the key being + /// the module identifier to pass to the ModuleLoader. The value is the set of + /// functions to import. + using ImportMapTy = StringMap<FunctionsToImportTy>; + + /// The set contains an entry for every global value the module exports. + using ExportSetTy = std::unordered_set<GlobalValue::GUID>; + + /// A function of this type is used to load modules referenced by the index. + using ModuleLoaderTy = + std::function<Expected<std::unique_ptr<Module>>(StringRef Identifier)>; + + /// Create a Function Importer. + FunctionImporter(const ModuleSummaryIndex &Index, ModuleLoaderTy ModuleLoader) + : Index(Index), ModuleLoader(std::move(ModuleLoader)) {} + + /// Import functions in Module \p M based on the supplied import list. + Expected<bool> importFunctions(Module &M, const ImportMapTy &ImportList); + +private: + /// The summaries index used to trigger importing. + const ModuleSummaryIndex &Index; + + /// Factory function to load a Module for a given identifier + ModuleLoaderTy ModuleLoader; +}; + +/// The function importing pass +class FunctionImportPass : public PassInfoMixin<FunctionImportPass> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); +}; + +/// Compute all the imports and exports for every module in the Index. +/// +/// \p ModuleToDefinedGVSummaries contains for each Module a map +/// (GUID -> Summary) for every global defined in the module. +/// +/// \p ImportLists will be populated with an entry for every Module we are +/// importing into. This entry is itself a map that can be passed to +/// FunctionImporter::importFunctions() above (see description there). +/// +/// \p ExportLists contains for each Module the set of globals (GUID) that will +/// be imported by another module, or referenced by such a function. I.e. this +/// is the set of globals that need to be promoted/renamed appropriately. +void ComputeCrossModuleImport( + const ModuleSummaryIndex &Index, + const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries, + StringMap<FunctionImporter::ImportMapTy> &ImportLists, + StringMap<FunctionImporter::ExportSetTy> &ExportLists); + +/// Compute all the imports for the given module using the Index. +/// +/// \p ImportList will be populated with a map that can be passed to +/// FunctionImporter::importFunctions() above (see description there). +void ComputeCrossModuleImportForModule( + StringRef ModulePath, const ModuleSummaryIndex &Index, + FunctionImporter::ImportMapTy &ImportList); + +/// Mark all external summaries in \p Index for import into the given module. +/// Used for distributed builds using a distributed index. +/// +/// \p ImportList will be populated with a map that can be passed to +/// FunctionImporter::importFunctions() above (see description there). +void ComputeCrossModuleImportForModuleFromIndex( + StringRef ModulePath, const ModuleSummaryIndex &Index, + FunctionImporter::ImportMapTy &ImportList); + +/// PrevailingType enum used as a return type of callback passed +/// to computeDeadSymbols. Yes and No values used when status explicitly +/// set by symbols resolution, otherwise status is Unknown. +enum class PrevailingType { Yes, No, Unknown }; + +/// Compute all the symbols that are "dead": i.e these that can't be reached +/// in the graph from any of the given symbols listed in +/// \p GUIDPreservedSymbols. Non-prevailing symbols are symbols without a +/// prevailing copy anywhere in IR and are normally dead, \p isPrevailing +/// predicate returns status of symbol. +void computeDeadSymbols( + ModuleSummaryIndex &Index, + const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols, + function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing); + +/// Compute dead symbols and run constant propagation in combined index +/// after that. +void computeDeadSymbolsWithConstProp( + ModuleSummaryIndex &Index, + const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols, + function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing, + bool ImportEnabled); + +/// Converts value \p GV to declaration, or replaces with a declaration if +/// it is an alias. Returns true if converted, false if replaced. +bool convertToDeclaration(GlobalValue &GV); + +/// Compute the set of summaries needed for a ThinLTO backend compilation of +/// \p ModulePath. +// +/// This includes summaries from that module (in case any global summary based +/// optimizations were recorded) and from any definitions in other modules that +/// should be imported. +// +/// \p ModuleToSummariesForIndex will be populated with the needed summaries +/// from each required module path. Use a std::map instead of StringMap to get +/// stable order for bitcode emission. +void gatherImportedSummariesForModule( + StringRef ModulePath, + const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries, + const FunctionImporter::ImportMapTy &ImportList, + std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex); + +/// Emit into \p OutputFilename the files module \p ModulePath will import from. +std::error_code EmitImportsFiles( + StringRef ModulePath, StringRef OutputFilename, + const std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex); + +/// Resolve prevailing symbol linkages in \p TheModule based on the information +/// recorded in the summaries during global summary-based analysis. +void thinLTOResolvePrevailingInModule(Module &TheModule, + const GVSummaryMapTy &DefinedGlobals); + +/// Internalize \p TheModule based on the information recorded in the summaries +/// during global summary-based analysis. +void thinLTOInternalizeModule(Module &TheModule, + const GVSummaryMapTy &DefinedGlobals); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_FUNCTIONIMPORT_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/GlobalDCE.h b/clang-r353983/include/llvm/Transforms/IPO/GlobalDCE.h new file mode 100644 index 00000000..c434484d --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/GlobalDCE.h @@ -0,0 +1,56 @@ +//===-- GlobalDCE.h - DCE unreachable internal functions ------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// This transform is designed to eliminate unreachable internal globals from the +// program. It uses an aggressive algorithm, searching out globals that are +// known to be alive. After it finds all of the globals which are needed, it +// deletes whatever is left over. This allows it to delete recursive chunks of +// the program which are unreachable. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_GLOBALDCE_H +#define LLVM_TRANSFORMS_IPO_GLOBALDCE_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" +#include <unordered_map> + +namespace llvm { + +/// Pass to remove unused function declarations. +class GlobalDCEPass : public PassInfoMixin<GlobalDCEPass> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); + +private: + SmallPtrSet<GlobalValue*, 32> AliveGlobals; + + /// Global -> Global that uses this global. + DenseMap<GlobalValue *, SmallPtrSet<GlobalValue *, 4>> GVDependencies; + + /// Constant -> Globals that use this global cache. + std::unordered_map<Constant *, SmallPtrSet<GlobalValue *, 8>> + ConstantDependenciesCache; + + /// Comdat -> Globals in that Comdat section. + std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers; + + void UpdateGVDependencies(GlobalValue &GV); + void MarkLive(GlobalValue &GV, + SmallVectorImpl<GlobalValue *> *Updates = nullptr); + bool RemoveUnusedGlobalValue(GlobalValue &GV); + + void ComputeDependencies(Value *V, SmallPtrSetImpl<GlobalValue *> &U); +}; + +} + +#endif // LLVM_TRANSFORMS_IPO_GLOBALDCE_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/GlobalOpt.h b/clang-r353983/include/llvm/Transforms/IPO/GlobalOpt.h new file mode 100644 index 00000000..48a861ff --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/GlobalOpt.h @@ -0,0 +1,32 @@ +//===- GlobalOpt.h - Optimize Global Variables ------------------*- 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 +// +//===----------------------------------------------------------------------===// +// +// This pass transforms simple global variables that never have their address +// taken. If obviously true, it marks read/write globals as constant, deletes +// variables only stored to, etc. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_GLOBALOPT_H +#define LLVM_TRANSFORMS_IPO_GLOBALOPT_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class Module; + +/// Optimize globals that never have their address taken. +class GlobalOptPass : public PassInfoMixin<GlobalOptPass> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_GLOBALOPT_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/GlobalSplit.h b/clang-r353983/include/llvm/Transforms/IPO/GlobalSplit.h new file mode 100644 index 00000000..690b23a2 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/GlobalSplit.h @@ -0,0 +1,33 @@ +//===- GlobalSplit.h - global variable splitter -----------------*- 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 +// +//===----------------------------------------------------------------------===// +// +// This pass uses inrange annotations on GEP indices to split globals where +// beneficial. Clang currently attaches these annotations to references to +// virtual table globals under the Itanium ABI for the benefit of the +// whole-program virtual call optimization and control flow integrity passes. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_GLOBALSPLIT_H +#define LLVM_TRANSFORMS_IPO_GLOBALSPLIT_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class Module; + +/// Pass to perform split of global variables. +class GlobalSplitPass : public PassInfoMixin<GlobalSplitPass> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_GLOBALSPLIT_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/HotColdSplitting.h b/clang-r353983/include/llvm/Transforms/IPO/HotColdSplitting.h new file mode 100644 index 00000000..73668844 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/HotColdSplitting.h @@ -0,0 +1,30 @@ +//===- HotColdSplitting.h ---- Outline Cold 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 +//===----------------------------------------------------------------------===// +// +// This pass outlines cold regions to a separate function. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_HOTCOLDSPLITTING_H +#define LLVM_TRANSFORMS_IPO_HOTCOLDSPLITTING_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class Module; + +/// Pass to outline cold regions. +class HotColdSplittingPass : public PassInfoMixin<HotColdSplittingPass> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_HOTCOLDSPLITTING_H + diff --git a/clang-r353983/include/llvm/Transforms/IPO/InferFunctionAttrs.h b/clang-r353983/include/llvm/Transforms/IPO/InferFunctionAttrs.h new file mode 100644 index 00000000..bb7907fb --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/InferFunctionAttrs.h @@ -0,0 +1,35 @@ +//===-- InferFunctionAttrs.h - Infer implicit function attributes ---------===// +// +// 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 +/// Interfaces for passes which infer implicit function attributes from the +/// name and signature of function declarations. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_INFERFUNCTIONATTRS_H +#define LLVM_TRANSFORMS_IPO_INFERFUNCTIONATTRS_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// A pass which infers function attributes from the names and signatures of +/// function declarations in a module. +struct InferFunctionAttrsPass : PassInfoMixin<InferFunctionAttrsPass> { + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); +}; + +/// Create a legacy pass manager instance of a pass to infer function +/// attributes. +Pass *createInferFunctionAttrsLegacyPass(); + +} + +#endif // LLVM_TRANSFORMS_IPO_INFERFUNCTIONATTRS_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/Inliner.h b/clang-r353983/include/llvm/Transforms/IPO/Inliner.h new file mode 100644 index 00000000..8202b94d --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/Inliner.h @@ -0,0 +1,113 @@ +//===- Inliner.h - Inliner pass and infrastructure --------------*- 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 +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_INLINER_H +#define LLVM_TRANSFORMS_IPO_INLINER_H + +#include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/Analysis/CallGraphSCCPass.h" +#include "llvm/Analysis/InlineCost.h" +#include "llvm/Analysis/LazyCallGraph.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h" +#include <utility> + +namespace llvm { + +class AssumptionCacheTracker; +class CallGraph; +class ProfileSummaryInfo; + +/// This class contains all of the helper code which is used to perform the +/// inlining operations that do not depend on the policy. It contains the core +/// bottom-up inlining infrastructure that specific inliner passes use. +struct LegacyInlinerBase : public CallGraphSCCPass { + explicit LegacyInlinerBase(char &ID); + explicit LegacyInlinerBase(char &ID, bool InsertLifetime); + + /// For this class, we declare that we require and preserve the call graph. + /// If the derived class implements this method, it should always explicitly + /// call the implementation here. + void getAnalysisUsage(AnalysisUsage &Info) const override; + + bool doInitialization(CallGraph &CG) override; + + /// Main run interface method, this implements the interface required by the + /// Pass class. + bool runOnSCC(CallGraphSCC &SCC) override; + + using llvm::Pass::doFinalization; + + /// Remove now-dead linkonce functions at the end of processing to avoid + /// breaking the SCC traversal. + bool doFinalization(CallGraph &CG) override; + + /// This method must be implemented by the subclass to determine the cost of + /// inlining the specified call site. If the cost returned is greater than + /// the current inline threshold, the call site is not inlined. + virtual InlineCost getInlineCost(CallSite CS) = 0; + + /// Remove dead functions. + /// + /// This also includes a hack in the form of the 'AlwaysInlineOnly' flag + /// which restricts it to deleting functions with an 'AlwaysInline' + /// attribute. This is useful for the InlineAlways pass that only wants to + /// deal with that subset of the functions. + bool removeDeadFunctions(CallGraph &CG, bool AlwaysInlineOnly = false); + + /// This function performs the main work of the pass. The default of + /// Inlinter::runOnSCC() calls skipSCC() before calling this method, but + /// derived classes which cannot be skipped can override that method and call + /// this function unconditionally. + bool inlineCalls(CallGraphSCC &SCC); + +private: + // Insert @llvm.lifetime intrinsics. + bool InsertLifetime = true; + +protected: + AssumptionCacheTracker *ACT; + ProfileSummaryInfo *PSI; + ImportedFunctionsInliningStatistics ImportedFunctionsStats; +}; + +/// The inliner pass for the new pass manager. +/// +/// This pass wires together the inlining utilities and the inline cost +/// analysis into a CGSCC pass. It considers every call in every function in +/// the SCC and tries to inline if profitable. It can be tuned with a number of +/// parameters to control what cost model is used and what tradeoffs are made +/// when making the decision. +/// +/// It should be noted that the legacy inliners do considerably more than this +/// inliner pass does. They provide logic for manually merging allocas, and +/// doing considerable DCE including the DCE of dead functions. This pass makes +/// every attempt to be simpler. DCE of functions requires complex reasoning +/// about comdat groups, etc. Instead, it is expected that other more focused +/// passes be composed to achieve the same end result. +class InlinerPass : public PassInfoMixin<InlinerPass> { +public: + InlinerPass(InlineParams Params = getInlineParams()) + : Params(std::move(Params)) {} + ~InlinerPass(); + InlinerPass(InlinerPass &&Arg) + : Params(std::move(Arg.Params)), + ImportedFunctionsStats(std::move(Arg.ImportedFunctionsStats)) {} + + PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, + LazyCallGraph &CG, CGSCCUpdateResult &UR); + +private: + InlineParams Params; + std::unique_ptr<ImportedFunctionsInliningStatistics> ImportedFunctionsStats; +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_INLINER_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/Internalize.h b/clang-r353983/include/llvm/Transforms/IPO/Internalize.h new file mode 100644 index 00000000..a7efd3e1 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/Internalize.h @@ -0,0 +1,78 @@ +//====- Internalize.h - Internalization API ---------------------*- 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 +// +//===----------------------------------------------------------------------===// +// +// This pass loops over all of the functions and variables in the input module. +// If the function or variable does not need to be preserved according to the +// client supplied callback, it is marked as internal. +// +// This transformation would not be legal in a regular compilation, but it gets +// extra information from the linker about what is safe. +// +// For example: Internalizing a function with external linkage. Only if we are +// told it is only used from within this module, it is safe to do it. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_INTERNALIZE_H +#define LLVM_TRANSFORMS_IPO_INTERNALIZE_H + +#include "llvm/ADT/StringSet.h" +#include "llvm/IR/GlobalValue.h" +#include "llvm/IR/PassManager.h" +#include <functional> +#include <set> + +namespace llvm { +class Module; +class CallGraph; + +/// A pass that internalizes all functions and variables other than those that +/// must be preserved according to \c MustPreserveGV. +class InternalizePass : public PassInfoMixin<InternalizePass> { + /// Client supplied callback to control wheter a symbol must be preserved. + const std::function<bool(const GlobalValue &)> MustPreserveGV; + /// Set of symbols private to the compiler that this pass should not touch. + StringSet<> AlwaysPreserved; + + /// Return false if we're allowed to internalize this GV. + bool shouldPreserveGV(const GlobalValue &GV); + /// Internalize GV if it is possible to do so, i.e. it is not externally + /// visible and is not a member of an externally visible comdat. + bool maybeInternalize(GlobalValue &GV, + const std::set<const Comdat *> &ExternalComdats); + /// If GV is part of a comdat and is externally visible, keep track of its + /// comdat so that we don't internalize any of its members. + void checkComdatVisibility(GlobalValue &GV, + std::set<const Comdat *> &ExternalComdats); + +public: + InternalizePass(); + InternalizePass(std::function<bool(const GlobalValue &)> MustPreserveGV) + : MustPreserveGV(std::move(MustPreserveGV)) {} + + /// Run the internalizer on \p TheModule, returns true if any changes was + /// made. + /// + /// If the CallGraph \p CG is supplied, it will be updated when + /// internalizing a function (by removing any edge from the "external node") + bool internalizeModule(Module &TheModule, CallGraph *CG = nullptr); + + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); +}; + +/// Helper function to internalize functions and variables in a Module. +inline bool +internalizeModule(Module &TheModule, + std::function<bool(const GlobalValue &)> MustPreserveGV, + CallGraph *CG = nullptr) { + return InternalizePass(std::move(MustPreserveGV)) + .internalizeModule(TheModule, CG); +} +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_INTERNALIZE_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/LowerTypeTests.h b/clang-r353983/include/llvm/Transforms/IPO/LowerTypeTests.h new file mode 100644 index 00000000..39b23f59 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/LowerTypeTests.h @@ -0,0 +1,210 @@ +//===- LowerTypeTests.h - type metadata lowering pass -----------*- 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 +// +//===----------------------------------------------------------------------===// +// +// This file defines parts of the type test lowering pass implementation that +// may be usefully unit tested. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H +#define LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H + +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/PassManager.h" +#include <cstdint> +#include <cstring> +#include <limits> +#include <set> +#include <vector> + +namespace llvm { + +class Module; +class ModuleSummaryIndex; +class raw_ostream; + +namespace lowertypetests { + +struct BitSetInfo { + // The indices of the set bits in the bitset. + std::set<uint64_t> Bits; + + // The byte offset into the combined global represented by the bitset. + uint64_t ByteOffset; + + // The size of the bitset in bits. + uint64_t BitSize; + + // Log2 alignment of the bit set relative to the combined global. + // For example, a log2 alignment of 3 means that bits in the bitset + // represent addresses 8 bytes apart. + unsigned AlignLog2; + + bool isSingleOffset() const { + return Bits.size() == 1; + } + + bool isAllOnes() const { + return Bits.size() == BitSize; + } + + bool containsGlobalOffset(uint64_t Offset) const; + + void print(raw_ostream &OS) const; +}; + +struct BitSetBuilder { + SmallVector<uint64_t, 16> Offsets; + uint64_t Min = std::numeric_limits<uint64_t>::max(); + uint64_t Max = 0; + + BitSetBuilder() = default; + + void addOffset(uint64_t Offset) { + if (Min > Offset) + Min = Offset; + if (Max < Offset) + Max = Offset; + + Offsets.push_back(Offset); + } + + BitSetInfo build(); +}; + +/// This class implements a layout algorithm for globals referenced by bit sets +/// that tries to keep members of small bit sets together. This can +/// significantly reduce bit set sizes in many cases. +/// +/// It works by assembling fragments of layout from sets of referenced globals. +/// Each set of referenced globals causes the algorithm to create a new +/// fragment, which is assembled by appending each referenced global in the set +/// into the fragment. If a referenced global has already been referenced by an +/// fragment created earlier, we instead delete that fragment and append its +/// contents into the fragment we are assembling. +/// +/// By starting with the smallest fragments, we minimize the size of the +/// fragments that are copied into larger fragments. This is most intuitively +/// thought about when considering the case where the globals are virtual tables +/// and the bit sets represent their derived classes: in a single inheritance +/// hierarchy, the optimum layout would involve a depth-first search of the +/// class hierarchy (and in fact the computed layout ends up looking a lot like +/// a DFS), but a naive DFS would not work well in the presence of multiple +/// inheritance. This aspect of the algorithm ends up fitting smaller +/// hierarchies inside larger ones where that would be beneficial. +/// +/// For example, consider this class hierarchy: +/// +/// A B +/// \ / | \ +/// C D E +/// +/// We have five bit sets: bsA (A, C), bsB (B, C, D, E), bsC (C), bsD (D) and +/// bsE (E). If we laid out our objects by DFS traversing B followed by A, our +/// layout would be {B, C, D, E, A}. This is optimal for bsB as it needs to +/// cover the only 4 objects in its hierarchy, but not for bsA as it needs to +/// cover 5 objects, i.e. the entire layout. Our algorithm proceeds as follows: +/// +/// Add bsC, fragments {{C}} +/// Add bsD, fragments {{C}, {D}} +/// Add bsE, fragments {{C}, {D}, {E}} +/// Add bsA, fragments {{A, C}, {D}, {E}} +/// Add bsB, fragments {{B, A, C, D, E}} +/// +/// This layout is optimal for bsA, as it now only needs to cover two (i.e. 3 +/// fewer) objects, at the cost of bsB needing to cover 1 more object. +/// +/// The bit set lowering pass assigns an object index to each object that needs +/// to be laid out, and calls addFragment for each bit set passing the object +/// indices of its referenced globals. It then assembles a layout from the +/// computed layout in the Fragments field. +struct GlobalLayoutBuilder { + /// The computed layout. Each element of this vector contains a fragment of + /// layout (which may be empty) consisting of object indices. + std::vector<std::vector<uint64_t>> Fragments; + + /// Mapping from object index to fragment index. + std::vector<uint64_t> FragmentMap; + + GlobalLayoutBuilder(uint64_t NumObjects) + : Fragments(1), FragmentMap(NumObjects) {} + + /// Add F to the layout while trying to keep its indices contiguous. + /// If a previously seen fragment uses any of F's indices, that + /// fragment will be laid out inside F. + void addFragment(const std::set<uint64_t> &F); +}; + +/// This class is used to build a byte array containing overlapping bit sets. By +/// loading from indexed offsets into the byte array and applying a mask, a +/// program can test bits from the bit set with a relatively short instruction +/// sequence. For example, suppose we have 15 bit sets to lay out: +/// +/// A (16 bits), B (15 bits), C (14 bits), D (13 bits), E (12 bits), +/// F (11 bits), G (10 bits), H (9 bits), I (7 bits), J (6 bits), K (5 bits), +/// L (4 bits), M (3 bits), N (2 bits), O (1 bit) +/// +/// These bits can be laid out in a 16-byte array like this: +/// +/// Byte Offset +/// 0123456789ABCDEF +/// Bit +/// 7 HHHHHHHHHIIIIIII +/// 6 GGGGGGGGGGJJJJJJ +/// 5 FFFFFFFFFFFKKKKK +/// 4 EEEEEEEEEEEELLLL +/// 3 DDDDDDDDDDDDDMMM +/// 2 CCCCCCCCCCCCCCNN +/// 1 BBBBBBBBBBBBBBBO +/// 0 AAAAAAAAAAAAAAAA +/// +/// For example, to test bit X of A, we evaluate ((bits[X] & 1) != 0), or to +/// test bit X of I, we evaluate ((bits[9 + X] & 0x80) != 0). This can be done +/// in 1-2 machine instructions on x86, or 4-6 instructions on ARM. +/// +/// This is a byte array, rather than (say) a 2-byte array or a 4-byte array, +/// because for one thing it gives us better packing (the more bins there are, +/// the less evenly they will be filled), and for another, the instruction +/// sequences can be slightly shorter, both on x86 and ARM. +struct ByteArrayBuilder { + /// The byte array built so far. + std::vector<uint8_t> Bytes; + + enum { BitsPerByte = 8 }; + + /// The number of bytes allocated so far for each of the bits. + uint64_t BitAllocs[BitsPerByte]; + + ByteArrayBuilder() { + memset(BitAllocs, 0, sizeof(BitAllocs)); + } + + /// Allocate BitSize bits in the byte array where Bits contains the bits to + /// set. AllocByteOffset is set to the offset within the byte array and + /// AllocMask is set to the bitmask for those bits. This uses the LPT (Longest + /// Processing Time) multiprocessor scheduling algorithm to lay out the bits + /// efficiently; the pass allocates bit sets in decreasing size order. + void allocate(const std::set<uint64_t> &Bits, uint64_t BitSize, + uint64_t &AllocByteOffset, uint8_t &AllocMask); +}; + +} // end namespace lowertypetests + +class LowerTypeTestsPass : public PassInfoMixin<LowerTypeTestsPass> { +public: + ModuleSummaryIndex *ExportSummary; + const ModuleSummaryIndex *ImportSummary; + LowerTypeTestsPass(ModuleSummaryIndex *ExportSummary, + const ModuleSummaryIndex *ImportSummary) + : ExportSummary(ExportSummary), ImportSummary(ImportSummary) {} + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/PartialInlining.h b/clang-r353983/include/llvm/Transforms/IPO/PartialInlining.h new file mode 100644 index 00000000..3b8297d6 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/PartialInlining.h @@ -0,0 +1,31 @@ +//===- PartialInlining.h - Inline parts of 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 +// +//===----------------------------------------------------------------------===// +// +// This pass performs partial inlining, typically by inlining an if statement +// that surrounds the body of the function. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_PARTIALINLINING_H +#define LLVM_TRANSFORMS_IPO_PARTIALINLINING_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class Module; + +/// Pass to remove unused function declarations. +class PartialInlinerPass : public PassInfoMixin<PartialInlinerPass> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_PARTIALINLINING_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/PassManagerBuilder.h b/clang-r353983/include/llvm/Transforms/IPO/PassManagerBuilder.h new file mode 100644 index 00000000..f82cfdc0 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/PassManagerBuilder.h @@ -0,0 +1,216 @@ +// llvm/Transforms/IPO/PassManagerBuilder.h - Build Standard Pass -*- 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 +// +//===----------------------------------------------------------------------===// +// +// This file defines the PassManagerBuilder class, which is used to set up a +// "standard" optimization sequence suitable for languages like C and C++. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_PASSMANAGERBUILDER_H +#define LLVM_TRANSFORMS_IPO_PASSMANAGERBUILDER_H + +#include <functional> +#include <memory> +#include <string> +#include <vector> + +namespace llvm { +class ModuleSummaryIndex; +class Pass; +class TargetLibraryInfoImpl; +class TargetMachine; + +// The old pass manager infrastructure is hidden in a legacy namespace now. +namespace legacy { +class FunctionPassManager; +class PassManagerBase; +} + +/// PassManagerBuilder - This class is used to set up a standard optimization +/// sequence for languages like C and C++, allowing some APIs to customize the +/// pass sequence in various ways. A simple example of using it would be: +/// +/// PassManagerBuilder Builder; +/// Builder.OptLevel = 2; +/// Builder.populateFunctionPassManager(FPM); +/// Builder.populateModulePassManager(MPM); +/// +/// In addition to setting up the basic passes, PassManagerBuilder allows +/// frontends to vend a plugin API, where plugins are allowed to add extensions +/// to the default pass manager. They do this by specifying where in the pass +/// pipeline they want to be added, along with a callback function that adds +/// the pass(es). For example, a plugin that wanted to add a loop optimization +/// could do something like this: +/// +/// static void addMyLoopPass(const PMBuilder &Builder, PassManagerBase &PM) { +/// if (Builder.getOptLevel() > 2 && Builder.getOptSizeLevel() == 0) +/// PM.add(createMyAwesomePass()); +/// } +/// ... +/// Builder.addExtension(PassManagerBuilder::EP_LoopOptimizerEnd, +/// addMyLoopPass); +/// ... +class PassManagerBuilder { +public: + /// Extensions are passed the builder itself (so they can see how it is + /// configured) as well as the pass manager to add stuff to. + typedef std::function<void(const PassManagerBuilder &Builder, + legacy::PassManagerBase &PM)> + ExtensionFn; + enum ExtensionPointTy { + /// EP_EarlyAsPossible - This extension point allows adding passes before + /// any other transformations, allowing them to see the code as it is coming + /// out of the frontend. + EP_EarlyAsPossible, + + /// EP_ModuleOptimizerEarly - This extension point allows adding passes + /// just before the main module-level optimization passes. + EP_ModuleOptimizerEarly, + + /// EP_LoopOptimizerEnd - This extension point allows adding loop passes to + /// the end of the loop optimizer. + EP_LoopOptimizerEnd, + + /// EP_ScalarOptimizerLate - This extension point allows adding optimization + /// passes after most of the main optimizations, but before the last + /// cleanup-ish optimizations. + EP_ScalarOptimizerLate, + + /// EP_OptimizerLast -- This extension point allows adding passes that + /// run after everything else. + EP_OptimizerLast, + + /// EP_VectorizerStart - This extension point allows adding optimization + /// passes before the vectorizer and other highly target specific + /// optimization passes are executed. + EP_VectorizerStart, + + /// EP_EnabledOnOptLevel0 - This extension point allows adding passes that + /// should not be disabled by O0 optimization level. The passes will be + /// inserted after the inlining pass. + EP_EnabledOnOptLevel0, + + /// EP_Peephole - This extension point allows adding passes that perform + /// peephole optimizations similar to the instruction combiner. These passes + /// will be inserted after each instance of the instruction combiner pass. + EP_Peephole, + + /// EP_LateLoopOptimizations - This extension point allows adding late loop + /// canonicalization and simplification passes. This is the last point in + /// the loop optimization pipeline before loop deletion. Each pass added + /// here must be an instance of LoopPass. + /// This is the place to add passes that can remove loops, such as target- + /// specific loop idiom recognition. + EP_LateLoopOptimizations, + + /// EP_CGSCCOptimizerLate - This extension point allows adding CallGraphSCC + /// passes at the end of the main CallGraphSCC passes and before any + /// function simplification passes run by CGPassManager. + EP_CGSCCOptimizerLate, + }; + + /// The Optimization Level - Specify the basic optimization level. + /// 0 = -O0, 1 = -O1, 2 = -O2, 3 = -O3 + unsigned OptLevel; + + /// SizeLevel - How much we're optimizing for size. + /// 0 = none, 1 = -Os, 2 = -Oz + unsigned SizeLevel; + + /// LibraryInfo - Specifies information about the runtime library for the + /// optimizer. If this is non-null, it is added to both the function and + /// per-module pass pipeline. + TargetLibraryInfoImpl *LibraryInfo; + + /// Inliner - Specifies the inliner to use. If this is non-null, it is + /// added to the per-module passes. + Pass *Inliner; + + /// The module summary index to use for exporting information from the + /// regular LTO phase, for example for the CFI and devirtualization type + /// tests. + ModuleSummaryIndex *ExportSummary = nullptr; + + /// The module summary index to use for importing information to the + /// thin LTO backends, for example for the CFI and devirtualization type + /// tests. + const ModuleSummaryIndex *ImportSummary = nullptr; + + bool DisableTailCalls; + bool DisableUnitAtATime; + bool DisableUnrollLoops; + bool SLPVectorize; + bool LoopVectorize; + bool RerollLoops; + bool NewGVN; + bool DisableGVNLoadPRE; + bool VerifyInput; + bool VerifyOutput; + bool MergeFunctions; + bool PrepareForLTO; + bool PrepareForThinLTO; + bool PerformThinLTO; + bool DivergentTarget; + + /// Enable profile instrumentation pass. + bool EnablePGOInstrGen; + /// Profile data file name that the instrumentation will be written to. + std::string PGOInstrGen; + /// Path of the profile data file. + std::string PGOInstrUse; + /// Path of the sample Profile data file. + std::string PGOSampleUse; + +private: + /// ExtensionList - This is list of all of the extensions that are registered. + std::vector<std::pair<ExtensionPointTy, ExtensionFn>> Extensions; + +public: + PassManagerBuilder(); + ~PassManagerBuilder(); + /// Adds an extension that will be used by all PassManagerBuilder instances. + /// This is intended to be used by plugins, to register a set of + /// optimisations to run automatically. + static void addGlobalExtension(ExtensionPointTy Ty, ExtensionFn Fn); + void addExtension(ExtensionPointTy Ty, ExtensionFn Fn); + +private: + void addExtensionsToPM(ExtensionPointTy ETy, + legacy::PassManagerBase &PM) const; + void addInitialAliasAnalysisPasses(legacy::PassManagerBase &PM) const; + void addLTOOptimizationPasses(legacy::PassManagerBase &PM); + void addLateLTOOptimizationPasses(legacy::PassManagerBase &PM); + void addPGOInstrPasses(legacy::PassManagerBase &MPM); + void addFunctionSimplificationPasses(legacy::PassManagerBase &MPM); + void addInstructionCombiningPass(legacy::PassManagerBase &MPM) const; + +public: + /// populateFunctionPassManager - This fills in the function pass manager, + /// which is expected to be run on each function immediately as it is + /// generated. The idea is to reduce the size of the IR in memory. + void populateFunctionPassManager(legacy::FunctionPassManager &FPM); + + /// populateModulePassManager - This sets up the primary pass manager. + void populateModulePassManager(legacy::PassManagerBase &MPM); + void populateLTOPassManager(legacy::PassManagerBase &PM); + void populateThinLTOPassManager(legacy::PassManagerBase &PM); +}; + +/// Registers a function for adding a standard set of passes. This should be +/// used by optimizer plugins to allow all front ends to transparently use +/// them. Create a static instance of this class in your plugin, providing a +/// private function that the PassManagerBuilder can use to add your passes. +struct RegisterStandardPasses { + RegisterStandardPasses(PassManagerBuilder::ExtensionPointTy Ty, + PassManagerBuilder::ExtensionFn Fn) { + PassManagerBuilder::addGlobalExtension(Ty, std::move(Fn)); + } +}; + +} // end namespace llvm +#endif diff --git a/clang-r353983/include/llvm/Transforms/IPO/SCCP.h b/clang-r353983/include/llvm/Transforms/IPO/SCCP.h new file mode 100644 index 00000000..3c40d44c --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/SCCP.h @@ -0,0 +1,37 @@ +//===- SCCP.h - Sparse Conditional Constant Propagation ---------*- 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 +// +//===----------------------------------------------------------------------===// +// +// This pass implements interprocedural sparse conditional constant +// propagation and merging. +// +// Specifically, this: +// * Assumes values are constant unless proven otherwise +// * Assumes BasicBlocks are dead unless proven otherwise +// * Proves values to be constant, and replaces them with constants +// * Proves conditional branches to be unconditional +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_SCCP_H +#define LLVM_TRANSFORMS_IPO_SCCP_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class Module; + +/// Pass to perform interprocedural constant propagation. +class IPSCCPPass : public PassInfoMixin<IPSCCPPass> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_SCCP_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/SampleProfile.h b/clang-r353983/include/llvm/Transforms/IPO/SampleProfile.h new file mode 100644 index 00000000..a5ad4455 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/SampleProfile.h @@ -0,0 +1,42 @@ +//===- SampleProfile.h - SamplePGO pass ---------- --------------*- 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 +/// This file provides the interface for the sampled PGO loader pass. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_SAMPLEPROFILE_H +#define LLVM_TRANSFORMS_IPO_SAMPLEPROFILE_H + +#include "llvm/IR/PassManager.h" +#include <string> + +namespace llvm { + +class Module; + +/// The sample profiler data loader pass. +class SampleProfileLoaderPass : public PassInfoMixin<SampleProfileLoaderPass> { +public: + SampleProfileLoaderPass(std::string File = "", std::string RemappingFile = "", + bool IsThinLTOPreLink = false) + : ProfileFileName(File), ProfileRemappingFileName(RemappingFile), + IsThinLTOPreLink(IsThinLTOPreLink) {} + + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); + +private: + std::string ProfileFileName; + std::string ProfileRemappingFileName; + bool IsThinLTOPreLink; +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_SAMPLEPROFILE_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/StripDeadPrototypes.h b/clang-r353983/include/llvm/Transforms/IPO/StripDeadPrototypes.h new file mode 100644 index 00000000..f4a15c36 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/StripDeadPrototypes.h @@ -0,0 +1,31 @@ +//===-- StripDeadPrototypes.h - Remove unused function declarations -------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// This pass loops over all of the functions in the input module, looking for +// dead declarations and removes them. Dead declarations are declarations of +// functions for which no implementation is available (i.e., declarations for +// unused library functions). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_STRIPDEADPROTOTYPES_H +#define LLVM_TRANSFORMS_IPO_STRIPDEADPROTOTYPES_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// Pass to remove unused function declarations. +struct StripDeadPrototypesPass : PassInfoMixin<StripDeadPrototypesPass> { + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); +}; + +} + +#endif // LLVM_TRANSFORMS_IPO_STRIPDEADPROTOTYPES_H diff --git a/clang-r353983/include/llvm/Transforms/IPO/SyntheticCountsPropagation.h b/clang-r353983/include/llvm/Transforms/IPO/SyntheticCountsPropagation.h new file mode 100644 index 00000000..0b3ba86b --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/SyntheticCountsPropagation.h @@ -0,0 +1,19 @@ +#ifndef LLVM_TRANSFORMS_IPO_SYNTHETIC_COUNTS_PROPAGATION_H +#define LLVM_TRANSFORMS_IPO_SYNTHETIC_COUNTS_PROPAGATION_H + +#include "llvm/ADT/STLExtras.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Support/ScaledNumber.h" + +namespace llvm { +class Function; +class Module; + +class SyntheticCountsPropagation + : public PassInfoMixin<SyntheticCountsPropagation> { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &MAM); +}; +} // namespace llvm +#endif diff --git a/clang-r353983/include/llvm/Transforms/IPO/ThinLTOBitcodeWriter.h b/clang-r353983/include/llvm/Transforms/IPO/ThinLTOBitcodeWriter.h new file mode 100644 index 00000000..7acb922b --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/ThinLTOBitcodeWriter.h @@ -0,0 +1,40 @@ +//===- ThinLTOBitcodeWriter.h - Bitcode writing pass for ThinLTO ----------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// This pass prepares a module containing type metadata for ThinLTO by splitting +// it into regular and thin LTO parts if possible, and writing both parts to +// a multi-module bitcode file. Modules that do not contain type metadata are +// written unmodified as a single module. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_THINLTOBITCODEWRITER_H +#define LLVM_TRANSFORMS_IPO_THINLTOBITCODEWRITER_H + +#include <llvm/IR/PassManager.h> +#include <llvm/Support/raw_ostream.h> + +namespace llvm { + +class ThinLTOBitcodeWriterPass + : public PassInfoMixin<ThinLTOBitcodeWriterPass> { + raw_ostream &OS; + raw_ostream *ThinLinkOS; + +public: + // Writes bitcode to OS. Also write thin link file to ThinLinkOS, if + // it's not nullptr. + ThinLTOBitcodeWriterPass(raw_ostream &OS, raw_ostream *ThinLinkOS) + : OS(OS), ThinLinkOS(ThinLinkOS) {} + + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); +}; + +} // namespace llvm + +#endif diff --git a/clang-r353983/include/llvm/Transforms/IPO/WholeProgramDevirt.h b/clang-r353983/include/llvm/Transforms/IPO/WholeProgramDevirt.h new file mode 100644 index 00000000..509fcc86 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/IPO/WholeProgramDevirt.h @@ -0,0 +1,233 @@ +//===- WholeProgramDevirt.h - Whole-program devirt pass ---------*- 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 +// +//===----------------------------------------------------------------------===// +// +// This file defines parts of the whole-program devirtualization pass +// implementation that may be usefully unit tested. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H +#define LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" +#include <cassert> +#include <cstdint> +#include <utility> +#include <vector> + +namespace llvm { + +template <typename T> class ArrayRef; +template <typename T> class MutableArrayRef; +class Function; +class GlobalVariable; +class ModuleSummaryIndex; + +namespace wholeprogramdevirt { + +// A bit vector that keeps track of which bits are used. We use this to +// pack constant values compactly before and after each virtual table. +struct AccumBitVector { + std::vector<uint8_t> Bytes; + + // Bits in BytesUsed[I] are 1 if matching bit in Bytes[I] is used, 0 if not. + std::vector<uint8_t> BytesUsed; + + std::pair<uint8_t *, uint8_t *> getPtrToData(uint64_t Pos, uint8_t Size) { + if (Bytes.size() < Pos + Size) { + Bytes.resize(Pos + Size); + BytesUsed.resize(Pos + Size); + } + return std::make_pair(Bytes.data() + Pos, BytesUsed.data() + Pos); + } + + // Set little-endian value Val with size Size at bit position Pos, + // and mark bytes as used. + void setLE(uint64_t Pos, uint64_t Val, uint8_t Size) { + assert(Pos % 8 == 0); + auto DataUsed = getPtrToData(Pos / 8, Size); + for (unsigned I = 0; I != Size; ++I) { + DataUsed.first[I] = Val >> (I * 8); + assert(!DataUsed.second[I]); + DataUsed.second[I] = 0xff; + } + } + + // Set big-endian value Val with size Size at bit position Pos, + // and mark bytes as used. + void setBE(uint64_t Pos, uint64_t Val, uint8_t Size) { + assert(Pos % 8 == 0); + auto DataUsed = getPtrToData(Pos / 8, Size); + for (unsigned I = 0; I != Size; ++I) { + DataUsed.first[Size - I - 1] = Val >> (I * 8); + assert(!DataUsed.second[Size - I - 1]); + DataUsed.second[Size - I - 1] = 0xff; + } + } + + // Set bit at bit position Pos to b and mark bit as used. + void setBit(uint64_t Pos, bool b) { + auto DataUsed = getPtrToData(Pos / 8, 1); + if (b) + *DataUsed.first |= 1 << (Pos % 8); + assert(!(*DataUsed.second & (1 << Pos % 8))); + *DataUsed.second |= 1 << (Pos % 8); + } +}; + +// The bits that will be stored before and after a particular vtable. +struct VTableBits { + // The vtable global. + GlobalVariable *GV; + + // Cache of the vtable's size in bytes. + uint64_t ObjectSize = 0; + + // The bit vector that will be laid out before the vtable. Note that these + // bytes are stored in reverse order until the globals are rebuilt. This means + // that any values in the array must be stored using the opposite endianness + // from the target. + AccumBitVector Before; + + // The bit vector that will be laid out after the vtable. + AccumBitVector After; +}; + +// Information about a member of a particular type identifier. +struct TypeMemberInfo { + // The VTableBits for the vtable. + VTableBits *Bits; + + // The offset in bytes from the start of the vtable (i.e. the address point). + uint64_t Offset; + + bool operator<(const TypeMemberInfo &other) const { + return Bits < other.Bits || (Bits == other.Bits && Offset < other.Offset); + } +}; + +// A virtual call target, i.e. an entry in a particular vtable. +struct VirtualCallTarget { + VirtualCallTarget(Function *Fn, const TypeMemberInfo *TM); + + // For testing only. + VirtualCallTarget(const TypeMemberInfo *TM, bool IsBigEndian) + : Fn(nullptr), TM(TM), IsBigEndian(IsBigEndian), WasDevirt(false) {} + + // The function stored in the vtable. + Function *Fn; + + // A pointer to the type identifier member through which the pointer to Fn is + // accessed. + const TypeMemberInfo *TM; + + // When doing virtual constant propagation, this stores the return value for + // the function when passed the currently considered argument list. + uint64_t RetVal; + + // Whether the target is big endian. + bool IsBigEndian; + + // Whether at least one call site to the target was devirtualized. + bool WasDevirt; + + // The minimum byte offset before the address point. This covers the bytes in + // the vtable object before the address point (e.g. RTTI, access-to-top, + // vtables for other base classes) and is equal to the offset from the start + // of the vtable object to the address point. + uint64_t minBeforeBytes() const { return TM->Offset; } + + // The minimum byte offset after the address point. This covers the bytes in + // the vtable object after the address point (e.g. the vtable for the current + // class and any later base classes) and is equal to the size of the vtable + // object minus the offset from the start of the vtable object to the address + // point. + uint64_t minAfterBytes() const { return TM->Bits->ObjectSize - TM->Offset; } + + // The number of bytes allocated (for the vtable plus the byte array) before + // the address point. + uint64_t allocatedBeforeBytes() const { + return minBeforeBytes() + TM->Bits->Before.Bytes.size(); + } + + // The number of bytes allocated (for the vtable plus the byte array) after + // the address point. + uint64_t allocatedAfterBytes() const { + return minAfterBytes() + TM->Bits->After.Bytes.size(); + } + + // Set the bit at position Pos before the address point to RetVal. + void setBeforeBit(uint64_t Pos) { + assert(Pos >= 8 * minBeforeBytes()); + TM->Bits->Before.setBit(Pos - 8 * minBeforeBytes(), RetVal); + } + + // Set the bit at position Pos after the address point to RetVal. + void setAfterBit(uint64_t Pos) { + assert(Pos >= 8 * minAfterBytes()); + TM->Bits->After.setBit(Pos - 8 * minAfterBytes(), RetVal); + } + + // Set the bytes at position Pos before the address point to RetVal. + // Because the bytes in Before are stored in reverse order, we use the + // opposite endianness to the target. + void setBeforeBytes(uint64_t Pos, uint8_t Size) { + assert(Pos >= 8 * minBeforeBytes()); + if (IsBigEndian) + TM->Bits->Before.setLE(Pos - 8 * minBeforeBytes(), RetVal, Size); + else + TM->Bits->Before.setBE(Pos - 8 * minBeforeBytes(), RetVal, Size); + } + + // Set the bytes at position Pos after the address point to RetVal. + void setAfterBytes(uint64_t Pos, uint8_t Size) { + assert(Pos >= 8 * minAfterBytes()); + if (IsBigEndian) + TM->Bits->After.setBE(Pos - 8 * minAfterBytes(), RetVal, Size); + else + TM->Bits->After.setLE(Pos - 8 * minAfterBytes(), RetVal, Size); + } +}; + +// Find the minimum offset that we may store a value of size Size bits at. If +// IsAfter is set, look for an offset before the object, otherwise look for an +// offset after the object. +uint64_t findLowestOffset(ArrayRef<VirtualCallTarget> Targets, bool IsAfter, + uint64_t Size); + +// Set the stored value in each of Targets to VirtualCallTarget::RetVal at the +// given allocation offset before the vtable address. Stores the computed +// byte/bit offset to OffsetByte/OffsetBit. +void setBeforeReturnValues(MutableArrayRef<VirtualCallTarget> Targets, + uint64_t AllocBefore, unsigned BitWidth, + int64_t &OffsetByte, uint64_t &OffsetBit); + +// Set the stored value in each of Targets to VirtualCallTarget::RetVal at the +// given allocation offset after the vtable address. Stores the computed +// byte/bit offset to OffsetByte/OffsetBit. +void setAfterReturnValues(MutableArrayRef<VirtualCallTarget> Targets, + uint64_t AllocAfter, unsigned BitWidth, + int64_t &OffsetByte, uint64_t &OffsetBit); + +} // end namespace wholeprogramdevirt + +struct WholeProgramDevirtPass : public PassInfoMixin<WholeProgramDevirtPass> { + ModuleSummaryIndex *ExportSummary; + const ModuleSummaryIndex *ImportSummary; + WholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary, + const ModuleSummaryIndex *ImportSummary) + : ExportSummary(ExportSummary), ImportSummary(ImportSummary) { + assert(!(ExportSummary && ImportSummary)); + } + PreservedAnalyses run(Module &M, ModuleAnalysisManager &); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H |