Add second fast path for DiagnosticsEngine::GetDiagStatePointForLoc

[djasper]

Summary

In many translation units I have tested, many of the calls to DiagnosticsEngine::GetDiagStatePointForLoc are for source locations before the first diag state point. AFAICT, this happens frequently for locations in the STL and other base libraries. This patch adds a fast path for this case to avoid the costly binary search. This binary search is costly, because the relatively slow SourceManager::isBeforeInTranslationUnit() is used to compare DiagStatePoints.

[rsmith]

lib/Basic/Diagnostic.cpp

179

It's surprising to me that this would be particularly frequent.

I suspect what you're actually seeing is a consequence of a bug in how we manage DiagStatePoints with modules. It looks like ASTReader::InitializeContext is called once per top-level PCM file that we load, and its call to ReadPragmaDiagnosticMappings adds entries to the DiagStatePoints list regardless of whether they've already been added. So, we'll end up with duplicates in the DiagStatePoints list, and it won't even be in translation unit order.

Can you take a look at the DiagStatePoints list for a translation unit where you see a performance problem and check whether it seems reasonable?

[djasper]

lib/Basic/Diagnostic.cpp

179

I looked at the DiagStatePoints and they do look somewhat sane but suspicious.

The translation unit I am looking at has (AFAICT) only includes that get translated to modules. DiagStatePoints only has entries for the translation unit itself, not a single one coming from any of the modules. So DiagStatePoints looks like:

[0]: <<invalid>>  (for the command line)
[1]: myfile.cc:100
[2]: myfile.cc:100
...
[2500]: myfile.cc:2800

And because of that, the new fast path is hit every single time when a source location coming from a module is queried. There are always two entries for a line of myfile.cc which always seem to denote entering and exiting a macro.

So, specific questions:

• Should there by DiagStatePoints from modules?
• Should there really be a DiagStatePoint entry (or actually two) for every macro invocation in myfile.cc?

[rsmith]

lib/Basic/Diagnostic.cpp

179

Yes, there should be DiagStatePoints from modules, but support for that seems to basically be unimplemented at this point.

I believe the DiagStatePoints for macros are coming from a _Pragma("clang diagnostic ...") within the macro expansion. Doesn't look like there's any other way we'd create them.

[djasper]

lib/Basic/Diagnostic.cpp

179

Ah yes, you are right. I can probably fix that and I presume then this patch won't help as much anymore.

lib/Basic/Diagnostic.cpp

 }
 
 DiagnosticsEngine::DiagStatePointsTy::iterator
 DiagnosticsEngine::GetDiagStatePointForLoc(SourceLocation L) const {
   assert(!DiagStatePoints.empty());
   assert(DiagStatePoints.front().Loc.isInvalid() &&
          "Should have created a DiagStatePoint for command-line");
 
-  if (!SourceMgr)
+  if (!SourceMgr || DiagStatePoints.size() == 1)
     return DiagStatePoints.end() - 1;
 
   FullSourceLoc Loc(L, *SourceMgr);
   if (Loc.isInvalid())
     return DiagStatePoints.end() - 1;
 
-  DiagStatePointsTy::iterator Pos = DiagStatePoints.end();
+  // Most frequent case: L is after the last diag state change.
   FullSourceLoc LastStateChangePos = DiagStatePoints.back().Loc;
-  if (LastStateChangePos.isValid() &&
-      Loc.isBeforeInTranslationUnitThan(LastStateChangePos))
-    Pos = std::upper_bound(DiagStatePoints.begin(), DiagStatePoints.end(),
-                           DiagStatePoint(nullptr, Loc));
-  --Pos;
-  return Pos;
+  assert(LastStateChangePos.isValid());
+  if (!Loc.isBeforeInTranslationUnitThan(LastStateChangePos))
+    return DiagStatePoints.end() - 1;
+
+  // 2nd most frequent case: L is before the first diag state change.
+  FullSourceLoc FirstStateChangePos = DiagStatePoints[1].Loc;
+  assert(FirstStateChangePos.isValid());
+  if (Loc.isBeforeInTranslationUnitThan(FirstStateChangePos))
+    return DiagStatePoints.begin();
+
+  // Fall back to binary search.
+  return std::upper_bound(DiagStatePoints.begin(), DiagStatePoints.end(),
+                          DiagStatePoint(nullptr, Loc)) - 1;
 }
 
 void DiagnosticsEngine::setSeverity(diag::kind Diag, diag::Severity Map,
                                     SourceLocation L) {
   assert(Diag < diag::DIAG_UPPER_LIMIT &&
          "Can only map builtin diagnostics");
   assert((Diags->isBuiltinWarningOrExtension(Diag) ||
           (Map == diag::Severity::Fatal || Map == diag::Severity::Error)) &&