Bug Summary

File:build/gcc/tree-chrec.c
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-unknown-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name tree-chrec.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -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 -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -fno-split-dwarf-inlining -debugger-tuning=gdb -resource-dir /usr/lib64/clang/11.0.0 -D IN_GCC -D HAVE_CONFIG_H -I . -I . -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/. -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../include -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libcpp/include -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libcody -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libdecnumber -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libdecnumber/bid -I ../libdecnumber -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libbacktrace -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/10/../../../../include/c++/10 -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/10/../../../../include/c++/10/x86_64-suse-linux -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/10/../../../../include/c++/10/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib64/clang/11.0.0/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-narrowing -Wwrite-strings -Wno-error=format-diag -Wno-long-long -Wno-variadic-macros -Wno-overlength-strings -fdeprecated-macro -fdebug-compilation-dir /home/marxin/BIG/buildbot/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 -o /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/clang-static-analyzer/2021-01-16-135054-17580-1/report-3TRMkk.plist -x c++ /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c
1/* Chains of recurrences.
2 Copyright (C) 2003-2021 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 ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 58, __FUNCTION__), 0 : 0))
;
59 gcc_assert (poly1)((void)(!(poly1) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 59, __FUNCTION__), 0 : 0))
;
60 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC)((void)(!(((enum tree_code) (poly0)->base.code) == POLYNOMIAL_CHREC
) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 60, __FUNCTION__), 0 : 0))
;
61 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC)((void)(!(((enum tree_code) (poly1)->base.code) == POLYNOMIAL_CHREC
) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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 ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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 ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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 ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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 ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 78, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 78, __FUNCTION__)))))
),
79 CHREC_RIGHT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 79, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 79, __FUNCTION__)))))
);
80 else
81 return build_polynomial_chrec
82 (CHREC_VARIABLE (poly1)(tree_check ((poly1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 83, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 83, __FUNCTION__)))))
),
84 chrec_fold_multiply (type, CHREC_RIGHT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 84, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 95, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 95, __FUNCTION__)))))
, poly1),
96 CHREC_RIGHT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 96, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 96, __FUNCTION__)))))
);
97 else
98 return build_polynomial_chrec
99 (CHREC_VARIABLE (poly0)(tree_check ((poly0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 100, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 100, __FUNCTION__)))))
, poly1),
101 CHREC_RIGHT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 101, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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
("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 116, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 116, __FUNCTION__)))))
, CHREC_LEFT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 116, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 116, __FUNCTION__)))))
);
117 right = chrec_fold_plus
118 (rtype, CHREC_RIGHT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 118, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 118, __FUNCTION__)))))
, CHREC_RIGHT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 118, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 123, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 123, __FUNCTION__)))))
, CHREC_LEFT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 123, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 123, __FUNCTION__)))))
);
124 right = chrec_fold_minus
125 (type, CHREC_RIGHT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 125, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 125, __FUNCTION__)))))
, CHREC_RIGHT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 125, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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 ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 149, __FUNCTION__), 0 : 0))
;
150 gcc_assert (poly1)((void)(!(poly1) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 150, __FUNCTION__), 0 : 0))
;
151 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC)((void)(!(((enum tree_code) (poly0)->base.code) == POLYNOMIAL_CHREC
) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 151, __FUNCTION__), 0 : 0))
;
152 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC)((void)(!(((enum tree_code) (poly1)->base.code) == POLYNOMIAL_CHREC
) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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 ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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 ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 163, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 163, __FUNCTION__)))))
, poly0),
164 CHREC_RIGHT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 164, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 170, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 170, __FUNCTION__)))))
, poly1),
171 CHREC_RIGHT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 171, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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
("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 184, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 184, __FUNCTION__)))))
, CHREC_LEFT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 184, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 187, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 187, __FUNCTION__)))))
, CHREC_RIGHT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 187, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 189, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 189, __FUNCTION__)))))
,
190 CHREC_LEFT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 190, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 190, __FUNCTION__)))))
));
191 /* "b*d". */
192 t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 192, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 192, __FUNCTION__)))))
, CHREC_RIGHT (poly1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((poly1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 192, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 242, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 242, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 248, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 248, __FUNCTION__), 0 : 0))
247 (!chrec_contains_symbols_defined_in_loop (op1,((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 248, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 248, __FUNCTION__), 0 : 0))
248 CHREC_VARIABLE (op1)))((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 248, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 255, __FUNCTION__)))))), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 275, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 275, __FUNCTION__)))))
, op1),
276 CHREC_RIGHT (op0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((op0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 276, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 276, __FUNCTION__)))))
);
277 else
278 return build_polynomial_chrec
279 (CHREC_VARIABLE (op0)(tree_check ((op0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 280, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 280, __FUNCTION__)))))
, op1),
281 CHREC_RIGHT (op0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((op0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 281, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 288, __FUNCTION__)))))), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 310, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 310, __FUNCTION__), 0 : 0))
309 (!chrec_contains_symbols_defined_in_loop (op1,((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 310, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 310, __FUNCTION__), 0 : 0))
310 CHREC_VARIABLE (op1)))((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 310, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 314, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 314, __FUNCTION__)))))
),
315 CHREC_RIGHT (op1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((op1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 315, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 315, __FUNCTION__)))))
);
316 else
317 return build_polynomial_chrec
318 (CHREC_VARIABLE (op1)(tree_check ((op1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 319, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 319, __FUNCTION__)))))
),
320 chrec_fold_multiply (type, CHREC_RIGHT (op1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((op1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 320, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 411, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 411, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 417, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 417, __FUNCTION__), 0 : 0))
416 (!chrec_contains_symbols_defined_in_loop (op1,((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 417, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 417, __FUNCTION__), 0 : 0))
417 CHREC_VARIABLE (op1)))((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 417, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 433, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 433, __FUNCTION__)))))
, op1),
434 chrec_fold_multiply (type, CHREC_RIGHT (op0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((op0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 434, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 454, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 454, __FUNCTION__), 0 : 0))
453 (!chrec_contains_symbols_defined_in_loop (op1,((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 454, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 454, __FUNCTION__), 0 : 0))
454 CHREC_VARIABLE (op1)))((void)(!(!chrec_contains_symbols_defined_in_loop (op1, (tree_check
((op1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 454, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 454, __FUNCTION__), 0 : 0))
;
455 return build_polynomial_chrec
456 (CHREC_VARIABLE (op1)(tree_check ((op1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 457, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 457, __FUNCTION__)))))
, op0),
458 chrec_fold_multiply (type, CHREC_RIGHT (op1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((op1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 458, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 545, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 557, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 563, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 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 if (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 615, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
!= var)
616 return build_polynomial_chrec
617 (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 617, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
,
618 chrec_apply (var, CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 618, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 618, __FUNCTION__)))))
, x),
619 chrec_apply (var, CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 619, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 619, __FUNCTION__)))))
, x));
620
621 /* "{a, +, b} (x)" -> "a + b*x". */
622 x = chrec_convert_rhs (type, x, NULLnullptr);
623 res = chrec_fold_multiply (TREE_TYPE (x)((contains_struct_check ((x), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 623, __FUNCTION__))->typed.type)
, CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 623, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 623, __FUNCTION__)))))
, x);
624 res = chrec_fold_plus (type, CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 624, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 624, __FUNCTION__)))))
, res);
625 }
626 else if (TREE_CODE (x)((enum tree_code) (x)->base.code) == INTEGER_CST
627 && tree_int_cst_sgn (x) == 1)
628 /* testsuite/.../ssa-chrec-38.c. */
629 res = chrec_convert (type, chrec_evaluate (var, chrec, x, 0), NULLnullptr);
630 else
631 res = chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
632 break;
633
634 CASE_CONVERTcase NOP_EXPR: case CONVERT_EXPR:
635 res = chrec_convert (TREE_TYPE (chrec)((contains_struct_check ((chrec), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 635, __FUNCTION__))->typed.type)
,
636 chrec_apply (var, TREE_OPERAND (chrec, 0)(*((const_cast<tree*> (tree_operand_check ((chrec), (0)
, "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 636, __FUNCTION__)))))
, x),
637 NULLnullptr);
638 break;
639
640 default:
641 res = chrec;
642 break;
643 }
644
645 if (dump_file && (dump_flags & TDF_SCEV))
646 {
647 fprintf (dump_file, " (varying_loop = %d\n", var);
648 fprintf (dump_file, ")\n (chrec = ");
649 print_generic_expr (dump_file, chrec);
650 fprintf (dump_file, ")\n (x = ");
651 print_generic_expr (dump_file, x);
652 fprintf (dump_file, ")\n (res = ");
653 print_generic_expr (dump_file, res);
654 fprintf (dump_file, "))\n");
655 }
656
657 return res;
658}
659
660/* For a given CHREC and an induction variable map IV_MAP that maps
661 (loop->num, expr) for every loop number of the current_loops an
662 expression, calls chrec_apply when the expression is not NULL. */
663
664tree
665chrec_apply_map (tree chrec, vec<tree> iv_map)
666{
667 int i;
668 tree expr;
669
670 FOR_EACH_VEC_ELT (iv_map, i, expr)for (i = 0; (iv_map).iterate ((i), &(expr)); ++(i))
671 if (expr)
672 chrec = chrec_apply (i, chrec, expr);
673
674 return chrec;
675}
676
677/* Replaces the initial condition in CHREC with INIT_COND. */
678
679tree
680chrec_replace_initial_condition (tree chrec,
681 tree init_cond)
682{
683 if (automatically_generated_chrec_p (chrec))
684 return chrec;
685
686 gcc_assert (chrec_type (chrec) == chrec_type (init_cond))((void)(!(chrec_type (chrec) == chrec_type (init_cond)) ? fancy_abort
("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 686, __FUNCTION__), 0 : 0))
;
687
688 switch (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code))
689 {
690 case POLYNOMIAL_CHREC:
691 return build_polynomial_chrec
692 (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 692, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
,
693 chrec_replace_initial_condition (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 693, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 693, __FUNCTION__)))))
, init_cond),
694 CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 694, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 694, __FUNCTION__)))))
);
695
696 default:
697 return init_cond;
698 }
699}
700
701/* Returns the initial condition of a given CHREC. */
702
703tree
704initial_condition (tree chrec)
705{
706 if (automatically_generated_chrec_p (chrec))
707 return chrec;
708
709 if (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLYNOMIAL_CHREC)
710 return initial_condition (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 710, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 710, __FUNCTION__)))))
);
711 else
712 return chrec;
713}
714
715/* Returns a univariate function that represents the evolution in
716 LOOP_NUM. Mask the evolution of any other loop. */
717
718tree
719hide_evolution_in_other_loops_than_loop (tree chrec,
720 unsigned loop_num)
721{
722 class loop *loop = get_loop (cfun(cfun + 0), loop_num), *chloop;
723 if (automatically_generated_chrec_p (chrec))
724 return chrec;
725
726 switch (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code))
727 {
728 case POLYNOMIAL_CHREC:
729 chloop = get_chrec_loop (chrec);
730
731 if (chloop == loop)
732 return build_polynomial_chrec
733 (loop_num,
734 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 734, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 734, __FUNCTION__)))))
,
735 loop_num),
736 CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 736, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 736, __FUNCTION__)))))
);
737
738 else if (flow_loop_nested_p (chloop, loop))
739 /* There is no evolution in this loop. */
740 return initial_condition (chrec);
741
742 else if (flow_loop_nested_p (loop, chloop))
743 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 743, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 743, __FUNCTION__)))))
,
744 loop_num);
745
746 else
747 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
748
749 default:
750 return chrec;
751 }
752}
753
754/* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
755 true, otherwise returns the initial condition in LOOP_NUM. */
756
757static tree
758chrec_component_in_loop_num (tree chrec,
759 unsigned loop_num,
760 bool right)
761{
762 tree component;
763 class loop *loop = get_loop (cfun(cfun + 0), loop_num), *chloop;
764
765 if (automatically_generated_chrec_p (chrec))
766 return chrec;
767
768 switch (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code))
769 {
770 case POLYNOMIAL_CHREC:
771 chloop = get_chrec_loop (chrec);
772
773 if (chloop == loop)
774 {
775 if (right)
776 component = CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 776, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 776, __FUNCTION__)))))
;
777 else
778 component = CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 778, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 778, __FUNCTION__)))))
;
779
780 if (TREE_CODE (CHREC_LEFT (chrec))((enum tree_code) ((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 780, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 780, __FUNCTION__))))))->base.code)
!= POLYNOMIAL_CHREC
781 || CHREC_VARIABLE (CHREC_LEFT (chrec))(tree_check (((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 781, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 781, __FUNCTION__)))))), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 781, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
!= CHREC_VARIABLE (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 781, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)
782 return component;
783
784 else
785 return build_polynomial_chrec
786 (loop_num,
787 chrec_component_in_loop_num (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 787, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 787, __FUNCTION__)))))
,
788 loop_num,
789 right),
790 component);
791 }
792
793 else if (flow_loop_nested_p (chloop, loop))
794 /* There is no evolution part in this loop. */
795 return NULL_TREE(tree) nullptr;
796
797 else
798 {
799 gcc_assert (flow_loop_nested_p (loop, chloop))((void)(!(flow_loop_nested_p (loop, chloop)) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 799, __FUNCTION__), 0 : 0))
;
800 return chrec_component_in_loop_num (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 800, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 800, __FUNCTION__)))))
,
801 loop_num,
802 right);
803 }
804
805 default:
806 if (right)
807 return NULL_TREE(tree) nullptr;
808 else
809 return chrec;
810 }
811}
812
813/* Returns the evolution part in LOOP_NUM. Example: the call
814 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
815 {1, +, 2}_1 */
816
817tree
818evolution_part_in_loop_num (tree chrec,
819 unsigned loop_num)
820{
821 return chrec_component_in_loop_num (chrec, loop_num, true);
822}
823
824/* Returns the initial condition in LOOP_NUM. Example: the call
825 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
826 {0, +, 1}_1 */
827
828tree
829initial_condition_in_loop_num (tree chrec,
830 unsigned loop_num)
831{
832 return chrec_component_in_loop_num (chrec, loop_num, false);
833}
834
835/* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
836 This function is essentially used for setting the evolution to
837 chrec_dont_know, for example after having determined that it is
838 impossible to say how many times a loop will execute. */
839
840tree
841reset_evolution_in_loop (unsigned loop_num,
842 tree chrec,
843 tree new_evol)
844{
845 class loop *loop = get_loop (cfun(cfun + 0), loop_num);
846
847 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
)
)
848 gcc_assert (ptrofftype_p (chrec_type (new_evol)))((void)(!(ptrofftype_p (chrec_type (new_evol))) ? fancy_abort
("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 848, __FUNCTION__), 0 : 0))
;
849 else
850 gcc_assert (chrec_type (chrec) == chrec_type (new_evol))((void)(!(chrec_type (chrec) == chrec_type (new_evol)) ? fancy_abort
("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 850, __FUNCTION__), 0 : 0))
;
851
852 if (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLYNOMIAL_CHREC
853 && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
854 {
855 tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 855, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 855, __FUNCTION__)))))
,
856 new_evol);
857 tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 857, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 857, __FUNCTION__)))))
,
858 new_evol);
859 return build_polynomial_chrec (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 859, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
, left, right);
860 }
861
862 while (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLYNOMIAL_CHREC
863 && CHREC_VARIABLE (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 863, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
== loop_num)
864 chrec = CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 864, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 864, __FUNCTION__)))))
;
865
866 return build_polynomial_chrec (loop_num, chrec, new_evol);
867}
868
869/* Merges two evolution functions that were found by following two
870 alternate paths of a conditional expression. */
871
872tree
873chrec_merge (tree chrec1,
874 tree chrec2)
875{
876 if (chrec1 == chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW]
877 || chrec2 == chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW])
878 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
879
880 if (chrec1 == chrec_knownglobal_trees[TI_CHREC_KNOWN]
881 || chrec2 == chrec_knownglobal_trees[TI_CHREC_KNOWN])
882 return chrec_knownglobal_trees[TI_CHREC_KNOWN];
883
884 if (chrec1 == chrec_not_analyzed_yet(tree) nullptr)
885 return chrec2;
886 if (chrec2 == chrec_not_analyzed_yet(tree) nullptr)
887 return chrec1;
888
889 if (eq_evolutions_p (chrec1, chrec2))
890 return chrec1;
891
892 return chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
893}
894
895
896
897/* Observers. */
898
899/* Helper function for is_multivariate_chrec. */
900
901static bool
902is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
903{
904 if (chrec == NULL_TREE(tree) nullptr)
905 return false;
906
907 if (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLYNOMIAL_CHREC)
908 {
909 if (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 909, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
!= rec_var)
910 return true;
911 else
912 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 912, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 912, __FUNCTION__)))))
, rec_var)
913 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 913, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 913, __FUNCTION__)))))
, rec_var));
914 }
915 else
916 return false;
917}
918
919/* Determine whether the given chrec is multivariate or not. */
920
921bool
922is_multivariate_chrec (const_tree chrec)
923{
924 if (chrec == NULL_TREE(tree) nullptr)
925 return false;
926
927 if (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLYNOMIAL_CHREC)
928 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 928, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 928, __FUNCTION__)))))
,
929 CHREC_VARIABLE (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 929, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
)
930 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 930, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 930, __FUNCTION__)))))
,
931 CHREC_VARIABLE (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 931, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
));
932 else
933 return false;
934}
935
936/* Determines whether the chrec contains symbolic names or not. If LOOP isn't
937 NULL, we also consider chrec wrto outer loops of LOOP as symbol. */
938
939static bool
940chrec_contains_symbols (const_tree chrec, hash_set<const_tree> &visited,
941 class loop *loop)
942{
943 int i, n;
944
945 if (chrec == NULL_TREE(tree) nullptr)
946 return false;
947
948 if (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == SSA_NAME
949 || VAR_P (chrec)(((enum tree_code) (chrec)->base.code) == VAR_DECL)
950 || TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLY_INT_CST
951 || TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == PARM_DECL
952 || TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == FUNCTION_DECL
953 || TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == LABEL_DECL
954 || TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == RESULT_DECL
955 || TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == FIELD_DECL)
956 return true;
957
958 if (loop != NULLnullptr
959 && TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLYNOMIAL_CHREC
960 && flow_loop_nested_p (get_chrec_loop (chrec), loop))
961 return true;
962
963 if (visited.add (chrec))
964 return false;
965
966 n = TREE_OPERAND_LENGTH (chrec)tree_operand_length (chrec);
967 for (i = 0; i < n; i++)
968 if (chrec_contains_symbols (TREE_OPERAND (chrec, i)(*((const_cast<tree*> (tree_operand_check ((chrec), (i)
, "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 968, __FUNCTION__)))))
, visited, loop))
969 return true;
970 return false;
971}
972
973/* Return true if CHREC contains any symbols. If LOOP is not NULL, check if
974 CHREC contains any chrec which is invariant wrto the loop (nest), in other
975 words, chrec defined by outer loops of loop, so from LOOP's point of view,
976 the chrec is considered as a SYMBOL. */
977
978bool
979chrec_contains_symbols (const_tree chrec, class loop* loop)
980{
981 hash_set<const_tree> visited;
982 return chrec_contains_symbols (chrec, visited, loop);
983}
984
985/* Return true when CHREC contains symbolic names defined in
986 LOOP_NB. */
987
988static bool
989chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb,
990 hash_set<const_tree> &visited)
991{
992 int i, n;
993
994 if (chrec == NULL_TREE(tree) nullptr)
995 return false;
996
997 if (is_gimple_min_invariant (chrec))
998 return false;
999
1000 if (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == SSA_NAME)
1001 {
1002 gimple *def;
1003 loop_p def_loop, loop;
1004
1005 if (SSA_NAME_IS_DEFAULT_DEF (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1005, __FUNCTION__, (SSA_NAME)))->base.default_def_flag
)
1006 return false;
1007
1008 def = SSA_NAME_DEF_STMT (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1008, __FUNCTION__, (SSA_NAME)))->ssa_name.def_stmt
;
1009 def_loop = loop_containing_stmt (def);
1010 loop = get_loop (cfun(cfun + 0), loop_nb);
1011
1012 if (def_loop == NULLnullptr)
1013 return false;
1014
1015 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
1016 return true;
1017
1018 return false;
1019 }
1020
1021 if (visited.add (chrec))
1022 return false;
1023
1024 n = TREE_OPERAND_LENGTH (chrec)tree_operand_length (chrec);
1025 for (i = 0; i < n; i++)
1026 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i)(*((const_cast<tree*> (tree_operand_check ((chrec), (i)
, "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1026, __FUNCTION__)))))
,
1027 loop_nb, visited))
1028 return true;
1029 return false;
1030}
1031
1032/* Return true when CHREC contains symbolic names defined in
1033 LOOP_NB. */
1034
1035bool
1036chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
1037{
1038 hash_set<const_tree> visited;
1039 return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited);
1040}
1041
1042/* Determines whether the chrec contains undetermined coefficients. */
1043
1044static bool
1045chrec_contains_undetermined (const_tree chrec, hash_set<const_tree> &visited)
1046{
1047 int i, n;
1048
1049 if (chrec == chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW])
1050 return true;
1051
1052 if (chrec == NULL_TREE(tree) nullptr)
1053 return false;
1054
1055 if (visited.add (chrec))
1056 return false;
1057
1058 n = TREE_OPERAND_LENGTH (chrec)tree_operand_length (chrec);
1059 for (i = 0; i < n; i++)
1060 if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)(*((const_cast<tree*> (tree_operand_check ((chrec), (i)
, "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1060, __FUNCTION__)))))
, visited))
1061 return true;
1062 return false;
1063}
1064
1065bool
1066chrec_contains_undetermined (const_tree chrec)
1067{
1068 hash_set<const_tree> visited;
1069 return chrec_contains_undetermined (chrec, visited);
1070}
1071
1072/* Determines whether the tree EXPR contains chrecs, and increment
1073 SIZE if it is not a NULL pointer by an estimation of the depth of
1074 the tree. */
1075
1076static bool
1077tree_contains_chrecs (const_tree expr, int *size, hash_set<const_tree> &visited)
1078{
1079 int i, n;
1080
1081 if (expr == NULL_TREE(tree) nullptr)
1082 return false;
1083
1084 if (size)
1085 (*size)++;
1086
1087 if (tree_is_chrec (expr))
1088 return true;
1089
1090 if (visited.add (expr))
1091 return false;
1092
1093 n = TREE_OPERAND_LENGTH (expr)tree_operand_length (expr);
1094 for (i = 0; i < n; i++)
1095 if (tree_contains_chrecs (TREE_OPERAND (expr, i)(*((const_cast<tree*> (tree_operand_check ((expr), (i),
"/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1095, __FUNCTION__)))))
, size, visited))
1096 return true;
1097 return false;
1098}
1099
1100bool
1101tree_contains_chrecs (const_tree expr, int *size)
1102{
1103 hash_set<const_tree> visited;
1104 return tree_contains_chrecs (expr, size, visited);
1105}
1106
1107
1108/* Recursive helper function. */
1109
1110static bool
1111evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
1112{
1113 if (evolution_function_is_constant_p (chrec))
1114 return true;
1115
1116 if (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == SSA_NAME
1117 && (loopnum == 0
1118 || expr_invariant_in_loop_p (get_loop (cfun(cfun + 0), loopnum), chrec)))
1119 return true;
1120
1121 if (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLYNOMIAL_CHREC)
1122 {
1123 if (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1123, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
== (unsigned) loopnum
1124 || flow_loop_nested_p (get_loop (cfun(cfun + 0), loopnum),
1125 get_chrec_loop (chrec))
1126 || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1126, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1126, __FUNCTION__)))))
,
1127 loopnum)
1128 || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1128, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1128, __FUNCTION__)))))
,
1129 loopnum))
1130 return false;
1131 return true;
1132 }
1133
1134 switch (TREE_OPERAND_LENGTH (chrec)tree_operand_length (chrec))
1135 {
1136 case 2:
1137 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1)(*((const_cast<tree*> (tree_operand_check ((chrec), (1)
, "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1137, __FUNCTION__)))))
,
1138 loopnum))
1139 return false;
1140 /* FALLTHRU */
1141
1142 case 1:
1143 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0)(*((const_cast<tree*> (tree_operand_check ((chrec), (0)
, "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1143, __FUNCTION__)))))
,
1144 loopnum))
1145 return false;
1146 return true;
1147
1148 default:
1149 return false;
1150 }
1151
1152 return false;
1153}
1154
1155/* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
1156
1157bool
1158evolution_function_is_invariant_p (tree chrec, int loopnum)
1159{
1160 return evolution_function_is_invariant_rec_p (chrec, loopnum);
1161}
1162
1163/* Determine whether the given tree is an affine multivariate
1164 evolution. */
1165
1166bool
1167evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1168{
1169 if (chrec == NULL_TREE(tree) nullptr)
1170 return false;
1171
1172 switch (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code))
1173 {
1174 case POLYNOMIAL_CHREC:
1175 if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1175, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1175, __FUNCTION__)))))
, loopnum))
1176 {
1177 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1177, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1177, __FUNCTION__)))))
, loopnum))
1178 return true;
1179 else
1180 {
1181 if (TREE_CODE (CHREC_RIGHT (chrec))((enum tree_code) ((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1181, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1181, __FUNCTION__))))))->base.code)
== POLYNOMIAL_CHREC
1182 && CHREC_VARIABLE (CHREC_RIGHT (chrec))(tree_check (((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1182, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1182, __FUNCTION__)))))), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1182, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
1183 != CHREC_VARIABLE (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1183, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
1184 && evolution_function_is_affine_multivariate_p
1185 (CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1185, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1185, __FUNCTION__)))))
, loopnum))
1186 return true;
1187 else
1188 return false;
1189 }
1190 }
1191 else
1192 {
1193 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1193, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1193, __FUNCTION__)))))
, loopnum)
1194 && TREE_CODE (CHREC_LEFT (chrec))((enum tree_code) ((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1194, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1194, __FUNCTION__))))))->base.code)
== POLYNOMIAL_CHREC
1195 && CHREC_VARIABLE (CHREC_LEFT (chrec))(tree_check (((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1195, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1195, __FUNCTION__)))))), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1195, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
!= CHREC_VARIABLE (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1195, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
1196 && evolution_function_is_affine_multivariate_p
1197 (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1197, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1197, __FUNCTION__)))))
, loopnum))
1198 return true;
1199 else
1200 return false;
1201 }
1202
1203 default:
1204 return false;
1205 }
1206}
1207
1208/* Determine whether the given tree is a function in zero or one
1209 variables with respect to loop specified by LOOPNUM. Note only positive
1210 LOOPNUM stands for a real loop. */
1211
1212bool
1213evolution_function_is_univariate_p (const_tree chrec, int loopnum)
1214{
1215 if (chrec == NULL_TREE(tree) nullptr)
1216 return true;
1217
1218 tree sub_chrec;
1219 switch (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code))
1220 {
1221 case POLYNOMIAL_CHREC:
1222 switch (TREE_CODE (CHREC_LEFT (chrec))((enum tree_code) ((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1222, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1222, __FUNCTION__))))))->base.code)
)
1223 {
1224 case POLYNOMIAL_CHREC:
1225 sub_chrec = CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1225, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1225, __FUNCTION__)))))
;
1226 if (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1226, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
!= CHREC_VARIABLE (sub_chrec)(tree_check ((sub_chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1226, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
1227 && (loopnum <= 0
1228 || CHREC_VARIABLE (sub_chrec)(tree_check ((sub_chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1228, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
== (unsigned) loopnum
1229 || flow_loop_nested_p (get_loop (cfun(cfun + 0), loopnum),
1230 get_chrec_loop (sub_chrec))))
1231 return false;
1232 if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1233 return false;
1234 break;
1235
1236 default:
1237 if (tree_contains_chrecs (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1237, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1237, __FUNCTION__)))))
, NULLnullptr))
1238 return false;
1239 break;
1240 }
1241
1242 switch (TREE_CODE (CHREC_RIGHT (chrec))((enum tree_code) ((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1242, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1242, __FUNCTION__))))))->base.code)
)
1243 {
1244 case POLYNOMIAL_CHREC:
1245 sub_chrec = CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1245, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1245, __FUNCTION__)))))
;
1246 if (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1246, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
!= CHREC_VARIABLE (sub_chrec)(tree_check ((sub_chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1246, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
1247 && (loopnum <= 0
1248 || CHREC_VARIABLE (sub_chrec)(tree_check ((sub_chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1248, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
== (unsigned) loopnum
1249 || flow_loop_nested_p (get_loop (cfun(cfun + 0), loopnum),
1250 get_chrec_loop (sub_chrec))))
1251 return false;
1252 if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1253 return false;
1254 break;
1255
1256 default:
1257 if (tree_contains_chrecs (CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1257, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1257, __FUNCTION__)))))
, NULLnullptr))
1258 return false;
1259 break;
1260 }
1261 return true;
1262
1263 default:
1264 return true;
1265 }
1266}
1267
1268/* Returns the number of variables of CHREC. Example: the call
1269 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1270
1271unsigned
1272nb_vars_in_chrec (tree chrec)
1273{
1274 if (chrec == NULL_TREE(tree) nullptr)
1275 return 0;
1276
1277 switch (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code))
1278 {
1279 case POLYNOMIAL_CHREC:
1280 return 1 + nb_vars_in_chrec
1281 (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1281, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
));
1282
1283 default:
1284 return 0;
1285 }
1286}
1287
1288/* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1289 the scev corresponds to. AT_STMT is the statement at that the scev is
1290 evaluated. USE_OVERFLOW_SEMANTICS is true if this function should assume
1291 that the rules for overflow of the given language apply (e.g., that signed
1292 arithmetics in C does not overflow) -- i.e., to use them to avoid
1293 unnecessary tests, but also to enforce that the result follows them.
1294 FROM is the source variable converted if it's not NULL. Returns true if
1295 the conversion succeeded, false otherwise. */
1296
1297bool
1298convert_affine_scev (class loop *loop, tree type,
1299 tree *base, tree *step, gimple *at_stmt,
1300 bool use_overflow_semantics, tree from)
1301{
1302 tree ct = TREE_TYPE (*step)((contains_struct_check ((*step), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1302, __FUNCTION__))->typed.type)
;
1303 bool enforce_overflow_semantics;
1304 bool must_check_src_overflow, must_check_rslt_overflow;
1305 tree new_base, new_step;
1306 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;
1307
1308 /* In general,
1309 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1310 but we must check some assumptions.
1311
1312 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1313 of CT is smaller than the precision of TYPE. For example, when we
1314 cast unsigned char [254, +, 1] to unsigned, the values on left side
1315 are 254, 255, 0, 1, ..., but those on the right side are
1316 254, 255, 256, 257, ...
1317 2) In case that we must also preserve the fact that signed ivs do not
1318 overflow, we must additionally check that the new iv does not wrap.
1319 For example, unsigned char [125, +, 1] casted to signed char could
1320 become a wrapping variable with values 125, 126, 127, -128, -127, ...,
1321 which would confuse optimizers that assume that this does not
1322 happen. */
1323 must_check_src_overflow = TYPE_PRECISION (ct)((tree_class_check ((ct), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1323, __FUNCTION__))->type_common.precision)
< TYPE_PRECISION (type)((tree_class_check ((type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1323, __FUNCTION__))->type_common.precision)
;
1324
1325 enforce_overflow_semantics = (use_overflow_semantics
1326 && nowrap_type_p (type));
1327 if (enforce_overflow_semantics)
1328 {
1329 /* We can avoid checking whether the result overflows in the following
1330 cases:
1331
1332 -- must_check_src_overflow is true, and the range of TYPE is superset
1333 of the range of CT -- i.e., in all cases except if CT signed and
1334 TYPE unsigned.
1335 -- both CT and TYPE have the same precision and signedness, and we
1336 verify instead that the source does not overflow (this may be
1337 easier than verifying it for the result, as we may use the
1338 information about the semantics of overflow in CT). */
1339 if (must_check_src_overflow)
1340 {
1341 if (TYPE_UNSIGNED (type)((tree_class_check ((type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1341, __FUNCTION__))->base.u.bits.unsigned_flag)
&& !TYPE_UNSIGNED (ct)((tree_class_check ((ct), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1341, __FUNCTION__))->base.u.bits.unsigned_flag)
)
1342 must_check_rslt_overflow = true;
1343 else
1344 must_check_rslt_overflow = false;
1345 }
1346 else if (TYPE_UNSIGNED (ct)((tree_class_check ((ct), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1346, __FUNCTION__))->base.u.bits.unsigned_flag)
== TYPE_UNSIGNED (type)((tree_class_check ((type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1346, __FUNCTION__))->base.u.bits.unsigned_flag)
1347 && TYPE_PRECISION (ct)((tree_class_check ((ct), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1347, __FUNCTION__))->type_common.precision)
== TYPE_PRECISION (type)((tree_class_check ((type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1347, __FUNCTION__))->type_common.precision)
)
1348 {
1349 must_check_rslt_overflow = false;
1350 must_check_src_overflow = true;
1351 }
1352 else
1353 must_check_rslt_overflow = true;
1354 }
1355 else
1356 must_check_rslt_overflow = false;
1357
1358 if (must_check_src_overflow
1359 && scev_probably_wraps_p (from, *base, *step, at_stmt, loop,
1360 use_overflow_semantics))
1361 return false;
1362
1363 new_base = chrec_convert (type, *base, at_stmt, use_overflow_semantics);
1364 /* The step must be sign extended, regardless of the signedness
1365 of CT and TYPE. This only needs to be handled specially when
1366 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1367 (with values 100, 99, 98, ...) from becoming signed or unsigned
1368 [100, +, 255] with values 100, 355, ...; the sign-extension is
1369 performed by default when CT is signed. */
1370 new_step = *step;
1371 if (TYPE_PRECISION (step_type)((tree_class_check ((step_type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1371, __FUNCTION__))->type_common.precision)
> TYPE_PRECISION (ct)((tree_class_check ((ct), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1371, __FUNCTION__))->type_common.precision)
&& TYPE_UNSIGNED (ct)((tree_class_check ((ct), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1371, __FUNCTION__))->base.u.bits.unsigned_flag)
)
1372 {
1373 tree signed_ct = build_nonstandard_integer_type (TYPE_PRECISION (ct)((tree_class_check ((ct), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1373, __FUNCTION__))->type_common.precision)
, 0);
1374 new_step = chrec_convert (signed_ct, new_step, at_stmt,
1375 use_overflow_semantics);
1376 }
1377 new_step = chrec_convert (step_type, new_step, at_stmt,
1378 use_overflow_semantics);
1379
1380 if (automatically_generated_chrec_p (new_base)
1381 || automatically_generated_chrec_p (new_step))
1382 return false;
1383
1384 if (must_check_rslt_overflow
1385 /* Note that in this case we cannot use the fact that signed variables
1386 do not overflow, as this is what we are verifying for the new iv. */
1387 && scev_probably_wraps_p (NULL_TREE(tree) nullptr, new_base, new_step,
1388 at_stmt, loop, false))
1389 return false;
1390
1391 *base = new_base;
1392 *step = new_step;
1393 return true;
1394}
1395
1396
1397/* Convert CHREC for the right hand side of a CHREC.
1398 The increment for a pointer type is always sizetype. */
1399
1400tree
1401chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt)
1402{
1403 if (POINTER_TYPE_P (type)(((enum tree_code) (type)->base.code) == POINTER_TYPE || (
(enum tree_code) (type)->base.code) == REFERENCE_TYPE)
)
1404 type = sizetypesizetype_tab[(int) stk_sizetype];
1405
1406 return chrec_convert (type, chrec, at_stmt);
1407}
1408
1409/* Convert CHREC to TYPE. When the analyzer knows the context in
1410 which the CHREC is built, it sets AT_STMT to the statement that
1411 contains the definition of the analyzed variable, otherwise the
1412 conversion is less accurate: the information is used for
1413 determining a more accurate estimation of the number of iterations.
1414 By default AT_STMT could be safely set to NULL_TREE.
1415
1416 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1417 the rules for overflow of the given language apply (e.g., that signed
1418 arithmetics in C does not overflow) -- i.e., to use them to avoid
1419 unnecessary tests, but also to enforce that the result follows them.
1420
1421 FROM is the source variable converted if it's not NULL. */
1422
1423static tree
1424chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
1425 bool use_overflow_semantics, tree from)
1426{
1427 tree ct, res;
1428 tree base, step;
1429 class loop *loop;
1430
1431 if (automatically_generated_chrec_p (chrec))
1432 return chrec;
1433
1434 ct = chrec_type (chrec);
1435 if (useless_type_conversion_p (type, ct))
1436 return chrec;
1437
1438 if (!evolution_function_is_affine_p (chrec))
1439 goto keep_cast;
1440
1441 loop = get_chrec_loop (chrec);
1442 base = CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1442, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1442, __FUNCTION__)))))
;
1443 step = CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1443, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1443, __FUNCTION__)))))
;
1444
1445 if (convert_affine_scev (loop, type, &base, &step, at_stmt,
1446 use_overflow_semantics, from))
1447 return build_polynomial_chrec (loop->num, base, step);
1448
1449 /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1450keep_cast:
1451 /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1452 may be more expensive. We do want to perform this optimization here
1453 though for canonicalization reasons. */
1454 if (use_overflow_semantics
1455 && (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == PLUS_EXPR
1456 || TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == MINUS_EXPR)
1457 && TREE_CODE (type)((enum tree_code) (type)->base.code) == INTEGER_TYPE
1458 && TREE_CODE (ct)((enum tree_code) (ct)->base.code) == INTEGER_TYPE
1459 && TYPE_PRECISION (type)((tree_class_check ((type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1459, __FUNCTION__))->type_common.precision)
> TYPE_PRECISION (ct)((tree_class_check ((ct), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1459, __FUNCTION__))->type_common.precision)
1460 && 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1460, __FUNCTION__))->base.u.bits.unsigned_flag &&
!global_options.x_flag_wrapv && !global_options.x_flag_trapv
))
)
1461 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),
"/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1462, __FUNCTION__)))))), fold_convert_loc (((location_t) 0
), type, (*((const_cast<tree*> (tree_operand_check ((chrec
), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1463, __FUNCTION__)))))) )
1462 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),
"/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1462, __FUNCTION__)))))), fold_convert_loc (((location_t) 0
), type, (*((const_cast<tree*> (tree_operand_check ((chrec
), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1463, __FUNCTION__)))))) )
1463 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),
"/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1462, __FUNCTION__)))))), fold_convert_loc (((location_t) 0
), type, (*((const_cast<tree*> (tree_operand_check ((chrec
), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1463, __FUNCTION__)))))) )
;
1464 /* Similar perform the trick that (signed char)((int)x + 2) can be
1465 narrowed to (signed char)((unsigned char)x + 2). */
1466 else if (use_overflow_semantics
1467 && TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) == POLYNOMIAL_CHREC
1468 && TREE_CODE (ct)((enum tree_code) (ct)->base.code) == INTEGER_TYPE
1469 && TREE_CODE (type)((enum tree_code) (type)->base.code) == INTEGER_TYPE
1470 && 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), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1470, __FUNCTION__))->base.u.bits.unsigned_flag &&
!global_options.x_flag_wrapv && !global_options.x_flag_trapv
))
1471 && TYPE_PRECISION (type)((tree_class_check ((type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1471, __FUNCTION__))->type_common.precision)
< TYPE_PRECISION (ct)((tree_class_check ((ct), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1471, __FUNCTION__))->type_common.precision)
)
1472 {
1473 tree utype = unsigned_type_for (type);
1474 res = build_polynomial_chrec (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1474, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
,
1475 fold_convert (utype,fold_convert_loc (((location_t) 0), utype, (*((const_cast<
tree*> (tree_operand_check (((tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1476, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1476, __FUNCTION__))))))
1476 CHREC_LEFT (chrec))fold_convert_loc (((location_t) 0), utype, (*((const_cast<
tree*> (tree_operand_check (((tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1476, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1476, __FUNCTION__))))))
,
1477 fold_convert (utype,fold_convert_loc (((location_t) 0), utype, (*((const_cast<
tree*> (tree_operand_check (((tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1478, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1478, __FUNCTION__))))))
1478 CHREC_RIGHT (chrec))fold_convert_loc (((location_t) 0), utype, (*((const_cast<
tree*> (tree_operand_check (((tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1478, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1478, __FUNCTION__))))))
);
1479 res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
1480 }
1481 else
1482 res = fold_convert (type, chrec)fold_convert_loc (((location_t) 0), type, chrec);
1483
1484 /* Don't propagate overflows. */
1485 if (CONSTANT_CLASS_P (res)(tree_code_type[(int) (((enum tree_code) (res)->base.code)
)] == tcc_constant)
)
1486 TREE_OVERFLOW (res)((tree_class_check ((res), (tcc_constant), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1486, __FUNCTION__))->base.public_flag)
= 0;
1487
1488 /* But reject constants that don't fit in their type after conversion.
1489 This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the
1490 natural values associated with TYPE_PRECISION and TYPE_UNSIGNED,
1491 and can cause problems later when computing niters of loops. Note
1492 that we don't do the check before converting because we don't want
1493 to reject conversions of negative chrecs to unsigned types. */
1494 if (TREE_CODE (res)((enum tree_code) (res)->base.code) == INTEGER_CST
1495 && TREE_CODE (type)((enum tree_code) (type)->base.code) == INTEGER_TYPE
1496 && !int_fits_type_p (res, type))
1497 res = chrec_dont_knowglobal_trees[TI_CHREC_DONT_KNOW];
1498
1499 return res;
1500}
1501
1502/* Convert CHREC to TYPE. When the analyzer knows the context in
1503 which the CHREC is built, it sets AT_STMT to the statement that
1504 contains the definition of the analyzed variable, otherwise the
1505 conversion is less accurate: the information is used for
1506 determining a more accurate estimation of the number of iterations.
1507 By default AT_STMT could be safely set to NULL_TREE.
1508
1509 The following rule is always true: TREE_TYPE (chrec) ==
1510 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1511 An example of what could happen when adding two chrecs and the type
1512 of the CHREC_RIGHT is different than CHREC_LEFT is:
1513
1514 {(uint) 0, +, (uchar) 10} +
1515 {(uint) 0, +, (uchar) 250}
1516
1517 that would produce a wrong result if CHREC_RIGHT is not (uint):
1518
1519 {(uint) 0, +, (uchar) 4}
1520
1521 instead of
1522
1523 {(uint) 0, +, (uint) 260}
1524
1525 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1526 the rules for overflow of the given language apply (e.g., that signed
1527 arithmetics in C does not overflow) -- i.e., to use them to avoid
1528 unnecessary tests, but also to enforce that the result follows them.
1529
1530 FROM is the source variable converted if it's not NULL. */
1531
1532tree
1533chrec_convert (tree type, tree chrec, gimple *at_stmt,
1534 bool use_overflow_semantics, tree from)
1535{
1536 return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from);
1537}
1538
1539/* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
1540 chrec if something else than what chrec_convert would do happens, NULL_TREE
1541 otherwise. This function set TRUE to variable pointed by FOLD_CONVERSIONS
1542 if the result chrec may overflow. */
1543
1544tree
1545chrec_convert_aggressive (tree type, tree chrec, bool *fold_conversions)
1546{
1547 tree inner_type, left, right, lc, rc, rtype;
1548
1549 gcc_assert (fold_conversions != NULL)((void)(!(fold_conversions != nullptr) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1549, __FUNCTION__), 0 : 0))
;
1550
1551 if (automatically_generated_chrec_p (chrec)
1552 || TREE_CODE (chrec)((enum tree_code) (chrec)->base.code) != POLYNOMIAL_CHREC)
1553 return NULL_TREE(tree) nullptr;
1554
1555 inner_type = TREE_TYPE (chrec)((contains_struct_check ((chrec), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1555, __FUNCTION__))->typed.type)
;
1556 if (TYPE_PRECISION (type)((tree_class_check ((type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1556, __FUNCTION__))->type_common.precision)
> TYPE_PRECISION (inner_type)((tree_class_check ((inner_type), (tcc_type), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1556, __FUNCTION__))->type_common.precision)
)
1557 return NULL_TREE(tree) nullptr;
1558
1559 if (useless_type_conversion_p (type, inner_type))
1560 return NULL_TREE(tree) nullptr;
1561
1562 if (!*fold_conversions && evolution_function_is_affine_p (chrec))
1563 {
1564 tree base, step;
1565 class loop *loop;
1566
1567 loop = get_chrec_loop (chrec);
1568 base = CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1568, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1568, __FUNCTION__)))))
;
1569 step = CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1569, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1569, __FUNCTION__)))))
;
1570 if (convert_affine_scev (loop, type, &base, &step, NULLnullptr, true))
1571 return build_polynomial_chrec (loop->num, base, step);
1572 }
1573 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;
1574
1575 left = CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1575, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1575, __FUNCTION__)))))
;
1576 right = CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1576, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1576, __FUNCTION__)))))
;
1577 lc = chrec_convert_aggressive (type, left, fold_conversions);
1578 if (!lc)
1579 lc = chrec_convert (type, left, NULLnullptr);
1580 rc = chrec_convert_aggressive (rtype, right, fold_conversions);
1581 if (!rc)
1582 rc = chrec_convert (rtype, right, NULLnullptr);
1583
1584 *fold_conversions = true;
1585
1586 return build_polynomial_chrec (CHREC_VARIABLE (chrec)(tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1586, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
, lc, rc);
1587}
1588
1589/* Returns true when CHREC0 == CHREC1. */
1590
1591bool
1592eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1593{
1594 if (chrec0 == NULL_TREE(tree) nullptr
1595 || chrec1 == NULL_TREE(tree) nullptr
1596 || TREE_CODE (chrec0)((enum tree_code) (chrec0)->base.code) != TREE_CODE (chrec1)((enum tree_code) (chrec1)->base.code))
1597 return false;
1598
1599 if (chrec0 == chrec1)
1600 return true;
1601
1602 if (! types_compatible_p (TREE_TYPE (chrec0)((contains_struct_check ((chrec0), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1602, __FUNCTION__))->typed.type)
, TREE_TYPE (chrec1)((contains_struct_check ((chrec1), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1602, __FUNCTION__))->typed.type)
))
1603 return false;
1604
1605 switch (TREE_CODE (chrec0)((enum tree_code) (chrec0)->base.code))
1606 {
1607 case POLYNOMIAL_CHREC:
1608 return (CHREC_VARIABLE (chrec0)(tree_check ((chrec0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1608, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
== CHREC_VARIABLE (chrec1)(tree_check ((chrec1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1608, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
1609 && eq_evolutions_p (CHREC_LEFT (chrec0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1609, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1609, __FUNCTION__)))))
, CHREC_LEFT (chrec1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1609, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1609, __FUNCTION__)))))
)
1610 && eq_evolutions_p (CHREC_RIGHT (chrec0)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1610, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1610, __FUNCTION__)))))
, CHREC_RIGHT (chrec1)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1610, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1610, __FUNCTION__)))))
));
1611
1612 case PLUS_EXPR:
1613 case MULT_EXPR:
1614 case MINUS_EXPR:
1615 case POINTER_PLUS_EXPR:
1616 return eq_evolutions_p (TREE_OPERAND (chrec0, 0)(*((const_cast<tree*> (tree_operand_check ((chrec0), (0
), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1616, __FUNCTION__)))))
,
1617 TREE_OPERAND (chrec1, 0)(*((const_cast<tree*> (tree_operand_check ((chrec1), (0
), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1617, __FUNCTION__)))))
)
1618 && eq_evolutions_p (TREE_OPERAND (chrec0, 1)(*((const_cast<tree*> (tree_operand_check ((chrec0), (1
), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1618, __FUNCTION__)))))
,
1619 TREE_OPERAND (chrec1, 1)(*((const_cast<tree*> (tree_operand_check ((chrec1), (1
), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1619, __FUNCTION__)))))
);
1620
1621 CASE_CONVERTcase NOP_EXPR: case CONVERT_EXPR:
1622 return eq_evolutions_p (TREE_OPERAND (chrec0, 0)(*((const_cast<tree*> (tree_operand_check ((chrec0), (0
), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1622, __FUNCTION__)))))
,
1623 TREE_OPERAND (chrec1, 0)(*((const_cast<tree*> (tree_operand_check ((chrec1), (0
), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1623, __FUNCTION__)))))
);
1624
1625 default:
1626 return operand_equal_p (chrec0, chrec1, 0);
1627 }
1628}
1629
1630/* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1631 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1632 which of these cases happens. */
1633
1634enum ev_direction
1635scev_direction (const_tree chrec)
1636{
1637 const_tree step;
1638
1639 if (!evolution_function_is_affine_p (chrec))
1640 return EV_DIR_UNKNOWN;
1641
1642 step = CHREC_RIGHT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1642, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1642, __FUNCTION__)))))
;
1643 if (TREE_CODE (step)((enum tree_code) (step)->base.code) != INTEGER_CST)
1644 return EV_DIR_UNKNOWN;
1645
1646 if (tree_int_cst_sign_bit (step))
1647 return EV_DIR_DECREASES;
1648 else
1649 return EV_DIR_GROWS;
1650}
1651
1652/* Iterates over all the components of SCEV, and calls CBCK. */
1653
1654void
1655for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
1656{
1657 switch (TREE_CODE_LENGTH (TREE_CODE (*scev))tree_code_length[(int) (((enum tree_code) (*scev)->base.code
))]
)
1658 {
1659 case 3:
1660 for_each_scev_op (&TREE_OPERAND (*scev, 2)(*((const_cast<tree*> (tree_operand_check ((*scev), (2)
, "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1660, __FUNCTION__)))))
, cbck, data);
1661 /* FALLTHRU */
1662
1663 case 2:
1664 for_each_scev_op (&TREE_OPERAND (*scev, 1)(*((const_cast<tree*> (tree_operand_check ((*scev), (1)
, "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1664, __FUNCTION__)))))
, cbck, data);
1665 /* FALLTHRU */
1666
1667 case 1:
1668 for_each_scev_op (&TREE_OPERAND (*scev, 0)(*((const_cast<tree*> (tree_operand_check ((*scev), (0)
, "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1668, __FUNCTION__)))))
, cbck, data);
1669 /* FALLTHRU */
1670
1671 default:
1672 cbck (scev, data);
1673 break;
1674 }
1675}
1676
1677/* Returns true when the operation can be part of a linear
1678 expression. */
1679
1680static inline bool
1681operator_is_linear (tree scev)
1682{
1683 switch (TREE_CODE (scev)((enum tree_code) (scev)->base.code))
1684 {
1685 case INTEGER_CST:
1686 case POLYNOMIAL_CHREC:
1687 case PLUS_EXPR:
1688 case POINTER_PLUS_EXPR:
1689 case MULT_EXPR:
1690 case MINUS_EXPR:
1691 case NEGATE_EXPR:
1692 case SSA_NAME:
1693 case NON_LVALUE_EXPR:
1694 case BIT_NOT_EXPR:
1695 CASE_CONVERTcase NOP_EXPR: case CONVERT_EXPR:
1696 return true;
1697
1698 default:
1699 return false;
1700 }
1701}
1702
1703/* Return true when SCEV is a linear expression. Linear expressions
1704 can contain additions, substractions and multiplications.
1705 Multiplications are restricted to constant scaling: "cst * x". */
1706
1707bool
1708scev_is_linear_expression (tree scev)
1709{
1710 if (evolution_function_is_constant_p (scev))
1711 return true;
1712
1713 if (scev == NULLnullptr
1714 || !operator_is_linear (scev))
1715 return false;
1716
1717 if (TREE_CODE (scev)((enum tree_code) (scev)->base.code) == MULT_EXPR)
1718 return !(tree_contains_chrecs (TREE_OPERAND (scev, 0)(*((const_cast<tree*> (tree_operand_check ((scev), (0),
"/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1718, __FUNCTION__)))))
, NULLnullptr)
1719 && tree_contains_chrecs (TREE_OPERAND (scev, 1)(*((const_cast<tree*> (tree_operand_check ((scev), (1),
"/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1719, __FUNCTION__)))))
, NULLnullptr));
1720
1721 if (TREE_CODE (scev)((enum tree_code) (scev)->base.code) == POLYNOMIAL_CHREC
1722 && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)(tree_check ((scev), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1722, __FUNCTION__, (POLYNOMIAL_CHREC)))->base.u.chrec_var
))
1723 return false;
1724
1725 switch (TREE_CODE_LENGTH (TREE_CODE (scev))tree_code_length[(int) (((enum tree_code) (scev)->base.code
))]
)
1726 {
1727 case 3:
1728 return scev_is_linear_expression (TREE_OPERAND (scev, 0)(*((const_cast<tree*> (tree_operand_check ((scev), (0),
"/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1728, __FUNCTION__)))))
)
1729 && scev_is_linear_expression (TREE_OPERAND (scev, 1)(*((const_cast<tree*> (tree_operand_check ((scev), (1),
"/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1729, __FUNCTION__)))))
)
1730 && scev_is_linear_expression (TREE_OPERAND (scev, 2)(*((const_cast<tree*> (tree_operand_check ((scev), (2),
"/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1730, __FUNCTION__)))))
);
1731
1732 case 2:
1733 return scev_is_linear_expression (TREE_OPERAND (scev, 0)(*((const_cast<tree*> (tree_operand_check ((scev), (0),
"/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1733, __FUNCTION__)))))
)
1734 && scev_is_linear_expression (TREE_OPERAND (scev, 1)(*((const_cast<tree*> (tree_operand_check ((scev), (1),
"/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1734, __FUNCTION__)))))
);
1735
1736 case 1:
1737 return scev_is_linear_expression (TREE_OPERAND (scev, 0)(*((const_cast<tree*> (tree_operand_check ((scev), (0),
"/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1737, __FUNCTION__)))))
);
1738
1739 case 0:
1740 return true;
1741
1742 default:
1743 return false;
1744 }
1745}
1746
1747/* Determines whether the expression CHREC contains only interger consts
1748 in the right parts. */
1749
1750bool
1751evolution_function_right_is_integer_cst (const_tree chrec)
1752{
1753 if (chrec == NULL_TREE(tree) nullptr)
1754 return false;
1755
1756 switch (TREE_CODE (chrec)((enum tree_code) (chrec)->base.code))
1757 {
1758 case INTEGER_CST:
1759 return true;
1760
1761 case POLYNOMIAL_CHREC:
1762 return TREE_CODE (CHREC_RIGHT (chrec))((enum tree_code) ((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1762, __FUNCTION__, (POLYNOMIAL_CHREC)))), (1), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1762, __FUNCTION__))))))->base.code)
== INTEGER_CST
1763 && (TREE_CODE (CHREC_LEFT (chrec))((enum tree_code) ((*((const_cast<tree*> (tree_operand_check
(((tree_check ((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1763, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1763, __FUNCTION__))))))->base.code)
!= POLYNOMIAL_CHREC
1764 || evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)(*((const_cast<tree*> (tree_operand_check (((tree_check
((chrec), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1764, __FUNCTION__, (POLYNOMIAL_CHREC)))), (0), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1764, __FUNCTION__)))))
));
1765
1766 CASE_CONVERTcase NOP_EXPR: case CONVERT_EXPR:
1767 return evolution_function_right_is_integer_cst (TREE_OPERAND (chrec, 0)(*((const_cast<tree*> (tree_operand_check ((chrec), (0)
, "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-chrec.c"
, 1767, __FUNCTION__)))))
);
1768
1769 default:
1770 return false;
1771 }
1772}