Index: lib/Format/Format.cpp
===================================================================
--- lib/Format/Format.cpp
+++ lib/Format/Format.cpp
@@ -1442,6 +1442,10 @@
          llvm::Regex(IncludeRegexPattern).match(Replace.getReplacementText());
 }
 
+inline unsigned getOffset(const Environment &Env, SourceLocation Loc) {
+  return Env.getSourceManager().getDecomposedLoc(Loc).second;
+}
+
 // FIXME: do not insert headers into conditional #include blocks, e.g. #includes
 // surrounded by compile condition "#if...".
 // FIXME: do not insert existing headers.
@@ -1475,6 +1479,11 @@
   StringRef FileName = Replaces.begin()->getFilePath();
   IncludeCategoryManager Categories(Style, FileName);
 
+  std::unique_ptr<Environment> Env =
+      Environment::CreateVirtualEnvironment(Code, FileName, /*Ranges=*/{});
+  FormatTokenLexer Lexer(Env->getSourceManager(), Env->getFileID(), Style,
+                         encoding::detectEncoding(Code));
+  auto Tokens = Lexer.lex();
   // Record the offset of the end of the last include in each category.
   std::map<int, int> CategoryEndOffsets;
   // All possible priorities.
@@ -1483,11 +1492,22 @@
   for (const auto &Category : Style.IncludeCategories)
     Priorities.insert(Category.Priority);
   int FirstIncludeOffset = -1;
-  int Offset = 0;
-  int AfterHeaderGuard = 0;
+  // All new headers should be inserted after this offset.
+  int MinInsertOffset = 0;
+  bool HeaderGuardFound = false;
+  auto TokIter = Tokens.begin();
+  auto TokEnd = Tokens.end();
+  while (TokIter != TokEnd && (*TokIter)->is(tok::comment))
+    ++TokIter;
+  MinInsertOffset = (TokIter == TokEnd)
+                        ? Code.size()
+                        : getOffset(*Env, (*TokIter)->Tok.getLocation());
+  StringRef TrimmedCode = Code.drop_front(MinInsertOffset);
   SmallVector<StringRef, 32> Lines;
