[InstrProf] Support for external functions in text format.

[mtrofin]

Summary

External functions appearing as indirect call targets could not be
found in the SymTab, and the value:counter record was represented,
in the text format, using an empty string for the name. This would
then cause a silent parsing error when reading.

This CL:

• adds explicit support for such functions
• fixes the places where we would not propagate errors when reading
• addresses a performance issue due to eager resorting of the SymTab.

[davidxl]

include/llvm/ProfileData/InstrProf.h

430

Why do we need to do this? Is it better to return an empty string and skip the entry when it is empty?

479

Sorted = false should be executed only when insertion succeeds.

[mtrofin]

Skip dirty-ing the SymTab on unsuccessful name insertions.

[mtrofin]

include/llvm/ProfileData/InstrProf.h

430

Just to distinguish it from an erroneous input.

[davidxl]

lib/ProfileData/InstrProfWriter.cpp

361

What I suggested is that instead of emitting a fake target with a name that may collide with a real function, just skip the target (or better emit some comments here). Of course, the value of ND needs to be precomputed/adjusted first.

[mtrofin]

lib/ProfileData/InstrProfWriter.cpp

361

Wouldn't we lose a counter value in that case? (which would shift thresholds, for example)

I share the concern of potential (albeit low probability) name collision. How about building a name using invalid characters, such as space - since the reader matches on ':' (so the external symbol name could be "External Symbol")

[davidxl]

lib/ProfileData/InstrProfWriter.cpp

361

Ok. Also avoid using __llvm which is a reserved namespace for profiling library symbols.

[mtrofin]

Changed symbol name

[davidxl]

lgtm

include/llvm/ProfileData/InstrProf.h

private:
   // A map from MD5 keys to function name strings.
   std::vector<std::pair<uint64_t, StringRef>> MD5NameMap;
   // A map from MD5 keys to function define. We only populate this map
   // when build the Symtab from a Module.
   std::vector<std::pair<uint64_t, Function *>> MD5FuncMap;
   // A map from function runtime address to function name MD5 hash.
   // This map is only populated and used by raw instr profile reader.
   AddrHashMap AddrToMD5Map;
+  bool Sorted = false;
+
+  static StringRef getExternalSymbol() {
+    return "__llvm_prof_external_symbol__";
+  }
+
+  // If the symtab is created by a series of calls to \c addFuncName, \c
+  // finalizeSymtab needs to be called before looking up function names.
+  // This is required because the underlying map is a vector (for space
+  // efficiency) which needs to be sorted.
+  inline void finalizeSymtab();
 
 public:
-  InstrProfSymtab() = default; 
+  InstrProfSymtab() = default;
 
   /// Create InstrProfSymtab from an object file section which
   /// contains function PGO names. When section may contain raw
   /// string data or string data in compressed form. This method
   /// only initialize the symtab with reference to the data and
   /// the section base address. The decompression will be delayed
   /// until before it is used. See also \c create(StringRef) method.
   Error create(object::SectionRef &Section);
public:
   /// passes such as indirect function call promotion. Variable \c InLTO
   /// indicates if this is called from LTO optimization passes.
   Error create(Module &M, bool InLTO = false);
 
   /// Create InstrProfSymtab from a set of names iteratable from
   /// \p IterRange. This interface is used by IndexedProfReader.
   template <typename NameIterRange> Error create(const NameIterRange &IterRange);
 
-  // If the symtab is created by a series of calls to \c addFuncName, \c
-  // finalizeSymtab needs to be called before looking up function names.
-  // This is required because the underlying map is a vector (for space
-  // efficiency) which needs to be sorted.
-  inline void finalizeSymtab();
-
   /// Update the symtab by adding \p FuncName to the table. This interface
   /// is used by the raw and text profile readers.
   Error addFuncName(StringRef FuncName) {
     if (FuncName.empty())
       return make_error<InstrProfError>(instrprof_error::malformed);
     auto Ins = NameTab.insert(FuncName);
     if (Ins.second)
       MD5NameMap.push_back(std::make_pair(
           IndexedInstrProf::ComputeHash(FuncName), Ins.first->getKey()));
+    Sorted = false;
     return Error::success();
   }
 
   /// Map a function address to its name's MD5 hash. This interface
   /// is only used by the raw profiler reader.
   void mapAddress(uint64_t Addr, uint64_t MD5Val) {
     AddrToMD5Map.push_back(std::make_pair(Addr, MD5Val));
   }
 
   AddrHashMap &getAddrHashMap() { return AddrToMD5Map; }
 
   /// Return function's PGO name from the function name's symbol
   /// address in the object file. If an error occurs, return
   /// an empty string.
   StringRef getFuncName(uint64_t FuncNameAddress, size_t NameSize);
 
   /// Return function's PGO name from the name's md5 hash value.
   /// If not found, return an empty string.
   inline StringRef getFuncName(uint64_t FuncMD5Hash);
 
