[SCCIterator] Check if a SCC is a natural loop.

[baziotis]

Summary

• Get LoopInfo for the function.
• Given an SCC, take one random block of it. Then, call getLoopFor() with

that block.
If we don't get a loop back, then this SCC is definitely not a loop.

• Otherwise, we compare the size of the SCC with that of the loop and there

are 3 cases:

• They're equal: this SCC is a loop.
• The SCC is smaller: This SCC is not a loop because getLoopFor() gives

the innermost loop. So, if this is smaller, it is an SCC inside a loop.

• The SCC is bigger: In that case, we can't decide since let's say the

SCC has blocks A, B, C. And the loop has blocks A, B. But blocks A, B, C
might also make a loop. However, since getLoopFor() gives us the
innermost loop, it will give us A, B. So, in that case, use
getParentLoop() repeatedly and repeat the procedure for the parent loops.

[baziotis]

First of all, do you think this is a useful addition to the SCC interface? We recently needed it in a patch.

Second, I currently don't know how to get LoopInfo. There's also a problem that it is not sure that we'll be able
to get LoopInfo and in that case, what do we return ? (i.e. with this interface there's no way to signify an error).

Third, do you think there's a better way ? I was thinking that maybe there was a
more straightforward way by trying to verify whether the criteria for a natural
loop are satisfied (i.e. there's a block that dominates all the other
blocks).

[lebedev.ri]

I'm not sure this fits here, this is very specific to GraphT=Function*, since LoopInfo::getLoopFor() is only defined for (function) basic blocks.

[Meinersbur]

"ADT" stands for "Abstract Data Type". This use case is rather concrete. Unfortunately, LoopInfo ignores non-natural loops, but it would be the place for this.

IIUC, there will be an SCC only for an topmost loop including all its nested loop. Its not possible using SCCIterator to match a non-topmost loops.

[baziotis]

In D75024#1888366, @lebedev.ri wrote:

I'm not sure this fits here, this is very specific to GraphT=Function*, since LoopInfo::getLoopFor() is only defined for (function) basic blocks.

Yes, that's a problem. Where else could it be placed?
Ideally, I would like to have something that does not depend on LoopInfo, but I don't. :/

[baziotis]

In D75024#1888381, @Meinersbur wrote:

"ADT" stands for "Abstract Data Type". This use case is rather concrete. Unfortunately, LoopInfo ignores non-natural loops, but it would be the place for this.

So, a function that gets an SCC and decides if it's a loop, alright.
Edit: Meaning, member function of LoopInfo.

IIUC, there will be an SCC only for an topmost loop including all its nested loop. Its not possible using SCCIterator to match a non-topmost loops.

Hmm, that's bizarre. Won't the SCCIterator go through all the SCCs? That is, let's say we have a topmost loop with blocks: A, B, C. And blocks B, C also form a loop.
Won't we get a separate SCC for A, B, C and B, C?

[Meinersbur]

In D75024#1888383, @baziotis wrote:

Hmm, that's bizarre. Won't the SCCIterator go through all the SCCs? That is, let's say we have a topmost loop with blocks: A, B, C. And blocks B, C also form a loop.
Won't we get a separate SCC for A, B, C and B, C?

It uses Tarjan's algorithm which only returns maximal connected subgraphs. Anything else would be infeasible. Think of a complete graph, every subset of nodes would by strongly connected (but not maximal), hence return an exponential number of strongly connected subgraphs. Only the entire complete graph is maximal and considered a component.

[baziotis]

In D75024#1888385, @Meinersbur wrote:

In D75024#1888383, @baziotis wrote:

Hmm, that's bizarre. Won't the SCCIterator go through all the SCCs? That is, let's say we have a topmost loop with blocks: A, B, C. And blocks B, C also form a loop.
Won't we get a separate SCC for A, B, C and B, C?

It uses Tarjan's algorithm which only returns maximal connected subgraphs. Anything else would be infeasible. Think of a complete graph, every subset of nodes would by strongly connected (but not maximal), hence return an exponential number of strongly connected subgraphs. Only the entire complete graph is maximal and considered a component.

Oh, that's quite bad. Big mistake on my part. I knew it was Tarjan and actually I had implemented but 3-4 years ago. Somehow, I remembered it gets every sub-graph. I just saw the algorithm again and this
makes both this patch wrong and the other.
Thank you very much Michael!

Edit: Actually, it probably doesn't make this patch wrong, given that I do it in LoopInfo but well...

[baziotis]

I think that with the news about SCCIterator, the implementation will be something like that:

bool isSCCNaturalLoop(scc_iterator<Function *> SCCIt) const {
  Loop *L = getLoopFor((*SCCIt).front());
  return L != nullptr;
}

This is basically a hack and I don't know if it makes sense to put it as part of LoopInfo. It doesn't do anything internal to LoopInfo that the user couldn't know.
What do you think?

[baziotis]

In D75024#1892194, @baziotis wrote:

I think that with the news about SCCIterator, the implementation will be something like that:

bool isSCCNaturalLoop(scc_iterator<Function *> SCCIt) const {
  Loop *L = getLoopFor((*SCCIt).front());
  return L != nullptr;
}

This is basically a hack and I don't know if it makes sense to put it as part of LoopInfo. It doesn't do anything internal to LoopInfo that the user couldn't know.
What do you think?

Abandoning this as I personally don't see any value :/

llvm/include/llvm/ADT/SCCIterator.h

public:
   }
 
   /// Test if the current SCC has a loop.
   ///
   /// 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;
 
+  /// Test if the current SCC is a natural loop.
+  bool isNaturalLoop() 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];
     nodeVisitNumbers[New] = tempVal;
bool scc_iterator<GraphT, GT>::hasLoop() const {
     NodeRef N = CurrentSCC.front();
     for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
          ++CI)
       if (*CI == N)
         return true;
     return false;
   }
 
+template <class GraphT, class GT>
+bool scc_iterator<GraphT, GT>::isNaturalLoop() const {
+  assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
+
+  // TODO: Somehow get LoopInfo analysis for this graph into a variable LI.
+
+  if (!hasLoop())
+    return false;
+  Loop *L = LI->getLoopFor(CurrentSCC.front());
+  // If any random block in this SCC does not belong to a loop,
+  // then this SCC is definitely not a loop.
+  if (!L)
+    return false;
+  // L is the _innermost_ loop that has a common block with the SCC.
+  // Since a loop is always an SCC, if their number of blocks
+  // are equal, the SCC is a loop - specifically, L. Otherwise, there are 2 cases:
+  // - If the SCC has less blocks, then it is definitely not a loop.
+  // - If it has more, then we can't decide since the SCC can be a parent loop of L.
+  //   So, we perform the same test for the parent of L.
+  do {
+    if (L->getNumBlocks() == CurrentSCC.size())
+      return true;
+    if (CurrentSCC.size() < L->getNumBlocks())
+      return false;
+    L = L->getParentLoop();
+  } while (L);
+  // L is nullptr, so we found no loop that matches exactly
+  // the number of blocks of the SCC and so the SCC is not a loop.
+  return false;
+}
+
 /// Construct the begin iterator for a deduced graph type T.
 template <class T> scc_iterator<T> scc_begin(const T &G) {
   return scc_iterator<T>::begin(G);
 }
 
 /// Construct the end iterator for a deduced graph type T.
 template <class T> scc_iterator<T> scc_end(const T &G) {
   return scc_iterator<T>::end(G);
 }
 
 } // end namespace llvm
 
 #endif // LLVM_ADT_SCCITERATOR_H