Bug 19925 - Implied do-loop in an initialization expression is broken
Implied do-loop in an initialization expression is broken
Status: RESOLVED FIXED
Product: gcc
Classification: Unclassified
Component: fortran
4.0.0
: P2 normal
: ---
Assigned To: Not yet assigned to anyone
: ice-on-valid-code
: 20925 (view as bug list)
Depends on:
Blocks: 32834
  Show dependency treegraph
 
Reported: 2005-02-12 16:21 UTC by Steve Kargl
Modified: 2008-11-01 17:07 UTC (History)
6 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2007-11-26 04:50:29


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Steve Kargl 2005-02-12 16:21:34 UTC
From Richard Maine, editor of the F2003 standard

   program stuff
     integer :: i_do
     integer :: i(101) = (/ (i_do, i_do=1,101) /)
     write (*,*) i
   end program stuff

   bug1.f90: In function 'MAIN__':
   bug1.f90:4: internal compiler error: Possible frontend bug: array 
   constructor not expanded

   Note that it works up to size 100; fails at size 101.

If we look in array.c, we find the magic number 100.

/* This parameter is the size of the largest array constructor that we
   will expand to an array constructor without iterators.
   Constructors larger than this will remain in the iterator form.  */

#define GFC_MAX_AC_EXPAND 100
Comment 1 Andrew Pinski 2005-02-12 16:40:19 UTC
Confirmed.
Comment 2 Andrew Pinski 2005-05-14 20:58:25 UTC
*** Bug 20925 has been marked as a duplicate of this bug. ***
Comment 3 Erik Edelmann 2005-07-28 11:50:05 UTC
This bug has been briefly discussed on the mailing list:
http://gcc.gnu.org/ml/fortran/2005-06/msg00485.html
Comment 4 Andrew Pinski 2005-11-04 01:19:56 UTC
Hmm, I might take a look at this bug as I found it independently while compiling some other fortran code.
Comment 5 Andrew Pinski 2006-01-09 22:33:22 UTC
Here is a testcase which fails currently because of this bug:
   program stuff
     integer :: i_do
     integer :: i(100001) = (/ (i_do, i_do=1,100001) /)
     write (*,*) i
   end program stuff

