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

[Marcello Maggioni]

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