]>
Commit | Line | Data |
---|---|---|
73f30c63 | 1 | /* Operations with affine combinations of trees. |
8d9254fc | 2 | Copyright (C) 2005-2020 Free Software Foundation, Inc. |
b8698a0f | 3 | |
73f30c63 | 4 | This file is part of GCC. |
b8698a0f | 5 | |
73f30c63 ZD |
6 | GCC is free software; you can redistribute it and/or modify it |
7 | under the terms of the GNU General Public License as published by the | |
9dcd6f09 | 8 | Free Software Foundation; either version 3, or (at your option) any |
73f30c63 | 9 | later version. |
b8698a0f | 10 | |
73f30c63 ZD |
11 | GCC is distributed in the hope that it will be useful, but WITHOUT |
12 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 | for more details. | |
b8698a0f | 15 | |
73f30c63 | 16 | You should have received a copy of the GNU General Public License |
9dcd6f09 NC |
17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
73f30c63 ZD |
19 | |
20 | #include "config.h" | |
21 | #include "system.h" | |
22 | #include "coretypes.h" | |
c7131fb2 | 23 | #include "backend.h" |
957060b5 | 24 | #include "rtl.h" |
73f30c63 | 25 | #include "tree.h" |
c7131fb2 | 26 | #include "gimple.h" |
ba00284c | 27 | #include "ssa.h" |
957060b5 | 28 | #include "tree-pretty-print.h" |
c7131fb2 | 29 | #include "fold-const.h" |
73f30c63 | 30 | #include "tree-affine.h" |
45b0be94 | 31 | #include "gimplify.h" |
7ee2468b | 32 | #include "dumpfile.h" |
1fe37220 | 33 | #include "cfgexpand.h" |
73f30c63 ZD |
34 | |
35 | /* Extends CST as appropriate for the affine combinations COMB. */ | |
36 | ||
cc8bea09 | 37 | static widest_int |
5291ab73 | 38 | wide_int_ext_for_comb (const widest_int &cst, tree type) |
73f30c63 | 39 | { |
5291ab73 | 40 | return wi::sext (cst, TYPE_PRECISION (type)); |
73f30c63 ZD |
41 | } |
42 | ||
cc8bea09 RS |
43 | /* Likewise for polynomial offsets. */ |
44 | ||
45 | static poly_widest_int | |
46 | wide_int_ext_for_comb (const poly_widest_int &cst, tree type) | |
47 | { | |
48 | return wi::sext (cst, TYPE_PRECISION (type)); | |
49 | } | |
50 | ||
73f30c63 ZD |
51 | /* Initializes affine combination COMB so that its value is zero in TYPE. */ |
52 | ||
53 | static void | |
54 | aff_combination_zero (aff_tree *comb, tree type) | |
55 | { | |
807e902e | 56 | int i; |
73f30c63 | 57 | comb->type = type; |
807e902e | 58 | comb->offset = 0; |
73f30c63 | 59 | comb->n = 0; |
807e902e KZ |
60 | for (i = 0; i < MAX_AFF_ELTS; i++) |
61 | comb->elts[i].coef = 0; | |
73f30c63 ZD |
62 | comb->rest = NULL_TREE; |
63 | } | |
64 | ||
65 | /* Sets COMB to CST. */ | |
66 | ||
67 | void | |
cc8bea09 | 68 | aff_combination_const (aff_tree *comb, tree type, const poly_widest_int &cst) |
73f30c63 ZD |
69 | { |
70 | aff_combination_zero (comb, type); | |
5291ab73 | 71 | comb->offset = wide_int_ext_for_comb (cst, comb->type);; |
73f30c63 ZD |
72 | } |
73 | ||
74 | /* Sets COMB to single element ELT. */ | |
75 | ||
76 | void | |
77 | aff_combination_elt (aff_tree *comb, tree type, tree elt) | |
78 | { | |
79 | aff_combination_zero (comb, type); | |
80 | ||
81 | comb->n = 1; | |
82 | comb->elts[0].val = elt; | |
807e902e | 83 | comb->elts[0].coef = 1; |
73f30c63 ZD |
84 | } |
85 | ||
86 | /* Scales COMB by SCALE. */ | |
87 | ||
88 | void | |
807e902e | 89 | aff_combination_scale (aff_tree *comb, const widest_int &scale_in) |
73f30c63 ZD |
90 | { |
91 | unsigned i, j; | |
92 | ||
5291ab73 | 93 | widest_int scale = wide_int_ext_for_comb (scale_in, comb->type); |
807e902e | 94 | if (scale == 1) |
73f30c63 ZD |
95 | return; |
96 | ||
807e902e | 97 | if (scale == 0) |
73f30c63 ZD |
98 | { |
99 | aff_combination_zero (comb, comb->type); | |
100 | return; | |
101 | } | |
102 | ||
5291ab73 | 103 | comb->offset = wide_int_ext_for_comb (scale * comb->offset, comb->type); |
73f30c63 ZD |
104 | for (i = 0, j = 0; i < comb->n; i++) |
105 | { | |
807e902e | 106 | widest_int new_coef |
5291ab73 | 107 | = wide_int_ext_for_comb (scale * comb->elts[i].coef, comb->type); |
73f30c63 ZD |
108 | /* A coefficient may become zero due to overflow. Remove the zero |
109 | elements. */ | |
807e902e | 110 | if (new_coef == 0) |
73f30c63 ZD |
111 | continue; |
112 | comb->elts[j].coef = new_coef; | |
113 | comb->elts[j].val = comb->elts[i].val; | |
114 | j++; | |
115 | } | |
116 | comb->n = j; | |
117 | ||
118 | if (comb->rest) | |
119 | { | |
5c24ddaf AP |
120 | tree type = comb->type; |
121 | if (POINTER_TYPE_P (type)) | |
122 | type = sizetype; | |
73f30c63 ZD |
123 | if (comb->n < MAX_AFF_ELTS) |
124 | { | |
125 | comb->elts[comb->n].coef = scale; | |
126 | comb->elts[comb->n].val = comb->rest; | |
127 | comb->rest = NULL_TREE; | |
128 | comb->n++; | |
129 | } | |
130 | else | |
b8698a0f | 131 | comb->rest = fold_build2 (MULT_EXPR, type, comb->rest, |
807e902e | 132 | wide_int_to_tree (type, scale)); |
73f30c63 ZD |
133 | } |
134 | } | |
135 | ||
136 | /* Adds ELT * SCALE to COMB. */ | |
137 | ||
138 | void | |
807e902e | 139 | aff_combination_add_elt (aff_tree *comb, tree elt, const widest_int &scale_in) |
73f30c63 ZD |
140 | { |
141 | unsigned i; | |
f46fe0e6 | 142 | tree type; |
73f30c63 | 143 | |
5291ab73 | 144 | widest_int scale = wide_int_ext_for_comb (scale_in, comb->type); |
807e902e | 145 | if (scale == 0) |
73f30c63 ZD |
146 | return; |
147 | ||
148 | for (i = 0; i < comb->n; i++) | |
149 | if (operand_equal_p (comb->elts[i].val, elt, 0)) | |
150 | { | |
807e902e | 151 | widest_int new_coef |
5291ab73 | 152 | = wide_int_ext_for_comb (comb->elts[i].coef + scale, comb->type); |
807e902e | 153 | if (new_coef != 0) |
73f30c63 ZD |
154 | { |
155 | comb->elts[i].coef = new_coef; | |
156 | return; | |
157 | } | |
158 | ||
159 | comb->n--; | |
160 | comb->elts[i] = comb->elts[comb->n]; | |
161 | ||
162 | if (comb->rest) | |
163 | { | |
164 | gcc_assert (comb->n == MAX_AFF_ELTS - 1); | |
807e902e | 165 | comb->elts[comb->n].coef = 1; |
73f30c63 ZD |
166 | comb->elts[comb->n].val = comb->rest; |
167 | comb->rest = NULL_TREE; | |
168 | comb->n++; | |
169 | } | |
170 | return; | |
171 | } | |
172 | if (comb->n < MAX_AFF_ELTS) | |
173 | { | |
174 | comb->elts[comb->n].coef = scale; | |
175 | comb->elts[comb->n].val = elt; | |
176 | comb->n++; | |
177 | return; | |
178 | } | |
179 | ||
f46fe0e6 AP |
180 | type = comb->type; |
181 | if (POINTER_TYPE_P (type)) | |
182 | type = sizetype; | |
183 | ||
807e902e | 184 | if (scale == 1) |
f46fe0e6 | 185 | elt = fold_convert (type, elt); |
73f30c63 | 186 | else |
f46fe0e6 AP |
187 | elt = fold_build2 (MULT_EXPR, type, |
188 | fold_convert (type, elt), | |
807e902e | 189 | wide_int_to_tree (type, scale)); |
73f30c63 ZD |
190 | |
191 | if (comb->rest) | |
5c24ddaf AP |
192 | comb->rest = fold_build2 (PLUS_EXPR, type, comb->rest, |
193 | elt); | |
73f30c63 ZD |
194 | else |
195 | comb->rest = elt; | |
196 | } | |
197 | ||
7e2ac86c ZD |
198 | /* Adds CST to C. */ |
199 | ||
200 | static void | |
cc8bea09 | 201 | aff_combination_add_cst (aff_tree *c, const poly_widest_int &cst) |
7e2ac86c | 202 | { |
5291ab73 | 203 | c->offset = wide_int_ext_for_comb (c->offset + cst, c->type); |
7e2ac86c ZD |
204 | } |
205 | ||
73f30c63 ZD |
206 | /* Adds COMB2 to COMB1. */ |
207 | ||
208 | void | |
209 | aff_combination_add (aff_tree *comb1, aff_tree *comb2) | |
210 | { | |
211 | unsigned i; | |
212 | ||
7e2ac86c | 213 | aff_combination_add_cst (comb1, comb2->offset); |
73f30c63 ZD |
214 | for (i = 0; i < comb2->n; i++) |
215 | aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef); | |
216 | if (comb2->rest) | |
807e902e | 217 | aff_combination_add_elt (comb1, comb2->rest, 1); |
73f30c63 ZD |
218 | } |
219 | ||
220 | /* Converts affine combination COMB to TYPE. */ | |
221 | ||
222 | void | |
223 | aff_combination_convert (aff_tree *comb, tree type) | |
224 | { | |
225 | unsigned i, j; | |
226 | tree comb_type = comb->type; | |
227 | ||
7e2ac86c ZD |
228 | if (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type)) |
229 | { | |
230 | tree val = fold_convert (type, aff_combination_to_tree (comb)); | |
231 | tree_to_aff_combination (val, type, comb); | |
232 | return; | |
233 | } | |
234 | ||
73f30c63 | 235 | comb->type = type; |
5c24ddaf | 236 | if (comb->rest && !POINTER_TYPE_P (type)) |
73f30c63 ZD |
237 | comb->rest = fold_convert (type, comb->rest); |
238 | ||
239 | if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type)) | |
240 | return; | |
241 | ||
5291ab73 | 242 | comb->offset = wide_int_ext_for_comb (comb->offset, comb->type); |
73f30c63 ZD |
243 | for (i = j = 0; i < comb->n; i++) |
244 | { | |
807e902e | 245 | if (comb->elts[i].coef == 0) |
73f30c63 | 246 | continue; |
807e902e | 247 | comb->elts[j].coef = comb->elts[i].coef; |
73f30c63 ZD |
248 | comb->elts[j].val = fold_convert (type, comb->elts[i].val); |
249 | j++; | |
250 | } | |
251 | ||
252 | comb->n = j; | |
253 | if (comb->n < MAX_AFF_ELTS && comb->rest) | |
254 | { | |
807e902e | 255 | comb->elts[comb->n].coef = 1; |
73f30c63 ZD |
256 | comb->elts[comb->n].val = comb->rest; |
257 | comb->rest = NULL_TREE; | |
258 | comb->n++; | |
259 | } | |
260 | } | |
261 | ||
5120e0d8 RB |
262 | /* Tries to handle OP0 CODE OP1 as affine combination of parts. Returns |
263 | true when that was successful and returns the combination in COMB. */ | |
73f30c63 | 264 | |
5120e0d8 RB |
265 | static bool |
266 | expr_to_aff_combination (aff_tree *comb, tree_code code, tree type, | |
267 | tree op0, tree op1 = NULL_TREE) | |
73f30c63 ZD |
268 | { |
269 | aff_tree tmp; | |
f37fac2b | 270 | poly_int64 bitpos, bitsize, bytepos; |
73f30c63 | 271 | |
73f30c63 ZD |
272 | switch (code) |
273 | { | |
5be014d5 | 274 | case POINTER_PLUS_EXPR: |
5120e0d8 RB |
275 | tree_to_aff_combination (op0, type, comb); |
276 | tree_to_aff_combination (op1, sizetype, &tmp); | |
5be014d5 | 277 | aff_combination_add (comb, &tmp); |
5120e0d8 | 278 | return true; |
5be014d5 | 279 | |
73f30c63 ZD |
280 | case PLUS_EXPR: |
281 | case MINUS_EXPR: | |
5120e0d8 RB |
282 | tree_to_aff_combination (op0, type, comb); |
283 | tree_to_aff_combination (op1, type, &tmp); | |
73f30c63 | 284 | if (code == MINUS_EXPR) |
807e902e | 285 | aff_combination_scale (&tmp, -1); |
73f30c63 | 286 | aff_combination_add (comb, &tmp); |
5120e0d8 | 287 | return true; |
73f30c63 ZD |
288 | |
289 | case MULT_EXPR: | |
5120e0d8 | 290 | if (TREE_CODE (op1) != INTEGER_CST) |
73f30c63 | 291 | break; |
5120e0d8 RB |
292 | tree_to_aff_combination (op0, type, comb); |
293 | aff_combination_scale (comb, wi::to_widest (op1)); | |
294 | return true; | |
73f30c63 ZD |
295 | |
296 | case NEGATE_EXPR: | |
5120e0d8 | 297 | tree_to_aff_combination (op0, type, comb); |
807e902e | 298 | aff_combination_scale (comb, -1); |
5120e0d8 | 299 | return true; |
73f30c63 | 300 | |
7e2ac86c ZD |
301 | case BIT_NOT_EXPR: |
302 | /* ~x = -x - 1 */ | |
5120e0d8 | 303 | tree_to_aff_combination (op0, type, comb); |
807e902e KZ |
304 | aff_combination_scale (comb, -1); |
305 | aff_combination_add_cst (comb, -1); | |
5120e0d8 | 306 | return true; |
73f30c63 | 307 | |
1b92ccde BC |
308 | CASE_CONVERT: |
309 | { | |
5120e0d8 RB |
310 | tree otype = type; |
311 | tree inner = op0; | |
1b92ccde BC |
312 | tree itype = TREE_TYPE (inner); |
313 | enum tree_code icode = TREE_CODE (inner); | |
314 | ||
5120e0d8 RB |
315 | /* STRIP_NOPS */ |
316 | if (tree_nop_conversion_p (otype, itype)) | |
317 | { | |
318 | tree_to_aff_combination (op0, type, comb); | |
319 | return true; | |
320 | } | |
321 | ||
1b92ccde BC |
322 | /* In principle this is a valid folding, but it isn't necessarily |
323 | an optimization, so do it here and not in fold_unary. */ | |
324 | if ((icode == PLUS_EXPR || icode == MINUS_EXPR || icode == MULT_EXPR) | |
325 | && TREE_CODE (itype) == INTEGER_TYPE | |
326 | && TREE_CODE (otype) == INTEGER_TYPE | |
8813f50d | 327 | && TYPE_PRECISION (otype) > TYPE_PRECISION (itype)) |
1b92ccde | 328 | { |
8813f50d BC |
329 | tree op0 = TREE_OPERAND (inner, 0), op1 = TREE_OPERAND (inner, 1); |
330 | ||
331 | /* If inner type has undefined overflow behavior, fold conversion | |
332 | for below two cases: | |
333 | (T1)(X *+- CST) -> (T1)X *+- (T1)CST | |
334 | (T1)(X + X) -> (T1)X + (T1)X. */ | |
335 | if (TYPE_OVERFLOW_UNDEFINED (itype) | |
336 | && (TREE_CODE (op1) == INTEGER_CST | |
337 | || (icode == PLUS_EXPR && operand_equal_p (op0, op1, 0)))) | |
338 | { | |
339 | op0 = fold_convert (otype, op0); | |
340 | op1 = fold_convert (otype, op1); | |
5120e0d8 | 341 | return expr_to_aff_combination (comb, icode, otype, op0, op1); |
8813f50d | 342 | } |
ba00284c BC |
343 | wide_int minv, maxv; |
344 | /* If inner type has wrapping overflow behavior, fold conversion | |
345 | for below case: | |
0447929f XL |
346 | (T1)(X *+- CST) -> (T1)X *+- (T1)CST |
347 | if X *+- CST doesn't overflow by range information. */ | |
ba00284c BC |
348 | if (TYPE_UNSIGNED (itype) |
349 | && TYPE_OVERFLOW_WRAPS (itype) | |
ba00284c | 350 | && TREE_CODE (op1) == INTEGER_CST |
0447929f | 351 | && determine_value_range (op0, &minv, &maxv) == VR_RANGE) |
ba00284c | 352 | { |
0447929f XL |
353 | wi::overflow_type overflow = wi::OVF_NONE; |
354 | signop sign = UNSIGNED; | |
ba00284c | 355 | if (icode == PLUS_EXPR) |
0447929f XL |
356 | wi::add (maxv, wi::to_wide (op1), sign, &overflow); |
357 | else if (icode == MULT_EXPR) | |
358 | wi::mul (maxv, wi::to_wide (op1), sign, &overflow); | |
359 | else | |
360 | wi::sub (minv, wi::to_wide (op1), sign, &overflow); | |
361 | ||
362 | if (overflow == wi::OVF_NONE) | |
ba00284c BC |
363 | { |
364 | op0 = fold_convert (otype, op0); | |
365 | op1 = fold_convert (otype, op1); | |
0447929f XL |
366 | return expr_to_aff_combination (comb, icode, otype, op0, |
367 | op1); | |
ba00284c BC |
368 | } |
369 | } | |
1b92ccde BC |
370 | } |
371 | } | |
372 | break; | |
373 | ||
5120e0d8 RB |
374 | default:; |
375 | } | |
376 | ||
377 | return false; | |
378 | } | |
379 | ||
380 | /* Splits EXPR into an affine combination of parts. */ | |
381 | ||
382 | void | |
383 | tree_to_aff_combination (tree expr, tree type, aff_tree *comb) | |
384 | { | |
385 | aff_tree tmp; | |
386 | enum tree_code code; | |
387 | tree core, toffset; | |
388 | poly_int64 bitpos, bitsize, bytepos; | |
389 | machine_mode mode; | |
390 | int unsignedp, reversep, volatilep; | |
391 | ||
392 | STRIP_NOPS (expr); | |
393 | ||
394 | code = TREE_CODE (expr); | |
395 | switch (code) | |
396 | { | |
397 | case POINTER_PLUS_EXPR: | |
398 | case PLUS_EXPR: | |
399 | case MINUS_EXPR: | |
400 | case MULT_EXPR: | |
401 | if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0), | |
402 | TREE_OPERAND (expr, 1))) | |
403 | return; | |
404 | break; | |
405 | ||
406 | case NEGATE_EXPR: | |
407 | case BIT_NOT_EXPR: | |
408 | if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0))) | |
409 | return; | |
410 | break; | |
411 | ||
412 | CASE_CONVERT: | |
413 | /* ??? TREE_TYPE (expr) should be equal to type here, but IVOPTS | |
414 | calls this with not showing an outer widening cast. */ | |
415 | if (expr_to_aff_combination (comb, code, | |
416 | TREE_TYPE (expr), TREE_OPERAND (expr, 0))) | |
417 | { | |
418 | aff_combination_convert (comb, type); | |
419 | return; | |
420 | } | |
421 | break; | |
422 | ||
423 | case ADDR_EXPR: | |
424 | /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */ | |
425 | if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF) | |
426 | { | |
427 | expr = TREE_OPERAND (expr, 0); | |
428 | tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); | |
429 | tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp); | |
430 | aff_combination_add (comb, &tmp); | |
431 | return; | |
432 | } | |
433 | core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos, | |
434 | &toffset, &mode, &unsignedp, &reversep, | |
435 | &volatilep); | |
436 | if (!multiple_p (bitpos, BITS_PER_UNIT, &bytepos)) | |
437 | break; | |
438 | aff_combination_const (comb, type, bytepos); | |
439 | if (TREE_CODE (core) == MEM_REF) | |
440 | { | |
441 | tree mem_offset = TREE_OPERAND (core, 1); | |
442 | aff_combination_add_cst (comb, wi::to_poly_widest (mem_offset)); | |
443 | core = TREE_OPERAND (core, 0); | |
444 | } | |
445 | else | |
446 | core = build_fold_addr_expr (core); | |
447 | ||
448 | if (TREE_CODE (core) == ADDR_EXPR) | |
449 | aff_combination_add_elt (comb, core, 1); | |
450 | else | |
451 | { | |
452 | tree_to_aff_combination (core, type, &tmp); | |
453 | aff_combination_add (comb, &tmp); | |
454 | } | |
455 | if (toffset) | |
456 | { | |
457 | tree_to_aff_combination (toffset, type, &tmp); | |
458 | aff_combination_add (comb, &tmp); | |
459 | } | |
460 | return; | |
461 | ||
73f30c63 | 462 | default: |
cc8bea09 RS |
463 | { |
464 | if (poly_int_tree_p (expr)) | |
465 | { | |
466 | aff_combination_const (comb, type, wi::to_poly_widest (expr)); | |
467 | return; | |
468 | } | |
469 | break; | |
470 | } | |
73f30c63 ZD |
471 | } |
472 | ||
473 | aff_combination_elt (comb, type, expr); | |
474 | } | |
475 | ||
476 | /* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine | |
477 | combination COMB. */ | |
478 | ||
479 | static tree | |
5291ab73 | 480 | add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in) |
73f30c63 ZD |
481 | { |
482 | enum tree_code code; | |
483 | ||
5291ab73 | 484 | widest_int scale = wide_int_ext_for_comb (scale_in, type); |
78de2333 | 485 | |
aac69a62 | 486 | elt = fold_convert (type, elt); |
807e902e | 487 | if (scale == 1) |
73f30c63 ZD |
488 | { |
489 | if (!expr) | |
aac69a62 | 490 | return elt; |
78de2333 | 491 | |
aac69a62 | 492 | return fold_build2 (PLUS_EXPR, type, expr, elt); |
73f30c63 ZD |
493 | } |
494 | ||
807e902e | 495 | if (scale == -1) |
73f30c63 ZD |
496 | { |
497 | if (!expr) | |
aac69a62 | 498 | return fold_build1 (NEGATE_EXPR, type, elt); |
78de2333 | 499 | |
aac69a62 | 500 | return fold_build2 (MINUS_EXPR, type, expr, elt); |
73f30c63 ZD |
501 | } |
502 | ||
503 | if (!expr) | |
aac69a62 | 504 | return fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale)); |
73f30c63 | 505 | |
807e902e | 506 | if (wi::neg_p (scale)) |
73f30c63 ZD |
507 | { |
508 | code = MINUS_EXPR; | |
27bcd47c | 509 | scale = -scale; |
73f30c63 ZD |
510 | } |
511 | else | |
512 | code = PLUS_EXPR; | |
513 | ||
aac69a62 BC |
514 | elt = fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale)); |
515 | return fold_build2 (code, type, expr, elt); | |
73f30c63 ZD |
516 | } |
517 | ||
518 | /* Makes tree from the affine combination COMB. */ | |
519 | ||
520 | tree | |
521 | aff_combination_to_tree (aff_tree *comb) | |
522 | { | |
aac69a62 | 523 | tree type = comb->type, base = NULL_TREE, expr = NULL_TREE; |
73f30c63 | 524 | unsigned i; |
cc8bea09 RS |
525 | poly_widest_int off; |
526 | int sgn; | |
73f30c63 ZD |
527 | |
528 | gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE); | |
529 | ||
aac69a62 BC |
530 | i = 0; |
531 | if (POINTER_TYPE_P (type)) | |
532 | { | |
533 | type = sizetype; | |
534 | if (comb->n > 0 && comb->elts[0].coef == 1 | |
535 | && POINTER_TYPE_P (TREE_TYPE (comb->elts[0].val))) | |
536 | { | |
537 | base = comb->elts[0].val; | |
538 | ++i; | |
539 | } | |
540 | } | |
541 | ||
542 | for (; i < comb->n; i++) | |
5291ab73 | 543 | expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef); |
73f30c63 | 544 | |
6df588cb | 545 | if (comb->rest) |
5291ab73 | 546 | expr = add_elt_to_tree (expr, type, comb->rest, 1); |
6df588cb | 547 | |
73f30c63 ZD |
548 | /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is |
549 | unsigned. */ | |
cc8bea09 | 550 | if (known_lt (comb->offset, 0)) |
73f30c63 | 551 | { |
27bcd47c | 552 | off = -comb->offset; |
807e902e | 553 | sgn = -1; |
73f30c63 ZD |
554 | } |
555 | else | |
556 | { | |
557 | off = comb->offset; | |
807e902e | 558 | sgn = 1; |
73f30c63 | 559 | } |
aac69a62 BC |
560 | expr = add_elt_to_tree (expr, type, wide_int_to_tree (type, off), sgn); |
561 | ||
562 | if (base) | |
563 | return fold_build_pointer_plus (base, expr); | |
564 | else | |
565 | return fold_convert (comb->type, expr); | |
73f30c63 ZD |
566 | } |
567 | ||
568 | /* Copies the tree elements of COMB to ensure that they are not shared. */ | |
569 | ||
570 | void | |
571 | unshare_aff_combination (aff_tree *comb) | |
572 | { | |
573 | unsigned i; | |
574 | ||
575 | for (i = 0; i < comb->n; i++) | |
576 | comb->elts[i].val = unshare_expr (comb->elts[i].val); | |
577 | if (comb->rest) | |
578 | comb->rest = unshare_expr (comb->rest); | |
579 | } | |
580 | ||
581 | /* Remove M-th element from COMB. */ | |
582 | ||
583 | void | |
584 | aff_combination_remove_elt (aff_tree *comb, unsigned m) | |
585 | { | |
586 | comb->n--; | |
587 | if (m <= comb->n) | |
588 | comb->elts[m] = comb->elts[comb->n]; | |
589 | if (comb->rest) | |
590 | { | |
807e902e | 591 | comb->elts[comb->n].coef = 1; |
73f30c63 ZD |
592 | comb->elts[comb->n].val = comb->rest; |
593 | comb->rest = NULL_TREE; | |
594 | comb->n++; | |
595 | } | |
596 | } | |
7e2ac86c ZD |
597 | |
598 | /* Adds C * COEF * VAL to R. VAL may be NULL, in that case only | |
599 | C * COEF is added to R. */ | |
b8698a0f | 600 | |
7e2ac86c ZD |
601 | |
602 | static void | |
807e902e | 603 | aff_combination_add_product (aff_tree *c, const widest_int &coef, tree val, |
7e2ac86c ZD |
604 | aff_tree *r) |
605 | { | |
606 | unsigned i; | |
607 | tree aval, type; | |
608 | ||
609 | for (i = 0; i < c->n; i++) | |
610 | { | |
611 | aval = c->elts[i].val; | |
612 | if (val) | |
613 | { | |
614 | type = TREE_TYPE (aval); | |
615 | aval = fold_build2 (MULT_EXPR, type, aval, | |
616 | fold_convert (type, val)); | |
617 | } | |
618 | ||
27bcd47c | 619 | aff_combination_add_elt (r, aval, coef * c->elts[i].coef); |
7e2ac86c ZD |
620 | } |
621 | ||
622 | if (c->rest) | |
623 | { | |
624 | aval = c->rest; | |
625 | if (val) | |
626 | { | |
627 | type = TREE_TYPE (aval); | |
628 | aval = fold_build2 (MULT_EXPR, type, aval, | |
629 | fold_convert (type, val)); | |
630 | } | |
631 | ||
632 | aff_combination_add_elt (r, aval, coef); | |
633 | } | |
634 | ||
635 | if (val) | |
cc8bea09 RS |
636 | { |
637 | if (c->offset.is_constant ()) | |
638 | /* Access coeffs[0] directly, for efficiency. */ | |
639 | aff_combination_add_elt (r, val, coef * c->offset.coeffs[0]); | |
640 | else | |
641 | { | |
642 | /* c->offset is polynomial, so multiply VAL rather than COEF | |
643 | by it. */ | |
644 | tree offset = wide_int_to_tree (TREE_TYPE (val), c->offset); | |
645 | val = fold_build2 (MULT_EXPR, TREE_TYPE (val), val, offset); | |
646 | aff_combination_add_elt (r, val, coef); | |
647 | } | |
648 | } | |
7e2ac86c | 649 | else |
27bcd47c | 650 | aff_combination_add_cst (r, coef * c->offset); |
7e2ac86c ZD |
651 | } |
652 | ||
653 | /* Multiplies C1 by C2, storing the result to R */ | |
654 | ||
655 | void | |
656 | aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r) | |
657 | { | |
658 | unsigned i; | |
659 | gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type)); | |
660 | ||
661 | aff_combination_zero (r, c1->type); | |
662 | ||
663 | for (i = 0; i < c2->n; i++) | |
664 | aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r); | |
665 | if (c2->rest) | |
807e902e | 666 | aff_combination_add_product (c1, 1, c2->rest, r); |
cc8bea09 RS |
667 | if (c2->offset.is_constant ()) |
668 | /* Access coeffs[0] directly, for efficiency. */ | |
669 | aff_combination_add_product (c1, c2->offset.coeffs[0], NULL, r); | |
670 | else | |
671 | { | |
672 | /* c2->offset is polynomial, so do the multiplication in tree form. */ | |
673 | tree offset = wide_int_to_tree (c2->type, c2->offset); | |
674 | aff_combination_add_product (c1, 1, offset, r); | |
675 | } | |
7e2ac86c | 676 | } |
bbc8a8dc ZD |
677 | |
678 | /* Returns the element of COMB whose value is VAL, or NULL if no such | |
679 | element exists. If IDX is not NULL, it is set to the index of VAL in | |
680 | COMB. */ | |
b8698a0f | 681 | |
99b1c316 | 682 | static class aff_comb_elt * |
bbc8a8dc ZD |
683 | aff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx) |
684 | { | |
685 | unsigned i; | |
686 | ||
687 | for (i = 0; i < comb->n; i++) | |
688 | if (operand_equal_p (comb->elts[i].val, val, 0)) | |
689 | { | |
690 | if (idx) | |
691 | *idx = i; | |
692 | ||
693 | return &comb->elts[i]; | |
694 | } | |
695 | ||
696 | return NULL; | |
697 | } | |
698 | ||
699 | /* Element of the cache that maps ssa name NAME to its expanded form | |
700 | as an affine expression EXPANSION. */ | |
701 | ||
6c1dae73 | 702 | class name_expansion |
bbc8a8dc | 703 | { |
6c1dae73 | 704 | public: |
bbc8a8dc ZD |
705 | aff_tree expansion; |
706 | ||
707 | /* True if the expansion for the name is just being generated. */ | |
708 | unsigned in_progress : 1; | |
709 | }; | |
710 | ||
72425608 ZD |
711 | /* Expands SSA names in COMB recursively. CACHE is used to cache the |
712 | results. */ | |
bbc8a8dc ZD |
713 | |
714 | void | |
726a989a | 715 | aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED, |
39c8aaa4 | 716 | hash_map<tree, name_expansion *> **cache) |
bbc8a8dc ZD |
717 | { |
718 | unsigned i; | |
719 | aff_tree to_add, current, curre; | |
5120e0d8 | 720 | tree e; |
355fe088 | 721 | gimple *def; |
807e902e | 722 | widest_int scale; |
99b1c316 | 723 | class name_expansion *exp; |
bbc8a8dc | 724 | |
72425608 | 725 | aff_combination_zero (&to_add, comb->type); |
bbc8a8dc ZD |
726 | for (i = 0; i < comb->n; i++) |
727 | { | |
e544c850 | 728 | tree type, name; |
726a989a RB |
729 | enum tree_code code; |
730 | ||
bbc8a8dc | 731 | e = comb->elts[i].val; |
e544c850 RG |
732 | type = TREE_TYPE (e); |
733 | name = e; | |
734 | /* Look through some conversions. */ | |
625a9766 | 735 | if (CONVERT_EXPR_P (e) |
e544c850 RG |
736 | && (TYPE_PRECISION (type) |
737 | >= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (e, 0))))) | |
738 | name = TREE_OPERAND (e, 0); | |
739 | if (TREE_CODE (name) != SSA_NAME) | |
bbc8a8dc | 740 | continue; |
e544c850 | 741 | def = SSA_NAME_DEF_STMT (name); |
726a989a | 742 | if (!is_gimple_assign (def) || gimple_assign_lhs (def) != name) |
bbc8a8dc ZD |
743 | continue; |
744 | ||
726a989a RB |
745 | code = gimple_assign_rhs_code (def); |
746 | if (code != SSA_NAME | |
747 | && !IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)) | |
748 | && (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS | |
749 | || !is_gimple_min_invariant (gimple_assign_rhs1 (def)))) | |
bbc8a8dc ZD |
750 | continue; |
751 | ||
752 | /* We do not know whether the reference retains its value at the | |
753 | place where the expansion is used. */ | |
726a989a | 754 | if (TREE_CODE_CLASS (code) == tcc_reference) |
bbc8a8dc ZD |
755 | continue; |
756 | ||
e5840e75 RB |
757 | name_expansion **slot = NULL; |
758 | if (*cache) | |
759 | slot = (*cache)->get (name); | |
760 | exp = slot ? *slot : NULL; | |
bbc8a8dc ZD |
761 | if (!exp) |
762 | { | |
e5840e75 RB |
763 | /* Only bother to handle cases tree_to_aff_combination will. */ |
764 | switch (code) | |
765 | { | |
766 | case POINTER_PLUS_EXPR: | |
767 | case PLUS_EXPR: | |
768 | case MINUS_EXPR: | |
769 | case MULT_EXPR: | |
5120e0d8 RB |
770 | if (!expr_to_aff_combination (¤t, code, TREE_TYPE (name), |
771 | gimple_assign_rhs1 (def), | |
772 | gimple_assign_rhs2 (def))) | |
773 | continue; | |
774 | break; | |
e5840e75 RB |
775 | case NEGATE_EXPR: |
776 | case BIT_NOT_EXPR: | |
5120e0d8 RB |
777 | if (!expr_to_aff_combination (¤t, code, TREE_TYPE (name), |
778 | gimple_assign_rhs1 (def))) | |
779 | continue; | |
780 | break; | |
e5840e75 | 781 | CASE_CONVERT: |
5120e0d8 RB |
782 | if (!expr_to_aff_combination (¤t, code, TREE_TYPE (name), |
783 | gimple_assign_rhs1 (def))) | |
784 | /* This makes us always expand conversions which we did | |
785 | in the past and makes gcc.dg/tree-ssa/ivopts-lt-2.c | |
786 | PASS, eliminating one induction variable in IVOPTs. | |
787 | ??? But it is really excessive and we should try | |
788 | harder to do without it. */ | |
789 | aff_combination_elt (¤t, TREE_TYPE (name), | |
790 | fold_convert (TREE_TYPE (name), | |
791 | gimple_assign_rhs1 (def))); | |
e5840e75 RB |
792 | break; |
793 | case ADDR_EXPR: | |
794 | case INTEGER_CST: | |
795 | case POLY_INT_CST: | |
5120e0d8 RB |
796 | tree_to_aff_combination (gimple_assign_rhs1 (def), |
797 | TREE_TYPE (name), ¤t); | |
e5840e75 RB |
798 | break; |
799 | default: | |
800 | continue; | |
801 | } | |
99b1c316 | 802 | exp = XNEW (class name_expansion); |
bbc8a8dc | 803 | exp->in_progress = 1; |
e5840e75 RB |
804 | if (!*cache) |
805 | *cache = new hash_map<tree, name_expansion *>; | |
806 | (*cache)->put (name, exp); | |
807 | aff_combination_expand (¤t, cache); | |
bbc8a8dc ZD |
808 | exp->expansion = current; |
809 | exp->in_progress = 0; | |
810 | } | |
811 | else | |
812 | { | |
813 | /* Since we follow the definitions in the SSA form, we should not | |
814 | enter a cycle unless we pass through a phi node. */ | |
815 | gcc_assert (!exp->in_progress); | |
816 | current = exp->expansion; | |
817 | } | |
e5840e75 RB |
818 | if (!useless_type_conversion_p (comb->type, current.type)) |
819 | aff_combination_convert (¤t, comb->type); | |
bbc8a8dc ZD |
820 | |
821 | /* Accumulate the new terms to TO_ADD, so that we do not modify | |
822 | COMB while traversing it; include the term -coef * E, to remove | |
823 | it from COMB. */ | |
824 | scale = comb->elts[i].coef; | |
72425608 | 825 | aff_combination_zero (&curre, comb->type); |
27bcd47c | 826 | aff_combination_add_elt (&curre, e, -scale); |
bbc8a8dc ZD |
827 | aff_combination_scale (¤t, scale); |
828 | aff_combination_add (&to_add, ¤t); | |
829 | aff_combination_add (&to_add, &curre); | |
830 | } | |
831 | aff_combination_add (comb, &to_add); | |
832 | } | |
833 | ||
72425608 ZD |
834 | /* Similar to tree_to_aff_combination, but follows SSA name definitions |
835 | and expands them recursively. CACHE is used to cache the expansions | |
836 | of the ssa names, to avoid exponential time complexity for cases | |
837 | like | |
838 | ||
839 | a1 = a0 + a0; | |
840 | a2 = a1 + a1; | |
841 | a3 = a2 + a2; | |
842 | ... */ | |
843 | ||
844 | void | |
845 | tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb, | |
39c8aaa4 | 846 | hash_map<tree, name_expansion *> **cache) |
72425608 ZD |
847 | { |
848 | tree_to_aff_combination (expr, type, comb); | |
849 | aff_combination_expand (comb, cache); | |
850 | } | |
851 | ||
bbc8a8dc | 852 | /* Frees memory occupied by struct name_expansion in *VALUE. Callback for |
39c8aaa4 | 853 | hash_map::traverse. */ |
bbc8a8dc | 854 | |
39c8aaa4 TS |
855 | bool |
856 | free_name_expansion (tree const &, name_expansion **value, void *) | |
bbc8a8dc | 857 | { |
39c8aaa4 | 858 | free (*value); |
bbc8a8dc ZD |
859 | return true; |
860 | } | |
861 | ||
862 | /* Frees memory allocated for the CACHE used by | |
863 | tree_to_aff_combination_expand. */ | |
864 | ||
865 | void | |
39c8aaa4 | 866 | free_affine_expand_cache (hash_map<tree, name_expansion *> **cache) |
bbc8a8dc ZD |
867 | { |
868 | if (!*cache) | |
869 | return; | |
870 | ||
39c8aaa4 TS |
871 | (*cache)->traverse<void *, free_name_expansion> (NULL); |
872 | delete (*cache); | |
bbc8a8dc ZD |
873 | *cache = NULL; |
874 | } | |
875 | ||
876 | /* If VAL != CST * DIV for any constant CST, returns false. | |
b03be25f RB |
877 | Otherwise, if *MULT_SET is true, additionally compares CST and MULT, |
878 | and if they are different, returns false. Finally, if neither of these | |
879 | two cases occur, true is returned, and CST is stored to MULT and MULT_SET | |
880 | is set to true. */ | |
bbc8a8dc ZD |
881 | |
882 | static bool | |
cc8bea09 RS |
883 | wide_int_constant_multiple_p (const poly_widest_int &val, |
884 | const poly_widest_int &div, | |
885 | bool *mult_set, poly_widest_int *mult) | |
bbc8a8dc | 886 | { |
cc8bea09 | 887 | poly_widest_int rem, cst; |
bbc8a8dc | 888 | |
cc8bea09 | 889 | if (known_eq (val, 0)) |
b03be25f | 890 | { |
cc8bea09 | 891 | if (*mult_set && maybe_ne (*mult, 0)) |
b03be25f RB |
892 | return false; |
893 | *mult_set = true; | |
807e902e | 894 | *mult = 0; |
b03be25f RB |
895 | return true; |
896 | } | |
bbc8a8dc | 897 | |
cc8bea09 | 898 | if (maybe_eq (div, 0)) |
bbc8a8dc ZD |
899 | return false; |
900 | ||
cc8bea09 | 901 | if (!multiple_p (val, div, &cst)) |
bbc8a8dc ZD |
902 | return false; |
903 | ||
cc8bea09 | 904 | if (*mult_set && maybe_ne (*mult, cst)) |
bbc8a8dc ZD |
905 | return false; |
906 | ||
907 | *mult_set = true; | |
908 | *mult = cst; | |
909 | return true; | |
910 | } | |
911 | ||
912 | /* Returns true if VAL = X * DIV for some constant X. If this is the case, | |
913 | X is stored to MULT. */ | |
914 | ||
915 | bool | |
916 | aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div, | |
cc8bea09 | 917 | poly_widest_int *mult) |
bbc8a8dc ZD |
918 | { |
919 | bool mult_set = false; | |
920 | unsigned i; | |
921 | ||
cc8bea09 | 922 | if (val->n == 0 && known_eq (val->offset, 0)) |
bbc8a8dc | 923 | { |
807e902e | 924 | *mult = 0; |
bbc8a8dc ZD |
925 | return true; |
926 | } | |
927 | if (val->n != div->n) | |
928 | return false; | |
929 | ||
930 | if (val->rest || div->rest) | |
931 | return false; | |
932 | ||
807e902e KZ |
933 | if (!wide_int_constant_multiple_p (val->offset, div->offset, |
934 | &mult_set, mult)) | |
bbc8a8dc ZD |
935 | return false; |
936 | ||
937 | for (i = 0; i < div->n; i++) | |
938 | { | |
99b1c316 | 939 | class aff_comb_elt *elt |
bbc8a8dc ZD |
940 | = aff_combination_find_elt (val, div->elts[i].val, NULL); |
941 | if (!elt) | |
942 | return false; | |
807e902e KZ |
943 | if (!wide_int_constant_multiple_p (elt->coef, div->elts[i].coef, |
944 | &mult_set, mult)) | |
bbc8a8dc ZD |
945 | return false; |
946 | } | |
947 | ||
948 | gcc_assert (mult_set); | |
949 | return true; | |
950 | } | |
ea336dd5 AP |
951 | |
952 | /* Prints the affine VAL to the FILE. */ | |
953 | ||
aeb83f09 | 954 | static void |
ea336dd5 AP |
955 | print_aff (FILE *file, aff_tree *val) |
956 | { | |
957 | unsigned i; | |
807e902e | 958 | signop sgn = TYPE_SIGN (val->type); |
ea336dd5 | 959 | if (POINTER_TYPE_P (val->type)) |
807e902e | 960 | sgn = SIGNED; |
ea336dd5 AP |
961 | fprintf (file, "{\n type = "); |
962 | print_generic_expr (file, val->type, TDF_VOPS|TDF_MEMSYMS); | |
963 | fprintf (file, "\n offset = "); | |
807e902e | 964 | print_dec (val->offset, file, sgn); |
ea336dd5 AP |
965 | if (val->n > 0) |
966 | { | |
967 | fprintf (file, "\n elements = {\n"); | |
968 | for (i = 0; i < val->n; i++) | |
969 | { | |
970 | fprintf (file, " [%d] = ", i); | |
971 | print_generic_expr (file, val->elts[i].val, TDF_VOPS|TDF_MEMSYMS); | |
b8698a0f | 972 | |
ea336dd5 | 973 | fprintf (file, " * "); |
807e902e | 974 | print_dec (val->elts[i].coef, file, sgn); |
ea336dd5 AP |
975 | if (i != val->n - 1) |
976 | fprintf (file, ", \n"); | |
977 | } | |
978 | fprintf (file, "\n }"); | |
979 | } | |
980 | if (val->rest) | |
981 | { | |
982 | fprintf (file, "\n rest = "); | |
983 | print_generic_expr (file, val->rest, TDF_VOPS|TDF_MEMSYMS); | |
984 | } | |
985 | fprintf (file, "\n}"); | |
986 | } | |
987 | ||
988 | /* Prints the affine VAL to the standard error, used for debugging. */ | |
989 | ||
24e47c76 | 990 | DEBUG_FUNCTION void |
ea336dd5 AP |
991 | debug_aff (aff_tree *val) |
992 | { | |
993 | print_aff (stderr, val); | |
994 | fprintf (stderr, "\n"); | |
995 | } | |
72425608 | 996 | |
be8c1c8c BC |
997 | /* Computes address of the reference REF in ADDR. The size of the accessed |
998 | location is stored to SIZE. Returns the ultimate containing object to | |
999 | which REF refers. */ | |
72425608 | 1000 | |
be8c1c8c | 1001 | tree |
a85d87b2 | 1002 | get_inner_reference_aff (tree ref, aff_tree *addr, poly_widest_int *size) |
72425608 | 1003 | { |
f37fac2b | 1004 | poly_int64 bitsize, bitpos; |
72425608 | 1005 | tree toff; |
ef4bddc2 | 1006 | machine_mode mode; |
ee45a32d | 1007 | int uns, rev, vol; |
72425608 ZD |
1008 | aff_tree tmp; |
1009 | tree base = get_inner_reference (ref, &bitsize, &bitpos, &toff, &mode, | |
25b75a48 | 1010 | &uns, &rev, &vol); |
72425608 ZD |
1011 | tree base_addr = build_fold_addr_expr (base); |
1012 | ||
1013 | /* ADDR = &BASE + TOFF + BITPOS / BITS_PER_UNIT. */ | |
1014 | ||
1015 | tree_to_aff_combination (base_addr, sizetype, addr); | |
1016 | ||
1017 | if (toff) | |
1018 | { | |
1019 | tree_to_aff_combination (toff, sizetype, &tmp); | |
1020 | aff_combination_add (addr, &tmp); | |
1021 | } | |
1022 | ||
f37fac2b | 1023 | aff_combination_const (&tmp, sizetype, bits_to_bytes_round_down (bitpos)); |
72425608 ZD |
1024 | aff_combination_add (addr, &tmp); |
1025 | ||
f37fac2b | 1026 | *size = bits_to_bytes_round_up (bitsize); |
be8c1c8c BC |
1027 | |
1028 | return base; | |
72425608 ZD |
1029 | } |
1030 | ||
02f5d6c5 RG |
1031 | /* Returns true if a region of size SIZE1 at position 0 and a region of |
1032 | size SIZE2 at position DIFF cannot overlap. */ | |
1033 | ||
1034 | bool | |
cc8bea09 RS |
1035 | aff_comb_cannot_overlap_p (aff_tree *diff, const poly_widest_int &size1, |
1036 | const poly_widest_int &size2) | |
02f5d6c5 | 1037 | { |
02f5d6c5 RG |
1038 | /* Unless the difference is a constant, we fail. */ |
1039 | if (diff->n != 0) | |
1040 | return false; | |
1041 | ||
cc8bea09 RS |
1042 | if (!ordered_p (diff->offset, 0)) |
1043 | return false; | |
1044 | ||
1045 | if (maybe_lt (diff->offset, 0)) | |
02f5d6c5 RG |
1046 | { |
1047 | /* The second object is before the first one, we succeed if the last | |
1048 | element of the second object is before the start of the first one. */ | |
cc8bea09 | 1049 | return known_le (diff->offset + size2, 0); |
02f5d6c5 RG |
1050 | } |
1051 | else | |
1052 | { | |
1053 | /* We succeed if the second object starts after the first one ends. */ | |
cc8bea09 | 1054 | return known_le (size1, diff->offset); |
02f5d6c5 RG |
1055 | } |
1056 | } | |
1057 |