[ADT][NFC] SCCIterator: Change hasLoop() to hasCycle()

[baziotis]

Summary

hasLoop() seems to be a misleading name in that the user may think that it checks if the SCC contains a loop that satisfies
the criteria of the loop terminology (i.e. a normal loop).

[efriedma]

Seems fine.

[baziotis]

In D74801#1881679, @efriedma wrote:

Seems fine.

Great, thanks and to @jdoerfert!
Any way I can find the correct reviewers next time?

[lebedev.ri]

While i certainly agree that it's kinda confusing, i'm not really sure this is conceptually correct change.
https://en.wikipedia.org/wiki/Loop_(graph_theory)

In graph theory, a loop (also called a self-loop or a "buckle") is an edge that connects a vertex to itself. A simple graph contains no loops.

which is exactly the case here.

https://en.wikipedia.org/wiki/Cycle_(graph_theory)
seems more generic than that.

[lebedev.ri]

llvm/tools/opt/PrintSCC.cpp

82–83

err, i was specifically talking about this

104–105

And this

[baziotis]

In D74801#1881693, @lebedev.ri wrote:

While i certainly agree that it's kinda confusing, i'm not really sure this is conceptually correct change.
https://en.wikipedia.org/wiki/Loop_(graph_theory)

In graph theory, a loop (also called a self-loop or a "buckle") is an edge that connects a vertex to itself. A simple graph contains no loops.

which is exactly the case here.

https://en.wikipedia.org/wiki/Cycle_(graph_theory)
seems more generic than that.

Yes, I agree, but it was the closest word I could find that is not "loop" but still gets the point across. I mean technically maybe the better term would be "hasALoopButNotNecessarilyANormalLoop()" but well... :P
In any case, that was an experience of mine as a newcomer. If you think it's not worth it, so be it. :)

llvm/tools/opt/PrintSCC.cpp

82–83

Maybe we can keep the "Has self-loop here".

[lebedev.ri]

llvm/tools/opt/PrintSCC.cpp

82–83

Then this would look good to me

[baziotis]

llvm/tools/opt/PrintSCC.cpp

82–83

Ok, uploading new diff in a bit.

[baziotis]

Self-cycle to self-loop

[lebedev.ri]

lg

[baziotis]

In D74801#1882155, @lebedev.ri wrote:

lg

Great! Just a note: I don't have commit access.

[baziotis]

Ping :)

[lattner]

Seems fine to me.

[baziotis]

In D74801#1897267, @lattner wrote:

Seems fine to me.

Thank you! Please note that I don't have commit access.

[lattner]

I'd be happy to help fix that problem. Please take a look at the llvm developer policy. :-)

[baziotis]

In D74801#1898660, @lattner wrote:

I'd be happy to help fix that problem. Please take a look at the llvm developer policy. :-)

Oh thanks, I thought I had to submit way more patches.

[baziotis]

I committed that (https://reviews.llvm.org/rG21390eab4c05e0ed7e7d13ada9e85f62b87ea484) but as it seems, I should have added the differential division in the commit message. I'll try the next commit to be better.

[Meinersbur]

In D74801#1899999, @baziotis wrote:

I committed that (https://reviews.llvm.org/rG21390eab4c05e0ed7e7d13ada9e85f62b87ea484) but as it seems, I should have added the differential division in the commit message. I'll try the next commit to be better.

If that happens, this Phabricator review does not close automatically. It has to be closed manually using the "Add Action..." dropdown.

[baziotis]

If that happens, this Phabricator review does not close automatically. It has to be closed manually using the "Add Action..." dropdown.

Noted.

clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp

void NoRecursionCheck::check(const MatchFinder::MatchResult &Result) {
   CallGraph CG;
   CG.addToCallGraph(const_cast<TranslationUnitDecl *>(TU));
 
   // Look for cycles in call graph,
   // by looking for Strongly Connected Comonents (SCC's)
   for (llvm::scc_iterator<CallGraph *> SCCI = llvm::scc_begin(&CG),
                                        SCCE = llvm::scc_end(&CG);
        SCCI != SCCE; ++SCCI) {
-    if (!SCCI.hasLoop()) // We only care about cycles, not standalone nodes.
+    if (!SCCI.hasCycle()) // We only care about cycles, not standalone nodes.
       continue;
     handleSCC(*SCCI);
   }
 }
 
 } // namespace misc
 } // namespace tidy
 } // namespace clang

