From 5b78fc3ed4960c5eda8ec76ab2e86548c51a6811 Mon Sep 17 00:00:00 2001 From: Jan Sjodin Date: Tue, 20 May 2008 16:05:09 +0000 Subject: [PATCH] re PR middle-end/36206 (ice for legal code with -O3) 2008-05-20 Jan Sjodin Sebastian Pop PR tree-optimization/36206 * tree-scalar-evolution.c: Remove enum INSERT_SUPERLOOP_CHRECS, FOLD_CONVERSIONS. (instantiate_scev_1): Rename flags to fold_conversions. Do not check for INSERT_SUPERLOOP_CHRECS, keep SSA_NAMEs defined outeside instantiation_loop. * tree-chrec.h (evolution_function_is_affine_in_loop): New. (evolution_function_is_affine_or_constant_p): Removed. * tree-data-ref.c (dr_analyze_indices): Replace resolve_mixers with instantiate_scev. (analyze_siv_subscript): Pass in the loop nest number. Call evolution_function_is_affine_in_loop instead of evolution_function_is_affine_p. (analyze_overlapping_iterations): Pass in the loop nest number. * tree-chrec.h (chrec_fold_op): New. * tree-data-ref.c (initialize_matrix_A): Traverse NOP_EXPR, PLUS_EXPR, and other trees. * testsuite/gfortran.dg/pr36206.f: New. Co-Authored-By: Sebastian Pop From-SVN: r135663 --- gcc/ChangeLog | 26 ++++++++ gcc/testsuite/ChangeLog | 6 ++ gcc/testsuite/gfortran.dg/pr36206.f | 95 +++++++++++++++++++++++++++++ gcc/tree-chrec.h | 51 ++++++++++++---- gcc/tree-data-ref.c | 55 ++++++++++++----- gcc/tree-scalar-evolution.c | 72 +++++++++++----------- 6 files changed, 243 insertions(+), 62 deletions(-) create mode 100644 gcc/testsuite/gfortran.dg/pr36206.f diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 94677e69b4a..f7d2ff13faf 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,29 @@ +2008-05-20 Jan Sjodin + Sebastian Pop + + PR tree-optimization/36206 + * tree-scalar-evolution.c: Remove enum INSERT_SUPERLOOP_CHRECS, + FOLD_CONVERSIONS. + (instantiate_scev_1): Rename flags to fold_conversions. + Do not check for INSERT_SUPERLOOP_CHRECS, keep SSA_NAMEs defined + outeside instantiation_loop. + * tree-chrec.h (evolution_function_is_affine_in_loop): New. + (evolution_function_is_affine_or_constant_p): Removed. + * tree-data-ref.c (dr_analyze_indices): Replace resolve_mixers with + instantiate_scev. + (analyze_siv_subscript): Pass in the loop nest number. + Call evolution_function_is_affine_in_loop instead of + evolution_function_is_affine_p. + (analyze_overlapping_iterations): Pass in the loop nest number. + +2008-05-20 Jan Sjodin + Sebastian Pop + + PR tree-optimization/36206 + * tree-chrec.h (chrec_fold_op): New. + * tree-data-ref.c (initialize_matrix_A): Traverse NOP_EXPR, PLUS_EXPR, and + other trees. + 2008-05-20 Nathan Sidwell * c-incpath.c (INO_T_EQ): Do not define on non-inode systems. diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index d26eee12f45..e712f051739 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2008-05-20 Jan Sjodin + Sebastian Pop + + PR tree-optimization/36206 + * testsuite/gfortran.dg/pr36206.f: New. + 2008-05-20 Arnaud Charlet * gnat.dg/testint.adb: New test. diff --git a/gcc/testsuite/gfortran.dg/pr36206.f b/gcc/testsuite/gfortran.dg/pr36206.f new file mode 100644 index 00000000000..7b0b56639dd --- /dev/null +++ b/gcc/testsuite/gfortran.dg/pr36206.f @@ -0,0 +1,95 @@ +! { dg-do compile } +! { dg-options "-O3" } +! PR fortran/36206 + + SUBROUTINE SSPR(UPLO,N,ALPHA,X,INCX,AP) + REAL ALPHA + INTEGER INCX,N + CHARACTER UPLO + REAL AP(*),X(*) + REAL ZERO + PARAMETER (ZERO=0.0E+0) + REAL TEMP + INTEGER I,INFO,IX,J,JX,K,KK,KX + LOGICAL LSAME + EXTERNAL LSAME + EXTERNAL XERBLA + + INFO = 0 + IF (.NOT.LSAME(UPLO,'U') .AND. .NOT.LSAME(UPLO,'L')) THEN + INFO = 1 + ELSE IF (N.LT.0) THEN + INFO = 2 + ELSE IF (INCX.EQ.0) THEN + INFO = 5 + END IF + IF (INFO.NE.0) THEN + CALL XERBLA('SSPR ',INFO) + RETURN + END IF + IF ((N.EQ.0) .OR. (ALPHA.EQ.ZERO)) RETURN + IF (INCX.LE.0) THEN + KX = 1 - (N-1)*INCX + ELSE IF (INCX.NE.1) THEN + KX = 1 + END IF + KK = 1 + IF (LSAME(UPLO,'U')) THEN + IF (INCX.EQ.1) THEN + DO 20 J = 1,N + IF (X(J).NE.ZERO) THEN + TEMP = ALPHA*X(J) + K = KK + DO 10 I = 1,J + AP(K) = AP(K) + X(I)*TEMP + K = K + 1 + 10 CONTINUE + END IF + KK = KK + J + 20 CONTINUE + ELSE + JX = KX + DO 40 J = 1,N + IF (X(JX).NE.ZERO) THEN + TEMP = ALPHA*X(JX) + IX = KX + DO 30 K = KK,KK + J - 1 + AP(K) = AP(K) + X(IX)*TEMP + IX = IX + INCX + 30 CONTINUE + END IF + JX = JX + INCX + KK = KK + J + 40 CONTINUE + END IF + ELSE + IF (INCX.EQ.1) THEN + DO 60 J = 1,N + IF (X(J).NE.ZERO) THEN + TEMP = ALPHA*X(J) + K = KK + DO 50 I = J,N + AP(K) = AP(K) + X(I)*TEMP + K = K + 1 + 50 CONTINUE + END IF + KK = KK + N - J + 1 + 60 CONTINUE + ELSE + JX = KX + DO 80 J = 1,N + IF (X(JX).NE.ZERO) THEN + TEMP = ALPHA*X(JX) + IX = JX + DO 70 K = KK,KK + N - J + AP(K) = AP(K) + X(IX)*TEMP + IX = IX + INCX + 70 CONTINUE + END IF + JX = JX + INCX + KK = KK + N - J + 1 + 80 CONTINUE + END IF + END IF + RETURN + END diff --git a/gcc/tree-chrec.h b/gcc/tree-chrec.h index c908ec5c66b..a9246929816 100644 --- a/gcc/tree-chrec.h +++ b/gcc/tree-chrec.h @@ -168,10 +168,10 @@ evolution_function_is_constant_p (const_tree chrec) } } -/* Determine whether the given tree is an affine evolution function or not. */ +/* Determine whether CHREC is an affine evolution function in LOOPNUM. */ static inline bool -evolution_function_is_affine_p (const_tree chrec) +evolution_function_is_affine_in_loop (const_tree chrec, int loopnum) { if (chrec == NULL_TREE) return false; @@ -179,10 +179,8 @@ evolution_function_is_affine_p (const_tree chrec) switch (TREE_CODE (chrec)) { case POLYNOMIAL_CHREC: - if (evolution_function_is_invariant_p (CHREC_LEFT (chrec), - CHREC_VARIABLE (chrec)) - && evolution_function_is_invariant_p (CHREC_RIGHT (chrec), - CHREC_VARIABLE (chrec))) + if (evolution_function_is_invariant_p (CHREC_LEFT (chrec), loopnum) + && evolution_function_is_invariant_p (CHREC_RIGHT (chrec), loopnum)) return true; else return false; @@ -192,14 +190,26 @@ evolution_function_is_affine_p (const_tree chrec) } } -/* Determine whether the given tree is an affine or constant evolution - function. */ +/* Determine whether CHREC is an affine evolution function or not. */ static inline bool -evolution_function_is_affine_or_constant_p (const_tree chrec) +evolution_function_is_affine_p (const_tree chrec) { - return evolution_function_is_affine_p (chrec) - || evolution_function_is_constant_p (chrec); + if (chrec == NULL_TREE) + return false; + + switch (TREE_CODE (chrec)) + { + case POLYNOMIAL_CHREC: + if (evolution_function_is_invariant_p (CHREC_LEFT (chrec), CHREC_VARIABLE (chrec)) + && evolution_function_is_invariant_p (CHREC_RIGHT (chrec), CHREC_VARIABLE (chrec))) + return true; + else + return false; + + default: + return false; + } } /* Determines whether EXPR does not contains chrec expressions. */ @@ -221,5 +231,24 @@ chrec_type (const_tree chrec) return TREE_TYPE (chrec); } +static inline tree +chrec_fold_op (enum tree_code code, tree type, tree op0, tree op1) +{ + switch (code) + { + case PLUS_EXPR: + return chrec_fold_plus (type, op0, op1); + + case MINUS_EXPR: + return chrec_fold_minus (type, op0, op1); + + case MULT_EXPR: + return chrec_fold_multiply (type, op0, op1); + + default: + gcc_unreachable (); + } + +} #endif /* GCC_TREE_CHREC_H */ diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 7e9c99fc53a..75545496a17 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -754,7 +754,7 @@ dr_analyze_indices (struct data_reference *dr, struct loop *nest) { op = TREE_OPERAND (aref, 0); access_fn = analyze_scalar_evolution (loop, op); - access_fn = resolve_mixers (nest, access_fn); + access_fn = instantiate_scev (nest, loop, access_fn); base = initial_condition (access_fn); split_constant_offset (base, &base, &off); access_fn = chrec_replace_initial_condition (access_fn, @@ -1849,16 +1849,42 @@ analyze_siv_subscript_cst_affine (tree chrec_a, /* Helper recursive function for initializing the matrix A. Returns the initial value of CHREC. */ -static HOST_WIDE_INT +static tree initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult) { gcc_assert (chrec); - if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) - return int_cst_value (chrec); + switch (TREE_CODE (chrec)) + { + case POLYNOMIAL_CHREC: + gcc_assert (TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST); + + A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec)); + return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult); + + case PLUS_EXPR: + case MULT_EXPR: + case MINUS_EXPR: + { + tree op0 = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult); + tree op1 = initialize_matrix_A (A, TREE_OPERAND (chrec, 1), index, mult); + + return chrec_fold_op (TREE_CODE (chrec), chrec_type (chrec), op0, op1); + } - A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec)); - return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult); + case NOP_EXPR: + { + tree op = initialize_matrix_A (A, TREE_OPERAND (chrec, 0), index, mult); + return chrec_convert (chrec_type (chrec), op, NULL_TREE); + } + + case INTEGER_CST: + return chrec; + + default: + gcc_unreachable (); + return NULL_TREE; + } } #define FLOOR_DIV(x,y) ((x) / (y)) @@ -2090,8 +2116,8 @@ analyze_subscript_affine_affine (tree chrec_a, A = lambda_matrix_new (dim, 1); S = lambda_matrix_new (dim, 1); - init_a = initialize_matrix_A (A, chrec_a, 0, 1); - init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1); + init_a = int_cst_value (initialize_matrix_A (A, chrec_a, 0, 1)); + init_b = int_cst_value (initialize_matrix_A (A, chrec_b, nb_vars_a, -1)); gamma = init_b - init_a; /* Don't do all the hard work of solving the Diophantine equation @@ -2369,7 +2395,8 @@ analyze_siv_subscript (tree chrec_a, tree chrec_b, conflict_function **overlaps_a, conflict_function **overlaps_b, - tree *last_conflicts) + tree *last_conflicts, + int loop_nest_num) { dependence_stats.num_siv++; @@ -2377,17 +2404,17 @@ analyze_siv_subscript (tree chrec_a, fprintf (dump_file, "(analyze_siv_subscript \n"); if (evolution_function_is_constant_p (chrec_a) - && evolution_function_is_affine_p (chrec_b)) + && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num)) analyze_siv_subscript_cst_affine (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts); - else if (evolution_function_is_affine_p (chrec_a) + else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num) && evolution_function_is_constant_p (chrec_b)) analyze_siv_subscript_cst_affine (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts); - else if (evolution_function_is_affine_p (chrec_a) - && evolution_function_is_affine_p (chrec_b)) + else if (evolution_function_is_affine_in_loop (chrec_a, loop_nest_num) + && evolution_function_is_affine_in_loop (chrec_b, loop_nest_num)) { if (!chrec_contains_symbols (chrec_a) && !chrec_contains_symbols (chrec_b)) @@ -2649,7 +2676,7 @@ analyze_overlapping_iterations (tree chrec_a, else if (siv_subscript_p (chrec_a, chrec_b)) analyze_siv_subscript (chrec_a, chrec_b, overlap_iterations_a, overlap_iterations_b, - last_conflicts); + last_conflicts, lnn); else analyze_miv_subscript (chrec_a, chrec_b, diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index cc2df617294..7c9736a3b02 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -1952,26 +1952,23 @@ loop_closed_phi_def (tree var) } /* Analyze all the parameters of the chrec, between INSTANTIATION_LOOP - and EVOLUTION_LOOP, that were left under a symbolic form. CHREC is - the scalar evolution to instantiate. CACHE is the cache of already - instantiated values. FLAGS modify the way chrecs are instantiated. + and EVOLUTION_LOOP, that were left under a symbolic form. + + CHREC is the scalar evolution to instantiate. + + CACHE is the cache of already instantiated values. + + FOLD_CONVERSIONS should be set to true when the conversions that + may wrap in signed/pointer type are folded, as long as the value of + the chrec is preserved. + SIZE_EXPR is used for computing the size of the expression to be instantiated, and to stop if it exceeds some limit. */ - -/* Values for FLAGS. */ -enum -{ - INSERT_SUPERLOOP_CHRECS = 1, /* Loop invariants are replaced with chrecs - in outer loops. */ - FOLD_CONVERSIONS = 2 /* The conversions that may wrap in - signed/pointer type are folded, as long as the - value of the chrec is preserved. */ -}; static tree instantiate_scev_1 (struct loop *instantiation_loop, struct loop *evolution_loop, tree chrec, - int flags, htab_t cache, int size_expr) + bool fold_conversions, htab_t cache, int size_expr) { tree res, op0, op1, op2; basic_block def_bb; @@ -1995,8 +1992,7 @@ instantiate_scev_1 (struct loop *instantiation_loop, evolutions in outer loops), nothing to do. */ if (!def_bb || loop_depth (def_bb->loop_father) == 0 - || (!(flags & INSERT_SUPERLOOP_CHRECS) - && !flow_bb_inside_loop_p (instantiation_loop, def_bb))) + || !flow_bb_inside_loop_p (instantiation_loop, def_bb)) return chrec; /* We cache the value of instantiated variable to avoid exponential @@ -2052,7 +2048,7 @@ instantiate_scev_1 (struct loop *instantiation_loop, else if (res != chrec_dont_know) res = instantiate_scev_1 (instantiation_loop, evolution_loop, res, - flags, cache, size_expr); + fold_conversions, cache, size_expr); bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec)); @@ -2062,12 +2058,14 @@ instantiate_scev_1 (struct loop *instantiation_loop, case POLYNOMIAL_CHREC: op0 = instantiate_scev_1 (instantiation_loop, evolution_loop, - CHREC_LEFT (chrec), flags, cache, size_expr); + CHREC_LEFT (chrec), fold_conversions, cache, + size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; op1 = instantiate_scev_1 (instantiation_loop, evolution_loop, - CHREC_RIGHT (chrec), flags, cache, size_expr); + CHREC_RIGHT (chrec), fold_conversions, cache, + size_expr); if (op1 == chrec_dont_know) return chrec_dont_know; @@ -2082,13 +2080,13 @@ instantiate_scev_1 (struct loop *instantiation_loop, case POINTER_PLUS_EXPR: case PLUS_EXPR: op0 = instantiate_scev_1 (instantiation_loop, evolution_loop, - TREE_OPERAND (chrec, 0), flags, cache, + TREE_OPERAND (chrec, 0), fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; op1 = instantiate_scev_1 (instantiation_loop, evolution_loop, - TREE_OPERAND (chrec, 1), flags, cache, + TREE_OPERAND (chrec, 1), fold_conversions, cache, size_expr); if (op1 == chrec_dont_know) return chrec_dont_know; @@ -2104,14 +2102,14 @@ instantiate_scev_1 (struct loop *instantiation_loop, case MINUS_EXPR: op0 = instantiate_scev_1 (instantiation_loop, evolution_loop, - TREE_OPERAND (chrec, 0), flags, cache, + TREE_OPERAND (chrec, 0), fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; op1 = instantiate_scev_1 (instantiation_loop, evolution_loop, TREE_OPERAND (chrec, 1), - flags, cache, size_expr); + fold_conversions, cache, size_expr); if (op1 == chrec_dont_know) return chrec_dont_know; @@ -2127,13 +2125,13 @@ instantiate_scev_1 (struct loop *instantiation_loop, case MULT_EXPR: op0 = instantiate_scev_1 (instantiation_loop, evolution_loop, TREE_OPERAND (chrec, 0), - flags, cache, size_expr); + fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; op1 = instantiate_scev_1 (instantiation_loop, evolution_loop, TREE_OPERAND (chrec, 1), - flags, cache, size_expr); + fold_conversions, cache, size_expr); if (op1 == chrec_dont_know) return chrec_dont_know; @@ -2149,11 +2147,11 @@ instantiate_scev_1 (struct loop *instantiation_loop, CASE_CONVERT: op0 = instantiate_scev_1 (instantiation_loop, evolution_loop, TREE_OPERAND (chrec, 0), - flags, cache, size_expr); + fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; - if (flags & FOLD_CONVERSIONS) + if (fold_conversions) { tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0); if (tmp) @@ -2166,7 +2164,7 @@ instantiate_scev_1 (struct loop *instantiation_loop, /* If we used chrec_convert_aggressive, we can no longer assume that signed chrecs do not overflow, as chrec_convert does, so avoid calling it in that case. */ - if (flags & FOLD_CONVERSIONS) + if (fold_conversions) return fold_convert (TREE_TYPE (chrec), op0); return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE); @@ -2187,19 +2185,19 @@ instantiate_scev_1 (struct loop *instantiation_loop, case 3: op0 = instantiate_scev_1 (instantiation_loop, evolution_loop, TREE_OPERAND (chrec, 0), - flags, cache, size_expr); + fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; op1 = instantiate_scev_1 (instantiation_loop, evolution_loop, TREE_OPERAND (chrec, 1), - flags, cache, size_expr); + fold_conversions, cache, size_expr); if (op1 == chrec_dont_know) return chrec_dont_know; op2 = instantiate_scev_1 (instantiation_loop, evolution_loop, TREE_OPERAND (chrec, 2), - flags, cache, size_expr); + fold_conversions, cache, size_expr); if (op2 == chrec_dont_know) return chrec_dont_know; @@ -2214,13 +2212,13 @@ instantiate_scev_1 (struct loop *instantiation_loop, case 2: op0 = instantiate_scev_1 (instantiation_loop, evolution_loop, TREE_OPERAND (chrec, 0), - flags, cache, size_expr); + fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; op1 = instantiate_scev_1 (instantiation_loop, evolution_loop, TREE_OPERAND (chrec, 1), - flags, cache, size_expr); + fold_conversions, cache, size_expr); if (op1 == chrec_dont_know) return chrec_dont_know; @@ -2232,7 +2230,7 @@ instantiate_scev_1 (struct loop *instantiation_loop, case 1: op0 = instantiate_scev_1 (instantiation_loop, evolution_loop, TREE_OPERAND (chrec, 0), - flags, cache, size_expr); + fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; if (op0 == TREE_OPERAND (chrec, 0)) @@ -2272,8 +2270,8 @@ instantiate_scev (struct loop *instantiation_loop, struct loop *evolution_loop, fprintf (dump_file, ")\n"); } - res = instantiate_scev_1 (instantiation_loop, evolution_loop, chrec, - INSERT_SUPERLOOP_CHRECS, cache, 0); + res = instantiate_scev_1 (instantiation_loop, evolution_loop, chrec, false, + cache, 0); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -2296,7 +2294,7 @@ tree resolve_mixers (struct loop *loop, tree chrec) { htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); - tree ret = instantiate_scev_1 (loop, loop, chrec, FOLD_CONVERSIONS, cache, 0); + tree ret = instantiate_scev_1 (loop, loop, chrec, true, cache, 0); htab_delete (cache); return ret; } -- 2.30.2