LoopInfo are not able to identify some natural loops?

Hi,

I found that some loops can not be identified by LoopInfo pass. For example, the loop at line 3094 of rdopt.c of benchmark 464.h264ref from spec cpu2006 is not a loop or a child (pr grandchild) of any loop in the loop list generated by LoopInfo pass. The documentation of LoopInfo says that it identifies natural loops, who have exactly one entry point. But the IR of this loops shows that it’s header only has one BB in preds. Does that mean LoopInfo can not identify some natural loops?

Thanks,
Bo

A natural loop is one whose header dominates all of the nodes in the loop. There is probably some block outside of the loop jumping to a block in the loop body.

Cameron

In C code, if a loop is not a natural loop, that means its loop body should at least have one label, right? In that case, some BB out of the loop can jump to the loop body, so the loop has more than on entry.

Does LoopInfo guarantee to identify all natural loops? This property is very important for my pass.

regards,
Bo

In C code, if a loop is not a natural loop, that means its loop body should at least have one label, right? In that case, some BB out of the loop can jump to the loop body, so the loop has more than on entry.

Off the top of my head, I would think you are right: a C label would have to exist within the loop in order to have a jump from outside the loop to the inside of the loop.

That said, have you looked at the LLVM IR generated for the function and determined that the loop meets all the criteria of a natural loop? Just my two cents, but I think looking at the IR directly is much more accurate than ensuring that your conclusion about C code and natural loops is correct.

– John T.

Thanks for the reply. The LoopInfo pass can actually identify the loop I mentioned. My former question is due to a bug in my pass. What I worried is that LoopInfo can not identify all the natural loops for the benchmarks I use, but now I haven’t found any such cases.

Bo

Unless there is a very subtle bug in the code, it finds all natural loops. It looks for edges where the destination dominates the source, then finds all nodes in the corresponding loop.

Cameron

Hello,

I wanted to ask what the current status of llvm-stack-switch[1] is.
Currently, we use uclib for implementing coroutines. The Problem with this is, that you either copy you stack (and invalidate pointers to lokals) or have many stacks on the heap (the is very memory inefficient). Having llvm doing some optimization there would really help.

A different approach (for asymmetric coroutines) that I can think of is the following:
As llvm already supports stackless architectures, it should be possible to translate a program written with coroutines into a program that implements these with state machines. This way, no system calls would be needed and everything would be with little memory usage. Obviously this could blow up the stack but it would be efficient in out use case. (Every coroutines pauses and returns to the scheduler, this scheduler then activates the next coroutine)

Toralf Niebuhr

[1]http://code.google.com/p/llvm-stack-switch/

Hello Toralf,

I wanted to ask what the current status of llvm-stack-switch[1] is.

Given that this project never appeared in this mailing list - have you
tried to ask its author?

It is on the mailing list. This is how I found this project.
http://lists.cs.uiuc.edu/pipermail/llvmdev/2010-April/030787.html

But I couldn't find any updates after this thread.

Toralf Niebuhr