+  /// Just like getFuncName, except that it will return a non-empty StringRef
+  /// if the function is external to this symbol table. All such cases
+  /// will be represented using the same StringRef value.
+  inline StringRef getFuncNameOrExternalSymbol(uint64_t FuncMD5Hash);
+
+  /// True if Symbol is the value used to represent external symbols.
+  static bool isExternalSymbol(const StringRef &Symbol) {
+    return Symbol == InstrProfSymtab::getExternalSymbol();
+  }
+
   /// Return function from the name's md5 hash. Return nullptr if not found.
   inline Function *getFunction(uint64_t FuncMD5Hash);
 
   /// Return the function's original assembly name by stripping off
   /// the prefix attached (to symbols with priviate linkage). For
   /// global functions, it returns the same string as getFuncName.
   inline StringRef getOrigFuncName(uint64_t FuncMD5Hash);
 
for (auto Name : IterRange)
     if (Error E = addFuncName(Name))
       return E;
 
   finalizeSymtab();
   return Error::success();
 }
 
 void InstrProfSymtab::finalizeSymtab() {
+  if (Sorted)
+    return;
   std::sort(MD5NameMap.begin(), MD5NameMap.end(), less_first());
   std::sort(MD5FuncMap.begin(), MD5FuncMap.end(), less_first());
   std::sort(AddrToMD5Map.begin(), AddrToMD5Map.end(), less_first());
   AddrToMD5Map.erase(std::unique(AddrToMD5Map.begin(), AddrToMD5Map.end()),
                      AddrToMD5Map.end());
+  Sorted = true;
+}
+
+StringRef InstrProfSymtab::getFuncNameOrExternalSymbol(uint64_t FuncMD5Hash) {
+  StringRef ret = getFuncName(FuncMD5Hash);
+  if (ret.empty())
+    return InstrProfSymtab::getExternalSymbol();
+  return ret;
 }
 
 StringRef InstrProfSymtab::getFuncName(uint64_t FuncMD5Hash) {
+  finalizeSymtab();
   auto Result =
       std::lower_bound(MD5NameMap.begin(), MD5NameMap.end(), FuncMD5Hash,
                        [](const std::pair<uint64_t, std::string> &LHS,
                           uint64_t RHS) { return LHS.first < RHS; });
   if (Result != MD5NameMap.end() && Result->first == FuncMD5Hash)
     return Result->second;
   return StringRef();
 }
 
 Function* InstrProfSymtab::getFunction(uint64_t FuncMD5Hash) {
+  finalizeSymtab();
   auto Result =
       std::lower_bound(MD5FuncMap.begin(), MD5FuncMap.end(), FuncMD5Hash,
                        [](const std::pair<uint64_t, Function*> &LHS,
                           uint64_t RHS) { return LHS.first < RHS; });
   if (Result != MD5FuncMap.end() && Result->first == FuncMD5Hash)
     return Result->second;
   return nullptr;
 }

include/llvm/ProfileData/InstrProfReader.h

protected:
   /// Set the current error and return same.
   Error error(instrprof_error Err) {
     LastError = Err;
     if (Err == instrprof_error::success)
       return Error::success();
     return make_error<InstrProfError>(Err);
   }
 
-  Error error(Error E) { return error(InstrProfError::take(std::move(E))); }
+  Error error(Error &&E) { return error(InstrProfError::take(std::move(E))); }
 
   /// Clear the current error and return a successful one.
   Error success() { return error(instrprof_error::success); }
 
 public:
   /// Return true if the reader has finished reading the profile data.
   bool isEOF() { return LastError == instrprof_error::eof; }
 

lib/ProfileData/InstrProf.cpp

