Bug Summary

File:build/gcc/tree-chrec.cc
Warning:line 593, column 8
Value stored to 'res' during its initialization is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-suse-linux -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name tree-chrec.cc -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model static -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/gcc -resource-dir /usr/lib64/clang/15.0.7 -D IN_GCC -D HAVE_CONFIG_H -I . -I . -I /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc -I /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/. -I /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../include -I /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libcpp/include -I /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libcody -I /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libdecnumber -I /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libdecnumber/bid -I ../libdecnumber -I /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libbacktrace -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/13/../../../../include/c++/13 -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/13/../../../../include/c++/13/x86_64-suse-linux -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/13/../../../../include/c++/13/backward -internal-isystem /usr/lib64/clang/15.0.7/include -internal-isystem /usr/local/include -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/13/../../../../x86_64-suse-linux/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-narrowing -Wwrite-strings -Wno-long-long -Wno-variadic-macros -Wno-overlength-strings -fdeprecated-macro -fdebug-compilation-dir=/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/gcc -ferror-limit 19 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=plist-html -analyzer-config silence-checkers=core.NullDereference -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /buildworker/marxinbox-gcc-clang-static-analyzer/objdir/clang-static-analyzer/2023-03-27-141847-20772-1/report-5vbBuv.plist -x c++ /buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc
1/* Chains of recurrences.
2 Copyright (C) 2003-2023 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21/* This file implements operations on chains of recurrences. Chains
22 of recurrences are used for modeling evolution functions of scalar
23 variables.
24*/
25
26#include "config.h"
27#include "system.h"
28#include "coretypes.h"
29#include "backend.h"
30#include "tree.h"
31#include "gimple-expr.h"
32#include "tree-pretty-print.h"
33#include "fold-const.h"
34#include "cfgloop.h"
35#include "tree-ssa-loop-ivopts.h"
36#include "tree-ssa-loop-niter.h"
37#include "tree-chrec.h"
38#include "gimple.h"
39#include "tree-ssa-loop.h"
40#include "dumpfile.h"
41#include "tree-scalar-evolution.h"
42
43/* Extended folder for chrecs. */
44
45/* Fold the addition of two polynomial functions. */
46
47static inline tree
48chrec_fold_plus_poly_poly (enum tree_code code,
49 tree type,
50 tree poly0,
51 tree poly1)
52{
53 tree left, right;
54 class loop *loop0 = get_chrec_loop (poly0);
55 class loop *loop1 = get_chrec_loop (poly1);
56 tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (poly1) : type;
57
58 gcc_assert (poly0)((void)(!(poly0) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 58, __FUNCTION__), 0 : 0));
59 gcc_assert (poly1)((void)(!(poly1) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 59, __FUNCTION__), 0 : 0));
60 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC)((void)(!(((enum tree_code) (poly0)->base.code) == POLYNOMIAL_CHREC
) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 60, __FUNCTION__), 0 : 0));
61 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC)((void)(!(((enum tree_code) (poly1)->base.code) == POLYNOMIAL_CHREC
) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 61, __FUNCTION__), 0 : 0));
62 if (POINTER_TYPE_P (chrec_type (poly0))(((enum tree_code) (chrec_type (poly0))->base.code) == POINTER_TYPE
|| ((enum tree_code) (chrec_type (poly0))->base.code) == REFERENCE_TYPE
))
63 gcc_checking_assert (ptrofftype_p (chrec_type (poly1))((void)(!(ptrofftype_p (chrec_type (poly1)) && useless_type_conversion_p
(type, chrec_type (poly0))) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 64, __FUNCTION__), 0 : 0))
64 && useless_type_conversion_p (type, chrec_type (poly0)))((void)(!(ptrofftype_p (chrec_type (poly1)) && useless_type_conversion_p
(type, chrec_type (poly0))) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 64, __FUNCTION__), 0 : 0));
65 else
66 gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0))((void)(!(useless_type_conversion_p (type, chrec_type (poly0)
) && useless_type_conversion_p (type, chrec_type (poly1
))) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 67, __FUNCTION__), 0 : 0))
67 && useless_type_conversion_p (type, chrec_type (poly1)))((void)(!(useless_type_conversion_p (type, chrec_type (poly0)
) && useless_type_conversion_p (type, chrec_type (poly1
))) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 67, __FUNCTION__), 0 : 0));
68
69 /*
70 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
71 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
72 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
73 if (flow_loop_nested_p (loop0, loop1))
74 {
75 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
76 return build_polynomial_chrec
77 (CHREC_VARIABLE (poly1)(tree_check ((poly1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 77, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var,
78 chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 78, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 78, __FUNCTION__)))))),
79 CHREC_RIGHT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 79, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 79, __FUNCTION__))))));
80 else
81 return build_polynomial_chrec
82 (CHREC_VARIABLE (poly1)(tree_check ((poly1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 82, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var,
83 chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 83, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 83, __FUNCTION__)))))),
84 chrec_fold_multiply (type, CHREC_RIGHT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 84, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 84, __FUNCTION__))))),
85 SCALAR_FLOAT_TYPE_P (type)(((enum tree_code) (type)->base.code) == REAL_TYPE)
86 ? build_real (type, dconstm1)
87 : build_int_cst_type (type, -1)));
88 }
89
90 if (flow_loop_nested_p (loop1, loop0))
91 {
92 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
93 return build_polynomial_chrec
94 (CHREC_VARIABLE (poly0)(tree_check ((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 94, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var,
95 chrec_fold_plus (type, CHREC_LEFT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 95, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 95, __FUNCTION__))))), poly1),
96 CHREC_RIGHT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 96, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 96, __FUNCTION__))))));
97 else
98 return build_polynomial_chrec
99 (CHREC_VARIABLE (poly0)(tree_check ((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 99, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var,
100 chrec_fold_minus (type, CHREC_LEFT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 100, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 100, __FUNCTION__))))), poly1),
101 CHREC_RIGHT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 101, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 101, __FUNCTION__))))));
102 }
103
104 /* This function should never be called for chrecs of loops that
105 do not belong to the same loop nest. */
106 if (loop0 != loop1)
107 {
108 /* It still can happen if we are not in loop-closed SSA form. */
109 gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA))((void)(!(! loops_state_satisfies_p (LOOP_CLOSED_SSA)) ? fancy_abort
("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 109, __FUNCTION__), 0 : 0));
110 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
111 }
112
113 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
114 {
115 left = chrec_fold_plus
116 (type, CHREC_LEFT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 116, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 116, __FUNCTION__))))), CHREC_LEFT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 116, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 116, __FUNCTION__))))));
117 right = chrec_fold_plus
118 (rtype, CHREC_RIGHT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 118, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 118, __FUNCTION__))))), CHREC_RIGHT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 118, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 118, __FUNCTION__))))));
119 }
120 else
121 {
122 left = chrec_fold_minus
123 (type, CHREC_LEFT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 123, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 123, __FUNCTION__))))), CHREC_LEFT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 123, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 123, __FUNCTION__))))));
124 right = chrec_fold_minus
125 (type, CHREC_RIGHT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 125, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 125, __FUNCTION__))))), CHREC_RIGHT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 125, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 125, __FUNCTION__))))));
126 }
127
128 if (chrec_zerop (right))
129 return left;
130 else
131 return build_polynomial_chrec
132 (CHREC_VARIABLE (poly0)(tree_check ((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 132, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var, left, right);
133}
134
135
136
137/* Fold the multiplication of two polynomial functions. */
138
139static inline tree
140chrec_fold_multiply_poly_poly (tree type,
141 tree poly0,
142 tree poly1)
143{
144 tree t0, t1, t2;
145 int var;
146 class loop *loop0 = get_chrec_loop (poly0);
147 class loop *loop1 = get_chrec_loop (poly1);
148
149 gcc_assert (poly0)((void)(!(poly0) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 149, __FUNCTION__), 0 : 0));
150 gcc_assert (poly1)((void)(!(poly1) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 150, __FUNCTION__), 0 : 0));
151 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC)((void)(!(((enum tree_code) (poly0)->base.code) == POLYNOMIAL_CHREC
) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 151, __FUNCTION__), 0 : 0));
152 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC)((void)(!(((enum tree_code) (poly1)->base.code) == POLYNOMIAL_CHREC
) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 152, __FUNCTION__), 0 : 0));
153 gcc_checking_assert (useless_type_conversion_p (type, chrec_type (poly0))((void)(!(useless_type_conversion_p (type, chrec_type (poly0)
) && useless_type_conversion_p (type, chrec_type (poly1
))) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 154, __FUNCTION__), 0 : 0))
154 && useless_type_conversion_p (type, chrec_type (poly1)))((void)(!(useless_type_conversion_p (type, chrec_type (poly0)
) && useless_type_conversion_p (type, chrec_type (poly1
))) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 154, __FUNCTION__), 0 : 0));
155
156 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
157 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
158 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
159 if (flow_loop_nested_p (loop0, loop1))
160 /* poly0 is a constant wrt. poly1. */
161 return build_polynomial_chrec
162 (CHREC_VARIABLE (poly1)(tree_check ((poly1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 162, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var,
163 chrec_fold_multiply (type, CHREC_LEFT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 163, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 163, __FUNCTION__))))), poly0),
164 CHREC_RIGHT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 164, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 164, __FUNCTION__))))));
165
166 if (flow_loop_nested_p (loop1, loop0))
167 /* poly1 is a constant wrt. poly0. */
168 return build_polynomial_chrec
169 (CHREC_VARIABLE (poly0)(tree_check ((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 169, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var,
170 chrec_fold_multiply (type, CHREC_LEFT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 170, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 170, __FUNCTION__))))), poly1),
171 CHREC_RIGHT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 171, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 171, __FUNCTION__))))));
172
173 if (loop0 != loop1)
174 {
175 /* It still can happen if we are not in loop-closed SSA form. */
176 gcc_assert (! loops_state_satisfies_p (LOOP_CLOSED_SSA))((void)(!(! loops_state_satisfies_p (LOOP_CLOSED_SSA)) ? fancy_abort
("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 176, __FUNCTION__), 0 : 0));
177 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
178 }
179
180 /* poly0 and poly1 are two polynomials in the same variable,
181 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
182
183 /* "a*c". */
184 t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 184, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 184, __FUNCTION__))))), CHREC_LEFT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 184, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 184, __FUNCTION__))))));
185
186 /* "a*d + b*c". */
187 t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 187, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 187, __FUNCTION__))))), CHREC_RIGHT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 187, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 187, __FUNCTION__))))));
188 t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type,
189 CHREC_RIGHT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 189, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 189, __FUNCTION__))))),
190 CHREC_LEFT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 190, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 190, __FUNCTION__)))))));
191 /* "b*d". */
192 t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 192, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 192, __FUNCTION__))))), CHREC_RIGHT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 192, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 192, __FUNCTION__))))));
193 /* "a*d + b*c + b*d". */
194 t1 = chrec_fold_plus (type, t1, t2);
195 /* "2*b*d". */
196 t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)(((enum tree_code) (type)->base.code) == REAL_TYPE)
197 ? build_real (type, dconst2)
198 : build_int_cst (type, 2), t2);
199
200 var = CHREC_VARIABLE (poly0)(tree_check ((poly0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 200, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var;
201 return build_polynomial_chrec (var, t0,
202 build_polynomial_chrec (var, t1, t2));
203}
204
205/* When the operands are automatically_generated_chrec_p, the fold has
206 to respect the semantics of the operands. */
207
208static inline tree
209chrec_fold_automatically_generated_operands (tree op0,
210 tree op1)
211{
212 if (op0 == chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW]
213 || op1 == chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW])
214 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
215
216 if (op0 == chrec_knownglobal_trees[TI_CHREC_KNOWN]
217 || op1 == chrec_knownglobal_trees[TI_CHREC_KNOWN])
218 return chrec_knownglobal_trees[TI_CHREC_KNOWN];
219
220 if (op0 == chrec_not_analyzed_yet(tree) nullptr
221 || op1 == chrec_not_analyzed_yet(tree) nullptr)
222 return chrec_not_analyzed_yet(tree) nullptr;
223
224 /* The default case produces a safe result. */
225 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
226}
227
228/* Fold the addition of two chrecs. */
229
230static tree
231chrec_fold_plus_1 (enum tree_code code, tree type,
232 tree op0, tree op1)
233{
234 if (automatically_generated_chrec_p (op0)
235 || automatically_generated_chrec_p (op1))
236 return chrec_fold_automatically_generated_operands (op0, op1);
237
238 switch (TREE_CODE (op0)((enum tree_code) (op0)->base.code))
239 {
240 case POLYNOMIAL_CHREC:
241 gcc_checking_assert((void)(!(!chrec_contains_symbols_defined_in_loop (op0, (tree_check
((op0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 242, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 242, __FUNCTION__), 0 : 0))
242 (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)))((void)(!(!chrec_contains_symbols_defined_in_loop (op0, (tree_check
((op0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 242, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 242, __FUNCTION__), 0 : 0));
243 switch (TREE_CODE (op1)((enum tree_code) (op1)->base.code))
244 {
245 case POLYNOMIAL_CHREC:
246 gcc_checking_assert((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 248, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 248, __FUNCTION__), 0 : 0))
247 (!chrec_contains_symbols_defined_in_loop (op1,((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 248, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 248, __FUNCTION__), 0 : 0))
248 CHREC_VARIABLE (op1)))((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 248, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 248, __FUNCTION__), 0 : 0));
249 return chrec_fold_plus_poly_poly (code, type, op0, op1);
250
251 CASE_CONVERTcase NOP_EXPR: case CONVERT_EXPR:
252 {
253 /* We can strip sign-conversions to signed by performing the
254 operation in unsigned. */
255 tree optype = TREE_TYPE (TREE_OPERAND (op1, 0))((contains_struct_check (((*((const_cast<tree*> (tree_operand_check
((op1), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 255, __FUNCTION__)))))), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 255, __FUNCTION__))->typed.type);
256 if (INTEGRAL_TYPE_P (type)(((enum tree_code) (type)->base.code) == ENUMERAL_TYPE || (
(enum tree_code) (type)->base.code) == BOOLEAN_TYPE || ((enum
tree_code) (type)->base.code) == INTEGER_TYPE)
257 && INTEGRAL_TYPE_P (optype)(((enum tree_code) (optype)->base.code) == ENUMERAL_TYPE ||
((enum tree_code) (optype)->base.code) == BOOLEAN_TYPE ||
((enum tree_code) (optype)->base.code) == INTEGER_TYPE)
258 && tree_nop_conversion_p (type, optype)
259 && TYPE_UNSIGNED (optype)((tree_class_check ((optype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 259, __FUNCTION__))->base.u.bits.unsigned_flag))
260 return chrec_convert (type,
261 chrec_fold_plus_1 (code, optype,
262 chrec_convert (optype,
263 op0, NULLnullptr),
264 TREE_OPERAND (op1, 0)(*((const_cast<tree*> (tree_operand_check ((op1), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 264, __FUNCTION__)))))),
265 NULLnullptr);
266 if (tree_contains_chrecs (op1, NULLnullptr))
267 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
268 }
269 /* FALLTHRU */
270
271 default:
272 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
273 return build_polynomial_chrec
274 (CHREC_VARIABLE (op0)(tree_check ((op0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 274, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var,
275 chrec_fold_plus (type, CHREC_LEFT (op0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((op0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 275, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 275, __FUNCTION__))))), op1),
276 CHREC_RIGHT (op0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((op0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 276, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 276, __FUNCTION__))))));
277 else
278 return build_polynomial_chrec
279 (CHREC_VARIABLE (op0)(tree_check ((op0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 279, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var,
280 chrec_fold_minus (type, CHREC_LEFT (op0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((op0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 280, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 280, __FUNCTION__))))), op1),
281 CHREC_RIGHT (op0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((op0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 281, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 281, __FUNCTION__))))));
282 }
283
284 CASE_CONVERTcase NOP_EXPR: case CONVERT_EXPR:
285 {
286 /* We can strip sign-conversions to signed by performing the
287 operation in unsigned. */
288 tree optype = TREE_TYPE (TREE_OPERAND (op0, 0))((contains_struct_check (((*((const_cast<tree*> (tree_operand_check
((op0), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 288, __FUNCTION__)))))), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 288, __FUNCTION__))->typed.type);
289 if (INTEGRAL_TYPE_P (type)(((enum tree_code) (type)->base.code) == ENUMERAL_TYPE || (
(enum tree_code) (type)->base.code) == BOOLEAN_TYPE || ((enum
tree_code) (type)->base.code) == INTEGER_TYPE)
290 && INTEGRAL_TYPE_P (optype)(((enum tree_code) (optype)->base.code) == ENUMERAL_TYPE ||
((enum tree_code) (optype)->base.code) == BOOLEAN_TYPE ||
((enum tree_code) (optype)->base.code) == INTEGER_TYPE)
291 && tree_nop_conversion_p (type, optype)
292 && TYPE_UNSIGNED (optype)((tree_class_check ((optype), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 292, __FUNCTION__))->base.u.bits.unsigned_flag))
293 return chrec_convert (type,
294 chrec_fold_plus_1 (code, optype,
295 TREE_OPERAND (op0, 0)(*((const_cast<tree*> (tree_operand_check ((op0), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 295, __FUNCTION__))))),
296 chrec_convert (optype,
297 op1, NULLnullptr)),
298 NULLnullptr);
299 if (tree_contains_chrecs (op0, NULLnullptr))
300 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
301 }
302 /* FALLTHRU */
303
304 default:
305 switch (TREE_CODE (op1)((enum tree_code) (op1)->base.code))
306 {
307 case POLYNOMIAL_CHREC:
308 gcc_checking_assert((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 310, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 310, __FUNCTION__), 0 : 0))
309 (!chrec_contains_symbols_defined_in_loop (op1,((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 310, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 310, __FUNCTION__), 0 : 0))
310 CHREC_VARIABLE (op1)))((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 310, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 310, __FUNCTION__), 0 : 0));
311 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
312 return build_polynomial_chrec
313 (CHREC_VARIABLE (op1)(tree_check ((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 313, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var,
314 chrec_fold_plus (type, op0, CHREC_LEFT (op1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 314, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 314, __FUNCTION__)))))),
315 CHREC_RIGHT (op1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 315, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 315, __FUNCTION__))))));
316 else
317 return build_polynomial_chrec
318 (CHREC_VARIABLE (op1)(tree_check ((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 318, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var,
319 chrec_fold_minus (type, op0, CHREC_LEFT (op1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 319, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 319, __FUNCTION__)))))),
320 chrec_fold_multiply (type, CHREC_RIGHT (op1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 320, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 320, __FUNCTION__))))),
321 SCALAR_FLOAT_TYPE_P (type)(((enum tree_code) (type)->base.code) == REAL_TYPE)
322 ? build_real (type, dconstm1)
323 : build_int_cst_type (type, -1)));
324
325 CASE_CONVERTcase NOP_EXPR: case CONVERT_EXPR:
326 if (tree_contains_chrecs (op1, NULLnullptr))
327 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
328 /* FALLTHRU */
329
330 default:
331 {
332 int size = 0;
333 if ((tree_contains_chrecs (op0, &size)
334 || tree_contains_chrecs (op1, &size))
335 && size < param_scev_max_expr_sizeglobal_options.x_param_scev_max_expr_size)
336 return build2 (code, type, op0, op1);
337 else if (size < param_scev_max_expr_sizeglobal_options.x_param_scev_max_expr_size)
338 {
339 if (code == POINTER_PLUS_EXPR)
340 return fold_build_pointer_plus (fold_convert (type, op0),fold_build_pointer_plus_loc (((location_t) 0), fold_convert_loc
(((location_t) 0), type, op0), op1)
341 op1)fold_build_pointer_plus_loc (((location_t) 0), fold_convert_loc
(((location_t) 0), type, op0), op1);
342 else
343 return fold_build2 (code, type,fold_build2_loc (((location_t) 0), code, type, fold_convert_loc
(((location_t) 0), type, op0), fold_convert_loc (((location_t
) 0), type, op1) )
344 fold_convert (type, op0),fold_build2_loc (((location_t) 0), code, type, fold_convert_loc
(((location_t) 0), type, op0), fold_convert_loc (((location_t
) 0), type, op1) )
345 fold_convert (type, op1))fold_build2_loc (((location_t) 0), code, type, fold_convert_loc
(((location_t) 0), type, op0), fold_convert_loc (((location_t
) 0), type, op1) );
346 }
347 else
348 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
349 }
350 }
351 }
352}
353
354/* Fold the addition of two chrecs. */
355
356tree
357chrec_fold_plus (tree type,
358 tree op0,
359 tree op1)
360{
361 enum tree_code code;
362 if (automatically_generated_chrec_p (op0)
363 || automatically_generated_chrec_p (op1))
364 return chrec_fold_automatically_generated_operands (op0, op1);
365
366 if (integer_zerop (op0))
367 return chrec_convert (type, op1, NULLnullptr);
368 if (integer_zerop (op1))
369 return chrec_convert (type, op0, NULLnullptr);
370
371 if (POINTER_TYPE_P (type)(((enum tree_code) (type)->base.code) == POINTER_TYPE || (
(enum tree_code) (type)->base.code) == REFERENCE_TYPE))
372 code = POINTER_PLUS_EXPR;
373 else
374 code = PLUS_EXPR;
375
376 return chrec_fold_plus_1 (code, type, op0, op1);
377}
378
379/* Fold the subtraction of two chrecs. */
380
381tree
382chrec_fold_minus (tree type,
383 tree op0,
384 tree op1)
385{
386 if (automatically_generated_chrec_p (op0)
387 || automatically_generated_chrec_p (op1))
388 return chrec_fold_automatically_generated_operands (op0, op1);
389
390 if (integer_zerop (op1))
391 return op0;
392
393 return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
394}
395
396/* Fold the multiplication of two chrecs. */
397
398tree
399chrec_fold_multiply (tree type,
400 tree op0,
401 tree op1)
402{
403 if (automatically_generated_chrec_p (op0)
404 || automatically_generated_chrec_p (op1))
405 return chrec_fold_automatically_generated_operands (op0, op1);
406
407 switch (TREE_CODE (op0)((enum tree_code) (op0)->base.code))
408 {
409 case POLYNOMIAL_CHREC:
410 gcc_checking_assert((void)(!(!chrec_contains_symbols_defined_in_loop (op0, (tree_check
((op0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 411, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 411, __FUNCTION__), 0 : 0))
411 (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)))((void)(!(!chrec_contains_symbols_defined_in_loop (op0, (tree_check
((op0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 411, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 411, __FUNCTION__), 0 : 0));
412 switch (TREE_CODE (op1)((enum tree_code) (op1)->base.code))
413 {
414 case POLYNOMIAL_CHREC:
415 gcc_checking_assert((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 417, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 417, __FUNCTION__), 0 : 0))
416 (!chrec_contains_symbols_defined_in_loop (op1,((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 417, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 417, __FUNCTION__), 0 : 0))
417 CHREC_VARIABLE (op1)))((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 417, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 417, __FUNCTION__), 0 : 0));
418 return chrec_fold_multiply_poly_poly (type, op0, op1);
419
420 CASE_CONVERTcase NOP_EXPR: case CONVERT_EXPR:
421 if (tree_contains_chrecs (op1, NULLnullptr))
422 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
423 /* FALLTHRU */
424
425 default:
426 if (integer_onep (op1))
427 return op0;
428 if (integer_zerop (op1))
429 return build_int_cst (type, 0);
430
431 return build_polynomial_chrec
432 (CHREC_VARIABLE (op0)(tree_check ((op0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 432, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var,
433 chrec_fold_multiply (type, CHREC_LEFT (op0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((op0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 433, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 433, __FUNCTION__))))), op1),
434 chrec_fold_multiply (type, CHREC_RIGHT (op0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((op0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 434, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 434, __FUNCTION__))))), op1));
435 }
436
437 CASE_CONVERTcase NOP_EXPR: case CONVERT_EXPR:
438 if (tree_contains_chrecs (op0, NULLnullptr))
439 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
440 /* FALLTHRU */
441
442 default:
443 if (integer_onep (op0))
444 return op1;
445
446 if (integer_zerop (op0))
447 return build_int_cst (type, 0);
448
449 switch (TREE_CODE (op1)((enum tree_code) (op1)->base.code))
450 {
451 case POLYNOMIAL_CHREC:
452 gcc_checking_assert((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 454, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 454, __FUNCTION__), 0 : 0))
453 (!chrec_contains_symbols_defined_in_loop (op1,((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 454, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 454, __FUNCTION__), 0 : 0))
454 CHREC_VARIABLE (op1)))((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 454, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 454, __FUNCTION__), 0 : 0));
455 return build_polynomial_chrec
456 (CHREC_VARIABLE (op1)(tree_check ((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 456, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var,
457 chrec_fold_multiply (type, CHREC_LEFT (op1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 457, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 457, __FUNCTION__))))), op0),
458 chrec_fold_multiply (type, CHREC_RIGHT (op1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((op1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 458, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 458, __FUNCTION__))))), op0));
459
460 CASE_CONVERTcase NOP_EXPR: case CONVERT_EXPR:
461 if (tree_contains_chrecs (op1, NULLnullptr))
462 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
463 /* FALLTHRU */
464
465 default:
466 if (integer_onep (op1))
467 return op0;
468 if (integer_zerop (op1))
469 return build_int_cst (type, 0);
470 return fold_build2 (MULT_EXPR, type, op0, op1)fold_build2_loc (((location_t) 0), MULT_EXPR, type, op0, op1 );
471 }
472 }
473}
474
475
476
477/* Operations. */
478
479/* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
480 calculation overflows, otherwise return C(n,k) with type TYPE. */
481
482static tree
483tree_fold_binomial (tree type, tree n, unsigned int k)
484{
485 wi::overflow_type overflow;
486 unsigned int i;
487
488 /* Handle the most frequent cases. */
489 if (k == 0)
490 return build_int_cst (type, 1);
491 if (k == 1)
492 return fold_convert (type, n)fold_convert_loc (((location_t) 0), type, n);
493
494 widest_int num = wi::to_widest (n);
495
496 /* Check that k <= n. */
497 if (wi::ltu_p (num, k))
498 return NULL_TREE(tree) nullptr;
499
500 /* Denominator = 2. */
501 widest_int denom = 2;
502
503 /* Index = Numerator-1. */
504 widest_int idx = num - 1;
505
506 /* Numerator = Numerator*Index = n*(n-1). */
507 num = wi::smul (num, idx, &overflow);
508 if (overflow)
509 return NULL_TREE(tree) nullptr;
510
511 for (i = 3; i <= k; i++)
512 {
513 /* Index--. */
514 --idx;
515
516 /* Numerator *= Index. */
517 num = wi::smul (num, idx, &overflow);
518 if (overflow)
519 return NULL_TREE(tree) nullptr;
520
521 /* Denominator *= i. */
522 denom *= i;
523 }
524
525 /* Result = Numerator / Denominator. */
526 num = wi::udiv_trunc (num, denom);
527 if (! wi::fits_to_tree_p (num, type))
528 return NULL_TREE(tree) nullptr;
529 return wide_int_to_tree (type, num);
530}
531
532/* Helper function. Use the Newton's interpolating formula for
533 evaluating the value of the evolution function.
534 The result may be in an unsigned type of CHREC. */
535
536static tree
537chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
538{
539 tree arg0, arg1, binomial_n_k;
540 tree type = TREE_TYPE (chrec)((contains_struct_check ((chrec), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 540, __FUNCTION__))->typed.type);
541 class loop *var_loop = get_loop (cfun(cfun + 0), var);
542
543 while (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLYNOMIAL_CHREC
544 && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
545 chrec = CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 545, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 545, __FUNCTION__)))));
546
547 /* The formula associates the expression and thus we have to make
548 sure to not introduce undefined overflow. */
549 tree ctype = type;
550 if (INTEGRAL_TYPE_P (type)(((enum tree_code) (type)->base.code) == ENUMERAL_TYPE || (
(enum tree_code) (type)->base.code) == BOOLEAN_TYPE || ((enum
tree_code) (type)->base.code) == INTEGER_TYPE)
551 && ! TYPE_OVERFLOW_WRAPS (type)((((enum tree_code) (type)->base.code) == POINTER_TYPE || (
(enum tree_code) (type)->base.code) == REFERENCE_TYPE) ? global_options
.x_flag_wrapv_pointer : ((any_integral_type_check ((type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 551, __FUNCTION__))->base.u.bits.unsigned_flag || global_options
.x_flag_wrapv)))
552 ctype = unsigned_type_for (type);
553
554 if (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLYNOMIAL_CHREC
555 && CHREC_VARIABLE (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 555, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var == var)
556 {
557 arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 557, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 557, __FUNCTION__))))), n, k + 1);
558 if (arg1 == chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW])
559 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
560 binomial_n_k = tree_fold_binomial (ctype, n, k);
561 if (!binomial_n_k)
562 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
563 tree l = chrec_convert (ctype, CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 563, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 563, __FUNCTION__))))), NULLnullptr);
564 arg0 = fold_build2 (MULT_EXPR, ctype, l, binomial_n_k)fold_build2_loc (((location_t) 0), MULT_EXPR, ctype, l, binomial_n_k
);
565 return chrec_fold_plus (ctype, arg0, arg1);
566 }
567
568 binomial_n_k = tree_fold_binomial (ctype, n, k);
569 if (!binomial_n_k)
570 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
571
572 return fold_build2 (MULT_EXPR, ctype,fold_build2_loc (((location_t) 0), MULT_EXPR, ctype, chrec_convert
(ctype, chrec, nullptr), binomial_n_k )
573 chrec_convert (ctype, chrec, NULL), binomial_n_k)fold_build2_loc (((location_t) 0), MULT_EXPR, ctype, chrec_convert
(ctype, chrec, nullptr), binomial_n_k );
574}
575
576/* Evaluates "CHREC (X)" when the varying variable is VAR.
577 Example: Given the following parameters,
578
579 var = 1
580 chrec = {3, +, 4}_1
581 x = 10
582
583 The result is given by the Newton's interpolating formula:
584 3 * \binom{10}{0} + 4 * \binom{10}{1}.
585*/
586
587tree
588chrec_apply (unsigned var,
589 tree chrec,
590 tree x)
591{
592 tree type = chrec_type (chrec);
593 tree res = chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
Value stored to 'res' during its initialization is never read
594
595 if (automatically_generated_chrec_p (chrec)
596 || automatically_generated_chrec_p (x)
597
598 /* When the symbols are defined in an outer loop, it is possible
599 to symbolically compute the apply, since the symbols are
600 constants with respect to the varying loop. */
601 || chrec_contains_symbols_defined_in_loop (chrec, var))
602 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
603
604 if (dump_file && (dump_flags & TDF_SCEV))
605 fprintf (dump_file, "(chrec_apply \n");
606
607 if (TREE_CODE (x)((enum tree_code) (x)->base.code) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type)(((enum tree_code) (type)->base.code) == REAL_TYPE))
608 x = build_real_from_int_cst (type, x);
609
610 switch (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code))
611 {
612 case POLYNOMIAL_CHREC:
613 if (evolution_function_is_affine_p (chrec))
614 {
615 tree chrecr = CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 615, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 615, __FUNCTION__)))));
616 if (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 616, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var != var)
617 res = build_polynomial_chrec
618 (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 618, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var,
619 chrec_apply (var, CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 619, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 619, __FUNCTION__))))), x),
620 chrec_apply (var, chrecr, x));
621
622 /* "{a, +, b} (x)" -> "a + b*x". */
623 else if (operand_equal_p (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 623, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 623, __FUNCTION__))))), chrecr)
624 && TREE_CODE (x)((enum tree_code) (x)->base.code) == PLUS_EXPR
625 && integer_all_onesp (TREE_OPERAND (x, 1)(*((const_cast<tree*> (tree_operand_check ((x), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 625, __FUNCTION__))))))
626 && !POINTER_TYPE_P (type)(((enum tree_code) (type)->base.code) == POINTER_TYPE || (
(enum tree_code) (type)->base.code) == REFERENCE_TYPE)
627 && TYPE_PRECISION (TREE_TYPE (x))((tree_class_check ((((contains_struct_check ((x), (TS_TYPED)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 627, __FUNCTION__))->typed.type)), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 627, __FUNCTION__))->type_common.precision)
628 >= TYPE_PRECISION (type)((tree_class_check ((type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 628, __FUNCTION__))->type_common.precision))
629 {
630 /* We know the number of iterations can't be negative.
631 So {a, +, a} (x-1) -> "a*x". */
632 res = build_int_cst (TREE_TYPE (x)((contains_struct_check ((x), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 632, __FUNCTION__))->typed.type), 1);
633 res = chrec_fold_plus (TREE_TYPE (x)((contains_struct_check ((x), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 633, __FUNCTION__))->typed.type), x, res);
634 res = chrec_convert_rhs (type, res, NULLnullptr);
635 res = chrec_fold_multiply (type, chrecr, res);
636 }
637 else
638 {
639 res = chrec_convert_rhs (TREE_TYPE (chrecr)((contains_struct_check ((chrecr), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 639, __FUNCTION__))->typed.type), x, NULLnullptr);
640 res = chrec_fold_multiply (TREE_TYPE (chrecr)((contains_struct_check ((chrecr), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 640, __FUNCTION__))->typed.type), chrecr, res);
641 res = chrec_fold_plus (type, CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 641, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 641, __FUNCTION__))))), res);
642 }
643 }
644 else if (TREE_CODE (x)((enum tree_code) (x)->base.code) == INTEGER_CST
645 && tree_int_cst_sgn (x) == 1)
646 /* testsuite/.../ssa-chrec-38.c. */
647 res = chrec_convert (type, chrec_evaluate (var, chrec, x, 0), NULLnullptr);
648 else
649 res = chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
650 break;
651
652 CASE_CONVERTcase NOP_EXPR: case CONVERT_EXPR:
653 res = chrec_convert (TREE_TYPE (chrec)((contains_struct_check ((chrec), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 653, __FUNCTION__))->typed.type),
654 chrec_apply (var, TREE_OPERAND (chrec, 0)(*((const_cast<tree*> (tree_operand_check ((chrec), (0)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 654, __FUNCTION__))))), x),
655 NULLnullptr);
656 break;
657
658 default:
659 res = chrec;
660 break;
661 }
662
663 if (dump_file && (dump_flags & TDF_SCEV))
664 {
665 fprintf (dump_file, " (varying_loop = %d", var);
666 fprintf (dump_file, ")\n (chrec = ");
667 print_generic_expr (dump_file, chrec);
668 fprintf (dump_file, ")\n (x = ");
669 print_generic_expr (dump_file, x);
670 fprintf (dump_file, ")\n (res = ");
671 print_generic_expr (dump_file, res);
672 fprintf (dump_file, "))\n");
673 }
674
675 return res;
676}
677
678/* For a given CHREC and an induction variable map IV_MAP that maps
679 (loop->num, expr) for every loop number of the current_loops an
680 expression, calls chrec_apply when the expression is not NULL. */
681
682tree
683chrec_apply_map (tree chrec, vec<tree> iv_map)
684{
685 int i;
686 tree expr;
687
688 FOR_EACH_VEC_ELT (iv_map, i, expr)for (i = 0; (iv_map).iterate ((i), &(expr)); ++(i))
689 if (expr)
690 chrec = chrec_apply (i, chrec, expr);
691
692 return chrec;
693}
694
695/* Replaces the initial condition in CHREC with INIT_COND. */
696
697tree
698chrec_replace_initial_condition (tree chrec,
699 tree init_cond)
700{
701 if (automatically_generated_chrec_p (chrec))
702 return chrec;
703
704 gcc_assert (chrec_type (chrec) == chrec_type (init_cond))((void)(!(chrec_type (chrec) == chrec_type (init_cond)) ? fancy_abort
("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 704, __FUNCTION__), 0 : 0));
705
706 switch (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code))
707 {
708 case POLYNOMIAL_CHREC:
709 return build_polynomial_chrec
710 (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 710, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var,
711 chrec_replace_initial_condition (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 711, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 711, __FUNCTION__))))), init_cond),
712 CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 712, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 712, __FUNCTION__))))));
713
714 default:
715 return init_cond;
716 }
717}
718
719/* Returns the initial condition of a given CHREC. */
720
721tree
722initial_condition (tree chrec)
723{
724 if (automatically_generated_chrec_p (chrec))
725 return chrec;
726
727 if (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLYNOMIAL_CHREC)
728 return initial_condition (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 728, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 728, __FUNCTION__))))));
729 else
730 return chrec;
731}
732
733/* Returns a univariate function that represents the evolution in
734 LOOP_NUM. Mask the evolution of any other loop. */
735
736tree
737hide_evolution_in_other_loops_than_loop (tree chrec,
738 unsigned loop_num)
739{
740 class loop *loop = get_loop (cfun(cfun + 0), loop_num), *chloop;
741 if (automatically_generated_chrec_p (chrec))
742 return chrec;
743
744 switch (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code))
745 {
746 case POLYNOMIAL_CHREC:
747 chloop = get_chrec_loop (chrec);
748
749 if (chloop == loop)
750 return build_polynomial_chrec
751 (loop_num,
752 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 752, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 752, __FUNCTION__))))),
753 loop_num),
754 CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 754, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 754, __FUNCTION__))))));
755
756 else if (flow_loop_nested_p (chloop, loop))
757 /* There is no evolution in this loop. */
758 return initial_condition (chrec);
759
760 else if (flow_loop_nested_p (loop, chloop))
761 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 761, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 761, __FUNCTION__))))),
762 loop_num);
763
764 else
765 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
766
767 default:
768 return chrec;
769 }
770}
771
772/* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
773 true, otherwise returns the initial condition in LOOP_NUM. */
774
775static tree
776chrec_component_in_loop_num (tree chrec,
777 unsigned loop_num,
778 bool right)
779{
780 tree component;
781 class loop *loop = get_loop (cfun(cfun + 0), loop_num), *chloop;
782
783 if (automatically_generated_chrec_p (chrec))
784 return chrec;
785
786 switch (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code))
787 {
788 case POLYNOMIAL_CHREC:
789 chloop = get_chrec_loop (chrec);
790
791 if (chloop == loop)
792 {
793 if (right)
794 component = CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 794, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 794, __FUNCTION__)))));
795 else
796 component = CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 796, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 796, __FUNCTION__)))));
797
798 if (TREE_CODE (CHREC_LEFT (chrec))((enum tree_code) ((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 798, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 798, __FUNCTION__))))))->base.code) != POLYNOMIAL_CHREC
799 || CHREC_VARIABLE (CHREC_LEFT (chrec))(tree_check (((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 799, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 799, __FUNCTION__)))))), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 799, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var != CHREC_VARIABLE (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 799, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var)
800 return component;
801
802 else
803 return build_polynomial_chrec
804 (loop_num,
805 chrec_component_in_loop_num (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 805, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 805, __FUNCTION__))))),
806 loop_num,
807 right),
808 component);
809 }
810
811 else if (flow_loop_nested_p (chloop, loop))
812 /* There is no evolution part in this loop. */
813 return NULL_TREE(tree) nullptr;
814
815 else
816 {
817 gcc_assert (flow_loop_nested_p (loop, chloop))((void)(!(flow_loop_nested_p (loop, chloop)) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 817, __FUNCTION__), 0 : 0));
818 return chrec_component_in_loop_num (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 818, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 818, __FUNCTION__))))),
819 loop_num,
820 right);
821 }
822
823 default:
824 if (right)
825 return NULL_TREE(tree) nullptr;
826 else
827 return chrec;
828 }
829}
830
831/* Returns the evolution part in LOOP_NUM. Example: the call
832 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
833 {1, +, 2}_1 */
834
835tree
836evolution_part_in_loop_num (tree chrec,
837 unsigned loop_num)
838{
839 return chrec_component_in_loop_num (chrec, loop_num, true);
840}
841
842/* Returns the initial condition in LOOP_NUM. Example: the call
843 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
844 {0, +, 1}_1 */
845
846tree
847initial_condition_in_loop_num (tree chrec,
848 unsigned loop_num)
849{
850 return chrec_component_in_loop_num (chrec, loop_num, false);
851}
852
853/* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
854 This function is essentially used for setting the evolution to
855 chrec_dont_know, for example after having determined that it is
856 impossible to say how many times a loop will execute. */
857
858tree
859reset_evolution_in_loop (unsigned loop_num,
860 tree chrec,
861 tree new_evol)
862{
863 class loop *loop = get_loop (cfun(cfun + 0), loop_num);
864
865 if (POINTER_TYPE_P (chrec_type (chrec))(((enum tree_code) (chrec_type (chrec))->base.code) == POINTER_TYPE
|| ((enum tree_code) (chrec_type (chrec))->base.code) == REFERENCE_TYPE
))
866 gcc_assert (ptrofftype_p (chrec_type (new_evol)))((void)(!(ptrofftype_p (chrec_type (new_evol))) ? fancy_abort
("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 866, __FUNCTION__), 0 : 0));
867 else
868 gcc_assert (chrec_type (chrec) == chrec_type (new_evol))((void)(!(chrec_type (chrec) == chrec_type (new_evol)) ? fancy_abort
("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 868, __FUNCTION__), 0 : 0));
869
870 if (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLYNOMIAL_CHREC
871 && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
872 {
873 tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 873, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 873, __FUNCTION__))))),
874 new_evol);
875 tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 875, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 875, __FUNCTION__))))),
876 new_evol);
877 return build_polynomial_chrec (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 877, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var, left, right);
878 }
879
880 while (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLYNOMIAL_CHREC
881 && CHREC_VARIABLE (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 881, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var == loop_num)
882 chrec = CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 882, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 882, __FUNCTION__)))));
883
884 return build_polynomial_chrec (loop_num, chrec, new_evol);
885}
886
887/* Merges two evolution functions that were found by following two
888 alternate paths of a conditional expression. */
889
890tree
891chrec_merge (tree chrec1,
892 tree chrec2)
893{
894 if (chrec1 == chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW]
895 || chrec2 == chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW])
896 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
897
898 if (chrec1 == chrec_knownglobal_trees[TI_CHREC_KNOWN]
899 || chrec2 == chrec_knownglobal_trees[TI_CHREC_KNOWN])
900 return chrec_knownglobal_trees[TI_CHREC_KNOWN];
901
902 if (chrec1 == chrec_not_analyzed_yet(tree) nullptr)
903 return chrec2;
904 if (chrec2 == chrec_not_analyzed_yet(tree) nullptr)
905 return chrec1;
906
907 if (eq_evolutions_p (chrec1, chrec2))
908 return chrec1;
909
910 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
911}
912
913
914
915/* Observers. */
916
917/* Helper function for is_multivariate_chrec. */
918
919static bool
920is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
921{
922 if (chrec == NULL_TREE(tree) nullptr)
923 return false;
924
925 if (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLYNOMIAL_CHREC)
926 {
927 if (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 927, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var != rec_var)
928 return true;
929 else
930 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 930, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 930, __FUNCTION__))))), rec_var)
931 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 931, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 931, __FUNCTION__))))), rec_var));
932 }
933 else
934 return false;
935}
936
937/* Determine whether the given chrec is multivariate or not. */
938
939bool
940is_multivariate_chrec (const_tree chrec)
941{
942 if (chrec == NULL_TREE(tree) nullptr)
943 return false;
944
945 if (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLYNOMIAL_CHREC)
946 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 946, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 946, __FUNCTION__))))),
947 CHREC_VARIABLE (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 947, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var)
948 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 948, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 948, __FUNCTION__))))),
949 CHREC_VARIABLE (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 949, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var));
950 else
951 return false;
952}
953
954/* Determines whether the chrec contains symbolic names or not. If LOOP isn't
955 NULL, we also consider chrec wrto outer loops of LOOP as symbol. */
956
957static bool
958chrec_contains_symbols (const_tree chrec, hash_set<const_tree> &visited,
959 class loop *loop)
960{
961 int i, n;
962
963 if (chrec == NULL_TREE(tree) nullptr)
964 return false;
965
966 if (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == SSA_NAME
967 || VAR_P (chrec)(((enum tree_code) (chrec)->base.code) == VAR_DECL)
968 || TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLY_INT_CST
969 || TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == PARM_DECL
970 || TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == FUNCTION_DECL
971 || TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == LABEL_DECL
972 || TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == RESULT_DECL
973 || TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == FIELD_DECL)
974 return true;
975
976 if (loop != NULLnullptr
977 && TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLYNOMIAL_CHREC
978 && flow_loop_nested_p (get_chrec_loop (chrec), loop))
979 return true;
980
981 if (visited.add (chrec))
982 return false;
983
984 n = TREE_OPERAND_LENGTH (chrec)tree_operand_length (chrec);
985 for (i = 0; i < n; i++)
986 if (chrec_contains_symbols (TREE_OPERAND (chrec, i)(*((const_cast<tree*> (tree_operand_check ((chrec), (i)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 986, __FUNCTION__))))), visited, loop))
987 return true;
988 return false;
989}
990
991/* Return true if CHREC contains any symbols. If LOOP is not NULL, check if
992 CHREC contains any chrec which is invariant wrto the loop (nest), in other
993 words, chrec defined by outer loops of loop, so from LOOP's point of view,
994 the chrec is considered as a SYMBOL. */
995
996bool
997chrec_contains_symbols (const_tree chrec, class loop* loop)
998{
999 hash_set<const_tree> visited;
1000 return chrec_contains_symbols (chrec, visited, loop);
1001}
1002
1003/* Return true when CHREC contains symbolic names defined in
1004 LOOP_NB. */
1005
1006static bool
1007chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb,
1008 hash_set<const_tree> &visited)
1009{
1010 int i, n;
1011
1012 if (chrec == NULL_TREE(tree) nullptr)
1013 return false;
1014
1015 if (is_gimple_min_invariant (chrec))
1016 return false;
1017
1018 if (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == SSA_NAME)
1019 {
1020 gimple *def;
1021 loop_p def_loop, loop;
1022
1023 if (SSA_NAME_IS_DEFAULT_DEF (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1023, __FUNCTION__, (SSA_NAME)))->base.default_def_flag)
1024 return false;
1025
1026 def = SSA_NAME_DEF_STMT (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1026, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt;
1027 def_loop = loop_containing_stmt (def);
1028 loop = get_loop (cfun(cfun + 0), loop_nb);
1029
1030 if (def_loop == NULLnullptr)
1031 return false;
1032
1033 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
1034 return true;
1035
1036 return false;
1037 }
1038
1039 if (visited.add (chrec))
1040 return false;
1041
1042 n = TREE_OPERAND_LENGTH (chrec)tree_operand_length (chrec);
1043 for (i = 0; i < n; i++)
1044 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i)(*((const_cast<tree*> (tree_operand_check ((chrec), (i)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1044, __FUNCTION__))))),
1045 loop_nb, visited))
1046 return true;
1047 return false;
1048}
1049
1050/* Return true when CHREC contains symbolic names defined in
1051 LOOP_NB. */
1052
1053bool
1054chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
1055{
1056 hash_set<const_tree> visited;
1057 return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited);
1058}
1059
1060/* Determines whether the chrec contains undetermined coefficients. */
1061
1062static bool
1063chrec_contains_undetermined (const_tree chrec, hash_set<const_tree> &visited)
1064{
1065 int i, n;
1066
1067 if (chrec == chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW])
1068 return true;
1069
1070 if (chrec == NULL_TREE(tree) nullptr)
1071 return false;
1072
1073 if (visited.add (chrec))
1074 return false;
1075
1076 n = TREE_OPERAND_LENGTH (chrec)tree_operand_length (chrec);
1077 for (i = 0; i < n; i++)
1078 if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)(*((const_cast<tree*> (tree_operand_check ((chrec), (i)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1078, __FUNCTION__))))), visited))
1079 return true;
1080 return false;
1081}
1082
1083bool
1084chrec_contains_undetermined (const_tree chrec)
1085{
1086 hash_set<const_tree> visited;
1087 return chrec_contains_undetermined (chrec, visited);
1088}
1089
1090/* Determines whether the tree EXPR contains chrecs, and increment
1091 SIZE if it is not a NULL pointer by an estimation of the depth of
1092 the tree. */
1093
1094static bool
1095tree_contains_chrecs (const_tree expr, int *size, hash_set<const_tree> &visited)
1096{
1097 int i, n;
1098
1099 if (expr == NULL_TREE(tree) nullptr)
1100 return false;
1101
1102 if (size)
1103 (*size)++;
1104
1105 if (tree_is_chrec (expr))
1106 return true;
1107
1108 if (visited.add (expr))
1109 return false;
1110
1111 n = TREE_OPERAND_LENGTH (expr)tree_operand_length (expr);
1112 for (i = 0; i < n; i++)
1113 if (tree_contains_chrecs (TREE_OPERAND (expr, i)(*((const_cast<tree*> (tree_operand_check ((expr), (i),
"/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1113, __FUNCTION__))))), size, visited))
1114 return true;
1115 return false;
1116}
1117
1118bool
1119tree_contains_chrecs (const_tree expr, int *size)
1120{
1121 hash_set<const_tree> visited;
1122 return tree_contains_chrecs (expr, size, visited);
1123}
1124
1125
1126/* Recursive helper function. */
1127
1128static bool
1129evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
1130{
1131 if (evolution_function_is_constant_p (chrec))
1132 return true;
1133
1134 if (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == SSA_NAME
1135 && (loopnum == 0
1136 || expr_invariant_in_loop_p (get_loop (cfun(cfun + 0), loopnum), chrec)))
1137 return true;
1138
1139 if (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLYNOMIAL_CHREC)
1140 {
1141 if (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1141, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var == (unsigned) loopnum
1142 || flow_loop_nested_p (get_loop (cfun(cfun + 0), loopnum),
1143 get_chrec_loop (chrec))
1144 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1144, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1144, __FUNCTION__))))),
1145 loopnum)
1146 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1146, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1146, __FUNCTION__))))),
1147 loopnum))
1148 return false;
1149 return true;
1150 }
1151
1152 switch (TREE_OPERAND_LENGTH (chrec)tree_operand_length (chrec))
1153 {
1154 case 2:
1155 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1)(*((const_cast<tree*> (tree_operand_check ((chrec), (1)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1155, __FUNCTION__))))),
1156 loopnum))
1157 return false;
1158 /* FALLTHRU */
1159
1160 case 1:
1161 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0)(*((const_cast<tree*> (tree_operand_check ((chrec), (0)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1161, __FUNCTION__))))),
1162 loopnum))
1163 return false;
1164 return true;
1165
1166 default:
1167 return false;
1168 }
1169}
1170
1171/* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1172
1173bool
1174evolution_function_is_invariant_p (tree chrec, int loopnum)
1175{
1176 return evolution_function_is_invariant_rec_p (chrec, loopnum);
1177}
1178
1179/* Determine whether the given tree is an affine multivariate
1180 evolution. */
1181
1182bool
1183evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1184{
1185 if (chrec == NULL_TREE(tree) nullptr)
1186 return false;
1187
1188 switch (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code))
1189 {
1190 case POLYNOMIAL_CHREC:
1191 if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1191, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1191, __FUNCTION__))))), loopnum))
1192 {
1193 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1193, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1193, __FUNCTION__))))), loopnum))
1194 return true;
1195 else
1196 {
1197 if (TREE_CODE (CHREC_RIGHT (chrec))((enum tree_code) ((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1197, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1197, __FUNCTION__))))))->base.code) == POLYNOMIAL_CHREC
1198 && CHREC_VARIABLE (CHREC_RIGHT (chrec))(tree_check (((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1198, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1198, __FUNCTION__)))))), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1198, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
1199 != CHREC_VARIABLE (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1199, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
1200 && evolution_function_is_affine_multivariate_p
1201 (CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1201, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1201, __FUNCTION__))))), loopnum))
1202 return true;
1203 else
1204 return false;
1205 }
1206 }
1207 else
1208 {
1209 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1209, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1209, __FUNCTION__))))), loopnum)
1210 && TREE_CODE (CHREC_LEFT (chrec))((enum tree_code) ((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1210, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1210, __FUNCTION__))))))->base.code) == POLYNOMIAL_CHREC
1211 && CHREC_VARIABLE (CHREC_LEFT (chrec))(tree_check (((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1211, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1211, __FUNCTION__)))))), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1211, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var != CHREC_VARIABLE (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1211, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
1212 && evolution_function_is_affine_multivariate_p
1213 (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1213, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1213, __FUNCTION__))))), loopnum))
1214 return true;
1215 else
1216 return false;
1217 }
1218
1219 default:
1220 return false;
1221 }
1222}
1223
1224/* Determine whether the given tree is a function in zero or one
1225 variables with respect to loop specified by LOOPNUM. Note only positive
1226 LOOPNUM stands for a real loop. */
1227
1228bool
1229evolution_function_is_univariate_p (const_tree chrec, int loopnum)
1230{
1231 if (chrec == NULL_TREE(tree) nullptr)
1232 return true;
1233
1234 tree sub_chrec;
1235 switch (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code))
1236 {
1237 case POLYNOMIAL_CHREC:
1238 switch (TREE_CODE (CHREC_LEFT (chrec))((enum tree_code) ((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1238, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1238, __FUNCTION__))))))->base.code))
1239 {
1240 case POLYNOMIAL_CHREC:
1241 sub_chrec = CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1241, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1241, __FUNCTION__)))));
1242 if (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1242, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var != CHREC_VARIABLE (sub_chrec)(tree_check ((sub_chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1242, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
1243 && (loopnum <= 0
1244 || CHREC_VARIABLE (sub_chrec)(tree_check ((sub_chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1244, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var == (unsigned) loopnum
1245 || flow_loop_nested_p (get_loop (cfun(cfun + 0), loopnum),
1246 get_chrec_loop (sub_chrec))))
1247 return false;
1248 if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1249 return false;
1250 break;
1251
1252 default:
1253 if (tree_contains_chrecs (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1253, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1253, __FUNCTION__))))), NULLnullptr))
1254 return false;
1255 break;
1256 }
1257
1258 switch (TREE_CODE (CHREC_RIGHT (chrec))((enum tree_code) ((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1258, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1258, __FUNCTION__))))))->base.code))
1259 {
1260 case POLYNOMIAL_CHREC:
1261 sub_chrec = CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1261, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1261, __FUNCTION__)))));
1262 if (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1262, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var != CHREC_VARIABLE (sub_chrec)(tree_check ((sub_chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1262, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
1263 && (loopnum <= 0
1264 || CHREC_VARIABLE (sub_chrec)(tree_check ((sub_chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1264, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var == (unsigned) loopnum
1265 || flow_loop_nested_p (get_loop (cfun(cfun + 0), loopnum),
1266 get_chrec_loop (sub_chrec))))
1267 return false;
1268 if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1269 return false;
1270 break;
1271
1272 default:
1273 if (tree_contains_chrecs (CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1273, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1273, __FUNCTION__))))), NULLnullptr))
1274 return false;
1275 break;
1276 }
1277 return true;
1278
1279 default:
1280 return true;
1281 }
1282}
1283
1284/* Returns the number of variables of CHREC. Example: the call
1285 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1286
1287unsigned
1288nb_vars_in_chrec (tree chrec)
1289{
1290 if (chrec == NULL_TREE(tree) nullptr)
1291 return 0;
1292
1293 switch (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code))
1294 {
1295 case POLYNOMIAL_CHREC:
1296 return 1 + nb_vars_in_chrec
1297 (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1297, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var));
1298
1299 default:
1300 return 0;
1301 }
1302}
1303
1304/* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1305 the scev corresponds to. AT_STMT is the statement at that the scev is
1306 evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume
1307 that the rules for overflow of the given language apply (e.g., that signed
1308 arithmetics in C does not overflow) -- i.e., to use them to avoid
1309 unnecessary tests, but also to enforce that the result follows them.
1310 FROM is the source variable converted if it's not NULL. Returns true if
1311 the conversion succeeded, false otherwise. */
1312
1313bool
1314convert_affine_scev (class loop *loop, tree type,
1315 tree *base, tree *step, gimple *at_stmt,
1316 bool use_overflow_semantics, tree from)
1317{
1318 tree ct = TREE_TYPE (*step)((contains_struct_check ((*step), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1318, __FUNCTION__))->typed.type);
1319 bool enforce_overflow_semantics;
1320 bool must_check_src_overflow, must_check_rslt_overflow;
1321 tree new_base, new_step;
1322 tree step_type = POINTER_TYPE_P (type)(((enum tree_code) (type)->base.code) == POINTER_TYPE || (
(enum tree_code) (type)->base.code) == REFERENCE_TYPE) ? sizetypesizetype_tab[(int) stk_sizetype] : type;
1323
1324 /* In general,
1325 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1326 but we must check some assumptions.
1327
1328 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1329 of CT is smaller than the precision of TYPE. For example, when we
1330 cast unsigned char [254, +, 1] to unsigned, the values on left side
1331 are 254, 255, 0, 1, ..., but those on the right side are
1332 254, 255, 256, 257, ...
1333 2) In case that we must also preserve the fact that signed ivs do not
1334 overflow, we must additionally check that the new iv does not wrap.
1335 For example, unsigned char [125, +, 1] casted to signed char could
1336 become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1337 which would confuse optimizers that assume that this does not
1338 happen. */
1339 must_check_src_overflow = TYPE_PRECISION (ct)((tree_class_check ((ct), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1339, __FUNCTION__))->type_common.precision) < TYPE_PRECISION (type)((tree_class_check ((type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1339, __FUNCTION__))->type_common.precision);
1340
1341 enforce_overflow_semantics = (use_overflow_semantics
1342 && nowrap_type_p (type));
1343 if (enforce_overflow_semantics)
1344 {
1345 /* We can avoid checking whether the result overflows in the following
1346 cases:
1347
1348 -- must_check_src_overflow is true, and the range of TYPE is superset
1349 of the range of CT -- i.e., in all cases except if CT signed and
1350 TYPE unsigned.
1351 -- both CT and TYPE have the same precision and signedness, and we
1352 verify instead that the source does not overflow (this may be
1353 easier than verifying it for the result, as we may use the
1354 information about the semantics of overflow in CT). */
1355 if (must_check_src_overflow)
1356 {
1357 if (TYPE_UNSIGNED (type)((tree_class_check ((type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1357, __FUNCTION__))->base.u.bits.unsigned_flag) && !TYPE_UNSIGNED (ct)((tree_class_check ((ct), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1357, __FUNCTION__))->base.u.bits.unsigned_flag))
1358 must_check_rslt_overflow = true;
1359 else
1360 must_check_rslt_overflow = false;
1361 }
1362 else if (TYPE_UNSIGNED (ct)((tree_class_check ((ct), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1362, __FUNCTION__))->base.u.bits.unsigned_flag) == TYPE_UNSIGNED (type)((tree_class_check ((type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1362, __FUNCTION__))->base.u.bits.unsigned_flag)
1363 && TYPE_PRECISION (ct)((tree_class_check ((ct), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1363, __FUNCTION__))->type_common.precision) == TYPE_PRECISION (type)((tree_class_check ((type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1363, __FUNCTION__))->type_common.precision))
1364 {
1365 must_check_rslt_overflow = false;
1366 must_check_src_overflow = true;
1367 }
1368 else
1369 must_check_rslt_overflow = true;
1370 }
1371 else
1372 must_check_rslt_overflow = false;
1373
1374 if (must_check_src_overflow
1375 && scev_probably_wraps_p (from, *base, *step, at_stmt, loop,
1376 use_overflow_semantics))
1377 return false;
1378
1379 new_base = chrec_convert (type, *base, at_stmt, use_overflow_semantics);
1380 /* The step must be sign extended, regardless of the signedness
1381 of CT and TYPE. This only needs to be handled specially when
1382 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1383 (with values 100, 99, 98, ...) from becoming signed or unsigned
1384 [100, +, 255] with values 100, 355, ...; the sign-extension is
1385 performed by default when CT is signed. */
1386 new_step = *step;
1387 if (TYPE_PRECISION (step_type)((tree_class_check ((step_type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1387, __FUNCTION__))->type_common.precision) > TYPE_PRECISION (ct)((tree_class_check ((ct), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1387, __FUNCTION__))->type_common.precision) && TYPE_UNSIGNED (ct)((tree_class_check ((ct), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1387, __FUNCTION__))->base.u.bits.unsigned_flag))
1388 {
1389 tree signed_ct = build_nonstandard_integer_type (TYPE_PRECISION (ct)((tree_class_check ((ct), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1389, __FUNCTION__))->type_common.precision), 0);
1390 new_step = chrec_convert (signed_ct, new_step, at_stmt,
1391 use_overflow_semantics);
1392 }
1393 new_step = chrec_convert (step_type, new_step, at_stmt,
1394 use_overflow_semantics);
1395
1396 if (automatically_generated_chrec_p (new_base)
1397 || automatically_generated_chrec_p (new_step))
1398 return false;
1399
1400 if (must_check_rslt_overflow
1401 /* Note that in this case we cannot use the fact that signed variables
1402 do not overflow, as this is what we are verifying for the new iv. */
1403 && scev_probably_wraps_p (NULL_TREE(tree) nullptr, new_base, new_step,
1404 at_stmt, loop, false))
1405 return false;
1406
1407 *base = new_base;
1408 *step = new_step;
1409 return true;
1410}
1411
1412
1413/* Convert CHREC for the right hand side of a CHREC.
1414 The increment for a pointer type is always sizetype. */
1415
1416tree
1417chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt)
1418{
1419 if (POINTER_TYPE_P (type)(((enum tree_code) (type)->base.code) == POINTER_TYPE || (
(enum tree_code) (type)->base.code) == REFERENCE_TYPE))
1420 type = sizetypesizetype_tab[(int) stk_sizetype];
1421
1422 return chrec_convert (type, chrec, at_stmt);
1423}
1424
1425/* Convert CHREC to TYPE. When the analyzer knows the context in
1426 which the CHREC is built, it sets AT_STMT to the statement that
1427 contains the definition of the analyzed variable, otherwise the
1428 conversion is less accurate: the information is used for
1429 determining a more accurate estimation of the number of iterations.
1430 By default AT_STMT could be safely set to NULL_TREE.
1431
1432 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1433 the rules for overflow of the given language apply (e.g., that signed
1434 arithmetics in C does not overflow) -- i.e., to use them to avoid
1435 unnecessary tests, but also to enforce that the result follows them.
1436
1437 FROM is the source variable converted if it's not NULL. */
1438
1439static tree
1440chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
1441 bool use_overflow_semantics, tree from)
1442{
1443 tree ct, res;
1444 tree base, step;
1445 class loop *loop;
1446
1447 if (automatically_generated_chrec_p (chrec))
1448 return chrec;
1449
1450 ct = chrec_type (chrec);
1451 if (useless_type_conversion_p (type, ct))
1452 return chrec;
1453
1454 if (!evolution_function_is_affine_p (chrec))
1455 goto keep_cast;
1456
1457 loop = get_chrec_loop (chrec);
1458 base = CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1458, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1458, __FUNCTION__)))));
1459 step = CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1459, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1459, __FUNCTION__)))));
1460
1461 if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1462 use_overflow_semantics, from))
1463 return build_polynomial_chrec (loop->num, base, step);
1464
1465 /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1466keep_cast:
1467 /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1468 may be more expensive. We do want to perform this optimization here
1469 though for canonicalization reasons. */
1470 if (use_overflow_semantics
1471 && (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == PLUS_EXPR
1472 || TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == MINUS_EXPR)
1473 && TREE_CODE (type)((enum tree_code) (type)->base.code) == INTEGER_TYPE
1474 && TREE_CODE (ct)((enum tree_code) (ct)->base.code) == INTEGER_TYPE
1475 && TYPE_PRECISION (type)((tree_class_check ((type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1475, __FUNCTION__))->type_common.precision) > TYPE_PRECISION (ct)((tree_class_check ((ct), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1475, __FUNCTION__))->type_common.precision)
1476 && TYPE_OVERFLOW_UNDEFINED (ct)((((enum tree_code) (ct)->base.code) == POINTER_TYPE || ((
enum tree_code) (ct)->base.code) == REFERENCE_TYPE) ? !global_options
.x_flag_wrapv_pointer : (!(any_integral_type_check ((ct), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1476, __FUNCTION__))->base.u.bits.unsigned_flag &&
!global_options.x_flag_wrapv && !global_options.x_flag_trapv
)))
1477 res = fold_build2 (TREE_CODE (chrec), type,fold_build2_loc (((location_t) 0), ((enum tree_code) (chrec)->
base.code), type, fold_convert_loc (((location_t) 0), type, (
*((const_cast<tree*> (tree_operand_check ((chrec), (0),
"/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1478, __FUNCTION__)))))), fold_convert_loc (((location_t) 0
), type, (*((const_cast<tree*> (tree_operand_check ((chrec
), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1479, __FUNCTION__)))))) )
1478 fold_convert (type, TREE_OPERAND (chrec, 0)),fold_build2_loc (((location_t) 0), ((enum tree_code) (chrec)->
base.code), type, fold_convert_loc (((location_t) 0), type, (
*((const_cast<tree*> (tree_operand_check ((chrec), (0),
"/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1478, __FUNCTION__)))))), fold_convert_loc (((location_t) 0
), type, (*((const_cast<tree*> (tree_operand_check ((chrec
), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1479, __FUNCTION__)))))) )
1479 fold_convert (type, TREE_OPERAND (chrec, 1)))fold_build2_loc (((location_t) 0), ((enum tree_code) (chrec)->
base.code), type, fold_convert_loc (((location_t) 0), type, (
*((const_cast<tree*> (tree_operand_check ((chrec), (0),
"/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1478, __FUNCTION__)))))), fold_convert_loc (((location_t) 0
), type, (*((const_cast<tree*> (tree_operand_check ((chrec
), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1479, __FUNCTION__)))))) );
1480 /* Similar perform the trick that (signed char)((int)x + 2) can be
1481 narrowed to (signed char)((unsigned char)x + 2). */
1482 else if (use_overflow_semantics
1483 && TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLYNOMIAL_CHREC
1484 && TREE_CODE (ct)((enum tree_code) (ct)->base.code) == INTEGER_TYPE
1485 && TREE_CODE (type)((enum tree_code) (type)->base.code) == INTEGER_TYPE
1486 && TYPE_OVERFLOW_UNDEFINED (type)((((enum tree_code) (type)->base.code) == POINTER_TYPE || (
(enum tree_code) (type)->base.code) == REFERENCE_TYPE) ? !
global_options.x_flag_wrapv_pointer : (!(any_integral_type_check
((type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1486, __FUNCTION__))->base.u.bits.unsigned_flag &&
!global_options.x_flag_wrapv && !global_options.x_flag_trapv
))
1487 && TYPE_PRECISION (type)((tree_class_check ((type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1487, __FUNCTION__))->type_common.precision) < TYPE_PRECISION (ct)((tree_class_check ((ct), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1487, __FUNCTION__))->type_common.precision))
1488 {
1489 tree utype = unsigned_type_for (type);
1490 res = build_polynomial_chrec (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1490, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var,
1491 fold_convert (utype,fold_convert_loc (((location_t) 0), utype, (*((const_cast<
tree*> (tree_operand_check (((tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1492, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1492, __FUNCTION__))))))
1492 CHREC_LEFT (chrec))fold_convert_loc (((location_t) 0), utype, (*((const_cast<
tree*> (tree_operand_check (((tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1492, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1492, __FUNCTION__)))))),
1493 fold_convert (utype,fold_convert_loc (((location_t) 0), utype, (*((const_cast<
tree*> (tree_operand_check (((tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1494, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1494, __FUNCTION__))))))
1494 CHREC_RIGHT (chrec))fold_convert_loc (((location_t) 0), utype, (*((const_cast<
tree*> (tree_operand_check (((tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1494, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1494, __FUNCTION__)))))));
1495 res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
1496 }
1497 else
1498 res = fold_convert (type, chrec)fold_convert_loc (((location_t) 0), type, chrec);
1499
1500 /* Don't propagate overflows. */
1501 if (CONSTANT_CLASS_P (res)(tree_code_type_tmpl <0>::tree_code_type[(int) (((enum tree_code
) (res)->base.code))] == tcc_constant))
1502 TREE_OVERFLOW (res)((tree_class_check ((res), (tcc_constant), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1502, __FUNCTION__))->base.public_flag) = 0;
1503
1504 /* But reject constants that don't fit in their type after conversion.
1505 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1506 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1507 and can cause problems later when computing niters of loops. Note
1508 that we don't do the check before converting because we don't want
1509 to reject conversions of negative chrecs to unsigned types. */
1510 if (TREE_CODE (res)((enum tree_code) (res)->base.code) == INTEGER_CST
1511 && TREE_CODE (type)((enum tree_code) (type)->base.code) == INTEGER_TYPE
1512 && !int_fits_type_p (res, type))
1513 res = chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
1514
1515 return res;
1516}
1517
1518/* Convert CHREC to TYPE. When the analyzer knows the context in
1519 which the CHREC is built, it sets AT_STMT to the statement that
1520 contains the definition of the analyzed variable, otherwise the
1521 conversion is less accurate: the information is used for
1522 determining a more accurate estimation of the number of iterations.
1523 By default AT_STMT could be safely set to NULL_TREE.
1524
1525 The following rule is always true: TREE_TYPE (chrec) ==
1526 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1527 An example of what could happen when adding two chrecs and the type
1528 of the CHREC_RIGHT is different than CHREC_LEFT is:
1529
1530 {(uint) 0, +, (uchar) 10} +
1531 {(uint) 0, +, (uchar) 250}
1532
1533 that would produce a wrong result if CHREC_RIGHT is not (uint):
1534
1535 {(uint) 0, +, (uchar) 4}
1536
1537 instead of
1538
1539 {(uint) 0, +, (uint) 260}
1540
1541 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1542 the rules for overflow of the given language apply (e.g., that signed
1543 arithmetics in C does not overflow) -- i.e., to use them to avoid
1544 unnecessary tests, but also to enforce that the result follows them.
1545
1546 FROM is the source variable converted if it's not NULL. */
1547
1548tree
1549chrec_convert (tree type, tree chrec, gimple *at_stmt,
1550 bool use_overflow_semantics, tree from)
1551{
1552 return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from);
1553}
1554
1555/* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1556 chrec if something else than what chrec_convert would do happens, NULL_TREE
1557 otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS
1558 if the result chrec may overflow. */
1559
1560tree
1561chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions)
1562{
1563 tree inner_type, left, right, lc, rc, rtype;
1564
1565 gcc_assert (fold_conversions != NULL)((void)(!(fold_conversions != nullptr) ? fancy_abort ("/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1565, __FUNCTION__), 0 : 0));
1566
1567 if (automatically_generated_chrec_p (chrec)
1568 || TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) != POLYNOMIAL_CHREC)
1569 return NULL_TREE(tree) nullptr;
1570
1571 inner_type = TREE_TYPE (chrec)((contains_struct_check ((chrec), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1571, __FUNCTION__))->typed.type);
1572 if (TYPE_PRECISION (type)((tree_class_check ((type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1572, __FUNCTION__))->type_common.precision) > TYPE_PRECISION (inner_type)((tree_class_check ((inner_type), (tcc_type), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1572, __FUNCTION__))->type_common.precision))
1573 return NULL_TREE(tree) nullptr;
1574
1575 if (useless_type_conversion_p (type, inner_type))
1576 return NULL_TREE(tree) nullptr;
1577
1578 if (!*fold_conversions && evolution_function_is_affine_p (chrec))
1579 {
1580 tree base, step;
1581 class loop *loop;
1582
1583 loop = get_chrec_loop (chrec);
1584 base = CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1584, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1584, __FUNCTION__)))));
1585 step = CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1585, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1585, __FUNCTION__)))));
1586 if (convert_affine_scev (loop, type, &base, &step, NULLnullptr, true))
1587 return build_polynomial_chrec (loop->num, base, step);
1588 }
1589 rtype = POINTER_TYPE_P (type)(((enum tree_code) (type)->base.code) == POINTER_TYPE || (
(enum tree_code) (type)->base.code) == REFERENCE_TYPE) ? sizetypesizetype_tab[(int) stk_sizetype] : type;
1590
1591 left = CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1591, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1591, __FUNCTION__)))));
1592 right = CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1592, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1592, __FUNCTION__)))));
1593 lc = chrec_convert_aggressive (type, left, fold_conversions);
1594 if (!lc)
1595 lc = chrec_convert (type, left, NULLnullptr);
1596 rc = chrec_convert_aggressive (rtype, right, fold_conversions);
1597 if (!rc)
1598 rc = chrec_convert (rtype, right, NULLnullptr);
1599
1600 *fold_conversions = true;
1601
1602 return build_polynomial_chrec (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1602, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var, lc, rc);
1603}
1604
1605/* Returns true when CHREC0 == CHREC1. */
1606
1607bool
1608eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1609{
1610 if (chrec0 == NULL_TREE(tree) nullptr
1611 || chrec1 == NULL_TREE(tree) nullptr
1612 || TREE_CODE (chrec0)((enum tree_code) (chrec0)->base.code) != TREE_CODE (chrec1)((enum tree_code) (chrec1)->base.code))
1613 return false;
1614
1615 if (chrec0 == chrec1)
1616 return true;
1617
1618 if (! types_compatible_p (TREE_TYPE (chrec0)((contains_struct_check ((chrec0), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1618, __FUNCTION__))->typed.type), TREE_TYPE (chrec1)((contains_struct_check ((chrec1), (TS_TYPED), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1618, __FUNCTION__))->typed.type)))
1619 return false;
1620
1621 switch (TREE_CODE (chrec0)((enum tree_code) (chrec0)->base.code))
1622 {
1623 case POLYNOMIAL_CHREC:
1624 return (CHREC_VARIABLE (chrec0)(tree_check ((chrec0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1624, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var == CHREC_VARIABLE (chrec1)(tree_check ((chrec1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1624, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
1625 && eq_evolutions_p (CHREC_LEFT (chrec0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1625, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1625, __FUNCTION__))))), CHREC_LEFT (chrec1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1625, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1625, __FUNCTION__))))))
1626 && eq_evolutions_p (CHREC_RIGHT (chrec0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1626, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1626, __FUNCTION__))))), CHREC_RIGHT (chrec1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1626, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1626, __FUNCTION__)))))));
1627
1628 case PLUS_EXPR:
1629 case MULT_EXPR:
1630 case MINUS_EXPR:
1631 case POINTER_PLUS_EXPR:
1632 return eq_evolutions_p (TREE_OPERAND (chrec0, 0)(*((const_cast<tree*> (tree_operand_check ((chrec0), (0
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1632, __FUNCTION__))))),
1633 TREE_OPERAND (chrec1, 0)(*((const_cast<tree*> (tree_operand_check ((chrec1), (0
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1633, __FUNCTION__))))))
1634 && eq_evolutions_p (TREE_OPERAND (chrec0, 1)(*((const_cast<tree*> (tree_operand_check ((chrec0), (1
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1634, __FUNCTION__))))),
1635 TREE_OPERAND (chrec1, 1)(*((const_cast<tree*> (tree_operand_check ((chrec1), (1
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1635, __FUNCTION__))))));
1636
1637 CASE_CONVERTcase NOP_EXPR: case CONVERT_EXPR:
1638 return eq_evolutions_p (TREE_OPERAND (chrec0, 0)(*((const_cast<tree*> (tree_operand_check ((chrec0), (0
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1638, __FUNCTION__))))),
1639 TREE_OPERAND (chrec1, 0)(*((const_cast<tree*> (tree_operand_check ((chrec1), (0
), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1639, __FUNCTION__))))));
1640
1641 default:
1642 return operand_equal_p (chrec0, chrec1, 0);
1643 }
1644}
1645
1646/* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1647 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1648 which of these cases happens. */
1649
1650enum ev_direction
1651scev_direction (const_tree chrec)
1652{
1653 const_tree step;
1654
1655 if (!evolution_function_is_affine_p (chrec))
1656 return EV_DIR_UNKNOWN;
1657
1658 step = CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1658, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1658, __FUNCTION__)))));
1659 if (TREE_CODE (step)((enum tree_code) (step)->base.code) != INTEGER_CST)
1660 return EV_DIR_UNKNOWN;
1661
1662 if (tree_int_cst_sign_bit (step))
1663 return EV_DIR_DECREASES;
1664 else
1665 return EV_DIR_GROWS;
1666}
1667
1668/* Iterates over all the components of SCEV, and calls CBCK. */
1669
1670void
1671for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1672{
1673 switch (TREE_CODE_LENGTH (TREE_CODE (*scev))tree_code_length_tmpl <0>::tree_code_length[(int) (((enum
tree_code) (*scev)->base.code))])
1674 {
1675 case 3:
1676 for_each_scev_op (&TREE_OPERAND (*scev, 2)(*((const_cast<tree*> (tree_operand_check ((*scev), (2)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1676, __FUNCTION__))))), cbck, data);
1677 /* FALLTHRU */
1678
1679 case 2:
1680 for_each_scev_op (&TREE_OPERAND (*scev, 1)(*((const_cast<tree*> (tree_operand_check ((*scev), (1)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1680, __FUNCTION__))))), cbck, data);
1681 /* FALLTHRU */
1682
1683 case 1:
1684 for_each_scev_op (&TREE_OPERAND (*scev, 0)(*((const_cast<tree*> (tree_operand_check ((*scev), (0)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1684, __FUNCTION__))))), cbck, data);
1685 /* FALLTHRU */
1686
1687 default:
1688 cbck (scev, data);
1689 break;
1690 }
1691}
1692
1693/* Returns true when the operation can be part of a linear
1694 expression. */
1695
1696static inline bool
1697operator_is_linear (tree scev)
1698{
1699 switch (TREE_CODE (scev)((enum tree_code) (scev)->base.code))
1700 {
1701 case INTEGER_CST:
1702 case POLYNOMIAL_CHREC:
1703 case PLUS_EXPR:
1704 case POINTER_PLUS_EXPR:
1705 case MULT_EXPR:
1706 case MINUS_EXPR:
1707 case NEGATE_EXPR:
1708 case SSA_NAME:
1709 case NON_LVALUE_EXPR:
1710 case BIT_NOT_EXPR:
1711 CASE_CONVERTcase NOP_EXPR: case CONVERT_EXPR:
1712 return true;
1713
1714 default:
1715 return false;
1716 }
1717}
1718
1719/* Return true when SCEV is a linear expression. Linear expressions
1720 can contain additions, substractions and multiplications.
1721 Multiplications are restricted to constant scaling: "cst * x". */
1722
1723bool
1724scev_is_linear_expression (tree scev)
1725{
1726 if (evolution_function_is_constant_p (scev))
1727 return true;
1728
1729 if (scev == NULLnullptr
1730 || !operator_is_linear (scev))
1731 return false;
1732
1733 if (TREE_CODE (scev)((enum tree_code) (scev)->base.code) == MULT_EXPR)
1734 return !(tree_contains_chrecs (TREE_OPERAND (scev, 0)(*((const_cast<tree*> (tree_operand_check ((scev), (0),
"/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1734, __FUNCTION__))))), NULLnullptr)
1735 && tree_contains_chrecs (TREE_OPERAND (scev, 1)(*((const_cast<tree*> (tree_operand_check ((scev), (1),
"/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1735, __FUNCTION__))))), NULLnullptr));
1736
1737 if (TREE_CODE (scev)((enum tree_code) (scev)->base.code) == POLYNOMIAL_CHREC
1738 && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)(tree_check ((scev), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1738, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var))
1739 return false;
1740
1741 switch (TREE_CODE_LENGTH (TREE_CODE (scev))tree_code_length_tmpl <0>::tree_code_length[(int) (((enum
tree_code) (scev)->base.code))])
1742 {
1743 case 3:
1744 return scev_is_linear_expression (TREE_OPERAND (scev, 0)(*((const_cast<tree*> (tree_operand_check ((scev), (0),
"/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1744, __FUNCTION__))))))
1745 && scev_is_linear_expression (TREE_OPERAND (scev, 1)(*((const_cast<tree*> (tree_operand_check ((scev), (1),
"/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1745, __FUNCTION__))))))
1746 && scev_is_linear_expression (TREE_OPERAND (scev, 2)(*((const_cast<tree*> (tree_operand_check ((scev), (2),
"/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1746, __FUNCTION__))))));
1747
1748 case 2:
1749 return scev_is_linear_expression (TREE_OPERAND (scev, 0)(*((const_cast<tree*> (tree_operand_check ((scev), (0),
"/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1749, __FUNCTION__))))))
1750 && scev_is_linear_expression (TREE_OPERAND (scev, 1)(*((const_cast<tree*> (tree_operand_check ((scev), (1),
"/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1750, __FUNCTION__))))));
1751
1752 case 1:
1753 return scev_is_linear_expression (TREE_OPERAND (scev, 0)(*((const_cast<tree*> (tree_operand_check ((scev), (0),
"/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1753, __FUNCTION__))))));
1754
1755 case 0:
1756 return true;
1757
1758 default:
1759 return false;
1760 }
1761}
1762
1763/* Determines whether the expression CHREC contains only interger consts
1764 in the right parts. */
1765
1766bool
1767evolution_function_right_is_integer_cst (const_tree chrec)
1768{
1769 if (chrec == NULL_TREE(tree) nullptr)
1770 return false;
1771
1772 switch (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code))
1773 {
1774 case INTEGER_CST:
1775 return true;
1776
1777 case POLYNOMIAL_CHREC:
1778 return TREE_CODE (CHREC_RIGHT (chrec))((enum tree_code) ((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1778, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1778, __FUNCTION__))))))->base.code) == INTEGER_CST
1779 && (TREE_CODE (CHREC_LEFT (chrec))((enum tree_code) ((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1779, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1779, __FUNCTION__))))))->base.code) != POLYNOMIAL_CHREC
1780 || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1780, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1780, __FUNCTION__)))))));
1781
1782 CASE_CONVERTcase NOP_EXPR: case CONVERT_EXPR:
1783 return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0)(*((const_cast<tree*> (tree_operand_check ((chrec), (0)
, "/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.cc"
, 1783, __FUNCTION__))))));
1784
1785 default:
1786 return false;
1787 }
1788}