diff --git a/clang/include/clang/Tooling/Syntax/Tokens.h b/clang/include/clang/Tooling/Syntax/Tokens.h
--- a/clang/include/clang/Tooling/Syntax/Tokens.h
+++ b/clang/include/clang/Tooling/Syntax/Tokens.h
@@ -34,6 +34,7 @@
 #include "clang/Basic/TokenKinds.h"
 #include "clang/Lex/Token.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Compiler.h"
@@ -366,6 +367,9 @@
   /// same stream as 'clang -E' (excluding the preprocessor directives like
   /// #file, etc.).
   std::vector<syntax::Token> ExpandedTokens;
+  // Index of ExpandedTokens for faster lookups by SourceLocation. This is
+  // useful while finding expanded tokens in a 'token range'.
+  llvm::DenseMap<SourceLocation, unsigned> ExpandedTokIndex;
   llvm::DenseMap<FileID, MarkedFile> Files;
   // The value is never null, pointer instead of reference to avoid disabling
   // implicit assignment operator.
diff --git a/clang/lib/Tooling/Syntax/Tokens.cpp b/clang/lib/Tooling/Syntax/Tokens.cpp
--- a/clang/lib/Tooling/Syntax/Tokens.cpp
+++ b/clang/lib/Tooling/Syntax/Tokens.cpp
@@ -184,6 +184,18 @@
 }
 
 llvm::ArrayRef<syntax::Token> TokenBuffer::expandedTokens(SourceRange R) const {
+  // Quick lookup if `R` is a token range.
+  // This is a huge win since majority of the users use ranges provided by an
+  // AST. Ranges in AST are token ranges from expanded token stream.
+  const auto Begin = ExpandedTokIndex.find(R.getBegin());
+  const auto End = ExpandedTokIndex.find(R.getEnd());
+  if (Begin != ExpandedTokIndex.end() && End != ExpandedTokIndex.end()) {
+    // Add 1 to End to make a half-open range.
+    return {ExpandedTokens.data() + Begin->getSecond(),
+            ExpandedTokens.data() + End->getSecond() + 1};
+  }
+  // Slow case. Use `isBeforeInTranslationUnit` to binary search for the
+  // required range.
   return getTokensCovering(expandedTokens(), R, *SourceMgr);
 }
 
@@ -638,6 +650,11 @@
     assert(!Result.ExpandedTokens.empty());
     assert(Result.ExpandedTokens.back().kind() == tok::eof);
 
+    // Index ExpandedTokens for faster lookups by SourceLocation.
+    unsigned ExpandedIndex = 0;
+    for (const Token &Tok : Result.ExpandedTokens)
+      Result.ExpandedTokIndex[Tok.location()] = ExpandedIndex++;
+
     // Tokenize every file that contributed tokens to the expanded stream.
     buildSpelledTokens();