-  Code.split(Lines, '\n');
-  for (auto Line : Lines) {
+  TrimmedCode.split(Lines, '\n');
+  int Offset = MinInsertOffset;
+  for (auto I = Lines.begin(), E = Lines.end(); I != E; ++I) {
+    StringRef Line = *I;
     if (IncludeRegex.match(Line, &Matches)) {
       StringRef IncludeName = Matches[2];
       int Category = Categories.getIncludePriority(
@@ -1498,22 +1518,22 @@
     }
     Offset += Line.size() + 1;
     // FIXME: make header guard matching stricter, e.g. consider #ifndef.
-    if (AfterHeaderGuard == 0 && DefineRegex.match(Line))
-      AfterHeaderGuard = Offset;
+    if (!HeaderGuardFound && DefineRegex.match(Line)) {
+      HeaderGuardFound = true;
+      MinInsertOffset = Offset;
+    }
   }
 
   // Populate CategoryEndOfssets:
   // - Ensure that CategoryEndOffset[Highest] is always populated.
   // - If CategoryEndOffset[Priority] isn't set, use the next higher value that
   //   is set, up to CategoryEndOffset[Highest].
-  // FIXME: skip comment section in the beginning of the code if there is no
-  // existing #include and #define.
   auto Highest = Priorities.begin();
   if (CategoryEndOffsets.find(*Highest) == CategoryEndOffsets.end()) {
     if (FirstIncludeOffset >= 0)
       CategoryEndOffsets[*Highest] = FirstIncludeOffset;
     else
-      CategoryEndOffsets[*Highest] = AfterHeaderGuard;
+      CategoryEndOffsets[*Highest] = MinInsertOffset;
   }
   // By this point, CategoryEndOffset[Highest] is always set appropriately:
   //  - to an appropriate location before/after existing #includes, or
Index: unittests/Format/CleanupTest.cpp
===================================================================
--- unittests/Format/CleanupTest.cpp
+++ unittests/Format/CleanupTest.cpp
@@ -465,13 +465,13 @@
 
 TEST_F(CleanUpReplacementsTest, InsertMultipleNewHeadersAndSortLLVM) {
   std::string Code = "\nint x;";
-  std::string Expected = "#include \"fix.h\"\n"
+  std::string Expected = "\n#include \"fix.h\"\n"
                          "#include \"a.h\"\n"
                          "#include \"b.h\"\n"
                          "#include \"c.h\"\n"
                          "#include <list>\n"
                          "#include <vector>\n"
-                         "\nint x;";
+                         "int x;";
   tooling::Replacements Replaces = {createInsertion("#include \"a.h\""),
                                     createInsertion("#include \"c.h\""),
                                     createInsertion("#include \"b.h\""),
@@ -483,13 +483,13 @@
 
 TEST_F(CleanUpReplacementsTest, InsertMultipleNewHeadersAndSortGoogle) {
   std::string Code = "\nint x;";
-  std::string Expected = "#include \"fix.h\"\n"
+  std::string Expected = "\n#include \"fix.h\"\n"
                          "#include <list>\n"
                          "#include <vector>\n"
                          "#include \"a.h\"\n"
                          "#include \"b.h\"\n"
                          "#include \"c.h\"\n"
-                         "\nint x;";
+                         "int x;";
   tooling::Replacements Replaces = {createInsertion("#include \"a.h\""),
                                     createInsertion("#include \"c.h\""),
                                     createInsertion("#include \"b.h\""),
@@ -502,21 +502,22 @@
 
 TEST_F(CleanUpReplacementsTest, FormatCorrectLineWhenHeadersAreInserted) {
   std::string Code = "\n"
+                     "int x;\n"
                      "int    a;\n"
                      "int    a;\n"
                      "int    a;";
 
-  std::string Expected = "#include \"x.h\"\n"
+  std::string Expected = "\n#include \"x.h\"\n"
                          "#include \"y.h\"\n"
                          "#include \"clang/x/x.h\"\n"
                          "#include <list>\n"
                          "#include <vector>\n"
-                         "\n"
+                         "int x;\n"
                          "int    a;\n"
                          "int b;\n"
                          "int    a;";
   tooling::Replacements Replaces = {
-      createReplacement(getOffset(Code, 3, 8), 1, "b"),
+      createReplacement(getOffset(Code, 4, 8), 1, "b"),
       createInsertion("#include <vector>"),
       createInsertion("#include <list>"),
       createInsertion("#include \"clang/x/x.h\""),
@@ -537,6 +538,76 @@
   EXPECT_EQ(Expected, formatAndApply(Code, Replaces));
 }
 
+TEST_F(CleanUpReplacementsTest, SkippedTopComment) {
+  std::string Code = "// comment\n"
+                     "\n"
+                     "   // comment\n";
+  std::string Expected = "// comment\n"
+                         "\n"
+                         "   // comment\n"
+                         "#include <vector>\n";
+  tooling::Replacements Replaces = {createInsertion("#include <vector>")};
+  EXPECT_EQ(Expected, apply(Code, Replaces));
+}
+
+TEST_F(CleanUpReplacementsTest, SkippedMixedComments) {
+  std::string Code = "// comment\n"
+                     "// comment \\\n"
+                     " comment continued\n"
+                     "/*\n"
+                     "* comment\n"
+                     "*/\n";
+  std::string Expected = "// comment\n"
+                         "// comment \\\n"
+                         " comment continued\n"
+                         "/*\n"
+                         "* comment\n"
+                         "*/\n"
+                         "#include <vector>\n";
+  tooling::Replacements Replaces = {createInsertion("#include <vector>")};
+  EXPECT_EQ(Expected, apply(Code, Replaces));
+}
+
+TEST_F(CleanUpReplacementsTest, MultipleBlockCommentsInOneLine) {
+  std::string Code = "/*\n"
+                     "* comment\n"
+                     "*/ /* comment\n"
+                     "*/\n"
+                     "\n\n"
+                     "/* c1 */ /*c2 */\n";
+  std::string Expected = "/*\n"
+                         "* comment\n"
+                         "*/ /* comment\n"
+                         "*/\n"
+                         "\n\n"
+                         "/* c1 */ /*c2 */\n"
+                         "#include <vector>\n";
+  tooling::Replacements Replaces = {createInsertion("#include <vector>")};
+  EXPECT_EQ(Expected, apply(Code, Replaces));
+}
+
+TEST_F(CleanUpReplacementsTest, CodeAfterComments) {
+  std::string Code = "/*\n"
+                     "* comment\n"
+                     "*/ /* comment\n"
+                     "*/\n"
+                     "\n\n"
+                     "/* c1 */ /*c2 */\n"
+                     "\n"
+                     "int x;\n";
+  std::string Expected = "/*\n"
+                         "* comment\n"
+                         "*/ /* comment\n"
+                         "*/\n"
+                         "\n\n"
+                         "/* c1 */ /*c2 */\n"
+                         "\n"
+                         "#include <vector>\n"
+                         "int x;\n";
+  tooling::Replacements Replaces = {createInsertion("#include <vector>")};
+  EXPECT_EQ(Expected, apply(Code, Replaces));
+}
+
 } // end namespace
 } // end namespace format
 } // end namespace clang