[LLVMdev] determining the number of iteration of a loop

[khaled hamidouche]

Hello

I'm wandring to know how many times a block is executed inside a loop  ?
knowing that I can't use  getSmallConstantTripCount() because the number is unkown  "for (i=0;i<N;i++)  for example"

I'm using a Function pass

for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
    if (Loop *L = LI->getLoopFor(BB)) {
            if (L->getHeader() == BB)
               {
                 the code of the loop   (the header)
               }
             else{the code of the block inside the loop}
   else
     the code of a basicblock (outside a loop)


How can I get the variable N (even only the name of this variable !!)   ???

I mean I want to get  "the loop will be executed  "%N"  times"

Thank you so much

K.H 
    

[Trevor Harmon]

On Apr 21, 2010, at 7:31 AM, khaled hamidouche wrote:

> I'm wandring to know how many times a block is executed inside a
> loop ?
> knowing that I can't use getSmallConstantTripCount() because the
> number is unkown "for (i=0;i<N;i++) for example"

In general, the number of iterations is undecidable. For example:

int main(char **argv, int N) {
for (int i = 0; i < N; i++) {
std::cout << "arg: " << argv[i] << std::endl;
}
return 0;
}

If you are parsing code whose iterations can be determined, please
post it.

Trevor

_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


--
Subscription settings: http://groups.google.com/group/llvm-dev/subscribe?hl=en

[Eugene Toder]

In your example the the number of iterations is known -- it is N. It
is not known at compile time, but it's known at run-time before you
enter the loop. So you can do transforms like if( N < threshold ) copy
of loop optimized for small iterations count; else copy of loop
optimized for large iterations count;

But you are right, in general, the number of iterations in unknown. I
think Khaled is interested in a large number of cases when it is
known, either as a constant or value.

Eugene

[ether zhhb]

hi,

you could try the getBackedgeTakenCount function of ScalarEvolution.

opt -scalar-evolution -analyze
define void @f(i64* nocapture %a, i64 %N) nounwind {
entry:
  %0 = icmp sgt i64 %N, 0                         ; <i1> [#uses=1]
  br i1 %0, label %bb, label %return

bb:                                               ; preds = %bb, %entry
  %1 = phi i64 [ 0, %entry ], [ %2, %bb ]         ; <i64> [#uses=3]
  %scevgep = getelementptr i64* %a, i64 %1        ; <i64*> [#uses=1]
  store i64 %1, i64* %scevgep, align 8
  %2 = add nsw i64 %1, 1                          ; <i64> [#uses=2]
  %exitcond = icmp eq i64 %2, %N                  ; <i1> [#uses=1]
  br i1 %exitcond, label %return, label %bb

return:                                           ; preds = %bb, %entry
  ret void
}
Printing analysis 'Scalar Evolution Analysis' for function 'f':
Classifying expressions for: @f
  %0 = icmp sgt i64 %N, 0                         ; <i1> [#uses=1]
  -->  %0
  %1 = phi i64 [ 0, %entry ], [ %2, %bb ]         ; <i64> [#uses=3]
  -->  {0,+,1}<%bb>             Exits: (-1 + %N)
  %scevgep = getelementptr i64* %a, i64 %1        ; <i64*> [#uses=1]
  -->  {%a,+,sizeof(i64)}<%bb>          Exits: (((-1 + %N) * sizeof(i64)) + %a)
  %2 = add nsw i64 %1, 1                          ; <i64> [#uses=2]
  -->  {1,+,1}<%bb>             Exits: %N
  %exitcond = icmp eq i64 %2, %N                  ; <i1> [#uses=1]
  -->  %exitcond                Exits: <<Unknown>>
Determining loop execution counts for: @f
Loop %bb: backedge-taken count is (-1 + %N)
Loop %bb: max backedge-taken count is (-1 + %N)

--best regares
ether