Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-chrec.c @ 55:77e2b8dfacca gcc-4.4.5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update it from 4.4.3 to 4.5.0
author ryoma <e075725@ie.u-ryukyu.ac.jp>
date Fri, 12 Feb 2010 23:39:51 +0900
parents 58ad6c70ea60
children b7f97abdc517
comparison
equal deleted inserted replaced
52:c156f1bd5cd9 55:77e2b8dfacca
35 #include "cfgloop.h" 35 #include "cfgloop.h"
36 #include "tree-flow.h" 36 #include "tree-flow.h"
37 #include "tree-chrec.h" 37 #include "tree-chrec.h"
38 #include "tree-pass.h" 38 #include "tree-pass.h"
39 #include "params.h" 39 #include "params.h"
40 #include "flags.h"
40 #include "tree-scalar-evolution.h" 41 #include "tree-scalar-evolution.h"
41 42
42 43
43 44
44 /* Extended folder for chrecs. */ 45 /* Extended folder for chrecs. */
51 return (TREE_CODE (cst) == POLYNOMIAL_CHREC); 52 return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
52 } 53 }
53 54
54 /* Fold CODE for a polynomial function and a constant. */ 55 /* Fold CODE for a polynomial function and a constant. */
55 56
56 static inline tree 57 static inline tree
57 chrec_fold_poly_cst (enum tree_code code, 58 chrec_fold_poly_cst (enum tree_code code,
58 tree type, 59 tree type,
59 tree poly, 60 tree poly,
60 tree cst) 61 tree cst)
61 { 62 {
62 gcc_assert (poly); 63 gcc_assert (poly);
63 gcc_assert (cst); 64 gcc_assert (cst);
64 gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC); 65 gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC);
66 gcc_assert (type == chrec_type (poly)); 67 gcc_assert (type == chrec_type (poly));
67 68
68 switch (code) 69 switch (code)
69 { 70 {
70 case PLUS_EXPR: 71 case PLUS_EXPR:
71 return build_polynomial_chrec 72 return build_polynomial_chrec
72 (CHREC_VARIABLE (poly), 73 (CHREC_VARIABLE (poly),
73 chrec_fold_plus (type, CHREC_LEFT (poly), cst), 74 chrec_fold_plus (type, CHREC_LEFT (poly), cst),
74 CHREC_RIGHT (poly)); 75 CHREC_RIGHT (poly));
75 76
76 case MINUS_EXPR: 77 case MINUS_EXPR:
77 return build_polynomial_chrec 78 return build_polynomial_chrec
78 (CHREC_VARIABLE (poly), 79 (CHREC_VARIABLE (poly),
79 chrec_fold_minus (type, CHREC_LEFT (poly), cst), 80 chrec_fold_minus (type, CHREC_LEFT (poly), cst),
80 CHREC_RIGHT (poly)); 81 CHREC_RIGHT (poly));
81 82
82 case MULT_EXPR: 83 case MULT_EXPR:
83 return build_polynomial_chrec 84 return build_polynomial_chrec
84 (CHREC_VARIABLE (poly), 85 (CHREC_VARIABLE (poly),
85 chrec_fold_multiply (type, CHREC_LEFT (poly), cst), 86 chrec_fold_multiply (type, CHREC_LEFT (poly), cst),
86 chrec_fold_multiply (type, CHREC_RIGHT (poly), cst)); 87 chrec_fold_multiply (type, CHREC_RIGHT (poly), cst));
87 88
88 default: 89 default:
89 return chrec_dont_know; 90 return chrec_dont_know;
90 } 91 }
91 } 92 }
92 93
93 /* Fold the addition of two polynomial functions. */ 94 /* Fold the addition of two polynomial functions. */
94 95
95 static inline tree 96 static inline tree
96 chrec_fold_plus_poly_poly (enum tree_code code, 97 chrec_fold_plus_poly_poly (enum tree_code code,
97 tree type, 98 tree type,
98 tree poly0, 99 tree poly0,
99 tree poly1) 100 tree poly1)
100 { 101 {
101 tree left, right; 102 tree left, right;
102 struct loop *loop0 = get_chrec_loop (poly0); 103 struct loop *loop0 = get_chrec_loop (poly0);
103 struct loop *loop1 = get_chrec_loop (poly1); 104 struct loop *loop1 = get_chrec_loop (poly1);
110 if (POINTER_TYPE_P (chrec_type (poly0))) 111 if (POINTER_TYPE_P (chrec_type (poly0)))
111 gcc_assert (chrec_type (poly1) == sizetype); 112 gcc_assert (chrec_type (poly1) == sizetype);
112 else 113 else
113 gcc_assert (chrec_type (poly0) == chrec_type (poly1)); 114 gcc_assert (chrec_type (poly0) == chrec_type (poly1));
114 gcc_assert (type == chrec_type (poly0)); 115 gcc_assert (type == chrec_type (poly0));
115 116
116 /* 117 /*
117 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2, 118 {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
118 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2, 119 {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
119 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */ 120 {a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
120 if (flow_loop_nested_p (loop0, loop1)) 121 if (flow_loop_nested_p (loop0, loop1))
121 { 122 {
122 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR) 123 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
123 return build_polynomial_chrec 124 return build_polynomial_chrec
124 (CHREC_VARIABLE (poly1), 125 (CHREC_VARIABLE (poly1),
125 chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)), 126 chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
126 CHREC_RIGHT (poly1)); 127 CHREC_RIGHT (poly1));
127 else 128 else
128 return build_polynomial_chrec 129 return build_polynomial_chrec
129 (CHREC_VARIABLE (poly1), 130 (CHREC_VARIABLE (poly1),
130 chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)), 131 chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
131 chrec_fold_multiply (type, CHREC_RIGHT (poly1), 132 chrec_fold_multiply (type, CHREC_RIGHT (poly1),
132 SCALAR_FLOAT_TYPE_P (type) 133 SCALAR_FLOAT_TYPE_P (type)
133 ? build_real (type, dconstm1) 134 ? build_real (type, dconstm1)
134 : build_int_cst_type (type, -1))); 135 : build_int_cst_type (type, -1)));
135 } 136 }
136 137
137 if (flow_loop_nested_p (loop1, loop0)) 138 if (flow_loop_nested_p (loop1, loop0))
138 { 139 {
139 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR) 140 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
140 return build_polynomial_chrec 141 return build_polynomial_chrec
141 (CHREC_VARIABLE (poly0), 142 (CHREC_VARIABLE (poly0),
142 chrec_fold_plus (type, CHREC_LEFT (poly0), poly1), 143 chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
143 CHREC_RIGHT (poly0)); 144 CHREC_RIGHT (poly0));
144 else 145 else
145 return build_polynomial_chrec 146 return build_polynomial_chrec
146 (CHREC_VARIABLE (poly0), 147 (CHREC_VARIABLE (poly0),
147 chrec_fold_minus (type, CHREC_LEFT (poly0), poly1), 148 chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
148 CHREC_RIGHT (poly0)); 149 CHREC_RIGHT (poly0));
149 } 150 }
150 151
151 /* This function should never be called for chrecs of loops that 152 /* This function should never be called for chrecs of loops that
152 do not belong to the same loop nest. */ 153 do not belong to the same loop nest. */
153 gcc_assert (loop0 == loop1); 154 gcc_assert (loop0 == loop1);
154 155
155 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR) 156 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
156 { 157 {
157 left = chrec_fold_plus 158 left = chrec_fold_plus
158 (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); 159 (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
159 right = chrec_fold_plus 160 right = chrec_fold_plus
160 (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)); 161 (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
161 } 162 }
162 else 163 else
163 { 164 {
164 left = chrec_fold_minus 165 left = chrec_fold_minus
165 (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); 166 (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
166 right = chrec_fold_minus 167 right = chrec_fold_minus
167 (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)); 168 (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
168 } 169 }
169 170
170 if (chrec_zerop (right)) 171 if (chrec_zerop (right))
171 return left; 172 return left;
172 else 173 else
173 return build_polynomial_chrec 174 return build_polynomial_chrec
174 (CHREC_VARIABLE (poly0), left, right); 175 (CHREC_VARIABLE (poly0), left, right);
175 } 176 }
176 177
177 178
178 179
179 /* Fold the multiplication of two polynomial functions. */ 180 /* Fold the multiplication of two polynomial functions. */
180 181
181 static inline tree 182 static inline tree
182 chrec_fold_multiply_poly_poly (tree type, 183 chrec_fold_multiply_poly_poly (tree type,
183 tree poly0, 184 tree poly0,
184 tree poly1) 185 tree poly1)
185 { 186 {
186 tree t0, t1, t2; 187 tree t0, t1, t2;
187 int var; 188 int var;
188 struct loop *loop0 = get_chrec_loop (poly0); 189 struct loop *loop0 = get_chrec_loop (poly0);
192 gcc_assert (poly1); 193 gcc_assert (poly1);
193 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC); 194 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
194 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC); 195 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
195 gcc_assert (chrec_type (poly0) == chrec_type (poly1)); 196 gcc_assert (chrec_type (poly0) == chrec_type (poly1));
196 gcc_assert (type == chrec_type (poly0)); 197 gcc_assert (type == chrec_type (poly0));
197 198
198 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2, 199 /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2,
199 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2, 200 {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2,
200 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ 201 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
201 if (flow_loop_nested_p (loop0, loop1)) 202 if (flow_loop_nested_p (loop0, loop1))
202 /* poly0 is a constant wrt. poly1. */ 203 /* poly0 is a constant wrt. poly1. */
203 return build_polynomial_chrec 204 return build_polynomial_chrec
204 (CHREC_VARIABLE (poly1), 205 (CHREC_VARIABLE (poly1),
205 chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0), 206 chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
206 CHREC_RIGHT (poly1)); 207 CHREC_RIGHT (poly1));
207 208
208 if (flow_loop_nested_p (loop1, loop0)) 209 if (flow_loop_nested_p (loop1, loop0))
209 /* poly1 is a constant wrt. poly0. */ 210 /* poly1 is a constant wrt. poly0. */
210 return build_polynomial_chrec 211 return build_polynomial_chrec
211 (CHREC_VARIABLE (poly0), 212 (CHREC_VARIABLE (poly0),
212 chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1), 213 chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1),
213 CHREC_RIGHT (poly0)); 214 CHREC_RIGHT (poly0));
214 215
215 gcc_assert (loop0 == loop1); 216 gcc_assert (loop0 == loop1);
216 217
217 /* poly0 and poly1 are two polynomials in the same variable, 218 /* poly0 and poly1 are two polynomials in the same variable,
218 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ 219 {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */
219 220
220 /* "a*c". */ 221 /* "a*c". */
221 t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); 222 t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
222 223
223 /* "a*d + b*c". */ 224 /* "a*d + b*c". */
224 t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1)); 225 t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1));
240 } 241 }
241 242
242 /* When the operands are automatically_generated_chrec_p, the fold has 243 /* When the operands are automatically_generated_chrec_p, the fold has
243 to respect the semantics of the operands. */ 244 to respect the semantics of the operands. */
244 245
245 static inline tree 246 static inline tree
246 chrec_fold_automatically_generated_operands (tree op0, 247 chrec_fold_automatically_generated_operands (tree op0,
247 tree op1) 248 tree op1)
248 { 249 {
249 if (op0 == chrec_dont_know 250 if (op0 == chrec_dont_know
250 || op1 == chrec_dont_know) 251 || op1 == chrec_dont_know)
251 return chrec_dont_know; 252 return chrec_dont_know;
252 253
253 if (op0 == chrec_known 254 if (op0 == chrec_known
254 || op1 == chrec_known) 255 || op1 == chrec_known)
255 return chrec_known; 256 return chrec_known;
256 257
257 if (op0 == chrec_not_analyzed_yet 258 if (op0 == chrec_not_analyzed_yet
258 || op1 == chrec_not_analyzed_yet) 259 || op1 == chrec_not_analyzed_yet)
259 return chrec_not_analyzed_yet; 260 return chrec_not_analyzed_yet;
260 261
261 /* The default case produces a safe result. */ 262 /* The default case produces a safe result. */
262 return chrec_dont_know; 263 return chrec_dont_know;
263 } 264 }
264 265
265 /* Fold the addition of two chrecs. */ 266 /* Fold the addition of two chrecs. */
266 267
267 static tree 268 static tree
268 chrec_fold_plus_1 (enum tree_code code, tree type, 269 chrec_fold_plus_1 (enum tree_code code, tree type,
269 tree op0, tree op1) 270 tree op0, tree op1)
270 { 271 {
271 tree op1_type = code == POINTER_PLUS_EXPR ? sizetype : type; 272 tree op1_type = code == POINTER_PLUS_EXPR ? sizetype : type;
272 273
273 if (automatically_generated_chrec_p (op0) 274 if (automatically_generated_chrec_p (op0)
274 || automatically_generated_chrec_p (op1)) 275 || automatically_generated_chrec_p (op1))
275 return chrec_fold_automatically_generated_operands (op0, op1); 276 return chrec_fold_automatically_generated_operands (op0, op1);
276 277
277 switch (TREE_CODE (op0)) 278 switch (TREE_CODE (op0))
278 { 279 {
279 case POLYNOMIAL_CHREC: 280 case POLYNOMIAL_CHREC:
280 switch (TREE_CODE (op1)) 281 switch (TREE_CODE (op1))
281 { 282 {
282 case POLYNOMIAL_CHREC: 283 case POLYNOMIAL_CHREC:
283 return chrec_fold_plus_poly_poly (code, type, op0, op1); 284 return chrec_fold_plus_poly_poly (code, type, op0, op1);
284 285
285 default: 286 default:
286 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR) 287 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
287 return build_polynomial_chrec 288 return build_polynomial_chrec
288 (CHREC_VARIABLE (op0), 289 (CHREC_VARIABLE (op0),
289 chrec_fold_plus (type, CHREC_LEFT (op0), op1), 290 chrec_fold_plus (type, CHREC_LEFT (op0), op1),
290 CHREC_RIGHT (op0)); 291 CHREC_RIGHT (op0));
291 else 292 else
292 return build_polynomial_chrec 293 return build_polynomial_chrec
293 (CHREC_VARIABLE (op0), 294 (CHREC_VARIABLE (op0),
294 chrec_fold_minus (type, CHREC_LEFT (op0), op1), 295 chrec_fold_minus (type, CHREC_LEFT (op0), op1),
295 CHREC_RIGHT (op0)); 296 CHREC_RIGHT (op0));
296 } 297 }
297 298
298 default: 299 default:
299 switch (TREE_CODE (op1)) 300 switch (TREE_CODE (op1))
300 { 301 {
301 case POLYNOMIAL_CHREC: 302 case POLYNOMIAL_CHREC:
302 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR) 303 if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
303 return build_polynomial_chrec 304 return build_polynomial_chrec
304 (CHREC_VARIABLE (op1), 305 (CHREC_VARIABLE (op1),
305 chrec_fold_plus (type, op0, CHREC_LEFT (op1)), 306 chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
306 CHREC_RIGHT (op1)); 307 CHREC_RIGHT (op1));
307 else 308 else
308 return build_polynomial_chrec 309 return build_polynomial_chrec
309 (CHREC_VARIABLE (op1), 310 (CHREC_VARIABLE (op1),
310 chrec_fold_minus (type, op0, CHREC_LEFT (op1)), 311 chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
311 chrec_fold_multiply (type, CHREC_RIGHT (op1), 312 chrec_fold_multiply (type, CHREC_RIGHT (op1),
312 SCALAR_FLOAT_TYPE_P (type) 313 SCALAR_FLOAT_TYPE_P (type)
313 ? build_real (type, dconstm1) 314 ? build_real (type, dconstm1)
314 : build_int_cst_type (type, -1))); 315 : build_int_cst_type (type, -1)));
315 316
316 default: 317 default:
332 } 333 }
333 334
334 /* Fold the addition of two chrecs. */ 335 /* Fold the addition of two chrecs. */
335 336
336 tree 337 tree
337 chrec_fold_plus (tree type, 338 chrec_fold_plus (tree type,
338 tree op0, 339 tree op0,
339 tree op1) 340 tree op1)
340 { 341 {
341 enum tree_code code; 342 enum tree_code code;
342 if (automatically_generated_chrec_p (op0) 343 if (automatically_generated_chrec_p (op0)
350 351
351 if (POINTER_TYPE_P (type)) 352 if (POINTER_TYPE_P (type))
352 code = POINTER_PLUS_EXPR; 353 code = POINTER_PLUS_EXPR;
353 else 354 else
354 code = PLUS_EXPR; 355 code = PLUS_EXPR;
355 356
356 return chrec_fold_plus_1 (code, type, op0, op1); 357 return chrec_fold_plus_1 (code, type, op0, op1);
357 } 358 }
358 359
359 /* Fold the subtraction of two chrecs. */ 360 /* Fold the subtraction of two chrecs. */
360 361
361 tree 362 tree
362 chrec_fold_minus (tree type, 363 chrec_fold_minus (tree type,
363 tree op0, 364 tree op0,
364 tree op1) 365 tree op1)
365 { 366 {
366 if (automatically_generated_chrec_p (op0) 367 if (automatically_generated_chrec_p (op0)
367 || automatically_generated_chrec_p (op1)) 368 || automatically_generated_chrec_p (op1))
368 return chrec_fold_automatically_generated_operands (op0, op1); 369 return chrec_fold_automatically_generated_operands (op0, op1);
369 370
370 if (integer_zerop (op1)) 371 if (integer_zerop (op1))
371 return op0; 372 return op0;
372 373
373 return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1); 374 return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
374 } 375 }
375 376
376 /* Fold the multiplication of two chrecs. */ 377 /* Fold the multiplication of two chrecs. */
377 378
378 tree 379 tree
379 chrec_fold_multiply (tree type, 380 chrec_fold_multiply (tree type,
380 tree op0, 381 tree op0,
381 tree op1) 382 tree op1)
382 { 383 {
383 if (automatically_generated_chrec_p (op0) 384 if (automatically_generated_chrec_p (op0)
384 || automatically_generated_chrec_p (op1)) 385 || automatically_generated_chrec_p (op1))
385 return chrec_fold_automatically_generated_operands (op0, op1); 386 return chrec_fold_automatically_generated_operands (op0, op1);
386 387
387 switch (TREE_CODE (op0)) 388 switch (TREE_CODE (op0))
388 { 389 {
389 case POLYNOMIAL_CHREC: 390 case POLYNOMIAL_CHREC:
390 switch (TREE_CODE (op1)) 391 switch (TREE_CODE (op1))
391 { 392 {
392 case POLYNOMIAL_CHREC: 393 case POLYNOMIAL_CHREC:
393 return chrec_fold_multiply_poly_poly (type, op0, op1); 394 return chrec_fold_multiply_poly_poly (type, op0, op1);
394 395
395 default: 396 default:
396 if (integer_onep (op1)) 397 if (integer_onep (op1))
397 return op0; 398 return op0;
398 if (integer_zerop (op1)) 399 if (integer_zerop (op1))
399 return build_int_cst (type, 0); 400 return build_int_cst (type, 0);
400 401
401 return build_polynomial_chrec 402 return build_polynomial_chrec
402 (CHREC_VARIABLE (op0), 403 (CHREC_VARIABLE (op0),
403 chrec_fold_multiply (type, CHREC_LEFT (op0), op1), 404 chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
404 chrec_fold_multiply (type, CHREC_RIGHT (op0), op1)); 405 chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
405 } 406 }
406 407
407 default: 408 default:
408 if (integer_onep (op0)) 409 if (integer_onep (op0))
409 return op1; 410 return op1;
410 411
411 if (integer_zerop (op0)) 412 if (integer_zerop (op0))
412 return build_int_cst (type, 0); 413 return build_int_cst (type, 0);
413 414
414 switch (TREE_CODE (op1)) 415 switch (TREE_CODE (op1))
415 { 416 {
416 case POLYNOMIAL_CHREC: 417 case POLYNOMIAL_CHREC:
417 return build_polynomial_chrec 418 return build_polynomial_chrec
418 (CHREC_VARIABLE (op1), 419 (CHREC_VARIABLE (op1),
419 chrec_fold_multiply (type, CHREC_LEFT (op1), op0), 420 chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
420 chrec_fold_multiply (type, CHREC_RIGHT (op1), op0)); 421 chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
421 422
422 default: 423 default:
423 if (integer_onep (op1)) 424 if (integer_onep (op1))
424 return op0; 425 return op0;
425 if (integer_zerop (op1)) 426 if (integer_zerop (op1))
426 return build_int_cst (type, 0); 427 return build_int_cst (type, 0);
434 /* Operations. */ 435 /* Operations. */
435 436
436 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate 437 /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate
437 calculation overflows, otherwise return C(n,k) with type TYPE. */ 438 calculation overflows, otherwise return C(n,k) with type TYPE. */
438 439
439 static tree 440 static tree
440 tree_fold_binomial (tree type, tree n, unsigned int k) 441 tree_fold_binomial (tree type, tree n, unsigned int k)
441 { 442 {
442 unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum; 443 unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum;
443 HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum; 444 HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum;
444 unsigned int i; 445 unsigned int i;
507 } 508 }
508 509
509 /* Helper function. Use the Newton's interpolating formula for 510 /* Helper function. Use the Newton's interpolating formula for
510 evaluating the value of the evolution function. */ 511 evaluating the value of the evolution function. */
511 512
512 static tree 513 static tree
513 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k) 514 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
514 { 515 {
515 tree arg0, arg1, binomial_n_k; 516 tree arg0, arg1, binomial_n_k;
516 tree type = TREE_TYPE (chrec); 517 tree type = TREE_TYPE (chrec);
517 struct loop *var_loop = get_loop (var); 518 struct loop *var_loop = get_loop (var);
535 } 536 }
536 537
537 binomial_n_k = tree_fold_binomial (type, n, k); 538 binomial_n_k = tree_fold_binomial (type, n, k);
538 if (!binomial_n_k) 539 if (!binomial_n_k)
539 return chrec_dont_know; 540 return chrec_dont_know;
540 541
541 return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k); 542 return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k);
542 } 543 }
543 544
544 /* Evaluates "CHREC (X)" when the varying variable is VAR. 545 /* Evaluates "CHREC (X)" when the varying variable is VAR.
545 Example: Given the following parameters, 546 Example: Given the following parameters,
546 547
547 var = 1 548 var = 1
548 chrec = {3, +, 4}_1 549 chrec = {3, +, 4}_1
549 x = 10 550 x = 10
550 551
551 The result is given by the Newton's interpolating formula: 552 The result is given by the Newton's interpolating formula:
552 3 * \binom{10}{0} + 4 * \binom{10}{1}. 553 3 * \binom{10}{0} + 4 * \binom{10}{1}.
553 */ 554 */
554 555
555 tree 556 tree
556 chrec_apply (unsigned var, 557 chrec_apply (unsigned var,
557 tree chrec, 558 tree chrec,
558 tree x) 559 tree x)
559 { 560 {
560 tree type = chrec_type (chrec); 561 tree type = chrec_type (chrec);
561 tree res = chrec_dont_know; 562 tree res = chrec_dont_know;
562 563
566 /* When the symbols are defined in an outer loop, it is possible 567 /* When the symbols are defined in an outer loop, it is possible
567 to symbolically compute the apply, since the symbols are 568 to symbolically compute the apply, since the symbols are
568 constants with respect to the varying loop. */ 569 constants with respect to the varying loop. */
569 || chrec_contains_symbols_defined_in_loop (chrec, var)) 570 || chrec_contains_symbols_defined_in_loop (chrec, var))
570 return chrec_dont_know; 571 return chrec_dont_know;
571 572
572 if (dump_file && (dump_flags & TDF_DETAILS)) 573 if (dump_file && (dump_flags & TDF_DETAILS))
573 fprintf (dump_file, "(chrec_apply \n"); 574 fprintf (dump_file, "(chrec_apply \n");
574 575
575 if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type)) 576 if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
576 x = build_real_from_int_cst (type, x); 577 x = build_real_from_int_cst (type, x);
580 /* "{a, +, b} (x)" -> "a + b*x". */ 581 /* "{a, +, b} (x)" -> "a + b*x". */
581 x = chrec_convert_rhs (type, x, NULL); 582 x = chrec_convert_rhs (type, x, NULL);
582 res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x); 583 res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x);
583 res = chrec_fold_plus (type, CHREC_LEFT (chrec), res); 584 res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
584 } 585 }
585 586
586 else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) 587 else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
587 res = chrec; 588 res = chrec;
588 589
589 else if (TREE_CODE (x) == INTEGER_CST 590 else if (TREE_CODE (x) == INTEGER_CST
590 && tree_int_cst_sgn (x) == 1) 591 && tree_int_cst_sgn (x) == 1)
591 /* testsuite/.../ssa-chrec-38.c. */ 592 /* testsuite/.../ssa-chrec-38.c. */
592 res = chrec_evaluate (var, chrec, x, 0); 593 res = chrec_evaluate (var, chrec, x, 0);
593 else 594 else
594 res = chrec_dont_know; 595 res = chrec_dont_know;
595 596
596 if (dump_file && (dump_flags & TDF_DETAILS)) 597 if (dump_file && (dump_flags & TDF_DETAILS))
597 { 598 {
598 fprintf (dump_file, " (varying_loop = %d\n", var); 599 fprintf (dump_file, " (varying_loop = %d\n", var);
599 fprintf (dump_file, ")\n (chrec = "); 600 fprintf (dump_file, ")\n (chrec = ");
600 print_generic_expr (dump_file, chrec, 0); 601 print_generic_expr (dump_file, chrec, 0);
602 print_generic_expr (dump_file, x, 0); 603 print_generic_expr (dump_file, x, 0);
603 fprintf (dump_file, ")\n (res = "); 604 fprintf (dump_file, ")\n (res = ");
604 print_generic_expr (dump_file, res, 0); 605 print_generic_expr (dump_file, res, 0);
605 fprintf (dump_file, "))\n"); 606 fprintf (dump_file, "))\n");
606 } 607 }
607 608
608 return res; 609 return res;
609 } 610 }
610 611
611 /* Replaces the initial condition in CHREC with INIT_COND. */ 612 /* Replaces the initial condition in CHREC with INIT_COND. */
612 613
613 tree 614 tree
614 chrec_replace_initial_condition (tree chrec, 615 chrec_replace_initial_condition (tree chrec,
615 tree init_cond) 616 tree init_cond)
616 { 617 {
617 if (automatically_generated_chrec_p (chrec)) 618 if (automatically_generated_chrec_p (chrec))
618 return chrec; 619 return chrec;
619 620
620 gcc_assert (chrec_type (chrec) == chrec_type (init_cond)); 621 gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
621 622
622 switch (TREE_CODE (chrec)) 623 switch (TREE_CODE (chrec))
623 { 624 {
624 case POLYNOMIAL_CHREC: 625 case POLYNOMIAL_CHREC:
625 return build_polynomial_chrec 626 return build_polynomial_chrec
626 (CHREC_VARIABLE (chrec), 627 (CHREC_VARIABLE (chrec),
627 chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond), 628 chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond),
628 CHREC_RIGHT (chrec)); 629 CHREC_RIGHT (chrec));
629 630
630 default: 631 default:
631 return init_cond; 632 return init_cond;
632 } 633 }
633 } 634 }
634 635
635 /* Returns the initial condition of a given CHREC. */ 636 /* Returns the initial condition of a given CHREC. */
636 637
637 tree 638 tree
638 initial_condition (tree chrec) 639 initial_condition (tree chrec)
639 { 640 {
640 if (automatically_generated_chrec_p (chrec)) 641 if (automatically_generated_chrec_p (chrec))
641 return chrec; 642 return chrec;
642 643
643 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) 644 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
644 return initial_condition (CHREC_LEFT (chrec)); 645 return initial_condition (CHREC_LEFT (chrec));
645 else 646 else
646 return chrec; 647 return chrec;
647 } 648 }
648 649
649 /* Returns a univariate function that represents the evolution in 650 /* Returns a univariate function that represents the evolution in
650 LOOP_NUM. Mask the evolution of any other loop. */ 651 LOOP_NUM. Mask the evolution of any other loop. */
651 652
652 tree 653 tree
653 hide_evolution_in_other_loops_than_loop (tree chrec, 654 hide_evolution_in_other_loops_than_loop (tree chrec,
654 unsigned loop_num) 655 unsigned loop_num)
655 { 656 {
656 struct loop *loop = get_loop (loop_num), *chloop; 657 struct loop *loop = get_loop (loop_num), *chloop;
657 if (automatically_generated_chrec_p (chrec)) 658 if (automatically_generated_chrec_p (chrec))
658 return chrec; 659 return chrec;
659 660
660 switch (TREE_CODE (chrec)) 661 switch (TREE_CODE (chrec))
661 { 662 {
662 case POLYNOMIAL_CHREC: 663 case POLYNOMIAL_CHREC:
663 chloop = get_chrec_loop (chrec); 664 chloop = get_chrec_loop (chrec);
664 665
665 if (chloop == loop) 666 if (chloop == loop)
666 return build_polynomial_chrec 667 return build_polynomial_chrec
667 (loop_num, 668 (loop_num,
668 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), 669 hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
669 loop_num), 670 loop_num),
670 CHREC_RIGHT (chrec)); 671 CHREC_RIGHT (chrec));
671 672
672 else if (flow_loop_nested_p (chloop, loop)) 673 else if (flow_loop_nested_p (chloop, loop))
673 /* There is no evolution in this loop. */ 674 /* There is no evolution in this loop. */
674 return initial_condition (chrec); 675 return initial_condition (chrec);
675 676
676 else 677 else
677 { 678 {
678 gcc_assert (flow_loop_nested_p (loop, chloop)); 679 gcc_assert (flow_loop_nested_p (loop, chloop));
679 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), 680 return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
680 loop_num); 681 loop_num);
681 } 682 }
682 683
683 default: 684 default:
684 return chrec; 685 return chrec;
685 } 686 }
686 } 687 }
687 688
688 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is 689 /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is
689 true, otherwise returns the initial condition in LOOP_NUM. */ 690 true, otherwise returns the initial condition in LOOP_NUM. */
690 691
691 static tree 692 static tree
692 chrec_component_in_loop_num (tree chrec, 693 chrec_component_in_loop_num (tree chrec,
693 unsigned loop_num, 694 unsigned loop_num,
694 bool right) 695 bool right)
695 { 696 {
696 tree component; 697 tree component;
697 struct loop *loop = get_loop (loop_num), *chloop; 698 struct loop *loop = get_loop (loop_num), *chloop;
698 699
699 if (automatically_generated_chrec_p (chrec)) 700 if (automatically_generated_chrec_p (chrec))
700 return chrec; 701 return chrec;
701 702
702 switch (TREE_CODE (chrec)) 703 switch (TREE_CODE (chrec))
703 { 704 {
704 case POLYNOMIAL_CHREC: 705 case POLYNOMIAL_CHREC:
705 chloop = get_chrec_loop (chrec); 706 chloop = get_chrec_loop (chrec);
706 707
712 component = CHREC_LEFT (chrec); 713 component = CHREC_LEFT (chrec);
713 714
714 if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC 715 if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC
715 || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)) 716 || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec))
716 return component; 717 return component;
717 718
718 else 719 else
719 return build_polynomial_chrec 720 return build_polynomial_chrec
720 (loop_num, 721 (loop_num,
721 chrec_component_in_loop_num (CHREC_LEFT (chrec), 722 chrec_component_in_loop_num (CHREC_LEFT (chrec),
722 loop_num, 723 loop_num,
723 right), 724 right),
724 component); 725 component);
725 } 726 }
726 727
727 else if (flow_loop_nested_p (chloop, loop)) 728 else if (flow_loop_nested_p (chloop, loop))
728 /* There is no evolution part in this loop. */ 729 /* There is no evolution part in this loop. */
729 return NULL_TREE; 730 return NULL_TREE;
730 731
731 else 732 else
732 { 733 {
733 gcc_assert (flow_loop_nested_p (loop, chloop)); 734 gcc_assert (flow_loop_nested_p (loop, chloop));
734 return chrec_component_in_loop_num (CHREC_LEFT (chrec), 735 return chrec_component_in_loop_num (CHREC_LEFT (chrec),
735 loop_num, 736 loop_num,
736 right); 737 right);
737 } 738 }
738 739
739 default: 740 default:
740 if (right) 741 if (right)
741 return NULL_TREE; 742 return NULL_TREE;
742 else 743 else
743 return chrec; 744 return chrec;
744 } 745 }
745 } 746 }
746 747
747 /* Returns the evolution part in LOOP_NUM. Example: the call 748 /* Returns the evolution part in LOOP_NUM. Example: the call
748 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns 749 evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
749 {1, +, 2}_1 */ 750 {1, +, 2}_1 */
750 751
751 tree 752 tree
752 evolution_part_in_loop_num (tree chrec, 753 evolution_part_in_loop_num (tree chrec,
753 unsigned loop_num) 754 unsigned loop_num)
754 { 755 {
755 return chrec_component_in_loop_num (chrec, loop_num, true); 756 return chrec_component_in_loop_num (chrec, loop_num, true);
756 } 757 }
757 758
758 /* Returns the initial condition in LOOP_NUM. Example: the call 759 /* Returns the initial condition in LOOP_NUM. Example: the call
759 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns 760 initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
760 {0, +, 1}_1 */ 761 {0, +, 1}_1 */
761 762
762 tree 763 tree
763 initial_condition_in_loop_num (tree chrec, 764 initial_condition_in_loop_num (tree chrec,
764 unsigned loop_num) 765 unsigned loop_num)
765 { 766 {
766 return chrec_component_in_loop_num (chrec, loop_num, false); 767 return chrec_component_in_loop_num (chrec, loop_num, false);
767 } 768 }
768 769
769 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM. 770 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
770 This function is essentially used for setting the evolution to 771 This function is essentially used for setting the evolution to
771 chrec_dont_know, for example after having determined that it is 772 chrec_dont_know, for example after having determined that it is
772 impossible to say how many times a loop will execute. */ 773 impossible to say how many times a loop will execute. */
773 774
774 tree 775 tree
775 reset_evolution_in_loop (unsigned loop_num, 776 reset_evolution_in_loop (unsigned loop_num,
776 tree chrec, 777 tree chrec,
777 tree new_evol) 778 tree new_evol)
778 { 779 {
779 struct loop *loop = get_loop (loop_num); 780 struct loop *loop = get_loop (loop_num);
780 781
781 if (POINTER_TYPE_P (chrec_type (chrec))) 782 if (POINTER_TYPE_P (chrec_type (chrec)))
796 } 797 }
797 798
798 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC 799 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
799 && CHREC_VARIABLE (chrec) == loop_num) 800 && CHREC_VARIABLE (chrec) == loop_num)
800 chrec = CHREC_LEFT (chrec); 801 chrec = CHREC_LEFT (chrec);
801 802
802 return build_polynomial_chrec (loop_num, chrec, new_evol); 803 return build_polynomial_chrec (loop_num, chrec, new_evol);
803 } 804 }
804 805
805 /* Merges two evolution functions that were found by following two 806 /* Merges two evolution functions that were found by following two
806 alternate paths of a conditional expression. */ 807 alternate paths of a conditional expression. */
807 808
808 tree 809 tree
809 chrec_merge (tree chrec1, 810 chrec_merge (tree chrec1,
810 tree chrec2) 811 tree chrec2)
811 { 812 {
812 if (chrec1 == chrec_dont_know 813 if (chrec1 == chrec_dont_know
813 || chrec2 == chrec_dont_know) 814 || chrec2 == chrec_dont_know)
814 return chrec_dont_know; 815 return chrec_dont_know;
815 816
816 if (chrec1 == chrec_known 817 if (chrec1 == chrec_known
817 || chrec2 == chrec_known) 818 || chrec2 == chrec_known)
818 return chrec_known; 819 return chrec_known;
819 820
820 if (chrec1 == chrec_not_analyzed_yet) 821 if (chrec1 == chrec_not_analyzed_yet)
821 return chrec2; 822 return chrec2;
832 833
833 /* Observers. */ 834 /* Observers. */
834 835
835 /* Helper function for is_multivariate_chrec. */ 836 /* Helper function for is_multivariate_chrec. */
836 837
837 static bool 838 static bool
838 is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var) 839 is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
839 { 840 {
840 if (chrec == NULL_TREE) 841 if (chrec == NULL_TREE)
841 return false; 842 return false;
842 843
843 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) 844 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
844 { 845 {
845 if (CHREC_VARIABLE (chrec) != rec_var) 846 if (CHREC_VARIABLE (chrec) != rec_var)
846 return true; 847 return true;
847 else 848 else
848 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var) 849 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var)
849 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var)); 850 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var));
850 } 851 }
851 else 852 else
852 return false; 853 return false;
853 } 854 }
854 855
855 /* Determine whether the given chrec is multivariate or not. */ 856 /* Determine whether the given chrec is multivariate or not. */
856 857
857 bool 858 bool
858 is_multivariate_chrec (const_tree chrec) 859 is_multivariate_chrec (const_tree chrec)
859 { 860 {
860 if (chrec == NULL_TREE) 861 if (chrec == NULL_TREE)
861 return false; 862 return false;
862 863
863 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) 864 if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
864 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), 865 return (is_multivariate_chrec_rec (CHREC_LEFT (chrec),
865 CHREC_VARIABLE (chrec)) 866 CHREC_VARIABLE (chrec))
866 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), 867 || is_multivariate_chrec_rec (CHREC_RIGHT (chrec),
867 CHREC_VARIABLE (chrec))); 868 CHREC_VARIABLE (chrec)));
868 else 869 else
869 return false; 870 return false;
870 } 871 }
871 872
872 /* Determines whether the chrec contains symbolic names or not. */ 873 /* Determines whether the chrec contains symbolic names or not. */
873 874
874 bool 875 bool
875 chrec_contains_symbols (const_tree chrec) 876 chrec_contains_symbols (const_tree chrec)
876 { 877 {
877 int i, n; 878 int i, n;
878 879
879 if (chrec == NULL_TREE) 880 if (chrec == NULL_TREE)
880 return false; 881 return false;
881 882
882 if (TREE_CODE (chrec) == SSA_NAME 883 if (TREE_CODE (chrec) == SSA_NAME
883 || TREE_CODE (chrec) == VAR_DECL 884 || TREE_CODE (chrec) == VAR_DECL
884 || TREE_CODE (chrec) == PARM_DECL 885 || TREE_CODE (chrec) == PARM_DECL
885 || TREE_CODE (chrec) == FUNCTION_DECL 886 || TREE_CODE (chrec) == FUNCTION_DECL
886 || TREE_CODE (chrec) == LABEL_DECL 887 || TREE_CODE (chrec) == LABEL_DECL
895 return false; 896 return false;
896 } 897 }
897 898
898 /* Determines whether the chrec contains undetermined coefficients. */ 899 /* Determines whether the chrec contains undetermined coefficients. */
899 900
900 bool 901 bool
901 chrec_contains_undetermined (const_tree chrec) 902 chrec_contains_undetermined (const_tree chrec)
902 { 903 {
903 int i, n; 904 int i, n;
904 905
905 if (chrec == chrec_dont_know) 906 if (chrec == chrec_dont_know)
927 if (expr == NULL_TREE) 928 if (expr == NULL_TREE)
928 return false; 929 return false;
929 930
930 if (size) 931 if (size)
931 (*size)++; 932 (*size)++;
932 933
933 if (tree_is_chrec (expr)) 934 if (tree_is_chrec (expr))
934 return true; 935 return true;
935 936
936 n = TREE_OPERAND_LENGTH (expr); 937 n = TREE_OPERAND_LENGTH (expr);
937 for (i = 0; i < n; i++) 938 for (i = 0; i < n; i++)
968 { 969 {
969 case 2: 970 case 2:
970 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1), 971 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
971 loopnum)) 972 loopnum))
972 return false; 973 return false;
973 974
974 case 1: 975 case 1:
975 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0), 976 if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
976 loopnum)) 977 loopnum))
977 return false; 978 return false;
978 return true; 979 return true;
993 } 994 }
994 995
995 /* Determine whether the given tree is an affine multivariate 996 /* Determine whether the given tree is an affine multivariate
996 evolution. */ 997 evolution. */
997 998
998 bool 999 bool
999 evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum) 1000 evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
1000 { 1001 {
1001 if (chrec == NULL_TREE) 1002 if (chrec == NULL_TREE)
1002 return false; 1003 return false;
1003 1004
1004 switch (TREE_CODE (chrec)) 1005 switch (TREE_CODE (chrec))
1005 { 1006 {
1006 case POLYNOMIAL_CHREC: 1007 case POLYNOMIAL_CHREC:
1007 if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum)) 1008 if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
1008 { 1009 {
1009 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)) 1010 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
1010 return true; 1011 return true;
1011 else 1012 else
1012 { 1013 {
1013 if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC 1014 if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC
1014 && CHREC_VARIABLE (CHREC_RIGHT (chrec)) 1015 && CHREC_VARIABLE (CHREC_RIGHT (chrec))
1015 != CHREC_VARIABLE (chrec) 1016 != CHREC_VARIABLE (chrec)
1016 && evolution_function_is_affine_multivariate_p 1017 && evolution_function_is_affine_multivariate_p
1017 (CHREC_RIGHT (chrec), loopnum)) 1018 (CHREC_RIGHT (chrec), loopnum))
1018 return true; 1019 return true;
1019 else 1020 else
1020 return false; 1021 return false;
1021 } 1022 }
1023 else 1024 else
1024 { 1025 {
1025 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum) 1026 if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum)
1026 && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC 1027 && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1027 && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec) 1028 && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)
1028 && evolution_function_is_affine_multivariate_p 1029 && evolution_function_is_affine_multivariate_p
1029 (CHREC_LEFT (chrec), loopnum)) 1030 (CHREC_LEFT (chrec), loopnum))
1030 return true; 1031 return true;
1031 else 1032 else
1032 return false; 1033 return false;
1033 } 1034 }
1034 1035
1035 default: 1036 default:
1036 return false; 1037 return false;
1037 } 1038 }
1038 } 1039 }
1039 1040
1040 /* Determine whether the given tree is a function in zero or one 1041 /* Determine whether the given tree is a function in zero or one
1041 variables. */ 1042 variables. */
1042 1043
1043 bool 1044 bool
1044 evolution_function_is_univariate_p (const_tree chrec) 1045 evolution_function_is_univariate_p (const_tree chrec)
1045 { 1046 {
1046 if (chrec == NULL_TREE) 1047 if (chrec == NULL_TREE)
1047 return true; 1048 return true;
1048 1049
1049 switch (TREE_CODE (chrec)) 1050 switch (TREE_CODE (chrec))
1050 { 1051 {
1051 case POLYNOMIAL_CHREC: 1052 case POLYNOMIAL_CHREC:
1052 switch (TREE_CODE (CHREC_LEFT (chrec))) 1053 switch (TREE_CODE (CHREC_LEFT (chrec)))
1053 { 1054 {
1055 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec))) 1056 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec)))
1056 return false; 1057 return false;
1057 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec))) 1058 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec)))
1058 return false; 1059 return false;
1059 break; 1060 break;
1060 1061
1061 default: 1062 default:
1062 break; 1063 break;
1063 } 1064 }
1064 1065
1065 switch (TREE_CODE (CHREC_RIGHT (chrec))) 1066 switch (TREE_CODE (CHREC_RIGHT (chrec)))
1066 { 1067 {
1067 case POLYNOMIAL_CHREC: 1068 case POLYNOMIAL_CHREC:
1068 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec))) 1069 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec)))
1069 return false; 1070 return false;
1070 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec))) 1071 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec)))
1071 return false; 1072 return false;
1072 break; 1073 break;
1073 1074
1074 default: 1075 default:
1075 break; 1076 break;
1076 } 1077 }
1077 1078
1078 default: 1079 default:
1079 return true; 1080 return true;
1080 } 1081 }
1081 } 1082 }
1082 1083
1083 /* Returns the number of variables of CHREC. Example: the call 1084 /* Returns the number of variables of CHREC. Example: the call
1084 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */ 1085 nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */
1085 1086
1086 unsigned 1087 unsigned
1087 nb_vars_in_chrec (tree chrec) 1088 nb_vars_in_chrec (tree chrec)
1088 { 1089 {
1089 if (chrec == NULL_TREE) 1090 if (chrec == NULL_TREE)
1090 return 0; 1091 return 0;
1091 1092
1092 switch (TREE_CODE (chrec)) 1093 switch (TREE_CODE (chrec))
1093 { 1094 {
1094 case POLYNOMIAL_CHREC: 1095 case POLYNOMIAL_CHREC:
1095 return 1 + nb_vars_in_chrec 1096 return 1 + nb_vars_in_chrec
1096 (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec))); 1097 (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec)));
1097 1098
1098 default: 1099 default:
1099 return 0; 1100 return 0;
1100 } 1101 }
1101 }
1102
1103 /* Returns true if TYPE is a type in that we cannot directly perform
1104 arithmetics, even though it is a scalar type. */
1105
1106 static bool
1107 avoid_arithmetics_in_type_p (const_tree type)
1108 {
1109 /* Ada frontend uses subtypes -- an arithmetic cannot be directly performed
1110 in the subtype, but a base type must be used, and the result then can
1111 be casted to the subtype. */
1112 if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != NULL_TREE)
1113 return true;
1114
1115 return false;
1116 } 1102 }
1117 1103
1118 static tree chrec_convert_1 (tree, tree, gimple, bool); 1104 static tree chrec_convert_1 (tree, tree, gimple, bool);
1119 1105
1120 /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv 1106 /* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
1134 bool enforce_overflow_semantics; 1120 bool enforce_overflow_semantics;
1135 bool must_check_src_overflow, must_check_rslt_overflow; 1121 bool must_check_src_overflow, must_check_rslt_overflow;
1136 tree new_base, new_step; 1122 tree new_base, new_step;
1137 tree step_type = POINTER_TYPE_P (type) ? sizetype : type; 1123 tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1138 1124
1139 /* If we cannot perform arithmetic in TYPE, avoid creating an scev. */
1140 if (avoid_arithmetics_in_type_p (type))
1141 return false;
1142
1143 /* In general, 1125 /* In general,
1144 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i, 1126 (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
1145 but we must check some assumptions. 1127 but we must check some assumptions.
1146 1128
1147 1) If [BASE, +, STEP] wraps, the equation is not valid when precision 1129 1) If [BASE, +, STEP] wraps, the equation is not valid when precision
1148 of CT is smaller than the precision of TYPE. For example, when we 1130 of CT is smaller than the precision of TYPE. For example, when we
1149 cast unsigned char [254, +, 1] to unsigned, the values on left side 1131 cast unsigned char [254, +, 1] to unsigned, the values on left side
1150 are 254, 255, 0, 1, ..., but those on the right side are 1132 are 254, 255, 0, 1, ..., but those on the right side are
1151 254, 255, 256, 257, ... 1133 254, 255, 256, 257, ...
1199 use_overflow_semantics); 1181 use_overflow_semantics);
1200 /* The step must be sign extended, regardless of the signedness 1182 /* The step must be sign extended, regardless of the signedness
1201 of CT and TYPE. This only needs to be handled specially when 1183 of CT and TYPE. This only needs to be handled specially when
1202 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255] 1184 CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
1203 (with values 100, 99, 98, ...) from becoming signed or unsigned 1185 (with values 100, 99, 98, ...) from becoming signed or unsigned
1204 [100, +, 255] with values 100, 355, ...; the sign-extension is 1186 [100, +, 255] with values 100, 355, ...; the sign-extension is
1205 performed by default when CT is signed. */ 1187 performed by default when CT is signed. */
1206 new_step = *step; 1188 new_step = *step;
1207 if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct)) 1189 if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
1208 new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt, 1190 new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt,
1209 use_overflow_semantics); 1191 use_overflow_semantics);
1225 } 1207 }
1226 1208
1227 1209
1228 /* Convert CHREC for the right hand side of a CREC. 1210 /* Convert CHREC for the right hand side of a CREC.
1229 The increment for a pointer type is always sizetype. */ 1211 The increment for a pointer type is always sizetype. */
1230 tree 1212 tree
1231 chrec_convert_rhs (tree type, tree chrec, gimple at_stmt) 1213 chrec_convert_rhs (tree type, tree chrec, gimple at_stmt)
1232 { 1214 {
1233 if (POINTER_TYPE_P (type)) 1215 if (POINTER_TYPE_P (type))
1234 type = sizetype; 1216 type = sizetype;
1235 return chrec_convert (type, chrec, at_stmt); 1217 return chrec_convert (type, chrec, at_stmt);
1244 1226
1245 The following rule is always true: TREE_TYPE (chrec) == 1227 The following rule is always true: TREE_TYPE (chrec) ==
1246 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)). 1228 TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
1247 An example of what could happen when adding two chrecs and the type 1229 An example of what could happen when adding two chrecs and the type
1248 of the CHREC_RIGHT is different than CHREC_LEFT is: 1230 of the CHREC_RIGHT is different than CHREC_LEFT is:
1249 1231
1250 {(uint) 0, +, (uchar) 10} + 1232 {(uint) 0, +, (uchar) 10} +
1251 {(uint) 0, +, (uchar) 250} 1233 {(uint) 0, +, (uchar) 250}
1252 1234
1253 that would produce a wrong result if CHREC_RIGHT is not (uint): 1235 that would produce a wrong result if CHREC_RIGHT is not (uint):
1254 1236
1255 {(uint) 0, +, (uchar) 4} 1237 {(uint) 0, +, (uchar) 4}
1256 1238
1257 instead of 1239 instead of
1258 1240
1259 {(uint) 0, +, (uint) 260} 1241 {(uint) 0, +, (uint) 260}
1260 */ 1242 */
1261 1243
1262 tree 1244 tree
1263 chrec_convert (tree type, tree chrec, gimple at_stmt) 1245 chrec_convert (tree type, tree chrec, gimple at_stmt)
1264 { 1246 {
1265 return chrec_convert_1 (type, chrec, at_stmt, true); 1247 return chrec_convert_1 (type, chrec, at_stmt, true);
1266 } 1248 }
1267 1249
1269 which the CHREC is built, it sets AT_STMT to the statement that 1251 which the CHREC is built, it sets AT_STMT to the statement that
1270 contains the definition of the analyzed variable, otherwise the 1252 contains the definition of the analyzed variable, otherwise the
1271 conversion is less accurate: the information is used for 1253 conversion is less accurate: the information is used for
1272 determining a more accurate estimation of the number of iterations. 1254 determining a more accurate estimation of the number of iterations.
1273 By default AT_STMT could be safely set to NULL_TREE. 1255 By default AT_STMT could be safely set to NULL_TREE.
1274 1256
1275 USE_OVERFLOW_SEMANTICS is true if this function should assume that 1257 USE_OVERFLOW_SEMANTICS is true if this function should assume that
1276 the rules for overflow of the given language apply (e.g., that signed 1258 the rules for overflow of the given language apply (e.g., that signed
1277 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary 1259 arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
1278 tests, but also to enforce that the result follows them. */ 1260 tests, but also to enforce that the result follows them. */
1279 1261
1280 static tree 1262 static tree
1281 chrec_convert_1 (tree type, tree chrec, gimple at_stmt, 1263 chrec_convert_1 (tree type, tree chrec, gimple at_stmt,
1282 bool use_overflow_semantics) 1264 bool use_overflow_semantics)
1283 { 1265 {
1284 tree ct, res; 1266 tree ct, res;
1285 tree base, step; 1267 tree base, step;
1286 struct loop *loop; 1268 struct loop *loop;
1287 1269
1288 if (automatically_generated_chrec_p (chrec)) 1270 if (automatically_generated_chrec_p (chrec))
1289 return chrec; 1271 return chrec;
1290 1272
1291 ct = chrec_type (chrec); 1273 ct = chrec_type (chrec);
1292 if (ct == type) 1274 if (ct == type)
1293 return chrec; 1275 return chrec;
1294 1276
1295 if (!evolution_function_is_affine_p (chrec)) 1277 if (!evolution_function_is_affine_p (chrec))
1303 use_overflow_semantics)) 1285 use_overflow_semantics))
1304 return build_polynomial_chrec (loop->num, base, step); 1286 return build_polynomial_chrec (loop->num, base, step);
1305 1287
1306 /* If we cannot propagate the cast inside the chrec, just keep the cast. */ 1288 /* If we cannot propagate the cast inside the chrec, just keep the cast. */
1307 keep_cast: 1289 keep_cast:
1308 res = fold_convert (type, chrec); 1290 /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that
1291 may be more expensive. We do want to perform this optimization here
1292 though for canonicalization reasons. */
1293 if (use_overflow_semantics
1294 && (TREE_CODE (chrec) == PLUS_EXPR
1295 || TREE_CODE (chrec) == MINUS_EXPR)
1296 && TREE_CODE (type) == INTEGER_TYPE
1297 && TREE_CODE (ct) == INTEGER_TYPE
1298 && TYPE_PRECISION (type) > TYPE_PRECISION (ct)
1299 && TYPE_OVERFLOW_UNDEFINED (ct))
1300 res = fold_build2 (TREE_CODE (chrec), type,
1301 fold_convert (type, TREE_OPERAND (chrec, 0)),
1302 fold_convert (type, TREE_OPERAND (chrec, 1)));
1303 else
1304 res = fold_convert (type, chrec);
1309 1305
1310 /* Don't propagate overflows. */ 1306 /* Don't propagate overflows. */
1311 if (CONSTANT_CLASS_P (res)) 1307 if (CONSTANT_CLASS_P (res))
1312 TREE_OVERFLOW (res) = 0; 1308 TREE_OVERFLOW (res) = 0;
1313 1309
1340 1336
1341 inner_type = TREE_TYPE (chrec); 1337 inner_type = TREE_TYPE (chrec);
1342 if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type)) 1338 if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
1343 return NULL_TREE; 1339 return NULL_TREE;
1344 1340
1345 /* If we cannot perform arithmetic in TYPE, avoid creating an scev. */
1346 if (avoid_arithmetics_in_type_p (type))
1347 return NULL_TREE;
1348
1349 rtype = POINTER_TYPE_P (type) ? sizetype : type; 1341 rtype = POINTER_TYPE_P (type) ? sizetype : type;
1350 1342
1351 left = CHREC_LEFT (chrec); 1343 left = CHREC_LEFT (chrec);
1352 right = CHREC_RIGHT (chrec); 1344 right = CHREC_RIGHT (chrec);
1353 lc = chrec_convert_aggressive (type, left); 1345 lc = chrec_convert_aggressive (type, left);
1354 if (!lc) 1346 if (!lc)
1355 lc = chrec_convert (type, left, NULL); 1347 lc = chrec_convert (type, left, NULL);
1356 rc = chrec_convert_aggressive (rtype, right); 1348 rc = chrec_convert_aggressive (rtype, right);
1357 if (!rc) 1349 if (!rc)
1358 rc = chrec_convert (rtype, right, NULL); 1350 rc = chrec_convert (rtype, right, NULL);
1359 1351
1360 return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc); 1352 return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
1361 } 1353 }
1362 1354
1363 /* Returns true when CHREC0 == CHREC1. */ 1355 /* Returns true when CHREC0 == CHREC1. */
1364 1356
1365 bool 1357 bool
1366 eq_evolutions_p (const_tree chrec0, const_tree chrec1) 1358 eq_evolutions_p (const_tree chrec0, const_tree chrec1)
1367 { 1359 {
1368 if (chrec0 == NULL_TREE 1360 if (chrec0 == NULL_TREE
1369 || chrec1 == NULL_TREE 1361 || chrec1 == NULL_TREE
1370 || TREE_CODE (chrec0) != TREE_CODE (chrec1)) 1362 || TREE_CODE (chrec0) != TREE_CODE (chrec1))
1382 return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1) 1374 return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
1383 && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1)) 1375 && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (chrec1))
1384 && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1))); 1376 && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1)));
1385 default: 1377 default:
1386 return false; 1378 return false;
1387 } 1379 }
1388 } 1380 }
1389 1381
1390 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow), 1382 /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow),
1391 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine 1383 EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
1392 which of these cases happens. */ 1384 which of these cases happens. */
1419 case 3: 1411 case 3:
1420 for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data); 1412 for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, data);
1421 1413
1422 case 2: 1414 case 2:
1423 for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data); 1415 for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data);
1424 1416
1425 case 1: 1417 case 1:
1426 for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data); 1418 for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data);
1427 1419
1428 default: 1420 default:
1429 cbck (scev, data); 1421 cbck (scev, data);
1446 case MULT_EXPR: 1438 case MULT_EXPR:
1447 case MINUS_EXPR: 1439 case MINUS_EXPR:
1448 case NEGATE_EXPR: 1440 case NEGATE_EXPR:
1449 case SSA_NAME: 1441 case SSA_NAME:
1450 case NON_LVALUE_EXPR: 1442 case NON_LVALUE_EXPR:
1443 case BIT_NOT_EXPR:
1451 CASE_CONVERT: 1444 CASE_CONVERT:
1452 return true; 1445 return true;
1453 1446
1454 default: 1447 default:
1455 return false; 1448 return false;
1468 return false; 1461 return false;
1469 1462
1470 if (TREE_CODE (scev) == MULT_EXPR) 1463 if (TREE_CODE (scev) == MULT_EXPR)
1471 return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL) 1464 return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
1472 && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL)); 1465 && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
1466
1467 if (TREE_CODE (scev) == POLYNOMIAL_CHREC
1468 && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev)))
1469 return false;
1473 1470
1474 switch (TREE_CODE_LENGTH (TREE_CODE (scev))) 1471 switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
1475 { 1472 {
1476 case 3: 1473 case 3:
1477 return scev_is_linear_expression (TREE_OPERAND (scev, 0)) 1474 return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1479 && scev_is_linear_expression (TREE_OPERAND (scev, 2)); 1476 && scev_is_linear_expression (TREE_OPERAND (scev, 2));
1480 1477
1481 case 2: 1478 case 2:
1482 return scev_is_linear_expression (TREE_OPERAND (scev, 0)) 1479 return scev_is_linear_expression (TREE_OPERAND (scev, 0))
1483 && scev_is_linear_expression (TREE_OPERAND (scev, 1)); 1480 && scev_is_linear_expression (TREE_OPERAND (scev, 1));
1484 1481
1485 case 1: 1482 case 1:
1486 return scev_is_linear_expression (TREE_OPERAND (scev, 0)); 1483 return scev_is_linear_expression (TREE_OPERAND (scev, 0));
1487 1484
1488 case 0: 1485 case 0:
1489 return true; 1486 return true;
1490 1487
1491 default: 1488 default:
1492 return false; 1489 return false;
1493 } 1490 }
1494 } 1491 }
1492
1493 /* Determines whether the expression CHREC contains only interger consts
1494 in the right parts. */
1495
1496 bool
1497 evolution_function_right_is_integer_cst (const_tree chrec)
1498 {
1499 if (chrec == NULL_TREE)
1500 return false;
1501
1502 switch (TREE_CODE (chrec))
1503 {
1504 case INTEGER_CST:
1505 return true;
1506
1507 case POLYNOMIAL_CHREC:
1508 if (!evolution_function_right_is_integer_cst (CHREC_RIGHT (chrec)))
1509 return false;
1510
1511 if (TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC
1512 && !evolution_function_right_is_integer_cst (CHREC_LEFT (chrec)))
1513 return false;
1514
1515 return true;
1516
1517 default:
1518 return false;
1519 }
1520 }
1521