[LLVMdev] BackedgeTakenCount calculation for fortran loops and DragonEgg gfortran-4.6

[Marcello Maggioni]

Mmm, sorry, the patch I posted crashes if ExitBr is null (which it may
be ...) , this one should be ok (and passess all the ScalarEvolution
tests in LLVM):

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index daf7742..b10fab2 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -4293,9 +4293,15 @@ ScalarEvolution::ComputeExitLimit(const Loop
*L, BasicBlock *ExitingBlock) {
   //
   // FIXME: we should be able to handle switch instructions (with a
single exit)
   BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
+
   if (ExitBr == 0) return getCouldNotCompute();
   assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");

+  BranchInst* BrFirstSucc = dyn_cast<BranchInst>(ExitBr->
+                                            getSuccessor(0)->getTerminator());
+  BranchInst* BrSecondSucc = dyn_cast<BranchInst>(ExitBr->
+                                            getSuccessor(1)->getTerminator());
+
   // At this point, we know we have a conditional branch that
determines whether
   // the loop is exited.  However, we don't know if the branch is executed each
   // time through the loop.  If not, then the execution count of the
branch will
@@ -4316,10 +4322,23 @@ ScalarEvolution::ComputeExitLimit(const Loop
*L, BasicBlock *ExitingBlock) {
   if (ExitBr->getSuccessor(0) != L->getHeader() &&
       ExitBr->getSuccessor(1) != L->getHeader() &&
       ExitBr->getParent() != L->getHeader()) {
-    // The simple checks failed, try climbing the unique predecessor chain
-    // up to the header.
+
     bool Ok = false;
-    for (BasicBlock *BB = ExitBr->getParent(); BB; ) {
+    //Check if the one of the successor of the exit branch has the is a block
+    //that has only one predecessor and has an unconditional branch to the
+    //loop header
+    if (BrFirstSucc && BrFirstSucc->isUnconditional() &&
+        BrFirstSucc->getSuccessor(0) == L->getHeader() &&
+        BrFirstSucc->getParent()->getUniquePredecessor())
+      Ok = true;
+    if (BrSecondSucc && BrSecondSucc->isUnconditional() &&
+        BrSecondSucc->getSuccessor(0) == L->getHeader() &&
+        BrSecondSucc->getParent()->getUniquePredecessor())
+      Ok = true;
+     // The simple checks failed, try climbing the unique predecessor chain
+    // up to the header.
+
+    for (BasicBlock *BB = ExitBr->getParent(); BB && !Ok; ) {
       BasicBlock *Pred = BB->getUniquePredecessor();
       if (!Pred)
         return getCouldNotCompute();

anyway, this patch is only "a concept" of what I'm talking about.

PS=Sorry for the bad english in the previous post :p

2012/2/8 Marcello Maggioni <hayarms at gmail.com>:
> Hello, I'm finding problems with BackEdgeTaken count calculation in
> even simple fortran loops with gfortran-4.6 + DragonEgg 3.0.
>
> Even for simple double loops like this one:
>
>       program test2
>       integer i,j,k
>       dimension k(100,100)
>       do j=1,100
>        do i=1,100
>         k(i,j) = i
>        enddo
>       enddo
>       write(*,*) k(1,30)
>       end
>
> make the ScalarEvolution engine return "CouldNotCompute" even for the
> outer loop (the inner loop is fine).
>
> You can find a screenshot of the translation of this loop here (with
> -view-cfg Polly version):
> http://i.imgur.com/Jyaqd.png
>
> The problem seems to be the fact that the ScalarEvolution can't
> consider the outer loop exit branch instruction as the trivial case
> (where one of the successors of the exit block is the loop header or
> the exit block is the loop header itself) because of the (strange?)
> loop shape (the exit block instead of jumping to the header of the
> loop jumps instead to another block that increments the induction
> variable and has an unconditional branch to the loop header) and so
> starts backtracking the predecessors of the of the exit block and
> stops when it reaches the inner loop that has a block without a unique
> predecessor.
>
> What do you think about this problem? This makes , for example,
> difficult analyzing even simple fortran loops with Polly .
> I believe the case portrayed in the picture is the same to the trivial
> case (because the exit block jumps to a block with an unconditional
> jump to the header of the loop), am I right?
>
> I've written this little patch that adds this case to the trivial case :
>
> diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
> index daf7742..fcbaffe 100644
> --- a/lib/Analysis/ScalarEvolution.cpp
> +++ b/lib/Analysis/ScalarEvolution.cpp
> @@ -4293,6 +4293,11 @@ ScalarEvolution::ComputeExitLimit(const Loop
> *L, BasicBlock *ExitingBlock) {
>   //
>   // FIXME: we should be able to handle switch instructions (with a
> single exit)
>   BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
> +  BranchInst* BrFirstSucc = dyn_cast<BranchInst>(ExitBr->
> +                                            getSuccessor(0)->getTerminator());
> +  BranchInst* BrSecondSucc = dyn_cast<BranchInst>(ExitBr->
> +                                            getSuccessor(1)->getTerminator());
> +
>   if (ExitBr == 0) return getCouldNotCompute();
>   assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
>
> @@ -4315,8 +4320,12 @@ ScalarEvolution::ComputeExitLimit(const Loop
> *L, BasicBlock *ExitingBlock) {
>   //
>   if (ExitBr->getSuccessor(0) != L->getHeader() &&
>       ExitBr->getSuccessor(1) != L->getHeader() &&
> -      ExitBr->getParent() != L->getHeader()) {
> -    // The simple checks failed, try climbing the unique predecessor chain
> +      ExitBr->getParent() != L->getHeader() &&
> +      !((BrFirstSucc && BrFirstSucc->isUnconditional() &&
> +         BrFirstSucc->getSuccessor(0) == L->getHeader()) ||
> +        (BrSecondSucc && BrSecondSucc->isUnconditional() &&
> +         BrSecondSucc->getSuccessor(0) == L->getHeader())) ) {
> +     // The simple checks failed, try climbing the unique predecessor chain
>     // up to the header.
>     bool Ok = false;
>     for (BasicBlock *BB = ExitBr->getParent(); BB; ) {
>
> what do you think about this? There is a better solution to the
> problem? Is the compiler itself broken?
>
> Thank you
>
> Marcello