ENH: Analyze inter-target dependencies to safely fix cycles

  - Cycles may be formed among static libraries
  - Native build system should not have cycles in target deps
  - Create cmComputeTargetDepends to analyze dependencies
  - Identify conneced components and use them to fix deps
  - Diagnose cycles containing non-STATIC targets
  - Add debug mode property GLOBAL_DEPENDS_DEBUG_MODE
  - Use results in cmGlobalGenerator as target direct depends

7 files changed, 642 insertions, 144 deletions

diff --git a/Source/CMakeLists.txt b/Source/CMakeLists.txt
index a73f511..dc83ca3 100644
--- a/Source/CMakeLists.txt
+++ b/Source/CMakeLists.txt
@@ -91,6 +91,8 @@ SET(SRCS
   cmComputeLinkDepends.h
   cmComputeLinkInformation.cxx
   cmComputeLinkInformation.h
+  cmComputeTargetDepends.h
+  cmComputeTargetDepends.cxx
   cmCustomCommand.cxx
   cmCustomCommand.h
   cmDepends.cxx
diff --git a/Source/cmComputeTargetDepends.cxx b/Source/cmComputeTargetDepends.cxx
new file mode 100644
index 0000000..3062c4d
--- /dev/null
+++ b/Source/cmComputeTargetDepends.cxx
@@ -0,0 +1,527 @@
+/*=========================================================================
+
+  Program:   CMake - Cross-Platform Makefile Generator
+  Module:    $RCSfile$
+  Language:  C++
+  Date:      $Date$
+  Version:   $Revision$
+
+  Copyright (c) 2002 Kitware, Inc., Insight Consortium.  All rights reserved.
+  See Copyright.txt or http://www.cmake.org/HTML/Copyright.html for details.
+
+     This software is distributed WITHOUT ANY WARRANTY; without even
+     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+     PURPOSE.  See the above copyright notices for more information.
+
+=========================================================================*/
+#include "cmComputeTargetDepends.h"
+
+#include "cmGlobalGenerator.h"
+#include "cmLocalGenerator.h"
+#include "cmMakefile.h"
+#include "cmSystemTools.h"
+#include "cmTarget.h"
+#include "cmake.h"
+
+#include <algorithm>
+
+#include <assert.h>
+
+/*
+
+This class is meant to analyze inter-target dependencies globally
+during the generation step.  The goal is to produce a set of direct
+dependencies for each target such that no cycles are left and the
+build order is safe.
+
+For most target types cyclic dependencies are not allowed.  However
+STATIC libraries may depend on each other in a cyclic fasion.  In
+general the directed dependency graph forms a directed-acyclic-graph
+of strongly connected components.  All strongly connected components
+should consist of only STATIC_LIBRARY targets.
+
+In order to safely break dependency cycles we must preserve all other
+dependencies passing through the corresponding strongly connected component.
+The approach taken by this class is as follows:
+
+  - Collect all targets and form the original dependency graph
+  - Run Tarjan's algorithm to extract the strongly connected components
+    (error if any member of a non-trivial component is not STATIC)
+  - The original dependencies imply a DAG on the components.
+    Use the implied DAG to construct a final safe set of dependencies.
+
+The final dependency set is constructed as follows:
+
+  - For each connected component targets are placed in an arbitrary
+    order.  Each target depends on the target following it in the order.
+    The first target is designated the head and the last target the tail.
+    (most components will be just 1 target anyway)
+
+  - Original dependencies between targets in different components are
+    converted to connect the depender's component tail to the
+    dependee's component head.
+
+In most cases this will reproduce the original dependencies.  However
+when there are cycles of static libraries they will be broken in a
+safe manner.
+
+For example, consider targets A0, A1, A2, B0, B1, B2, and C with these
+dependencies:
+
+  A0 -> A1 -> A2 -> A0  ,  B0 -> B1 -> B2 -> B0 -> A0  ,  C -> B0
+
+Components may be identified as
+
+  Component 0: A0, A1, A2
+  Component 1: B0, B1, B2
+  Component 2: C
+
+Intra-component dependencies are:
+
+  0: A0 -> A1 -> A2   , head=A0, tail=A2
+  1: B0 -> B1 -> B2   , head=B0, tail=B2
+  2: head=C, tail=C
+
+The inter-component dependencies are converted as:
+
+  B0 -> A0  is component 1->0 and becomes  B2 -> A0
+  C  -> B0  is component 2->1 and becomes  C  -> B0
+
+This leads to the final target dependencies:
+
+  C -> B0 -> B1 -> B2 -> A0 -> A1 -> A2
+
+These produce a safe build order since C depends directly or
+transitively on all the static libraries it links.
+
+*/
+
+//----------------------------------------------------------------------------
+cmComputeTargetDepends::cmComputeTargetDepends(cmGlobalGenerator* gg)
+{
+  this->GlobalGenerator = gg;
+  cmake* cm = this->GlobalGenerator->GetCMakeInstance();
+  this->DebugMode = cm->GetPropertyAsBool("GLOBAL_DEPENDS_DEBUG_MODE");
+}
+
+//----------------------------------------------------------------------------
+cmComputeTargetDepends::~cmComputeTargetDepends()
+{
+}
+
+//----------------------------------------------------------------------------
+bool cmComputeTargetDepends::Compute()
+{
+  // Build the original graph.
+  this->CollectTargets();
+  this->CollectDepends();
+  if(this->DebugMode)
+    {
+    this->DisplayGraph(this->TargetDependGraph, "initial");
+    }
+
+  // Identify components.
+  this->Tarjan();
+  if(this->DebugMode)
+    {
+    this->DisplayComponents();
+    }
+  if(!this->CheckComponents())
+    {
+    return false;
+    }
+
+  // Compute the final dependency graph.
+  this->ComputeFinalDepends();
+  if(this->DebugMode)
+    {
+    this->DisplayGraph(this->FinalDependGraph, "final");
+    }
+
+  return true;
+}
+
+//----------------------------------------------------------------------------
+void
+cmComputeTargetDepends::GetTargetDirectDepends(cmTarget* t,
+                                               std::set<cmTarget*>& deps)
+{
+  // Lookup the index for this target.  All targets should be known by
+  // this point.
+  std::map<cmTarget*, int>::const_iterator tii = this->TargetIndex.find(t);
+  assert(tii != this->TargetIndex.end());
+  int i = tii->second;
+
+  // Get its final dependencies.
+  TargetDependList const& tdl = this->FinalDependGraph[i];
+  for(TargetDependList::const_iterator di = tdl.begin();
+      di != tdl.end(); ++di)
+    {
+    deps.insert(this->Targets[*di]);
+    }
+}
+
+//----------------------------------------------------------------------------
+void cmComputeTargetDepends::CollectTargets()
+{
+  // Collect all targets from all generators.
+  std::vector<cmLocalGenerator*> const& lgens =
+    this->GlobalGenerator->GetLocalGenerators();
+  for(unsigned int i = 0; i < lgens.size(); ++i)
+    {
+    cmTargets& targets = lgens[i]->GetMakefile()->GetTargets();
+    for(cmTargets::iterator ti = targets.begin(); ti != targets.end(); ++ti)
+      {
+      cmTarget* target = &ti->second;
+      int index = static_cast<int>(this->Targets.size());
+      this->TargetIndex[target] = index;
+      this->Targets.push_back(target);
+      }
+    }
+}
+
+//----------------------------------------------------------------------------
+void cmComputeTargetDepends::CollectDepends()
+{
+  // Allocate the dependency graph adjacency lists.
+  this->TargetDependGraph.resize(this->Targets.size());
+
+  // Compute each dependency list.
+  for(unsigned int i=0; i < this->Targets.size(); ++i)
+    {
+    this->CollectTargetDepends(i);
+    }
+}
+
+//----------------------------------------------------------------------------
+void cmComputeTargetDepends::CollectTargetDepends(int depender_index)
+{
+  // Get the depender.
+  cmTarget* depender = this->Targets[depender_index];
+
+  // Keep track of dependencies already listed.
+  std::set<cmStdString> emitted;
+
+  // A target should not depend on itself.
+  emitted.insert(depender->GetName());
+
+  // Loop over all targets linked directly.
+  cmTarget::LinkLibraryVectorType const& tlibs =
+    depender->GetOriginalLinkLibraries();
+  for(cmTarget::LinkLibraryVectorType::const_iterator lib = tlibs.begin();
+      lib != tlibs.end(); ++lib)
+    {
+    // Don't emit the same library twice for this target.
+    if(emitted.insert(lib->first).second)
+      {
+      this->AddTargetDepend(depender_index, lib->first.c_str());
+      }
+    }
+
+  // Loop over all utility dependencies.
+  std::set<cmStdString> const& tutils = depender->GetUtilities();
+  for(std::set<cmStdString>::const_iterator util = tutils.begin();
+      util != tutils.end(); ++util)
+    {
+    // Don't emit the same utility twice for this target.
+    if(emitted.insert(*util).second)
+      {
+      this->AddTargetDepend(depender_index, util->c_str());
+      }
+    }
+}
+
+//----------------------------------------------------------------------------
+void cmComputeTargetDepends::AddTargetDepend(int depender_index,
+                                             const char* dependee_name)
+{
+  // Get the depender.
+  cmTarget* depender = this->Targets[depender_index];
+
+  // Check the target's makefile first.
+  cmTarget* dependee =
+    depender->GetMakefile()->FindTarget(dependee_name);
+
+  // Then search globally.
+  if(!dependee)
+    {
+    dependee = this->GlobalGenerator->FindTarget(0, dependee_name);
+    }
+
+  // If not found then skip then the dependee.
+  if(!dependee)
+    {
+    return;
+    }
+
+  // No imported targets should have been found.
+  assert(!dependee->IsImported());
+
+  // Lookup the index for this target.  All targets should be known by
+  // this point.
+  std::map<cmTarget*, int>::const_iterator tii =
+    this->TargetIndex.find(dependee);
+  assert(tii != this->TargetIndex.end());
+  int dependee_index = tii->second;
+
+  // Add this entry to the dependency graph.
+  this->TargetDependGraph[depender_index].push_back(dependee_index);
+}
+
+//----------------------------------------------------------------------------
+void
+cmComputeTargetDepends
+::DisplayGraph(std::vector<TargetDependList> const& graph,
+               const char* name)
+{
+  fprintf(stderr, "The %s target dependency graph is:\n", name);
+  int n = static_cast<int>(graph.size());
+  for(int depender_index = 0; depender_index < n; ++depender_index)
+    {
+    TargetDependList const& tdl = graph[depender_index];
+    cmTarget* depender = this->Targets[depender_index];
+    fprintf(stderr, "target %d is [%s]\n",
+            depender_index, depender->GetName());
+    for(TargetDependList::const_iterator di = tdl.begin();
+        di != tdl.end(); ++di)
+      {
+      int dependee_index = *di;
+      cmTarget* dependee = this->Targets[dependee_index];
+      fprintf(stderr, "  depends on target %d [%s]\n", dependee_index,
+              dependee->GetName());
+      }
+    }
+  fprintf(stderr, "\n");
+}
+
+//----------------------------------------------------------------------------
+void cmComputeTargetDepends::Tarjan()
+{
+  int n = static_cast<int>(this->TargetDependGraph.size());
+  TarjanEntry entry = {0,-1,0};
+  this->TarjanEntries.resize(n, entry);
+  this->TarjanWalkId = 0;
+  this->TarjanVisited.resize(n, 0);
+  for(int i = 0; i < n; ++i)
+    {
+    // Start a new DFS from this node if it has never been visited.
+    if(!this->TarjanVisited[i])
+      {
+      assert(this->TarjanStack.empty());
+      ++this->TarjanWalkId;
+      this->TarjanIndex = 0;
+      this->TarjanVisit(i);
+      }
+    }
+}
+
+//----------------------------------------------------------------------------
+void cmComputeTargetDepends::TarjanVisit(int i)
+{
+  // We are now visiting this node.
+  this->TarjanVisited[i] = this->TarjanWalkId;
+
+  // Initialize the entry.
+  this->TarjanEntries[i].Root = i;
+  this->TarjanEntries[i].Component = -1;
+  this->TarjanEntries[i].VisitIndex = ++this->TarjanIndex;
+  this->TarjanStack.push(i);
+
+  // Follow outgoing edges.
+  TargetDependList const& tdl = this->TargetDependGraph[i];
+  for(TargetDependList::const_iterator di = tdl.begin();
+      di != tdl.end(); ++di)
+    {
+    int j = *di;
+
+    // Ignore edges to nodes that have been reached by a previous DFS
+    // walk.  Since we did not reach the current node from that walk
+    // it must not belong to the same component and it has already
+    // been assigned to a component.
+    if(this->TarjanVisited[j] > 0 &&
+       this->TarjanVisited[j] < this->TarjanWalkId)
+      {
+      continue;
+      }
+
+    // Visit the destination if it has not yet been visited.
+    if(!this->TarjanVisited[j])
+      {
+      this->TarjanVisit(j);
+      }
+
+    // If the destination has not yet been assigned to a component,
+    // check if it is a better potential root for the current object.
+    if(this->TarjanEntries[j].Component < 0)
+      {
+      if(this->TarjanEntries[this->TarjanEntries[j].Root].VisitIndex <
+         this->TarjanEntries[this->TarjanEntries[i].Root].VisitIndex)
+        {
+        this->TarjanEntries[i].Root = this->TarjanEntries[j].Root;
+        }
+      }
+    }
+
+  // Check if we have found a component.
+  if(this->TarjanEntries[i].Root == i)
+    {
+    // Yes.  Create it.
+    int c = static_cast<int>(this->Components.size());
+    this->Components.push_back(ComponentList());
+    ComponentList& component = this->Components[c];
+
+    // Populate the component list.
+    int j;
+    do
+      {
+      // Get the next member of the component.
+      j = this->TarjanStack.top();
+      this->TarjanStack.pop();
+
+      // Assign the member to the component.
+      this->TarjanEntries[j].Component = c;
+      this->TarjanEntries[j].Root = i;
+
+      // Store the node in its component.
+      component.push_back(j);
+      } while(j != i);
+
+    // Sort the component members for clarity.
+    std::sort(component.begin(), component.end());
+    }
+}
+
+//----------------------------------------------------------------------------
+void cmComputeTargetDepends::DisplayComponents()
+{
+  fprintf(stderr, "The strongly connected components are:\n");
+  int n = static_cast<int>(this->Components.size());
+  for(int c = 0; c < n; ++c)
+    {
+    ComponentList const& cl = this->Components[c];
+    fprintf(stderr, "Component (%d):\n", c);
+    for(ComponentList::const_iterator ci = cl.begin();
+        ci != cl.end(); ++ci)
+      {
+      int i = *ci;
+      fprintf(stderr, "  contains target %d [%s]\n",
+              i, this->Targets[i]->GetName());
+      }
+    }
+  fprintf(stderr, "\n");
+}
+
+//----------------------------------------------------------------------------
+bool cmComputeTargetDepends::CheckComponents()
+{
+  // All non-trivial components should consist only of static
+  // libraries.
+  int nc = static_cast<int>(this->Components.size());
+  for(int c=0; c < nc; ++c)
+    {
+    // Get the current component.
+    ComponentList const& cl = this->Components[c];
+
+    // Skip trivial components.
+    if(cl.size() < 2)
+      {
+      continue;
+      }
+
+    // Make sure the component is all STATIC_LIBRARY targets.
+    for(ComponentList::const_iterator ci = cl.begin(); ci != cl.end(); ++ci)
+      {
+      if(this->Targets[*ci]->GetType() != cmTarget::STATIC_LIBRARY)
+        {
+        this->ComplainAboutBadComponent(c);
+        return false;
+        }
+      }
+    }
+  return true;
+}
+
+//----------------------------------------------------------------------------
+void
+cmComputeTargetDepends::ComplainAboutBadComponent(int c)
+{
+  // Get the bad component.
+  ComponentList const& cl = this->Components[c];
+
+  // Construct the error message.
+  cmOStringStream e;
+  e << "The inter-target dependency graph contains the following "
+    << "strongly connected component (cycle):\n";
+  for(ComponentList::const_iterator ci = cl.begin(); ci != cl.end(); ++ci)
+    {
+    // Get the depender.
+    int i = *ci;
+    cmTarget* depender = this->Targets[i];
+
+    // Describe the depender.
+    e << "  " << depender->GetName() << " of type "
+      << cmTarget::TargetTypeNames[depender->GetType()] << "\n";
+
+    // List its dependencies that are inside the component.
+    TargetDependList const& tdl = this->TargetDependGraph[i];
+    for(TargetDependList::const_iterator di = tdl.begin();
+        di != tdl.end(); ++di)
+      {
+      int j = *di;
+      if(this->TarjanEntries[j].Component == c)
+        {
+        cmTarget* dependee = this->Targets[j];
+        e << "    depends on " << dependee->GetName() << "\n";
+        }
+      }
+    }
+  e << "At least one of these targets is not a STATIC_LIBRARY.  "
+    << "Cyclic dependencies are allowed only among static libraries.";
+  cmSystemTools::Error(e.str().c_str());
+}
+
+//----------------------------------------------------------------------------
+void cmComputeTargetDepends::ComputeFinalDepends()
+{
+  int n = static_cast<int>(this->TargetDependGraph.size());
+  this->FinalDependGraph.resize(n);
+
+  // Convert inter-component edges to connect component tails to heads.
+  for(int i=0; i < n; ++i)
+    {
+    int depender_component = this->TarjanEntries[i].Component;
+    int depender_component_tail =
+      this->Components[depender_component].back();
+
+    TargetDependList const& tdl = this->TargetDependGraph[i];
+    for(TargetDependList::const_iterator di = tdl.begin();
+        di != tdl.end(); ++di)
+      {
+      int j = *di;
+      int dependee_component = this->TarjanEntries[j].Component;
+      int dependee_component_head =
+        this->Components[dependee_component].front();
+      if(depender_component != dependee_component)
+        {
+        this->FinalDependGraph[depender_component_tail]
+          .push_back(dependee_component_head);
+        }
+      }
+    }
+
+  // Compute intra-component edges.
+  int nc = static_cast<int>(this->Components.size());
+  for(int c=0; c < nc; ++c)
+    {
+    // Within the component each target depends on that following it.
+    ComponentList const& cl = this->Components[c];
+    ComponentList::const_iterator ci = cl.begin();
+    int last_i = *ci;
+    for(++ci; ci != cl.end(); ++ci)
+      {
+      int i = *ci;
+      this->FinalDependGraph[last_i].push_back(i);
+      last_i = i;
+      }
+    }
+}
diff --git a/Source/cmComputeTargetDepends.h b/Source/cmComputeTargetDepends.h
new file mode 100644
index 0000000..9c17731
--- /dev/null
+++ b/Source/cmComputeTargetDepends.h
@@ -0,0 +1,90 @@
+/*=========================================================================
+
+  Program:   CMake - Cross-Platform Makefile Generator
+  Module:    $RCSfile$
+  Language:  C++
+  Date:      $Date$
+  Version:   $Revision$
+
+  Copyright (c) 2002 Kitware, Inc., Insight Consortium.  All rights reserved.
+  See Copyright.txt or http://www.cmake.org/HTML/Copyright.html for details.
+
+     This software is distributed WITHOUT ANY WARRANTY; without even
+     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+     PURPOSE.  See the above copyright notices for more information.
+
+=========================================================================*/
+#ifndef cmComputeTargetDepends_h
+#define cmComputeTargetDepends_h
+
+#include "cmStandardIncludes.h"
+
+#include <stack>
+
+class cmGlobalGenerator;
+class cmTarget;
+
+/** \class cmComputeTargetDepends
+ * \brief Compute global interdependencies among targets.
+ *
+ * Static libraries may form cycles in the target dependency graph.
+ * This class evaluates target dependencies globally and adjusts them
+ * to remove cycles while preserving a safe build order.
+ */
+class cmComputeTargetDepends
+{
+public:
+  cmComputeTargetDepends(cmGlobalGenerator* gg);
+  ~cmComputeTargetDepends();
+
+  bool Compute();
+
+  std::vector<cmTarget*> const& GetTargets() const { return this->Targets; }
+  void GetTargetDirectDepends(cmTarget* t, std::set<cmTarget*>& deps);
+private:
+  void CollectTargets();
+  void CollectDepends();
+  void CollectTargetDepends(int depender_index);
+  void AddTargetDepend(int depender_index, const char* dependee_name);
+  void ComputeFinalDepends();
+
+  cmGlobalGenerator* GlobalGenerator;
+  bool DebugMode;
+
+  // Collect all targets.
+  std::vector<cmTarget*> Targets;
+  std::map<cmTarget*, int> TargetIndex;
+
+  // Represent the target dependency graph.  The entry at each
+  // top-level index corresponds to a depender whose dependencies are
+  // listed.
+  struct TargetDependList: public std::vector<int> {};
+  std::vector<TargetDependList> TargetDependGraph;
+  std::vector<TargetDependList> FinalDependGraph;
+  void DisplayGraph(std::vector<TargetDependList> const& graph,
+                    const char* name);
+
+  // Tarjan's algorithm.
+  struct TarjanEntry
+  {
+    int Root;
+    int Component;
+    int VisitIndex;
+  };
+  int TarjanWalkId;
+  std::vector<int> TarjanVisited;
+  std::vector<TarjanEntry> TarjanEntries;
+  std::stack<int> TarjanStack;
+  int TarjanIndex;
+  void Tarjan();
+  void TarjanVisit(int i);
+
+  // Connected components.
+  struct ComponentList: public std::vector<int> {};
+  std::vector<ComponentList> Components;
+  void DisplayComponents();
+  bool CheckComponents();
+  void ComplainAboutBadComponent(int c);
+};
+
+#endif
diff --git a/Source/cmGlobalGenerator.cxx b/Source/cmGlobalGenerator.cxx
index 0c7845f..25d1bef 100644
--- a/Source/cmGlobalGenerator.cxx
+++ b/Source/cmGlobalGenerator.cxx
@@ -26,6 +26,7 @@
 #include "cmSourceFile.h"
 #include "cmVersion.h"
 #include "cmExportInstallFileGenerator.h"
+#include "cmComputeTargetDepends.h"
 
 #include <cmsys/Directory.hxx>
 
@@ -788,6 +789,18 @@ void cmGlobalGenerator::Generate()
     this->LocalGenerators[i]->GenerateTargetManifest();
     }
 
