llvm dev - May 2010 - [LLVMdev] Back-edge taken count of loops

hi all,

i am have a project need to compute the back-edge taken count of a loop, and
the "getBackedgeTakenCount" function of ScalarEvolution could do this
for
me.

but later i found that ScalarEvolution could not compute loops with test
expression containing a "=", such as:

void scop_func(long A[], long n) {
  long i;

  for (i = 1; i<= n; i++)
    A[i] = 1;
}

after have a look at the code that computing the back-edge taken count, i
found that ScalarEvolution could only compute back-edge taken count if the
exit condition is ICMP_NE/ICMP_EQ/ICMP_SLT/ICMP_SGT/ICMP_ULT/ICMP_UGT
(ignoring "ComputeBackedgeTakenCountExhaustively"), and the function
"SimplifyICmpOperands" will try to convert other conditions to the
conditions listed above, by doing something like "i <= n" to
"i < n+1", but
it refuse to do that unless it could prove "n + 1" will not cause a
overflow.

So, could us just set "n + 1" to the Exact field of BackedgeTakenInfo,
and
set something like SCEVInfinite  to the Max field of BackedgeTakenInfo?

thanks
ether
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100506/af11583b/attachment.html>

I recently added support for <= loops on trunk. ScalarEvolution now
uses the nsw flag to prove that it doesn't need to consider the
infinite-loop case.

Dan

On May 6, 2010, at 2:50 AM, ether zhhb wrote:
> hi all,
> 
> i am have a project need to compute the back-edge taken count of a loop,
and the "getBackedgeTakenCount" function of ScalarEvolution could do
this for me.
> 
> but later i found that ScalarEvolution could not compute loops with test
expression containing a "=", such as:
> 
> void scop_func(long A[], long n) {
>   long i;
> 
>   for (i = 1; i<= n; i++)
>     A[i] = 1;
> }
> 
> after have a look at the code that computing the back-edge taken count, i
found that ScalarEvolution could only compute back-edge taken count if the exit
condition is ICMP_NE/ICMP_EQ/ICMP_SLT/ICMP_SGT/ICMP_ULT/ICMP_UGT (ignoring
"ComputeBackedgeTakenCountExhaustively"), and the function
"SimplifyICmpOperands" will try to convert other conditions to the
conditions listed above, by doing something like "i <= n" to
"i < n+1", but it refuse to do that unless it could prove "n +
1" will not cause a overflow.
> 
> So, could us just set "n + 1" to the Exact field of
BackedgeTakenInfo, and set something like SCEVInfinite  to the Max field of
BackedgeTakenInfo?
> 
> thanks
> ether
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

hi Dan,
On Fri, May 7, 2010 at 12:23 AM, Dan Gohman <gohman at apple.com> wrote:
> I recently added support for <= loops on trunk.
thanks very much, that will help us a lot :)
> ScalarEvolution now
> uses the nsw flag to prove that it doesn't need to consider the
> infinite-loop case.
>
> Dan
>
> best regards
--ether
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100507/f20a1c0d/attachment.html>