[LLVMdev] Question to Chris

[Wojciech Matyjewicz]

Seung,

> Would you please explain to me how I can access to this problem in a better way if you can figure out?

Here are my thoughts on your first question: "how to make it count
correctly for the reconstruction of loops?". I believe it can't be done
for an arbitrary loop. However, IIRC from previous posts your loops are
simple - for example: they don't contain any breaks, gotos. I think,
your reconstruction could be done for two forms of loops that are very
common:

1) rotated canonical loop (bb8.outer in your example):
The loop has only one backedge, and an induction variable counting from
0 with step 1. The only basic block that branches out of the loop (so
called, exiting block) is the backedge.

header:
  %i = phi [ 0, %preheader ], [ %i.next, %body ]
  ...
  br label %body ;%header and %body may be the same block

body:
  ...
  %i.next = add %i, 1
  %c = seteq %i.next, %n
  br %c, label %exit, label %header

exit:
  ...

The loop iteration count is %n. In this case, it means that _every_
basic block is executed %n times. Your current version of reconstruction
seems to be okay for loops in this form.

2) unrotated canonical loop (bb8 in your example):
The loop has only one backedge and an induction variable counting from 0
with step 1. The only basic block that branches out of the loop is the
loop header.

header:
  %i = phi [ 0, %preheader ], [ %i.next, %body ]
  ...
  %c = seteq %i, %n
  br %c, label %exit, label %body

body:
  ...
  %i.next = add %i, 1
  br label %header

exit:
  ...

The loop iteration count is also %n. However, this time it means that
the loop header is executed %n times, while the rest of blocks - %n-1
times. The reconstruction should take it into account. For example, it
could make a "for" loop from all loop basic blocks setting the iteration
count to %n-1, and then insert a copy of the loop header with %i==%n
after the "for".

I also suggest taking look at the LoopInfo pass. It has many useful
methods to analyze loops. To determine the loop iteration count you may
use the ScalarEvolution pass as well.

-Wojtek