ninja: break unnecessary target dependencies

Previously, given two libraries, X and Y where X depends on Y, all
object compilations of X would require the Y library to have been linked
before being compiled. This is not necessary and can instead be loosened
such that object compilations of X only depend on the order-only
dependencies of Y to be completed. This is to ensure that generated
sources, headers, custom commands, etc. are completed before X starts to
compile its objects.

This should help build performance in projects with many libraries which
cause a deep library dependency chain. Previously, a library at the
bottom would not start compilation until after all other libraries
completed, but now only its link step needs to wait and its compilation
jobs can be run in parallel with other tasks.

Fixes: #15555

12 files changed, 110 insertions, 24 deletions

diff --git a/Source/cmGlobalNinjaGenerator.cxx b/Source/cmGlobalNinjaGenerator.cxx
index e61cbd9..1a77d7c 100644
--- a/Source/cmGlobalNinjaGenerator.cxx
+++ b/Source/cmGlobalNinjaGenerator.cxx
@@ -966,8 +966,14 @@ void cmGlobalNinjaGenerator::WriteAssumedSourceDependencies()
   }
 }
 
+std::string OrderDependsTargetForTarget(cmGeneratorTarget const* target)
+{
+  return "cmake_object_order_depends_target_" + target->GetName();
+}
+
 void cmGlobalNinjaGenerator::AppendTargetOutputs(
-  cmGeneratorTarget const* target, cmNinjaDeps& outputs)
+  cmGeneratorTarget const* target, cmNinjaDeps& outputs,
+  cmNinjaTargetDepends depends)
 {
   std::string configName =
     target->Target->GetMakefile()->GetSafeDefinition("CMAKE_BUILD_TYPE");
@@ -979,15 +985,27 @@ void cmGlobalNinjaGenerator::AppendTargetOutputs(
   bool realname = target->IsFrameworkOnApple();
 
   switch (target->GetType()) {
-    case cmStateEnums::EXECUTABLE:
     case cmStateEnums::SHARED_LIBRARY:
     case cmStateEnums::STATIC_LIBRARY:
     case cmStateEnums::MODULE_LIBRARY: {
+      if (depends == DependOnTargetOrdering) {
+        outputs.push_back(OrderDependsTargetForTarget(target));
+        break;
+      }
+    }
+    // FALLTHROUGH
+    case cmStateEnums::EXECUTABLE: {
       outputs.push_back(this->ConvertToNinjaPath(target->GetFullPath(
         configName, cmStateEnums::RuntimeBinaryArtifact, realname)));
       break;
     }
-    case cmStateEnums::OBJECT_LIBRARY:
+    case cmStateEnums::OBJECT_LIBRARY: {
+      if (depends == DependOnTargetOrdering) {
+        outputs.push_back(OrderDependsTargetForTarget(target));
+        break;
+      }
+    }
+    // FALLTHROUGH
     case cmStateEnums::GLOBAL_TARGET:
     case cmStateEnums::UTILITY: {
       std::string path =
@@ -1003,7 +1021,8 @@ void cmGlobalNinjaGenerator::AppendTargetOutputs(
 }
 
 void cmGlobalNinjaGenerator::AppendTargetDepends(
-  cmGeneratorTarget const* target, cmNinjaDeps& outputs)
+  cmGeneratorTarget const* target, cmNinjaDeps& outputs,
+  cmNinjaTargetDepends depends)
 {
   if (target->GetType() == cmStateEnums::GLOBAL_TARGET) {
     // These depend only on other CMake-provided targets, e.g. "all".
@@ -1023,7 +1042,7 @@ void cmGlobalNinjaGenerator::AppendTargetDepends(
       if ((*i)->GetType() == cmStateEnums::INTERFACE_LIBRARY) {
         continue;
       }
-      this->AppendTargetOutputs(*i, outs);
+      this->AppendTargetOutputs(*i, outs, depends);
     }
     std::sort(outs.begin(), outs.end());
     outputs.insert(outputs.end(), outs.begin(), outs.end());
diff --git a/Source/cmGlobalNinjaGenerator.h b/Source/cmGlobalNinjaGenerator.h
index e06afb0..b1d6155 100644
--- a/Source/cmGlobalNinjaGenerator.h
+++ b/Source/cmGlobalNinjaGenerator.h
@@ -316,10 +316,12 @@ public:
     ASD.insert(deps.begin(), deps.end());
   }
 
-  void AppendTargetOutputs(cmGeneratorTarget const* target,
-                           cmNinjaDeps& outputs);
-  void AppendTargetDepends(cmGeneratorTarget const* target,
-                           cmNinjaDeps& outputs);
+  void AppendTargetOutputs(
+    cmGeneratorTarget const* target, cmNinjaDeps& outputs,
+    cmNinjaTargetDepends depends = DependOnTargetArtifact);
+  void AppendTargetDepends(
+    cmGeneratorTarget const* target, cmNinjaDeps& outputs,
+    cmNinjaTargetDepends depends = DependOnTargetArtifact);
   void AppendTargetDependsClosure(cmGeneratorTarget const* target,
                                   cmNinjaDeps& outputs);
   void AddDependencyToAll(cmGeneratorTarget* target);
diff --git a/Source/cmLocalNinjaGenerator.cxx b/Source/cmLocalNinjaGenerator.cxx
index c2d9d57..9d88e35 100644
--- a/Source/cmLocalNinjaGenerator.cxx
+++ b/Source/cmLocalNinjaGenerator.cxx
@@ -278,9 +278,11 @@ void cmLocalNinjaGenerator::AppendTargetOutputs(cmGeneratorTarget* target,
 }
 
 void cmLocalNinjaGenerator::AppendTargetDepends(cmGeneratorTarget* target,
-                                                cmNinjaDeps& outputs)
+                                                cmNinjaDeps& outputs,
+                                                cmNinjaTargetDepends depends)
 {
-  this->GetGlobalNinjaGenerator()->AppendTargetDepends(target, outputs);
+  this->GetGlobalNinjaGenerator()->AppendTargetDepends(target, outputs,
+                                                       depends);
 }
 
 void cmLocalNinjaGenerator::AppendCustomCommandDeps(
diff --git a/Source/cmLocalNinjaGenerator.h b/Source/cmLocalNinjaGenerator.h
index fda4578..a45e018 100644
--- a/Source/cmLocalNinjaGenerator.h
+++ b/Source/cmLocalNinjaGenerator.h
@@ -63,7 +63,9 @@ public:
   std::string BuildCommandLine(const std::vector<std::string>& cmdLines);
 
   void AppendTargetOutputs(cmGeneratorTarget* target, cmNinjaDeps& outputs);
-  void AppendTargetDepends(cmGeneratorTarget* target, cmNinjaDeps& outputs);
+  void AppendTargetDepends(
+    cmGeneratorTarget* target, cmNinjaDeps& outputs,
+    cmNinjaTargetDepends depends = DependOnTargetArtifact);
 
   void AddCustomCommandTarget(cmCustomCommand const* cc,
                               cmGeneratorTarget* target);
diff --git a/Source/cmNinjaTargetGenerator.cxx b/Source/cmNinjaTargetGenerator.cxx
index daad3fc..2c14a3e 100644
--- a/Source/cmNinjaTargetGenerator.cxx
+++ b/Source/cmNinjaTargetGenerator.cxx
@@ -715,8 +715,8 @@ void cmNinjaTargetGenerator::WriteObjectBuildStatements()
   }
 
   cmNinjaDeps orderOnlyDeps;
-  this->GetLocalGenerator()->AppendTargetDepends(this->GeneratorTarget,
-                                                 orderOnlyDeps);
+  this->GetLocalGenerator()->AppendTargetDepends(
+    this->GeneratorTarget, orderOnlyDeps, DependOnTargetOrdering);
 
   // Add order-only dependencies on other files associated with the target.
   orderOnlyDeps.insert(orderOnlyDeps.end(), this->ExtraFiles.begin(),
@@ -741,7 +741,7 @@ void cmNinjaTargetGenerator::WriteObjectBuildStatements()
   orderOnlyDeps.erase(std::unique(orderOnlyDeps.begin(), orderOnlyDeps.end()),
                       orderOnlyDeps.end());
 
-  if (!orderOnlyDeps.empty()) {
+  {
     cmNinjaDeps orderOnlyTarget;
     orderOnlyTarget.push_back(this->OrderDependsTargetForTarget());
     this->GetGlobalGenerator()->WritePhonyBuild(
@@ -754,7 +754,7 @@ void cmNinjaTargetGenerator::WriteObjectBuildStatements()
   for (std::vector<cmSourceFile const*>::const_iterator si =
          objectSources.begin();
        si != objectSources.end(); ++si) {
-    this->WriteObjectBuildStatement(*si, !orderOnlyDeps.empty());
+    this->WriteObjectBuildStatement(*si);
   }
 
   if (!this->DDIFiles.empty()) {
@@ -779,8 +779,8 @@ void cmNinjaTargetGenerator::WriteObjectBuildStatements()
     // our dependencies produces them.  Fixing this will require
     // refactoring the Ninja generator to generate targets in
     // dependency order so that we can collect the needed information.
-    this->GetLocalGenerator()->AppendTargetDepends(this->GeneratorTarget,
-                                                   ddOrderOnlyDeps);
+    this->GetLocalGenerator()->AppendTargetDepends(
+      this->GeneratorTarget, ddOrderOnlyDeps, DependOnTargetArtifact);
 
     this->GetGlobalGenerator()->WriteBuild(
       this->GetBuildFileStream(), ddComment, ddRule, ddOutputs, ddImplicitOuts,
@@ -791,7 +791,7 @@ void cmNinjaTargetGenerator::WriteObjectBuildStatements()
 }
 
 void cmNinjaTargetGenerator::WriteObjectBuildStatement(
-  cmSourceFile const* source, bool writeOrderDependsTargetForTarget)
+  cmSourceFile const* source)
 {
   std::string const language = source->GetLanguage();
   std::string const sourceFileName =
@@ -842,9 +842,7 @@ void cmNinjaTargetGenerator::WriteObjectBuildStatement(
   }
 
   cmNinjaDeps orderOnlyDeps;
-  if (writeOrderDependsTargetForTarget) {
-    orderOnlyDeps.push_back(this->OrderDependsTargetForTarget());
-  }
+  orderOnlyDeps.push_back(this->OrderDependsTargetForTarget());
 
   // If the source file is GENERATED and does not have a custom command
   // (either attached to this source file or another one), assume that one of
diff --git a/Source/cmNinjaTargetGenerator.h b/Source/cmNinjaTargetGenerator.h
index 9ce8651..5eb7a9a 100644
--- a/Source/cmNinjaTargetGenerator.h
+++ b/Source/cmNinjaTargetGenerator.h
@@ -119,8 +119,7 @@ protected:
   void WriteLanguageRules(const std::string& language);
   void WriteCompileRule(const std::string& language);
   void WriteObjectBuildStatements();
-  void WriteObjectBuildStatement(cmSourceFile const* source,
-                                 bool writeOrderDependsTargetForTarget);
+  void WriteObjectBuildStatement(cmSourceFile const* source);
   void WriteTargetDependInfo(std::string const& lang);
 
   void ExportObjectCompileCommand(
diff --git a/Source/cmNinjaTypes.h b/Source/cmNinjaTypes.h
index b4af70e..ec435d9 100644
--- a/Source/cmNinjaTypes.h
+++ b/Source/cmNinjaTypes.h
@@ -9,6 +9,12 @@
 #include <string>
 #include <vector>
 
+enum cmNinjaTargetDepends
+{
+  DependOnTargetArtifact,
+  DependOnTargetOrdering
+};
+
 typedef std::vector<std::string> cmNinjaDeps;
 typedef std::map<std::string, std::string> cmNinjaVars;
 
diff --git a/Tests/RunCMake/CMakeLists.txt b/Tests/RunCMake/CMakeLists.txt
index 32c4be8..21e6259 100644
--- a/Tests/RunCMake/CMakeLists.txt
+++ b/Tests/RunCMake/CMakeLists.txt
@@ -119,6 +119,10 @@ if(CMAKE_GENERATOR MATCHES "Make")
   add_RunCMake_test(Make)
 endif()
 if(CMAKE_GENERATOR STREQUAL "Ninja")
+  set(Ninja_ARGS
+    -DCMAKE_C_OUTPUT_EXTENSION=${CMAKE_C_OUTPUT_EXTENSION}
+    -DCMAKE_SHARED_LIBRARY_PREFIX=${CMAKE_SHARED_LIBRARY_PREFIX}
+    -DCMAKE_SHARED_LIBRARY_SUFFIX=${CMAKE_SHARED_LIBRARY_SUFFIX})
   add_RunCMake_test(Ninja)
 endif()
 add_RunCMake_test(CTest)
diff --git a/Tests/RunCMake/Ninja/LooseObjectDepends.cmake b/Tests/RunCMake/Ninja/LooseObjectDepends.cmake
new file mode 100644
index 0000000..360c7ba
--- /dev/null
+++ b/Tests/RunCMake/Ninja/LooseObjectDepends.cmake
@@ -0,0 +1,26 @@
+cmake_minimum_required(VERSION 3.8)
+project(LooseObjectDepends C)
+
+add_custom_command(
+  OUTPUT  "${CMAKE_CURRENT_BINARY_DIR}/command.h"
+  COMMAND "${CMAKE_COMMAND}" -E touch
+          "${CMAKE_CURRENT_BINARY_DIR}/command.h"
+          COMMENT "Creating command.h")
+add_custom_target(create-command.h
+  DEPENDS
+    "${CMAKE_CURRENT_BINARY_DIR}/command.h")
+
+add_custom_target(create-target.h
+  BYPRODUCTS  "${CMAKE_CURRENT_BINARY_DIR}/target.h"
+  COMMAND "${CMAKE_COMMAND}" -E touch
+          "${CMAKE_CURRENT_BINARY_DIR}/target.h"
+  COMMENT "Creating target.h")
+
+add_library(dep SHARED dep.c)
+add_dependencies(dep create-command.h create-target.h)
+target_include_directories(dep
+  PUBLIC
+    "${CMAKE_CURRENT_BINARY_DIR}")
+
+add_library(top top.c)
+target_link_libraries(top PRIVATE dep)
diff --git a/Tests/RunCMake/Ninja/RunCMakeTest.cmake b/Tests/RunCMake/Ninja/RunCMakeTest.cmake
index 063a6d1..fb7798d 100644
--- a/Tests/RunCMake/Ninja/RunCMakeTest.cmake
+++ b/Tests/RunCMake/Ninja/RunCMakeTest.cmake
@@ -95,6 +95,23 @@ ${ninja_stderr}
   endif()
 endfunction(run_ninja)
 
+function (run_LooseObjectDepends)
+  set(RunCMake_TEST_BINARY_DIR ${RunCMake_BINARY_DIR}/LooseObjectDepends-build)
+  run_cmake(LooseObjectDepends)
+  run_ninja("${RunCMake_TEST_BINARY_DIR}" "CMakeFiles/top.dir/top.c${CMAKE_C_OUTPUT_EXTENSION}")
+  if (EXISTS "${RunCMake_TEST_BINARY_DIR}/${CMAKE_SHARED_LIBRARY_PREFIX}dep${CMAKE_SHARED_LIBRARY_SUFFIX}")
+    message(FATAL_ERROR
+      "The `dep` library was created when requesting an object file to be "
+      "built; this should no longer be necessary.")
+  endif ()
+  if (EXISTS "${RunCMake_TEST_BINARY_DIR}/CMakeFiles/dep.dir/dep.c${CMAKE_C_OUTPUT_EXTENSION}")
+    message(FATAL_ERROR
+      "The `dep.c` object file was created when requesting an object file to "
+      "be built; this should no longer be necessary.")
+  endif ()
+endfunction ()
+run_LooseObjectDepends()
+
 function(sleep delay)
   execute_process(
     COMMAND ${CMAKE_COMMAND} -E sleep ${delay}
diff --git a/Tests/RunCMake/Ninja/dep.c b/Tests/RunCMake/Ninja/dep.c
new file mode 100644
index 0000000..728f031
--- /dev/null
+++ b/Tests/RunCMake/Ninja/dep.c
@@ -0,0 +1,4 @@
+int dep()
+{
+  return 0;
+}
diff --git a/Tests/RunCMake/Ninja/top.c b/Tests/RunCMake/Ninja/top.c
new file mode 100644
index 0000000..4a88eb2
--- /dev/null
+++ b/Tests/RunCMake/Ninja/top.c
@@ -0,0 +1,7 @@
+#include "command.h"
+#include "target.h"
+
+int top()
+{
+  return 0;
+}