if (InLTO) {
       if (pos != std::string::npos) {
         const std::string &OtherFuncName = PGOFuncName.substr(0, pos);
         if (Error E = addFuncName(OtherFuncName))
           return E;
         MD5FuncMap.emplace_back(Function::getGUID(OtherFuncName), &F);
       }
     }
   }
-
+  Sorted = false;
   finalizeSymtab();
   return Error::success();
 }
 
 Error collectPGOFuncNameStrings(ArrayRef<std::string> NameStrs,
                                 bool doCompression, std::string &Result) {
   assert(!NameStrs.empty() && "No name data to emit");
 
while (P < EndP) {
     NameStrings.split(Names, getInstrProfNameSeparator());
     for (StringRef &Name : Names)
       if (Error E = Symtab.addFuncName(Name))
         return E;
 
     while (P < EndP && *P == 0)
       P++;
   }
-  Symtab.finalizeSymtab();
   return Error::success();
 }
 
 void InstrProfValueSiteRecord::merge(InstrProfValueSiteRecord &Input,
                                      uint64_t Weight,
                                      function_ref<void(instrprof_error)> Warn) {
   this->sortByTargetValues();
   Input.sortByTargetValues();

lib/ProfileData/InstrProfReader.cpp

for (uint32_t S = 0; S < NumValueSites; S++) {
       VP_READ_ADVANCE(NumValueData);
 
       std::vector<InstrProfValueData> CurrentValues;
       for (uint32_t V = 0; V < NumValueData; V++) {
         CHECK_LINE_END(Line);
         std::pair<StringRef, StringRef> VD = Line->rsplit(':');
         uint64_t TakenCount, Value;
         if (ValueKind == IPVK_IndirectCallTarget) {
+          if (InstrProfSymtab::isExternalSymbol(VD.first)) {
+            Value = 0;
+          } else {
             if (Error E = Symtab->addFuncName(VD.first))
               return E;
             Value = IndexedInstrProf::ComputeHash(VD.first);
+          }
         } else {
           READ_NUM(VD.first, Value);
         }
         READ_NUM(VD.second, TakenCount);
         CurrentValues.push_back({Value, TakenCount});
         Line++;
       }
       Record.addValueData(ValueKind, S, CurrentValues.data(), NumValueData,
                           nullptr);
     }
   }
   return success();
 
 #undef CHECK_LINE_END
 #undef READ_NUM
 #undef VP_READ_ADVANCE
 }
 
 Error TextInstrProfReader::readNextRecord(NamedInstrProfRecord &Record) {
   // Skip empty lines and comments.
   while (!Line.is_at_end() && (Line->empty() || Line->startswith("#")))
     ++Line;
   // If we hit EOF while looking for a name, we're done.
   if (Line.is_at_end()) {
-    Symtab->finalizeSymtab();
     return error(instrprof_error::eof);
   }
 
   // Read the function name.
   Record.Name = *Line++;
   if (Error E = Symtab->addFuncName(Record.Name))
-    return E;
+    return error(std::move(E));
 
   // Read the function hash.
   if (Line.is_at_end())
     return error(instrprof_error::truncated);
   if ((Line++)->getAsInteger(0, Record.Hash))
     return error(instrprof_error::malformed);
 
   // Read the number of counters.
for (uint64_t I = 0; I < NumCounters; ++I) {
     uint64_t Count;
     if ((Line++)->getAsInteger(10, Count))
       return error(instrprof_error::malformed);
     Record.Counts.push_back(Count);
   }
 
   // Check if value profile data exists and read it if so.
   if (Error E = readValueProfileData(Record))
-    return E;
+    return error(std::move(E));
 
-  // This is needed to avoid two pass parsing because llvm-profdata
-  // does dumping while reading.
-  Symtab->finalizeSymtab();
   return success();
 }
 
 template <class IntPtrT>
 bool RawInstrProfReader<IntPtrT>::hasFormat(const MemoryBuffer &DataBuffer) {
   if (DataBuffer.getBufferSize() < sizeof(uint64_t))
     return false;
   uint64_t Magic =
Error RawInstrProfReader<IntPtrT>::createSymtab(InstrProfSymtab &Symtab) {
   if (Error E = Symtab.create(StringRef(NamesStart, NamesSize)))
     return error(std::move(E));
   for (const RawInstrProf::ProfileData<IntPtrT> *I = Data; I != DataEnd; ++I) {
     const IntPtrT FPtr = swap(I->FunctionPointer);
     if (!FPtr)
       continue;
     Symtab.mapAddress(FPtr, I->NameRef);
   }
-  Symtab.finalizeSymtab();
   return success();
 }
 
 template <class IntPtrT>
 Error RawInstrProfReader<IntPtrT>::readHeader(
     const RawInstrProf::Header &Header) {
   Version = swap(Header.Version);
   if (GET_VERSION(Version) != RawInstrProf::Version)
Error RawInstrProfReader<IntPtrT>::readValueProfilingData(
   return success();
 }
 
 template <class IntPtrT>
 Error RawInstrProfReader<IntPtrT>::readNextRecord(NamedInstrProfRecord &Record) {
   if (atEnd())
     // At this point, ValueDataStart field points to the next header.
     if (Error E = readNextHeader(getNextHeaderPos()))
-      return E;
+      return error(std::move(E));
 
   // Read name ad set it in Record.
   if (Error E = readName(Record))
-    return E;
+    return error(std::move(E));
 
   // Read FuncHash and set it in Record.
   if (Error E = readFuncHash(Record))
-    return E;
+    return error(std::move(E));
 
   // Read raw counts and set Record.
   if (Error E = readRawCounts(Record))
-    return E;
+    return error(std::move(E));
 
   // Read value data and set Record.
   if (Error E = readValueProfilingData(Record))
-    return E;
+    return error(std::move(E));
 
   // Iterate.
   advanceData();
   return success();
 }
 
 namespace llvm {
 

lib/ProfileData/InstrProfWriter.cpp

for (uint32_t VK = 0; VK < IPVK_Last + 1; VK++) {
     uint32_t NS = Func.getNumValueSites(VK);
     if (!NS)
       continue;
     OS << "# ValueKind = " << ValueProfKindStr[VK] << ":\n" << VK << "\n";
     OS << "# NumValueSites:\n" << NS << "\n";
     for (uint32_t S = 0; S < NS; S++) {
       uint32_t ND = Func.getNumValueDataForSite(VK, S);
       OS << ND << "\n";
       std::unique_ptr<InstrProfValueData[]> VD = Func.getValueForSite(VK, S);
       for (uint32_t I = 0; I < ND; I++) {
         if (VK == IPVK_IndirectCallTarget)
-          OS << Symtab.getFuncName(VD[I].Value) << ":" << VD[I].Count << "\n";
+          OS << Symtab.getFuncNameOrExternalSymbol(VD[I].Value) << ":"
+             << VD[I].Count << "\n";
         else
           OS << VD[I].Value << ":" << VD[I].Count << "\n";
       }
     }
   }
 
   OS << "\n";
 }
 
 Error InstrProfWriter::writeText(raw_fd_ostream &OS) {
   if (ProfileKind == PF_IRLevel)
     OS << "# IR level Instrumentation Flag\n:ir\n";
   InstrProfSymtab Symtab;
   for (const auto &I : FunctionData)
     if (shouldEncodeData(I.getValue()))
       if (Error E = Symtab.addFuncName(I.getKey()))
         return E;
-  Symtab.finalizeSymtab();
 
   for (const auto &I : FunctionData)
     if (shouldEncodeData(I.getValue()))
       for (const auto &Func : I.getValue())
         writeRecordInText(I.getKey(), Func.first, Func.second, Symtab, OS);
   return Error::success();
 }

test/tools/llvm-profdata/invalid-profdata.test

+RUN: echo ":ir"                     > %t.input
+RUN: echo "_ZN6Thread5StartEv"      >> %t.input
+RUN: echo "# Func Hash:"            >> %t.input
+RUN: echo "288793635542036872"      >> %t.input
+RUN: echo "# Num Counters:"         >> %t.input
+RUN: echo "3"                       >> %t.input
+RUN: echo "# Counter Values:"       >> %t.input
+RUN: echo "0"                       >> %t.input
+RUN: echo "12"                      >> %t.input
+RUN: echo "12"                      >> %t.input
+RUN: echo "# Num Value Kinds:"      >> %t.input
+RUN: echo "1"                       >> %t.input
+RUN: echo "# ValueKind = IPVK_IndirectCallTarget:"       >> %t.input
+RUN: echo "0"                                            >> %t.input
+RUN: echo "# NumValueSites:"                             >> %t.input
+RUN: echo "2"                                            >> %t.input
+RUN: echo "2"                                            >> %t.input
+RUN: echo "f1:10"                                        >> %t.input
+RUN: echo "f2:0"                                         >> %t.input
+RUN: echo "1"                                            >> %t.input
+RUN: echo ":10"                                          >> %t.input
+
+RUN: not llvm-profdata merge %t.input -text -output=/dev/null 2>&1  | FileCheck %s --check-prefix=BROKEN
+BROKEN: Malformed instrumentation profile data
+
+RUN: echo ":ir"                     > %t.input
+RUN: echo "_ZN6Thread5StartEv"      >> %t.input
+RUN: echo "# Func Hash:"            >> %t.input
+RUN: echo "288793635542036872"      >> %t.input
+RUN: echo "# Num Counters:"         >> %t.input
+RUN: echo "3"                       >> %t.input
+RUN: echo "# Counter Values:"       >> %t.input
+RUN: echo "0"                       >> %t.input
+RUN: echo "12"                      >> %t.input
+RUN: echo "12"                      >> %t.input
+RUN: echo "# Num Value Kinds:"      >> %t.input
+RUN: echo "1"                       >> %t.input
+RUN: echo "# ValueKind = IPVK_IndirectCallTarget:"       >> %t.input
+RUN: echo "0"                                            >> %t.input
+RUN: echo "# NumValueSites:"                             >> %t.input
+RUN: echo "2"                                            >> %t.input
+RUN: echo "2"                                            >> %t.input
+RUN: echo "f1:10"                                        >> %t.input
+RUN: echo "f2:0"                                         >> %t.input
+RUN: echo "1"                                            >> %t.input
+RUN: echo "__llvm_prof_external_symbol__:10"             >> %t.input
+
+# RUN: llvm-profdata merge %t.input -text -output=%t.out && cat %t.out | FileCheck %s
+
+CHECK: __llvm_prof_external_symbol__:10
 No newline at end of file

unittests/ProfileData/InstrProfTest.cpp

TEST_P(MaybeSparseInstrProfTest, value_prof_data_read_write_mapping) {
 
   NamedInstrProfRecord Record("caller", 0x1234, {1ULL << 31, 2});
   InstrProfSymtab Symtab;
   Symtab.mapAddress(uint64_t(callee1), 0x1000ULL);
   Symtab.mapAddress(uint64_t(callee2), 0x2000ULL);
   Symtab.mapAddress(uint64_t(callee3), 0x3000ULL);
   Symtab.mapAddress(uint64_t(callee4), 0x4000ULL);
   // Missing mapping for callee5
-  Symtab.finalizeSymtab();
 
   VPData->deserializeTo(Record, &Symtab.getAddrHashMap());
 
   // Now read data from Record and sanity check the data
   ASSERT_EQ(5U, Record.getNumValueSites(IPVK_IndirectCallTarget));
   ASSERT_EQ(5U, Record.getNumValueDataForSite(IPVK_IndirectCallTarget, 0));
 
   auto Cmp = [](const InstrProfValueData &VD1, const InstrProfValueData &VD2) {
TEST_P(MaybeSparseInstrProfTest, instr_prof_symtab_test) {
   ASSERT_EQ(StringRef(), R);
   R = Symtab.getFuncName(IndexedInstrProf::ComputeHash("foo4"));
   ASSERT_EQ(StringRef(), R);
 
   // Now incrementally update the symtab
   EXPECT_THAT_ERROR(Symtab.addFuncName("blah_1"), Succeeded());
   EXPECT_THAT_ERROR(Symtab.addFuncName("blah_2"), Succeeded());
   EXPECT_THAT_ERROR(Symtab.addFuncName("blah_3"), Succeeded());
-  // Finalize it
-  Symtab.finalizeSymtab();
 
   // Check again
   R = Symtab.getFuncName(IndexedInstrProf::ComputeHash("blah_1"));
   ASSERT_EQ(StringRef("blah_1"), R);
   R = Symtab.getFuncName(IndexedInstrProf::ComputeHash("blah_2"));
   ASSERT_EQ(StringRef("blah_2"), R);
   R = Symtab.getFuncName(IndexedInstrProf::ComputeHash("blah_3"));
   ASSERT_EQ(StringRef("blah_3"), R);