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