[NFC][SuffixTree] Add debug log and some comments for suffix tree

[dongAxis1944]

Summary

This is an NFC change for the suffix tree.

We use MachineOutliner to reduce our binary size recently, so I just look into the code of the suffix tree.
But I think it is hard to debug, so I use this NFC change to enhance this.
The log just like:

Node[Root#0]: StartIdx=4294967295, EndIdx=4294967295, Childrens = [3,2,1,]
Node[Leaf#1]: StartIdx=2, EndIdx=5, Childrens = []
Node[Leaf#2]: StartIdx=0, EndIdx=5, Childrens = []
Node[Leaf#3]: StartIdx=1, EndIdx=5, Childrens = []

BTW, I found the suffix tree does not have a default terminator in the array.

[MaskRay]

This may greatly increase memory usage. You can use #ifndef NDEBUG to not affect production usage.

BTW, I found the suffix tree does not have a default terminator in the array.

A (generalized) suffix tree does not necessarily need the '\0' terminal character as some textbooks require. See https://codeforces.com/blog/entry/16780

[dongAxis1944]

address comment

[dongAxis1944]

In D115855#3197020, @MaskRay wrote:

This may greatly increase memory usage. You can use #ifndef NDEBUG to not affect production usage.

BTW, I found the suffix tree does not have a default terminator in the array.

A (generalized) suffix tree does not necessarily need the '\0' terminal character as some textbooks require. See https://codeforces.com/blog/entry/16780

thanks, I will check the page you send. But considering the ut in https://github.com/llvm/llvm-project/blob/main/llvm/unittests/Support/SuffixTreeTest.cpp#L108, the developer needs to set the unique terminator by hand or they might get the wrong result.

[paquette]

llvm/include/llvm/Support/SuffixTree.h

150

More concise:

The last element of Str is expected to be unique.

372

May be worth printing "<null>" or something here, if this is for debugging purposes.

374

Maybe it would make sense to use SmallString?

https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallstring-h

375

Omit braces on this and the else if below.

https://llvm.org/docs/CodingStandards.html#don-t-use-braces-on-simple-single-statement-bodies-of-if-else-loop-statements

383

A little easier to read with a space?

384

More consistent spacing?

385

Grammar

387

Adding space since it's a little easier to read.

Also can we omit the extra ", " at the end?

E.g.

Children = [1, 2, 3]

rather than

Children = [1, 2, 3,]

llvm/lib/Support/SuffixTree.cpp

79

Comment explaining why this is here?

llvm/include/llvm/Support/SuffixTree.h

 #ifndef LLVM_SUPPORT_SUFFIXTREE_H
 #define LLVM_SUPPORT_SUFFIXTREE_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Support/Allocator.h"
 #include <vector>
 
+#ifndef NDEBUG
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#endif
+
 namespace llvm {
 
 /// Represents an undefined index in the suffix tree.
 const unsigned EmptyIdx = -1;
 
 /// A node in a suffix tree which represents a substring or suffix.
 ///
 /// Each node has either no children or at least two children, with the root
 /// being a exception in the empty tree.
 ///
 /// Children are represented as a map between unsigned integers and nodes. If
 /// a node N has a child M on unsigned integer k, then the mapping represented
 /// by N is a proper prefix of the mapping represented by M. Note that this,
 /// although similar to a trie is somewhat different: each node stores a full
 /// substring of the full mapping rather than a single character state.
 ///
 /// Each internal node contains a pointer to the internal node representing
 /// the same string, but with the first character chopped off. This is stored
 /// in \p Link. Each leaf node stores the start index of its respective
 /// suffix in \p SuffixIdx.
 struct SuffixTreeNode {
+  // The ID of the node
+#ifndef NDEBUG
+  uint64_t ID = 0;
+#endif
 
   /// The children of this node.
   ///
   /// A child existing on an unsigned integer implies that from the mapping
   /// represented by the current node, there is a way to reach another
   /// mapping by tacking that character on the end of the current string.
   llvm::DenseMap<unsigned, SuffixTreeNode *> Children;
 

 /// suffix tree construction. Ukkonen's algorithm is explained in more detail
 /// in the paper by Esko Ukkonen "On-line construction of suffix trees. The
 /// paper is available at
 ///
 /// https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
 class SuffixTree {
 public:
   /// Each element is an integer representing an instruction in the module.
+  ///
+  /// If the developer want to build a valid suffix tree, the last number of
+  /// array should be unique
   llvm::ArrayRef<unsigned> Str;
 
   /// A repeated substring in the tree.
   struct RepeatedSubstring {
     /// The length of the string.
     unsigned Length;
 
     /// The start indices of each occurrence.
private:
   unsigned extend(unsigned EndIdx, unsigned SuffixesToAdd);
 
 public:
   /// Construct a suffix tree from a sequence of unsigned integers.
   ///
   /// \param Str The string to construct the suffix tree for.
   SuffixTree(const std::vector<unsigned> &Str);
 
+  const SuffixTreeNode *getRoot() const { return Root; }
+
   /// Iterator for finding all repeated substrings in the suffix tree.
   struct RepeatedSubstringIterator {
   private:
     /// The current node we're visiting.
     SuffixTreeNode *N = nullptr;
 
     /// The repeated substring associated with this node.
     RepeatedSubstring RS;
public:
     }
   };
 
   typedef RepeatedSubstringIterator iterator;
   iterator begin() { return iterator(Root); }
   iterator end() { return iterator(nullptr); }
 };
 
+#ifndef NDEBUG
+
+inline raw_ostream &operator<<(raw_ostream &OS, const SuffixTree &Tree) {
+  std::vector<const SuffixTreeNode *> Worklist;
+  Worklist.push_back(Tree.getRoot());
+  while (!Worklist.empty()) {
+    const SuffixTreeNode *Node = Worklist.back();
+    Worklist.pop_back();
+
+    if (!Node)
+      continue;
+
+    std::string NodeType = "Internal";
+    if (Node->isRoot()) {
+      NodeType = "Root";
+    } else if (Node->isLeaf()) {
+      NodeType = "Leaf";
+    }
+
+    std::string EndIdxValue =
+        Node->EndIdx ? std::to_string(*Node->EndIdx) : "$";
+    OS << "Node[" << NodeType << "#" << std::to_string(Node->ID)
+       << "]: StartIdx=" << Node->StartIdx << ", EndIdx=" << EndIdxValue;
+    OS << ", Childrens = [";
+    for (auto &ChildPair : Node->Children) {
+      OS << ChildPair.second->ID << ",";
+      Worklist.push_back(ChildPair.second);
+    }
+    OS << "]\n";
+  }
+  return OS;
+}
+
+#endif
+
 } // namespace llvm
 
 #endif // LLVM_SUPPORT_SUFFIXTREE_H

llvm/lib/CodeGen/MachineOutliner.cpp

void MachineOutliner::emitOutlinedFunctionRemark(OutlinedFunction &OF) {
 
   MORE.emit(R);
 }
 
 void MachineOutliner::findCandidates(
     InstructionMapper &Mapper, std::vector<OutlinedFunction> &FunctionList) {
   FunctionList.clear();
   SuffixTree ST(Mapper.UnsignedVec);
+#ifndef NDEBUG
+  LLVM_DEBUG(dbgs() << "Dumping SuffixTree:\n" << ST << "\n");
+#endif
 
   // First, find all of the repeated substrings in the tree of minimum length
   // 2.
   std::vector<Candidate> CandidatesForRepeatedSeq;
   for (const SuffixTree::RepeatedSubstring &RS : ST) {
     CandidatesForRepeatedSeq.clear();
     unsigned StringLen = RS.Length;
     for (const unsigned &StartIdx : RS.StartIndices) {

llvm/lib/Support/SuffixTree.cpp

 void SuffixTree::setSuffixIndices() {
   // List of nodes we need to visit along with the current length of the
   // string.
   std::vector<std::pair<SuffixTreeNode *, unsigned>> ToVisit;
 
   // Current node being visited.
   SuffixTreeNode *CurrNode = Root;
 
+#ifndef NDEBUG
+  uint64_t CurID = 0;
+#endif
   // Sum of the lengths of the nodes down the path to the current one.
   unsigned CurrNodeLen = 0;
   ToVisit.push_back({CurrNode, CurrNodeLen});
   while (!ToVisit.empty()) {
     std::tie(CurrNode, CurrNodeLen) = ToVisit.back();
     ToVisit.pop_back();
     CurrNode->ConcatLen = CurrNodeLen;
+#ifndef NDEBUG
+    CurrNode->ID = CurID++;
+#endif
     for (auto &ChildPair : CurrNode->Children) {
       assert(ChildPair.second && "Node had a null child!");
       ToVisit.push_back(
           {ChildPair.second, CurrNodeLen + ChildPair.second->size()});
     }
 
     // No children, so we are at the end of the string.
     if (CurrNode->Children.size() == 0 && !CurrNode->isRoot())