Linking: Optionally reorder direct dependencies from LINK_LIBRARIES

Traditionally CMake generates link lines by starting with the direct
link dependencies specified by `LINK_LIBRARIES` in their original order
and then appending indirect dependencies that the direct dependencies
do not express.  This gives projects control over ordering among
independent entries, which can be important when intermixing flags
and libraries, or when multiple libraries provide the same symbol.
However, it may also result in inefficient link lines.

Add support for an alternative strategy that can reorder direct link
dependencies to produce more efficient link lines.  This is useful
for projects that cannot easily specify their targets' direct
dependencies in an order that satisfies indirect dependencies.

Add a `CMAKE_LINK_LIBRARIES_STRATEGY` variable and corresponding
`LINK_LIBRARIES_STRATEGY` target property to select a strategy.

Fixes: #26271

4 files changed, 48 insertions, 5 deletions

diff --git a/Source/cmComputeLinkDepends.cxx b/Source/cmComputeLinkDepends.cxx
index ae33c12..70e992e 100644
--- a/Source/cmComputeLinkDepends.cxx
+++ b/Source/cmComputeLinkDepends.cxx
@@ -581,7 +581,8 @@ std::string const& cmComputeLinkDepends::LinkEntry::DEFAULT =
 
 cmComputeLinkDepends::cmComputeLinkDepends(const cmGeneratorTarget* target,
                                            const std::string& config,
-                                           const std::string& linkLanguage)
+                                           const std::string& linkLanguage,
+                                           LinkLibrariesStrategy strategy)
   : Target(target)
   , Makefile(this->Target->Target->GetMakefile())
   , GlobalGenerator(this->Target->GetLocalGenerator()->GetGlobalGenerator())
@@ -592,6 +593,7 @@ cmComputeLinkDepends::cmComputeLinkDepends(const cmGeneratorTarget* target,
   , LinkLanguage(linkLanguage)
   , LinkType(CMP0003_ComputeLinkType(
       this->Config, this->Makefile->GetCMakeInstance()->GetDebugConfigs()))
+  , Strategy(strategy)
 
 {
   // target oriented feature override property takes precedence over
@@ -1488,8 +1490,22 @@ void cmComputeLinkDepends::OrderLinkEntries()
   }
 
   // Start with the original link line.
-  for (size_t originalEntry : this->OriginalEntries) {
-    this->VisitEntry(originalEntry);
+  switch (this->Strategy) {
+    case LinkLibrariesStrategy::PRESERVE_ORDER: {
+      // Emit the direct dependencies in their original order.
+      // This gives projects control over ordering.
+      for (size_t originalEntry : this->OriginalEntries) {
+        this->VisitEntry(originalEntry);
+      }
+    } break;
+    case LinkLibrariesStrategy::REORDER: {
+      // Schedule the direct dependencies for emission in topo order.
+      // This may produce more efficient link lines.
+      for (size_t originalEntry : this->OriginalEntries) {
+        this->MakePendingComponent(
+          this->CCG->GetComponentMap()[originalEntry]);
+      }
+    } break;
   }
 
   // Now explore anything left pending.  Since the component graph is
diff --git a/Source/cmComputeLinkDepends.h b/Source/cmComputeLinkDepends.h
index 55f0032..8b8aba4 100644
--- a/Source/cmComputeLinkDepends.h
+++ b/Source/cmComputeLinkDepends.h
@@ -27,6 +27,12 @@ class cmMakefile;
 class cmSourceFile;
 class cmake;
 
+enum class LinkLibrariesStrategy
+{
+  PRESERVE_ORDER,
+  REORDER,
+};
+
 /** \class cmComputeLinkDepends
  * \brief Compute link dependencies for targets.
  */
@@ -35,7 +41,8 @@ class cmComputeLinkDepends
 public:
   cmComputeLinkDepends(cmGeneratorTarget const* target,
                        const std::string& config,
-                       const std::string& linkLanguage);
+                       const std::string& linkLanguage,
+                       LinkLibrariesStrategy strategy);
   ~cmComputeLinkDepends();
 
   cmComputeLinkDepends(const cmComputeLinkDepends&) = delete;
@@ -94,6 +101,7 @@ private:
   bool DebugMode = false;
   std::string LinkLanguage;
   cmTargetLinkLibraryType LinkType;
+  LinkLibrariesStrategy Strategy;
 
   EntryVector FinalLinkEntries;
   std::map<std::string, std::string> LinkLibraryOverride;
diff --git a/Source/cmComputeLinkInformation.cxx b/Source/cmComputeLinkInformation.cxx
index dd194ed..26ff326 100644
--- a/Source/cmComputeLinkInformation.cxx
+++ b/Source/cmComputeLinkInformation.cxx
@@ -9,6 +9,7 @@
 
 #include <cm/memory>
 #include <cm/optional>
+#include <cm/string_view>
 #include <cmext/algorithm>
 #include <cmext/string_view>
 
@@ -567,8 +568,25 @@ bool cmComputeLinkInformation::Compute()
     return false;
   }
 
+  LinkLibrariesStrategy strategy = LinkLibrariesStrategy::PRESERVE_ORDER;
+  if (cmValue s = this->Target->GetProperty("LINK_LIBRARIES_STRATEGY")) {
+    if (*s == "PRESERVE_ORDER"_s) {
+      strategy = LinkLibrariesStrategy::PRESERVE_ORDER;
+    } else if (*s == "REORDER"_s) {
+      strategy = LinkLibrariesStrategy::REORDER;
+    } else {
+      this->CMakeInstance->IssueMessage(
+        MessageType::FATAL_ERROR,
+        cmStrCat("LINK_LIBRARIES_STRATEGY value '", *s,
+                 "' is not recognized."),
+        this->Target->GetBacktrace());
+      return false;
+    }
+  }
+
   // Compute the ordered link line items.
-  cmComputeLinkDepends cld(this->Target, this->Config, this->LinkLanguage);
+  cmComputeLinkDepends cld(this->Target, this->Config, this->LinkLanguage,
+                           strategy);
   cld.SetOldLinkDirMode(this->OldLinkDirMode);
   cmComputeLinkDepends::EntryVector const& linkEntries = cld.Compute();
   FeatureDescriptor const* currentFeature = nullptr;
diff --git a/Source/cmTarget.cxx b/Source/cmTarget.cxx
index da0091b..f220837 100644
--- a/Source/cmTarget.cxx
+++ b/Source/cmTarget.cxx
@@ -466,6 +466,7 @@ TargetProperty const StaticTargetProperties[] = {
   { "LINKER_TYPE"_s, IC::CanCompileSources },
   { "ENABLE_EXPORTS"_s, IC::TargetWithSymbolExports },
   { "LINK_LIBRARIES_ONLY_TARGETS"_s, IC::NormalNonImportedTarget },
+  { "LINK_LIBRARIES_STRATEGY"_s, IC::NormalNonImportedTarget },
   { "LINK_SEARCH_START_STATIC"_s, IC::CanCompileSources },
   { "LINK_SEARCH_END_STATIC"_s, IC::CanCompileSources },
   // Initialize per-configuration name postfix property from the variable only