Page MenuHomePhabricator

[LOOPINFO] Add member function to retrieve loops in breadth-first order
AbandonedPublic

Authored by etiotto on Jul 8 2019, 11:59 AM.

Details

Summary

LoopInfo contains a utility to retrieve loops in depth-first order (preorder traversal). This patch adds a similar utility to retrieve loops in breadth-first order.

Diff Detail

Repository
rL LLVM

Event Timeline

etiotto created this revision.Jul 8 2019, 11:59 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 8 2019, 11:59 AM
jdoerfert added inline comments.
llvm/include/llvm/Analysis/LoopInfo.h
363

This is just a hunch but isn't this potentially expensive? What if we do not remove old elements in the worklist, e.g.:

while (Idx < Worklist.size()) {
  L = Worklist[Idx++];
  Worklist.append(L->begin(), L->end());
  BreadthFirstLoops.append(L->begin(), L->end());
}

Unrelated, why rbegin/rend? I would not associate an order in the loop levels with BFS, maybe document that there is one if you use these.

fhahn added a comment.Jul 8 2019, 3:06 PM

AFAIK, GraphTraits is implemented for Loop and you should be able to just use breadth_first from ADT/BreadthFirstIterator.h. It should return a breadth-first iterator range over the sub loops. Given it is a one-liner, I am not sure we would need to add a special method to LoopBase.

What's the intended use?

Test case?

etiotto abandoned this revision.Jul 9 2019, 9:51 AM

I can use breadth_first from ADT/BreadthFirstIterator.h to collect the loops in breadth-first order. Arguably the getLoopsInPreorder() member functions could also be removed in favor of using ADT/DepthFirstIterator.h (need to confirm whether that does a preorder traversal).

fhahn added a comment.Jul 9 2019, 9:56 AM

I can use breadth_first from ADT/BreadthFirstIterator.h to collect the loops in breadth-first order. Arguably the getLoopsInPreorder() member functions could also be removed in favor of using ADT/DepthFirstIterator.h (need to confirm whether that does a preorder traversal).

Yep, that was something I wanted to look into as a follow up.