llvm/include/llvm/ADT/SCCIterator.h

scc_iterator &operator++() {
     return *this;
   }
 
   reference operator*() const {
     assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
     return CurrentSCC;
   }
 
-  /// Test if the current SCC has a loop.
+  /// Test if the current SCC has a cycle.
   ///
   /// If the SCC has more than one node, this is trivially true.  If not, it may
-  /// still contain a loop if the node has an edge back to itself.
-  bool hasLoop() const;
+  /// still contain a cycle if the node has an edge back to itself.
+  bool hasCycle() const;
 
   /// This informs the \c scc_iterator that the specified \c Old node
   /// has been deleted, and \c New is to be used in its place.
   void ReplaceNode(NodeRef Old, NodeRef New) {
     assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");
     // Do the assignment in two steps, in case 'New' is not yet in the map, and
     // inserting it causes the map to grow.
     auto tempVal = nodeVisitNumbers[Old];
do {
       SCCNodeStack.pop_back();
       nodeVisitNumbers[CurrentSCC.back()] = ~0U;
     } while (CurrentSCC.back() != visitingN);
     return;
   }
 }
 
 template <class GraphT, class GT>
-bool scc_iterator<GraphT, GT>::hasLoop() const {
+bool scc_iterator<GraphT, GT>::hasCycle() const {
     assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
     if (CurrentSCC.size() > 1)
       return true;
     NodeRef N = CurrentSCC.front();
     for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
          ++CI)
       if (*CI == N)
         return true;

llvm/lib/IR/ModuleSummaryIndex.cpp

for (scc_iterator<ModuleSummaryIndex *> I =
        !I.isAtEnd(); ++I) {
     O << "SCC (" << utostr(I->size()) << " node" << (I->size() == 1 ? "" : "s")
       << ") {\n";
     for (const ValueInfo &V : *I) {
       FunctionSummary *F = nullptr;
       if (V.getSummaryList().size())
         F = cast<FunctionSummary>(V.getSummaryList().front().get());
       O << " " << (F == nullptr ? "External" : "") << " " << utostr(V.getGUID())
-        << (I.hasLoop() ? " (has loop)" : "") << "\n";
+        << (I.hasCycle() ? " (has cycle)" : "") << "\n";
     }
     O << "}\n";
   }
 }
 
 namespace {
 struct Attributes {
   void add(const Twine &Name, const Twine &Value,

llvm/tools/opt/PrintSCC.cpp

bool CFGSCC::runOnFunction(Function &F) {
   unsigned sccNum = 0;
   errs() << "SCCs for Function " << F.getName() << " in PostOrder:";
   for (scc_iterator<Function*> SCCI = scc_begin(&F); !SCCI.isAtEnd(); ++SCCI) {
     const std::vector<BasicBlock *> &nextSCC = *SCCI;
     errs() << "\nSCC #" << ++sccNum << " : ";
     for (std::vector<BasicBlock*>::const_iterator I = nextSCC.begin(),
            E = nextSCC.end(); I != E; ++I)
       errs() << (*I)->getName() << ", ";
-    if (nextSCC.size() == 1 && SCCI.hasLoop())
-      errs() << " (Has self-loop).";
+    if (nextSCC.size() == 1 && SCCI.hasCycle())
+      errs() << " (Has self-cycle).";
   }
   errs() << "\n";
 
   return true;
 }
 
 
 // run - Print out SCCs in the call graph for the specified module.
 bool CallGraphSCC::runOnModule(Module &M) {
   CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
   unsigned sccNum = 0;
   errs() << "SCCs for the program in PostOrder:";
   for (scc_iterator<CallGraph*> SCCI = scc_begin(&CG); !SCCI.isAtEnd();
        ++SCCI) {
     const std::vector<CallGraphNode*> &nextSCC = *SCCI;
     errs() << "\nSCC #" << ++sccNum << " : ";
     for (std::vector<CallGraphNode*>::const_iterator I = nextSCC.begin(),
            E = nextSCC.end(); I != E; ++I)
       errs() << ((*I)->getFunction() ? (*I)->getFunction()->getName()
                                      : "external node") << ", ";
-    if (nextSCC.size() == 1 && SCCI.hasLoop())
-      errs() << " (Has self-loop).";
+    if (nextSCC.size() == 1 && SCCI.hasCycle())
+      errs() << " (Has self-cycle).";
   }
   errs() << "\n";
 
   return true;
 }