-----
The limit was rose but we should be able to do better.
Comment 6 eedelman 2006-01-10 00:03:16 UTC
(In reply to comment #5)
> The limit was rose but we should be able to do better.

Indeed.  But the problem is not trivial.  For a case like above, where the array is a variable, we can translate it to

(program|function|subroutine) stuff
   integer :: i_do
   integer :: i(100001)
   logical, save :: _i_initialized = .FALSE.

   if (.not._i_initialized) then
         i = (/ (i_do, i_do=1,100001) /)
         _i_initialized = .TRUE.
   end if

   write (*,*) i
end (program|function|subroutine) stuff

(The _i_initialized variable is not needed in a main program, but it is in a procedure.) This far it isn't a huge problem, but when 'i' is a PARAMETER it gets more complicated. PARAMETERs are meant to be compile time constants. Let's say we have e.g.

subroutine stuff
   integer :: i_do
   integer, parameter :: i(100001) = <whatever>
   real(kind=i(1975)) :: a

   ...

end subroutine stuff

I can't at the moment think of a situation where we would need the entire array at the stage of compilation, but at least we need to be able to access individual elements.
Comment 7 Brian Taylor 2007-01-02 21:47:58 UTC
(In reply to comment #6)
> (The _i_initialized variable is not needed in a main program, but it is in a
> procedure.) This far it isn't a huge problem, but when 'i' is a PARAMETER it
> gets more complicated. PARAMETERs are meant to be compile time constants. Let's
> say we have e.g.
> 
> subroutine stuff
>    integer :: i_do
>    integer, parameter :: i(100001) = <whatever>
>    real(kind=i(1975)) :: a
> 
>    ...
> 
> end subroutine stuff

> 

This code is illegal - the kind specifier of a variable must be a scalar integer value.  That should eliminate at least this need for compile-time evaluation of parameter arrays.
Comment 8 Jerry DeLisle 2007-05-09 04:02:39 UTC
Apparently the magic limit here is 65535, not 100000 as stated previously. 
Comment 9 Tobias Schlüter 2007-10-06 14:09:02 UTC
There's no related bug field, but it's worth mentioning that PR20923 and this should probably be attacked at the same time.
Comment 10 Joost VandeVondele 2007-10-29 14:59:50 UTC
Since this is the oldest F95-only bug in gfortran, I had a look if it still exists. I'm not quite sure it does (at in the same form).

This

INTEGER, PARAMETER :: N=100000
INTEGER, PARAMETER :: I(N)=(/(MOD(K,2),K=1,N)/)
END

now compiles. However:

INTEGER, PARAMETER :: N=100000
INTEGER, PARAMETER :: I(N)=(/(MOD(K,2),K=1,N)/)
INTEGER, PARAMETER :: M(N)=I(N:1:-1)
END

causes an ICE
Comment 11 Jerry DeLisle 2007-11-26 04:50:29 UTC
I have been studying this more in some debug sessions.  We actually successfully match the iterator multiple times.  However, by the time we get through several attempted matchings, I think we get left with the last one which is NULL.  There is an attempt to match multiple iterators, I presume for each dimension of the array and these are kept in a linked list.  I suspect the handling of this list is what is messed up.

I will have to keep digging at this a bit before I can say anything with any certainty,  :)
Comment 12 Jerry DeLisle 2007-11-26 06:28:23 UTC
OK, tracing this farther, the correct iterator makes it to translation at gfc_conv_array_initializer.  Here we simply have not implemented code to handle it and we have this:

          if (c->iterator)
            {
              /* Problems occur when we get something like
                 integer :: a(lots) = (/(i, i=1,lots)/)  */
              /* TODO: Unexpanded array initializers.  */
              internal_error
                ("Possible frontend bug: array constructor not expanded");
	    }
So I keep at it.
Comment 13 Jerry DeLisle 2007-11-26 06:52:25 UTC
Food for thought:

I wonder if this is best solved by creating a general purpose iterator function that we call at run time whenever needed.  A function for each Basic Type.  Seems this would be fine for initializing arrays.
Comment 14 Jerry DeLisle 2008-01-08 19:04:31 UTC
This may be fixable employing gfc_trans_assignment at the right place similar to the fix Paul used in PR34438.  I have not time to chase this. Un-assigning.
Comment 15 Joost VandeVondele 2008-01-29 06:31:08 UTC
the comment #10 test case is still broken, and reaching its 3rd anniversary soon. Just a back trace to the segfault:

1347              cons = cons->next;
(gdb) bt
#0  0x0000000000422cda in find_array_section (expr=0xf740f0, ref=0xf74c00) at /data03/vondele/gcc_trunk/gcc/gcc/fortran/expr.c:1347
#1  0x00000000004233d4 in simplify_const_ref (p=0xf740f0) at /data03/vondele/gcc_trunk/gcc/gcc/fortran/expr.c:1431
#2  0x0000000000423c1d in gfc_simplify_expr (p=0xf740f0, type=0) at /data03/vondele/gcc_trunk/gcc/gcc/fortran/expr.c:1666
#3  0x0000000000423f0a in simplify_parameter_variable (p=0xf73d00, type=0) at /data03/vondele/gcc_trunk/gcc/gcc/fortran/expr.c:1533
#4  0x000000000042508a in gfc_match_init_expr (result=0x7fff62ec25e0) at /data03/vondele/gcc_trunk/gcc/gcc/fortran/expr.c:2328
#5  0x000000000041b440 in gfc_match_data_decl () at /data03/vondele/gcc_trunk/gcc/gcc/fortran/decl.c:1743
#6  0x000000000045097a in match_word (str=0x2aea48083980 "", subr=0x41a910 <gfc_match_data_decl>, old_locus=0x7fff62ec2660)
    at /data03/vondele/gcc_trunk/gcc/gcc/fortran/parse.c:64
#7  0x0000000000450f8e in decode_statement () at /data03/vondele/gcc_trunk/gcc/gcc/fortran/parse.c:280
#8  0x0000000000452045 in next_statement () at /data03/vondele/gcc_trunk/gcc/gcc/fortran/parse.c:652
#9  0x0000000000453444 in parse_spec (st=ST_DATA_DECL) at /data03/vondele/gcc_trunk/gcc/gcc/fortran/parse.c:2163
Comment 16 Jerry DeLisle 2008-01-29 15:29:41 UTC
The segfault here is the same segfault I reported in 34828 yesterday.  I have a patch all ready for that part.
Comment 17 Jerry DeLisle 2008-01-30 05:06:06 UTC
Regarding the segfault, it is similar to pr34828, but not the same place.  Apparently we do not traverse the constructors very well.
Comment 18 Jerry DeLisle 2008-02-01 04:43:12 UTC
With this patch:

@@ -1341,7 +1345,7 @@ find_array_section (gfc_expr *expr, gfc_
          cons = base;
        }
 
-      while (mpz_cmp (ptr, index) > 0)
+      while (mpz_cmp (ptr, index) > 0 && cons && cons->next)
        {
          mpz_add_ui (index, index, one);
          cons = cons->next;

The ICE for the second case on comment 10 goes away.  However, compile time is very long as N increases:

  N = 1000,   .113 secs
      5000,   .702
     10000,  5.627
     12000, 11.091
     15000, 21.500
     20000, 42.228
     25000, 66.600

For N=100000 After several minutes we get the error message:

pr19925-10.f90:9.36:

INTEGER, PARAMETER :: M(N)=I(N:1:-1)
                                   1
Error: Initialization expression didn't reduce (1)

The ICE for this example is not related to the original problem in this PR.
Using the case of N = 5000, the printed results fo the array I, and m agree with ifort and sun f95.  I am going to break this out as a separate PR and submit this patch as a fix.  The failure to reduce, I am guessing is a different problem.
Comment 19 Tobias Burnus 2008-02-01 13:39:57 UTC
> The ICE for the second case on comment 10 goes away.  However, compile time is
> very long as N increases:

I played around (w/o your patch) with several compilers and gfortran does not do too bad (all compilers with N=15000 and -O0): gfortran: 10.45s, ifort: 10.43, g95: 34.73s. However, it can be much faster: openf95 0.11s; NAG f95 0.12s. sunf95 0.2s.
Comment 20 Dominique d'Humieres 2008-02-01 15:31:48 UTC
With the patch in comment #18, on a Core2Duo 2.16Ghz I get:

    5000      0.54   secs
  10000      1.82
  20000      6.74
  40000    36.5
  60000  206
  65535  258
  65536     68         <--   Error: Initialization expression didn't reduce (1)
  80000  149                                            Ditto
100000  281                                            Ditto

So the threshold seems to be 2**16. While the timings in comment #18 seem more or less cubic in n, on the Core2duo, they start more or less quadratic in n up to 20000, then grow up much faster with n, as if they were the addition of one quadratic behavior and one cubic (or faster) with prefactors depending on the processor.

Note that the patch in #18, is not needed below some value of n: n=10000 pass on unpatched ppc.

Comment 21 Steve Kargl 2008-02-01 16:04:10 UTC
Subject: Re:  Implied do-loop in an initialization expression is broken

On Fri, Feb 01, 2008 at 03:31:49PM -0000, dominiq at lps dot ens dot fr wrote:
> 
> With the patch in comment #18, on a Core2Duo 2.16Ghz I get:
> 
>     5000      0.54   secs
>   10000      1.82
>   20000      6.74
>   40000    36.5
>   60000  206
>   65535  258
>   65536     68         <--   Error: Initialization expression didn't reduce (1)
>   80000  149                                            Ditto
> 100000  281                                            Ditto
> 
> So the threshold seems to be 2**16.

'grep ChangeLog-2005 6553'.

Comment 22 Dominique d'Humieres 2008-02-01 16:41:17 UTC
For large values of n, most of the time is spent in gfc_append_constructor, starting from 5% and up to 92%.  Most of the remaining time is spent in find_array_section, starting from 75% down to 2.5%.
Although I did not follow closely the algorithm, I got it is basically quadratic (for an intrinsically linear problem). Also, each time gfc_get_constructor is called, there is a call to "gfc_getmem (sizeof(gfc_constructor))".


Comment 23 Dominique d'Humieres 2008-02-01 16:58:45 UTC
On ppc G5 1.8Ghz, I get an almost perfect quadratic behavior:

10000    18 secs
20000    72
40000  290
60000  655
65535  778

Comment 24 Jerry DeLisle 2008-02-02 02:05:02 UTC
Reply to comment #21.  I am aware of the 65535 limit.  At least this minor patch gets rid of a segfault, and handling the large array constructors by building the array at run time is obviously not fixed yet.
Comment 25 Dominique d'Humieres 2008-02-02 11:09:35 UTC
From comment #24:

> ... handling the large array constructors by building the array at run time is obviously not fixed yet.

This can be done for

INTEGER, PARAMETER :: N=65535
INTEGER :: I(N)=(/(MOD(K,2),K=1,N)/)
INTEGER :: M(N)=(/(MOD(K,2),K=N,1,-1)/)
print *, M(N)

but not when I and M are PARAMETERs: if I am not mistaken PARAMETER defines constants for the compiler, hence cannot be deferred to run time.  Note that the above code compiles in few seconds while it takes several hundred seconds with PARAMETER.

A short term solution could be to improve the error message when the 65535 limit is reached: "Initialization expression didn't reduce" does not point clearly to this limit. An error (if correct?) such that "Array constructors cannot have more than 65535 elements" will give a better diagnostic of what's going wrong.
Comment 26 Steve Kargl 2008-02-02 16:38:51 UTC
Subject: Re:  Implied do-loop in an initialization expression is broken

On Sat, Feb 02, 2008 at 11:09:36AM -0000, dominiq at lps dot ens dot fr wrote:
> 
> A short term solution could be to improve the error message when the 65535
> limit is reached: "Initialization expression didn't reduce" does not point
> clearly to this limit. An error (if correct?) such that "Array constructors
> cannot have more than 65535 elements" will give a better diagnostic of what's
> going wrong.
> 

65535 was arbitrarily chosen by me.  This value allowed the
fmlib package to compile and run.  65535 should actually be
spelled as 100 (or maybe even smaller).  Short term solutions
have the uncanny nature of becoming long term bandaids.
See PR 19925 for an example.

Erik suggested in comment #6 one possible solution to the
problem.  In the mailing list or IRC, Paul Brook suggested
that a CTOR/DTOR methods should be considered.

Comment 27 macius bat 2008-09-07 08:25:54 UTC
somebody fix it please.
Comment 28 Steve Kargl 2008-09-07 16:33:42 UTC
Subject: Re:  Implied do-loop in an initialization expression is broken

On Sun, Sep 07, 2008 at 08:25:54AM -0000, linuxl4 at sohu dot com wrote:
> 
> somebody fix it please.
> 

If it were easy to fix, someone would have done this already.
Please read the audit trail.

Comment 29 Dominique d'Humieres 2008-10-11 10:31:45 UTC
On Sat, 20 Sep 2008 08:20:29 +0200, Paul Richard Thomas wrote (http://gcc.gnu.org/ml/gcc-patches/2008-09/msg01415.html):

> It looks good to me - I'm just out of the door for the weekend (for
> once!) - I'll attend to it tomorrow night if nobody beats me to it.

If I am not mistaken nothing happened since then.  Could the patch in http://gcc.gnu.org/ml/gcc-patches/2008-09/msg01410.html be committed?

Comment 30 Jerry DeLisle 2008-11-01 16:43:55 UTC
Subject: Bug 19925

Author: jvdelisle
Date: Sat Nov  1 16:42:31 2008
New Revision: 141518

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=141518
Log:
2008-11-01  Steven G. Kargl  <kargls@comcast.net>

	PR fortran/19925
	* trans-array.c (gfc_trans_array_constructor_value): Fix comment.
	(gfc_conv_array_initializer): Convert internal_error() to gfc_error_now.
	* array.c: Remove GFC_MAX_AC_EXPAND macro.
	(gfc_expand_constructor): Use gfc_option.flag_max_array_constructor.
	* gfortran.h (gfc_option): Add flag_max_array_constructor member.
	* lang.opt: Add -fmax-array-constructor option.
	* expr.c (gfc_match_init_expr): Fix error message to mention new option.
	* invoke.texi: Document new option.
	* options.c (gfc_init_options): Set default value for new option.
	(gfc_handle_option): Deal with commandline.

Modified:
    trunk/gcc/fortran/ChangeLog
    trunk/gcc/fortran/array.c
    trunk/gcc/fortran/gfortran.h
    trunk/gcc/fortran/invoke.texi
    trunk/gcc/fortran/lang.opt
    trunk/gcc/fortran/options.c
    trunk/gcc/fortran/trans-array.c

Comment 31 Jerry DeLisle 2008-11-01 17:02:17 UTC
Subject: Bug 19925

Author: jvdelisle
Date: Sat Nov  1 17:00:49 2008
New Revision: 141519

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=141519
Log:
2008-11-01  Steven G. Kargl  <kargls@comcast.net>

	PR fortran/19925
	* gfortran.dg/initialization_20.f90: New test.
	* gfortran.dg/initialization_21.f90: Ditto.

Added:
    trunk/gcc/testsuite/gfortran.dg/initialization_20.f90
    trunk/gcc/testsuite/gfortran.dg/initialization_21.f90
Modified:
    trunk/gcc/testsuite/ChangeLog

Comment 32 Jerry DeLisle 2008-11-01 17:07:27 UTC
Finally, I hope.  :)