[Coverage][NFC] Remove skipped region after added into MappingRegions

[zequanwu]

Summary

There is no need to scan through all SkippedRegions when some of them are already added into MappingRegions.

[vsk]

Unfortunately it does look like the work done in gatherSkippedRegions is O(n^2) in the number of functions, at the moment. If the goal is to speed it up, it'd be good to grab some performance numbers for some representative compile unit (the sqlite3 amalgamation is my go-to for this sort of thing).

clang/lib/CodeGen/CoverageMappingGen.cpp

353

In the worst case, the work done in gatherSkippedRegions may still be n + (n-1) + ... ~ O(n^2) (I'm subtracting 1 each time the skipped regions for a function are erased).

356

It'd probably be good to split the lambda out into a separate/named helper.

[vsk]

(Depending on what the potential performance gains look like, it might be advisable to keep things simple with the current O(n^2) approach. Optimizing things can carry some risk -- not sure if we've already ruled this out, but e.g. perhaps there's some edge case with nested functions where we maybe don't want to erase skipped regions eagerly.)

[zequanwu]

clang/lib/CodeGen/CoverageMappingGen.cpp

353

Yeah, just notice that.

clang/lib/CodeGen/CoverageMappingGen.cpp

void gatherSkippedRegions() {
     for (const auto &R : MappingRegions) {
       FileLineRanges[R.FileID].first =
           std::min(FileLineRanges[R.FileID].first, R.LineStart);
       FileLineRanges[R.FileID].second =
           std::max(FileLineRanges[R.FileID].second, R.LineEnd);
     }
 
     auto SkippedRanges = CVM.getSourceInfo().getSkippedRanges();
-    for (auto &I : SkippedRanges) {
+    SkippedRanges.erase(
+        std::remove_if(
+            SkippedRanges.begin(), SkippedRanges.end(),
+            [&](SkippedRange I) {
               SourceRange Range = I.Range;
               auto LocStart = Range.getBegin();
               auto LocEnd = Range.getEnd();
               assert(SM.isWrittenInSameFile(LocStart, LocEnd) &&
                      "region spans multiple files");
 
               auto CovFileID = getCoverageFileID(LocStart);
               if (!CovFileID)
-        continue;
-      Optional<SpellingRegion> SR =
-          adjustSkippedRange(SM, LocStart, LocEnd, I.PrevTokLoc, I.NextTokLoc);
-      if (!SR.hasValue())
-        continue;
+                return false;
+              auto SR = adjustSkippedRange(SM, LocStart, LocEnd, I.PrevTokLoc,
+                                           I.NextTokLoc);
+              if (!SR)
+                return false;
               auto Region = CounterMappingRegion::makeSkipped(
                   *CovFileID, SR->LineStart, SR->ColumnStart, SR->LineEnd,
                   SR->ColumnEnd);
               // Make sure that we only collect the regions that are inside
               // the source code of this function.
               if (Region.LineStart >= FileLineRanges[*CovFileID].first &&
-          Region.LineEnd <= FileLineRanges[*CovFileID].second)
+                  Region.LineEnd <= FileLineRanges[*CovFileID].second) {
                 MappingRegions.push_back(Region);
+                return true;
               }
+              return false;
+            }),
+        SkippedRanges.end());
   }
 
   /// Generate the coverage counter mapping regions from collected
   /// source regions.
   void emitSourceRegions(const SourceRegionFilter &Filter) {
     for (const auto &Region : SourceRegions) {
       assert(Region.hasEndLoc() && "incomplete region");