[Coverage] Reduce complexity of adding function mapping records

[vsk]

Summary

Replace a string append operation in addFunctionMappingRecord with a
vector append. The existing behavior is quadratic in the worst case:
this patch makes it linear.

[davidxl]

LGTM

cfe/trunk/lib/CodeGen/CoverageMappingGen.h

 /// code coverage mapping data.
 class CoverageMappingModuleGen {
   CodeGenModule &CGM;
   CoverageSourceInfo &SourceInfo;
   llvm::SmallDenseMap<const FileEntry *, unsigned, 8> FileEntries;
   std::vector<llvm::Constant *> FunctionRecords;
   std::vector<llvm::Constant *> FunctionNames;
   llvm::StructType *FunctionRecordTy;
-  std::string CoverageMappings;
+  std::vector<std::string> CoverageMappings;
 
 public:
   CoverageMappingModuleGen(CodeGenModule &CGM, CoverageSourceInfo &SourceInfo)
       : CGM(CGM), SourceInfo(SourceInfo), FunctionRecordTy(nullptr) {}
 
   CoverageSourceInfo &getSourceInfo() const {
     return SourceInfo;
   }

cfe/trunk/lib/CodeGen/CoverageMappingGen.cpp

 // Instrumentation-based code coverage mapping generator
 //
 //===----------------------------------------------------------------------===//
 
 #include "CoverageMappingGen.h"
 #include "CodeGenFunction.h"
 #include "clang/AST/StmtVisitor.h"
 #include "clang/Lex/Lexer.h"
+#include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ProfileData/CoverageMapping.h"
 #include "llvm/ProfileData/CoverageMappingReader.h"
 #include "llvm/ProfileData/CoverageMappingWriter.h"
 #include "llvm/ProfileData/InstrProfReader.h"
 #include "llvm/Support/FileSystem.h"
 
 using namespace clang;
#define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) LLVMType,
   llvm::Constant *FunctionRecordVals[] = {
       #include "llvm/ProfileData/InstrProfData.inc"
   };
   FunctionRecords.push_back(llvm::ConstantStruct::get(
       FunctionRecordTy, makeArrayRef(FunctionRecordVals)));
   if (!IsUsed)
     FunctionNames.push_back(
         llvm::ConstantExpr::getBitCast(NamePtr, llvm::Type::getInt8PtrTy(Ctx)));
-  CoverageMappings += CoverageMapping;
+  CoverageMappings.push_back(CoverageMapping);
 
   if (CGM.getCodeGenOpts().DumpCoverageMapping) {
     // Dump the coverage mapping data for this function by decoding the
     // encoded data. This allows us to dump the mapping regions which were
     // also processed by the CoverageMappingWriter which performs
     // additional minimization operations such as reducing the number of
     // expressions.
     std::vector<StringRef> Filenames;
for (const auto &Entry : FileEntries) {
     auto I = Entry.second;
     FilenameStrs[I] = std::string(Path.begin(), Path.end());
     FilenameRefs[I] = FilenameStrs[I];
   }
 
   std::string FilenamesAndCoverageMappings;
   llvm::raw_string_ostream OS(FilenamesAndCoverageMappings);
   CoverageFilenamesSectionWriter(FilenameRefs).write(OS);
-  OS << CoverageMappings;
-  size_t CoverageMappingSize = CoverageMappings.size();
+  std::string RawCoverageMappings =
+      llvm::join(CoverageMappings.begin(), CoverageMappings.end(), "");
+  OS << RawCoverageMappings;
+  size_t CoverageMappingSize = RawCoverageMappings.size();
   size_t FilenamesSize = OS.str().size() - CoverageMappingSize;
   // Append extra zeroes if necessary to ensure that the size of the filenames
   // and coverage mappings is a multiple of 8.
   if (size_t Rem = OS.str().size() % 8) {
     CoverageMappingSize += 8 - Rem;
     for (size_t I = 0, S = 8 - Rem; I < S; ++I)
       OS << '\0';
   }