X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FProfileData%2FInstrProf.cpp;h=d6777639abe7ab2adf873d97fb6976adc027e75f;hp=2dd0f916c6d25955071b6d341932f9cc452607fb;hb=21314fb7684a3055e440155016b95b91c7cae9bb;hpb=0833ccb526c74402438bfc5f5a79606de9991156 diff --git a/lib/ProfileData/InstrProf.cpp b/lib/ProfileData/InstrProf.cpp index 2dd0f916c6d..d6777639abe 100644 --- a/lib/ProfileData/InstrProf.cpp +++ b/lib/ProfileData/InstrProf.cpp @@ -12,12 +12,15 @@ // //===----------------------------------------------------------------------===// +#include "llvm/ProfileData/InstrProf.h" +#include "llvm/ADT/StringExtras.h" #include "llvm/IR/Constants.h" #include "llvm/IR/Function.h" -#include "llvm/IR/Module.h" #include "llvm/IR/GlobalVariable.h" -#include "llvm/ProfileData/InstrProf.h" +#include "llvm/IR/Module.h" +#include "llvm/Support/Compression.h" #include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/LEB128.h" #include "llvm/Support/ManagedStatic.h" using namespace llvm; @@ -74,7 +77,8 @@ namespace llvm { std::string getPGOFuncName(StringRef RawFuncName, GlobalValue::LinkageTypes Linkage, - StringRef FileName) { + StringRef FileName, + uint64_t Version LLVM_ATTRIBUTE_UNUSED) { // Function names may be prefixed with a binary '1' to indicate // that the backend should not modify the symbols due to any platform @@ -96,8 +100,38 @@ std::string getPGOFuncName(StringRef RawFuncName, return FuncName; } -std::string getPGOFuncName(const Function &F) { - return getPGOFuncName(F.getName(), F.getLinkage(), F.getParent()->getName()); +std::string getPGOFuncName(const Function &F, uint64_t Version) { + return getPGOFuncName(F.getName(), F.getLinkage(), F.getParent()->getName(), + Version); +} + +StringRef getFuncNameWithoutPrefix(StringRef PGOFuncName, StringRef FileName) { + if (FileName.empty()) + return PGOFuncName; + // Drop the file name including ':'. See also getPGOFuncName. + if (PGOFuncName.startswith(FileName)) + PGOFuncName = PGOFuncName.drop_front(FileName.size() + 1); + return PGOFuncName; +} + +// \p FuncName is the string used as profile lookup key for the function. A +// symbol is created to hold the name. Return the legalized symbol name. +static std::string getPGOFuncNameVarName(StringRef FuncName, + GlobalValue::LinkageTypes Linkage) { + std::string VarName = getInstrProfNameVarPrefix(); + VarName += FuncName; + + if (!GlobalValue::isLocalLinkage(Linkage)) + return VarName; + + // Now fix up illegal chars in local VarName that may upset the assembler. + const char *InvalidChars = "-:<>\"'"; + size_t found = VarName.find_first_of(InvalidChars); + while (found != std::string::npos) { + VarName[found] = '_'; + found = VarName.find_first_of(InvalidChars, found + 1); + } + return VarName; } GlobalVariable *createPGOFuncNameVar(Module &M, @@ -118,7 +152,7 @@ GlobalVariable *createPGOFuncNameVar(Module &M, auto *Value = ConstantDataArray::getString(M.getContext(), FuncName, false); auto FuncNameVar = new GlobalVariable(M, Value->getType(), true, Linkage, Value, - Twine(getInstrProfNameVarPrefix()) + FuncName); + getPGOFuncNameVarName(FuncName, Linkage)); // Hide the symbol so that we correctly get a copy for each executable. if (!GlobalValue::isLocalLinkage(FuncNameVar->getLinkage())) @@ -131,66 +165,312 @@ GlobalVariable *createPGOFuncNameVar(Function &F, StringRef FuncName) { return createPGOFuncNameVar(*F.getParent(), F.getLinkage(), FuncName); } -namespace IndexedInstrProf { +int collectPGOFuncNameStrings(const std::vector &NameStrs, + bool doCompression, std::string &Result) { + uint8_t Header[16], *P = Header; + std::string UncompressedNameStrings = + join(NameStrs.begin(), NameStrs.end(), StringRef(" ")); + + unsigned EncLen = encodeULEB128(UncompressedNameStrings.length(), P); + P += EncLen; + + auto WriteStringToResult = [&](size_t CompressedLen, + const std::string &InputStr) { + EncLen = encodeULEB128(CompressedLen, P); + P += EncLen; + char *HeaderStr = reinterpret_cast(&Header[0]); + unsigned HeaderLen = P - &Header[0]; + Result.append(HeaderStr, HeaderLen); + Result += InputStr; + return 0; + }; + + if (!doCompression) + return WriteStringToResult(0, UncompressedNameStrings); + + SmallVector CompressedNameStrings; + zlib::Status Success = + zlib::compress(StringRef(UncompressedNameStrings), CompressedNameStrings, + zlib::BestSizeCompression); + + if (Success != zlib::StatusOK) + return 1; + + return WriteStringToResult( + CompressedNameStrings.size(), + std::string(CompressedNameStrings.data(), CompressedNameStrings.size())); +} -uint32_t ValueProfRecord::getHeaderSize(uint32_t NumValueSites) { - uint32_t Size = offsetof(ValueProfRecord, SiteCountArray) + - sizeof(uint8_t) * NumValueSites; - // Round the size to multiple of 8 bytes. - Size = (Size + 7) & ~7; - return Size; +StringRef getPGOFuncNameInitializer(GlobalVariable *NameVar) { + auto *Arr = cast(NameVar->getInitializer()); + StringRef NameStr = + Arr->isCString() ? Arr->getAsCString() : Arr->getAsString(); + return NameStr; } -uint32_t ValueProfRecord::getSize(uint32_t NumValueSites, - uint32_t NumValueData) { - return getHeaderSize(NumValueSites) + - sizeof(InstrProfValueData) * NumValueData; +int collectPGOFuncNameStrings(const std::vector &NameVars, + std::string &Result) { + std::vector NameStrs; + for (auto *NameVar : NameVars) { + NameStrs.push_back(getPGOFuncNameInitializer(NameVar)); + } + return collectPGOFuncNameStrings(NameStrs, zlib::isAvailable(), Result); } -void ValueProfRecord::deserializeTo(InstrProfRecord &Record, - InstrProfRecord::ValueMapType *VMap) { - Record.reserveSites(Kind, NumValueSites); +int readPGOFuncNameStrings(StringRef NameStrings, InstrProfSymtab &Symtab) { + const uint8_t *P = reinterpret_cast(NameStrings.data()); + const uint8_t *EndP = reinterpret_cast(NameStrings.data() + + NameStrings.size()); + while (P < EndP) { + uint32_t N; + uint64_t UncompressedSize = decodeULEB128(P, &N); + P += N; + uint64_t CompressedSize = decodeULEB128(P, &N); + P += N; + bool isCompressed = (CompressedSize != 0); + SmallString<128> UncompressedNameStrings; + StringRef NameStrings; + if (isCompressed) { + StringRef CompressedNameStrings(reinterpret_cast(P), + CompressedSize); + if (zlib::uncompress(CompressedNameStrings, UncompressedNameStrings, + UncompressedSize) != zlib::StatusOK) + return 1; + P += CompressedSize; + NameStrings = StringRef(UncompressedNameStrings.data(), + UncompressedNameStrings.size()); + } else { + NameStrings = + StringRef(reinterpret_cast(P), UncompressedSize); + P += UncompressedSize; + } + // Now parse the name strings. + SmallVector Names; + NameStrings.split(Names, ' '); + for (StringRef &Name : Names) + Symtab.addFuncName(Name); + + while (P < EndP && *P == 0) + P++; + } + Symtab.finalizeSymtab(); + return 0; +} - InstrProfValueData *ValueData = this->getValueData(); - for (uint64_t VSite = 0; VSite < NumValueSites; ++VSite) { - uint8_t ValueDataCount = this->SiteCountArray[VSite]; - Record.addValueData(Kind, VSite, ValueData, ValueDataCount, VMap); - ValueData += ValueDataCount; +instrprof_error InstrProfValueSiteRecord::merge(InstrProfValueSiteRecord &Input, + uint64_t Weight) { + this->sortByTargetValues(); + Input.sortByTargetValues(); + auto I = ValueData.begin(); + auto IE = ValueData.end(); + instrprof_error Result = instrprof_error::success; + for (auto J = Input.ValueData.begin(), JE = Input.ValueData.end(); J != JE; + ++J) { + while (I != IE && I->Value < J->Value) + ++I; + if (I != IE && I->Value == J->Value) { + bool Overflowed; + I->Count = SaturatingMultiplyAdd(J->Count, Weight, I->Count, &Overflowed); + if (Overflowed) + Result = instrprof_error::counter_overflow; + ++I; + continue; + } + ValueData.insert(I, *J); + } + return Result; +} + +instrprof_error InstrProfValueSiteRecord::scale(uint64_t Weight) { + instrprof_error Result = instrprof_error::success; + for (auto I = ValueData.begin(), IE = ValueData.end(); I != IE; ++I) { + bool Overflowed; + I->Count = SaturatingMultiply(I->Count, Weight, &Overflowed); + if (Overflowed) + Result = instrprof_error::counter_overflow; + } + return Result; +} + +// Merge Value Profile data from Src record to this record for ValueKind. +// Scale merged value counts by \p Weight. +instrprof_error InstrProfRecord::mergeValueProfData(uint32_t ValueKind, + InstrProfRecord &Src, + uint64_t Weight) { + uint32_t ThisNumValueSites = getNumValueSites(ValueKind); + uint32_t OtherNumValueSites = Src.getNumValueSites(ValueKind); + if (ThisNumValueSites != OtherNumValueSites) + return instrprof_error::value_site_count_mismatch; + std::vector &ThisSiteRecords = + getValueSitesForKind(ValueKind); + std::vector &OtherSiteRecords = + Src.getValueSitesForKind(ValueKind); + instrprof_error Result = instrprof_error::success; + for (uint32_t I = 0; I < ThisNumValueSites; I++) + MergeResult(Result, ThisSiteRecords[I].merge(OtherSiteRecords[I], Weight)); + return Result; +} + +instrprof_error InstrProfRecord::merge(InstrProfRecord &Other, + uint64_t Weight) { + // If the number of counters doesn't match we either have bad data + // or a hash collision. + if (Counts.size() != Other.Counts.size()) + return instrprof_error::count_mismatch; + + instrprof_error Result = instrprof_error::success; + + for (size_t I = 0, E = Other.Counts.size(); I < E; ++I) { + bool Overflowed; + Counts[I] = + SaturatingMultiplyAdd(Other.Counts[I], Weight, Counts[I], &Overflowed); + if (Overflowed) + Result = instrprof_error::counter_overflow; } + + for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind) + MergeResult(Result, mergeValueProfData(Kind, Other, Weight)); + + return Result; +} + +instrprof_error InstrProfRecord::scaleValueProfData(uint32_t ValueKind, + uint64_t Weight) { + uint32_t ThisNumValueSites = getNumValueSites(ValueKind); + std::vector &ThisSiteRecords = + getValueSitesForKind(ValueKind); + instrprof_error Result = instrprof_error::success; + for (uint32_t I = 0; I < ThisNumValueSites; I++) + MergeResult(Result, ThisSiteRecords[I].scale(Weight)); + return Result; } -void ValueProfRecord::serializeFrom(const InstrProfRecord &Record, - uint32_t ValueKind, - uint32_t NumValueSites) { - Kind = ValueKind; - this->NumValueSites = NumValueSites; - InstrProfValueData *DstVD = getValueData(); - for (uint32_t S = 0; S < NumValueSites; S++) { - uint32_t ND = Record.getNumValueDataForSite(ValueKind, S); - SiteCountArray[S] = ND; - std::unique_ptr SrcVD = - Record.getValueForSite(ValueKind, S); - for (uint32_t I = 0; I < ND; I++) { - DstVD[I] = SrcVD[I]; - switch (ValueKind) { - case IPVK_IndirectCallTarget: - DstVD[I].Value = ComputeHash(HashType, (const char *)DstVD[I].Value); - break; - default: - llvm_unreachable("value kind not handled !"); - } +instrprof_error InstrProfRecord::scale(uint64_t Weight) { + instrprof_error Result = instrprof_error::success; + for (auto &Count : this->Counts) { + bool Overflowed; + Count = SaturatingMultiply(Count, Weight, &Overflowed); + if (Overflowed && Result == instrprof_error::success) { + Result = instrprof_error::counter_overflow; } - DstVD += ND; } + for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind) + MergeResult(Result, scaleValueProfData(Kind, Weight)); + + return Result; } -template -static T swapToHostOrder(const unsigned char *&D, support::endianness Orig) { - using namespace support; - if (Orig == little) - return endian::readNext(D); +// Map indirect call target name hash to name string. +uint64_t InstrProfRecord::remapValue(uint64_t Value, uint32_t ValueKind, + ValueMapType *ValueMap) { + if (!ValueMap) + return Value; + switch (ValueKind) { + case IPVK_IndirectCallTarget: { + auto Result = + std::lower_bound(ValueMap->begin(), ValueMap->end(), Value, + [](const std::pair &LHS, + uint64_t RHS) { return LHS.first < RHS; }); + if (Result != ValueMap->end()) + Value = (uint64_t)Result->second; + break; + } + } + return Value; +} + +void InstrProfRecord::addValueData(uint32_t ValueKind, uint32_t Site, + InstrProfValueData *VData, uint32_t N, + ValueMapType *ValueMap) { + for (uint32_t I = 0; I < N; I++) { + VData[I].Value = remapValue(VData[I].Value, ValueKind, ValueMap); + } + std::vector &ValueSites = + getValueSitesForKind(ValueKind); + if (N == 0) + ValueSites.push_back(InstrProfValueSiteRecord()); else - return endian::readNext(D); + ValueSites.emplace_back(VData, VData + N); +} + +#define INSTR_PROF_COMMON_API_IMPL +#include "llvm/ProfileData/InstrProfData.inc" + +/*! + * \brief ValueProfRecordClosure Interface implementation for InstrProfRecord + * class. These C wrappers are used as adaptors so that C++ code can be + * invoked as callbacks. + */ +uint32_t getNumValueKindsInstrProf(const void *Record) { + return reinterpret_cast(Record)->getNumValueKinds(); +} + +uint32_t getNumValueSitesInstrProf(const void *Record, uint32_t VKind) { + return reinterpret_cast(Record) + ->getNumValueSites(VKind); +} + +uint32_t getNumValueDataInstrProf(const void *Record, uint32_t VKind) { + return reinterpret_cast(Record) + ->getNumValueData(VKind); +} + +uint32_t getNumValueDataForSiteInstrProf(const void *R, uint32_t VK, + uint32_t S) { + return reinterpret_cast(R) + ->getNumValueDataForSite(VK, S); +} + +void getValueForSiteInstrProf(const void *R, InstrProfValueData *Dst, + uint32_t K, uint32_t S, + uint64_t (*Mapper)(uint32_t, uint64_t)) { + return reinterpret_cast(R)->getValueForSite( + Dst, K, S, Mapper); +} + +ValueProfData *allocValueProfDataInstrProf(size_t TotalSizeInBytes) { + ValueProfData *VD = + (ValueProfData *)(new (::operator new(TotalSizeInBytes)) ValueProfData()); + memset(VD, 0, TotalSizeInBytes); + return VD; +} + +static ValueProfRecordClosure InstrProfRecordClosure = { + 0, + getNumValueKindsInstrProf, + getNumValueSitesInstrProf, + getNumValueDataInstrProf, + getNumValueDataForSiteInstrProf, + 0, + getValueForSiteInstrProf, + allocValueProfDataInstrProf}; + +// Wrapper implementation using the closure mechanism. +uint32_t ValueProfData::getSize(const InstrProfRecord &Record) { + InstrProfRecordClosure.Record = &Record; + return getValueProfDataSize(&InstrProfRecordClosure); +} + +// Wrapper implementation using the closure mechanism. +std::unique_ptr +ValueProfData::serializeFrom(const InstrProfRecord &Record) { + InstrProfRecordClosure.Record = &Record; + + std::unique_ptr VPD( + serializeValueProfDataFrom(&InstrProfRecordClosure, nullptr)); + return VPD; +} + +void ValueProfRecord::deserializeTo(InstrProfRecord &Record, + InstrProfRecord::ValueMapType *VMap) { + Record.reserveSites(Kind, NumValueSites); + + InstrProfValueData *ValueData = getValueProfRecordValueData(this); + for (uint64_t VSite = 0; VSite < NumValueSites; ++VSite) { + uint8_t ValueDataCount = this->SiteCountArray[VSite]; + Record.addValueData(Kind, VSite, ValueData, ValueDataCount, VMap); + ValueData += ValueDataCount; + } } // For writing/serializing, Old is the host endianness, and New is @@ -206,8 +486,8 @@ void ValueProfRecord::swapBytes(support::endianness Old, sys::swapByteOrder(NumValueSites); sys::swapByteOrder(Kind); } - uint32_t ND = getNumValueData(); - InstrProfValueData *VD = getValueData(); + uint32_t ND = getValueProfRecordNumValueData(this); + InstrProfValueData *VD = getValueProfRecordValueData(this); // No need to swap byte array: SiteCountArrray. for (uint32_t I = 0; I < ND; I++) { @@ -220,56 +500,48 @@ void ValueProfRecord::swapBytes(support::endianness Old, } } -uint32_t ValueProfData::getSize(const InstrProfRecord &Record) { - uint32_t TotalSize = sizeof(ValueProfData); - uint32_t NumValueKinds = Record.getNumValueKinds(); - if (NumValueKinds == 0) - return TotalSize; - - for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; Kind++) { - uint32_t NumValueSites = Record.getNumValueSites(Kind); - if (!NumValueSites) - continue; - TotalSize += - ValueProfRecord::getSize(NumValueSites, Record.getNumValueData(Kind)); - } - return TotalSize; -} - void ValueProfData::deserializeTo(InstrProfRecord &Record, InstrProfRecord::ValueMapType *VMap) { if (NumValueKinds == 0) return; - ValueProfRecord *VR = getFirstValueProfRecord(); + ValueProfRecord *VR = getFirstValueProfRecord(this); for (uint32_t K = 0; K < NumValueKinds; K++) { VR->deserializeTo(Record, VMap); - VR = VR->getNext(); + VR = getValueProfRecordNext(VR); } } -static std::unique_ptr AllocValueProfData(uint32_t TotalSize) { +template +static T swapToHostOrder(const unsigned char *&D, support::endianness Orig) { + using namespace support; + if (Orig == little) + return endian::readNext(D); + else + return endian::readNext(D); +} + +static std::unique_ptr allocValueProfData(uint32_t TotalSize) { return std::unique_ptr(new (::operator new(TotalSize)) ValueProfData()); } -std::unique_ptr -ValueProfData::serializeFrom(const InstrProfRecord &Record) { - uint32_t TotalSize = getSize(Record); - - std::unique_ptr VPD = AllocValueProfData(TotalSize); +instrprof_error ValueProfData::checkIntegrity() { + if (NumValueKinds > IPVK_Last + 1) + return instrprof_error::malformed; + // Total size needs to be mulltiple of quadword size. + if (TotalSize % sizeof(uint64_t)) + return instrprof_error::malformed; - VPD->TotalSize = TotalSize; - VPD->NumValueKinds = Record.getNumValueKinds(); - ValueProfRecord *VR = VPD->getFirstValueProfRecord(); - for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; Kind++) { - uint32_t NumValueSites = Record.getNumValueSites(Kind); - if (!NumValueSites) - continue; - VR->serializeFrom(Record, Kind, NumValueSites); - VR = VR->getNext(); + ValueProfRecord *VR = getFirstValueProfRecord(this); + for (uint32_t K = 0; K < this->NumValueKinds; K++) { + if (VR->Kind > IPVK_Last) + return instrprof_error::malformed; + VR = getValueProfRecordNext(VR); + if ((char *)VR - (char *)this > (ptrdiff_t)TotalSize) + return instrprof_error::malformed; } - return VPD; + return instrprof_error::success; } ErrorOr> @@ -282,31 +554,17 @@ ValueProfData::getValueProfData(const unsigned char *D, const unsigned char *Header = D; uint32_t TotalSize = swapToHostOrder(Header, Endianness); - uint32_t NumValueKinds = swapToHostOrder(Header, Endianness); - if (D + TotalSize > BufferEnd) return instrprof_error::too_large; - if (NumValueKinds > IPVK_Last + 1) - return instrprof_error::malformed; - // Total size needs to be mulltiple of quadword size. - if (TotalSize % sizeof(uint64_t)) - return instrprof_error::malformed; - - std::unique_ptr VPD = AllocValueProfData(TotalSize); + std::unique_ptr VPD = allocValueProfData(TotalSize); memcpy(VPD.get(), D, TotalSize); // Byte swap. VPD->swapBytesToHost(Endianness); - // Data integrety check: - ValueProfRecord *VR = VPD->getFirstValueProfRecord(); - for (uint32_t K = 0; K < VPD->NumValueKinds; K++) { - if (VR->Kind > IPVK_Last) - return instrprof_error::malformed; - VR = VR->getNext(); - if ((char *)VR - (char *)VPD.get() > (ptrdiff_t)TotalSize) - return instrprof_error::malformed; - } + instrprof_error EC = VPD->checkIntegrity(); + if (EC != instrprof_error::success) + return EC; return std::move(VPD); } @@ -319,10 +577,10 @@ void ValueProfData::swapBytesToHost(support::endianness Endianness) { sys::swapByteOrder(TotalSize); sys::swapByteOrder(NumValueKinds); - ValueProfRecord *VR = getFirstValueProfRecord(); + ValueProfRecord *VR = getFirstValueProfRecord(this); for (uint32_t K = 0; K < NumValueKinds; K++) { VR->swapBytes(Endianness, getHostEndianness()); - VR = VR->getNext(); + VR = getValueProfRecordNext(VR); } } @@ -331,9 +589,9 @@ void ValueProfData::swapBytesFromHost(support::endianness Endianness) { if (Endianness == getHostEndianness()) return; - ValueProfRecord *VR = getFirstValueProfRecord(); + ValueProfRecord *VR = getFirstValueProfRecord(this); for (uint32_t K = 0; K < NumValueKinds; K++) { - ValueProfRecord *NVR = VR->getNext(); + ValueProfRecord *NVR = getValueProfRecordNext(VR); VR->swapBytes(getHostEndianness(), Endianness); VR = NVR; } @@ -341,26 +599,4 @@ void ValueProfData::swapBytesFromHost(support::endianness Endianness) { sys::swapByteOrder(NumValueKinds); } -ValueProfRecord *ValueProfData::getFirstValueProfRecord() { - return reinterpret_cast((char *)this + - sizeof(ValueProfData)); -} - -uint32_t ValueProfRecord::getNumValueData() const { - uint32_t NumValueData = 0; - for (uint32_t I = 0; I < NumValueSites; I++) - NumValueData += SiteCountArray[I]; - return NumValueData; -} - -ValueProfRecord *ValueProfRecord::getNext() { - return reinterpret_cast((char *)this + getSize()); -} - -InstrProfValueData *ValueProfRecord::getValueData() { - return reinterpret_cast((char *)this + - getHeaderSize(NumValueSites)); -} - -} // End of IndexedInstrProf namespace. }