138fd1498Szrj /* Chains of recurrences.
238fd1498Szrj Copyright (C) 2003-2018 Free Software Foundation, Inc.
338fd1498Szrj Contributed by Sebastian Pop <pop@cri.ensmp.fr>
438fd1498Szrj
538fd1498Szrj This file is part of GCC.
638fd1498Szrj
738fd1498Szrj GCC is free software; you can redistribute it and/or modify it under
838fd1498Szrj the terms of the GNU General Public License as published by the Free
938fd1498Szrj Software Foundation; either version 3, or (at your option) any later
1038fd1498Szrj version.
1138fd1498Szrj
1238fd1498Szrj GCC is distributed in the hope that it will be useful, but WITHOUT ANY
1338fd1498Szrj WARRANTY; without even the implied warranty of MERCHANTABILITY or
1438fd1498Szrj FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1538fd1498Szrj for more details.
1638fd1498Szrj
1738fd1498Szrj You should have received a copy of the GNU General Public License
1838fd1498Szrj along with GCC; see the file COPYING3. If not see
1938fd1498Szrj <http://www.gnu.org/licenses/>. */
2038fd1498Szrj
2138fd1498Szrj /* This file implements operations on chains of recurrences. Chains
2238fd1498Szrj of recurrences are used for modeling evolution functions of scalar
2338fd1498Szrj variables.
2438fd1498Szrj */
2538fd1498Szrj
2638fd1498Szrj #include "config.h"
2738fd1498Szrj #include "system.h"
2838fd1498Szrj #include "coretypes.h"
2938fd1498Szrj #include "backend.h"
3038fd1498Szrj #include "tree.h"
3138fd1498Szrj #include "gimple-expr.h"
3238fd1498Szrj #include "tree-pretty-print.h"
3338fd1498Szrj #include "fold-const.h"
3438fd1498Szrj #include "cfgloop.h"
3538fd1498Szrj #include "tree-ssa-loop-ivopts.h"
3638fd1498Szrj #include "tree-ssa-loop-niter.h"
3738fd1498Szrj #include "tree-chrec.h"
3838fd1498Szrj #include "dumpfile.h"
3938fd1498Szrj #include "params.h"
4038fd1498Szrj #include "tree-scalar-evolution.h"
4138fd1498Szrj
4238fd1498Szrj /* Extended folder for chrecs. */
4338fd1498Szrj
4438fd1498Szrj /* Determines whether CST is not a constant evolution. */
4538fd1498Szrj
4638fd1498Szrj static inline bool
is_not_constant_evolution(const_tree cst)4738fd1498Szrj is_not_constant_evolution (const_tree cst)
4838fd1498Szrj {
4938fd1498Szrj return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
5038fd1498Szrj }
5138fd1498Szrj
5238fd1498Szrj /* Fold CODE for a polynomial function and a constant. */
5338fd1498Szrj
5438fd1498Szrj static inline tree
chrec_fold_poly_cst(enum tree_code code,tree type,tree poly,tree cst)5538fd1498Szrj chrec_fold_poly_cst (enum tree_code code,
5638fd1498Szrj tree type,
5738fd1498Szrj tree poly,
5838fd1498Szrj tree cst)
5938fd1498Szrj {
6038fd1498Szrj gcc_assert (poly);
6138fd1498Szrj gcc_assert (cst);
6238fd1498Szrj gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC);
6338fd1498Szrj gcc_checking_assert (!is_not_constant_evolution (cst));
6438fd1498Szrj gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly)));
6538fd1498Szrj
6638fd1498Szrj switch (code)
6738fd1498Szrj {
6838fd1498Szrj case PLUS_EXPR:
6938fd1498Szrj return build_polynomial_chrec
7038fd1498Szrj (CHREC_VARIABLE (poly),
7138fd1498Szrj chrec_fold_plus (type, CHREC_LEFT (poly), cst),
7238fd1498Szrj CHREC_RIGHT (poly));
7338fd1498Szrj
7438fd1498Szrj case MINUS_EXPR:
7538fd1498Szrj return build_polynomial_chrec
7638fd1498Szrj (CHREC_VARIABLE (poly),
7738fd1498Szrj chrec_fold_minus (type, CHREC_LEFT (poly), cst),
7838fd1498Szrj CHREC_RIGHT (poly));
7938fd1498Szrj
8038fd1498Szrj case MULT_EXPR:
8138fd1498Szrj return build_polynomial_chrec
8238fd1498Szrj (CHREC_VARIABLE (poly),
8338fd1498Szrj chrec_fold_multiply (type, CHREC_LEFT (poly), cst),
8438fd1498Szrj chrec_fold_multiply (type, CHREC_RIGHT (poly), cst));
8538fd1498Szrj
8638fd1498Szrj default:
8738fd1498Szrj return chrec_dont_know;
8838fd1498Szrj }
8938fd1498Szrj }
9038fd1498Szrj
9138fd1498Szrj /* Fold the addition of two polynomial functions. */
9238fd1498Szrj
9338fd1498Szrj static inline tree
chrec_fold_plus_poly_poly(enum tree_code code,tree type,tree poly0,tree poly1)9438fd1498Szrj chrec_fold_plus_poly_poly (enum tree_code code,
9538fd1498Szrj tree type,
9638fd1498Szrj tree poly0,
9738fd1498Szrj tree poly1)
9838fd1498Szrj {
9938fd1498Szrj tree left, right;
10038fd1498Szrj struct loop *loop0 = get_chrec_loop (poly0);
10138fd1498Szrj struct loop *loop1 = get_chrec_loop (poly1);
10238fd1498Szrj tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (poly1) : type;
10338fd1498Szrj
10438fd1498Szrj gcc_assert (poly0);
10538fd1498Szrj gcc_assert (poly1);
10638fd1498Szrj gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
10738fd1498Szrj gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
10838fd1498Szrj if (POINTER_TYPE_P (chrec_type (poly0)))
10938fd1498Szrj gcc_checking_assert (ptrofftype_p (chrec_type (poly1))
11038fd1498Szrj && useless_type_conversion_p (type, chrec_type (poly0)));
11138fd1498Szrj else
11238fd1498Szrj gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0))
11338fd1498Szrj && useless_type_conversion_p (type, chrec_type (poly1)));
11438fd1498Szrj
11538fd1498Szrj /*
11638fd1498Szrj {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
11738fd1498Szrj {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
11838fd1498Szrj {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
11938fd1498Szrj if (flow_loop_nested_p (loop0, loop1))
12038fd1498Szrj {
12138fd1498Szrj if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
12238fd1498Szrj return build_polynomial_chrec
12338fd1498Szrj (CHREC_VARIABLE (poly1),
12438fd1498Szrj chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
12538fd1498Szrj CHREC_RIGHT (poly1));
12638fd1498Szrj else
12738fd1498Szrj return build_polynomial_chrec
12838fd1498Szrj (CHREC_VARIABLE (poly1),
12938fd1498Szrj chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
13038fd1498Szrj chrec_fold_multiply (type, CHREC_RIGHT (poly1),
13138fd1498Szrj SCALAR_FLOAT_TYPE_P (type)
13238fd1498Szrj ? build_real (type, dconstm1)
13338fd1498Szrj : build_int_cst_type (type, -1)));
13438fd1498Szrj }
13538fd1498Szrj
13638fd1498Szrj if (flow_loop_nested_p (loop1, loop0))
13738fd1498Szrj {
13838fd1498Szrj if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
13938fd1498Szrj return build_polynomial_chrec
14038fd1498Szrj (CHREC_VARIABLE (poly0),
14138fd1498Szrj chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
14238fd1498Szrj CHREC_RIGHT (poly0));
14338fd1498Szrj else
14438fd1498Szrj return build_polynomial_chrec
14538fd1498Szrj (CHREC_VARIABLE (poly0),
14638fd1498Szrj chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
14738fd1498Szrj CHREC_RIGHT (poly0));
14838fd1498Szrj }
14938fd1498Szrj
15038fd1498Szrj /* This function should never be called for chrecs of loops that
15138fd1498Szrj do not belong to the same loop nest. */
15238fd1498Szrj if (loop0 != loop1)
15338fd1498Szrj {
15438fd1498Szrj /* It still can happen if we are not in loop-closed SSA form. */
15538fd1498Szrj gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA));
15638fd1498Szrj return chrec_dont_know;
15738fd1498Szrj }
15838fd1498Szrj
15938fd1498Szrj if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
16038fd1498Szrj {
16138fd1498Szrj left = chrec_fold_plus
16238fd1498Szrj (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
16338fd1498Szrj right = chrec_fold_plus
16438fd1498Szrj (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
16538fd1498Szrj }
16638fd1498Szrj else
16738fd1498Szrj {
16838fd1498Szrj left = chrec_fold_minus
16938fd1498Szrj (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
17038fd1498Szrj right = chrec_fold_minus
17138fd1498Szrj (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
17238fd1498Szrj }
17338fd1498Szrj
17438fd1498Szrj if (chrec_zerop (right))
17538fd1498Szrj return left;
17638fd1498Szrj else
17738fd1498Szrj return build_polynomial_chrec
17838fd1498Szrj (CHREC_VARIABLE (poly0), left, right);
17938fd1498Szrj }
18038fd1498Szrj
18138fd1498Szrj
18238fd1498Szrj
18338fd1498Szrj /* Fold the multiplication of two polynomial functions. */
18438fd1498Szrj
18538fd1498Szrj static inline tree
chrec_fold_multiply_poly_poly(tree type,tree poly0,tree poly1)18638fd1498Szrj chrec_fold_multiply_poly_poly (tree type,
18738fd1498Szrj tree poly0,
18838fd1498Szrj tree poly1)
18938fd1498Szrj {
19038fd1498Szrj tree t0, t1, t2;
19138fd1498Szrj int var;
19238fd1498Szrj struct loop *loop0 = get_chrec_loop (poly0);
19338fd1498Szrj struct loop *loop1 = get_chrec_loop (poly1);
19438fd1498Szrj
19538fd1498Szrj gcc_assert (poly0);
19638fd1498Szrj gcc_assert (poly1);
19738fd1498Szrj gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
19838fd1498Szrj gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
19938fd1498Szrj gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0))
20038fd1498Szrj && useless_type_conversion_p (type, chrec_type (poly1)));
20138fd1498Szrj
20238fd1498Szrj /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
20338fd1498Szrj {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
20438fd1498Szrj {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
20538fd1498Szrj if (flow_loop_nested_p (loop0, loop1))
20638fd1498Szrj /* poly0 is a constant wrt. poly1. */
20738fd1498Szrj return build_polynomial_chrec
20838fd1498Szrj (CHREC_VARIABLE (poly1),
20938fd1498Szrj chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
21038fd1498Szrj CHREC_RIGHT (poly1));
21138fd1498Szrj
21238fd1498Szrj if (flow_loop_nested_p (loop1, loop0))
21338fd1498Szrj /* poly1 is a constant wrt. poly0. */
21438fd1498Szrj return build_polynomial_chrec
21538fd1498Szrj (CHREC_VARIABLE (poly0),
21638fd1498Szrj chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
21738fd1498Szrj CHREC_RIGHT (poly0));
21838fd1498Szrj
21938fd1498Szrj if (loop0 != loop1)
22038fd1498Szrj {
22138fd1498Szrj /* It still can happen if we are not in loop-closed SSA form. */
22238fd1498Szrj gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA));
22338fd1498Szrj return chrec_dont_know;
22438fd1498Szrj }
22538fd1498Szrj
22638fd1498Szrj /* poly0 and poly1 are two polynomials in the same variable,
22738fd1498Szrj {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
22838fd1498Szrj
22938fd1498Szrj /* "a*c". */
23038fd1498Szrj t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
23138fd1498Szrj
23238fd1498Szrj /* "a*d + b*c". */
23338fd1498Szrj t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
23438fd1498Szrj t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
23538fd1498Szrj CHREC_RIGHT (poly0),
23638fd1498Szrj CHREC_LEFT (poly1)));
23738fd1498Szrj /* "b*d". */
23838fd1498Szrj t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
23938fd1498Szrj /* "a*d + b*c + b*d". */
24038fd1498Szrj t1 = chrec_fold_plus (type, t1, t2);
24138fd1498Szrj /* "2*b*d". */
24238fd1498Szrj t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
24338fd1498Szrj ? build_real (type, dconst2)
24438fd1498Szrj : build_int_cst (type, 2), t2);
24538fd1498Szrj
24638fd1498Szrj var = CHREC_VARIABLE (poly0);
24738fd1498Szrj return build_polynomial_chrec (var, t0,
24838fd1498Szrj build_polynomial_chrec (var, t1, t2));
24938fd1498Szrj }
25038fd1498Szrj
25138fd1498Szrj /* When the operands are automatically_generated_chrec_p, the fold has
25238fd1498Szrj to respect the semantics of the operands. */
25338fd1498Szrj
25438fd1498Szrj static inline tree
chrec_fold_automatically_generated_operands(tree op0,tree op1)25538fd1498Szrj chrec_fold_automatically_generated_operands (tree op0,
25638fd1498Szrj tree op1)
25738fd1498Szrj {
25838fd1498Szrj if (op0 == chrec_dont_know
25938fd1498Szrj || op1 == chrec_dont_know)
26038fd1498Szrj return chrec_dont_know;
26138fd1498Szrj
26238fd1498Szrj if (op0 == chrec_known
26338fd1498Szrj || op1 == chrec_known)
26438fd1498Szrj return chrec_known;
26538fd1498Szrj
26638fd1498Szrj if (op0 == chrec_not_analyzed_yet
26738fd1498Szrj || op1 == chrec_not_analyzed_yet)
26838fd1498Szrj return chrec_not_analyzed_yet;
26938fd1498Szrj
27038fd1498Szrj /* The default case produces a safe result. */
27138fd1498Szrj return chrec_dont_know;
27238fd1498Szrj }
27338fd1498Szrj
27438fd1498Szrj /* Fold the addition of two chrecs. */
27538fd1498Szrj
27638fd1498Szrj static tree
chrec_fold_plus_1(enum tree_code code,tree type,tree op0,tree op1)27738fd1498Szrj chrec_fold_plus_1 (enum tree_code code, tree type,
27838fd1498Szrj tree op0, tree op1)
27938fd1498Szrj {
28038fd1498Szrj if (automatically_generated_chrec_p (op0)
28138fd1498Szrj || automatically_generated_chrec_p (op1))
28238fd1498Szrj return chrec_fold_automatically_generated_operands (op0, op1);
28338fd1498Szrj
28438fd1498Szrj switch (TREE_CODE (op0))
28538fd1498Szrj {
28638fd1498Szrj case POLYNOMIAL_CHREC:
28738fd1498Szrj gcc_checking_assert
28838fd1498Szrj (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
28938fd1498Szrj switch (TREE_CODE (op1))
29038fd1498Szrj {
29138fd1498Szrj case POLYNOMIAL_CHREC:
29238fd1498Szrj gcc_checking_assert
29338fd1498Szrj (!chrec_contains_symbols_defined_in_loop (op1,
29438fd1498Szrj CHREC_VARIABLE (op1)));
29538fd1498Szrj return chrec_fold_plus_poly_poly (code, type, op0, op1);
29638fd1498Szrj
29738fd1498Szrj CASE_CONVERT:
29838fd1498Szrj {
29938fd1498Szrj /* We can strip sign-conversions to signed by performing the
30038fd1498Szrj operation in unsigned. */
30138fd1498Szrj tree optype = TREE_TYPE (TREE_OPERAND (op1, 0));
30238fd1498Szrj if (INTEGRAL_TYPE_P (type)
30338fd1498Szrj && INTEGRAL_TYPE_P (optype)
30438fd1498Szrj && tree_nop_conversion_p (type, optype)
30538fd1498Szrj && TYPE_UNSIGNED (optype))
30638fd1498Szrj return chrec_convert (type,
30738fd1498Szrj chrec_fold_plus_1 (code, optype,
30838fd1498Szrj chrec_convert (optype,
30938fd1498Szrj op0, NULL),
31038fd1498Szrj TREE_OPERAND (op1, 0)),
31138fd1498Szrj NULL);
31238fd1498Szrj if (tree_contains_chrecs (op1, NULL))
31338fd1498Szrj return chrec_dont_know;
31438fd1498Szrj }
31538fd1498Szrj /* FALLTHRU */
31638fd1498Szrj
31738fd1498Szrj default:
31838fd1498Szrj if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
31938fd1498Szrj return build_polynomial_chrec
32038fd1498Szrj (CHREC_VARIABLE (op0),
32138fd1498Szrj chrec_fold_plus (type, CHREC_LEFT (op0), op1),
32238fd1498Szrj CHREC_RIGHT (op0));
32338fd1498Szrj else
32438fd1498Szrj return build_polynomial_chrec
32538fd1498Szrj (CHREC_VARIABLE (op0),
32638fd1498Szrj chrec_fold_minus (type, CHREC_LEFT (op0), op1),
32738fd1498Szrj CHREC_RIGHT (op0));
32838fd1498Szrj }
32938fd1498Szrj
33038fd1498Szrj CASE_CONVERT:
33138fd1498Szrj {
33238fd1498Szrj /* We can strip sign-conversions to signed by performing the
33338fd1498Szrj operation in unsigned. */
33438fd1498Szrj tree optype = TREE_TYPE (TREE_OPERAND (op0, 0));
33538fd1498Szrj if (INTEGRAL_TYPE_P (type)
33638fd1498Szrj && INTEGRAL_TYPE_P (optype)
33738fd1498Szrj && tree_nop_conversion_p (type, optype)
33838fd1498Szrj && TYPE_UNSIGNED (optype))
33938fd1498Szrj return chrec_convert (type,
34038fd1498Szrj chrec_fold_plus_1 (code, optype,
34138fd1498Szrj TREE_OPERAND (op0, 0),
34238fd1498Szrj chrec_convert (optype,
34338fd1498Szrj op1, NULL)),
34438fd1498Szrj NULL);
34538fd1498Szrj if (tree_contains_chrecs (op0, NULL))
34638fd1498Szrj return chrec_dont_know;
34738fd1498Szrj }
34838fd1498Szrj /* FALLTHRU */
34938fd1498Szrj
35038fd1498Szrj default:
35138fd1498Szrj switch (TREE_CODE (op1))
35238fd1498Szrj {
35338fd1498Szrj case POLYNOMIAL_CHREC:
35438fd1498Szrj gcc_checking_assert
35538fd1498Szrj (!chrec_contains_symbols_defined_in_loop (op1,
35638fd1498Szrj CHREC_VARIABLE (op1)));
35738fd1498Szrj if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
35838fd1498Szrj return build_polynomial_chrec
35938fd1498Szrj (CHREC_VARIABLE (op1),
36038fd1498Szrj chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
36138fd1498Szrj CHREC_RIGHT (op1));
36238fd1498Szrj else
36338fd1498Szrj return build_polynomial_chrec
36438fd1498Szrj (CHREC_VARIABLE (op1),
36538fd1498Szrj chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
36638fd1498Szrj chrec_fold_multiply (type, CHREC_RIGHT (op1),
36738fd1498Szrj SCALAR_FLOAT_TYPE_P (type)
36838fd1498Szrj ? build_real (type, dconstm1)
36938fd1498Szrj : build_int_cst_type (type, -1)));
37038fd1498Szrj
37138fd1498Szrj CASE_CONVERT:
37238fd1498Szrj if (tree_contains_chrecs (op1, NULL))
37338fd1498Szrj return chrec_dont_know;
37438fd1498Szrj /* FALLTHRU */
37538fd1498Szrj
37638fd1498Szrj default:
37738fd1498Szrj {
378*58e805e6Szrj int size = 0;
379*58e805e6Szrj if ((tree_contains_chrecs (op0, &size)
380*58e805e6Szrj || tree_contains_chrecs (op1, &size))
381*58e805e6Szrj && size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
38238fd1498Szrj return build2 (code, type, op0, op1);
383*58e805e6Szrj else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
38438fd1498Szrj {
38538fd1498Szrj if (code == POINTER_PLUS_EXPR)
38638fd1498Szrj return fold_build_pointer_plus (fold_convert (type, op0),
38738fd1498Szrj op1);
38838fd1498Szrj else
38938fd1498Szrj return fold_build2 (code, type,
39038fd1498Szrj fold_convert (type, op0),
39138fd1498Szrj fold_convert (type, op1));
39238fd1498Szrj }
393*58e805e6Szrj else
394*58e805e6Szrj return chrec_dont_know;
39538fd1498Szrj }
39638fd1498Szrj }
39738fd1498Szrj }
39838fd1498Szrj }
39938fd1498Szrj
40038fd1498Szrj /* Fold the addition of two chrecs. */
40138fd1498Szrj
40238fd1498Szrj tree
chrec_fold_plus(tree type,tree op0,tree op1)40338fd1498Szrj chrec_fold_plus (tree type,
40438fd1498Szrj tree op0,
40538fd1498Szrj tree op1)
40638fd1498Szrj {
40738fd1498Szrj enum tree_code code;
40838fd1498Szrj if (automatically_generated_chrec_p (op0)
40938fd1498Szrj || automatically_generated_chrec_p (op1))
41038fd1498Szrj return chrec_fold_automatically_generated_operands (op0, op1);
41138fd1498Szrj
41238fd1498Szrj if (integer_zerop (op0))
41338fd1498Szrj return chrec_convert (type, op1, NULL);
41438fd1498Szrj if (integer_zerop (op1))
41538fd1498Szrj return chrec_convert (type, op0, NULL);
41638fd1498Szrj
41738fd1498Szrj if (POINTER_TYPE_P (type))
41838fd1498Szrj code = POINTER_PLUS_EXPR;
41938fd1498Szrj else
42038fd1498Szrj code = PLUS_EXPR;
42138fd1498Szrj
42238fd1498Szrj return chrec_fold_plus_1 (code, type, op0, op1);
42338fd1498Szrj }
42438fd1498Szrj
42538fd1498Szrj /* Fold the subtraction of two chrecs. */
42638fd1498Szrj
42738fd1498Szrj tree
chrec_fold_minus(tree type,tree op0,tree op1)42838fd1498Szrj chrec_fold_minus (tree type,
42938fd1498Szrj tree op0,
43038fd1498Szrj tree op1)
43138fd1498Szrj {
43238fd1498Szrj if (automatically_generated_chrec_p (op0)
43338fd1498Szrj || automatically_generated_chrec_p (op1))
43438fd1498Szrj return chrec_fold_automatically_generated_operands (op0, op1);
43538fd1498Szrj
43638fd1498Szrj if (integer_zerop (op1))
43738fd1498Szrj return op0;
43838fd1498Szrj
43938fd1498Szrj return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
44038fd1498Szrj }
44138fd1498Szrj
44238fd1498Szrj /* Fold the multiplication of two chrecs. */
44338fd1498Szrj
44438fd1498Szrj tree
chrec_fold_multiply(tree type,tree op0,tree op1)44538fd1498Szrj chrec_fold_multiply (tree type,
44638fd1498Szrj tree op0,
44738fd1498Szrj tree op1)
44838fd1498Szrj {
44938fd1498Szrj if (automatically_generated_chrec_p (op0)
45038fd1498Szrj || automatically_generated_chrec_p (op1))
45138fd1498Szrj return chrec_fold_automatically_generated_operands (op0, op1);
45238fd1498Szrj
45338fd1498Szrj switch (TREE_CODE (op0))
45438fd1498Szrj {
45538fd1498Szrj case POLYNOMIAL_CHREC:
45638fd1498Szrj gcc_checking_assert
45738fd1498Szrj (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
45838fd1498Szrj switch (TREE_CODE (op1))
45938fd1498Szrj {
46038fd1498Szrj case POLYNOMIAL_CHREC:
46138fd1498Szrj gcc_checking_assert
46238fd1498Szrj (!chrec_contains_symbols_defined_in_loop (op1,
46338fd1498Szrj CHREC_VARIABLE (op1)));
46438fd1498Szrj return chrec_fold_multiply_poly_poly (type, op0, op1);
46538fd1498Szrj
46638fd1498Szrj CASE_CONVERT:
46738fd1498Szrj if (tree_contains_chrecs (op1, NULL))
46838fd1498Szrj return chrec_dont_know;
46938fd1498Szrj /* FALLTHRU */
47038fd1498Szrj
47138fd1498Szrj default:
47238fd1498Szrj if (integer_onep (op1))
47338fd1498Szrj return op0;
47438fd1498Szrj if (integer_zerop (op1))
47538fd1498Szrj return build_int_cst (type, 0);
47638fd1498Szrj
47738fd1498Szrj return build_polynomial_chrec
47838fd1498Szrj (CHREC_VARIABLE (op0),
47938fd1498Szrj chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
48038fd1498Szrj chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
48138fd1498Szrj }
48238fd1498Szrj
48338fd1498Szrj CASE_CONVERT:
48438fd1498Szrj if (tree_contains_chrecs (op0, NULL))
48538fd1498Szrj return chrec_dont_know;
48638fd1498Szrj /* FALLTHRU */
48738fd1498Szrj
48838fd1498Szrj default:
48938fd1498Szrj if (integer_onep (op0))
49038fd1498Szrj return op1;
49138fd1498Szrj
49238fd1498Szrj if (integer_zerop (op0))
49338fd1498Szrj return build_int_cst (type, 0);
49438fd1498Szrj
49538fd1498Szrj switch (TREE_CODE (op1))
49638fd1498Szrj {
49738fd1498Szrj case POLYNOMIAL_CHREC:
49838fd1498Szrj gcc_checking_assert
49938fd1498Szrj (!chrec_contains_symbols_defined_in_loop (op1,
50038fd1498Szrj CHREC_VARIABLE (op1)));
50138fd1498Szrj return build_polynomial_chrec
50238fd1498Szrj (CHREC_VARIABLE (op1),
50338fd1498Szrj chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
50438fd1498Szrj chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
50538fd1498Szrj
50638fd1498Szrj CASE_CONVERT:
50738fd1498Szrj if (tree_contains_chrecs (op1, NULL))
50838fd1498Szrj return chrec_dont_know;
50938fd1498Szrj /* FALLTHRU */
51038fd1498Szrj
51138fd1498Szrj default:
51238fd1498Szrj if (integer_onep (op1))
51338fd1498Szrj return op0;
51438fd1498Szrj if (integer_zerop (op1))
51538fd1498Szrj return build_int_cst (type, 0);
51638fd1498Szrj return fold_build2 (MULT_EXPR, type, op0, op1);
51738fd1498Szrj }
51838fd1498Szrj }
51938fd1498Szrj }
52038fd1498Szrj
52138fd1498Szrj
52238fd1498Szrj
52338fd1498Szrj /* Operations. */
52438fd1498Szrj
52538fd1498Szrj /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
52638fd1498Szrj calculation overflows, otherwise return C(n,k) with type TYPE. */
52738fd1498Szrj
52838fd1498Szrj static tree
tree_fold_binomial(tree type,tree n,unsigned int k)52938fd1498Szrj tree_fold_binomial (tree type, tree n, unsigned int k)
53038fd1498Szrj {
53138fd1498Szrj bool overflow;
53238fd1498Szrj unsigned int i;
53338fd1498Szrj
53438fd1498Szrj /* Handle the most frequent cases. */
53538fd1498Szrj if (k == 0)
53638fd1498Szrj return build_int_cst (type, 1);
53738fd1498Szrj if (k == 1)
53838fd1498Szrj return fold_convert (type, n);
53938fd1498Szrj
54038fd1498Szrj widest_int num = wi::to_widest (n);
54138fd1498Szrj
54238fd1498Szrj /* Check that k <= n. */
54338fd1498Szrj if (wi::ltu_p (num, k))
54438fd1498Szrj return NULL_TREE;
54538fd1498Szrj
54638fd1498Szrj /* Denominator = 2. */
54738fd1498Szrj widest_int denom = 2;
54838fd1498Szrj
54938fd1498Szrj /* Index = Numerator-1. */
55038fd1498Szrj widest_int idx = num - 1;
55138fd1498Szrj
55238fd1498Szrj /* Numerator = Numerator*Index = n*(n-1). */
55338fd1498Szrj num = wi::smul (num, idx, &overflow);
55438fd1498Szrj if (overflow)
55538fd1498Szrj return NULL_TREE;
55638fd1498Szrj
55738fd1498Szrj for (i = 3; i <= k; i++)
55838fd1498Szrj {
55938fd1498Szrj /* Index--. */
56038fd1498Szrj --idx;
56138fd1498Szrj
56238fd1498Szrj /* Numerator *= Index. */
56338fd1498Szrj num = wi::smul (num, idx, &overflow);
56438fd1498Szrj if (overflow)
56538fd1498Szrj return NULL_TREE;
56638fd1498Szrj
56738fd1498Szrj /* Denominator *= i. */
56838fd1498Szrj denom *= i;
56938fd1498Szrj }
57038fd1498Szrj
57138fd1498Szrj /* Result = Numerator / Denominator. */
57238fd1498Szrj num = wi::udiv_trunc (num, denom);
57338fd1498Szrj if (! wi::fits_to_tree_p (num, type))
57438fd1498Szrj return NULL_TREE;
57538fd1498Szrj return wide_int_to_tree (type, num);
57638fd1498Szrj }
57738fd1498Szrj
57838fd1498Szrj /* Helper function. Use the Newton's interpolating formula for
57938fd1498Szrj evaluating the value of the evolution function.
58038fd1498Szrj The result may be in an unsigned type of CHREC. */
58138fd1498Szrj
58238fd1498Szrj static tree
chrec_evaluate(unsigned var,tree chrec,tree n,unsigned int k)58338fd1498Szrj chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
58438fd1498Szrj {
58538fd1498Szrj tree arg0, arg1, binomial_n_k;
58638fd1498Szrj tree type = TREE_TYPE (chrec);
58738fd1498Szrj struct loop *var_loop = get_loop (cfun, var);
58838fd1498Szrj
58938fd1498Szrj while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
59038fd1498Szrj && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
59138fd1498Szrj chrec = CHREC_LEFT (chrec);
59238fd1498Szrj
59338fd1498Szrj /* The formula associates the expression and thus we have to make
59438fd1498Szrj sure to not introduce undefined overflow. */
59538fd1498Szrj tree ctype = type;
59638fd1498Szrj if (INTEGRAL_TYPE_P (type)
59738fd1498Szrj && ! TYPE_OVERFLOW_WRAPS (type))
59838fd1498Szrj ctype = unsigned_type_for (type);
59938fd1498Szrj
60038fd1498Szrj if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
60138fd1498Szrj && CHREC_VARIABLE (chrec) == var)
60238fd1498Szrj {
60338fd1498Szrj arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
60438fd1498Szrj if (arg1 == chrec_dont_know)
60538fd1498Szrj return chrec_dont_know;
60638fd1498Szrj binomial_n_k = tree_fold_binomial (ctype, n, k);
60738fd1498Szrj if (!binomial_n_k)
60838fd1498Szrj return chrec_dont_know;
60938fd1498Szrj tree l = chrec_convert (ctype, CHREC_LEFT (chrec), NULL);
61038fd1498Szrj arg0 = fold_build2 (MULT_EXPR, ctype, l, binomial_n_k);
61138fd1498Szrj return chrec_fold_plus (ctype, arg0, arg1);
61238fd1498Szrj }
61338fd1498Szrj
61438fd1498Szrj binomial_n_k = tree_fold_binomial (ctype, n, k);
61538fd1498Szrj if (!binomial_n_k)
61638fd1498Szrj return chrec_dont_know;
61738fd1498Szrj
61838fd1498Szrj return fold_build2 (MULT_EXPR, ctype,
61938fd1498Szrj chrec_convert (ctype, chrec, NULL), binomial_n_k);
62038fd1498Szrj }
62138fd1498Szrj
62238fd1498Szrj /* Evaluates "CHREC (X)" when the varying variable is VAR.
62338fd1498Szrj Example: Given the following parameters,
62438fd1498Szrj
62538fd1498Szrj var = 1
62638fd1498Szrj chrec = {3, +, 4}_1
62738fd1498Szrj x = 10
62838fd1498Szrj
62938fd1498Szrj The result is given by the Newton's interpolating formula:
63038fd1498Szrj 3 * \binom{10}{0} + 4 * \binom{10}{1}.
63138fd1498Szrj */
63238fd1498Szrj
63338fd1498Szrj tree
chrec_apply(unsigned var,tree chrec,tree x)63438fd1498Szrj chrec_apply (unsigned var,
63538fd1498Szrj tree chrec,
63638fd1498Szrj tree x)
63738fd1498Szrj {
63838fd1498Szrj tree type = chrec_type (chrec);
63938fd1498Szrj tree res = chrec_dont_know;
64038fd1498Szrj
64138fd1498Szrj if (automatically_generated_chrec_p (chrec)
64238fd1498Szrj || automatically_generated_chrec_p (x)
64338fd1498Szrj
64438fd1498Szrj /* When the symbols are defined in an outer loop, it is possible
64538fd1498Szrj to symbolically compute the apply, since the symbols are
64638fd1498Szrj constants with respect to the varying loop. */
64738fd1498Szrj || chrec_contains_symbols_defined_in_loop (chrec, var))
64838fd1498Szrj return chrec_dont_know;
64938fd1498Szrj
65038fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
65138fd1498Szrj fprintf (dump_file, "(chrec_apply \n");
65238fd1498Szrj
65338fd1498Szrj if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
65438fd1498Szrj x = build_real_from_int_cst (type, x);
65538fd1498Szrj
65638fd1498Szrj switch (TREE_CODE (chrec))
65738fd1498Szrj {
65838fd1498Szrj case POLYNOMIAL_CHREC:
65938fd1498Szrj if (evolution_function_is_affine_p (chrec))
66038fd1498Szrj {
66138fd1498Szrj if (CHREC_VARIABLE (chrec) != var)
66238fd1498Szrj return build_polynomial_chrec
66338fd1498Szrj (CHREC_VARIABLE (chrec),
66438fd1498Szrj chrec_apply (var, CHREC_LEFT (chrec), x),
66538fd1498Szrj chrec_apply (var, CHREC_RIGHT (chrec), x));
66638fd1498Szrj
66738fd1498Szrj /* "{a, +, b} (x)" -> "a + b*x". */
66838fd1498Szrj x = chrec_convert_rhs (type, x, NULL);
66938fd1498Szrj res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x);
67038fd1498Szrj res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
67138fd1498Szrj }
67238fd1498Szrj else if (TREE_CODE (x) == INTEGER_CST
67338fd1498Szrj && tree_int_cst_sgn (x) == 1)
67438fd1498Szrj /* testsuite/.../ssa-chrec-38.c. */
67538fd1498Szrj res = chrec_convert (type, chrec_evaluate (var, chrec, x, 0), NULL);
67638fd1498Szrj else
67738fd1498Szrj res = chrec_dont_know;
67838fd1498Szrj break;
67938fd1498Szrj
68038fd1498Szrj CASE_CONVERT:
68138fd1498Szrj res = chrec_convert (TREE_TYPE (chrec),
68238fd1498Szrj chrec_apply (var, TREE_OPERAND (chrec, 0), x),
68338fd1498Szrj NULL);
68438fd1498Szrj break;
68538fd1498Szrj
68638fd1498Szrj default:
68738fd1498Szrj res = chrec;
68838fd1498Szrj break;
68938fd1498Szrj }
69038fd1498Szrj
69138fd1498Szrj if (dump_file && (dump_flags & TDF_SCEV))
69238fd1498Szrj {
69338fd1498Szrj fprintf (dump_file, " (varying_loop = %d\n", var);
69438fd1498Szrj fprintf (dump_file, ")\n (chrec = ");
69538fd1498Szrj print_generic_expr (dump_file, chrec);
69638fd1498Szrj fprintf (dump_file, ")\n (x = ");
69738fd1498Szrj print_generic_expr (dump_file, x);
69838fd1498Szrj fprintf (dump_file, ")\n (res = ");
69938fd1498Szrj print_generic_expr (dump_file, res);
70038fd1498Szrj fprintf (dump_file, "))\n");
70138fd1498Szrj }
70238fd1498Szrj
70338fd1498Szrj return res;
70438fd1498Szrj }
70538fd1498Szrj
70638fd1498Szrj /* For a given CHREC and an induction variable map IV_MAP that maps
70738fd1498Szrj (loop->num, expr) for every loop number of the current_loops an
70838fd1498Szrj expression, calls chrec_apply when the expression is not NULL. */
70938fd1498Szrj
71038fd1498Szrj tree
chrec_apply_map(tree chrec,vec<tree> iv_map)71138fd1498Szrj chrec_apply_map (tree chrec, vec<tree> iv_map)
71238fd1498Szrj {
71338fd1498Szrj int i;
71438fd1498Szrj tree expr;
71538fd1498Szrj
71638fd1498Szrj FOR_EACH_VEC_ELT (iv_map, i, expr)
71738fd1498Szrj if (expr)
71838fd1498Szrj chrec = chrec_apply (i, chrec, expr);
71938fd1498Szrj
72038fd1498Szrj return chrec;
72138fd1498Szrj }
72238fd1498Szrj
72338fd1498Szrj /* Replaces the initial condition in CHREC with INIT_COND. */
72438fd1498Szrj
72538fd1498Szrj tree
chrec_replace_initial_condition(tree chrec,tree init_cond)72638fd1498Szrj chrec_replace_initial_condition (tree chrec,
72738fd1498Szrj tree init_cond)
72838fd1498Szrj {
72938fd1498Szrj if (automatically_generated_chrec_p (chrec))
73038fd1498Szrj return chrec;
73138fd1498Szrj
73238fd1498Szrj gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
73338fd1498Szrj
73438fd1498Szrj switch (TREE_CODE (chrec))
73538fd1498Szrj {
73638fd1498Szrj case POLYNOMIAL_CHREC:
73738fd1498Szrj return build_polynomial_chrec
73838fd1498Szrj (CHREC_VARIABLE (chrec),
73938fd1498Szrj chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
74038fd1498Szrj CHREC_RIGHT (chrec));
74138fd1498Szrj
74238fd1498Szrj default:
74338fd1498Szrj return init_cond;
74438fd1498Szrj }
74538fd1498Szrj }
74638fd1498Szrj
74738fd1498Szrj /* Returns the initial condition of a given CHREC. */
74838fd1498Szrj
74938fd1498Szrj tree
initial_condition(tree chrec)75038fd1498Szrj initial_condition (tree chrec)
75138fd1498Szrj {
75238fd1498Szrj if (automatically_generated_chrec_p (chrec))
75338fd1498Szrj return chrec;
75438fd1498Szrj
75538fd1498Szrj if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
75638fd1498Szrj return initial_condition (CHREC_LEFT (chrec));
75738fd1498Szrj else
75838fd1498Szrj return chrec;
75938fd1498Szrj }
76038fd1498Szrj
76138fd1498Szrj /* Returns a univariate function that represents the evolution in
76238fd1498Szrj LOOP_NUM. Mask the evolution of any other loop. */
76338fd1498Szrj
76438fd1498Szrj tree
hide_evolution_in_other_loops_than_loop(tree chrec,unsigned loop_num)76538fd1498Szrj hide_evolution_in_other_loops_than_loop (tree chrec,
76638fd1498Szrj unsigned loop_num)
76738fd1498Szrj {
76838fd1498Szrj struct loop *loop = get_loop (cfun, loop_num), *chloop;
76938fd1498Szrj if (automatically_generated_chrec_p (chrec))
77038fd1498Szrj return chrec;
77138fd1498Szrj
77238fd1498Szrj switch (TREE_CODE (chrec))
77338fd1498Szrj {
77438fd1498Szrj case POLYNOMIAL_CHREC:
77538fd1498Szrj chloop = get_chrec_loop (chrec);
77638fd1498Szrj
77738fd1498Szrj if (chloop == loop)
77838fd1498Szrj return build_polynomial_chrec
77938fd1498Szrj (loop_num,
78038fd1498Szrj hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
78138fd1498Szrj loop_num),
78238fd1498Szrj CHREC_RIGHT (chrec));
78338fd1498Szrj
78438fd1498Szrj else if (flow_loop_nested_p (chloop, loop))
78538fd1498Szrj /* There is no evolution in this loop. */
78638fd1498Szrj return initial_condition (chrec);
78738fd1498Szrj
78838fd1498Szrj else if (flow_loop_nested_p (loop, chloop))
78938fd1498Szrj return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
79038fd1498Szrj loop_num);
79138fd1498Szrj
79238fd1498Szrj else
79338fd1498Szrj return chrec_dont_know;
79438fd1498Szrj
79538fd1498Szrj default:
79638fd1498Szrj return chrec;
79738fd1498Szrj }
79838fd1498Szrj }
79938fd1498Szrj
80038fd1498Szrj /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
80138fd1498Szrj true, otherwise returns the initial condition in LOOP_NUM. */
80238fd1498Szrj
80338fd1498Szrj static tree
chrec_component_in_loop_num(tree chrec,unsigned loop_num,bool right)80438fd1498Szrj chrec_component_in_loop_num (tree chrec,
80538fd1498Szrj unsigned loop_num,
80638fd1498Szrj bool right)
80738fd1498Szrj {
80838fd1498Szrj tree component;
80938fd1498Szrj struct loop *loop = get_loop (cfun, loop_num), *chloop;
81038fd1498Szrj
81138fd1498Szrj if (automatically_generated_chrec_p (chrec))
81238fd1498Szrj return chrec;
81338fd1498Szrj
81438fd1498Szrj switch (TREE_CODE (chrec))
81538fd1498Szrj {
81638fd1498Szrj case POLYNOMIAL_CHREC:
81738fd1498Szrj chloop = get_chrec_loop (chrec);
81838fd1498Szrj
81938fd1498Szrj if (chloop == loop)
82038fd1498Szrj {
82138fd1498Szrj if (right)
82238fd1498Szrj component = CHREC_RIGHT (chrec);
82338fd1498Szrj else
82438fd1498Szrj component = CHREC_LEFT (chrec);
82538fd1498Szrj
82638fd1498Szrj if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
82738fd1498Szrj || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
82838fd1498Szrj return component;
82938fd1498Szrj
83038fd1498Szrj else
83138fd1498Szrj return build_polynomial_chrec
83238fd1498Szrj (loop_num,
83338fd1498Szrj chrec_component_in_loop_num (CHREC_LEFT (chrec),
83438fd1498Szrj loop_num,
83538fd1498Szrj right),
83638fd1498Szrj component);
83738fd1498Szrj }
83838fd1498Szrj
83938fd1498Szrj else if (flow_loop_nested_p (chloop, loop))
84038fd1498Szrj /* There is no evolution part in this loop. */
84138fd1498Szrj return NULL_TREE;
84238fd1498Szrj
84338fd1498Szrj else
84438fd1498Szrj {
84538fd1498Szrj gcc_assert (flow_loop_nested_p (loop, chloop));
84638fd1498Szrj return chrec_component_in_loop_num (CHREC_LEFT (chrec),
84738fd1498Szrj loop_num,
84838fd1498Szrj right);
84938fd1498Szrj }
85038fd1498Szrj
85138fd1498Szrj default:
85238fd1498Szrj if (right)
85338fd1498Szrj return NULL_TREE;
85438fd1498Szrj else
85538fd1498Szrj return chrec;
85638fd1498Szrj }
85738fd1498Szrj }
85838fd1498Szrj
85938fd1498Szrj /* Returns the evolution part in LOOP_NUM. Example: the call
86038fd1498Szrj evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
86138fd1498Szrj {1, +, 2}_1 */
86238fd1498Szrj
86338fd1498Szrj tree
evolution_part_in_loop_num(tree chrec,unsigned loop_num)86438fd1498Szrj evolution_part_in_loop_num (tree chrec,
86538fd1498Szrj unsigned loop_num)
86638fd1498Szrj {
86738fd1498Szrj return chrec_component_in_loop_num (chrec, loop_num, true);
86838fd1498Szrj }
86938fd1498Szrj
87038fd1498Szrj /* Returns the initial condition in LOOP_NUM. Example: the call
87138fd1498Szrj initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
87238fd1498Szrj {0, +, 1}_1 */
87338fd1498Szrj
87438fd1498Szrj tree
initial_condition_in_loop_num(tree chrec,unsigned loop_num)87538fd1498Szrj initial_condition_in_loop_num (tree chrec,
87638fd1498Szrj unsigned loop_num)
87738fd1498Szrj {
87838fd1498Szrj return chrec_component_in_loop_num (chrec, loop_num, false);
87938fd1498Szrj }
88038fd1498Szrj
88138fd1498Szrj /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
88238fd1498Szrj This function is essentially used for setting the evolution to
88338fd1498Szrj chrec_dont_know, for example after having determined that it is
88438fd1498Szrj impossible to say how many times a loop will execute. */
88538fd1498Szrj
88638fd1498Szrj tree
reset_evolution_in_loop(unsigned loop_num,tree chrec,tree new_evol)88738fd1498Szrj reset_evolution_in_loop (unsigned loop_num,
88838fd1498Szrj tree chrec,
88938fd1498Szrj tree new_evol)
89038fd1498Szrj {
89138fd1498Szrj struct loop *loop = get_loop (cfun, loop_num);
89238fd1498Szrj
89338fd1498Szrj if (POINTER_TYPE_P (chrec_type (chrec)))
89438fd1498Szrj gcc_assert (ptrofftype_p (chrec_type (new_evol)));
89538fd1498Szrj else
89638fd1498Szrj gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
89738fd1498Szrj
89838fd1498Szrj if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
89938fd1498Szrj && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
90038fd1498Szrj {
90138fd1498Szrj tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
90238fd1498Szrj new_evol);
90338fd1498Szrj tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
90438fd1498Szrj new_evol);
90538fd1498Szrj return build_polynomial_chrec (CHREC_VARIABLE (chrec), left, right);
90638fd1498Szrj }
90738fd1498Szrj
90838fd1498Szrj while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
90938fd1498Szrj && CHREC_VARIABLE (chrec) == loop_num)
91038fd1498Szrj chrec = CHREC_LEFT (chrec);
91138fd1498Szrj
91238fd1498Szrj return build_polynomial_chrec (loop_num, chrec, new_evol);
91338fd1498Szrj }
91438fd1498Szrj
91538fd1498Szrj /* Merges two evolution functions that were found by following two
91638fd1498Szrj alternate paths of a conditional expression. */
91738fd1498Szrj
91838fd1498Szrj tree
chrec_merge(tree chrec1,tree chrec2)91938fd1498Szrj chrec_merge (tree chrec1,
92038fd1498Szrj tree chrec2)
92138fd1498Szrj {
92238fd1498Szrj if (chrec1 == chrec_dont_know
92338fd1498Szrj || chrec2 == chrec_dont_know)
92438fd1498Szrj return chrec_dont_know;
92538fd1498Szrj
92638fd1498Szrj if (chrec1 == chrec_known
92738fd1498Szrj || chrec2 == chrec_known)
92838fd1498Szrj return chrec_known;
92938fd1498Szrj
93038fd1498Szrj if (chrec1 == chrec_not_analyzed_yet)
93138fd1498Szrj return chrec2;
93238fd1498Szrj if (chrec2 == chrec_not_analyzed_yet)
93338fd1498Szrj return chrec1;
93438fd1498Szrj
93538fd1498Szrj if (eq_evolutions_p (chrec1, chrec2))
93638fd1498Szrj return chrec1;
93738fd1498Szrj
93838fd1498Szrj return chrec_dont_know;
93938fd1498Szrj }
94038fd1498Szrj
94138fd1498Szrj
94238fd1498Szrj
94338fd1498Szrj /* Observers. */
94438fd1498Szrj
94538fd1498Szrj /* Helper function for is_multivariate_chrec. */
94638fd1498Szrj
94738fd1498Szrj static bool
is_multivariate_chrec_rec(const_tree chrec,unsigned int rec_var)94838fd1498Szrj is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
94938fd1498Szrj {
95038fd1498Szrj if (chrec == NULL_TREE)
95138fd1498Szrj return false;
95238fd1498Szrj
95338fd1498Szrj if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
95438fd1498Szrj {
95538fd1498Szrj if (CHREC_VARIABLE (chrec) != rec_var)
95638fd1498Szrj return true;
95738fd1498Szrj else
95838fd1498Szrj return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
95938fd1498Szrj || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
96038fd1498Szrj }
96138fd1498Szrj else
96238fd1498Szrj return false;
96338fd1498Szrj }
96438fd1498Szrj
96538fd1498Szrj /* Determine whether the given chrec is multivariate or not. */
96638fd1498Szrj
96738fd1498Szrj bool
is_multivariate_chrec(const_tree chrec)96838fd1498Szrj is_multivariate_chrec (const_tree chrec)
96938fd1498Szrj {
97038fd1498Szrj if (chrec == NULL_TREE)
97138fd1498Szrj return false;
97238fd1498Szrj
97338fd1498Szrj if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
97438fd1498Szrj return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
97538fd1498Szrj CHREC_VARIABLE (chrec))
97638fd1498Szrj || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
97738fd1498Szrj CHREC_VARIABLE (chrec)));
97838fd1498Szrj else
97938fd1498Szrj return false;
98038fd1498Szrj }
98138fd1498Szrj
98238fd1498Szrj /* Determines whether the chrec contains symbolic names or not. */
98338fd1498Szrj
98438fd1498Szrj bool
chrec_contains_symbols(const_tree chrec)98538fd1498Szrj chrec_contains_symbols (const_tree chrec)
98638fd1498Szrj {
98738fd1498Szrj int i, n;
98838fd1498Szrj
98938fd1498Szrj if (chrec == NULL_TREE)
99038fd1498Szrj return false;
99138fd1498Szrj
99238fd1498Szrj if (TREE_CODE (chrec) == SSA_NAME
99338fd1498Szrj || VAR_P (chrec)
99438fd1498Szrj || TREE_CODE (chrec) == POLY_INT_CST
99538fd1498Szrj || TREE_CODE (chrec) == PARM_DECL
99638fd1498Szrj || TREE_CODE (chrec) == FUNCTION_DECL
99738fd1498Szrj || TREE_CODE (chrec) == LABEL_DECL
99838fd1498Szrj || TREE_CODE (chrec) == RESULT_DECL
99938fd1498Szrj || TREE_CODE (chrec) == FIELD_DECL)
100038fd1498Szrj return true;
100138fd1498Szrj
100238fd1498Szrj n = TREE_OPERAND_LENGTH (chrec);
100338fd1498Szrj for (i = 0; i < n; i++)
100438fd1498Szrj if (chrec_contains_symbols (TREE_OPERAND (chrec, i)))
100538fd1498Szrj return true;
100638fd1498Szrj return false;
100738fd1498Szrj }
100838fd1498Szrj
100938fd1498Szrj /* Determines whether the chrec contains undetermined coefficients. */
101038fd1498Szrj
101138fd1498Szrj bool
chrec_contains_undetermined(const_tree chrec)101238fd1498Szrj chrec_contains_undetermined (const_tree chrec)
101338fd1498Szrj {
101438fd1498Szrj int i, n;
101538fd1498Szrj
101638fd1498Szrj if (chrec == chrec_dont_know)
101738fd1498Szrj return true;
101838fd1498Szrj
101938fd1498Szrj if (chrec == NULL_TREE)
102038fd1498Szrj return false;
102138fd1498Szrj
102238fd1498Szrj n = TREE_OPERAND_LENGTH (chrec);
102338fd1498Szrj for (i = 0; i < n; i++)
102438fd1498Szrj if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)))
102538fd1498Szrj return true;
102638fd1498Szrj return false;
102738fd1498Szrj }
102838fd1498Szrj
102938fd1498Szrj /* Determines whether the tree EXPR contains chrecs, and increment
103038fd1498Szrj SIZE if it is not a NULL pointer by an estimation of the depth of
103138fd1498Szrj the tree. */
103238fd1498Szrj
103338fd1498Szrj bool
tree_contains_chrecs(const_tree expr,int * size)103438fd1498Szrj tree_contains_chrecs (const_tree expr, int *size)
103538fd1498Szrj {
103638fd1498Szrj int i, n;
103738fd1498Szrj
103838fd1498Szrj if (expr == NULL_TREE)
103938fd1498Szrj return false;
104038fd1498Szrj
104138fd1498Szrj if (size)
104238fd1498Szrj (*size)++;
104338fd1498Szrj
104438fd1498Szrj if (tree_is_chrec (expr))
104538fd1498Szrj return true;
104638fd1498Szrj
104738fd1498Szrj n = TREE_OPERAND_LENGTH (expr);
104838fd1498Szrj for (i = 0; i < n; i++)
104938fd1498Szrj if (tree_contains_chrecs (TREE_OPERAND (expr, i), size))
105038fd1498Szrj return true;
105138fd1498Szrj return false;
105238fd1498Szrj }
105338fd1498Szrj
105438fd1498Szrj /* Recursive helper function. */
105538fd1498Szrj
105638fd1498Szrj static bool
evolution_function_is_invariant_rec_p(tree chrec,int loopnum)105738fd1498Szrj evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
105838fd1498Szrj {
105938fd1498Szrj if (evolution_function_is_constant_p (chrec))
106038fd1498Szrj return true;
106138fd1498Szrj
106238fd1498Szrj if (TREE_CODE (chrec) == SSA_NAME
106338fd1498Szrj && (loopnum == 0
106438fd1498Szrj || expr_invariant_in_loop_p (get_loop (cfun, loopnum), chrec)))
106538fd1498Szrj return true;
106638fd1498Szrj
106738fd1498Szrj if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
106838fd1498Szrj {
106938fd1498Szrj if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
107038fd1498Szrj || flow_loop_nested_p (get_loop (cfun, loopnum),
107138fd1498Szrj get_chrec_loop (chrec))
107238fd1498Szrj || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
107338fd1498Szrj loopnum)
107438fd1498Szrj || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
107538fd1498Szrj loopnum))
107638fd1498Szrj return false;
107738fd1498Szrj return true;
107838fd1498Szrj }
107938fd1498Szrj
108038fd1498Szrj switch (TREE_OPERAND_LENGTH (chrec))
108138fd1498Szrj {
108238fd1498Szrj case 2:
108338fd1498Szrj if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
108438fd1498Szrj loopnum))
108538fd1498Szrj return false;
108638fd1498Szrj /* FALLTHRU */
108738fd1498Szrj
108838fd1498Szrj case 1:
108938fd1498Szrj if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
109038fd1498Szrj loopnum))
109138fd1498Szrj return false;
109238fd1498Szrj return true;
109338fd1498Szrj
109438fd1498Szrj default:
109538fd1498Szrj return false;
109638fd1498Szrj }
109738fd1498Szrj
109838fd1498Szrj return false;
109938fd1498Szrj }
110038fd1498Szrj
110138fd1498Szrj /* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
110238fd1498Szrj
110338fd1498Szrj bool
evolution_function_is_invariant_p(tree chrec,int loopnum)110438fd1498Szrj evolution_function_is_invariant_p (tree chrec, int loopnum)
110538fd1498Szrj {
110638fd1498Szrj return evolution_function_is_invariant_rec_p (chrec, loopnum);
110738fd1498Szrj }
110838fd1498Szrj
110938fd1498Szrj /* Determine whether the given tree is an affine multivariate
111038fd1498Szrj evolution. */
111138fd1498Szrj
111238fd1498Szrj bool
evolution_function_is_affine_multivariate_p(const_tree chrec,int loopnum)111338fd1498Szrj evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
111438fd1498Szrj {
111538fd1498Szrj if (chrec == NULL_TREE)
111638fd1498Szrj return false;
111738fd1498Szrj
111838fd1498Szrj switch (TREE_CODE (chrec))
111938fd1498Szrj {
112038fd1498Szrj case POLYNOMIAL_CHREC:
112138fd1498Szrj if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
112238fd1498Szrj {
112338fd1498Szrj if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
112438fd1498Szrj return true;
112538fd1498Szrj else
112638fd1498Szrj {
112738fd1498Szrj if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
112838fd1498Szrj && CHREC_VARIABLE (CHREC_RIGHT (chrec))
112938fd1498Szrj != CHREC_VARIABLE (chrec)
113038fd1498Szrj && evolution_function_is_affine_multivariate_p
113138fd1498Szrj (CHREC_RIGHT (chrec), loopnum))
113238fd1498Szrj return true;
113338fd1498Szrj else
113438fd1498Szrj return false;
113538fd1498Szrj }
113638fd1498Szrj }
113738fd1498Szrj else
113838fd1498Szrj {
113938fd1498Szrj if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
114038fd1498Szrj && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
114138fd1498Szrj && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
114238fd1498Szrj && evolution_function_is_affine_multivariate_p
114338fd1498Szrj (CHREC_LEFT (chrec), loopnum))
114438fd1498Szrj return true;
114538fd1498Szrj else
114638fd1498Szrj return false;
114738fd1498Szrj }
114838fd1498Szrj
114938fd1498Szrj default:
115038fd1498Szrj return false;
115138fd1498Szrj }
115238fd1498Szrj }
115338fd1498Szrj
115438fd1498Szrj /* Determine whether the given tree is a function in zero or one
115538fd1498Szrj variables. */
115638fd1498Szrj
115738fd1498Szrj bool
evolution_function_is_univariate_p(const_tree chrec)115838fd1498Szrj evolution_function_is_univariate_p (const_tree chrec)
115938fd1498Szrj {
116038fd1498Szrj if (chrec == NULL_TREE)
116138fd1498Szrj return true;
116238fd1498Szrj
116338fd1498Szrj switch (TREE_CODE (chrec))
116438fd1498Szrj {
116538fd1498Szrj case POLYNOMIAL_CHREC:
116638fd1498Szrj switch (TREE_CODE (CHREC_LEFT (chrec)))
116738fd1498Szrj {
116838fd1498Szrj case POLYNOMIAL_CHREC:
116938fd1498Szrj if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
117038fd1498Szrj return false;
117138fd1498Szrj if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
117238fd1498Szrj return false;
117338fd1498Szrj break;
117438fd1498Szrj
117538fd1498Szrj default:
117638fd1498Szrj if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL))
117738fd1498Szrj return false;
117838fd1498Szrj break;
117938fd1498Szrj }
118038fd1498Szrj
118138fd1498Szrj switch (TREE_CODE (CHREC_RIGHT (chrec)))
118238fd1498Szrj {
118338fd1498Szrj case POLYNOMIAL_CHREC:
118438fd1498Szrj if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
118538fd1498Szrj return false;
118638fd1498Szrj if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
118738fd1498Szrj return false;
118838fd1498Szrj break;
118938fd1498Szrj
119038fd1498Szrj default:
119138fd1498Szrj if (tree_contains_chrecs (CHREC_RIGHT (chrec), NULL))
119238fd1498Szrj return false;
119338fd1498Szrj break;
119438fd1498Szrj }
119538fd1498Szrj return true;
119638fd1498Szrj
119738fd1498Szrj default:
119838fd1498Szrj return true;
119938fd1498Szrj }
120038fd1498Szrj }
120138fd1498Szrj
120238fd1498Szrj /* Returns the number of variables of CHREC. Example: the call
120338fd1498Szrj nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
120438fd1498Szrj
120538fd1498Szrj unsigned
nb_vars_in_chrec(tree chrec)120638fd1498Szrj nb_vars_in_chrec (tree chrec)
120738fd1498Szrj {
120838fd1498Szrj if (chrec == NULL_TREE)
120938fd1498Szrj return 0;
121038fd1498Szrj
121138fd1498Szrj switch (TREE_CODE (chrec))
121238fd1498Szrj {
121338fd1498Szrj case POLYNOMIAL_CHREC:
121438fd1498Szrj return 1 + nb_vars_in_chrec
121538fd1498Szrj (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
121638fd1498Szrj
121738fd1498Szrj default:
121838fd1498Szrj return 0;
121938fd1498Szrj }
122038fd1498Szrj }
122138fd1498Szrj
122238fd1498Szrj /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
122338fd1498Szrj the scev corresponds to. AT_STMT is the statement at that the scev is
122438fd1498Szrj evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume
122538fd1498Szrj that the rules for overflow of the given language apply (e.g., that signed
122638fd1498Szrj arithmetics in C does not overflow) -- i.e., to use them to avoid
122738fd1498Szrj unnecessary tests, but also to enforce that the result follows them.
122838fd1498Szrj FROM is the source variable converted if it's not NULL. Returns true if
122938fd1498Szrj the conversion succeeded, false otherwise. */
123038fd1498Szrj
123138fd1498Szrj bool
convert_affine_scev(struct loop * loop,tree type,tree * base,tree * step,gimple * at_stmt,bool use_overflow_semantics,tree from)123238fd1498Szrj convert_affine_scev (struct loop *loop, tree type,
123338fd1498Szrj tree *base, tree *step, gimple *at_stmt,
123438fd1498Szrj bool use_overflow_semantics, tree from)
123538fd1498Szrj {
123638fd1498Szrj tree ct = TREE_TYPE (*step);
123738fd1498Szrj bool enforce_overflow_semantics;
123838fd1498Szrj bool must_check_src_overflow, must_check_rslt_overflow;
123938fd1498Szrj tree new_base, new_step;
124038fd1498Szrj tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
124138fd1498Szrj
124238fd1498Szrj /* In general,
124338fd1498Szrj (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
124438fd1498Szrj but we must check some assumptions.
124538fd1498Szrj
124638fd1498Szrj 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
124738fd1498Szrj of CT is smaller than the precision of TYPE. For example, when we
124838fd1498Szrj cast unsigned char [254, +, 1] to unsigned, the values on left side
124938fd1498Szrj are 254, 255, 0, 1, ..., but those on the right side are
125038fd1498Szrj 254, 255, 256, 257, ...
125138fd1498Szrj 2) In case that we must also preserve the fact that signed ivs do not
125238fd1498Szrj overflow, we must additionally check that the new iv does not wrap.
125338fd1498Szrj For example, unsigned char [125, +, 1] casted to signed char could
125438fd1498Szrj become a wrapping variable with values 125, 126, 127, -128, -127, ...,
125538fd1498Szrj which would confuse optimizers that assume that this does not
125638fd1498Szrj happen. */
125738fd1498Szrj must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
125838fd1498Szrj
125938fd1498Szrj enforce_overflow_semantics = (use_overflow_semantics
126038fd1498Szrj && nowrap_type_p (type));
126138fd1498Szrj if (enforce_overflow_semantics)
126238fd1498Szrj {
126338fd1498Szrj /* We can avoid checking whether the result overflows in the following
126438fd1498Szrj cases:
126538fd1498Szrj
126638fd1498Szrj -- must_check_src_overflow is true, and the range of TYPE is superset
126738fd1498Szrj of the range of CT -- i.e., in all cases except if CT signed and
126838fd1498Szrj TYPE unsigned.
126938fd1498Szrj -- both CT and TYPE have the same precision and signedness, and we
127038fd1498Szrj verify instead that the source does not overflow (this may be
127138fd1498Szrj easier than verifying it for the result, as we may use the
127238fd1498Szrj information about the semantics of overflow in CT). */
127338fd1498Szrj if (must_check_src_overflow)
127438fd1498Szrj {
127538fd1498Szrj if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
127638fd1498Szrj must_check_rslt_overflow = true;
127738fd1498Szrj else
127838fd1498Szrj must_check_rslt_overflow = false;
127938fd1498Szrj }
128038fd1498Szrj else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
128138fd1498Szrj && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
128238fd1498Szrj {
128338fd1498Szrj must_check_rslt_overflow = false;
128438fd1498Szrj must_check_src_overflow = true;
128538fd1498Szrj }
128638fd1498Szrj else
128738fd1498Szrj must_check_rslt_overflow = true;
128838fd1498Szrj }
128938fd1498Szrj else
129038fd1498Szrj must_check_rslt_overflow = false;
129138fd1498Szrj
129238fd1498Szrj if (must_check_src_overflow
129338fd1498Szrj && scev_probably_wraps_p (from, *base, *step, at_stmt, loop,
129438fd1498Szrj use_overflow_semantics))
129538fd1498Szrj return false;
129638fd1498Szrj
129738fd1498Szrj new_base = chrec_convert (type, *base, at_stmt, use_overflow_semantics);
129838fd1498Szrj /* The step must be sign extended, regardless of the signedness
129938fd1498Szrj of CT and TYPE. This only needs to be handled specially when
130038fd1498Szrj CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
130138fd1498Szrj (with values 100, 99, 98, ...) from becoming signed or unsigned
130238fd1498Szrj [100, +, 255] with values 100, 355, ...; the sign-extension is
130338fd1498Szrj performed by default when CT is signed. */
130438fd1498Szrj new_step = *step;
130538fd1498Szrj if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
130638fd1498Szrj {
130738fd1498Szrj tree signed_ct = build_nonstandard_integer_type (TYPE_PRECISION (ct), 0);
130838fd1498Szrj new_step = chrec_convert (signed_ct, new_step, at_stmt,
130938fd1498Szrj use_overflow_semantics);
131038fd1498Szrj }
131138fd1498Szrj new_step = chrec_convert (step_type, new_step, at_stmt,
131238fd1498Szrj use_overflow_semantics);
131338fd1498Szrj
131438fd1498Szrj if (automatically_generated_chrec_p (new_base)
131538fd1498Szrj || automatically_generated_chrec_p (new_step))
131638fd1498Szrj return false;
131738fd1498Szrj
131838fd1498Szrj if (must_check_rslt_overflow
131938fd1498Szrj /* Note that in this case we cannot use the fact that signed variables
132038fd1498Szrj do not overflow, as this is what we are verifying for the new iv. */
132138fd1498Szrj && scev_probably_wraps_p (NULL_TREE, new_base, new_step,
132238fd1498Szrj at_stmt, loop, false))
132338fd1498Szrj return false;
132438fd1498Szrj
132538fd1498Szrj *base = new_base;
132638fd1498Szrj *step = new_step;
132738fd1498Szrj return true;
132838fd1498Szrj }
132938fd1498Szrj
133038fd1498Szrj
133138fd1498Szrj /* Convert CHREC for the right hand side of a CHREC.
133238fd1498Szrj The increment for a pointer type is always sizetype. */
133338fd1498Szrj
133438fd1498Szrj tree
chrec_convert_rhs(tree type,tree chrec,gimple * at_stmt)133538fd1498Szrj chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt)
133638fd1498Szrj {
133738fd1498Szrj if (POINTER_TYPE_P (type))
133838fd1498Szrj type = sizetype;
133938fd1498Szrj
134038fd1498Szrj return chrec_convert (type, chrec, at_stmt);
134138fd1498Szrj }
134238fd1498Szrj
134338fd1498Szrj /* Convert CHREC to TYPE. When the analyzer knows the context in
134438fd1498Szrj which the CHREC is built, it sets AT_STMT to the statement that
134538fd1498Szrj contains the definition of the analyzed variable, otherwise the
134638fd1498Szrj conversion is less accurate: the information is used for
134738fd1498Szrj determining a more accurate estimation of the number of iterations.
134838fd1498Szrj By default AT_STMT could be safely set to NULL_TREE.
134938fd1498Szrj
135038fd1498Szrj USE_OVERFLOW_SEMANTICS is true if this function should assume that
135138fd1498Szrj the rules for overflow of the given language apply (e.g., that signed
135238fd1498Szrj arithmetics in C does not overflow) -- i.e., to use them to avoid
135338fd1498Szrj unnecessary tests, but also to enforce that the result follows them.
135438fd1498Szrj
135538fd1498Szrj FROM is the source variable converted if it's not NULL. */
135638fd1498Szrj
135738fd1498Szrj static tree
chrec_convert_1(tree type,tree chrec,gimple * at_stmt,bool use_overflow_semantics,tree from)135838fd1498Szrj chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
135938fd1498Szrj bool use_overflow_semantics, tree from)
136038fd1498Szrj {
136138fd1498Szrj tree ct, res;
136238fd1498Szrj tree base, step;
136338fd1498Szrj struct loop *loop;
136438fd1498Szrj
136538fd1498Szrj if (automatically_generated_chrec_p (chrec))
136638fd1498Szrj return chrec;
136738fd1498Szrj
136838fd1498Szrj ct = chrec_type (chrec);
136938fd1498Szrj if (useless_type_conversion_p (type, ct))
137038fd1498Szrj return chrec;
137138fd1498Szrj
137238fd1498Szrj if (!evolution_function_is_affine_p (chrec))
137338fd1498Szrj goto keep_cast;
137438fd1498Szrj
137538fd1498Szrj loop = get_chrec_loop (chrec);
137638fd1498Szrj base = CHREC_LEFT (chrec);
137738fd1498Szrj step = CHREC_RIGHT (chrec);
137838fd1498Szrj
137938fd1498Szrj if (convert_affine_scev (loop, type, &base, &step, at_stmt,
138038fd1498Szrj use_overflow_semantics, from))
138138fd1498Szrj return build_polynomial_chrec (loop->num, base, step);
138238fd1498Szrj
138338fd1498Szrj /* If we cannot propagate the cast inside the chrec, just keep the cast. */
138438fd1498Szrj keep_cast:
138538fd1498Szrj /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
138638fd1498Szrj may be more expensive. We do want to perform this optimization here
138738fd1498Szrj though for canonicalization reasons. */
138838fd1498Szrj if (use_overflow_semantics
138938fd1498Szrj && (TREE_CODE (chrec) == PLUS_EXPR
139038fd1498Szrj || TREE_CODE (chrec) == MINUS_EXPR)
139138fd1498Szrj && TREE_CODE (type) == INTEGER_TYPE
139238fd1498Szrj && TREE_CODE (ct) == INTEGER_TYPE
139338fd1498Szrj && TYPE_PRECISION (type) > TYPE_PRECISION (ct)
139438fd1498Szrj && TYPE_OVERFLOW_UNDEFINED (ct))
139538fd1498Szrj res = fold_build2 (TREE_CODE (chrec), type,
139638fd1498Szrj fold_convert (type, TREE_OPERAND (chrec, 0)),
139738fd1498Szrj fold_convert (type, TREE_OPERAND (chrec, 1)));
139838fd1498Szrj /* Similar perform the trick that (signed char)((int)x + 2) can be
139938fd1498Szrj narrowed to (signed char)((unsigned char)x + 2). */
140038fd1498Szrj else if (use_overflow_semantics
140138fd1498Szrj && TREE_CODE (chrec) == POLYNOMIAL_CHREC
140238fd1498Szrj && TREE_CODE (ct) == INTEGER_TYPE
140338fd1498Szrj && TREE_CODE (type) == INTEGER_TYPE
140438fd1498Szrj && TYPE_OVERFLOW_UNDEFINED (type)
140538fd1498Szrj && TYPE_PRECISION (type) < TYPE_PRECISION (ct))
140638fd1498Szrj {
140738fd1498Szrj tree utype = unsigned_type_for (type);
140838fd1498Szrj res = build_polynomial_chrec (CHREC_VARIABLE (chrec),
140938fd1498Szrj fold_convert (utype,
141038fd1498Szrj CHREC_LEFT (chrec)),
141138fd1498Szrj fold_convert (utype,
141238fd1498Szrj CHREC_RIGHT (chrec)));
141338fd1498Szrj res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
141438fd1498Szrj }
141538fd1498Szrj else
141638fd1498Szrj res = fold_convert (type, chrec);
141738fd1498Szrj
141838fd1498Szrj /* Don't propagate overflows. */
141938fd1498Szrj if (CONSTANT_CLASS_P (res))
142038fd1498Szrj TREE_OVERFLOW (res) = 0;
142138fd1498Szrj
142238fd1498Szrj /* But reject constants that don't fit in their type after conversion.
142338fd1498Szrj This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
142438fd1498Szrj natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
142538fd1498Szrj and can cause problems later when computing niters of loops. Note
142638fd1498Szrj that we don't do the check before converting because we don't want
142738fd1498Szrj to reject conversions of negative chrecs to unsigned types. */
142838fd1498Szrj if (TREE_CODE (res) == INTEGER_CST
142938fd1498Szrj && TREE_CODE (type) == INTEGER_TYPE
143038fd1498Szrj && !int_fits_type_p (res, type))
143138fd1498Szrj res = chrec_dont_know;
143238fd1498Szrj
143338fd1498Szrj return res;
143438fd1498Szrj }
143538fd1498Szrj
143638fd1498Szrj /* Convert CHREC to TYPE. When the analyzer knows the context in
143738fd1498Szrj which the CHREC is built, it sets AT_STMT to the statement that
143838fd1498Szrj contains the definition of the analyzed variable, otherwise the
143938fd1498Szrj conversion is less accurate: the information is used for
144038fd1498Szrj determining a more accurate estimation of the number of iterations.
144138fd1498Szrj By default AT_STMT could be safely set to NULL_TREE.
144238fd1498Szrj
144338fd1498Szrj The following rule is always true: TREE_TYPE (chrec) ==
144438fd1498Szrj TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
144538fd1498Szrj An example of what could happen when adding two chrecs and the type
144638fd1498Szrj of the CHREC_RIGHT is different than CHREC_LEFT is:
144738fd1498Szrj
144838fd1498Szrj {(uint) 0, +, (uchar) 10} +
144938fd1498Szrj {(uint) 0, +, (uchar) 250}
145038fd1498Szrj
145138fd1498Szrj that would produce a wrong result if CHREC_RIGHT is not (uint):
145238fd1498Szrj
145338fd1498Szrj {(uint) 0, +, (uchar) 4}
145438fd1498Szrj
145538fd1498Szrj instead of
145638fd1498Szrj
145738fd1498Szrj {(uint) 0, +, (uint) 260}
145838fd1498Szrj
145938fd1498Szrj USE_OVERFLOW_SEMANTICS is true if this function should assume that
146038fd1498Szrj the rules for overflow of the given language apply (e.g., that signed
146138fd1498Szrj arithmetics in C does not overflow) -- i.e., to use them to avoid
146238fd1498Szrj unnecessary tests, but also to enforce that the result follows them.
146338fd1498Szrj
146438fd1498Szrj FROM is the source variable converted if it's not NULL. */
146538fd1498Szrj
146638fd1498Szrj tree
chrec_convert(tree type,tree chrec,gimple * at_stmt,bool use_overflow_semantics,tree from)146738fd1498Szrj chrec_convert (tree type, tree chrec, gimple *at_stmt,
146838fd1498Szrj bool use_overflow_semantics, tree from)
146938fd1498Szrj {
147038fd1498Szrj return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from);
147138fd1498Szrj }
147238fd1498Szrj
147338fd1498Szrj /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
147438fd1498Szrj chrec if something else than what chrec_convert would do happens, NULL_TREE
147538fd1498Szrj otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS
147638fd1498Szrj if the result chrec may overflow. */
147738fd1498Szrj
147838fd1498Szrj tree
chrec_convert_aggressive(tree type,tree chrec,bool * fold_conversions)147938fd1498Szrj chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions)
148038fd1498Szrj {
148138fd1498Szrj tree inner_type, left, right, lc, rc, rtype;
148238fd1498Szrj
148338fd1498Szrj gcc_assert (fold_conversions != NULL);
148438fd1498Szrj
148538fd1498Szrj if (automatically_generated_chrec_p (chrec)
148638fd1498Szrj || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
148738fd1498Szrj return NULL_TREE;
148838fd1498Szrj
148938fd1498Szrj inner_type = TREE_TYPE (chrec);
149038fd1498Szrj if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
149138fd1498Szrj return NULL_TREE;
149238fd1498Szrj
149338fd1498Szrj if (useless_type_conversion_p (type, inner_type))
149438fd1498Szrj return NULL_TREE;
149538fd1498Szrj
149638fd1498Szrj if (!*fold_conversions && evolution_function_is_affine_p (chrec))
149738fd1498Szrj {
149838fd1498Szrj tree base, step;
149938fd1498Szrj struct loop *loop;
150038fd1498Szrj
150138fd1498Szrj loop = get_chrec_loop (chrec);
150238fd1498Szrj base = CHREC_LEFT (chrec);
150338fd1498Szrj step = CHREC_RIGHT (chrec);
150438fd1498Szrj if (convert_affine_scev (loop, type, &base, &step, NULL, true))
150538fd1498Szrj return build_polynomial_chrec (loop->num, base, step);
150638fd1498Szrj }
150738fd1498Szrj rtype = POINTER_TYPE_P (type) ? sizetype : type;
150838fd1498Szrj
150938fd1498Szrj left = CHREC_LEFT (chrec);
151038fd1498Szrj right = CHREC_RIGHT (chrec);
151138fd1498Szrj lc = chrec_convert_aggressive (type, left, fold_conversions);
151238fd1498Szrj if (!lc)
151338fd1498Szrj lc = chrec_convert (type, left, NULL);
151438fd1498Szrj rc = chrec_convert_aggressive (rtype, right, fold_conversions);
151538fd1498Szrj if (!rc)
151638fd1498Szrj rc = chrec_convert (rtype, right, NULL);
151738fd1498Szrj
151838fd1498Szrj *fold_conversions = true;
151938fd1498Szrj
152038fd1498Szrj return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
152138fd1498Szrj }
152238fd1498Szrj
152338fd1498Szrj /* Returns true when CHREC0 == CHREC1. */
152438fd1498Szrj
152538fd1498Szrj bool
eq_evolutions_p(const_tree chrec0,const_tree chrec1)152638fd1498Szrj eq_evolutions_p (const_tree chrec0, const_tree chrec1)
152738fd1498Szrj {
152838fd1498Szrj if (chrec0 == NULL_TREE
152938fd1498Szrj || chrec1 == NULL_TREE
153038fd1498Szrj || TREE_CODE (chrec0) != TREE_CODE (chrec1))
153138fd1498Szrj return false;
153238fd1498Szrj
153338fd1498Szrj if (chrec0 == chrec1)
153438fd1498Szrj return true;
153538fd1498Szrj
153638fd1498Szrj if (! types_compatible_p (TREE_TYPE (chrec0), TREE_TYPE (chrec1)))
153738fd1498Szrj return false;
153838fd1498Szrj
153938fd1498Szrj switch (TREE_CODE (chrec0))
154038fd1498Szrj {
154138fd1498Szrj case POLYNOMIAL_CHREC:
154238fd1498Szrj return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
154338fd1498Szrj && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
154438fd1498Szrj && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
154538fd1498Szrj
154638fd1498Szrj case PLUS_EXPR:
154738fd1498Szrj case MULT_EXPR:
154838fd1498Szrj case MINUS_EXPR:
154938fd1498Szrj case POINTER_PLUS_EXPR:
155038fd1498Szrj return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
155138fd1498Szrj TREE_OPERAND (chrec1, 0))
155238fd1498Szrj && eq_evolutions_p (TREE_OPERAND (chrec0, 1),
155338fd1498Szrj TREE_OPERAND (chrec1, 1));
155438fd1498Szrj
155538fd1498Szrj CASE_CONVERT:
155638fd1498Szrj return eq_evolutions_p (TREE_OPERAND (chrec0, 0),
155738fd1498Szrj TREE_OPERAND (chrec1, 0));
155838fd1498Szrj
155938fd1498Szrj default:
156038fd1498Szrj return operand_equal_p (chrec0, chrec1, 0);
156138fd1498Szrj }
156238fd1498Szrj }
156338fd1498Szrj
156438fd1498Szrj /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
156538fd1498Szrj EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
156638fd1498Szrj which of these cases happens. */
156738fd1498Szrj
156838fd1498Szrj enum ev_direction
scev_direction(const_tree chrec)156938fd1498Szrj scev_direction (const_tree chrec)
157038fd1498Szrj {
157138fd1498Szrj const_tree step;
157238fd1498Szrj
157338fd1498Szrj if (!evolution_function_is_affine_p (chrec))
157438fd1498Szrj return EV_DIR_UNKNOWN;
157538fd1498Szrj
157638fd1498Szrj step = CHREC_RIGHT (chrec);
157738fd1498Szrj if (TREE_CODE (step) != INTEGER_CST)
157838fd1498Szrj return EV_DIR_UNKNOWN;
157938fd1498Szrj
158038fd1498Szrj if (tree_int_cst_sign_bit (step))
158138fd1498Szrj return EV_DIR_DECREASES;
158238fd1498Szrj else
158338fd1498Szrj return EV_DIR_GROWS;
158438fd1498Szrj }
158538fd1498Szrj
158638fd1498Szrj /* Iterates over all the components of SCEV, and calls CBCK. */
158738fd1498Szrj
158838fd1498Szrj void
for_each_scev_op(tree * scev,bool (* cbck)(tree *,void *),void * data)158938fd1498Szrj for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
159038fd1498Szrj {
159138fd1498Szrj switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
159238fd1498Szrj {
159338fd1498Szrj case 3:
159438fd1498Szrj for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
159538fd1498Szrj /* FALLTHRU */
159638fd1498Szrj
159738fd1498Szrj case 2:
159838fd1498Szrj for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
159938fd1498Szrj /* FALLTHRU */
160038fd1498Szrj
160138fd1498Szrj case 1:
160238fd1498Szrj for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
160338fd1498Szrj /* FALLTHRU */
160438fd1498Szrj
160538fd1498Szrj default:
160638fd1498Szrj cbck (scev, data);
160738fd1498Szrj break;
160838fd1498Szrj }
160938fd1498Szrj }
161038fd1498Szrj
161138fd1498Szrj /* Returns true when the operation can be part of a linear
161238fd1498Szrj expression. */
161338fd1498Szrj
161438fd1498Szrj static inline bool
operator_is_linear(tree scev)161538fd1498Szrj operator_is_linear (tree scev)
161638fd1498Szrj {
161738fd1498Szrj switch (TREE_CODE (scev))
161838fd1498Szrj {
161938fd1498Szrj case INTEGER_CST:
162038fd1498Szrj case POLYNOMIAL_CHREC:
162138fd1498Szrj case PLUS_EXPR:
162238fd1498Szrj case POINTER_PLUS_EXPR:
162338fd1498Szrj case MULT_EXPR:
162438fd1498Szrj case MINUS_EXPR:
162538fd1498Szrj case NEGATE_EXPR:
162638fd1498Szrj case SSA_NAME:
162738fd1498Szrj case NON_LVALUE_EXPR:
162838fd1498Szrj case BIT_NOT_EXPR:
162938fd1498Szrj CASE_CONVERT:
163038fd1498Szrj return true;
163138fd1498Szrj
163238fd1498Szrj default:
163338fd1498Szrj return false;
163438fd1498Szrj }
163538fd1498Szrj }
163638fd1498Szrj
163738fd1498Szrj /* Return true when SCEV is a linear expression. Linear expressions
163838fd1498Szrj can contain additions, substractions and multiplications.
163938fd1498Szrj Multiplications are restricted to constant scaling: "cst * x". */
164038fd1498Szrj
164138fd1498Szrj bool
scev_is_linear_expression(tree scev)164238fd1498Szrj scev_is_linear_expression (tree scev)
164338fd1498Szrj {
164438fd1498Szrj if (evolution_function_is_constant_p (scev))
164538fd1498Szrj return true;
164638fd1498Szrj
164738fd1498Szrj if (scev == NULL
164838fd1498Szrj || !operator_is_linear (scev))
164938fd1498Szrj return false;
165038fd1498Szrj
165138fd1498Szrj if (TREE_CODE (scev) == MULT_EXPR)
165238fd1498Szrj return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
165338fd1498Szrj && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
165438fd1498Szrj
165538fd1498Szrj if (TREE_CODE (scev) == POLYNOMIAL_CHREC
165638fd1498Szrj && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
165738fd1498Szrj return false;
165838fd1498Szrj
165938fd1498Szrj switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
166038fd1498Szrj {
166138fd1498Szrj case 3:
166238fd1498Szrj return scev_is_linear_expression (TREE_OPERAND (scev, 0))
166338fd1498Szrj && scev_is_linear_expression (TREE_OPERAND (scev, 1))
166438fd1498Szrj && scev_is_linear_expression (TREE_OPERAND (scev, 2));
166538fd1498Szrj
166638fd1498Szrj case 2:
166738fd1498Szrj return scev_is_linear_expression (TREE_OPERAND (scev, 0))
166838fd1498Szrj && scev_is_linear_expression (TREE_OPERAND (scev, 1));
166938fd1498Szrj
167038fd1498Szrj case 1:
167138fd1498Szrj return scev_is_linear_expression (TREE_OPERAND (scev, 0));
167238fd1498Szrj
167338fd1498Szrj case 0:
167438fd1498Szrj return true;
167538fd1498Szrj
167638fd1498Szrj default:
167738fd1498Szrj return false;
167838fd1498Szrj }
167938fd1498Szrj }
168038fd1498Szrj
168138fd1498Szrj /* Determines whether the expression CHREC contains only interger consts
168238fd1498Szrj in the right parts. */
168338fd1498Szrj
168438fd1498Szrj bool
evolution_function_right_is_integer_cst(const_tree chrec)168538fd1498Szrj evolution_function_right_is_integer_cst (const_tree chrec)
168638fd1498Szrj {
168738fd1498Szrj if (chrec == NULL_TREE)
168838fd1498Szrj return false;
168938fd1498Szrj
169038fd1498Szrj switch (TREE_CODE (chrec))
169138fd1498Szrj {
169238fd1498Szrj case INTEGER_CST:
169338fd1498Szrj return true;
169438fd1498Szrj
169538fd1498Szrj case POLYNOMIAL_CHREC:
169638fd1498Szrj return TREE_CODE (CHREC_RIGHT (chrec)) == INTEGER_CST
169738fd1498Szrj && (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
169838fd1498Szrj || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)));
169938fd1498Szrj
170038fd1498Szrj CASE_CONVERT:
170138fd1498Szrj return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0));
170238fd1498Szrj
170338fd1498Szrj default:
170438fd1498Szrj return false;
170538fd1498Szrj }
170638fd1498Szrj }
1707