While I was looking for an ICE, I noticed that the following code causes gfortran to take a long time (almost a minute, this is without optimizations) program sel implicit none integer,parameter :: n=1000 integer :: i,j real,dimension(n*n) :: vect vect(:) = (/ ((( (i+j+3)),i=1,n),j=1,n) /) end
Confirmed. This is because the array constructor is expanded at compile-time. If the constructor were used in an initialization we would abort, IIRC.
The time behavior is strictly linear BTW: n = 100: real 0m0.604s user 0m0.485s sys 0m0.021s n = 1000: real 1m0.860s user 0m49.055s sys 0m0.078s (the array grows quadratically with n) One thing that's interesting is that in the -fdump-parse-tree output the array constructor is only expanded in the first case but not in the second, so it looks like in the latter case we explicitly calculate the array and then throw it away.
ugh, it is quadratic, only the inner array constructor gets expanded. And this is where the <= 100 restriction I alluded to above comes in. For n = 100 the relevant line from the -fdump-parse-tree output looks like: ASSIGN vect(:) __convert_i4_r4[[(((/ ((/ (+ (+ 1 j) 3) , (+ (+ 2 j) 3) , (+ (+ 3 j) 3) , (+ (+ 4 j) 3) , (+ (+ 5 j) 3) , (+ (+ 6 j) 3) , (+ (+ 7 j) 3) , (+ (+ 8 j) 3) , (+ (+ 9 j) 3) , (+ (+ 10 j) 3) , (+ (+ 11 j) 3) , (+ (+ 12 j) 3), (+ (+ 13 j) 3) , (+ (+ 14 j) 3) , (+ (+ 15 j) 3) , (+ (+ 16 j) 3) , (+ (+ 17 j) 3) , (+ (+ 18 j) 3) , (+ (+ 19 j) 3) , (+ (+ 20 j) 3) , (+ (+ 21 j) 3) , (+ (+ 22 j) 3) , (+ (+ 23 j) 3) , (+ (+ 24 j) 3) , (+ (+ 25 j) 3) , (+ (+ 26 j) 3) ,(+ (+ 27 j) 3) , (+ (+ 28 j) 3) , (+ (+ 29 j) 3) , (+ (+ 30 j) 3) , (+ (+ 31 j)3) , (+ (+ 32 j) 3) , (+ (+ 33 j) 3) , (+ (+ 34 j) 3) , (+ (+ 35 j) 3) , (+ (+ 36 j) 3) , (+ (+ 37 j) 3) , (+ (+ 38 j) 3) , (+ (+ 39 j) 3) , (+ (+ 40 j) 3) , (+ (+ 41 j) 3) , (+ (+ 42 j) 3) , (+ (+ 43 j) 3) , (+ (+ 44 j) 3) , (+ (+ 45 j) 3) , (+ (+ 46 j) 3) , (+ (+ 47 j) 3) , (+ (+ 48 j) 3) , (+ (+ 49 j) 3) , (+ (+ 50j) 3) , (+ (+ 51 j) 3) , (+ (+ 52 j) 3) , (+ (+ 53 j) 3) , (+ (+ 54 j) 3) , (+ (+ 55 j) 3) , (+ (+ 56 j) 3) , (+ (+ 57 j) 3) , (+ (+ 58 j) 3) , (+ (+ 59 j) 3) , (+ (+ 60 j) 3) , (+ (+ 61 j) 3) , (+ (+ 62 j) 3) , (+ (+ 63 j) 3) , (+ (+ 64 j) 3) , (+ (+ 65 j) 3) , (+ (+ 66 j) 3) , (+ (+ 67 j) 3) , (+ (+ 68 j) 3) , (+ (+69 j) 3) , (+ (+ 70 j) 3) , (+ (+ 71 j) 3) , (+ (+ 72 j) 3) , (+ (+ 73 j) 3) , (+ (+ 74 j) 3) , (+ (+ 75 j) 3) , (+ (+ 76 j) 3) , (+ (+ 77 j) 3) , (+ (+ 78 j) 3) , (+ (+ 79 j) 3) , (+ (+ 80 j) 3) , (+ (+ 81 j) 3) , (+ (+ 82 j) 3) , (+ (+ 83 j) 3) , (+ (+ 84 j) 3) , (+ (+ 85 j) 3) , (+ (+ 86 j) 3) , (+ (+ 87 j) 3) , (+(+ 88 j) 3) , (+ (+ 89 j) 3) , (+ (+ 90 j) 3) , (+ (+ 91 j) 3) , (+ (+ 92 j) 3), (+ (+ 93 j) 3) , (+ (+ 94 j) 3) , (+ (+ 95 j) 3) , (+ (+ 96 j) 3) , (+ (+ 97 j) 3) , (+ (+ 98 j) 3) , (+ (+ 99 j) 3) , (+ (+ 100 j) 3) /) j=1,100,1) /)))]] while for n = 101 it loks like: ASSIGN vect(:) __convert_i4_r4[[(((/ ((/ ((/ (+ (+ i j) 3) /) i=1,101,1) /) j=1,101,1) /)))]] IOW the array constructor is not expanded any longer, but still the compilation takes longer :-(
One more thing I forgot to mention: for n = 100 the .original dump looks like this: int4 offset.1; struct array1_int4 atmp.0; atmp.0.dtype = 265; atmp.0.dim[0].stride = 1; atmp.0.dim[0].lbound = 0; atmp.0.dim[0].ubound = 9999; atmp.0.data = (int4[0:] *) _gfortran_internal_malloc (40000); atmp.0.offset = 0; offset.1 = 0; j = 1; while (1) { if (j > 100) goto L.1; else (void) 0; (*atmp.0.data)[offset.1] = j + 4; offset.1 = offset.1 + 1; (*atmp.0.data)[offset.1] = j + 5; offset.1 = offset.1 + 1; (*atmp.0.data)[offset.1] = j + 6; offset.1 = offset.1 + 1; (*atmp.0.data)[offset.1] = j + 7; ... offset.1 = offset.1 + 1; (*atmp.0.data)[offset.1] = j + 102; offset.1 = offset.1 + 1; (*atmp.0.data)[offset.1] = j + 103; offset.1 = offset.1 + 1; j = j + 1; etc. which is probably not what we want. The optimizers can't reduce this to the original form either.
This bug is related to slow compile found in test case for PR28914 with large array size. Constructor related.
*** Bug 31301 has been marked as a duplicate of this bug. ***
*** Bug 32489 has been marked as a duplicate of this bug. ***
There's no related bug field, but it's worth mentioning that PR19925 and this should probably be attacked at the same time.
And this looks like the right place for an attack: /* Given an array constructor, determine if the constructor is constant or not by expanding it and making sure that all elements are constants. This is a bit of a hack since something like (/ (i, i=1,100000000) /) will take a while as* opposed to a more clever function that traverses the expression tree. FIXME. */ int gfc_constant_ac (gfc_expr *e) {
See also notes/patch attempt in PR 32489.
Also see PR 41807 for related info.
Created attachment 19161 [details] Preliminary patch This patch cuts the compilation time of the original test case in half. It passes all regression tests except initialization_20.f90. I think this is an example of case that relies on a side effect to work. If we can resilve this one regression we will make substantial progress. The failing test case needs expansion/reduction. I just need to find the spot, which I suspect is in expr.c (gfc_reduce_init_expr)
Created attachment 19168 [details] Updated patch This exploratory patch passes all regression tests. I have also successfully compiled and run the polyhedron benchmarks. I have not tested higher order arrays to see if there is a compile time improvement yet. Feel free to test. What I hope to eventually do is move the expansion functions higher up the calling chain away from gfc_is_constant_expr. Regardless, this is gives a fairly good improvement.
I missed one regression from the patch in comment #13. Stay tuned.
Created attachment 19170 [details] Third time is a charm This patch resolves the last remaining regression. Removing the "didn't reduce" error allows things to proceed to the exceeds maximum size error message expected by initialization_20.f90. It also triggers at the correct limit. I reworked one of the test conditions to assure that both gfc_check_constructor_type and gfc_expand_constructor (expr) are executed. I was not sure that was strictly neccessary, but I was suspicious of that logic that could eliminate one of the two in the OR.
With this simply modified case: program sel implicit none integer,parameter :: n=10 integer :: i,j,k,l real,dimension(n*n*n*n) :: vect vect(:) = (/ ((((( (i+j+k+l+3)),i=1,n),j=1,n),k=1,n),l=1,n) /) print *, vect end Compilation time is reduced by 1/2 with the patch. Other more complex examples need to be tested of course.
With the patch in comment #15 (gfc, gfc_c without), I see the following for the test [macbook] f90/bug% cat pr19925_1_db.f90 INTEGER, PARAMETER :: N=100000 INTEGER, PARAMETER :: I(N)=(/(MOD(K,2),K=1,N)/) INTEGER, PARAMETER :: M(N)=I(N:1:-1) print *, I(1), M(1), I(N), M(N) END without (pr19925_1.f90)/with (pr19925_1_db.f90) the print line: [macbook] f90/bug% time gfc_c pr19925_1.f90 pr19925_1.f90:3.36: INTEGER, PARAMETER :: M(N)=I(N:1:-1) 1 Error: Initialization expression didn't reduce (1) 368.554u 0.801s 6:09.49 99.9% 0+0k 0+5io 0pf+0w [macbook] f90/bug% time gfc pr19925_1.f90 369.495u 0.629s 6:10.22 99.9% 0+0k 0+19io 0pf+0w [macbook] f90/bug% a.out [macbook] f90/bug% time gfc_c pr19925_1_db.f90 pr19925_1_db.f90:3.36: INTEGER, PARAMETER :: M(N)=I(N:1:-1) 1 Error: Initialization expression didn't reduce (1) 367.576u 0.591s 6:08.25 99.9% 0+0k 0+5io 0pf+0w [macbook] f90/bug% time gfc pr19925_1_db.f90 pr19925_1_db.f90:2.27: INTEGER, PARAMETER :: I(N)=(/(MOD(K,2),K=1,N)/) 1 Error: The number of elements in the array constructor at (1) requires an increase of the allowed 65535 upper limit. See -fmax-array-constructor option pr19925_1_db.f90: In function 'MAIN__': pr19925_1_db.f90:4:0: internal compiler error: in gfc_conv_array_constructor_expr, at fortran/trans-expr.c:3710 Please submit a full bug report, with preprocessed source if appropriate. See <http://gcc.gnu.org/bugs.html> for instructions. 369.184u 0.620s 6:09.87 99.9% 0+0k 0+5io 0pf+0w
Created attachment 19172 [details] Slightly modified charm This version handles Dominique's test case in comment #17.
The patch in comment #18 passes all regression tests as well. I hope we are honing in on this. It does make me wonder why at this point the BT type is unknown.
Created attachment 19180 [details] Hopefully final patch This patch moves the number of elements patch up front so that the error is given almost immediately. Previously, with one of Dominique's test cases, it would take over 15 minutes on my machine here before one find's out there is a problem. I use gfc_fatal_error because compilation at that this early stage continues on happily before quitting. Can be very annoying for programs with large array constructors. Testing continues.
With the patch in comment #20, I get several new failures: gcc/testsuite/gfortran.dg/actual_array_constructor_3.f90 pr20923 and friends pr34554 " IIRC when the constructors are used as initialization or in statements, they are expanded at compile time when possible if the length is less than 2^16, otherwise they are computed at run time. I think this behavior should be kept. The only cases for which the fatal error should be triggered is for PARAMETERS as in pr19925 that must be computed at compile time.
Ok, if I back up one step and leave the error message in trans-array.c and use gfc_fatal_error we get a usable patch. One thing this is showing is that the expansion is being done in the parsing/matching phase of compilation and also in the resolution phase. I do not yet understand why the ICE is triggered after the error: (with the changes I have made elsewhere.) if (c->iterator) { /* Problems occur when we get something like integer :: a(lots) = (/(i, i=1, lots)/) */ gfc_error_now ("The number of elements in the array constructor " "at %L requires an increase of the allowed %d " "upper limit. See -fmax-array-constructor " "option", &expr->where, gfc_option.flag_max_array_constructor); return NULL_TREE; }
Subject: Bug 20923 Author: jvdelisle Date: Sat Jan 9 17:47:04 2010 New Revision: 155769 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=155769 Log: 2010-01-09 Jerry DeLisle <jvdelisle@gcc.gnu.org> PR fortran/20923 PR fortran/32489 * trans-array.c (gfc_conv_array_initializer): Change call to gfc_error_now to call to gfc_fatal_error. * array.c (count_elements): Whitespace. (extract_element): Whitespace. (is_constant_element): Changed name from constant_element. (gfc_constant_ac): Only use expand_construuctor for expression types of EXPR_ARRAY. If expression type is EXPR_CONSTANT, no need to call gfc_is_constant_expr. * expr.c (gfc_reduce_init_expr): Adjust conditionals and delete error message. * resolve.c (gfc_is_expandable_expr): New function that determiners if array expressions should have their constructors expanded. (gfc_resolve_expr): Use new function to determine whether or not to call gfc_expand_constructor. Modified: trunk/gcc/fortran/ChangeLog trunk/gcc/fortran/array.c trunk/gcc/fortran/expr.c trunk/gcc/fortran/resolve.c trunk/gcc/fortran/trans-array.c
Subject: Bug 20923 Author: jvdelisle Date: Sat Jan 9 19:01:41 2010 New Revision: 155773 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=155773 Log: 2010-01-09 Jerry DeLisle <jvdelisle@gcc.gnu.org> PR fortran/32489 * gfortran.dg/array_constructor_33.f90: New test. PR fortran/20923 Fix ChangeLog entry. Added: trunk/gcc/testsuite/gfortran.dg/array_constructor_34.f90 Modified: trunk/gcc/testsuite/ChangeLog
Fixed on trunk. New constructor code on fortran-exp will probably take a whole new approach on this. Closing.