X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FProfileData%2FInstrProf.cpp;h=94c701de093c0031ad1832e3f1968d3f2c7af424;hb=0bd34e693f223908930aa924e28e4cf23ba46c24;hp=8a3a61ff67935429d66d6b411580d6da2d78d416;hpb=f722f529e7f3147ee286fb1d0baa2bb4e2313967;p=oota-llvm.git diff --git a/lib/ProfileData/InstrProf.cpp b/lib/ProfileData/InstrProf.cpp index 8a3a61ff679..94c701de093 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,253 @@ GlobalVariable *createPGOFuncNameVar(Function &F, StringRef FuncName) { return createPGOFuncNameVar(*F.getParent(), F.getLinkage(), FuncName); } -/// Return the total size in bytes of the on-disk value profile data -/// given the data stored in Record. -uint32_t getValueProfDataSize(ValueProfRecordClosure *Closure) { - uint32_t Kind; - uint32_t TotalSize = sizeof(ValueProfData); - const void *Record = Closure->Record; - uint32_t NumValueKinds = Closure->GetNumValueKinds(Record); - if (NumValueKinds == 0) - return TotalSize; +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())); +} - for (Kind = IPVK_First; Kind <= IPVK_Last; Kind++) { - uint32_t NumValueSites = Closure->GetNumValueSites(Record, Kind); - if (!NumValueSites) +StringRef getPGOFuncNameInitializer(GlobalVariable *NameVar) { + auto *Arr = cast(NameVar->getInitializer()); + StringRef NameStr = + Arr->isCString() ? Arr->getAsCString() : Arr->getAsString(); + return NameStr; +} + +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); +} + +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; +} + +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) { + uint64_t JCount = J->Count; + bool Overflowed; + if (Weight > 1) { + JCount = SaturatingMultiply(JCount, Weight, &Overflowed); + if (Overflowed) + Result = instrprof_error::counter_overflow; + } + I->Count = SaturatingAdd(I->Count, JCount, &Overflowed); + if (Overflowed) + Result = instrprof_error::counter_overflow; + ++I; continue; - TotalSize += getValueProfRecordSize(NumValueSites, - Closure->GetNumValueData(Record, Kind)); + } + ValueData.insert(I, *J); } - return TotalSize; -} - -// Extract data from \c Closure and serialize into \c This instance. -void serializeValueProfRecordFrom(ValueProfRecord *This, - ValueProfRecordClosure *Closure, - uint32_t ValueKind, uint32_t NumValueSites) { - uint32_t S; - const void *Record = Closure->Record; - This->Kind = ValueKind; - This->NumValueSites = NumValueSites; - InstrProfValueData *DstVD = getValueProfRecordValueData(This); - - for (S = 0; S < NumValueSites; S++) { - uint32_t ND = Closure->GetNumValueDataForSite(Record, ValueKind, S); - This->SiteCountArray[S] = ND; - Closure->GetValueForSite(Record, DstVD, ValueKind, S, - Closure->RemapValueData); - DstVD += ND; + 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; } -ValueProfData *serializeValueProfDataFrom(ValueProfRecordClosure *Closure) { - uint32_t TotalSize = getValueProfDataSize(Closure); +// 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; +} - ValueProfData *VPD = Closure->AllocValueProfData(TotalSize); +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; + uint64_t OtherCount = Other.Counts[I]; + if (Weight > 1) { + OtherCount = SaturatingMultiply(OtherCount, Weight, &Overflowed); + if (Overflowed) + Result = instrprof_error::counter_overflow; + } + Counts[I] = SaturatingAdd(Counts[I], OtherCount, &Overflowed); + if (Overflowed) + Result = instrprof_error::counter_overflow; + } - VPD->TotalSize = TotalSize; - VPD->NumValueKinds = Closure->GetNumValueKinds(Closure->Record); - ValueProfRecord *VR = getFirstValueProfRecord(VPD); - for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; Kind++) { - uint32_t NumValueSites = Closure->GetNumValueSites(Closure->Record, Kind); - if (!NumValueSites) - continue; - serializeValueProfRecordFrom(VR, Closure, Kind, NumValueSites); - VR = getValueProfRecordNext(VR); + 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; +} + +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; + } } - return VPD; + for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind) + MergeResult(Result, scaleValueProfData(Kind, Weight)); + + return Result; +} + +// 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 + ValueSites.emplace_back(VData, VData + N); } -// C wrappers of InstrProfRecord member functions used in Closure. -// These C wrappers are used as adaptors so that C++ code can be -// invoked as callbacks. +#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(); } @@ -214,25 +435,15 @@ uint32_t getNumValueDataForSiteInstrProf(const void *R, uint32_t VK, 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); -} - -uint64_t stringToHash(uint32_t ValueKind, uint64_t Value) { - switch (ValueKind) { - case IPVK_IndirectCallTarget: - return IndexedInstrProf::ComputeHash(IndexedInstrProf::HashType, - (const char *)Value); - break; - default: - llvm_unreachable("value kind not handled !"); - } - return Value; + return reinterpret_cast(R)->getValueForSite( + Dst, K, S, Mapper); } ValueProfData *allocValueProfDataInstrProf(size_t TotalSizeInBytes) { - return (ValueProfData *)(new (::operator new(TotalSizeInBytes)) - ValueProfData()); + ValueProfData *VD = + (ValueProfData *)(new (::operator new(TotalSizeInBytes)) ValueProfData()); + memset(VD, 0, TotalSizeInBytes); + return VD; } static ValueProfRecordClosure InstrProfRecordClosure = { @@ -241,10 +452,9 @@ static ValueProfRecordClosure InstrProfRecordClosure = { getNumValueSitesInstrProf, getNumValueDataInstrProf, getNumValueDataForSiteInstrProf, - stringToHash, + 0, getValueForSiteInstrProf, - allocValueProfDataInstrProf -}; + allocValueProfDataInstrProf}; // Wrapper implementation using the closure mechanism. uint32_t ValueProfData::getSize(const InstrProfRecord &Record) { @@ -258,7 +468,7 @@ ValueProfData::serializeFrom(const InstrProfRecord &Record) { InstrProfRecordClosure.Record = &Record; std::unique_ptr VPD( - serializeValueProfDataFrom(&InstrProfRecordClosure)); + serializeValueProfDataFrom(&InstrProfRecordClosure, nullptr)); return VPD; } @@ -273,6 +483,7 @@ void ValueProfRecord::deserializeTo(InstrProfRecord &Record, ValueData += ValueDataCount; } } + // For writing/serializing, Old is the host endianness, and New is // byte order intended on disk. For Reading/deserialization, Old // is the on-disk source endianness, and New is the host endianness. @@ -326,6 +537,24 @@ static std::unique_ptr allocValueProfData(uint32_t TotalSize) { ValueProfData()); } +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; + + 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 instrprof_error::success; +} + ErrorOr> ValueProfData::getValueProfData(const unsigned char *D, const unsigned char *const BufferEnd, @@ -336,31 +565,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); - memcpy(VPD.get(), D, TotalSize); // Byte swap. VPD->swapBytesToHost(Endianness); - // Data integrity check: - ValueProfRecord *VR = getFirstValueProfRecord(VPD.get()); - for (uint32_t K = 0; K < VPD->NumValueKinds; K++) { - if (VR->Kind > IPVK_Last) - return instrprof_error::malformed; - VR = getValueProfRecordNext(VR); - 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); }