+  // Compute the inter-target dependencies.
+  {
+  cmComputeTargetDepends ctd(this);
+  ctd.Compute();
+  std::vector<cmTarget*> const& targets = ctd.GetTargets();
+  for(std::vector<cmTarget*>::const_iterator ti = targets.begin();
+      ti != targets.end(); ++ti)
+    {
+    ctd.GetTargetDirectDepends(*ti, this->TargetDependencies[*ti]);
+    }
+  }
+
   // Create a map from local generator to the complete set of targets
   // it builds by default.
   this->FillLocalGeneratorToTargetMap();
@@ -1718,144 +1731,7 @@ void cmGlobalGenerator::AppendDirectoryForConfig(const char*, const char*,
 cmGlobalGenerator::TargetDependSet &
 cmGlobalGenerator::GetTargetDirectDepends(cmTarget & target)
 {
-  // Clarify the role of the input target.
-  cmTarget * depender = &target;
-
-  // if the depends are already in the map then return
-  TargetDependMap::iterator tgtI =
-    this->TargetDependencies.find(depender);
-  if(tgtI != this->TargetDependencies.end())
-    {
-    return tgtI->second;
-    }
-
-  // Create an entry for this depender.
-  TargetDependSet& depender_depends = this->TargetDependencies[depender];
-
-  // Keep track of dependencies already listed.
-  std::set<cmStdString> emitted;
-
-  // A target should not depend on itself.
-  emitted.insert(depender->GetName());
-
-  // Loop over all targets linked directly.
-  cmTarget::LinkLibraryVectorType const& tlibs =
-    target.GetOriginalLinkLibraries();
-  for(cmTarget::LinkLibraryVectorType::const_iterator lib = tlibs.begin();
-      lib != tlibs.end(); ++lib)
-    {
-    // Don't emit the same library twice for this target.
-    if(emitted.insert(lib->first).second)
-      {
-      this->ConsiderTargetDepends(depender, depender_depends,
-                                  lib->first.c_str());
-      }
-    }
-
-  // Loop over all utility dependencies.
-  std::set<cmStdString> const& tutils = target.GetUtilities();
-  for(std::set<cmStdString>::const_iterator util = tutils.begin();
-      util != tutils.end(); ++util)
-    {
-    // Don't emit the same utility twice for this target.
-    if(emitted.insert(*util).second)
-      {
-      this->ConsiderTargetDepends(depender, depender_depends,
-                                  util->c_str());
-      }
-    }
-
-  return depender_depends;
-}
-
-//----------------------------------------------------------------------------
-bool
-cmGlobalGenerator::ConsiderTargetDepends(cmTarget * depender,
-                                         TargetDependSet& depender_depends,
-                                         const char* dependee_name)
-{
-  // Check the target's makefile first.
-  cmTarget * dependee =
-    depender->GetMakefile()->FindTarget(dependee_name);
-
-  // Then search globally.
-  if(!dependee)
-    {
-    dependee = this->FindTarget(0, dependee_name);
-    }
-
-  // If not found then skip then the dependee.
-  if(!dependee)
-    {
-    return false;
-    }
-
-  // Check whether the depender is among the dependee's dependencies.
-  std::vector<cmTarget *> steps;
-  if(this->FindDependency(depender, dependee, steps))
-    {
-    // This creates a cyclic dependency.
-    bool isStatic = depender->GetType() == cmTarget::STATIC_LIBRARY;
-    cmOStringStream e;
-    e << "Cyclic dependency among targets:\n"
-      << "  " << depender->GetName() << "\n";
-    for(unsigned int i = static_cast<unsigned int>(steps.size());
-        i > 0; --i)
-      {
-      cmTarget * step = steps[i-1];
-      e << "    -> " << step->GetName() << "\n";
-      isStatic = isStatic && step->GetType() == cmTarget::STATIC_LIBRARY;
-      }
-    if(isStatic)
-      {
-      e << "  All targets are STATIC libraries.\n";
-      e << "  Dropping "
-        << depender->GetName() << " -> " << dependee->GetName()
-        << " to resolve.\n";
-      cmSystemTools::Message(e.str().c_str());
-      }
-    else
-      {
-      e << "  At least one target is not a STATIC library.\n";
-      cmSystemTools::Error(e.str().c_str());
-      }
-    return false;
-    }
-  else
-    {
-    // This does not create a cyclic dependency.
-    depender_depends.insert(dependee);
-    return true;
-    }
-}
-
-//----------------------------------------------------------------------------
-bool
-cmGlobalGenerator
-::FindDependency(cmTarget * goal, cmTarget * current,
-                 std::vector<cmTarget*>& steps)
-{
-  if(current == goal)
-    {
-    steps.push_back(current);
-    return true;
-    }
-  TargetDependMap::iterator i = this->TargetDependencies.find(current);
-  if(i == this->TargetDependencies.end())
-    {
-    return false;
-    }
-  TargetDependSet & depends = i->second;
-  for(TargetDependSet::iterator j = depends.begin();
-      j != depends.end(); ++j)
-    {
-    if(this->FindDependency(goal, *j, steps))
-      {
-      steps.push_back(current);
-      return true;
-      }
-    }
-  return false;
+  return this->TargetDependencies[&target];
 }
 
 void cmGlobalGenerator::AddTarget(cmTargets::value_type &v)
diff --git a/Source/cmGlobalGenerator.h b/Source/cmGlobalGenerator.h
index bd5a8ee..9c13a4e 100644
--- a/Source/cmGlobalGenerator.h
+++ b/Source/cmGlobalGenerator.h
@@ -313,12 +313,7 @@ private:
   // track files replaced during a Generate
   std::vector<std::string> FilesReplacedDuringGenerate;
 
-  // Track inter-target dependencies.
-  bool ConsiderTargetDepends(cmTarget * depender,
-                             TargetDependSet& depender_depends,
-                             const char* dependee_name);
-  bool FindDependency(cmTarget * goal, cmTarget * current,
-                      std::vector<cmTarget *>& steps);
+  // Store computed inter-target dependencies.
   typedef std::map<cmTarget *, TargetDependSet> TargetDependMap;
   TargetDependMap TargetDependencies;
 
diff --git a/Source/cmake.cxx b/Source/cmake.cxx
index 271a6b6..c2714d0 100644
--- a/Source/cmake.cxx
+++ b/Source/cmake.cxx
@@ -3296,6 +3296,13 @@ void cmake::DefineProperties(cmake *cm)
     "Internal property",
     "Used to detect compiler changes, Do not set.");
 
+  cm->DefineProperty(
+    "GLOBAL_DEPENDS_DEBUG_MODE", cmProperty::GLOBAL,
+    "Enable global target dependency graph debug mode.",
+    "CMake automatically analyzes the global inter-target dependency graph "
+    "at the beginning of native build system generation.  "
+    "This property causes it to display details of its analysis to stderr.");
+
   // ================================================================
   // define variables as well
   // ================================================================
diff --git a/bootstrap b/bootstrap
index 6de4a02..4880ace 100755
--- a/bootstrap
+++ b/bootstrap
@@ -170,6 +170,7 @@ CMAKE_CXX_SOURCES="\
   cmComputeLinkDepends \
   cmComputeLinkInformation \
   cmOrderRuntimeDirectories \
+  cmComputeTargetDepends \
 "
 
 if ${cmake_system_mingw}; then