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

[Marcello Maggioni]

Attached

2012/2/8 Marcello Maggioni <hayarms at gmail.com>:
> 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: scevconcept.patch
Type: application/octet-stream
Size: 2395 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120208/f8cc55c8/attachment.obj>