diff --git a/llvm/include/llvm/Analysis/IVarOptAnalysis.h b/llvm/include/llvm/Analysis/IVarOptAnalysis.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Analysis/IVarOptAnalysis.h @@ -0,0 +1,265 @@ +//===------------------------- IVarOptAnalysis.h --------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/******************************************************************************* +TERMS USED: +- "Real Class Name" / realClassName: + In this optimization we deal with two class names: + * The class name as it appears in the metadata + This is the Clang-generated class name in the LLVM IR / ObjC metadata + Ex: OBJC_CLASS_$_MyWindow + * The "real class name" + This is the class name as it appears inside the source code + Ex: -> MyWindow +- "Preliminary Class Size/Start" / "Real Class Size" + This optimization gets class sizes from Clang's OBJC_CLASS_RO_ IR data + structure. However this is not always accurate(because of IVars declared in + the @implmentation / exteions). In this context, "Preliminary" refers to + these potentially inaccurate class attributes, while "Real" reffers to the + correct class size of an object at runtime (patched preliminary values) +*******************************************************************************/ + +#ifndef LLVM_ANALYSIS_IVAROPTANALYSIS_H +#define LLVM_ANALYSIS_IVAROPTANALYSIS_H + +#include "llvm/IR/Instruction.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/ModuleSummaryIndex.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { +// Struct containing info about preliminary class size. +// preliminaryInstanceStart, which is the size of the base class, is not +// guaranteed to be accurate, because the base class might have IVars declared +// in the implemenation - which will not show up in this size. +// The size of own data (excluding base class: preliminaryInstanceSize - +// preliminaryInstanceStart) is guaranteed to be accurate +struct IVarOptInfoForClass { + IVarOptInfoForClass() { + // These two memebers have to be valid / initialized - info should always + // exist for them + preliminaryInstanceStart = UINT_MAX; + preliminaryInstanceSize = UINT_MAX; + // Max Ivar align can be uninitialized as the class may not have any ivars + maxIVarAlign = 0; + baseClassShift = 0; + } + size_t preliminaryInstanceStart; + size_t preliminaryInstanceSize; + size_t maxIVarAlign; + size_t baseClassShift; +}; + +class LoadInst; +class ThinLTOBuffer; +class ConstantStruct; +extern bool EnableIVarDirectAccessRuntimeCheck; + +// This function gets the IVar name from the associated global variable name +// Ex: my_ivar -> OBJC_IVAR_$_my_ivar +extern bool +verifyIsIVarGlobalOffsetAndGetRealClassName(const GlobalVariable &globalVar, + std::string &iVarRealClassName); + +// Parse an ObjC metadata class name to get the real class name +// Ex: OBJC_CLASS_$_NSObject -> NSObject +// See top of IVarOptAnalysis.h for what "real class name" means +bool parseRealClassNameFromMetaClassName(const StringRef &irClassName, + std::string &realClassName); + +// Verify that the global is a class IVar list - and get real class name +// "\01l_OBJC_$_INSTANCE_VARIABLES_MyWindow" => "MyWindow" (real class name) +// See top of IVarOptAnalysis.h for what "real class name" means +bool verifyIsClassIVarListAndGetRealClassName(const GlobalVariable &globalVar, + std::string &realClassName); + +// Extract ConstantStruct* 's from a "\01l_OBJC_$_INSTANCE_VARIABLES_" global +// variable +bool getIVarsInGlobalVarIVarList( + const GlobalVariable &globalVar, + std::vector &arIVarStucts, + const Constant *&iVarArrayStruct, const char *errContext); + +// Given a GlovalVariable of type "\01l_OBJC_$_INSTANCE_VARIABLES_", go through +// all IVar's and determine max align value +bool getMaxIVarAlignFromIVarList(const GlobalVariable &globalVar, + size_t &maxIVarAlignValue); + +// Verify that the global is a class RO struct - and get real class name +// "\01l_OBJC_CLASS_RO_$_MyWindow" => "MyWindow" (real class name) +// See top of IVarOptAnalysis.h for what "real class name" means +bool verifyIsClassROAndGetRealClassName(const GlobalVariable &globalVar, + std::string &realClassName); + +GlobalValue::GUID +getInterfaceIDFromRealClassName(const std::string &realClassName); + +// Align value up to a given alignment alignment +size_t alignValueUp(const size_t valueToAlign, const size_t alignment); + +// ============================================================================ +// ============ Used during clang export of interface summary ================= +// ============================================================================ +class IVarOptClangExportHelper { +public: + IVarOptClangExportHelper(ModuleSummaryIndex &Index) : m_Index(Index) {} + + // Collect all necessary data in module + bool collectDataFromModule(const Module *pModule); + + // Get list of IVars for given class meta name + std::vector + getIVarListForClass(const StringRef &metaClassName); + + // Get class info for a class. Find it in m_ClassNameToOptInfo + bool getClassInfoForIVarOpt(const StringRef &metaClassName, + size_t &preliminaryInstanceStart, + size_t &preliminaryInstanceSize, + size_t &maxIVarAlign); + +private: + // Scan the given module for "\01l_OBJC_$_INSTANCE_VARIABLES_*" structures + // and extract the max iVar alignment value for each class. Store data in + // m_ClassNameToOptInfo + bool scanForClassIVarListsInModuleAndGetMaxIVarAlign(); + + // Scan the given module for IVars and store them in internal structs + // This goes through all "OBJC_IVAR_$_*" structures and populates + // m_ClassNameToClassIVars & m_IVarIDToIVarName + bool scanForIVarsInModule(); + + // Store IVar_ID -> IVar_Meta_Name mappings in ModuleSummaryIndex + bool populateIVarIDToMetaNameTable(); + + // Scan the given module for class definitions and store them internally + // This goes through all "\01l_OBJC_CLASS_RO_$_*" structures and populates + // m_ClassNameToOptInfo with info from that metadata. + bool scanForClassDefsInModule(); + + // Store info about this IVar in m_ClassNameToClassIVars & m_IVarIDToIVarName + bool storeDataForIVar(const GlobalVariable &iVarDefVar, + const std::string &iVarRealClassName, + const size_t iVarOffset); + + // Verify that the global is an IVar Definition and get const offset for it + bool verifyIsIVarDefVarAndGetOffset(const GlobalVariable &iVarDefVar, + size_t &iVarOffset); + + // Given a GlovalVariable of type "\01l_OBJC_CLASS_RO_$_", parse out + // preliminary class size info + bool parseClassPreliminarySizeInfoFromRoMetaData(const GlobalVariable &GV, + size_t &instanceStart, + size_t &instanceSize); + +private: + // Set of names of classes with hidden ivars + std::set m_ClassesWithHiddedIVars; + + // Map: Class_Name -> Vector_Of_Ivars_In_Class + std::map> + m_ClassNameToClassIVars; + + // Map: IVar_Name_ID -> IVar_Name + std::map m_IVarIDToIVarName; + + // Map of real class name ("FBNotificationClient") to class parameters + // See top of IVarOptAnalysis.h for what "real class name" means + std::map m_ClassNameToOptInfo; + + // Index of translation unit + ModuleSummaryIndex &m_Index; + + // Module that was scanned for IVars + const Module *m_pModuleScanned; +}; + +// ============================================================================ +// =========== Used during serial computation of module summary =============== +// ============================================================================ +class IVarOptThinLTOSummaryBuilder { +public: + IVarOptThinLTOSummaryBuilder(ModuleSummaryIndex &Index) : m_Index(Index) {} + + // Go through all classes in the module summary index and figure out which + // ones we can optimize. Also compute patch offsets for accessing instance + // variables + bool processModuleSummaryIndex(); + +private: + // Compute the size of NSObject and store it in m_SizeOfNSObject + bool computeSizeOfNSObject(); + + // Enumerate through interface summaries and populate data structures to + // enable fast lookup of info for classes by class GUID + bool fillLookupStructures(); + + // Get GUID for NSObject class + GlobalValue::GUID getNSObjectGUID(); + + // Check if instance variables in this interface can be optimized and compute + // patch offset if that is the case. + bool + checkCanOptimizeAndComputeClassIVarOffset(const ObjCInterfaceSummary *IfcSum, + size_t &classIVarOffset); + + // For every IVar in the interface, patch it with the patch offset obtained + // from checkCanOptimizeAndComputeClassIVarOffset and then store it in + // ModuleSummaryIndex via setIVarOffset + bool patchAndStoreInterfaceIVarOffsets(const ObjCInterfaceSummary *IfcSum, + const size_t classIVarOffset); + + // Record in ModuleSummaryIndex that this interface has known ivar offsets and + // therfore can be optimized + bool storeInterfaceWithKnownOffsetsInfo(const ObjCInterfaceSummary *IfcSum, + size_t iVarOffset); + + // Given an ObjCInterfaceSummary, compute the real size of its base class + bool computeRealSizeForClass(const GlobalValue::GUID classID, + size_t &classSize); + + // Given all params that influence class size at runtime, calculate what the + // actual class size will be + bool calculateRuntimeClassSizeFromParams(const GlobalValue::GUID classID, + const GlobalValue::GUID superClassID, + const IVarOptInfoForClass &classInfo, + const size_t runtimeSizeOfBaseClass, + size_t &finalClassSize); + + // Compute the patch offset that needs to be applied to class IVars + bool computeClassIVarOffset(const ObjCInterfaceSummary *IfcSum, + const size_t actualSizeOfClass, + const IVarOptInfoForClass &optInfo, + size_t &iVarOffset); + + // Get some info fror the class: base size & opt info + bool getInterfaceSizeAndOptInfo(const ObjCInterfaceSummary *IfcSum, + size_t &sizeOfClass, + IVarOptInfoForClass &optInfo); + +private: + // Map of class ID to its parent class ID. + std::map m_ClassIDToSuperClassID; + + // Map from class GUID to info used for applying optimization + std::map m_ClassIDToOptInfo; + + // Map from class GUID to real size of the class. + // Cache results from computeRealSizeForClass + // See top of IVarOptAnalysis.h for what "real class size" means + std::map m_ClassIDToRealClassSize; + + // The size of an NSObject object + uint32_t m_SizeOfNSObject; + + // The global module summary in which to store info + ModuleSummaryIndex &m_Index; +}; + +} // namespace llvm + +#endif // LLVM_ANALYSIS_IVAROPTANALYSIS_H \ No newline at end of file diff --git a/llvm/include/llvm/Analysis/IVarOptLog.h b/llvm/include/llvm/Analysis/IVarOptLog.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Analysis/IVarOptLog.h @@ -0,0 +1,115 @@ +//===---------------------------- IVarOptLog.h ----------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_IVAROPTLOG_H +#define LLVM_ANALYSIS_IVAROPTLOG_H + +#include "llvm/IR/Module.h" +#include "llvm/IR/ModuleSummaryIndex.h" +#include + +namespace llvm { +struct IVarOptInfoForClass; +class LoadInst; +class GlobalVariable; + +class IVarOptLog { +public: + // Print the statistics collected for the module + static bool printIVarStats(); + + // =========================================================================== + // =============== Logging for shared IVar Optimization code ================= + // =========================================================================== + // Failed to compute size of NSObject - might happen if no classes are present + static void onFailedComputeSizeOfNSObject(); + + // Log info on various events below + static void onInvalidIVarName(const GlobalVariable &iVarOffsetVar); + static void onComputeClassPatchOffset(const ModuleSummaryIndex &Index, + const ObjCInterfaceSummary *IfcSum, + const size_t classIVarOffset, + const size_t actualSizeOfClass, + const IVarOptInfoForClass &optInfo); + static void + onRecordPreliminaryClassInfo(const GlobalVariable &classROGlobalVar, + const std::string &realClassName, + const IVarOptInfoForClass &sizeInfo); + static void + onRecordMaxIVarAlignForClass(const GlobalVariable &classIVarListGlobalVar, + const std::string &realClassName, + const size_t maxIVarAlign); + static void onProcessInterface(const ModuleSummaryIndex &Index, + const ObjCInterfaceSummary *IfcSum); + static void onStoreDataForIVar(const GlobalVariable &iVarDefVar, + const std::string &iVarRealClassName, + const GlobalValue::GUID iVarID, + const size_t iVarOffset); + static bool shouldUseClassSizeCache(); + static void + onBeginComputeClassSize(const ModuleSummaryIndex &Index, + const ObjCInterfaceSummary *IfcSum, + const std::map &cacheMap); + static void onComputedSizeForClass(const GlobalValue::GUID classID, + const size_t classSize); + static void onComputeSizeReachNSObject(const size_t sizeOfNSObject); + + static void + onClassSizeComputeFailFindClassInfo(const GlobalValue::GUID classID); + static void + onClassSizeComputeFailGetBaseSize(const GlobalValue::GUID classID); + static void onFinishComputeClassSize(const size_t classSize); + static void onSummaryBuildSetOptInfo(const ModuleSummaryIndex &Index, + const ObjCInterfaceSummary *IfcSum, + const IVarOptInfoForClass &sizeInfo); + static void onComputeIVarOffset(const ModuleSummaryIndex &Index, + const GlobalValue::GUID iVarMetaNameID, + const size_t clangIVarOffset, + const size_t iVarOffset); + static void onPatchClassSize(std::string &realClassName, + GlobalVariable &classROGlobalVar, + Constant *oldClassSizeOp, + Constant *newClassSizeOp); + + // =========================================================================== + // ==================== Logging for IVar Direct Access ======================= + // =========================================================================== + static void onSkipOptimizeIVarAccess(const std::string &iVarRealClassName, + const LoadInst &loadInstr); + static void onOptimizeIVarAccess(const LoadInst &loadInstr, + const Value &replacementConst, + const size_t iVarReplacementOffset); + + // =========================================================================== + static std::string _padNumber(unsigned long long number, size_t padding); + +private: + // Statistics need to be atomic as they will be modified during codegen + // parallel step. + static std::atomic m_NumIVarsAccessesMadeDirect; + static std::atomic m_NumIVarsAccessesNotMadeDirect; + static std::atomic m_NumClassesIVarErased; + static std::atomic m_NumClassesIVarErasedWithSizePatch; + static std::atomic m_NumClassesNotIVarErased; + + // Lock this mutex while logging in multi-threaded environment (Codegen) + static std::mutex m_OptStageOutputMutex; + + // Temp storage for advanced logging of class sizes + static const ModuleSummaryIndex *m_pCSIndex; + static const ObjCInterfaceSummary *m_pCSIfcSum; + static const std::map *m_pCSCacheMap; + static bool b_bLoadingWhiteList; + static bool m_bLastCSSuccess; + static bool m_bPrintedStats; +}; + +} // namespace llvm + +#endif // LLVM_ANALYSIS_IVAROPTLOG_H \ No newline at end of file diff --git a/llvm/include/llvm/Bitcode/LLVMBitCodes.h b/llvm/include/llvm/Bitcode/LLVMBitCodes.h --- a/llvm/include/llvm/Bitcode/LLVMBitCodes.h +++ b/llvm/include/llvm/Bitcode/LLVMBitCodes.h @@ -288,6 +288,9 @@ // numrefs, numrefs x valueid, // n x (valueid, offset)] FS_PERMODULE_VTABLE_GLOBALVAR_INIT_REFS = 23, + OBJC_STRING_TABLE_CLASS = 24, + OBJC_INTERFACE = 25, + OBJC_STRING_TABLE_IVARS = 26, }; enum MetadataCodes { diff --git a/llvm/include/llvm/IR/ModuleSummaryIndex.h b/llvm/include/llvm/IR/ModuleSummaryIndex.h --- a/llvm/include/llvm/IR/ModuleSummaryIndex.h +++ b/llvm/include/llvm/IR/ModuleSummaryIndex.h @@ -280,7 +280,7 @@ class GlobalValueSummary { public: /// Sububclass discriminator (for dyn_cast<> et al.) - enum SummaryKind : unsigned { AliasKind, FunctionKind, GlobalVarKind }; + enum SummaryKind : unsigned { AliasKind, FunctionKind, GlobalVarKind, InterfaceKind }; /// Group flags (Linkage, NotEligibleToImport, etc.) as a bitfield. struct GVFlags { @@ -821,6 +821,97 @@ } }; + +struct IVarClangSummaryInfo { + // Hash of the name of the iVar global variable + GlobalValue::GUID IVarMetaNameID; + + // Clang-calculated offset of the iVar in the class memory layout + size_t IVarClangOffset; +}; + +struct IVarThinLTOSummaryInfo { + // Clang-calculated offset of the iVar in the class memory layout + size_t ClangIVarOffset; + + // ThinLTO-patched offset of the iVar in the class memory layout - this is the + // final, correct offset that the IVar will have at runtime. It is obtained by + // patching ClangIVarOffset with information that Clang does not have access + // to. + size_t ThinLTOIVarPatchedOffset; +}; + +struct ClassWithIVarsThinLTOSummaryInfo { + // Size by which the base class will grow at runtime (shifting this class up) + size_t BaseClassGrowth; + // InstanceSize, as present in the final binary, will be patched at runtime + size_t MaxIVarAlign; +}; + + +/// \brief Interface summary information to use during ThinLTO for ObjC +/// optimization +class ObjCInterfaceSummary : public GlobalValueSummary { +private: + /// Globally unique identifier representing this summary. + /// Note that ClassId is already being used to store another type of + /// summary, so here we use InterfaceSummaryId + /// (ID from [className + "_interface"]). + /// Otherwise, this summary would be overwritten. + /// In the future, we can piggyback this summary onto the summary stored + /// by ClassId. + GlobalValue::GUID InterfaceSummaryId; + /// Globally unique identifier of this class. + GlobalValue::GUID ClassId; + /// Globally unique identifier of the superclass of this class. + GlobalValue::GUID SuperclassId; + + // Preliminary size of base classes. This is not accurate as the size of the + // base class will change if there are instance variables in the base class + // implmentaiton, which is defined in another translation unit + size_t PreliminaryInstanceStart; + // Size of this class. Not accurate because size of base is also not accurate + // However, (PreliminaryInstanceSize - PreliminaryInstanceStart) which is the + // size of this class's member(no base members) is accurate + size_t PreliminaryInstanceSize; + // The maximum align values of any of the IVars in the class + size_t MaxIVarAlign; + // List of Instance vairables in the class, ID & offset + std::vector IVarList; + +public: + ObjCInterfaceSummary(GVFlags Flags, std::vector Refs, + GlobalValue::GUID InterfaceSummaryId, + GlobalValue::GUID ClassId, + GlobalValue::GUID SuperclassId, + size_t PreliminaryInstanceStart, + size_t PreliminaryInstanceSize, size_t MaxIVarAlign, + std::vector IVarList) + : GlobalValueSummary(InterfaceKind, Flags, std::move(Refs)), + InterfaceSummaryId(InterfaceSummaryId), ClassId(ClassId), + SuperclassId(SuperclassId), + PreliminaryInstanceStart(PreliminaryInstanceStart), + PreliminaryInstanceSize(PreliminaryInstanceSize), + MaxIVarAlign(MaxIVarAlign), IVarList(std::move(IVarList)) {} + + GlobalValue::GUID getInterfaceSummaryID() const { return InterfaceSummaryId; } + GlobalValue::GUID getClassID() const { return ClassId; } + GlobalValue::GUID getSuperclassID() const { return SuperclassId; } + + size_t getPreliminaryInstanceStart() const { + return PreliminaryInstanceStart; + } + size_t getPreliminaryInstanceSize() const { return PreliminaryInstanceSize; } + size_t getMaxIVarAlign() const { return MaxIVarAlign; } + std::vector getIVarList() const { return IVarList; } + + /// Check if this is a function summary. + static bool classof(const GlobalValueSummary *GVS) { + return GVS->getSummaryKind() == InterfaceKind; + } +}; + + struct TypeTestResolution { /// Specifies which kind of type check we should emit for this byte array. /// See http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html for full @@ -1016,7 +1107,155 @@ .first; } + // IVar GUID to Meta name map + std::map IVarIDToMetaNameMap; + std::map ClassIDToString; + + // A set of classes (Actual name, Ex: MyWindow) that fit the requirements: + // - Their entire inheritance chain is defined in the ModuleIndex (except + // final base NSObject class). i.e. no classes that inheit from external + // classes (defined in dylibs). + // - No classes in the inheritance chain contain hidden instance variables + // (instance variables declared in the @implementation or in extensions). + std::set FullyDefinedClassesSet; + + // map Interface ID to offset that needs to be added to Clang IVar offsets + std::map + InterfaceIDsToClassWithIVarsInfo; + + // Map IVar Meta name to IVar offset in class. Ex: + // "OBJC_IVAR_$_ASDisplayNode._propertyLock" => 24 + std::map + IVarMetaNameIDToIVarThinLTOSummaryInfo; + + // The size of NSObject - used by IVar Direct Access optimization + size_t SizeOfNSObject; + public: + void classIDToString(GlobalValue::GUID CId, std::string name) { + ClassIDToString[CId] = name; + } + + std::string getClassName(GlobalValue::GUID CId) const { + auto iter = ClassIDToString.find(CId); + // For Protocols and Categories, this operation may fail for now. + // assert(iter != ClassIDToString.end()); + if (iter == ClassIDToString.end()) { + return ""; + } + return iter->second; + } + + bool getClassName(GlobalValue::GUID CId, std::string &className) const { + auto iter = ClassIDToString.find(CId); + if (iter == ClassIDToString.end()) { + return false; + } + + className = iter->second; + return true; + } + + const std::map &getClassNameTable() const { + return ClassIDToString; + } + std::map &getClassNameTable() { + return ClassIDToString; + } + + void setClassWithIVarsThinLTOSummaryInfo( + const GlobalValue::GUID interfaceID, + ClassWithIVarsThinLTOSummaryInfo &classThinLTOIVarInfo) { + InterfaceIDsToClassWithIVarsInfo[interfaceID] = classThinLTOIVarInfo; + } + + // If a class is here, then it can be optimized by IVar Direct + bool getClassWithIVarsThinLTOSummaryInfo( + const GlobalValue::GUID interfaceID, + ClassWithIVarsThinLTOSummaryInfo &classThinLTOIVarInfo) const { + auto it = InterfaceIDsToClassWithIVarsInfo.find(interfaceID); + if (it == InterfaceIDsToClassWithIVarsInfo.end()) { + return false; + } + classThinLTOIVarInfo = it->second; + return true; + } + + // Used by IVar Direct Access Optimization + // Store the offset for a given IVar. + // Ex: _OBJC_IVAR_$_ASDisplayNode._propertyLock => 24 + void setIVarThinLTOSummaryInfo(const GlobalValue::GUID iVarMetaNameID, + const IVarThinLTOSummaryInfo iVarInfo) { + IVarMetaNameIDToIVarThinLTOSummaryInfo[iVarMetaNameID] = iVarInfo; + } + + // Used by IVar Direct Access Optimization + // Get the offset for a given IVar. + // When optimizing loads, the replacement offsets will be obtained from here + bool getIVarThinLTOSummaryInfo( + const GlobalValue::GUID iVarMetaNameID, + IVarThinLTOSummaryInfo &iVarThinLTOSummaryInfo) const { + iVarThinLTOSummaryInfo.ClangIVarOffset = 0; + iVarThinLTOSummaryInfo.ThinLTOIVarPatchedOffset = 0; + + auto it = IVarMetaNameIDToIVarThinLTOSummaryInfo.find(iVarMetaNameID); + if (it == IVarMetaNameIDToIVarThinLTOSummaryInfo.end()) + return false; + + iVarThinLTOSummaryInfo = it->second; + return true; + } + + std::map & + getIVarMetaNameIDToIVarThinLTOSummaryInfoMap() { + return IVarMetaNameIDToIVarThinLTOSummaryInfo; + } + + // Used by IVar Direct Access Optimization + // For figuring out class sizes we need the size of NSObject - store it here + // to not compute it multiple times + void setSizeOfNSObject(const uint32_t sizeOfNSobject) { + SizeOfNSObject = sizeOfNSobject; + } + + // Used by IVar Direct Access Optimization + // Get the size of NSObject + uint32_t getSizeOfNSObject() const { return SizeOfNSObject; } + + // Used by IVar Direct Access Optimization + // Store the mapping of an IVar ID to an IVar meta name + void setIVarIDToMetaNameMapping(const GlobalValue::GUID &iVarID, + const std::string &iVarMetaName) { + IVarIDToMetaNameMap[iVarID] = iVarMetaName; + } + + // Used by IVar Direct Access Optimization + // Get the mapping of an IVar ID to an IVar meta name + bool getIVarMetaNameFromIVarID(const GlobalValue::GUID iVarID, + std::string &iVarName) const { + auto iter = IVarIDToMetaNameMap.find(iVarID); + + if (iter == IVarIDToMetaNameMap.end()) { + return false; + } + + iVarName = iter->second; + return true; + } + + // Used by IVar Direct Access Optimization + // Get the hashmap that maps ivar ids to ivar names + std::map &getIVarIDToMetaNameTable() { + return IVarIDToMetaNameMap; + } + + // Used by IVar Direct Access Optimization + // Get the hashmap that maps ivar ids to ivar names -- const + const std::map & + getIVarIDToMetaNameTable() const { + return IVarIDToMetaNameMap; + } + // See HaveGVs variable comment. ModuleSummaryIndex(bool HaveGVs, bool EnableSplitLTOUnit = false) : HaveGVs(HaveGVs), EnableSplitLTOUnit(EnableSplitLTOUnit), Saver(Alloc) { diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -195,6 +195,7 @@ void initializeInterleavedLoadCombinePass(PassRegistry &); void initializeInternalizeLegacyPassPass(PassRegistry&); void initializeIntervalPartitionPass(PassRegistry&); +void initializeIVarDirectAccessLegacyPassPass(PassRegistry &); void initializeJumpThreadingPass(PassRegistry&); void initializeLCSSAVerificationPassPass(PassRegistry&); void initializeLCSSAWrapperPassPass(PassRegistry&); diff --git a/llvm/include/llvm/Transforms/IPO.h b/llvm/include/llvm/Transforms/IPO.h --- a/llvm/include/llvm/Transforms/IPO.h +++ b/llvm/include/llvm/Transforms/IPO.h @@ -273,6 +273,9 @@ /// devirtualization and control-flow integrity. ModulePass *createGlobalSplitPass(); +ModulePass * +createIVarDirectAccessLegacyPass(const ModuleSummaryIndex *ImportSummary); + //===----------------------------------------------------------------------===// // SampleProfilePass - Loads sample profile data from disk and generates // IR metadata to reflect the profile. diff --git a/llvm/include/llvm/Transforms/IPO/IVarDirectAccess.h b/llvm/include/llvm/Transforms/IPO/IVarDirectAccess.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Transforms/IPO/IVarDirectAccess.h @@ -0,0 +1,109 @@ +//===- IVarDirectAccess.h - Optimize accesses to ivars -------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===---------------------------------------------------------------------===// +/////////////////////////////////////////////////////////////////////////////// +//===== ObjC Optimizaton: IVar Direct Access - Make IVar offsets fragile ====== +/////////////////////////////////////////////////////////////////////////////// +/// ThinLTO Optimization pass. Pass -fivar-direct-access to clang driver ////// +/// OR -mllvm -enable-ivar-direct-access to both CC1 and linker /////////////// +/////////////////////////////////////////////////////////////////////////////// + +/****************************************************************************** + In ObjC you can add ivars to child classes and any class that inherits from +them will continue to work without re-compilation. Overhead associated with +having this feature: +- [Optimized out by this pass] All accesses to ivars are indirect (double + dereferencing memory) - leading to a larger binary and more instructions + executed at runtime. +- [Not addressed by this pass] A global variable (offset) is required for each + IVar - leading to a larger binary + + This pass converts accesses to instance variables from indirect (double +derefrence memory) to direct (single derefrence memory) by converting the load +of the IVar offset to a compile-time constant. +Ex: *** The following LLVM bytecode: + %ivar1 = load i64,i64* @"OBJC_IVAR_$_Class01.the_iVar_Impl", align 8 + %add.ptr2 = getelementptr inbounds i8, i8* %0, i64 ===> %ivar1 <=== + + *** Transforms Into: + %add.ptr2 = getelementptr inbounds i8, i8* %0, i64 ===> 16 <=== +******************************************************************************/ + +#ifndef LLVM_TRANSFORMS_IPO_IVARDIRECTACCES_H +#define LLVM_TRANSFORMS_IPO_IVARDIRECTACCES_H + +#include "llvm/Analysis/IVarOptAnalysis.h" +#include "llvm/IR/Instruction.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/ModuleSummaryIndex.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { +class LoadInst; + +// ============================================================================ +// ====================== Used during parallel codegen ======================== +// ============================================================================ +class IVarDirectAccessCodeOptimizer { +public: + IVarDirectAccessCodeOptimizer(const ModuleSummaryIndex &ImportSummary) + : m_ImportSummary(ImportSummary) {} + + // Go through all the instructions in the module and detect accesses to + // ivars. When an access is detected, remove the indirection + bool optimizeIVarAccessesInModule(Module &M); + +private: + // Can we optimize a specific load instruction (Load from a IVar Global + // Offset that meets criteria?) + bool verifyIsOptimizableLoadAndGetIVarClassName(const LoadInst &loadInstr, + std::string &realClassName); + + // Given a load from an ivar, get the offset to be used to replace the load + // with + bool getReplacementOffsetForIVar(const LoadInst &loadInstr, + const std::string &iVarRealClassName, + size_t &iVarOffset); + + // Build a replacement Value*(constant int) to be used for replacing an + // LoadInst + Value *buildReplacementConstForLoad(const LoadInst &loadInstr, + const size_t iVarReplacementOffset); + + // Check if IVar Direct Access optimization can be applied to a LoadInst and + // apply it + bool tryConvertLoadToConstant(LoadInst &loadInstr); + + // This does the actual replacing of the load with a const + bool replaceIVarLoadInstrWithConst(LoadInst &loadInstr, + Value *replacementConst); + + // This replaces the access with a const, but does not remove the load. + // Instead, the load is still performed and checked against the predicted + // const. Trigger infinite loop if check fails. + // Enable via EnableIVarDirectAccessRuntimeCheck + bool replaceLoadValueWithConstAndCheck(LoadInst &loadInstr, + Value *replacementConst); + +private: + // The global module summary in which to store info + const ModuleSummaryIndex &m_ImportSummary; + + // Keep track of the current load in block - this is used for giving nice + // names to newly created blocks (avoiding name collisions) + int m_CurrentLoadInBlock = 0; + + // Since we might be adding / invalidating blocks, keep track of the current + // block & current instruction since we want to iterate through everything + BasicBlock *m_pCurrentBlock; + BasicBlock::iterator m_CurrentInstructionIterator; +}; + +} // namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_IVARDIRECTACCES_H diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt --- a/llvm/lib/Analysis/CMakeLists.txt +++ b/llvm/lib/Analysis/CMakeLists.txt @@ -43,6 +43,8 @@ InstructionSimplify.cpp Interval.cpp IntervalPartition.cpp + IVarOptAnalysis.cpp + IVarOptLog.cpp LazyBranchProbabilityInfo.cpp LazyBlockFrequencyInfo.cpp LazyCallGraph.cpp diff --git a/llvm/lib/Analysis/IVarOptAnalysis.cpp b/llvm/lib/Analysis/IVarOptAnalysis.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Analysis/IVarOptAnalysis.cpp @@ -0,0 +1,943 @@ +//===----------------------- IVarOptAnalysis.cpp -------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===---------------------------------------------------------------------===// + +#include "llvm/Analysis/IVarOptAnalysis.h" +#include "llvm/Analysis/IVarOptLog.h" +#include "llvm/IR/Constants.h" +#include "llvm/Support/CommandLine.h" + +using namespace llvm; + +// ============================================================================ +// ================== Flags for debugging / runtime checks ==================== +// ============================================================================ + +// Enable runtime check for IVar Direct Access +bool llvm::EnableIVarDirectAccessRuntimeCheck; +cl::opt EnableIVarDirectAccessRuntimeCheckFlag( + "enable-ivar-direct-access-runtime-check", cl::Hidden, + cl::location(EnableIVarDirectAccessRuntimeCheck), cl::init(false), + cl::desc("Enable runtime checks for direct access of IVars (slow, " + "debugging only) ")); + +// ============================================================================ +// ========================== Shared Helper functions ========================= +// ============================================================================ + +// In ObjC, every instance variable has an associated global variable +// This function gets the IVar name from the associated global variable name +// Ex: my_ivar -> OBJC_IVAR_$_my_ivar +bool llvm::verifyIsIVarGlobalOffsetAndGetRealClassName( + const GlobalVariable &globalVar, std::string &iVarRealClassName) { + + // Prefix of the name of the global variable that stores the IVar offset + const char *const IVarOffsetVarPrefix = "OBJC_IVAR_$_"; + const size_t IVarOffsetVarPrefix_Length = strlen(IVarOffsetVarPrefix); + + const StringRef &ivarOffsetVarName = globalVar.getName(); + + if (!ivarOffsetVarName.startswith(IVarOffsetVarPrefix)) { + return false; + } + + size_t classEndPos = ivarOffsetVarName.find('.', IVarOffsetVarPrefix_Length); + if (classEndPos == StringRef::npos) { + return false; + } + + iVarRealClassName.assign(ivarOffsetVarName.begin() + + IVarOffsetVarPrefix_Length, + classEndPos - IVarOffsetVarPrefix_Length); + + // Make sure this is a valid IVar, some complex IVar's hit this + if (ivarOffsetVarName.find('.', classEndPos + 1) != std::string::npos) { + IVarOptLog::onInvalidIVarName(globalVar); + return false; + } + + return true; +} + +// Parse an ObjC metadata class name to get the real class name +// Ex: OBJC_CLASS_$_NSObject -> NSObject +// See top of IVarOptAnalysis.h for what "real class name" means +bool llvm::parseRealClassNameFromMetaClassName(const StringRef &irClassName, + std::string &realClassName) { + + const char *objc_IR_Class_Prefix = "OBJC_CLASS_$_"; + const size_t objc_IR_Class_Prefix_Length = strlen(objc_IR_Class_Prefix); + + if (!irClassName.startswith(objc_IR_Class_Prefix)) { + return false; + } + + realClassName.assign(irClassName.begin() + objc_IR_Class_Prefix_Length); + return true; +} + +// Verify that the global is a class IVar list - and get real class name +// "\01l_OBJC_$_INSTANCE_VARIABLES_MyWindow" => "MyWindow" (real class name) +// See top of IVarOptAnalysis.h for what "real class name" means +bool llvm::verifyIsClassIVarListAndGetRealClassName( + const GlobalVariable &globalVar, std::string &realClassName) { + const char *const ClassIVarListGlobalVarPrefix = + "\01l_OBJC_$_INSTANCE_VARIABLES_"; + const size_t ClassIVarListGlobalVarPrefix_Length = + strlen(ClassIVarListGlobalVarPrefix); + const StringRef &globalVarName = globalVar.getName(); + + if (!globalVarName.startswith(ClassIVarListGlobalVarPrefix)) { + return false; + } + + realClassName.assign(globalVarName.begin() + + ClassIVarListGlobalVarPrefix_Length); + + return true; +} + +bool llvm::getIVarsInGlobalVarIVarList( + const GlobalVariable &globalVar, + std::vector &arIVarStucts, + const Constant *&iVarArrayStruct, const char *errContext) { + std::string realClassName; + +// Macro that verifies an iVar condition +#define IVR_VER(cond_verify) \ + if (!(cond_verify)) { \ + errs() << "\n#ERROR: " << errContext \ + << ": " \ + "Condition evaluates to false:\n" \ + << "# -- condition: " << #cond_verify "\n" \ + << "# -- globalVar: " << globalVar << "\n"; \ + return false; \ + } + const int count_ListGlobalVarElementCount = 3; + const int count_IVar_Struct_Elems = 5; + const int index_Ivar_Struct_List_In_GlobVar = 2; + + // globalVar = @"\01l_OBJC_$_INSTANCE_VARIABLES_Class01" = .... + IVR_VER(globalVar.hasInitializer()); + + const Constant *varListInitializer; + IVR_VER(varListInitializer = globalVar.getInitializer()); + + // varListStruct = { + // i32, + // i32, + // [2 x %struct._ivar_t] + // } + const ConstantStruct *varListStruct; + IVR_VER(varListStruct = dyn_cast(varListInitializer)); + + // Expect 3 operands to the IVar var list + IVR_VER(varListStruct->getNumOperands() == count_ListGlobalVarElementCount); + + // iVarStructList = [N x %struct._ivar_t] + const ConstantAggregate *iVarStructList; + IVR_VER(iVarStructList = dyn_cast( + varListStruct->getOperand(index_Ivar_Struct_List_In_GlobVar))); + + // struct_ivar_t = { + // i32* @"OBJC_IVAR_$_Class01.the_iVar01", + // i8* getelementptr inbounds [...] OBJC_METH_VAR_NAME_, + // i8* getelementptr inbounds [...] OBJC_METH_VAR_TYPE_, + // i32 2, + // i32 4 + // } + const Constant *struct_ivar_t; + int index = 0; + while ((struct_ivar_t = (iVarStructList->getAggregateElement(index)))) { + const ConstantStruct *iVarStruct; + + IVR_VER(iVarStruct = dyn_cast(struct_ivar_t)); + + IVR_VER(iVarStruct->getNumOperands() == count_IVar_Struct_Elems); + + arIVarStucts.push_back(iVarStruct); + index++; + } + + return true; +#undef IVR_VER +} + +// Given a GlovalVariable of type "\01l_OBJC_$_INSTANCE_VARIABLES_", get the +// initilizing struct and go through all IVar's and determine max align value +// The initializer is of type _ivar_list_t +// struct _ivar_t { +// unsigned[long] int *offset; // pointer to ivar offset location +// char *name; +// char *type; +// uint32_t alignment; +// uint32_t size; +// } +// struct _ivar_list_t { +// uint32 entsize; // sizeof(struct _ivar_t) +// uint32 count; +// struct _iver_t list[count]; +// } +bool llvm::getMaxIVarAlignFromIVarList(const GlobalVariable &globalVar, + size_t &maxIVarAlignValue) { + const int index_Align_Value_In_IVar_Struct = 3; + std::vector arIVarStucts; + const Constant *iVarStruct; + + if (!getIVarsInGlobalVarIVarList(globalVar, arIVarStucts, iVarStruct, + "getMaxIVarAlignFromIVarList")) { + return false; + } + + for (auto iVarStruct : arIVarStucts) { + ConstantInt *iVarAlignment = dyn_cast_or_null( + iVarStruct->getOperand(index_Align_Value_In_IVar_Struct)); + if (!iVarAlignment) { + errs() << "\n#ERROR: getMaxIVarAlignFromIVarList - iVarAlignment failed " + "to cast to ConstantInt:\n" + << "# -- globalVar: " << globalVar << "\n"; + return false; + } + + size_t curIVarAlignShift = (size_t)iVarAlignment->getZExtValue(); + size_t curIVarAlign = 1 << curIVarAlignShift; + maxIVarAlignValue = + curIVarAlign > maxIVarAlignValue ? curIVarAlign : maxIVarAlignValue; + } + + return true; +} + +// Verify that the global is a class RO struct - and get real class name if so +// "\01l_OBJC_CLASS_RO_$_MyWindow" => "MyWindow" (real class name) +// See top of IVarOptAnalysis.h for what "real class name" means +bool llvm::verifyIsClassROAndGetRealClassName(const GlobalVariable &globalVar, + std::string &realClassName) { + const char *const ClassROGlobalVarPrefix = "_OBJC_CLASS_RO_$_"; + const size_t ClassROGlobalVarPrefix_Length = strlen(ClassROGlobalVarPrefix); + const StringRef &globalVarName = globalVar.getName(); + + if (!globalVarName.startswith(ClassROGlobalVarPrefix)) { + return false; + } + + size_t dotPos = globalVarName.find('.', ClassROGlobalVarPrefix_Length); + + if (dotPos != StringRef::npos) { + + realClassName.assign(globalVarName.begin() + ClassROGlobalVarPrefix_Length, + globalVarName.begin() + dotPos); + } else { + realClassName.assign(globalVarName.begin() + ClassROGlobalVarPrefix_Length); + } + return true; +} + +GlobalValue::GUID +llvm::getInterfaceIDFromRealClassName(const std::string &realClassName) { + const char *objc_IR_Class_Prefix = "OBJC_CLASS_$_"; + SmallString<128> metaClassName; + metaClassName = objc_IR_Class_Prefix; + metaClassName += realClassName; + + GlobalValue::GUID interfaceID = GlobalValue::getGUID(metaClassName); + return interfaceID; +} + +size_t llvm::alignValueUp(const size_t valueToAlign, const size_t alignment) { + if (!alignment) + return valueToAlign; + // Align classSize to alignVal + size_t alignedValue = + (valueToAlign + (alignment - 1)) / alignment * alignment; + return alignedValue; +} + +// ============================================================================ +// ======================== IVarOptClangExportHelper ========================== +// ============================================================================ + +// Scan the given module for IVars and store them in internal structs +// This goes through all "OBJC_IVAR_$_*" structures and populates +// m_ClassNameToClassIVars & m_IVarIDToIVarName +bool IVarOptClangExportHelper::collectDataFromModule(const Module *pModule) { + m_pModuleScanned = pModule; + + if (!scanForIVarsInModule()) + return false; + + if (!scanForClassIVarListsInModuleAndGetMaxIVarAlign()) + return false; + + if (!scanForClassDefsInModule()) + return false; + + if (!populateIVarIDToMetaNameTable()) + return false; + + return true; +} + +// Scan the given module for IVars and store them in internal structs +// This goes through all "OBJC_IVAR_$_*" structures and populates +// m_ClassNameToClassIVars & m_IVarIDToIVarName +bool IVarOptClangExportHelper::scanForIVarsInModule() { + std::string realClassName; + size_t iVarOffset; + + for (const GlobalVariable &GV : m_pModuleScanned->globals()) { + // Check is IVar & Parse out the class name from the Offset Var Name + if (!verifyIsIVarGlobalOffsetAndGetRealClassName(GV, realClassName)) { + continue; + } + + if (!verifyIsIVarDefVarAndGetOffset(GV, iVarOffset)) { + continue; + } + + if (!storeDataForIVar(GV, realClassName, iVarOffset)) { + // Error occured, abort processing module + return false; + } + } + + return true; +} + +// Scan the given module for class definitions and store them internally +// This goes through all "\01l_OBJC_CLASS_RO_$_*" structures and populates +// m_ClassNameToOptInfo with info from that metadata. +bool IVarOptClangExportHelper::scanForClassDefsInModule() { + std::string realClassName; + for (const GlobalVariable &GV : m_pModuleScanned->globals()) { + if (!verifyIsClassROAndGetRealClassName(GV, realClassName)) { + continue; + } + + size_t preliminaryInstanceStart, preliminaryInstanceSize; + if (!parseClassPreliminarySizeInfoFromRoMetaData( + GV, preliminaryInstanceStart, preliminaryInstanceSize)) { + continue; + } + + auto &pi = m_ClassNameToOptInfo[realClassName]; + + // These params were already set ? + if (pi.preliminaryInstanceStart != UINT_MAX || + pi.preliminaryInstanceSize != UINT_MAX) { + errs() << "\n#ERROR: IVar Optimization[clang]: Class redefinition:\n" + << "# -- metaClassName: " << GV.getName() << "\n" + << "# -- realClassName: " << realClassName << "\n" + << "# -- maxIVarAlign : " << pi.maxIVarAlign << "\n" + << "# -- old_InstStart: " << pi.preliminaryInstanceStart << "\n" + << "# -- old_InstSize : " << pi.preliminaryInstanceSize << "\n" + << "# -- new_InstStart: " << preliminaryInstanceStart << "\n" + << "# -- new_InstSize : " << preliminaryInstanceSize << "\n"; + continue; + } + + // Update the structure in m_ClassNameToOptInfo + pi.preliminaryInstanceStart = preliminaryInstanceStart; + pi.preliminaryInstanceSize = preliminaryInstanceSize; + + IVarOptLog::onRecordPreliminaryClassInfo(GV, realClassName, pi); + } + + return true; +} + +// Scan the given module for "\01l_OBJC_$_INSTANCE_VARIABLES_*" structures +// and extract the max iVar alignment value for each class. Store data in +// m_ClassNameToOptInfo +bool IVarOptClangExportHelper:: + scanForClassIVarListsInModuleAndGetMaxIVarAlign() { + std::string realClassName; + for (const GlobalVariable &GV : m_pModuleScanned->globals()) { + // Check if the corresponding IVar is declared outside the @interface + if (!verifyIsClassIVarListAndGetRealClassName(GV, realClassName)) { + continue; + } + + size_t maxIVarAlignValue = 0; + if (!llvm::getMaxIVarAlignFromIVarList(GV, maxIVarAlignValue)) { + continue; + } + + auto &pi = m_ClassNameToOptInfo[realClassName]; + if (pi.maxIVarAlign != 0) { + errs() << "\n#ERROR: IVar Optimization[clang]: Class redefinition:\n" + << "# -- metaClassName: " << GV.getName() << "\n" + << "# -- realClassName: " << realClassName << "\n" + << "# -- old_align : " << pi.maxIVarAlign << "\n" + << "# -- new_align : " << maxIVarAlignValue << "\n" + << "# -- prevInstStart: " << pi.preliminaryInstanceStart << "\n" + << "# -- prevInstSize : " << pi.preliminaryInstanceSize << "\n"; + continue; + } + + // Update the structure in m_ClassNameToOptInfo + pi.maxIVarAlign = maxIVarAlignValue; + + IVarOptLog::onRecordMaxIVarAlignForClass(GV, realClassName, + maxIVarAlignValue); + } + + return true; +} + +// Get list of IVars for given class meta name +std::vector +IVarOptClangExportHelper::getIVarListForClass(const StringRef &metaClassName) { + std::string realClassName; + if (!parseRealClassNameFromMetaClassName(metaClassName, realClassName)) { + errs() << "\n#ERROR: IVar Optimization[clang]: Failed to parse " + "metaClassName in" + "getIVarListForClass\n" + << "# -- metaClassName: " << metaClassName << "\n"; + return std::vector(); + } + + if (!m_ClassNameToClassIVars.count(realClassName)) { + // This can happen if the class has no IVars => No IVars were recorded + return std::vector(); + } + + return m_ClassNameToClassIVars[realClassName]; +} + +// Store IVar_ID -> IVar_Meta_Name mappings in ModuleSummaryIndex +bool IVarOptClangExportHelper::populateIVarIDToMetaNameTable() { + for (auto it : m_IVarIDToIVarName) { + const GlobalValue::GUID &iVarID = it.first; + const std::string &iVarMetaName = it.second; + + // Check for hash collision & assert if found + std::string collideIVarMetaName; + if (m_Index.getIVarMetaNameFromIVarID(iVarID, collideIVarMetaName)) { + errs() << "\n#ERROR: IVar Optimization[clang]: " + << "IVar meta name HASH COLLISION: \n" + << "# -- metaName1: " << iVarMetaName << "\n" + << "# -- metaName2: " << collideIVarMetaName << "\n" + << "# -- In Module : " << m_pModuleScanned->getName() << " | " + << m_pModuleScanned->getSourceFileName() << "\n"; + + assert(false && "IVar Optimization[clang] meta name HASH COLLISION"); + } + + // Insert the mappings into ModuleSummaryIndex + m_Index.setIVarIDToMetaNameMapping(iVarID, iVarMetaName); + } + + return true; +} + +// Find preliminary class size info for a class in +// m_ClassNameToOptInfo +bool IVarOptClangExportHelper::getClassInfoForIVarOpt( + const StringRef &metaClassName, size_t &preliminaryInstanceStart, + size_t &preliminaryInstanceSize, size_t &maxIVarAlign) { + + preliminaryInstanceStart = preliminaryInstanceSize = maxIVarAlign = 0; + + std::string realClassName; + if (!parseRealClassNameFromMetaClassName(metaClassName, realClassName)) { + errs() << "\n#ERROR: IVar Optimization[clang]: " + "Failed to parse metaClassName in getClassInfoForIVarOpt\n" + << "# -- metaClassName: " << metaClassName << "\n"; + return false; + } + + auto itOptInfo = m_ClassNameToOptInfo.find(realClassName); + + if (itOptInfo == m_ClassNameToOptInfo.end()) { + errs() << "\n#ERROR: IVar Optimization[clang]: getClassInfoForIVarOpt " + << "failed - record not found:\n" + << "# -- realClassName: " << realClassName << "\n" + << "# -- metaClassName: " << metaClassName << "\n"; + return false; + } + + IVarOptInfoForClass &instanceExportInfo = itOptInfo->second; + preliminaryInstanceStart = instanceExportInfo.preliminaryInstanceStart; + preliminaryInstanceSize = instanceExportInfo.preliminaryInstanceSize; + maxIVarAlign = instanceExportInfo.maxIVarAlign; + + bool isAlignPowOf2 = (maxIVarAlign & (maxIVarAlign - 1)) == 0; + + if (preliminaryInstanceStart == UINT_MAX || + preliminaryInstanceSize == UINT_MAX || !isAlignPowOf2) { + errs() << "\n#ERROR: IVar Optimization[clang]: getClassInfoForIVarOpt " + "failed - invalid recorddddddddddddd:\n" + << "# -- realClassName: " << realClassName << "\n" + << "# -- metaClassName: " << metaClassName << "\n" + << "# -- instStart: " << preliminaryInstanceStart << "\n" + << "# -- instSize: " << preliminaryInstanceSize << "\n" + << "# -- maxIVarAlign: " << maxIVarAlign << "\n"; + return false; + } + + return true; +} + +// Store info about this IVar in m_ClassNameToClassIVars & m_IVarIDToIVarName +bool IVarOptClangExportHelper::storeDataForIVar( + const GlobalVariable &iVarDefVar, const std::string &iVarRealClassName, + const size_t iVarOffset) { + // Calculate ID for the global, MD5 of + GlobalValue::GUID iVarID = GlobalValue::getGUID(iVarDefVar.getName()); + + // This IVar ID was seen previously ? Either duplicate or hash collision + if (m_IVarIDToIVarName.count(iVarID)) { + if (m_IVarIDToIVarName[iVarID] == iVarDefVar.getName()) { + errs() << "\n#ERROR: IVar Optimization[clang]: " + "Duplicate IVar Definition\n" + << "# -- iVarID: " << iVarID << "\n" + << "# -- iVarName: " << iVarDefVar.getName() << "\n"; + } else { + errs() << "\n#ERROR: IVar Optimization[clang]: " + "HASH COLLISION in IVar Names\n" + << "# -- iVarID: " << iVarID << "\n" + << "# -- iVarName: " << iVarDefVar.getName() << "\n"; + + // Rather than generate compile error and fail the build, don't process + // this module => iVar's wont be optimized for this module + m_ClassNameToClassIVars.empty(); + m_IVarIDToIVarName.empty(); + return false; + } + } + + // Insert the IVar in internal data structures + IVarClangSummaryInfo iVarInfo; + iVarInfo.IVarMetaNameID = iVarID; + iVarInfo.IVarClangOffset = iVarOffset; + m_ClassNameToClassIVars[iVarRealClassName].push_back(iVarInfo); + m_IVarIDToIVarName[iVarID] = std::string(iVarDefVar.getName()); + + IVarOptLog::onStoreDataForIVar(iVarDefVar, iVarRealClassName, iVarID, + iVarOffset); + return true; +} + +// Verify that the global is an IVar Definition and get const offset for it +bool IVarOptClangExportHelper::verifyIsIVarDefVarAndGetOffset( + const GlobalVariable &iVarDefVar, size_t &iVarOffset) { + + if (!iVarDefVar.hasInitializer()) { + // This can be an "extern" iVar, defined in another module + return false; + } + + const ConstantInt *offsetInitializer = + dyn_cast(iVarDefVar.getInitializer()); + + if (!offsetInitializer) { + errs() << "\n#ERROR: IVar Optimization[clang]: " + "iVarOffsetVar initializer is not " + "ConstantInt\n" + << "# -- iVarDefVar: " << iVarDefVar; + return false; + } + + int64_t iVarOffsetVal = offsetInitializer->getSExtValue(); + + // An IVar offset can never be 0 as in ObjC all classes inherit from NSObject + // which has a non-zero size (varies depending on platform) + if (iVarOffsetVal == 0) { + errs() << "\n#ERROR: IVar Optimization[clang]: iVarOffsetVal is ZERO\n" + << "# -- iVarDefVar: " << iVarDefVar << "\n"; + return false; + } + + iVarOffset = (size_t)iVarOffsetVal; + return true; +} + +// Given a GlovalVariable of type "\01l_OBJC_CLASS_RO_$_", parse out +// preliminary class size info +bool IVarOptClangExportHelper::parseClassPreliminarySizeInfoFromRoMetaData( + const GlobalVariable &globalVar, size_t &instanceStart, + size_t &instanceSize) { + const ConstantStruct *cs; + if (!globalVar.hasInitializer() || + !(cs = dyn_cast(globalVar.getInitializer()))) { + errs() << "\n#ERROR: IVar Optimization[clang]: No RO ConstantStruct " + << "initializer : \n" + << "# -- globalVar: " << globalVar << "\n"; + return false; + } + + ConstantInt *metaInstanceStart = dyn_cast(cs->getOperand(1)); + ConstantInt *metaInstanceSize = dyn_cast(cs->getOperand(2)); + instanceStart = metaInstanceStart->getZExtValue(); + instanceSize = metaInstanceSize->getZExtValue(); + return true; +} + +// ============================================================================ +// ================== IVarOptThinLTOSummaryBuilder ============================ +// ============================================================================ + +// Enumerate through interface summaries and populate data structures to +// enable fast lookup of info for classes by class GUID +bool IVarOptThinLTOSummaryBuilder::fillLookupStructures() { + for (auto &P : m_Index) { + for (auto &S : P.second.SummaryList) { + auto summary = S.get(); + if (!isa(summary)) { + continue; + } + + ObjCInterfaceSummary *IfcSum = dyn_cast(summary); + + GlobalValue::GUID classID = IfcSum->getClassID(); + GlobalValue::GUID superClassID = IfcSum->getSuperclassID(); + + m_ClassIDToSuperClassID[classID] = superClassID; + + IVarOptInfoForClass OptInfo; + OptInfo.preliminaryInstanceStart = IfcSum->getPreliminaryInstanceStart(); + OptInfo.preliminaryInstanceSize = IfcSum->getPreliminaryInstanceSize(); + OptInfo.maxIVarAlign = IfcSum->getMaxIVarAlign(); + m_ClassIDToOptInfo[classID] = OptInfo; + + IVarOptLog::onSummaryBuildSetOptInfo(m_Index, IfcSum, OptInfo); + } + } + + return true; +} + +// Get GUID for NSObject class +GlobalValue::GUID IVarOptThinLTOSummaryBuilder::getNSObjectGUID() { + static const GlobalValue::GUID GUID_NSObject = + GlobalValue::getGUID("OBJC_CLASS_$_NSObject"); + return GUID_NSObject; +} + +// Given an ObjCInterfaceSummary, compute the real size of the corresponding +// class +bool IVarOptThinLTOSummaryBuilder::computeRealSizeForClass( + const GlobalValue::GUID classID, size_t &classSize) { + + if (classID == getNSObjectGUID()) { + classSize = m_SizeOfNSObject; + IVarOptLog::onComputeSizeReachNSObject(classSize); + return true; + } + + // Was this already computed before ? Return cached result + auto itRealSize = m_ClassIDToRealClassSize.find(classID); + if (itRealSize != m_ClassIDToRealClassSize.end()) { + // We want complex logging + checks when enabled, so don't use cache + if (IVarOptLog::shouldUseClassSizeCache()) { + classSize = itRealSize->second; + return true; + } + } + + auto itClassInfo = m_ClassIDToOptInfo.find(classID); + if (itClassInfo == m_ClassIDToOptInfo.end()) { + // Prelliminary class size info not found => return false + IVarOptLog::onClassSizeComputeFailFindClassInfo(classID); + return false; + } + IVarOptInfoForClass &classInfo = itClassInfo->second; + + auto itSuper = m_ClassIDToSuperClassID.find(classID); + if (itSuper == m_ClassIDToSuperClassID.end()) { + // Parent not found but itClassInfo found ? Impossible + + errs() << "\n#ERROR: IVar Optimization[LTO_Bld]: " + "computeRealSizeForClass FAILED :\n" + << "# *className [" << m_Index.getClassName(classID) << "]\n" + << "# *classID [" << classID << "]\n\n"; + return false; + } + GlobalValue::GUID superClassID = itSuper->second; + + size_t superClassSize; + // Recursively find size of super class + if (!computeRealSizeForClass(superClassID, superClassSize)) { + IVarOptLog::onClassSizeComputeFailGetBaseSize(classID); + return false; + } + + size_t prelimInstStart = classInfo.preliminaryInstanceStart; + size_t actualInstStart = alignValueUp(superClassSize, classInfo.maxIVarAlign); + + // Check if base class shrunk - this should never happen + if (actualInstStart < prelimInstStart) { + errs() << "\n#ERROR: IVar Optimization[LTO_Bld]: " + "Base class size of class shrunk:\n" + << "# *toplClsName [" << m_Index.getClassName(classID) << "]\n" + << "# *toplClsID [" << classID << "]\n" + << "# *baseClsName [" << m_Index.getClassName(superClassID) + << "]\n" + << "# *baseClsID [" << superClassID << "]\n" + << "# *realBaseSize [" << superClassSize << "]\n" + << "# *topInstStart [" << classInfo.preliminaryInstanceStart + << "]\n" + << "# *topInstSize [" << classInfo.preliminaryInstanceSize + << "]\n\n"; + return false; + } + + if (!calculateRuntimeClassSizeFromParams(classID, superClassID, classInfo, + superClassSize, classSize)) { + return false; + } + + IVarOptLog::onComputedSizeForClass(classID, classSize); + m_ClassIDToRealClassSize[classID] = classSize; + return true; +} + +// Given all params that influence class size at runtime, calculate what the +// actual class size will be +bool IVarOptThinLTOSummaryBuilder::calculateRuntimeClassSizeFromParams( + const GlobalValue::GUID classID, const GlobalValue::GUID superClassID, + const IVarOptInfoForClass &classInfo, const size_t runtimeSizeOfBaseClass, + size_t &finalClassSize) { + + size_t preliminarySizeOfBaseClass = classInfo.preliminaryInstanceStart; + + // By how many bytes did the base class ghorw on us ? + size_t baseClassShift = runtimeSizeOfBaseClass - preliminarySizeOfBaseClass; + m_ClassIDToOptInfo[classID].baseClassShift = baseClassShift; + + // Base hasn't change => preliminaryInstanceSize is valid, return that + if (!baseClassShift) { + finalClassSize = classInfo.preliminaryInstanceSize; + return true; + } + + size_t iVarAlign = classInfo.maxIVarAlign; + size_t growClassBy = baseClassShift; + // Pad the class growth so that the shift is a multiple of iVarAlign + growClassBy = alignValueUp(growClassBy, iVarAlign); + + size_t preliminarySizeOfClass = classInfo.preliminaryInstanceSize; + finalClassSize = preliminarySizeOfClass + growClassBy; + + return true; +} + +// Get some info for the class: base size & opt info +bool IVarOptThinLTOSummaryBuilder::getInterfaceSizeAndOptInfo( + const ObjCInterfaceSummary *IfcSum, size_t &sizeOfClass, + IVarOptInfoForClass &optInfo) { + + GlobalValue::GUID classID = IfcSum->getClassID(); + + IVarOptLog::onBeginComputeClassSize(m_Index, IfcSum, + m_ClassIDToRealClassSize); + bool foundRealSize = computeRealSizeForClass(classID, sizeOfClass); + IVarOptLog::onFinishComputeClassSize(sizeOfClass); + + if (!foundRealSize) { + return false; + } + + if (!m_ClassIDToOptInfo.count(classID)) { + errs() << "\n#ERROR: IVar Optimization[LTO_Bld]: No class info :\n" + << "# *className [" << m_Index.getClassName(classID) << "]\n" + << "# *classID [" << classID << "]\n\n"; + + return false; + } + + optInfo = m_ClassIDToOptInfo[classID]; + size_t preliminarySizeOfClass = optInfo.preliminaryInstanceStart; + + if (preliminarySizeOfClass > sizeOfClass) { + errs() << "\n#ERROR: IVar Optimization[LTO_Bld]:" + " Predicted size grater than actual :\n" + << "# *className [" << m_Index.getClassName(classID) << "]\n" + << "# *classID [" << classID << "]\n" + << "# *prelimSz [" << preliminarySizeOfClass << "]\n" + << "# *actualSz [" << sizeOfClass << "]\n\n"; + + return false; + } + + return true; +} + +// Compute the patch offset that needs to be applied to class IVars +bool IVarOptThinLTOSummaryBuilder::computeClassIVarOffset( + const ObjCInterfaceSummary *IfcSum, const size_t actualSizeOfClass, + const IVarOptInfoForClass &optInfo, size_t &iVarOffset) { + + size_t prelimSizeOfClass = optInfo.preliminaryInstanceSize; + if (prelimSizeOfClass == actualSizeOfClass) { + // The actual size of the class is same as preliminary size of class - + // no need to patch any IVars + iVarOffset = 0; + return true; + } + + if (prelimSizeOfClass > actualSizeOfClass) { + // Class size shrunk - impossible !!! + // This should already be logged in calculateRuntimeClassSizeFromParams + iVarOffset = 0; + return true; + } + + // The offset that IVars should be patched with is the size that the class + // grew by. This size is the size of the hidden variables in base classes + // plus the size of padding inserted in order to keep iVar alignment + + iVarOffset = actualSizeOfClass - prelimSizeOfClass; + return true; +} + +// Check if instance variables in this interface can be optimized and compute +// patch offset if that is the case. +bool IVarOptThinLTOSummaryBuilder::checkCanOptimizeAndComputeClassIVarOffset( + const ObjCInterfaceSummary *IfcSum, size_t &classIVarOffset) { + + size_t actualSizeOfClass, iVarPatchOffset; + IVarOptInfoForClass optInfo; + if (!getInterfaceSizeAndOptInfo(IfcSum, actualSizeOfClass, optInfo)) { + return false; + } + + if (!computeClassIVarOffset(IfcSum, actualSizeOfClass, optInfo, + iVarPatchOffset)) { + return false; + } + + IVarOptLog::onComputeClassPatchOffset(m_Index, IfcSum, iVarPatchOffset, + actualSizeOfClass, optInfo); + + classIVarOffset = iVarPatchOffset; + return true; +} + +// For every IVar in the interface, patch it with the patch offset obtained +// from checkCanOptimizeAndComputeClassIVarOffset and then store it in +// ModuleSummaryIndex via setIVarOffset +bool IVarOptThinLTOSummaryBuilder::patchAndStoreInterfaceIVarOffsets( + const ObjCInterfaceSummary *IfcSum, const size_t classIVarOffset) { + std::vector iVarList = IfcSum->getIVarList(); + + for (IVarClangSummaryInfo &clangIVarInfo : iVarList) { + size_t newIVarOffset = clangIVarInfo.IVarClangOffset + classIVarOffset; + + IVarThinLTOSummaryInfo iVarThinLTOSummaryInfo; + iVarThinLTOSummaryInfo.ClangIVarOffset = clangIVarInfo.IVarClangOffset; + iVarThinLTOSummaryInfo.ThinLTOIVarPatchedOffset = newIVarOffset; + m_Index.setIVarThinLTOSummaryInfo(clangIVarInfo.IVarMetaNameID, + iVarThinLTOSummaryInfo); + + IVarOptLog::onComputeIVarOffset(m_Index, clangIVarInfo.IVarMetaNameID, + clangIVarInfo.IVarClangOffset, + newIVarOffset); + } + + return true; +} + +// Record in ModuleSummaryIndex the iVar offset for this interface +bool IVarOptThinLTOSummaryBuilder::storeInterfaceWithKnownOffsetsInfo( + const ObjCInterfaceSummary *IfcSum, size_t iVarOffset) { + GlobalValue::GUID classID = IfcSum->getClassID(); + + auto itClassSize = m_ClassIDToRealClassSize.find(classID); + if (itClassSize == m_ClassIDToRealClassSize.end()) { + errs() << "\n#ERROR: IVar Optimization[LTO_Bld]:" + " Size of superclass unknown but size of parent known:\n" + << "# *className [" << m_Index.getClassName(classID) << "]\n" + << "# *classID [" << classID << "]\n\n"; + + return false; + } + + auto itClassInfo = m_ClassIDToOptInfo.find(classID); + if (itClassInfo == m_ClassIDToOptInfo.end()) { + errs() << "\n#ERROR: IVar Optimization[LTO_Bld]:" + " Superclass info not found for known-offsets class:\n" + << "# *className [" << m_Index.getClassName(classID) << "]\n" + << "# *classID [" << classID << "]\n\n"; + return false; + } + + IVarOptInfoForClass &classInfo = itClassInfo->second; + + ClassWithIVarsThinLTOSummaryInfo classThinLTOIVarInfo; + classThinLTOIVarInfo.BaseClassGrowth = classInfo.baseClassShift; + classThinLTOIVarInfo.MaxIVarAlign = classInfo.maxIVarAlign; + m_Index.setClassWithIVarsThinLTOSummaryInfo(classID, classThinLTOIVarInfo); + return true; +} + +// Go through all classes in the module summary index and figure out which ones +// we can optimize. Also compute patch offsets for accessing instance variables +bool IVarOptThinLTOSummaryBuilder::processModuleSummaryIndex() { + // Find size of NSObject and store it in ModuleSummaryIndex + if (!computeSizeOfNSObject()) { + IVarOptLog::onFailedComputeSizeOfNSObject(); + return false; + } + + // First, go through all the interface summaries and compute + // m_ClassIDToSuperClassID and m_ClassIDToOptInfo + fillLookupStructures(); + + // Now, for each interface, see if it meets conditions and if so, insert it in + // Index(insertToFullyDefinedClassesSet) for lookup in parallel codegen phase + for (auto &P : m_Index) { + for (auto &S : P.second.SummaryList) { + auto summary = S.get(); + + if (!isa(summary)) { + continue; + } + ObjCInterfaceSummary *IfcSum = dyn_cast(summary); + IVarOptLog::onProcessInterface(m_Index, IfcSum); + + size_t classIVarOffset; + if (!checkCanOptimizeAndComputeClassIVarOffset(IfcSum, classIVarOffset)) { + continue; + } + + if (!patchAndStoreInterfaceIVarOffsets(IfcSum, classIVarOffset)) { + continue; + } + + storeInterfaceWithKnownOffsetsInfo(IfcSum, classIVarOffset); + } + } + + return true; +} + +// Compute the size of NSObject and store it in m_SizeOfNSObject +bool IVarOptThinLTOSummaryBuilder::computeSizeOfNSObject() { + // Try to find a class that has NSObject as immediate base class and get size + // of NSObject from there + for (auto &P : m_Index) { + for (auto &S : P.second.SummaryList) { + auto summary = S.get(); + if (!isa(summary)) { + continue; + } + ObjCInterfaceSummary *IfcSum = dyn_cast(summary); + GlobalValue::GUID superClassID = IfcSum->getSuperclassID(); + if (superClassID != getNSObjectGUID()) + continue; + // IfcSum's inherits from NSObject, so its preliminaryInstanceStart is + // the size of NSObject + m_SizeOfNSObject = IfcSum->getPreliminaryInstanceStart(); + return true; + } + } + m_SizeOfNSObject = 0; + return false; +} diff --git a/llvm/lib/Analysis/IVarOptLog.cpp b/llvm/lib/Analysis/IVarOptLog.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Analysis/IVarOptLog.cpp @@ -0,0 +1,493 @@ +//===-------------------------- IVarOptLog.cpp ----------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/IVarOptLog.h" +#include "llvm/Analysis/IVarOptAnalysis.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Instructions.h" +#include "llvm/Support/CommandLine.h" +#include +#include + +using namespace llvm; + +enum IVarLogOption { + // Disable all warnings (disables important warnings) + no_warn, + + // Log all warnings (enables non-important warnings) + warn, + + // ############# All Clang IVar Analysis Logging ############# + all_clang_analysis, + // Clang Prelim Class Size Info & Max IVar Align + Processed Interfaces + ana_prelim_info, + + // ############# All Summary Builder IVar Analysis Logging ############# + all_sb_analysis, + // Summary Builder Class Size Info + sb_class_info, + // Summary Builder Compute IVar Offset + sb_ivar_offsets, + // Non-Zero Class Patch Offsets + ana_non_zero_patch_offsets, + // Clang Store Ivar Data + Zero Class Patch Offsets + ana_zero_patch_offsets, + // Class Size Compute Detailed logging + ana_class_info, + + // ############# All IVar Info Import/Export Logging ############# + all_imp_exp, + // Log file operations for import/export + impexp_file_ops, + // Log imoprted IVar Info + impexp_imported_entries, + // Log exported IVar Info + impexp_exp_entries, + + // ############# All IVar Direct Logging ############# + all_ivar_direct, + // IVars accesses that were NOT made direct + ida_no_direct, + // IVars accesses that were made direct + ida_yes_direct, + + // ############# Log EVERYTHING ############# + log_all +}; + +static cl::bits IVarOptLogItems( + "ivar-opt-log-options", + cl::desc("Specify IVar optimization logging options:"), + cl::values(clEnumVal(no_warn, "no_warn"), clEnumVal(warn, "warn"), + clEnumVal(all_clang_analysis, "all_clang_analysis"), + clEnumVal(ana_non_zero_patch_offsets, + "ana_non_zero_patch_offsets"), + clEnumVal(ana_prelim_info, "ana_prelim_info"), + clEnumVal(ana_zero_patch_offsets, "ana_zero_patch_offsets"), + clEnumVal(ana_class_info, "ana_class_info"), + clEnumVal(all_sb_analysis, "all_sb_analysis"), + clEnumVal(sb_class_info, "sb_class_info"), + clEnumVal(sb_ivar_offsets, "sb_ivar_offsets"), + clEnumVal(all_imp_exp, "all_imp_exp"), + clEnumVal(impexp_file_ops, "impexp_file_ops"), + clEnumVal(impexp_imported_entries, "impexp_imported_entries"), + clEnumVal(impexp_exp_entries, "impexp_exp_entries"), + clEnumVal(all_ivar_direct, "all_ivar_direct"), + clEnumVal(ida_no_direct, "ida_no_direct"), + clEnumVal(ida_yes_direct, "ida_yes_direct"), + + clEnumVal(log_all, "log_all"))); + +template bool isAnyOfFlagsOrLogAllSet() { return false; } + +template +bool isAnyOfFlagsOrLogAllSet(T First, Ts... rest) { + return IVarOptLogItems.isSet(log_all) || IVarOptLogItems.isSet(First) || + isAnyOfFlagsOrLogAllSet(rest...); +} + +std::atomic IVarOptLog::m_NumIVarsAccessesMadeDirect; +std::atomic IVarOptLog::m_NumIVarsAccessesNotMadeDirect; + +std::atomic IVarOptLog::m_NumClassesIVarErased; +std::atomic IVarOptLog::m_NumClassesIVarErasedWithSizePatch; +std::atomic IVarOptLog::m_NumClassesNotIVarErased; + +std::mutex IVarOptLog::m_OptStageOutputMutex; +const ModuleSummaryIndex *IVarOptLog::m_pCSIndex; +const ObjCInterfaceSummary *IVarOptLog::m_pCSIfcSum; +const std::map *IVarOptLog::m_pCSCacheMap; +bool IVarOptLog::m_bLastCSSuccess; +bool IVarOptLog::b_bLoadingWhiteList; +bool IVarOptLog::m_bPrintedStats = false; + +// This will run after parallel codegen step +bool IVarOptLog::printIVarStats() { + if (m_bPrintedStats) { + return true; + } + m_bPrintedStats = true; + +#define PRINT_HEADER_OR_SEPARATOR \ + errs() \ + << (printedHeader \ + ? "--------------------------------------------------------\n" \ + : "\n\n========================================================" \ + "\n"); \ + printedHeader = true; + + bool printedHeader = false; + PRINT_HEADER_OR_SEPARATOR; + + if (EnableIVarDirectAccessRuntimeCheck) { + errs() << "#### IVar Direct Access: Runtime Checks ENABLED !!!\n"; + } + + errs() << "#### IVar Direct Access: Count made direct - " + << m_NumIVarsAccessesMadeDirect << "\n"; + + errs() << "#### IVar Direct Access: Count left indirect - " + << m_NumIVarsAccessesNotMadeDirect << "\n"; + + if (printedHeader) { + errs() << "========================================================\n\n"; + } + + return true; +} + +// =========================================================================== +std::string IVarOptLog::_padNumber(unsigned long long number, size_t padding) { + std::ostringstream ss; + ss << std::left << std::setfill(' ') << std::setw(padding) << number; + return ss.str(); +} + +// ============================================================================= +// ================= Logging for shared IVar Optimization code ================= +// ============================================================================= +// Failed to compute size of NSObject - might happen if no classes are present +void IVarOptLog::onFailedComputeSizeOfNSObject() { + + if (IVarOptLogItems.isSet(no_warn)) + return; + + errs() << "\n#[IVar_DA][WARN]: Failed to compute size of NSObject\n"; +} + +// Call when finding an IVar that matches prefix but there is something wrong +void IVarOptLog::onInvalidIVarName(const GlobalVariable &iVarOffsetVar) { + + if (!isAnyOfFlagsOrLogAllSet(warn)) + return; + + errs() << "\n#[IVar_DA][WARN][Clang]: Invalid Name for IVar: " + << iVarOffsetVar << "\n"; +} + +// Functions to log various events below +void IVarOptLog::onComputeClassPatchOffset(const ModuleSummaryIndex &Index, + const ObjCInterfaceSummary *IfcSum, + const size_t classIVarOffset, + const size_t actualSizeOfClass, + const IVarOptInfoForClass &optInfo) { + + if (!isAnyOfFlagsOrLogAllSet(all_sb_analysis, ana_zero_patch_offsets, + ana_non_zero_patch_offsets)) + return; + + GlobalValue::GUID classID = IfcSum->getClassID(); + + std::string metaClassName; + if (!Index.getClassName(classID, metaClassName)) { + errs() << "\n#ERROR: IVar Direct Access[SBld]: " + << "onComputeClassPatchOffset - class with ID not found" + << "class meta name:\n" + << "# *classID [" << classID << "]\n" + << "# *metaClsName [" << metaClassName << "]\n"; + } + + std::string realClassName; + if (!parseRealClassNameFromMetaClassName(metaClassName, realClassName)) { + errs() << "\n#ERROR: IVar Direct Access[SBld]: " + << "onComputeClassPatchOffset - failed to parse class meta name:\n" + << "# *classID [" << classID << "]\n" + << "# *metaClsName [" << metaClassName << "]\n" + << "# *realClsName [" << realClassName << "]\n"; + } + + if (classIVarOffset && + isAnyOfFlagsOrLogAllSet(all_sb_analysis, ana_non_zero_patch_offsets)) { + errs() << "\n#[IVar_DA][SBld]: Non-Zero IVar Patch For Class: \n" + << "# *nonZClsName [" << realClassName << "]\n" + << "# *iVarOffset [" << classIVarOffset << "]\n" + << "# *prelSize [" << optInfo.preliminaryInstanceSize << "]\n" + << "# *accSize [" << actualSizeOfClass << "]\n"; + } + + if (!classIVarOffset && + isAnyOfFlagsOrLogAllSet(all_sb_analysis, ana_zero_patch_offsets)) { + errs() << "\n#[IVar_DA][SBld]: Zero IVar Patch For Class: \n" + << "# *zeroClsName [" << realClassName << "]\n" + << "# *accSize [" << actualSizeOfClass << "]\n"; + } +} + +void IVarOptLog::onRecordPreliminaryClassInfo( + const GlobalVariable &classROGlobalVar, const std::string &realClassName, + const IVarOptInfoForClass &sizeInfo) { + + if (!isAnyOfFlagsOrLogAllSet(all_clang_analysis, ana_prelim_info)) + return; + + errs() << "\n#[IVar_DA][Clang]: Store Class Info - SizeInfo: \n" + << "# *storeClsName [" << realClassName << "]\n" + << "# *instStart [" << sizeInfo.preliminaryInstanceStart << "]\n" + << "# *instSize [" << sizeInfo.preliminaryInstanceSize << "]\n" + << "# *classROVar [" << classROGlobalVar << "]\n"; +} + +void IVarOptLog::onRecordMaxIVarAlignForClass( + const GlobalVariable &classIVarListGlobalVar, + const std::string &realClassName, const size_t maxIVarAlign) { + + if (!isAnyOfFlagsOrLogAllSet(all_clang_analysis, ana_prelim_info)) + return; + + errs() << "\n#[IVar_DA][Clang]: Store Class Info - Align: \n" + << "# *storeClsName [" << realClassName << "]\n" + << "# *maxIVarAlign [" << maxIVarAlign << "]\n" + << "# *ivarListVar [" << classIVarListGlobalVar << "]\n"; +} + +void IVarOptLog::onProcessInterface(const ModuleSummaryIndex &Index, + const ObjCInterfaceSummary *IfcSum) { + + if (!isAnyOfFlagsOrLogAllSet(all_sb_analysis, sb_class_info)) + return; + + GlobalValue::GUID ifcID = IfcSum->getInterfaceSummaryID(); + GlobalValue::GUID classID = IfcSum->getClassID(); + GlobalValue::GUID superID = IfcSum->getSuperclassID(); + size_t prelimInstStart = IfcSum->getPreliminaryInstanceStart(); + size_t prelimInstSize = IfcSum->getPreliminaryInstanceSize(); + size_t iVarCount = IfcSum->getIVarList().size(); + + std::string className = Index.getClassName(classID); + std::string superName = Index.getClassName(superID); + + errs() << "\n#[IVar_DA][SBld]: Processing Interface: \n" + << "# *interfaceID [" << ifcID << "]\n" + << "# *procClsID [" << classID << "]\n" + << "# *procClsName [" << className << "]\n" + << "# *baseClsID [" << superID << "]\n" + << "# *baseClsName [" << superName << "]\n" + << "# *prelInstStart[" << prelimInstStart << "]\n" + << "# *prelInstSize [" << prelimInstSize << "]\n" + << "# *iVarCount [" << iVarCount << "]\n"; +} + +void IVarOptLog::onStoreDataForIVar(const GlobalVariable &iVarDefVar, + const std::string &iVarRealClassName, + const GlobalValue::GUID iVarID, + const size_t iVarOffset) { + + if (!isAnyOfFlagsOrLogAllSet(all_clang_analysis, ana_prelim_info)) + return; + + errs() << "\n#[IVar_DA][Clang]: Store IVar Info: \n" + << "# *iVarClsName [" << iVarRealClassName << "]\n" + << "# *iVarID [" << iVarID << "]\n" + << "# *iVarOffset [" << iVarOffset << "]\n" + << "# *iVarDefVar [" << iVarDefVar << "]\n"; +} + +bool IVarOptLog::shouldUseClassSizeCache() { + + bool isClassSizeLoggingEnabled = + isAnyOfFlagsOrLogAllSet(all_sb_analysis, sb_class_info); + return !isClassSizeLoggingEnabled; +} + +void IVarOptLog::onBeginComputeClassSize( + const ModuleSummaryIndex &Index, const ObjCInterfaceSummary *IfcSum, + const std::map &cacheMap) { + + if (!isAnyOfFlagsOrLogAllSet(all_sb_analysis, sb_class_info)) + return; + + // Track Member variables + m_pCSIndex = &Index; + m_pCSIfcSum = IfcSum; + m_pCSCacheMap = &cacheMap; + m_bLastCSSuccess = true; + + GlobalValue::GUID classID = m_pCSIfcSum->getClassID(); + std::string className = m_pCSIndex->getClassName(classID); + + errs() << "\n" + << "#[IVar_DA][SBld]: Begin Compute Class Size: [" << className + << "] -- [" << classID << "]\n"; + + m_bLastCSSuccess = true; +} + +void IVarOptLog::onComputeSizeReachNSObject(const size_t sizeOfNSObject) { + + if (!isAnyOfFlagsOrLogAllSet(all_sb_analysis, sb_class_info)) + return; + + std::string strSize = _padNumber(sizeOfNSObject, 3); + errs() << "# +----- [" << strSize << "] -- [****NSObject****]\n"; +} + +void IVarOptLog::onComputedSizeForClass(const GlobalValue::GUID classID, + const size_t classSize) { + + if (!isAnyOfFlagsOrLogAllSet(all_sb_analysis, sb_class_info)) + return; + + std::string className = m_pCSIndex->getClassName(classID); + std::string strSize = _padNumber(classSize, 3); + errs() << "# +----- [" << strSize << "] -- [" << className << "] -- [" + << classID << "]\n"; +} + +void IVarOptLog::onClassSizeComputeFailFindClassInfo( + const GlobalValue::GUID classID) { + + if (!isAnyOfFlagsOrLogAllSet(all_sb_analysis, sb_class_info)) + return; + + std::string className = m_pCSIndex->getClassName(classID); + errs() << "# +----- Faild to find class Info : [" << className + << "] -- [" << classID << "]\n"; + m_bLastCSSuccess = false; +} + +void IVarOptLog::onClassSizeComputeFailGetBaseSize( + const GlobalValue::GUID classID) { + + if (!isAnyOfFlagsOrLogAllSet(all_sb_analysis, sb_class_info)) + return; + + std::string className = m_pCSIndex->getClassName(classID); + errs() << "# +----- Failed to get size of base class: [" << className + << "] -- [" << classID << "]\n"; +} + +void IVarOptLog::onFinishComputeClassSize(const size_t classSize) { + + if (!isAnyOfFlagsOrLogAllSet(all_sb_analysis, sb_class_info)) + return; + + GlobalValue::GUID classID = m_pCSIfcSum->getClassID(); + std::string className = m_pCSIndex->getClassName(classID); + std::string strSize = _padNumber(classSize, 4); + if (m_bLastCSSuccess) { + errs() << "######### Succeeded compute class size : [" << classSize + << "] -- [" << className << "] -- [" << classID << "]\n"; + } else { + errs() << "######### FAILED compute class size : [" << className + << "] -- [" << classID << "]\n"; + } + + m_pCSIndex = nullptr; + m_pCSIfcSum = nullptr; + m_pCSCacheMap = nullptr; +} + +void IVarOptLog::onSummaryBuildSetOptInfo(const ModuleSummaryIndex &Index, + const ObjCInterfaceSummary *IfcSum, + const IVarOptInfoForClass &sizeInfo) { + + if (!isAnyOfFlagsOrLogAllSet(all_sb_analysis, sb_class_info)) + return; + + GlobalValue::GUID classID = IfcSum->getClassID(); + GlobalValue::GUID superClassID = IfcSum->getSuperclassID(); + + std::string className = Index.getClassName(classID); + std::string superClassName = Index.getClassName(superClassID); + + errs() << "\n#[IVar_DA][SBld]: Setting Class Opt Info: \n" + << "# *setClsName [" << className << "]\n" + << "# *classID [" << classID << "]\n" + << "# *superClsID [" << superClassID << "]\n" + << "# *superClsName [" << superClassName << "]\n" + << "# *instStart [" << sizeInfo.preliminaryInstanceStart << "]\n" + << "# *instSize [" << sizeInfo.preliminaryInstanceSize << "]\n" + << "# *maxIVarAlign [" << sizeInfo.maxIVarAlign << "]\n"; +} + +void IVarOptLog::onComputeIVarOffset(const ModuleSummaryIndex &Index, + const GlobalValue::GUID iVarMetaNameID, + const size_t clangIVarOffset, + const size_t iVarOffset) { + + if (!isAnyOfFlagsOrLogAllSet(all_sb_analysis, sb_ivar_offsets)) + return; + + std::string iVarMetaName; + Index.getIVarMetaNameFromIVarID(iVarMetaNameID, iVarMetaName); + + if (clangIVarOffset == iVarOffset) { + errs() << "\n#[IVar_DA][SBld]: Setting Unpatched Offset For IVar: \n" + << "# *metaName [" << iVarMetaName << "]\n" + << "# *metaNameID [" << iVarMetaNameID << "]\n" + << "# *iVarOffset [" << iVarOffset << "]\n"; + } else { + errs() << "\n#[IVar_DA][SBld]: Setting Patched Offset For IVar: \n" + << "# *metaName [" << iVarMetaName << "]\n" + << "# *metaNameID [" << iVarMetaNameID << "]\n" + << "# *oldOffset [" << clangIVarOffset << "]\n" + << "# *newOffset [" << iVarOffset << "]\n"; + } +} + +// ============================================================================= +// ====================== Logging for IVar Direct Access ======================= +// ============================================================================= +void IVarOptLog::onSkipOptimizeIVarAccess(const std::string &iVarRealClassName, + const LoadInst &loadInstr) { + m_NumIVarsAccessesNotMadeDirect++; + + if (!isAnyOfFlagsOrLogAllSet(all_ivar_direct, ida_no_direct)) + return; + std::lock_guard lock(m_OptStageOutputMutex); + + const GlobalVariable *iVarOffsetVar = + dyn_cast(loadInstr.getPointerOperand()); + + errs() << "\n#[IVar_DA][Opt]: Skip Optimizing IVar Access: \n" + << "# *name [" << iVarOffsetVar->getName() << "]\n" + << "# *Type [" << *iVarOffsetVar->getType() << "]\n" + << "# *offsetVar [" << *iVarOffsetVar << "]\n" + << "# *skipClsName [" << iVarRealClassName << "]\n"; +} + +void IVarOptLog::onOptimizeIVarAccess(const LoadInst &loadInstr, + const Value &replacementConst, + const size_t iVarReplacementOffset) { + m_NumIVarsAccessesMadeDirect++; + + if (!isAnyOfFlagsOrLogAllSet(all_ivar_direct, ida_yes_direct)) + return; + std::lock_guard lock(m_OptStageOutputMutex); + + const GlobalVariable *iVarOffsetVar = + dyn_cast(loadInstr.getPointerOperand()); + + errs() << "\n#[IVar_DA][Opt]: IVar Access Made Direct: \n" + << "# *replaceOff [" << iVarReplacementOffset << "]\n" + << "# *offsetVar [" << *iVarOffsetVar << "]\n" + << "# *loadInstr [" << loadInstr << "]\n"; +} + +void IVarOptLog::onPatchClassSize(std::string &realClassName, + GlobalVariable &classROGlobalVar, + Constant *oldClassSizeOp, + Constant *newClassSizeOp) { + m_NumClassesIVarErasedWithSizePatch++; + if (!isAnyOfFlagsOrLogAllSet(all_ivar_direct, ana_class_info)) + return; + std::lock_guard lock(m_OptStageOutputMutex); + + ConstantInt *oldClassSizeOpInt = dyn_cast(oldClassSizeOp); + ConstantInt *newClassSizeOpInt = dyn_cast(newClassSizeOp); + uint32_t unOldInstSize = oldClassSizeOpInt->getZExtValue(); + uint32_t unNewInstSize = newClassSizeOpInt->getZExtValue(); + + errs() << "\n#[IVar_Meta][Opt]: Patching class runtime size for class \n" + << "# *className [" << realClassName << "]\n" + << "# *unOldInstSz [" << unOldInstSize << "]\n" + << "# *unNewInstSz [" << unNewInstSize << "]\n"; +} + diff --git a/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp b/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp --- a/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp +++ b/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp @@ -23,6 +23,7 @@ #include "llvm/Analysis/BlockFrequencyInfo.h" #include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/Analysis/IndirectCallPromotionAnalysis.h" +#include "llvm/Analysis/IVarOptAnalysis.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/ProfileSummaryInfo.h" #include "llvm/Analysis/TypeMetadataUtils.h" @@ -567,6 +568,71 @@ } } +// Go through the ObjC metadata and generate a summary for each interface. +static void computeInterfaceSummary(ModuleSummaryIndex &Index, + const Module &M) { + IVarOptClangExportHelper iVarSummaryBuilder(Index); + iVarSummaryBuilder.collectDataFromModule(&M); + + // We don't have a list of classes, so we will walk the list of all globals. + for (const GlobalVariable &GV : M.globals()) { + + bool NonRenamableLocal = isNonRenamableLocal(GV); + GlobalValueSummary::GVFlags Flags(GV.getLinkage(), NonRenamableLocal, + false /* LiveRoot */, + true /* Same Link Unit */, + GV.hasLinkOnceODRLinkage() && GV.hasGlobalUnnamedAddr()); + + // Check if this is a class or a category. + auto name = GV.getName(); + if (name.startswith("OBJC_CLASS_")) { + // Get the initializer of this class. + const ConstantStruct *cs; + + if (!GV.hasInitializer() || + !(cs = dyn_cast(GV.getInitializer()))) { + continue; + } + + std::string className = name.str(); + GlobalValue::GUID ClassId = GlobalValue::getGUID(className); + + // Find the superclass name. Superclass is the second operand (@index 1). + std::string superclassName; + GlobalValue::GUID SuperclassId = 0; + if (cs->getOperand(1)) { + superclassName = std::string(cs->getOperand(1)->getName()); + SuperclassId = GlobalValue::getGUID(superclassName); + Index.classIDToString(SuperclassId, superclassName); + } + + std::string interfaceName = className + "_interface"; + GlobalValue::GUID IntSumId = GlobalValue::getGUID(interfaceName); + + Index.classIDToString(ClassId, className); + auto classIVarList = iVarSummaryBuilder.getIVarListForClass(name); + + size_t preliminaryInstanceStart = 0, preliminaryInstanceSize = 0; + size_t maxIVarAlign = 0; + iVarSummaryBuilder.getClassInfoForIVarOpt( + GV.getName(), preliminaryInstanceStart, preliminaryInstanceSize, + maxIVarAlign); + + Index.classIDToString(ClassId, className); + // Note that ClassId is already being used to store another type of + // summary, so here we use IntSumId (ID from [className + "_interface"]). + // Otherwise, this summary would be overwritten. + // In the future, we can piggyback this summary onto the summary stored + // by ClassId. + auto InterfaceSummary = std::make_unique( + Flags, ArrayRef{}, IntSumId, ClassId, SuperclassId, + preliminaryInstanceStart, preliminaryInstanceSize, maxIVarAlign, + classIVarList); + Index.addGlobalValueSummary(interfaceName, std::move(InterfaceSummary)); + } + } +} + static void computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V, DenseSet &CantBePromoted, @@ -644,6 +710,8 @@ const Module &M, std::function GetBFICallback, ProfileSummaryInfo *PSI) { + + llvm::errs() << "LOOOGGG::: buildModuleSummaryIndex \n"; assert(PSI); bool EnableSplitLTOUnit = false; if (auto *MD = mdconst::extract_or_null( @@ -759,6 +827,8 @@ CantBePromoted, IsThinLTO); } + computeInterfaceSummary(Index, M); + // Compute summaries for all variables defined in module, and save in the // index. SmallVector Types; diff --git a/llvm/lib/Bitcode/Reader/BitcodeReader.cpp b/llvm/lib/Bitcode/Reader/BitcodeReader.cpp --- a/llvm/lib/Bitcode/Reader/BitcodeReader.cpp +++ b/llvm/lib/Bitcode/Reader/BitcodeReader.cpp @@ -837,6 +837,8 @@ void addThisModule(); ModuleSummaryIndex::ModuleInfo *getThisModule(); + Error parseObjCStringTable(ArrayRef Record, StringRef Blob, + std::map &NameTable); }; } // end anonymous namespace @@ -5831,7 +5833,9 @@ // in the combined index VST entries). The records also contain // information used for ThinLTO renaming and importing. Record.clear(); - Expected MaybeBitCode = Stream.readRecord(Entry.ID, Record); + + StringRef Blob; + Expected MaybeBitCode = Stream.readRecord(Entry.ID, Record, &Blob); if (!MaybeBitCode) return MaybeBitCode.takeError(); switch (unsigned BitCode = MaybeBitCode.get()) { @@ -6163,11 +6167,112 @@ case bitc::FS_TYPE_ID_METADATA: parseTypeIdCompatibleVtableSummaryRecord(Record); break; + + case bitc::OBJC_STRING_TABLE_CLASS: { + if (Error Err = parseObjCStringTable(Record, Blob, + TheIndex.getClassNameTable())) { + return Err; + } + break; + } + + case bitc::OBJC_STRING_TABLE_IVARS: { + if (Error Err = parseObjCStringTable( + Record, Blob, TheIndex.getIVarIDToMetaNameTable())) { + return Err; + } + break; + } + + case bitc::OBJC_INTERFACE: { + // Handle ObjCInterfaceSummary entry. + unsigned i = 0; + // 1st record is the Flags. + uint64_t RawFlags = Record[i++]; + GlobalValueSummary::GVFlags Flags = + getDecodedGVSummaryFlags(RawFlags, Version); + + // Next record is the Interface Summary GUID. + GlobalValue::GUID IntSumId = Record[i++]; + // Next record is the Class GUID. + GlobalValue::GUID ClassId = Record[i++]; + + auto VI = TheIndex.getOrInsertValueInfo(IntSumId); + // Next record is the Superclass GUID. + GlobalValue::GUID SuperClassId = Record[i++]; + + // Next record is the preliminary class start + size_t PreliminaryInstanceStart = Record[i++]; + // Next record is the preliminary class size + size_t PreliminaryInstanceSize = Record[i++]; + // Next record is the max ivar alignment + size_t MaxIVarAlign = Record[i++]; + + // Next record is the number of IVars. + uint64_t numIVars = Record[i++]; + // Number of IVars is followed by as many IVar ids and offset pairs. + std::vector IVarList; + for (unsigned idx = 0; idx < numIVars; idx++) { + IVarClangSummaryInfo iVarInfo; + iVarInfo.IVarMetaNameID = Record[i++]; + iVarInfo.IVarClangOffset = Record[i++]; + IVarList.push_back(iVarInfo); + } + + // Create the ObjCInterfaceSummary object. + std::vector Refs; + auto IS = std::make_unique( + Flags, std::move(Refs), IntSumId, ClassId, SuperClassId, + PreliminaryInstanceStart, PreliminaryInstanceSize, MaxIVarAlign, + std::move(IVarList)); + + IS->setModulePath(getThisModule()->first()); + TheIndex.addGlobalValueSummary(VI, std::move(IS)); + break; + } } } llvm_unreachable("Exit infinite loop"); } +Error ModuleSummaryIndexBitcodeReader::parseObjCStringTable( + ArrayRef Record, StringRef Blob, + std::map &NameTable) { + if (Record.size() != 2) + return error("Invalid record: objc string table layout"); + + unsigned NumEntries = Record[0]; + unsigned StringsOffset = Record[1]; + if (!NumEntries) + return error("Invalid record: objc string table with no entries"); + if (StringsOffset > Blob.size()) + return error("Invalid record: objc string table corrupt offset"); + + StringRef Lengths = Blob.slice(0, StringsOffset); + SimpleBitstreamCursor R(Lengths); + + StringRef Strings = Blob.drop_front(StringsOffset); + do { + if (R.AtEndOfStream()) + return error("Invalid record: objc string table bad length"); + + auto TheIDEx = R.ReadVBR64(32); + auto SizeEx = R.ReadVBR(6); + if(!TheIDEx || !SizeEx) + return error("Invalid record: objc string table values"); + + uint64_t TheID = TheIDEx.get(); + unsigned Size = SizeEx.get(); + if (Strings.size() < Size) + return error("Invalid record: objc string table truncated chars"); + + NameTable.insert(std::make_pair(TheID, Strings.slice(0, Size))); + Strings = Strings.drop_front(Size); + } while (--NumEntries); + + return Error::success(); +} + // Parse the module string table block into the Index. // This populates the ModulePathStringTable map in the index. Error ModuleSummaryIndexBitcodeReader::parseModuleStringTable() { diff --git a/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp b/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp --- a/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp +++ b/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp @@ -207,6 +207,10 @@ void writePerModuleGlobalValueSummary(); private: + unsigned createIDToStringMapAbbrev(bitc::GlobalValueSummarySymtabCodes TableType); + void writeIDToStringMap(const std::map &Lookup, + SmallVectorImpl &Record, + bitc::GlobalValueSummarySymtabCodes TableType); void writePerModuleFunctionSummaryRecord(SmallVector &NameVals, GlobalValueSummary *Summary, unsigned ValueID, @@ -3649,6 +3653,53 @@ } } +unsigned ModuleBitcodeWriterBase::createIDToStringMapAbbrev( + bitc::GlobalValueSummarySymtabCodes TableType) { + auto Abbv = std::make_shared(); + Abbv->Add(BitCodeAbbrevOp(TableType)); + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // # of entries + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // offset to chars + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob)); + return Stream.EmitAbbrev(std::move(Abbv)); +} + +void ModuleBitcodeWriterBase::writeIDToStringMap( + const std::map &Lookup, + SmallVectorImpl &Record, + bitc::GlobalValueSummarySymtabCodes TableType) { + if (Lookup.empty()) + return; + + assert(TableType == bitc::OBJC_STRING_TABLE_CLASS || + TableType == bitc::OBJC_STRING_TABLE_IVARS && + "Invalid table type encountered!"); + + Record.push_back(TableType); + Record.push_back(Lookup.size()); + + // Emit the sizes of the strings in the blob. + SmallString<256> Blob; + { + BitstreamWriter W(Blob); + for (auto p : Lookup) { + W.EmitVBR64(p.first, 32); + W.EmitVBR(p.second.size(), 6); + } + W.FlushToWord(); + } + + // Add the offset to the strings to the record. + Record.push_back(Blob.size()); + + // Add the strings to the blob. + for (auto p: Lookup) + Blob.append(p.second); + + // Emit the final record. + Stream.EmitRecordWithBlob(createIDToStringMapAbbrev(TableType), Record, Blob); + Record.clear(); +} + // Helper to emit a single function summary record. void ModuleBitcodeWriterBase::writePerModuleFunctionSummaryRecord( SmallVector &NameVals, GlobalValueSummary *Summary, @@ -3892,6 +3943,56 @@ NameVals.clear(); } + // Write Interface summary here. + // We don't have a list of classes anywhere else, + // so we will just go over the index and find interfaces. + for (auto IfcSumIdIter = Index->begin(), e = Index->end(); IfcSumIdIter != e; + IfcSumIdIter++) { + auto &summary = *IfcSumIdIter; + if (summary.second.SummaryList.size() == 0) { + continue; + } + auto *gvSummary = summary.second.SummaryList.front().get(); + if (!gvSummary) { + continue; + } + if (isa(gvSummary)) { + auto *IfcSum = dyn_cast(gvSummary); + // 1st record is the Flags. + NameVals.push_back(getEncodedGVSummaryFlags(IfcSum->flags())); + // Next record is the Interface Summary GUID. + NameVals.push_back(IfcSum->getInterfaceSummaryID()); + // Next record is the Class GUID. + NameVals.push_back(IfcSum->getClassID()); + // Next record is the Superclass GUID. + NameVals.push_back(IfcSum->getSuperclassID()); + + // Next record is the preliminary instance start. + NameVals.push_back(IfcSum->getPreliminaryInstanceStart()); + // Next record is the preliminary instance size. + NameVals.push_back(IfcSum->getPreliminaryInstanceSize()); + // Next record is the max ivar align. + NameVals.push_back(IfcSum->getMaxIVarAlign()); + + const std::vector &IVarList = IfcSum->getIVarList(); + NameVals.push_back((uint64_t)IVarList.size()); + for (const IVarClangSummaryInfo &iVarInfo : IVarList) { + NameVals.push_back(iVarInfo.IVarMetaNameID); + NameVals.push_back(iVarInfo.IVarClangOffset); + } + + // Emit the whole record in the end. + Stream.EmitRecord(bitc::OBJC_INTERFACE, NameVals); + NameVals.clear(); + } + } + + SmallVector Record; + writeIDToStringMap(Index->getClassNameTable(), Record, + bitc::OBJC_STRING_TABLE_CLASS); + writeIDToStringMap(Index->getIVarIDToMetaNameTable(), Record, + bitc::OBJC_STRING_TABLE_IVARS); + Stream.ExitBlock(); } diff --git a/llvm/lib/IR/AsmWriter.cpp b/llvm/lib/IR/AsmWriter.cpp --- a/llvm/lib/IR/AsmWriter.cpp +++ b/llvm/lib/IR/AsmWriter.cpp @@ -2895,6 +2895,8 @@ return "function"; case GlobalValueSummary::GlobalVarKind: return "variable"; + case GlobalValueSummary::InterfaceKind: + return "interface"; } llvm_unreachable("invalid summary kind"); } diff --git a/llvm/lib/LTO/LTO.cpp b/llvm/lib/LTO/LTO.cpp --- a/llvm/lib/LTO/LTO.cpp +++ b/llvm/lib/LTO/LTO.cpp @@ -46,6 +46,7 @@ #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetOptions.h" #include "llvm/Transforms/IPO.h" +#include "llvm/Transforms/IPO/IVarDirectAccess.h" #include "llvm/Transforms/IPO/PassManagerBuilder.h" #include "llvm/Transforms/IPO/WholeProgramDevirt.h" #include "llvm/Transforms/Utils/FunctionImportUtils.h" @@ -146,6 +147,8 @@ AddString(Conf.DefaultTriple); AddString(Conf.DwoDir); + AddUnsigned(EnableIVarDirectAccessRuntimeCheck); + // Include the hash for the current module auto ModHash = Index.getModuleHash(ModuleID); Hasher.update(ArrayRef((uint8_t *)&ModHash[0], sizeof(ModHash))); diff --git a/llvm/lib/LTO/LTOCodeGenerator.cpp b/llvm/lib/LTO/LTOCodeGenerator.cpp --- a/llvm/lib/LTO/LTOCodeGenerator.cpp +++ b/llvm/lib/LTO/LTOCodeGenerator.cpp @@ -15,6 +15,7 @@ #include "llvm/ADT/Statistic.h" #include "llvm/ADT/StringExtras.h" +#include "llvm/Analysis/IVarOptLog.h" #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetTransformInfo.h" @@ -149,6 +150,7 @@ initializeMemCpyOptLegacyPassPass(R); initializeDCELegacyPassPass(R); initializeCFGSimplifyPassPass(R); + initializeIVarDirectAccessLegacyPassPass(R); } void LTOCodeGenerator::setAsmUndefinedRefs(LTOModule *Mod) { @@ -587,6 +589,8 @@ // Run our queue of passes all at once now, efficiently. passes.run(*MergedModule); + IVarOptLog::printIVarStats(); + return true; } diff --git a/llvm/lib/LTO/ThinLTOCodeGenerator.cpp b/llvm/lib/LTO/ThinLTOCodeGenerator.cpp --- a/llvm/lib/LTO/ThinLTOCodeGenerator.cpp +++ b/llvm/lib/LTO/ThinLTOCodeGenerator.cpp @@ -16,6 +16,8 @@ #include "llvm/ADT/Statistic.h" #include "llvm/ADT/StringExtras.h" +#include "llvm/Analysis/IVarOptAnalysis.h" +#include "llvm/Analysis/IVarOptLog.h" #include "llvm/Analysis/ModuleSummaryAnalysis.h" #include "llvm/Analysis/ProfileSummaryInfo.h" #include "llvm/Analysis/TargetLibraryInfo.h" @@ -971,6 +973,9 @@ // Synthesize entry counts for functions in the combined index. computeSyntheticCounts(*Index); + IVarOptThinLTOSummaryBuilder iVarOptThinLTOSummaryBuilder(*Index); + iVarOptThinLTOSummaryBuilder.processModuleSummaryIndex(); + // Currently there is no support for enabling whole program visibility via a // linker option in the old LTO API, but this call allows it to be specified // via the internal option. Must be done before WPD below. @@ -1141,4 +1146,6 @@ if (llvm::AreStatisticsEnabled()) llvm::PrintStatistics(); reportAndResetTimings(); + + IVarOptLog::printIVarStats(); } diff --git a/llvm/lib/Transforms/IPO/CMakeLists.txt b/llvm/lib/Transforms/IPO/CMakeLists.txt --- a/llvm/lib/Transforms/IPO/CMakeLists.txt +++ b/llvm/lib/Transforms/IPO/CMakeLists.txt @@ -16,6 +16,7 @@ GlobalDCE.cpp GlobalOpt.cpp GlobalSplit.cpp + IVarDirectAccess.cpp HotColdSplitting.cpp IPConstantPropagation.cpp IPO.cpp diff --git a/llvm/lib/Transforms/IPO/IPO.cpp b/llvm/lib/Transforms/IPO/IPO.cpp --- a/llvm/lib/Transforms/IPO/IPO.cpp +++ b/llvm/lib/Transforms/IPO/IPO.cpp @@ -40,6 +40,7 @@ initializeSimpleInlinerPass(Registry); initializeInferFunctionAttrsLegacyPassPass(Registry); initializeInternalizeLegacyPassPass(Registry); + initializeIVarDirectAccessLegacyPassPass(Registry); initializeLoopExtractorPass(Registry); initializeBlockExtractorPass(Registry); initializeSingleLoopExtractorPass(Registry); diff --git a/llvm/lib/Transforms/IPO/IVarDirectAccess.cpp b/llvm/lib/Transforms/IPO/IVarDirectAccess.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Transforms/IPO/IVarDirectAccess.cpp @@ -0,0 +1,305 @@ +//===- IVarDirectAccess.cpp - Detect accesses to ivars -------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/IPO/IVarDirectAccess.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/IVarOptAnalysis.h" +#include "llvm/Analysis/IVarOptLog.h" +#include "llvm/Analysis/ModuleSummaryAnalysis.h" +#include "llvm/InitializePasses.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instruction.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/ModuleSummaryIndex.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/FormatVariadic.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/IPO.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" + +#include "llvm/LTO/legacy/ThinLTOCodeGenerator.h" + +using namespace llvm; + +#define DEBUG_TYPE "ivardirect" + +// ============================================================================ +// ===================== ThinLTO Parallel(CodeGen) Stage ====================== +// ============================================================================ + +// Can we optimize a specific load instruction (Load from a IVar Global Offset +// that meets criteria?) +bool IVarDirectAccessCodeOptimizer::verifyIsOptimizableLoadAndGetIVarClassName( + const LoadInst &loadInstr, std::string &realClassName) { + // This is the operand that says where the load instruction loads data from + const Value *addrOperand = loadInstr.getPointerOperand(); + + // IVar Global Offsets are all GlobalVariable's - check it + const GlobalVariable *iVarOffsetVar = + dyn_cast(addrOperand); + + if (!iVarOffsetVar) { + return false; + } + + // Name-based checking if this is indeed a IVar Global Offsets + if (!verifyIsIVarGlobalOffsetAndGetRealClassName(*iVarOffsetVar, + realClassName)) { + return false; + } + + return true; +} + +bool IVarDirectAccessCodeOptimizer::getReplacementOffsetForIVar( + const LoadInst &loadInstr, const std::string &iVarRealClassName, + size_t &iVarOffset) { + + const GlobalVariable *iVarOffsetVar = + dyn_cast(loadInstr.getPointerOperand()); + + GlobalValue::GUID iVarID = GlobalValue::getGUID(iVarOffsetVar->getName()); + + IVarThinLTOSummaryInfo iVarThinLTOSummaryInfo; + if (!m_ImportSummary.getIVarThinLTOSummaryInfo(iVarID, + iVarThinLTOSummaryInfo)) { + IVarOptLog::onSkipOptimizeIVarAccess(iVarRealClassName, loadInstr); + return false; + } + + iVarOffset = iVarThinLTOSummaryInfo.ThinLTOIVarPatchedOffset; + return true; +} + +// Build a replacement Value(constant int) for that can replace the LoadInst +Value *IVarDirectAccessCodeOptimizer::buildReplacementConstForLoad( + const LoadInst &loadInstr, size_t iVarReplacementOffset) { + // This will varry based on the architecture. Ex: + // - Simulator(x86_64): 64 bit + // - iPhone 8 (arm64): 32 bit + llvm::Type *iVarOffsetType = loadInstr.getType(); + + // Create replacement const + return llvm::ConstantInt::get(iVarOffsetType, iVarReplacementOffset); +} + +// Check if IVar Direct Access can be applied to a LoadInst and apply it if so +bool IVarDirectAccessCodeOptimizer::tryConvertLoadToConstant( + LoadInst &loadInstr) { + + // Check if can apply optimization to instruction + std::string iVarRealClassName; + + if (!verifyIsOptimizableLoadAndGetIVarClassName(loadInstr, + iVarRealClassName)) { + return false; + } + + size_t iVarReplacementOffset; + if (!getReplacementOffsetForIVar(loadInstr, iVarRealClassName, + iVarReplacementOffset)) { + return false; + } + + // Build a compile-time const value to replace the load instruction + Value *replacementConst = + buildReplacementConstForLoad(loadInstr, iVarReplacementOffset); + if (!replacementConst) { + return false; + } + + // Record optimizing an iVar + IVarOptLog::onOptimizeIVarAccess(loadInstr, *replacementConst, + iVarReplacementOffset); + m_CurrentLoadInBlock++; + + // If runtime check is enabled (debugging), use a const offset, but keep the + // load and perform a runtime check against the offset + if (EnableIVarDirectAccessRuntimeCheck) { + return replaceLoadValueWithConstAndCheck(loadInstr, replacementConst); + } + + // Replace the load with a const + return replaceIVarLoadInstrWithConst(loadInstr, replacementConst); +} + +// This does the actual replacing of the load with a const +bool IVarDirectAccessCodeOptimizer::replaceIVarLoadInstrWithConst( + LoadInst &loadInstr, Value *replacementConst) { + // Do the actual optimization - replace the load with a const + loadInstr.replaceAllUsesWith(replacementConst); + + // Erasing current instruction, move to next + m_CurrentInstructionIterator++; + + // Erase the load instruction - it has no use now + loadInstr.eraseFromParent(); + + return true; +} + +// This replaces the access with a const, but does not remove the load. Instead, +// the load is still performed and checked against the predicted const. Trigger +// infinite loop if check fails. Enable via EnableIVarDirectAccessRuntimeCheck +bool IVarDirectAccessCodeOptimizer::replaceLoadValueWithConstAndCheck( + LoadInst &loadInstr, Value *replacementConst) { + + // Replace all uses of the load with the const, leaving it floating + loadInstr.replaceAllUsesWith(replacementConst); + + // Instruction following the IVar offset load + Instruction *afterLoadInstr = &*(++loadInstr.getIterator()); + + // Compare result of IVar load against expected constant, inserted right after + // the load - insert the compare right after the load + CmpInst *valueValidationBranch = + CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_NE, replacementConst, + &loadInstr, "", afterLoadInstr); + + // Split the block containing the load into 3 basic block. The middle block + // will be returned containing a single branch instruction + BranchInst *middleBlockBranch = (BranchInst *)llvm::SplitBlockAndInsertIfThen( + valueValidationBranch, afterLoadInstr, false); + + std::string ivarCastInstrName = loadInstr.getName().data(); + ivarCastInstrName += "_ValueCast"; + + Module &M = *loadInstr.getModule(); + Type *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext()); + PointerType *IntPtrPtrTy = IntPtrTy->getPointerTo(); + IntToPtrInst *castInstrResultToPtr = new IntToPtrInst( + &loadInstr, IntPtrPtrTy, ivarCastInstrName, middleBlockBranch); + + std::string ivarAVLoadName = loadInstr.getName().data(); + ivarAVLoadName += "_AVLoad"; + new LoadInst(castInstrResultToPtr, ivarAVLoadName, + /*isVolatile*/ true, middleBlockBranch); + + // Give nice names to the blocks / instructions + const std::string &origBlockName = loadInstr.getParent()->getName().data(); + + // Set name of block containing the IVar load + std::string ivarLoadBBName = + formatv("{0}_preIVarLoad_{1}", origBlockName, m_CurrentLoadInBlock); + loadInstr.getParent()->setName(ivarLoadBBName); + + // Set the name of the verification compare instruction + std::string cmpInstrName = formatv("verifyLoad_{0}", m_CurrentLoadInBlock); + valueValidationBranch->setName(cmpInstrName); + + // Set the name of the middle AV block + std::string middleBlockName = formatv("{0}_wrongIVarLoadCrash_{1}", + origBlockName, m_CurrentLoadInBlock); + middleBlockBranch->getParent()->setName(middleBlockName); + + // Set the name of what remains of the block to the original block name + BasicBlock *postLoadBB = &*(++middleBlockBranch->getParent()->getIterator()); + postLoadBB->setName(origBlockName); + + // Resume scanning at 2nd half that resulting from original block split + m_pCurrentBlock = postLoadBB; + m_CurrentInstructionIterator = postLoadBB->begin(); + + return true; +} + +// Go through all the instructions in the module and detect accesses to ivars +// When an access is detected, remove the indirection +bool IVarDirectAccessCodeOptimizer::optimizeIVarAccessesInModule(Module &M) { + // Go through all instructions + for (Function &Fn : M) { + for (BasicBlock &BB : Fn) { + m_CurrentLoadInBlock = 0; + + m_pCurrentBlock = &BB; + m_CurrentInstructionIterator = BB.begin(); + + while (m_CurrentInstructionIterator != m_pCurrentBlock->end()) { + Instruction &I = *m_CurrentInstructionIterator; + + // We are looking for the instruction that loads the IVar offset from + // global data. So even if storing data to an IVar, a load will be + // generated, loading the offset from memory and then storing to the + // actual IVar using the loaded offset. + LoadInst *LI = dyn_cast(&I); + if (!LI) { + m_CurrentInstructionIterator++; + continue; + } + + llvm::errs() << *LI << "\n----------------------\n"; + + // Try apply IVar Direct Access to LoadInst + if (!tryConvertLoadToConstant(*LI)) { + m_CurrentInstructionIterator++; + continue; + } + } + } + } + + return true; +} + +// ============================================================================ +// ======================= Register the pass with llvm ======================== +// ============================================================================ +namespace { +struct IVarDirectAccessLegacyPass : public ModulePass { + const ModuleSummaryIndex *ImportSummary; + + static char ID; // Pass identification + IVarDirectAccessLegacyPass() : ModulePass(ID), ImportSummary(nullptr) { + initializeIVarDirectAccessLegacyPassPass(*PassRegistry::getPassRegistry()); + } + + IVarDirectAccessLegacyPass(const ModuleSummaryIndex *ImportSummary) + : ModulePass(ID), ImportSummary(ImportSummary) { + initializeIVarDirectAccessLegacyPassPass(*PassRegistry::getPassRegistry()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + if (ImportSummary == nullptr) { + AU.addRequired(); + } + } + + bool runOnModule(Module &M) override { + if (skipModule(M)) + return false; + // During monolithic LTO, we need to get ModuleSummaryIndex of the + // MergedModule from ModuleSummaryIndexWrapperPass. + if (ImportSummary == nullptr) { + auto *index = &(getAnalysis().getIndex()); + IVarOptThinLTOSummaryBuilder iVarOptThinLTOSummaryBuilder(*index); + iVarOptThinLTOSummaryBuilder.processModuleSummaryIndex(); + ImportSummary = index; + } + + IVarDirectAccessCodeOptimizer codeOptimizer(*ImportSummary); + return codeOptimizer.optimizeIVarAccessesInModule(M); + } +}; +} // namespace + +char IVarDirectAccessLegacyPass::ID = 0; +INITIALIZE_PASS_BEGIN(IVarDirectAccessLegacyPass, "ivardirect", + "IVar Direct access", false, false) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(ModuleSummaryIndexWrapperPass) +INITIALIZE_PASS_END(IVarDirectAccessLegacyPass, "ivardirect", + "IVar Direct access", false, false) + +llvm::ModulePass *llvm::createIVarDirectAccessLegacyPass( + const ModuleSummaryIndex *ImportSummary) { + return new IVarDirectAccessLegacyPass(ImportSummary); +} diff --git a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp --- a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp +++ b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp @@ -20,6 +20,7 @@ #include "llvm/Analysis/CFLSteensAliasAnalysis.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/InlineCost.h" +#include "llvm/Analysis/IVarOptAnalysis.h" #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/ScopedNoAliasAA.h" #include "llvm/Analysis/TargetLibraryInfo.h" @@ -35,6 +36,7 @@ #include "llvm/Transforms/IPO/ForceFunctionAttrs.h" #include "llvm/Transforms/IPO/FunctionAttrs.h" #include "llvm/Transforms/IPO/InferFunctionAttrs.h" +#include "llvm/Transforms/IPO/IVarDirectAccess.h" #include "llvm/Transforms/InstCombine/InstCombine.h" #include "llvm/Transforms/Instrumentation.h" #include "llvm/Transforms/Scalar.h" @@ -866,6 +868,8 @@ // Infer attributes about declarations if possible. PM.add(createInferFunctionAttrsLegacyPass()); + PM.add(createIVarDirectAccessLegacyPass(nullptr)); + if (OptLevel > 1) { // Split call-site with more constrained arguments. PM.add(createCallSiteSplittingPass()); @@ -1058,6 +1062,8 @@ if (VerifyInput) PM.add(createVerifierPass()); + PM.add(createIVarDirectAccessLegacyPass(ImportSummary)); + if (ImportSummary) { // These passes import type identifier resolutions for whole-program // devirtualization and CFI. They must run early because other passes may