This is the mail archive of the fortran@gcc.gnu.org mailing list for the GNU Fortran project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[FORTRAN PATCH] Another nested FORALL bug-fix


Whilst recently studying the implementation in gfc_trans_forall_1, I've
come across what I believe is another serious bug in the way that gfortran
expands/translates nested FORALL statements to GIMPLE.

At first I thought the issue was just a minor memory leak that the info
structure that we allocate with gfc_getmem at the start of that function
was not being freed by the end of that routine.  On closer analysis, it
looks like the strange decision to implement the nested_forall_info as a
doubly-linked list with the outermost FORALL at the head, complicates the
task of popping the current FORALL off of the list, which was then never
implemented, making it unsafe to free that memory.  The consequence is
that if ever we have multiple FORALLs inside a FORALL, we contine to
accumulate loops/scopes, leading to incorrect code/behaviour on the
following testcase.

  integer :: a(10,10)
  integer :: tot
  a(:,:) = 0
  forall (i = 1:10)
    forall (j = 1:10)
      a(i,j) = 1
    end forall
    forall (k = 1:10)
      a(i,k) = a(i,k) + 1
    end forall
  end forall
  tot = sum(a(:,:))
  print *, tot
  if (tot .ne. 200) call abort ()
end

Instead of the assignment to one and increment loops each being executed
100 (i.e. 10*10) times, we expand the second "increment" FORALL as a
triply nested loop of i,j,k which then gets executed a 1000 times.  This
then leads to the result that instead of tot being the expected 200,
mainline gfortran actually produces the result 1100!

Investigating in subversion, it turns out that like the previous FORALL
mask bug, this also dates back to the addition of trans-stmt.c to
mainline, and is therefore in the strictest sense not a regression.
Thankfully, Steve Kargl's recent FORALL analysis reveals the construct is
still rare, so hopefully not many codes are affected.

The fix below both simplifies the nested_forall_info data structure,
speeds up its processing/manipulation and resolves the correctness bug.
Instead of having the current quadratic behaviour where we represent the
head of nested_forall_info as the outermost loop, and therefore have to
append new scopes to the tail, and then traverse forward to the end of the
list and then backwards as we generate the actual loops, things can be
much simplified by reversing the datastructure and considering the head to
be the innermost FORALL.  This then only requires a singly linked list,
O(1) cons as we enter a scope and no need to unlink the head as we pop out
of a scope.  Much like other "scopes" are handled in GCC.

As an additional benefit, not only does this reorganization simplify the
code and resolve the bug, but also enables some further FORALL
optimizations that I'll submit as a follow-up patch.  However, its better
to keep this as an independent bug-fix, as I suspect the gfortran
maintainers might request a 4.2 backport given its seriousness despite not
being a "classical" regression.


The following patch has been tested on x86_64-unknown-linux-gnu with a
full "make bootstrap", all default languages including fortran and
regression tested with a top-level "make -k check" with no new failures.

Ok for mainline?


2007-01-26  Roger Sayle  <roger@eyesopen.com>

        * trans-stmt.c (forall_info): Replace the next_nest and outer
        fields that previously implemented a doubly-linked list with a
        single prev_nest field (singly-linked list).
        (gfc_trans_nested_forall_loop): The nested_forall_info argument
        now denotes the innermost FORALL in the loop nest.
        (compute_overall_iter_number): Use prev_nest instead of next_nest.
        (gfc_trans_forall_1): Link/cons the new "info" to the head of the
        nested_forall_info linked list.  Free the current "info" when done.

        * gfortran.dg/forall_7.f90: New test case.


Roger
--

Attachment: patchf4.txt
Description: Text document

Attachment: forall_7.f90
Description: Text document


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]