[LayoutPass] Add a method to check the followon graph structure.

Found that having a method to check the strucutre of the followon graph makes
it easy to debug file readers. The method checks if there's no wrong edge in
followOnNexts and followOnRoots. It is called only when debuggging is enabled
for LayoutPass.

Reviewers: shankarke

CC: llvm-commits

Differential Revision: http://llvm-reviews.chandlerc.com/D922

llvm-svn: 183553

3 files changed, 144 insertions, 17 deletions

diff --git a/lld/include/lld/Passes/LayoutPass.h b/lld/include/lld/Passes/LayoutPass.h
index b1949f4238e..b6190052f08 100644
--- a/lld/include/lld/Passes/LayoutPass.h
+++ b/lld/include/lld/Passes/LayoutPass.h
@@ -65,6 +65,11 @@ private:
   // Build a map of Atoms to ordinals for sorting the atoms
   void buildOrdinalOverrideMap(MutableFile::DefinedAtomRange &range);
 
+#ifndef NDEBUG
+  // Check if the follow-on graph is a correct structure. For debugging only.
+  void checkFollowonChain(MutableFile::DefinedAtomRange &range);
+#endif
+
   typedef llvm::DenseMap<const DefinedAtom *, const DefinedAtom *> AtomToAtomT;
   typedef llvm::DenseMap<const DefinedAtom *, uint64_t> AtomToOrdinalT;
 
diff --git a/lld/lib/Passes/LayoutPass.cpp b/lld/lib/Passes/LayoutPass.cpp
index b973bbbedbe..e060f9485db 100644
--- a/lld/lib/Passes/LayoutPass.cpp
+++ b/lld/lib/Passes/LayoutPass.cpp
@@ -10,8 +10,12 @@
 
 #define DEBUG_TYPE "LayoutPass"
 
+#include <set>
+
 #include "lld/Passes/LayoutPass.h"
 #include "lld/Core/Instrumentation.h"
+
+#include "llvm/ADT/Twine.h"
 #include "llvm/Support/Debug.h"
 
 using namespace lld;
@@ -395,6 +399,116 @@ void LayoutPass::buildOrdinalOverrideMap(MutableFile::DefinedAtomRange &range) {
   }
 }
 
+// Helper functions to check follow-on graph.
+#ifndef NDEBUG
+namespace {
+typedef llvm::DenseMap<const DefinedAtom *, const DefinedAtom *> AtomToAtomT;
+
+std::string atomToDebugString(const Atom *atom) {
+  const DefinedAtom *definedAtom = llvm::dyn_cast<DefinedAtom>(atom);
+  std::string str;
+  llvm::raw_string_ostream s(str);
+  if (definedAtom->name().empty())
+    s << "<anonymous " << definedAtom << ">";
+  else
+    s << definedAtom->name();
+  s << " in ";
+  if (definedAtom->customSectionName().empty())
+    s << "<anonymous>";
+  else
+    s << definedAtom->customSectionName();
+  s.flush();
+  return str;
+}
+
+void showCycleDetectedError(AtomToAtomT &followOnNexts,
+                            const DefinedAtom *atom) {
+  const DefinedAtom *start = atom;
+  llvm::dbgs() << "There's a cycle in a follow-on chain!\n";
+  do {
+    llvm::dbgs() << "  " << atomToDebugString(atom) << "\n";
+    for (const Reference *ref : *atom) {
+      llvm::dbgs() << "    " << ref->kindToString()
+                   << ": " << atomToDebugString(ref->target()) << "\n";
+    }
+    atom = followOnNexts[atom];
+  } while (atom != start);
+  llvm_unreachable("Cycle detected");
+}
+
+/// Exit if there's a cycle in a followon chain reachable from the
+/// given root atom. Uses the tortoise and hare algorithm to detect a
+/// cycle.
+void checkNoCycleInFollowonChain(AtomToAtomT &followOnNexts,
+                                 const DefinedAtom *root) {
+  const DefinedAtom *tortoise = root;
+  const DefinedAtom *hare = followOnNexts[root];
+  while (true) {
+    if (!tortoise || !hare)
+      return;
+    if (tortoise == hare)
+      showCycleDetectedError(followOnNexts, tortoise);
+    tortoise = followOnNexts[tortoise];
+    hare = followOnNexts[followOnNexts[hare]];
+  }
+}
+
+void checkReachabilityFromRoot(AtomToAtomT &followOnRoots,
+                               const DefinedAtom *atom) {
+  if (!atom) return;
+  auto i = followOnRoots.find(atom);
+  if (i == followOnRoots.end()) {
+    Twine msg(Twine("Atom <") + atomToDebugString(atom)
+              + "> has no follow-on root!");
+    llvm_unreachable(msg.str().c_str());
+  }
+  const DefinedAtom *ap = i->second;
+  while (true) {
+    const DefinedAtom *next = followOnRoots[ap];
+    if (!next) {
+      Twine msg(Twine("Atom <" + atomToDebugString(atom)
+                      + "> is not reachable from its root!"));
+      llvm_unreachable(msg.str().c_str());
+    }
+    if (next == ap)
+      return;
+    ap = next;
+  }
+}
+
+void printDefinedAtoms(const MutableFile::DefinedAtomRange &atomRange) {
+  for (const DefinedAtom *atom : atomRange) {
+    llvm::dbgs() << "  file=" << atom->file().path()
+                 << ", name=" << atom->name()
+                 << ", size=" << atom->size()
+                 << ", type=" << atom->contentType()
+                 << ", ordinal=" << atom->ordinal()
+                 << "\n";
+  }
+}
+} // end anonymous namespace
+
+/// Verify that the followon chain is sane. Should not be called in
+/// release binary.
+void LayoutPass::checkFollowonChain(MutableFile::DefinedAtomRange &range) {
+  ScopedTask task(getDefaultDomain(), "LayoutPass::checkFollowonChain");
+
+  // Verify that there's no cycle in follow-on chain.
+  std::set<const DefinedAtom *> roots;
+  for (const auto &ai : _followOnRoots)
+    roots.insert(ai.second);
+  for (const DefinedAtom *root : roots)
+    checkNoCycleInFollowonChain(_followOnNexts, root);
+
+  // Verify that all the atoms in followOnNexts have references to
+  // their roots.
+  for (const auto &ai : _followOnNexts) {
+    checkReachabilityFromRoot(_followOnRoots, ai.first);
+    checkReachabilityFromRoot(_followOnRoots, ai.second);
+  }
+}
+#endif  // #ifndef NDEBUG
+
 /// Perform the actual pass
 void LayoutPass::perform(MutableFile &mergedFile) {
   ScopedTask task(getDefaultDomain(), "LayoutPass");
@@ -409,19 +523,15 @@ void LayoutPass::perform(MutableFile &mergedFile) {
   // Build preceded by tables
   buildPrecededByTable(atomRange);
 
+  // Check the structure of followon graph if running in debug mode.
+  DEBUG(checkFollowonChain(atomRange));
+
   // Build override maps
   buildOrdinalOverrideMap(atomRange);
 
   DEBUG({
     llvm::dbgs() << "unsorted atoms:\n";
-    for (const DefinedAtom *atom : atomRange) {
-      llvm::dbgs() << "  file=" << atom->file().path()
-                   << ", name=" << atom->name()
-                   << ", size=" << atom->size()
-                   << ", type=" << atom->contentType()
-                   << ", ordinal=" << atom->ordinal()
-                   << "\n";
-    }
+    printDefinedAtoms(atomRange);
   });
 
   // sort the atoms
@@ -429,14 +539,6 @@ void LayoutPass::perform(MutableFile &mergedFile) {
 
   DEBUG({
     llvm::dbgs() << "sorted atoms:\n";
-    for (const DefinedAtom *atom : atomRange) {
-      llvm::dbgs() << "  file=" << atom->file().path()
-                   << ", name=" << atom->name()
-                   << ", size=" << atom->size()
-                   << ", type=" << atom->contentType()
-                   << ", ordinal=" << atom->ordinal()
-                   << "\n";
-    }
+    printDefinedAtoms(atomRange);
   });
-
 }
diff --git a/lld/test/layout-error-test.objtxt b/lld/test/layout-error-test.objtxt
new file mode 100644
index 00000000000..d0ae58752b3
--- /dev/null
+++ b/lld/test/layout-error-test.objtxt
@@ -0,0 +1,20 @@
+# RUN: lld -core --add-pass layout -mllvm -debug-only=LayoutPass %s 2>&1 \
+# RUN:   | FileCheck %s -check-prefix=CHECK
+
+---
+defined-atoms:
+  - name:            fn
+    scope:           global
+    references:
+      - kind:            layout-before
+        offset:          0
+        target:          fn
+      - kind:            in-group
+        offset:          0
+        target:          fn
+...
+
+# CHECK: There's a cycle in a follow-on chain!
+# CHECK:   fn
+# CHECK:     layout-before: fn
+# CHECK:     in-group: fn