tree-ssa-structalias.c revision 169689
1/* Tree based points-to analysis 2 Copyright (C) 2005, 2006 Free Software Foundation, Inc. 3 Contributed by Daniel Berlin <dberlin@dberlin.org> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 2 of the License, or 10(at your option) any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; if not, write to the Free Software 19Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 20*/ 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "tm.h" 26#include "ggc.h" 27#include "obstack.h" 28#include "bitmap.h" 29#include "flags.h" 30#include "rtl.h" 31#include "tm_p.h" 32#include "hard-reg-set.h" 33#include "basic-block.h" 34#include "output.h" 35#include "errors.h" 36#include "diagnostic.h" 37#include "tree.h" 38#include "c-common.h" 39#include "tree-flow.h" 40#include "tree-inline.h" 41#include "varray.h" 42#include "c-tree.h" 43#include "tree-gimple.h" 44#include "hashtab.h" 45#include "function.h" 46#include "cgraph.h" 47#include "tree-pass.h" 48#include "timevar.h" 49#include "alloc-pool.h" 50#include "splay-tree.h" 51#include "params.h" 52#include "tree-ssa-structalias.h" 53#include "cgraph.h" 54 55/* The idea behind this analyzer is to generate set constraints from the 56 program, then solve the resulting constraints in order to generate the 57 points-to sets. 58 59 Set constraints are a way of modeling program analysis problems that 60 involve sets. They consist of an inclusion constraint language, 61 describing the variables (each variable is a set) and operations that 62 are involved on the variables, and a set of rules that derive facts 63 from these operations. To solve a system of set constraints, you derive 64 all possible facts under the rules, which gives you the correct sets 65 as a consequence. 66 67 See "Efficient Field-sensitive pointer analysis for C" by "David 68 J. Pearce and Paul H. J. Kelly and Chris Hankin, at 69 http://citeseer.ist.psu.edu/pearce04efficient.html 70 71 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines 72 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at 73 http://citeseer.ist.psu.edu/heintze01ultrafast.html 74 75 There are three types of constraint expressions, DEREF, ADDRESSOF, and 76 SCALAR. Each constraint expression consists of a constraint type, 77 a variable, and an offset. 78 79 SCALAR is a constraint expression type used to represent x, whether 80 it appears on the LHS or the RHS of a statement. 81 DEREF is a constraint expression type used to represent *x, whether 82 it appears on the LHS or the RHS of a statement. 83 ADDRESSOF is a constraint expression used to represent &x, whether 84 it appears on the LHS or the RHS of a statement. 85 86 Each pointer variable in the program is assigned an integer id, and 87 each field of a structure variable is assigned an integer id as well. 88 89 Structure variables are linked to their list of fields through a "next 90 field" in each variable that points to the next field in offset 91 order. 92 Each variable for a structure field has 93 94 1. "size", that tells the size in bits of that field. 95 2. "fullsize, that tells the size in bits of the entire structure. 96 3. "offset", that tells the offset in bits from the beginning of the 97 structure to this field. 98 99 Thus, 100 struct f 101 { 102 int a; 103 int b; 104 } foo; 105 int *bar; 106 107 looks like 108 109 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b 110 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL 111 bar -> id 3, size 32, offset 0, fullsize 32, next NULL 112 113 114 In order to solve the system of set constraints, the following is 115 done: 116 117 1. Each constraint variable x has a solution set associated with it, 118 Sol(x). 119 120 2. Constraints are separated into direct, copy, and complex. 121 Direct constraints are ADDRESSOF constraints that require no extra 122 processing, such as P = &Q 123 Copy constraints are those of the form P = Q. 124 Complex constraints are all the constraints involving dereferences. 125 126 3. All direct constraints of the form P = &Q are processed, such 127 that Q is added to Sol(P) 128 129 4. All complex constraints for a given constraint variable are stored in a 130 linked list attached to that variable's node. 131 132 5. A directed graph is built out of the copy constraints. Each 133 constraint variable is a node in the graph, and an edge from 134 Q to P is added for each copy constraint of the form P = Q 135 136 6. The graph is then walked, and solution sets are 137 propagated along the copy edges, such that an edge from Q to P 138 causes Sol(P) <- Sol(P) union Sol(Q). 139 140 7. As we visit each node, all complex constraints associated with 141 that node are processed by adding appropriate copy edges to the graph, or the 142 appropriate variables to the solution set. 143 144 8. The process of walking the graph is iterated until no solution 145 sets change. 146 147 Prior to walking the graph in steps 6 and 7, We perform static 148 cycle elimination on the constraint graph, as well 149 as off-line variable substitution. 150 151 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted 152 on and turned into anything), but isn't. You can just see what offset 153 inside the pointed-to struct it's going to access. 154 155 TODO: Constant bounded arrays can be handled as if they were structs of the 156 same number of elements. 157 158 TODO: Modeling heap and incoming pointers becomes much better if we 159 add fields to them as we discover them, which we could do. 160 161 TODO: We could handle unions, but to be honest, it's probably not 162 worth the pain or slowdown. */ 163 164static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map))) 165htab_t heapvar_for_stmt; 166 167/* One variable to represent all non-local accesses. */ 168tree nonlocal_all; 169 170static bool use_field_sensitive = true; 171static int in_ipa_mode = 0; 172static bitmap_obstack predbitmap_obstack; 173static bitmap_obstack ptabitmap_obstack; 174static bitmap_obstack iteration_obstack; 175 176static unsigned int create_variable_info_for (tree, const char *); 177static void build_constraint_graph (void); 178 179DEF_VEC_P(constraint_t); 180DEF_VEC_ALLOC_P(constraint_t,heap); 181 182#define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \ 183 if (a) \ 184 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d) 185 186static struct constraint_stats 187{ 188 unsigned int total_vars; 189 unsigned int collapsed_vars; 190 unsigned int unified_vars_static; 191 unsigned int unified_vars_dynamic; 192 unsigned int iterations; 193 unsigned int num_edges; 194} stats; 195 196struct variable_info 197{ 198 /* ID of this variable */ 199 unsigned int id; 200 201 /* Name of this variable */ 202 const char *name; 203 204 /* Tree that this variable is associated with. */ 205 tree decl; 206 207 /* Offset of this variable, in bits, from the base variable */ 208 unsigned HOST_WIDE_INT offset; 209 210 /* Size of the variable, in bits. */ 211 unsigned HOST_WIDE_INT size; 212 213 /* Full size of the base variable, in bits. */ 214 unsigned HOST_WIDE_INT fullsize; 215 216 /* A link to the variable for the next field in this structure. */ 217 struct variable_info *next; 218 219 /* Node in the graph that represents the constraints and points-to 220 solution for the variable. */ 221 unsigned int node; 222 223 /* True if the address of this variable is taken. Needed for 224 variable substitution. */ 225 unsigned int address_taken:1; 226 227 /* True if this variable is the target of a dereference. Needed for 228 variable substitution. */ 229 unsigned int indirect_target:1; 230 231 /* True if the variable is directly the target of a dereference. 232 This is used to track which variables are *actually* dereferenced 233 so we can prune their points to listed. This is equivalent to the 234 indirect_target flag when no merging of variables happens. */ 235 unsigned int directly_dereferenced:1; 236 237 /* True if this is a variable created by the constraint analysis, such as 238 heap variables and constraints we had to break up. */ 239 unsigned int is_artificial_var:1; 240 241 /* True if this is a special variable whose solution set should not be 242 changed. */ 243 unsigned int is_special_var:1; 244 245 /* True for variables whose size is not known or variable. */ 246 unsigned int is_unknown_size_var:1; 247 248 /* True for variables that have unions somewhere in them. */ 249 unsigned int has_union:1; 250 251 /* True if this is a heap variable. */ 252 unsigned int is_heap_var:1; 253 254 /* Points-to set for this variable. */ 255 bitmap solution; 256 257 /* Variable ids represented by this node. */ 258 bitmap variables; 259 260 /* Vector of complex constraints for this node. Complex 261 constraints are those involving dereferences. */ 262 VEC(constraint_t,heap) *complex; 263 264 /* Variable id this was collapsed to due to type unsafety. 265 This should be unused completely after build_constraint_graph, or 266 something is broken. */ 267 struct variable_info *collapsed_to; 268}; 269typedef struct variable_info *varinfo_t; 270 271static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT); 272 273/* Pool of variable info structures. */ 274static alloc_pool variable_info_pool; 275 276DEF_VEC_P(varinfo_t); 277 278DEF_VEC_ALLOC_P(varinfo_t, heap); 279 280/* Table of variable info structures for constraint variables. Indexed directly 281 by variable info id. */ 282static VEC(varinfo_t,heap) *varmap; 283 284/* Return the varmap element N */ 285 286static inline varinfo_t 287get_varinfo (unsigned int n) 288{ 289 return VEC_index(varinfo_t, varmap, n); 290} 291 292/* Return the varmap element N, following the collapsed_to link. */ 293 294static inline varinfo_t 295get_varinfo_fc (unsigned int n) 296{ 297 varinfo_t v = VEC_index(varinfo_t, varmap, n); 298 299 if (v->collapsed_to) 300 return v->collapsed_to; 301 return v; 302} 303 304/* Variable that represents the unknown pointer. */ 305static varinfo_t var_anything; 306static tree anything_tree; 307static unsigned int anything_id; 308 309/* Variable that represents the NULL pointer. */ 310static varinfo_t var_nothing; 311static tree nothing_tree; 312static unsigned int nothing_id; 313 314/* Variable that represents read only memory. */ 315static varinfo_t var_readonly; 316static tree readonly_tree; 317static unsigned int readonly_id; 318 319/* Variable that represents integers. This is used for when people do things 320 like &0->a.b. */ 321static varinfo_t var_integer; 322static tree integer_tree; 323static unsigned int integer_id; 324 325/* Variable that represents escaped variables. This is used to give 326 incoming pointer variables a better set than ANYTHING. */ 327static varinfo_t var_escaped_vars; 328static tree escaped_vars_tree; 329static unsigned int escaped_vars_id; 330 331/* Variable that represents non-local variables before we expand it to 332 one for each type. */ 333static unsigned int nonlocal_vars_id; 334 335/* Lookup a heap var for FROM, and return it if we find one. */ 336 337static tree 338heapvar_lookup (tree from) 339{ 340 struct tree_map *h, in; 341 in.from = from; 342 343 h = htab_find_with_hash (heapvar_for_stmt, &in, htab_hash_pointer (from)); 344 if (h) 345 return h->to; 346 return NULL_TREE; 347} 348 349/* Insert a mapping FROM->TO in the heap var for statement 350 hashtable. */ 351 352static void 353heapvar_insert (tree from, tree to) 354{ 355 struct tree_map *h; 356 void **loc; 357 358 h = ggc_alloc (sizeof (struct tree_map)); 359 h->hash = htab_hash_pointer (from); 360 h->from = from; 361 h->to = to; 362 loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT); 363 *(struct tree_map **) loc = h; 364} 365 366/* Return a new variable info structure consisting for a variable 367 named NAME, and using constraint graph node NODE. */ 368 369static varinfo_t 370new_var_info (tree t, unsigned int id, const char *name, unsigned int node) 371{ 372 varinfo_t ret = pool_alloc (variable_info_pool); 373 374 ret->id = id; 375 ret->name = name; 376 ret->decl = t; 377 ret->node = node; 378 ret->address_taken = false; 379 ret->indirect_target = false; 380 ret->directly_dereferenced = false; 381 ret->is_artificial_var = false; 382 ret->is_heap_var = false; 383 ret->is_special_var = false; 384 ret->is_unknown_size_var = false; 385 ret->has_union = false; 386 ret->solution = BITMAP_ALLOC (&ptabitmap_obstack); 387 ret->variables = BITMAP_ALLOC (&ptabitmap_obstack); 388 ret->complex = NULL; 389 ret->next = NULL; 390 ret->collapsed_to = NULL; 391 return ret; 392} 393 394typedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type; 395 396/* An expression that appears in a constraint. */ 397 398struct constraint_expr 399{ 400 /* Constraint type. */ 401 constraint_expr_type type; 402 403 /* Variable we are referring to in the constraint. */ 404 unsigned int var; 405 406 /* Offset, in bits, of this constraint from the beginning of 407 variables it ends up referring to. 408 409 IOW, in a deref constraint, we would deref, get the result set, 410 then add OFFSET to each member. */ 411 unsigned HOST_WIDE_INT offset; 412}; 413 414typedef struct constraint_expr ce_s; 415DEF_VEC_O(ce_s); 416DEF_VEC_ALLOC_O(ce_s, heap); 417static void get_constraint_for (tree, VEC(ce_s, heap) **); 418static void do_deref (VEC (ce_s, heap) **); 419 420/* Our set constraints are made up of two constraint expressions, one 421 LHS, and one RHS. 422 423 As described in the introduction, our set constraints each represent an 424 operation between set valued variables. 425*/ 426struct constraint 427{ 428 struct constraint_expr lhs; 429 struct constraint_expr rhs; 430}; 431 432/* List of constraints that we use to build the constraint graph from. */ 433 434static VEC(constraint_t,heap) *constraints; 435static alloc_pool constraint_pool; 436 437/* An edge in the weighted constraint graph. The edges are weighted, 438 with a bit set in weights meaning their is an edge with that 439 weight. 440 We don't keep the src in the edge, because we always know what it 441 is. */ 442 443struct constraint_edge 444{ 445 unsigned int dest; 446 bitmap weights; 447}; 448 449typedef struct constraint_edge *constraint_edge_t; 450static alloc_pool constraint_edge_pool; 451 452/* Return a new constraint edge from SRC to DEST. */ 453 454static constraint_edge_t 455new_constraint_edge (unsigned int dest) 456{ 457 constraint_edge_t ret = pool_alloc (constraint_edge_pool); 458 ret->dest = dest; 459 ret->weights = NULL; 460 return ret; 461} 462 463DEF_VEC_P(constraint_edge_t); 464DEF_VEC_ALLOC_P(constraint_edge_t,heap); 465 466 467/* The constraint graph is represented internally in two different 468 ways. The overwhelming majority of edges in the constraint graph 469 are zero weigh edges, and thus, using a vector of contrainst_edge_t 470 is a waste of time and memory, since they have no weights. We 471 simply use a bitmap to store the preds and succs for each node. 472 The weighted edges are stored as a set of adjacency vectors, one 473 per variable. succs[x] is the vector of successors for variable x, 474 and preds[x] is the vector of predecessors for variable x. IOW, 475 all edges are "forward" edges, which is not like our CFG. So 476 remember that preds[x]->src == x, and succs[x]->src == x. */ 477 478struct constraint_graph 479{ 480 bitmap *zero_weight_succs; 481 bitmap *zero_weight_preds; 482 VEC(constraint_edge_t,heap) **succs; 483 VEC(constraint_edge_t,heap) **preds; 484}; 485 486typedef struct constraint_graph *constraint_graph_t; 487 488static constraint_graph_t graph; 489static int graph_size; 490 491/* Create a new constraint consisting of LHS and RHS expressions. */ 492 493static constraint_t 494new_constraint (const struct constraint_expr lhs, 495 const struct constraint_expr rhs) 496{ 497 constraint_t ret = pool_alloc (constraint_pool); 498 ret->lhs = lhs; 499 ret->rhs = rhs; 500 return ret; 501} 502 503/* Print out constraint C to FILE. */ 504 505void 506dump_constraint (FILE *file, constraint_t c) 507{ 508 if (c->lhs.type == ADDRESSOF) 509 fprintf (file, "&"); 510 else if (c->lhs.type == DEREF) 511 fprintf (file, "*"); 512 fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name); 513 if (c->lhs.offset != 0) 514 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset); 515 fprintf (file, " = "); 516 if (c->rhs.type == ADDRESSOF) 517 fprintf (file, "&"); 518 else if (c->rhs.type == DEREF) 519 fprintf (file, "*"); 520 fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name); 521 if (c->rhs.offset != 0) 522 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset); 523 fprintf (file, "\n"); 524} 525 526/* Print out constraint C to stderr. */ 527 528void 529debug_constraint (constraint_t c) 530{ 531 dump_constraint (stderr, c); 532} 533 534/* Print out all constraints to FILE */ 535 536void 537dump_constraints (FILE *file) 538{ 539 int i; 540 constraint_t c; 541 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) 542 dump_constraint (file, c); 543} 544 545/* Print out all constraints to stderr. */ 546 547void 548debug_constraints (void) 549{ 550 dump_constraints (stderr); 551} 552 553/* SOLVER FUNCTIONS 554 555 The solver is a simple worklist solver, that works on the following 556 algorithm: 557 558 sbitmap changed_nodes = all ones; 559 changed_count = number of nodes; 560 For each node that was already collapsed: 561 changed_count--; 562 563 while (changed_count > 0) 564 { 565 compute topological ordering for constraint graph 566 567 find and collapse cycles in the constraint graph (updating 568 changed if necessary) 569 570 for each node (n) in the graph in topological order: 571 changed_count--; 572 573 Process each complex constraint associated with the node, 574 updating changed if necessary. 575 576 For each outgoing edge from n, propagate the solution from n to 577 the destination of the edge, updating changed as necessary. 578 579 } */ 580 581/* Return true if two constraint expressions A and B are equal. */ 582 583static bool 584constraint_expr_equal (struct constraint_expr a, struct constraint_expr b) 585{ 586 return a.type == b.type && a.var == b.var && a.offset == b.offset; 587} 588 589/* Return true if constraint expression A is less than constraint expression 590 B. This is just arbitrary, but consistent, in order to give them an 591 ordering. */ 592 593static bool 594constraint_expr_less (struct constraint_expr a, struct constraint_expr b) 595{ 596 if (a.type == b.type) 597 { 598 if (a.var == b.var) 599 return a.offset < b.offset; 600 else 601 return a.var < b.var; 602 } 603 else 604 return a.type < b.type; 605} 606 607/* Return true if constraint A is less than constraint B. This is just 608 arbitrary, but consistent, in order to give them an ordering. */ 609 610static bool 611constraint_less (const constraint_t a, const constraint_t b) 612{ 613 if (constraint_expr_less (a->lhs, b->lhs)) 614 return true; 615 else if (constraint_expr_less (b->lhs, a->lhs)) 616 return false; 617 else 618 return constraint_expr_less (a->rhs, b->rhs); 619} 620 621/* Return true if two constraints A and B are equal. */ 622 623static bool 624constraint_equal (struct constraint a, struct constraint b) 625{ 626 return constraint_expr_equal (a.lhs, b.lhs) 627 && constraint_expr_equal (a.rhs, b.rhs); 628} 629 630 631/* Find a constraint LOOKFOR in the sorted constraint vector VEC */ 632 633static constraint_t 634constraint_vec_find (VEC(constraint_t,heap) *vec, 635 struct constraint lookfor) 636{ 637 unsigned int place; 638 constraint_t found; 639 640 if (vec == NULL) 641 return NULL; 642 643 place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less); 644 if (place >= VEC_length (constraint_t, vec)) 645 return NULL; 646 found = VEC_index (constraint_t, vec, place); 647 if (!constraint_equal (*found, lookfor)) 648 return NULL; 649 return found; 650} 651 652/* Union two constraint vectors, TO and FROM. Put the result in TO. */ 653 654static void 655constraint_set_union (VEC(constraint_t,heap) **to, 656 VEC(constraint_t,heap) **from) 657{ 658 int i; 659 constraint_t c; 660 661 for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++) 662 { 663 if (constraint_vec_find (*to, *c) == NULL) 664 { 665 unsigned int place = VEC_lower_bound (constraint_t, *to, c, 666 constraint_less); 667 VEC_safe_insert (constraint_t, heap, *to, place, c); 668 } 669 } 670} 671 672/* Take a solution set SET, add OFFSET to each member of the set, and 673 overwrite SET with the result when done. */ 674 675static void 676solution_set_add (bitmap set, unsigned HOST_WIDE_INT offset) 677{ 678 bitmap result = BITMAP_ALLOC (&iteration_obstack); 679 unsigned int i; 680 bitmap_iterator bi; 681 682 EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi) 683 { 684 /* If this is a properly sized variable, only add offset if it's 685 less than end. Otherwise, it is globbed to a single 686 variable. */ 687 688 if ((get_varinfo (i)->offset + offset) < get_varinfo (i)->fullsize) 689 { 690 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (i)->offset + offset; 691 varinfo_t v = first_vi_for_offset (get_varinfo (i), fieldoffset); 692 if (!v) 693 continue; 694 bitmap_set_bit (result, v->id); 695 } 696 else if (get_varinfo (i)->is_artificial_var 697 || get_varinfo (i)->has_union 698 || get_varinfo (i)->is_unknown_size_var) 699 { 700 bitmap_set_bit (result, i); 701 } 702 } 703 704 bitmap_copy (set, result); 705 BITMAP_FREE (result); 706} 707 708/* Union solution sets TO and FROM, and add INC to each member of FROM in the 709 process. */ 710 711static bool 712set_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc) 713{ 714 if (inc == 0) 715 return bitmap_ior_into (to, from); 716 else 717 { 718 bitmap tmp; 719 bool res; 720 721 tmp = BITMAP_ALLOC (&iteration_obstack); 722 bitmap_copy (tmp, from); 723 solution_set_add (tmp, inc); 724 res = bitmap_ior_into (to, tmp); 725 BITMAP_FREE (tmp); 726 return res; 727 } 728} 729 730/* Insert constraint C into the list of complex constraints for VAR. */ 731 732static void 733insert_into_complex (unsigned int var, constraint_t c) 734{ 735 varinfo_t vi = get_varinfo (var); 736 unsigned int place = VEC_lower_bound (constraint_t, vi->complex, c, 737 constraint_less); 738 VEC_safe_insert (constraint_t, heap, vi->complex, place, c); 739} 740 741 742/* Compare two constraint edges A and B, return true if they are equal. */ 743 744static bool 745constraint_edge_equal (struct constraint_edge a, struct constraint_edge b) 746{ 747 return a.dest == b.dest; 748} 749 750/* Compare two constraint edges, return true if A is less than B */ 751 752static bool 753constraint_edge_less (const constraint_edge_t a, const constraint_edge_t b) 754{ 755 if (a->dest < b->dest) 756 return true; 757 return false; 758} 759 760/* Find the constraint edge that matches LOOKFOR, in VEC. 761 Return the edge, if found, NULL otherwise. */ 762 763static constraint_edge_t 764constraint_edge_vec_find (VEC(constraint_edge_t,heap) *vec, 765 struct constraint_edge lookfor) 766{ 767 unsigned int place; 768 constraint_edge_t edge = NULL; 769 770 place = VEC_lower_bound (constraint_edge_t, vec, &lookfor, 771 constraint_edge_less); 772 if (place >= VEC_length (constraint_edge_t, vec)) 773 return NULL; 774 edge = VEC_index (constraint_edge_t, vec, place); 775 if (!constraint_edge_equal (*edge, lookfor)) 776 return NULL; 777 return edge; 778} 779 780/* Condense two variable nodes into a single variable node, by moving 781 all associated info from SRC to TO. */ 782 783static void 784condense_varmap_nodes (unsigned int to, unsigned int src) 785{ 786 varinfo_t tovi = get_varinfo (to); 787 varinfo_t srcvi = get_varinfo (src); 788 unsigned int i; 789 constraint_t c; 790 bitmap_iterator bi; 791 792 /* the src node, and all its variables, are now the to node. */ 793 srcvi->node = to; 794 EXECUTE_IF_SET_IN_BITMAP (srcvi->variables, 0, i, bi) 795 get_varinfo (i)->node = to; 796 797 /* Merge the src node variables and the to node variables. */ 798 bitmap_set_bit (tovi->variables, src); 799 bitmap_ior_into (tovi->variables, srcvi->variables); 800 bitmap_clear (srcvi->variables); 801 802 /* Move all complex constraints from src node into to node */ 803 for (i = 0; VEC_iterate (constraint_t, srcvi->complex, i, c); i++) 804 { 805 /* In complex constraints for node src, we may have either 806 a = *src, and *src = a. */ 807 808 if (c->rhs.type == DEREF) 809 c->rhs.var = to; 810 else 811 c->lhs.var = to; 812 } 813 constraint_set_union (&tovi->complex, &srcvi->complex); 814 VEC_free (constraint_t, heap, srcvi->complex); 815 srcvi->complex = NULL; 816} 817 818/* Erase an edge from SRC to SRC from GRAPH. This routine only 819 handles self-edges (e.g. an edge from a to a). */ 820 821static void 822erase_graph_self_edge (constraint_graph_t graph, unsigned int src) 823{ 824 VEC(constraint_edge_t,heap) *predvec = graph->preds[src]; 825 VEC(constraint_edge_t,heap) *succvec = graph->succs[src]; 826 struct constraint_edge edge; 827 unsigned int place; 828 829 edge.dest = src; 830 831 /* Remove from the successors. */ 832 place = VEC_lower_bound (constraint_edge_t, succvec, &edge, 833 constraint_edge_less); 834 835 /* Make sure we found the edge. */ 836#ifdef ENABLE_CHECKING 837 { 838 constraint_edge_t tmp = VEC_index (constraint_edge_t, succvec, place); 839 gcc_assert (constraint_edge_equal (*tmp, edge)); 840 } 841#endif 842 VEC_ordered_remove (constraint_edge_t, succvec, place); 843 844 /* Remove from the predecessors. */ 845 place = VEC_lower_bound (constraint_edge_t, predvec, &edge, 846 constraint_edge_less); 847 848 /* Make sure we found the edge. */ 849#ifdef ENABLE_CHECKING 850 { 851 constraint_edge_t tmp = VEC_index (constraint_edge_t, predvec, place); 852 gcc_assert (constraint_edge_equal (*tmp, edge)); 853 } 854#endif 855 VEC_ordered_remove (constraint_edge_t, predvec, place); 856} 857 858/* Remove edges involving NODE from GRAPH. */ 859 860static void 861clear_edges_for_node (constraint_graph_t graph, unsigned int node) 862{ 863 VEC(constraint_edge_t,heap) *succvec = graph->succs[node]; 864 VEC(constraint_edge_t,heap) *predvec = graph->preds[node]; 865 bitmap_iterator bi; 866 unsigned int j; 867 constraint_edge_t c = NULL; 868 int i; 869 870 /* Walk the successors, erase the associated preds. */ 871 872 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[node], 0, j, bi) 873 if (j != node) 874 bitmap_clear_bit (graph->zero_weight_preds[j], node); 875 876 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++) 877 if (c->dest != node) 878 { 879 unsigned int place; 880 struct constraint_edge lookfor; 881 constraint_edge_t result; 882 883 lookfor.dest = node; 884 place = VEC_lower_bound (constraint_edge_t, graph->preds[c->dest], 885 &lookfor, constraint_edge_less); 886 result = VEC_ordered_remove (constraint_edge_t, 887 graph->preds[c->dest], place); 888 pool_free (constraint_edge_pool, result); 889 } 890 891 /* Walk the preds, erase the associated succs. */ 892 893 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_preds[node], 0, j, bi) 894 if (j != node) 895 bitmap_clear_bit (graph->zero_weight_succs[j], node); 896 897 for (i =0; VEC_iterate (constraint_edge_t, predvec, i, c); i++) 898 if (c->dest != node) 899 { 900 unsigned int place; 901 struct constraint_edge lookfor; 902 constraint_edge_t result; 903 904 lookfor.dest = node; 905 place = VEC_lower_bound (constraint_edge_t, graph->succs[c->dest], 906 &lookfor, constraint_edge_less); 907 result = VEC_ordered_remove (constraint_edge_t, 908 graph->succs[c->dest], place); 909 pool_free (constraint_edge_pool, result); 910 911 } 912 913 if (graph->zero_weight_preds[node]) 914 { 915 BITMAP_FREE (graph->zero_weight_preds[node]); 916 graph->zero_weight_preds[node] = NULL; 917 } 918 919 if (graph->zero_weight_succs[node]) 920 { 921 BITMAP_FREE (graph->zero_weight_succs[node]); 922 graph->zero_weight_succs[node] = NULL; 923 } 924 925 VEC_free (constraint_edge_t, heap, graph->preds[node]); 926 VEC_free (constraint_edge_t, heap, graph->succs[node]); 927 graph->preds[node] = NULL; 928 graph->succs[node] = NULL; 929} 930 931static bool edge_added = false; 932 933/* Add edge (src, dest) to the graph. */ 934 935static bool 936add_graph_edge (constraint_graph_t graph, unsigned int src, unsigned int dest) 937{ 938 unsigned int place; 939 VEC(constraint_edge_t,heap) *vec; 940 struct constraint_edge newe; 941 newe.dest = dest; 942 943 vec = graph->preds[src]; 944 place = VEC_lower_bound (constraint_edge_t, vec, &newe, 945 constraint_edge_less); 946 if (place == VEC_length (constraint_edge_t, vec) 947 || VEC_index (constraint_edge_t, vec, place)->dest != dest) 948 { 949 constraint_edge_t edge = new_constraint_edge (dest); 950 951 VEC_safe_insert (constraint_edge_t, heap, graph->preds[src], 952 place, edge); 953 edge = new_constraint_edge (src); 954 955 place = VEC_lower_bound (constraint_edge_t, graph->succs[dest], 956 edge, constraint_edge_less); 957 VEC_safe_insert (constraint_edge_t, heap, graph->succs[dest], 958 place, edge); 959 edge_added = true; 960 stats.num_edges++; 961 return true; 962 } 963 else 964 return false; 965} 966 967 968/* Return the bitmap representing the weights of edge (SRC, DEST). */ 969 970static bitmap * 971get_graph_weights (constraint_graph_t graph, unsigned int src, 972 unsigned int dest) 973{ 974 constraint_edge_t edge; 975 VEC(constraint_edge_t,heap) *vec; 976 struct constraint_edge lookfor; 977 978 lookfor.dest = dest; 979 980 vec = graph->preds[src]; 981 edge = constraint_edge_vec_find (vec, lookfor); 982 gcc_assert (edge != NULL); 983 return &edge->weights; 984} 985 986/* Allocate graph weight bitmap for the edges associated with SRC and 987 DEST in GRAPH. Both the pred and the succ edges share a single 988 bitmap, so we need to set both edges to that bitmap. */ 989 990static bitmap 991allocate_graph_weights (constraint_graph_t graph, unsigned int src, 992 unsigned int dest) 993{ 994 bitmap result; 995 constraint_edge_t edge; 996 VEC(constraint_edge_t,heap) *vec; 997 struct constraint_edge lookfor; 998 999 result = BITMAP_ALLOC (&ptabitmap_obstack); 1000 1001 /* Set the pred weight. */ 1002 lookfor.dest = dest; 1003 vec = graph->preds[src]; 1004 edge = constraint_edge_vec_find (vec, lookfor); 1005 gcc_assert (edge != NULL); 1006 edge->weights = result; 1007 1008 /* Set the succ weight. */ 1009 lookfor.dest = src; 1010 vec = graph->succs[dest]; 1011 edge = constraint_edge_vec_find (vec, lookfor); 1012 gcc_assert (edge != NULL); 1013 edge->weights = result; 1014 1015 return result; 1016} 1017 1018 1019/* Merge GRAPH nodes FROM and TO into node TO. */ 1020 1021static void 1022merge_graph_nodes (constraint_graph_t graph, unsigned int to, 1023 unsigned int from) 1024{ 1025 VEC(constraint_edge_t,heap) *succvec = graph->succs[from]; 1026 VEC(constraint_edge_t,heap) *predvec = graph->preds[from]; 1027 int i; 1028 constraint_edge_t c; 1029 unsigned int j; 1030 bitmap_iterator bi; 1031 1032 /* Merge all the zero weighted predecessor edges. */ 1033 if (graph->zero_weight_preds[from]) 1034 { 1035 if (!graph->zero_weight_preds[to]) 1036 graph->zero_weight_preds[to] = BITMAP_ALLOC (&predbitmap_obstack); 1037 1038 EXECUTE_IF_SET_IN_BITMAP (graph->zero_weight_preds[from], 0, j, bi) 1039 { 1040 if (j != to) 1041 { 1042 bitmap_clear_bit (graph->zero_weight_succs[j], from); 1043 bitmap_set_bit (graph->zero_weight_succs[j], to); 1044 } 1045 } 1046 bitmap_ior_into (graph->zero_weight_preds[to], 1047 graph->zero_weight_preds[from]); 1048 } 1049 1050 /* Merge all the zero weighted successor edges. */ 1051 if (graph->zero_weight_succs[from]) 1052 { 1053 if (!graph->zero_weight_succs[to]) 1054 graph->zero_weight_succs[to] = BITMAP_ALLOC (&ptabitmap_obstack); 1055 EXECUTE_IF_SET_IN_BITMAP (graph->zero_weight_succs[from], 0, j, bi) 1056 { 1057 bitmap_clear_bit (graph->zero_weight_preds[j], from); 1058 bitmap_set_bit (graph->zero_weight_preds[j], to); 1059 } 1060 bitmap_ior_into (graph->zero_weight_succs[to], 1061 graph->zero_weight_succs[from]); 1062 } 1063 1064 /* Merge all the nonzero weighted predecessor edges. */ 1065 for (i = 0; VEC_iterate (constraint_edge_t, predvec, i, c); i++) 1066 { 1067 unsigned int d = c->dest; 1068 bitmap temp; 1069 bitmap *weights; 1070 1071 if (c->dest == from) 1072 d = to; 1073 1074 add_graph_edge (graph, to, d); 1075 1076 temp = *(get_graph_weights (graph, from, c->dest)); 1077 if (temp) 1078 { 1079 weights = get_graph_weights (graph, to, d); 1080 if (!*weights) 1081 *weights = allocate_graph_weights (graph, to, d); 1082 1083 bitmap_ior_into (*weights, temp); 1084 } 1085 1086 } 1087 1088 /* Merge all the nonzero weighted successor edges. */ 1089 for (i = 0; VEC_iterate (constraint_edge_t, succvec, i, c); i++) 1090 { 1091 unsigned int d = c->dest; 1092 bitmap temp; 1093 bitmap *weights; 1094 1095 if (c->dest == from) 1096 d = to; 1097 1098 add_graph_edge (graph, d, to); 1099 1100 temp = *(get_graph_weights (graph, c->dest, from)); 1101 if (temp) 1102 { 1103 weights = get_graph_weights (graph, d, to); 1104 if (!*weights) 1105 *weights = allocate_graph_weights (graph, d, to); 1106 bitmap_ior_into (*weights, temp); 1107 } 1108 } 1109 clear_edges_for_node (graph, from); 1110} 1111 1112/* Add a graph edge to GRAPH, going from TO to FROM, with WEIGHT, if 1113 it doesn't exist in the graph already. 1114 Return false if the edge already existed, true otherwise. */ 1115 1116static bool 1117int_add_graph_edge (constraint_graph_t graph, unsigned int to, 1118 unsigned int from, unsigned HOST_WIDE_INT weight) 1119{ 1120 if (to == from && weight == 0) 1121 { 1122 return false; 1123 } 1124 else 1125 { 1126 bool r = false; 1127 1128 if (weight == 0) 1129 { 1130 if (!graph->zero_weight_preds[to]) 1131 graph->zero_weight_preds[to] = BITMAP_ALLOC (&predbitmap_obstack); 1132 if (!graph->zero_weight_succs[from]) 1133 graph->zero_weight_succs[from] = BITMAP_ALLOC (&ptabitmap_obstack); 1134 if (!bitmap_bit_p (graph->zero_weight_succs[from], to)) 1135 { 1136 edge_added = true; 1137 r = true; 1138 stats.num_edges++; 1139 bitmap_set_bit (graph->zero_weight_preds[to], from); 1140 bitmap_set_bit (graph->zero_weight_succs[from], to); 1141 } 1142 } 1143 else 1144 { 1145 bitmap *weights; 1146 1147 r = add_graph_edge (graph, to, from); 1148 weights = get_graph_weights (graph, to, from); 1149 1150 if (!*weights) 1151 { 1152 r = true; 1153 *weights = allocate_graph_weights (graph, to, from); 1154 bitmap_set_bit (*weights, weight); 1155 } 1156 else 1157 { 1158 r |= !bitmap_bit_p (*weights, weight); 1159 bitmap_set_bit (*weights, weight); 1160 } 1161 } 1162 1163 return r; 1164 } 1165} 1166 1167 1168/* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */ 1169 1170static bool 1171valid_graph_edge (constraint_graph_t graph, unsigned int src, 1172 unsigned int dest) 1173{ 1174 struct constraint_edge lookfor; 1175 lookfor.dest = src; 1176 1177 return (graph->zero_weight_succs[dest] 1178 && bitmap_bit_p (graph->zero_weight_succs[dest], src)) 1179 || constraint_edge_vec_find (graph->succs[dest], lookfor) != NULL; 1180} 1181 1182/* Return true if {DEST, SRC} is an existing weighted graph edge (IE has 1183 a weight other than 0) in GRAPH. */ 1184static bool 1185valid_weighted_graph_edge (constraint_graph_t graph, unsigned int src, 1186 unsigned int dest) 1187{ 1188 struct constraint_edge lookfor; 1189 lookfor.dest = src; 1190 1191 return graph->preds[src] 1192 && constraint_edge_vec_find (graph->succs[dest], lookfor) != NULL; 1193} 1194 1195 1196/* Build the constraint graph. */ 1197 1198static void 1199build_constraint_graph (void) 1200{ 1201 int i = 0; 1202 constraint_t c; 1203 1204 graph = XNEW (struct constraint_graph); 1205 graph_size = VEC_length (varinfo_t, varmap) + 1; 1206 graph->succs = XCNEWVEC (VEC(constraint_edge_t,heap) *, graph_size); 1207 graph->preds = XCNEWVEC (VEC(constraint_edge_t,heap) *, graph_size); 1208 graph->zero_weight_succs = XCNEWVEC (bitmap, graph_size); 1209 graph->zero_weight_preds = XCNEWVEC (bitmap, graph_size); 1210 1211 for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) 1212 { 1213 struct constraint_expr lhs = c->lhs; 1214 struct constraint_expr rhs = c->rhs; 1215 unsigned int lhsvar = get_varinfo_fc (lhs.var)->id; 1216 unsigned int rhsvar = get_varinfo_fc (rhs.var)->id; 1217 1218 if (lhs.type == DEREF) 1219 { 1220 /* *x = y or *x = &y (complex) */ 1221 if (rhs.type == ADDRESSOF || rhsvar > anything_id) 1222 insert_into_complex (lhsvar, c); 1223 } 1224 else if (rhs.type == DEREF) 1225 { 1226 /* !special var= *y */ 1227 if (!(get_varinfo (lhsvar)->is_special_var)) 1228 insert_into_complex (rhsvar, c); 1229 } 1230 else if (rhs.type == ADDRESSOF) 1231 { 1232 /* x = &y */ 1233 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar); 1234 } 1235 else if (lhsvar > anything_id) 1236 { 1237 /* Ignore 0 weighted self edges, as they can't possibly contribute 1238 anything */ 1239 if (lhsvar != rhsvar || rhs.offset != 0 || lhs.offset != 0) 1240 { 1241 /* x = y (simple) */ 1242 int_add_graph_edge (graph, lhs.var, rhs.var, rhs.offset); 1243 } 1244 1245 } 1246 } 1247} 1248 1249 1250/* Changed variables on the last iteration. */ 1251static unsigned int changed_count; 1252static sbitmap changed; 1253 1254DEF_VEC_I(unsigned); 1255DEF_VEC_ALLOC_I(unsigned,heap); 1256 1257 1258/* Strongly Connected Component visitation info. */ 1259 1260struct scc_info 1261{ 1262 sbitmap visited; 1263 sbitmap in_component; 1264 int current_index; 1265 unsigned int *visited_index; 1266 VEC(unsigned,heap) *scc_stack; 1267 VEC(unsigned,heap) *unification_queue; 1268}; 1269 1270 1271/* Recursive routine to find strongly connected components in GRAPH. 1272 SI is the SCC info to store the information in, and N is the id of current 1273 graph node we are processing. 1274 1275 This is Tarjan's strongly connected component finding algorithm, as 1276 modified by Nuutila to keep only non-root nodes on the stack. 1277 The algorithm can be found in "On finding the strongly connected 1278 connected components in a directed graph" by Esko Nuutila and Eljas 1279 Soisalon-Soininen, in Information Processing Letters volume 49, 1280 number 1, pages 9-14. */ 1281 1282static void 1283scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n) 1284{ 1285 unsigned int i; 1286 bitmap_iterator bi; 1287 1288 gcc_assert (get_varinfo (n)->node == n); 1289 SET_BIT (si->visited, n); 1290 RESET_BIT (si->in_component, n); 1291 si->visited_index[n] = si->current_index ++; 1292 1293 /* Visit all the successors. */ 1294 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[n], 0, i, bi) 1295 { 1296 unsigned int w = i; 1297 if (!TEST_BIT (si->visited, w)) 1298 scc_visit (graph, si, w); 1299 if (!TEST_BIT (si->in_component, w)) 1300 { 1301 unsigned int t = get_varinfo (w)->node; 1302 unsigned int nnode = get_varinfo (n)->node; 1303 if (si->visited_index[t] < si->visited_index[nnode]) 1304 get_varinfo (n)->node = t; 1305 } 1306 } 1307 1308 /* See if any components have been identified. */ 1309 if (get_varinfo (n)->node == n) 1310 { 1311 unsigned int t = si->visited_index[n]; 1312 SET_BIT (si->in_component, n); 1313 while (VEC_length (unsigned, si->scc_stack) != 0 1314 && t < si->visited_index[VEC_last (unsigned, si->scc_stack)]) 1315 { 1316 unsigned int w = VEC_pop (unsigned, si->scc_stack); 1317 get_varinfo (w)->node = n; 1318 SET_BIT (si->in_component, w); 1319 /* Mark this node for collapsing. */ 1320 VEC_safe_push (unsigned, heap, si->unification_queue, w); 1321 } 1322 } 1323 else 1324 VEC_safe_push (unsigned, heap, si->scc_stack, n); 1325} 1326 1327 1328/* Collapse two variables into one variable. */ 1329 1330static void 1331collapse_nodes (constraint_graph_t graph, unsigned int to, unsigned int from) 1332{ 1333 bitmap tosol, fromsol; 1334 1335 condense_varmap_nodes (to, from); 1336 tosol = get_varinfo (to)->solution; 1337 fromsol = get_varinfo (from)->solution; 1338 bitmap_ior_into (tosol, fromsol); 1339 merge_graph_nodes (graph, to, from); 1340 1341 if (valid_graph_edge (graph, to, to)) 1342 { 1343 if (graph->zero_weight_preds[to]) 1344 { 1345 bitmap_clear_bit (graph->zero_weight_preds[to], to); 1346 bitmap_clear_bit (graph->zero_weight_succs[to], to); 1347 } 1348 if (valid_weighted_graph_edge (graph, to, to)) 1349 { 1350 bitmap weights = *(get_graph_weights (graph, to, to)); 1351 if (!weights || bitmap_empty_p (weights)) 1352 erase_graph_self_edge (graph, to); 1353 } 1354 } 1355 BITMAP_FREE (fromsol); 1356 get_varinfo (to)->address_taken |= get_varinfo (from)->address_taken; 1357 get_varinfo (to)->indirect_target |= get_varinfo (from)->indirect_target; 1358} 1359 1360 1361/* Unify nodes in GRAPH that we have found to be part of a cycle. 1362 SI is the Strongly Connected Components information structure that tells us 1363 what components to unify. 1364 UPDATE_CHANGED should be set to true if the changed sbitmap and changed 1365 count should be updated to reflect the unification. */ 1366 1367static void 1368process_unification_queue (constraint_graph_t graph, struct scc_info *si, 1369 bool update_changed) 1370{ 1371 size_t i = 0; 1372 bitmap tmp = BITMAP_ALLOC (update_changed ? &iteration_obstack : NULL); 1373 bitmap_clear (tmp); 1374 1375 /* We proceed as follows: 1376 1377 For each component in the queue (components are delineated by 1378 when current_queue_element->node != next_queue_element->node): 1379 1380 rep = representative node for component 1381 1382 For each node (tounify) to be unified in the component, 1383 merge the solution for tounify into tmp bitmap 1384 1385 clear solution for tounify 1386 1387 merge edges from tounify into rep 1388 1389 merge complex constraints from tounify into rep 1390 1391 update changed count to note that tounify will never change 1392 again 1393 1394 Merge tmp into solution for rep, marking rep changed if this 1395 changed rep's solution. 1396 1397 Delete any 0 weighted self-edges we now have for rep. */ 1398 while (i != VEC_length (unsigned, si->unification_queue)) 1399 { 1400 unsigned int tounify = VEC_index (unsigned, si->unification_queue, i); 1401 unsigned int n = get_varinfo (tounify)->node; 1402 1403 if (dump_file && (dump_flags & TDF_DETAILS)) 1404 fprintf (dump_file, "Unifying %s to %s\n", 1405 get_varinfo (tounify)->name, 1406 get_varinfo (n)->name); 1407 if (update_changed) 1408 stats.unified_vars_dynamic++; 1409 else 1410 stats.unified_vars_static++; 1411 bitmap_ior_into (tmp, get_varinfo (tounify)->solution); 1412 merge_graph_nodes (graph, n, tounify); 1413 condense_varmap_nodes (n, tounify); 1414 1415 if (update_changed && TEST_BIT (changed, tounify)) 1416 { 1417 RESET_BIT (changed, tounify); 1418 if (!TEST_BIT (changed, n)) 1419 SET_BIT (changed, n); 1420 else 1421 { 1422 gcc_assert (changed_count > 0); 1423 changed_count--; 1424 } 1425 } 1426 1427 bitmap_clear (get_varinfo (tounify)->solution); 1428 ++i; 1429 1430 /* If we've either finished processing the entire queue, or 1431 finished processing all nodes for component n, update the solution for 1432 n. */ 1433 if (i == VEC_length (unsigned, si->unification_queue) 1434 || get_varinfo (VEC_index (unsigned, si->unification_queue, i))->node != n) 1435 { 1436 /* If the solution changes because of the merging, we need to mark 1437 the variable as changed. */ 1438 if (bitmap_ior_into (get_varinfo (n)->solution, tmp)) 1439 { 1440 if (update_changed && !TEST_BIT (changed, n)) 1441 { 1442 SET_BIT (changed, n); 1443 changed_count++; 1444 } 1445 } 1446 bitmap_clear (tmp); 1447 1448 if (valid_graph_edge (graph, n, n)) 1449 { 1450 if (graph->zero_weight_succs[n]) 1451 { 1452 if (graph->zero_weight_preds[n]) 1453 bitmap_clear_bit (graph->zero_weight_preds[n], n); 1454 bitmap_clear_bit (graph->zero_weight_succs[n], n); 1455 } 1456 if (valid_weighted_graph_edge (graph, n, n)) 1457 { 1458 bitmap weights = *(get_graph_weights (graph, n, n)); 1459 if (!weights || bitmap_empty_p (weights)) 1460 erase_graph_self_edge (graph, n); 1461 } 1462 } 1463 } 1464 } 1465 BITMAP_FREE (tmp); 1466} 1467 1468 1469/* Information needed to compute the topological ordering of a graph. */ 1470 1471struct topo_info 1472{ 1473 /* sbitmap of visited nodes. */ 1474 sbitmap visited; 1475 /* Array that stores the topological order of the graph, *in 1476 reverse*. */ 1477 VEC(unsigned,heap) *topo_order; 1478}; 1479 1480 1481/* Initialize and return a topological info structure. */ 1482 1483static struct topo_info * 1484init_topo_info (void) 1485{ 1486 size_t size = VEC_length (varinfo_t, varmap); 1487 struct topo_info *ti = XNEW (struct topo_info); 1488 ti->visited = sbitmap_alloc (size); 1489 sbitmap_zero (ti->visited); 1490 ti->topo_order = VEC_alloc (unsigned, heap, 1); 1491 return ti; 1492} 1493 1494 1495/* Free the topological sort info pointed to by TI. */ 1496 1497static void 1498free_topo_info (struct topo_info *ti) 1499{ 1500 sbitmap_free (ti->visited); 1501 VEC_free (unsigned, heap, ti->topo_order); 1502 free (ti); 1503} 1504 1505/* Visit the graph in topological order, and store the order in the 1506 topo_info structure. */ 1507 1508static void 1509topo_visit (constraint_graph_t graph, struct topo_info *ti, 1510 unsigned int n) 1511{ 1512 VEC(constraint_edge_t,heap) *succs = graph->succs[n]; 1513 bitmap temp; 1514 bitmap_iterator bi; 1515 constraint_edge_t c; 1516 int i; 1517 unsigned int j; 1518 1519 SET_BIT (ti->visited, n); 1520 if (VEC_length (constraint_edge_t, succs) != 0) 1521 { 1522 temp = BITMAP_ALLOC (&iteration_obstack); 1523 if (graph->zero_weight_succs[n]) 1524 bitmap_ior_into (temp, graph->zero_weight_succs[n]); 1525 for (i = 0; VEC_iterate (constraint_edge_t, succs, i, c); i++) 1526 bitmap_set_bit (temp, c->dest); 1527 } 1528 else 1529 temp = graph->zero_weight_succs[n]; 1530 1531 if (temp) 1532 EXECUTE_IF_SET_IN_BITMAP (temp, 0, j, bi) 1533 { 1534 if (!TEST_BIT (ti->visited, j)) 1535 topo_visit (graph, ti, j); 1536 } 1537 VEC_safe_push (unsigned, heap, ti->topo_order, n); 1538} 1539 1540/* Return true if variable N + OFFSET is a legal field of N. */ 1541 1542static bool 1543type_safe (unsigned int n, unsigned HOST_WIDE_INT *offset) 1544{ 1545 varinfo_t ninfo = get_varinfo (n); 1546 1547 /* For things we've globbed to single variables, any offset into the 1548 variable acts like the entire variable, so that it becomes offset 1549 0. */ 1550 if (ninfo->is_special_var 1551 || ninfo->is_artificial_var 1552 || ninfo->is_unknown_size_var) 1553 { 1554 *offset = 0; 1555 return true; 1556 } 1557 return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize; 1558} 1559 1560/* Process a constraint C that represents *x = &y. */ 1561 1562static void 1563do_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED, 1564 constraint_t c, bitmap delta) 1565{ 1566 unsigned int rhs = c->rhs.var; 1567 unsigned int j; 1568 bitmap_iterator bi; 1569 1570 /* For each member j of Delta (Sol(x)), add x to Sol(j) */ 1571 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) 1572 { 1573 unsigned HOST_WIDE_INT offset = c->lhs.offset; 1574 if (type_safe (j, &offset) && !(get_varinfo (j)->is_special_var)) 1575 { 1576 /* *x != NULL && *x != ANYTHING*/ 1577 varinfo_t v; 1578 unsigned int t; 1579 bitmap sol; 1580 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset; 1581 1582 v = first_vi_for_offset (get_varinfo (j), fieldoffset); 1583 if (!v) 1584 continue; 1585 t = v->node; 1586 sol = get_varinfo (t)->solution; 1587 if (!bitmap_bit_p (sol, rhs)) 1588 { 1589 bitmap_set_bit (sol, rhs); 1590 if (!TEST_BIT (changed, t)) 1591 { 1592 SET_BIT (changed, t); 1593 changed_count++; 1594 } 1595 } 1596 } 1597 else if (0 && dump_file && !(get_varinfo (j)->is_special_var)) 1598 fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n"); 1599 1600 } 1601} 1602 1603/* Process a constraint C that represents x = *y, using DELTA as the 1604 starting solution. */ 1605 1606static void 1607do_sd_constraint (constraint_graph_t graph, constraint_t c, 1608 bitmap delta) 1609{ 1610 unsigned int lhs = get_varinfo (c->lhs.var)->node; 1611 bool flag = false; 1612 bitmap sol = get_varinfo (lhs)->solution; 1613 unsigned int j; 1614 bitmap_iterator bi; 1615 1616 if (bitmap_bit_p (delta, anything_id)) 1617 { 1618 flag = !bitmap_bit_p (sol, anything_id); 1619 if (flag) 1620 bitmap_set_bit (sol, anything_id); 1621 goto done; 1622 } 1623 /* For each variable j in delta (Sol(y)), add 1624 an edge in the graph from j to x, and union Sol(j) into Sol(x). */ 1625 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) 1626 { 1627 unsigned HOST_WIDE_INT roffset = c->rhs.offset; 1628 if (type_safe (j, &roffset)) 1629 { 1630 varinfo_t v; 1631 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset; 1632 unsigned int t; 1633 1634 v = first_vi_for_offset (get_varinfo (j), fieldoffset); 1635 if (!v) 1636 continue; 1637 t = v->node; 1638 1639 /* Adding edges from the special vars is pointless. 1640 They don't have sets that can change. */ 1641 if (get_varinfo (t) ->is_special_var) 1642 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution); 1643 else if (int_add_graph_edge (graph, lhs, t, 0)) 1644 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution); 1645 } 1646 else if (0 && dump_file && !(get_varinfo (j)->is_special_var)) 1647 fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n"); 1648 1649 } 1650 1651done: 1652 /* If the LHS solution changed, mark the var as changed. */ 1653 if (flag) 1654 { 1655 get_varinfo (lhs)->solution = sol; 1656 if (!TEST_BIT (changed, lhs)) 1657 { 1658 SET_BIT (changed, lhs); 1659 changed_count++; 1660 } 1661 } 1662} 1663 1664/* Process a constraint C that represents *x = y. */ 1665 1666static void 1667do_ds_constraint (constraint_graph_t graph, constraint_t c, bitmap delta) 1668{ 1669 unsigned int rhs = get_varinfo (c->rhs.var)->node; 1670 unsigned HOST_WIDE_INT roff = c->rhs.offset; 1671 bitmap sol = get_varinfo (rhs)->solution; 1672 unsigned int j; 1673 bitmap_iterator bi; 1674 1675 if (bitmap_bit_p (sol, anything_id)) 1676 { 1677 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) 1678 { 1679 varinfo_t jvi = get_varinfo (j); 1680 unsigned int t; 1681 unsigned int loff = c->lhs.offset; 1682 unsigned HOST_WIDE_INT fieldoffset = jvi->offset + loff; 1683 varinfo_t v; 1684 1685 v = first_vi_for_offset (get_varinfo (j), fieldoffset); 1686 if (!v) 1687 continue; 1688 t = v->node; 1689 1690 if (!bitmap_bit_p (get_varinfo (t)->solution, anything_id)) 1691 { 1692 bitmap_set_bit (get_varinfo (t)->solution, anything_id); 1693 if (!TEST_BIT (changed, t)) 1694 { 1695 SET_BIT (changed, t); 1696 changed_count++; 1697 } 1698 } 1699 } 1700 return; 1701 } 1702 1703 /* For each member j of delta (Sol(x)), add an edge from y to j and 1704 union Sol(y) into Sol(j) */ 1705 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) 1706 { 1707 unsigned HOST_WIDE_INT loff = c->lhs.offset; 1708 if (type_safe (j, &loff) && !(get_varinfo(j)->is_special_var)) 1709 { 1710 varinfo_t v; 1711 unsigned int t; 1712 unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff; 1713 1714 v = first_vi_for_offset (get_varinfo (j), fieldoffset); 1715 if (!v) 1716 continue; 1717 t = v->node; 1718 if (int_add_graph_edge (graph, t, rhs, roff)) 1719 { 1720 bitmap tmp = get_varinfo (t)->solution; 1721 if (set_union_with_increment (tmp, sol, roff)) 1722 { 1723 get_varinfo (t)->solution = tmp; 1724 if (t == rhs) 1725 sol = get_varinfo (rhs)->solution; 1726 if (!TEST_BIT (changed, t)) 1727 { 1728 SET_BIT (changed, t); 1729 changed_count++; 1730 } 1731 } 1732 } 1733 } 1734 else if (0 && dump_file && !(get_varinfo (j)->is_special_var)) 1735 fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n"); 1736 } 1737} 1738 1739/* Handle a non-simple (simple meaning requires no iteration), non-copy 1740 constraint (IE *x = &y, x = *y, and *x = y). */ 1741 1742static void 1743do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta) 1744{ 1745 if (c->lhs.type == DEREF) 1746 { 1747 if (c->rhs.type == ADDRESSOF) 1748 { 1749 /* *x = &y */ 1750 do_da_constraint (graph, c, delta); 1751 } 1752 else 1753 { 1754 /* *x = y */ 1755 do_ds_constraint (graph, c, delta); 1756 } 1757 } 1758 else 1759 { 1760 /* x = *y */ 1761 if (!(get_varinfo (c->lhs.var)->is_special_var)) 1762 do_sd_constraint (graph, c, delta); 1763 } 1764} 1765 1766/* Initialize and return a new SCC info structure. */ 1767 1768static struct scc_info * 1769init_scc_info (void) 1770{ 1771 struct scc_info *si = XNEW (struct scc_info); 1772 size_t size = VEC_length (varinfo_t, varmap); 1773 1774 si->current_index = 0; 1775 si->visited = sbitmap_alloc (size); 1776 sbitmap_zero (si->visited); 1777 si->in_component = sbitmap_alloc (size); 1778 sbitmap_ones (si->in_component); 1779 si->visited_index = XCNEWVEC (unsigned int, size + 1); 1780 si->scc_stack = VEC_alloc (unsigned, heap, 1); 1781 si->unification_queue = VEC_alloc (unsigned, heap, 1); 1782 return si; 1783} 1784 1785/* Free an SCC info structure pointed to by SI */ 1786 1787static void 1788free_scc_info (struct scc_info *si) 1789{ 1790 sbitmap_free (si->visited); 1791 sbitmap_free (si->in_component); 1792 free (si->visited_index); 1793 VEC_free (unsigned, heap, si->scc_stack); 1794 VEC_free (unsigned, heap, si->unification_queue); 1795 free(si); 1796} 1797 1798 1799/* Find cycles in GRAPH that occur, using strongly connected components, and 1800 collapse the cycles into a single representative node. if UPDATE_CHANGED 1801 is true, then update the changed sbitmap to note those nodes whose 1802 solutions have changed as a result of collapsing. */ 1803 1804static void 1805find_and_collapse_graph_cycles (constraint_graph_t graph, bool update_changed) 1806{ 1807 unsigned int i; 1808 unsigned int size = VEC_length (varinfo_t, varmap); 1809 struct scc_info *si = init_scc_info (); 1810 1811 for (i = 0; i != size; ++i) 1812 if (!TEST_BIT (si->visited, i) && get_varinfo (i)->node == i) 1813 scc_visit (graph, si, i); 1814 1815 process_unification_queue (graph, si, update_changed); 1816 free_scc_info (si); 1817} 1818 1819/* Compute a topological ordering for GRAPH, and store the result in the 1820 topo_info structure TI. */ 1821 1822static void 1823compute_topo_order (constraint_graph_t graph, 1824 struct topo_info *ti) 1825{ 1826 unsigned int i; 1827 unsigned int size = VEC_length (varinfo_t, varmap); 1828 1829 for (i = 0; i != size; ++i) 1830 if (!TEST_BIT (ti->visited, i) && get_varinfo (i)->node == i) 1831 topo_visit (graph, ti, i); 1832} 1833 1834/* Return true if bitmap B is empty, or a bitmap other than bit 0 is set. */ 1835 1836static bool 1837bitmap_other_than_zero_bit_set (bitmap b) 1838{ 1839 unsigned int i; 1840 bitmap_iterator bi; 1841 1842 if (bitmap_empty_p (b)) 1843 return false; 1844 EXECUTE_IF_SET_IN_BITMAP (b, 1, i, bi) 1845 return true; 1846 return false; 1847} 1848 1849/* Perform offline variable substitution. 1850 1851 This is a linear time way of identifying variables that must have 1852 equivalent points-to sets, including those caused by static cycles, 1853 and single entry subgraphs, in the constraint graph. 1854 1855 The technique is described in "Off-line variable substitution for 1856 scaling points-to analysis" by Atanas Rountev and Satish Chandra, 1857 in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. */ 1858 1859static void 1860perform_var_substitution (constraint_graph_t graph) 1861{ 1862 struct topo_info *ti = init_topo_info (); 1863 1864 bitmap_obstack_initialize (&iteration_obstack); 1865 /* Compute the topological ordering of the graph, then visit each 1866 node in topological order. */ 1867 compute_topo_order (graph, ti); 1868 1869 while (VEC_length (unsigned, ti->topo_order) != 0) 1870 { 1871 unsigned int i = VEC_pop (unsigned, ti->topo_order); 1872 unsigned int pred; 1873 varinfo_t vi = get_varinfo (i); 1874 bool okay_to_elim = false; 1875 unsigned int root = VEC_length (varinfo_t, varmap); 1876 VEC(constraint_edge_t,heap) *predvec = graph->preds[i]; 1877 constraint_edge_t ce = NULL; 1878 bitmap tmp; 1879 unsigned int k; 1880 bitmap_iterator bi; 1881 1882 /* We can't eliminate things whose address is taken, or which is 1883 the target of a dereference. */ 1884 if (vi->address_taken || vi->indirect_target) 1885 continue; 1886 1887 /* See if all predecessors of I are ripe for elimination */ 1888 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_preds[i], 0, k, bi) 1889 { 1890 unsigned int w; 1891 w = get_varinfo (k)->node; 1892 1893 /* We can't eliminate the node if one of the predecessors is 1894 part of a different strongly connected component. */ 1895 if (!okay_to_elim) 1896 { 1897 root = w; 1898 okay_to_elim = true; 1899 } 1900 else if (w != root) 1901 { 1902 okay_to_elim = false; 1903 break; 1904 } 1905 1906 /* Theorem 4 in Rountev and Chandra: If i is a direct node, 1907 then Solution(i) is a subset of Solution (w), where w is a 1908 predecessor in the graph. 1909 Corollary: If all predecessors of i have the same 1910 points-to set, then i has that same points-to set as 1911 those predecessors. */ 1912 tmp = BITMAP_ALLOC (NULL); 1913 bitmap_and_compl (tmp, get_varinfo (i)->solution, 1914 get_varinfo (w)->solution); 1915 if (!bitmap_empty_p (tmp)) 1916 { 1917 okay_to_elim = false; 1918 BITMAP_FREE (tmp); 1919 break; 1920 } 1921 BITMAP_FREE (tmp); 1922 } 1923 1924 if (okay_to_elim) 1925 for (pred = 0; 1926 VEC_iterate (constraint_edge_t, predvec, pred, ce); 1927 pred++) 1928 { 1929 bitmap weight; 1930 unsigned int w; 1931 weight = *(get_graph_weights (graph, i, ce->dest)); 1932 1933 /* We can't eliminate variables that have nonzero weighted 1934 edges between them. */ 1935 if (weight && bitmap_other_than_zero_bit_set (weight)) 1936 { 1937 okay_to_elim = false; 1938 break; 1939 } 1940 w = get_varinfo (ce->dest)->node; 1941 1942 /* We can't eliminate the node if one of the predecessors is 1943 part of a different strongly connected component. */ 1944 if (!okay_to_elim) 1945 { 1946 root = w; 1947 okay_to_elim = true; 1948 } 1949 else if (w != root) 1950 { 1951 okay_to_elim = false; 1952 break; 1953 } 1954 1955 /* Theorem 4 in Rountev and Chandra: If i is a direct node, 1956 then Solution(i) is a subset of Solution (w), where w is a 1957 predecessor in the graph. 1958 Corollary: If all predecessors of i have the same 1959 points-to set, then i has that same points-to set as 1960 those predecessors. */ 1961 tmp = BITMAP_ALLOC (NULL); 1962 bitmap_and_compl (tmp, get_varinfo (i)->solution, 1963 get_varinfo (w)->solution); 1964 if (!bitmap_empty_p (tmp)) 1965 { 1966 okay_to_elim = false; 1967 BITMAP_FREE (tmp); 1968 break; 1969 } 1970 BITMAP_FREE (tmp); 1971 } 1972 1973 /* See if the root is different than the original node. 1974 If so, we've found an equivalence. */ 1975 if (root != get_varinfo (i)->node && okay_to_elim) 1976 { 1977 /* Found an equivalence */ 1978 get_varinfo (i)->node = root; 1979 collapse_nodes (graph, root, i); 1980 if (dump_file && (dump_flags & TDF_DETAILS)) 1981 fprintf (dump_file, "Collapsing %s into %s\n", 1982 get_varinfo (i)->name, 1983 get_varinfo (root)->name); 1984 stats.collapsed_vars++; 1985 } 1986 } 1987 1988 bitmap_obstack_release (&iteration_obstack); 1989 free_topo_info (ti); 1990} 1991 1992/* Solve the constraint graph GRAPH using our worklist solver. 1993 This is based on the PW* family of solvers from the "Efficient Field 1994 Sensitive Pointer Analysis for C" paper. 1995 It works by iterating over all the graph nodes, processing the complex 1996 constraints and propagating the copy constraints, until everything stops 1997 changed. This corresponds to steps 6-8 in the solving list given above. */ 1998 1999static void 2000solve_graph (constraint_graph_t graph) 2001{ 2002 unsigned int size = VEC_length (varinfo_t, varmap); 2003 unsigned int i; 2004 2005 changed_count = size; 2006 changed = sbitmap_alloc (size); 2007 sbitmap_ones (changed); 2008 2009 /* The already collapsed/unreachable nodes will never change, so we 2010 need to account for them in changed_count. */ 2011 for (i = 0; i < size; i++) 2012 if (get_varinfo (i)->node != i) 2013 changed_count--; 2014 2015 while (changed_count > 0) 2016 { 2017 unsigned int i; 2018 struct topo_info *ti = init_topo_info (); 2019 stats.iterations++; 2020 2021 bitmap_obstack_initialize (&iteration_obstack); 2022 2023 if (edge_added) 2024 { 2025 /* We already did cycle elimination once, when we did 2026 variable substitution, so we don't need it again for the 2027 first iteration. */ 2028 if (stats.iterations > 1) 2029 find_and_collapse_graph_cycles (graph, true); 2030 2031 edge_added = false; 2032 } 2033 2034 compute_topo_order (graph, ti); 2035 2036 while (VEC_length (unsigned, ti->topo_order) != 0) 2037 { 2038 i = VEC_pop (unsigned, ti->topo_order); 2039 gcc_assert (get_varinfo (i)->node == i); 2040 2041 /* If the node has changed, we need to process the 2042 complex constraints and outgoing edges again. */ 2043 if (TEST_BIT (changed, i)) 2044 { 2045 unsigned int j; 2046 constraint_t c; 2047 constraint_edge_t e = NULL; 2048 bitmap solution; 2049 bitmap_iterator bi; 2050 VEC(constraint_t,heap) *complex = get_varinfo (i)->complex; 2051 VEC(constraint_edge_t,heap) *succs; 2052 bool solution_empty; 2053 2054 RESET_BIT (changed, i); 2055 changed_count--; 2056 2057 solution = get_varinfo (i)->solution; 2058 solution_empty = bitmap_empty_p (solution); 2059 2060 /* Process the complex constraints */ 2061 for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++) 2062 { 2063 /* The only complex constraint that can change our 2064 solution to non-empty, given an empty solution, 2065 is a constraint where the lhs side is receiving 2066 some set from elsewhere. */ 2067 if (!solution_empty || c->lhs.type != DEREF) 2068 do_complex_constraint (graph, c, solution); 2069 } 2070 2071 solution_empty = bitmap_empty_p (solution); 2072 2073 if (!solution_empty) 2074 { 2075 /* Propagate solution to all successors. */ 2076 succs = graph->succs[i]; 2077 2078 EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[i], 2079 0, j, bi) 2080 { 2081 bitmap tmp = get_varinfo (j)->solution; 2082 bool flag = false; 2083 2084 flag = set_union_with_increment (tmp, solution, 0); 2085 2086 if (flag) 2087 { 2088 get_varinfo (j)->solution = tmp; 2089 if (!TEST_BIT (changed, j)) 2090 { 2091 SET_BIT (changed, j); 2092 changed_count++; 2093 } 2094 } 2095 } 2096 for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++) 2097 { 2098 bitmap tmp = get_varinfo (e->dest)->solution; 2099 bool flag = false; 2100 unsigned int k; 2101 bitmap weights = e->weights; 2102 bitmap_iterator bi; 2103 2104 gcc_assert (weights && !bitmap_empty_p (weights)); 2105 EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi) 2106 flag |= set_union_with_increment (tmp, solution, k); 2107 2108 if (flag) 2109 { 2110 get_varinfo (e->dest)->solution = tmp; 2111 if (!TEST_BIT (changed, e->dest)) 2112 { 2113 SET_BIT (changed, e->dest); 2114 changed_count++; 2115 } 2116 } 2117 } 2118 } 2119 } 2120 } 2121 free_topo_info (ti); 2122 bitmap_obstack_release (&iteration_obstack); 2123 } 2124 2125 sbitmap_free (changed); 2126} 2127 2128 2129/* CONSTRAINT AND VARIABLE GENERATION FUNCTIONS */ 2130 2131/* Map from trees to variable ids. */ 2132static htab_t id_for_tree; 2133 2134typedef struct tree_id 2135{ 2136 tree t; 2137 unsigned int id; 2138} *tree_id_t; 2139 2140/* Hash a tree id structure. */ 2141 2142static hashval_t 2143tree_id_hash (const void *p) 2144{ 2145 const tree_id_t ta = (tree_id_t) p; 2146 return htab_hash_pointer (ta->t); 2147} 2148 2149/* Return true if the tree in P1 and the tree in P2 are the same. */ 2150 2151static int 2152tree_id_eq (const void *p1, const void *p2) 2153{ 2154 const tree_id_t ta1 = (tree_id_t) p1; 2155 const tree_id_t ta2 = (tree_id_t) p2; 2156 return ta1->t == ta2->t; 2157} 2158 2159/* Insert ID as the variable id for tree T in the hashtable. */ 2160 2161static void 2162insert_id_for_tree (tree t, int id) 2163{ 2164 void **slot; 2165 struct tree_id finder; 2166 tree_id_t new_pair; 2167 2168 finder.t = t; 2169 slot = htab_find_slot (id_for_tree, &finder, INSERT); 2170 gcc_assert (*slot == NULL); 2171 new_pair = XNEW (struct tree_id); 2172 new_pair->t = t; 2173 new_pair->id = id; 2174 *slot = (void *)new_pair; 2175} 2176 2177/* Find the variable id for tree T in ID_FOR_TREE. If T does not 2178 exist in the hash table, return false, otherwise, return true and 2179 set *ID to the id we found. */ 2180 2181static bool 2182lookup_id_for_tree (tree t, unsigned int *id) 2183{ 2184 tree_id_t pair; 2185 struct tree_id finder; 2186 2187 finder.t = t; 2188 pair = htab_find (id_for_tree, &finder); 2189 if (pair == NULL) 2190 return false; 2191 *id = pair->id; 2192 return true; 2193} 2194 2195/* Return a printable name for DECL */ 2196 2197static const char * 2198alias_get_name (tree decl) 2199{ 2200 const char *res = get_name (decl); 2201 char *temp; 2202 int num_printed = 0; 2203 2204 if (res != NULL) 2205 return res; 2206 2207 res = "NULL"; 2208 if (!dump_file) 2209 return res; 2210 2211 if (TREE_CODE (decl) == SSA_NAME) 2212 { 2213 num_printed = asprintf (&temp, "%s_%u", 2214 alias_get_name (SSA_NAME_VAR (decl)), 2215 SSA_NAME_VERSION (decl)); 2216 } 2217 else if (DECL_P (decl)) 2218 { 2219 num_printed = asprintf (&temp, "D.%u", DECL_UID (decl)); 2220 } 2221 if (num_printed > 0) 2222 { 2223 res = ggc_strdup (temp); 2224 free (temp); 2225 } 2226 return res; 2227} 2228 2229/* Find the variable id for tree T in the hashtable. 2230 If T doesn't exist in the hash table, create an entry for it. */ 2231 2232static unsigned int 2233get_id_for_tree (tree t) 2234{ 2235 tree_id_t pair; 2236 struct tree_id finder; 2237 2238 finder.t = t; 2239 pair = htab_find (id_for_tree, &finder); 2240 if (pair == NULL) 2241 return create_variable_info_for (t, alias_get_name (t)); 2242 2243 return pair->id; 2244} 2245 2246/* Get a constraint expression from an SSA_VAR_P node. */ 2247 2248static struct constraint_expr 2249get_constraint_exp_from_ssa_var (tree t) 2250{ 2251 struct constraint_expr cexpr; 2252 2253 gcc_assert (SSA_VAR_P (t) || DECL_P (t)); 2254 2255 /* For parameters, get at the points-to set for the actual parm 2256 decl. */ 2257 if (TREE_CODE (t) == SSA_NAME 2258 && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL 2259 && default_def (SSA_NAME_VAR (t)) == t) 2260 return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t)); 2261 2262 cexpr.type = SCALAR; 2263 2264 cexpr.var = get_id_for_tree (t); 2265 /* If we determine the result is "anything", and we know this is readonly, 2266 say it points to readonly memory instead. */ 2267 if (cexpr.var == anything_id && TREE_READONLY (t)) 2268 { 2269 cexpr.type = ADDRESSOF; 2270 cexpr.var = readonly_id; 2271 } 2272 2273 cexpr.offset = 0; 2274 return cexpr; 2275} 2276 2277/* Process a completed constraint T, and add it to the constraint 2278 list. */ 2279 2280static void 2281process_constraint (constraint_t t) 2282{ 2283 struct constraint_expr rhs = t->rhs; 2284 struct constraint_expr lhs = t->lhs; 2285 2286 gcc_assert (rhs.var < VEC_length (varinfo_t, varmap)); 2287 gcc_assert (lhs.var < VEC_length (varinfo_t, varmap)); 2288 2289 if (lhs.type == DEREF) 2290 get_varinfo (lhs.var)->directly_dereferenced = true; 2291 if (rhs.type == DEREF) 2292 get_varinfo (rhs.var)->directly_dereferenced = true; 2293 2294 /* ANYTHING == ANYTHING is pointless. */ 2295 if (lhs.var == anything_id && rhs.var == anything_id) 2296 return; 2297 2298 /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */ 2299 else if (lhs.var == anything_id && lhs.type == ADDRESSOF) 2300 { 2301 rhs = t->lhs; 2302 t->lhs = t->rhs; 2303 t->rhs = rhs; 2304 process_constraint (t); 2305 } 2306 /* This can happen in our IR with things like n->a = *p */ 2307 else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id) 2308 { 2309 /* Split into tmp = *rhs, *lhs = tmp */ 2310 tree rhsdecl = get_varinfo (rhs.var)->decl; 2311 tree pointertype = TREE_TYPE (rhsdecl); 2312 tree pointedtotype = TREE_TYPE (pointertype); 2313 tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp"); 2314 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar); 2315 2316 /* If this is an aggregate of known size, we should have passed 2317 this off to do_structure_copy, and it should have broken it 2318 up. */ 2319 gcc_assert (!AGGREGATE_TYPE_P (pointedtotype) 2320 || get_varinfo (rhs.var)->is_unknown_size_var); 2321 2322 process_constraint (new_constraint (tmplhs, rhs)); 2323 process_constraint (new_constraint (lhs, tmplhs)); 2324 } 2325 else if (rhs.type == ADDRESSOF) 2326 { 2327 varinfo_t vi; 2328 gcc_assert (rhs.offset == 0); 2329 2330 /* No need to mark address taken simply because of escaped vars 2331 constraints. */ 2332 if (lhs.var != escaped_vars_id) 2333 for (vi = get_varinfo (rhs.var); vi != NULL; vi = vi->next) 2334 vi->address_taken = true; 2335 2336 VEC_safe_push (constraint_t, heap, constraints, t); 2337 } 2338 else 2339 { 2340 if (lhs.type != DEREF && rhs.type == DEREF) 2341 get_varinfo (lhs.var)->indirect_target = true; 2342 VEC_safe_push (constraint_t, heap, constraints, t); 2343 } 2344} 2345 2346/* Return true if T is a variable of a type that could contain 2347 pointers. */ 2348 2349static bool 2350could_have_pointers (tree t) 2351{ 2352 tree type = TREE_TYPE (t); 2353 2354 if (POINTER_TYPE_P (type) || AGGREGATE_TYPE_P (type) 2355 || TREE_CODE (type) == COMPLEX_TYPE) 2356 return true; 2357 return false; 2358} 2359 2360/* Return the position, in bits, of FIELD_DECL from the beginning of its 2361 structure. */ 2362 2363static unsigned HOST_WIDE_INT 2364bitpos_of_field (const tree fdecl) 2365{ 2366 2367 if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST 2368 || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST) 2369 return -1; 2370 2371 return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8) 2372 + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1); 2373} 2374 2375 2376/* Return true if an access to [ACCESSPOS, ACCESSSIZE] 2377 overlaps with a field at [FIELDPOS, FIELDSIZE] */ 2378 2379static bool 2380offset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos, 2381 const unsigned HOST_WIDE_INT fieldsize, 2382 const unsigned HOST_WIDE_INT accesspos, 2383 const unsigned HOST_WIDE_INT accesssize) 2384{ 2385 if (fieldpos == accesspos && fieldsize == accesssize) 2386 return true; 2387 if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize)) 2388 return true; 2389 if (accesspos < fieldpos && (accesspos + accesssize > fieldpos)) 2390 return true; 2391 2392 return false; 2393} 2394 2395/* Given a COMPONENT_REF T, return the constraint_expr for it. */ 2396 2397static void 2398get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results) 2399{ 2400 tree orig_t = t; 2401 HOST_WIDE_INT bitsize = -1; 2402 HOST_WIDE_INT bitmaxsize = -1; 2403 HOST_WIDE_INT bitpos; 2404 tree forzero; 2405 struct constraint_expr *result; 2406 unsigned int beforelength = VEC_length (ce_s, *results); 2407 2408 /* Some people like to do cute things like take the address of 2409 &0->a.b */ 2410 forzero = t; 2411 while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero)) 2412 forzero = TREE_OPERAND (forzero, 0); 2413 2414 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero)) 2415 { 2416 struct constraint_expr temp; 2417 2418 temp.offset = 0; 2419 temp.var = integer_id; 2420 temp.type = SCALAR; 2421 VEC_safe_push (ce_s, heap, *results, &temp); 2422 return; 2423 } 2424 2425 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize); 2426 2427 /* String constants's are readonly, so there is nothing to really do 2428 here. */ 2429 if (TREE_CODE (t) == STRING_CST) 2430 return; 2431 2432 get_constraint_for (t, results); 2433 result = VEC_last (ce_s, *results); 2434 result->offset = bitpos; 2435 2436 gcc_assert (beforelength + 1 == VEC_length (ce_s, *results)); 2437 2438 /* This can also happen due to weird offsetof type macros. */ 2439 if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF) 2440 result->type = SCALAR; 2441 2442 if (result->type == SCALAR) 2443 { 2444 /* In languages like C, you can access one past the end of an 2445 array. You aren't allowed to dereference it, so we can 2446 ignore this constraint. When we handle pointer subtraction, 2447 we may have to do something cute here. */ 2448 2449 if (result->offset < get_varinfo (result->var)->fullsize 2450 && bitmaxsize != 0) 2451 { 2452 /* It's also not true that the constraint will actually start at the 2453 right offset, it may start in some padding. We only care about 2454 setting the constraint to the first actual field it touches, so 2455 walk to find it. */ 2456 varinfo_t curr; 2457 for (curr = get_varinfo (result->var); curr; curr = curr->next) 2458 { 2459 if (offset_overlaps_with_access (curr->offset, curr->size, 2460 result->offset, bitmaxsize)) 2461 { 2462 result->var = curr->id; 2463 break; 2464 } 2465 } 2466 /* assert that we found *some* field there. The user couldn't be 2467 accessing *only* padding. */ 2468 /* Still the user could access one past the end of an array 2469 embedded in a struct resulting in accessing *only* padding. */ 2470 gcc_assert (curr || ref_contains_array_ref (orig_t)); 2471 } 2472 else if (bitmaxsize == 0) 2473 { 2474 if (dump_file && (dump_flags & TDF_DETAILS)) 2475 fprintf (dump_file, "Access to zero-sized part of variable," 2476 "ignoring\n"); 2477 } 2478 else 2479 if (dump_file && (dump_flags & TDF_DETAILS)) 2480 fprintf (dump_file, "Access to past the end of variable, ignoring\n"); 2481 2482 result->offset = 0; 2483 } 2484} 2485 2486 2487/* Dereference the constraint expression CONS, and return the result. 2488 DEREF (ADDRESSOF) = SCALAR 2489 DEREF (SCALAR) = DEREF 2490 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp)) 2491 This is needed so that we can handle dereferencing DEREF constraints. */ 2492 2493static void 2494do_deref (VEC (ce_s, heap) **constraints) 2495{ 2496 struct constraint_expr *c; 2497 unsigned int i = 0; 2498 for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++) 2499 { 2500 if (c->type == SCALAR) 2501 c->type = DEREF; 2502 else if (c->type == ADDRESSOF) 2503 c->type = SCALAR; 2504 else if (c->type == DEREF) 2505 { 2506 tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp"); 2507 struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar); 2508 process_constraint (new_constraint (tmplhs, *c)); 2509 c->var = tmplhs.var; 2510 } 2511 else 2512 gcc_unreachable (); 2513 } 2514} 2515 2516/* Create a nonlocal variable of TYPE to represent nonlocals we can 2517 alias. */ 2518 2519static tree 2520create_nonlocal_var (tree type) 2521{ 2522 tree nonlocal = create_tmp_var_raw (type, "NONLOCAL"); 2523 2524 if (referenced_vars) 2525 add_referenced_var (nonlocal); 2526 2527 DECL_EXTERNAL (nonlocal) = 1; 2528 return nonlocal; 2529} 2530 2531/* Given a tree T, return the constraint expression for it. */ 2532 2533static void 2534get_constraint_for (tree t, VEC (ce_s, heap) **results) 2535{ 2536 struct constraint_expr temp; 2537 2538 /* x = integer is all glommed to a single variable, which doesn't 2539 point to anything by itself. That is, of course, unless it is an 2540 integer constant being treated as a pointer, in which case, we 2541 will return that this is really the addressof anything. This 2542 happens below, since it will fall into the default case. The only 2543 case we know something about an integer treated like a pointer is 2544 when it is the NULL pointer, and then we just say it points to 2545 NULL. */ 2546 if (TREE_CODE (t) == INTEGER_CST 2547 && !POINTER_TYPE_P (TREE_TYPE (t))) 2548 { 2549 temp.var = integer_id; 2550 temp.type = SCALAR; 2551 temp.offset = 0; 2552 VEC_safe_push (ce_s, heap, *results, &temp); 2553 return; 2554 } 2555 else if (TREE_CODE (t) == INTEGER_CST 2556 && integer_zerop (t)) 2557 { 2558 temp.var = nothing_id; 2559 temp.type = ADDRESSOF; 2560 temp.offset = 0; 2561 VEC_safe_push (ce_s, heap, *results, &temp); 2562 return; 2563 } 2564 2565 switch (TREE_CODE_CLASS (TREE_CODE (t))) 2566 { 2567 case tcc_expression: 2568 { 2569 switch (TREE_CODE (t)) 2570 { 2571 case ADDR_EXPR: 2572 { 2573 struct constraint_expr *c; 2574 unsigned int i; 2575 tree exp = TREE_OPERAND (t, 0); 2576 tree pttype = TREE_TYPE (TREE_TYPE (t)); 2577 2578 get_constraint_for (exp, results); 2579 /* Make sure we capture constraints to all elements 2580 of an array. */ 2581 if ((handled_component_p (exp) 2582 && ref_contains_array_ref (exp)) 2583 || TREE_CODE (TREE_TYPE (exp)) == ARRAY_TYPE) 2584 { 2585 struct constraint_expr *origrhs; 2586 varinfo_t origvar; 2587 struct constraint_expr tmp; 2588 2589 if (VEC_length (ce_s, *results) == 0) 2590 return; 2591 2592 gcc_assert (VEC_length (ce_s, *results) == 1); 2593 origrhs = VEC_last (ce_s, *results); 2594 tmp = *origrhs; 2595 VEC_pop (ce_s, *results); 2596 origvar = get_varinfo (origrhs->var); 2597 for (; origvar; origvar = origvar->next) 2598 { 2599 tmp.var = origvar->id; 2600 VEC_safe_push (ce_s, heap, *results, &tmp); 2601 } 2602 } 2603 else if (VEC_length (ce_s, *results) == 1 2604 && (AGGREGATE_TYPE_P (pttype) 2605 || TREE_CODE (pttype) == COMPLEX_TYPE)) 2606 { 2607 struct constraint_expr *origrhs; 2608 varinfo_t origvar; 2609 struct constraint_expr tmp; 2610 2611 gcc_assert (VEC_length (ce_s, *results) == 1); 2612 origrhs = VEC_last (ce_s, *results); 2613 tmp = *origrhs; 2614 VEC_pop (ce_s, *results); 2615 origvar = get_varinfo (origrhs->var); 2616 for (; origvar; origvar = origvar->next) 2617 { 2618 tmp.var = origvar->id; 2619 VEC_safe_push (ce_s, heap, *results, &tmp); 2620 } 2621 } 2622 2623 for (i = 0; VEC_iterate (ce_s, *results, i, c); i++) 2624 { 2625 if (c->type == DEREF) 2626 c->type = SCALAR; 2627 else 2628 c->type = ADDRESSOF; 2629 } 2630 return; 2631 } 2632 break; 2633 case CALL_EXPR: 2634 /* XXX: In interprocedural mode, if we didn't have the 2635 body, we would need to do *each pointer argument = 2636 &ANYTHING added. */ 2637 if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)) 2638 { 2639 varinfo_t vi; 2640 tree heapvar = heapvar_lookup (t); 2641 2642 if (heapvar == NULL) 2643 { 2644 heapvar = create_tmp_var_raw (ptr_type_node, "HEAP"); 2645 DECL_EXTERNAL (heapvar) = 1; 2646 if (referenced_vars) 2647 add_referenced_var (heapvar); 2648 heapvar_insert (t, heapvar); 2649 } 2650 2651 temp.var = create_variable_info_for (heapvar, 2652 alias_get_name (heapvar)); 2653 2654 vi = get_varinfo (temp.var); 2655 vi->is_artificial_var = 1; 2656 vi->is_heap_var = 1; 2657 temp.type = ADDRESSOF; 2658 temp.offset = 0; 2659 VEC_safe_push (ce_s, heap, *results, &temp); 2660 return; 2661 } 2662 else 2663 { 2664 temp.var = escaped_vars_id; 2665 temp.type = SCALAR; 2666 temp.offset = 0; 2667 VEC_safe_push (ce_s, heap, *results, &temp); 2668 return; 2669 } 2670 break; 2671 default: 2672 { 2673 temp.type = ADDRESSOF; 2674 temp.var = anything_id; 2675 temp.offset = 0; 2676 VEC_safe_push (ce_s, heap, *results, &temp); 2677 return; 2678 } 2679 } 2680 } 2681 case tcc_reference: 2682 { 2683 switch (TREE_CODE (t)) 2684 { 2685 case INDIRECT_REF: 2686 { 2687 get_constraint_for (TREE_OPERAND (t, 0), results); 2688 do_deref (results); 2689 return; 2690 } 2691 case ARRAY_REF: 2692 case ARRAY_RANGE_REF: 2693 case COMPONENT_REF: 2694 get_constraint_for_component_ref (t, results); 2695 return; 2696 default: 2697 { 2698 temp.type = ADDRESSOF; 2699 temp.var = anything_id; 2700 temp.offset = 0; 2701 VEC_safe_push (ce_s, heap, *results, &temp); 2702 return; 2703 } 2704 } 2705 } 2706 case tcc_unary: 2707 { 2708 switch (TREE_CODE (t)) 2709 { 2710 case NOP_EXPR: 2711 case CONVERT_EXPR: 2712 case NON_LVALUE_EXPR: 2713 { 2714 tree op = TREE_OPERAND (t, 0); 2715 2716 /* Cast from non-pointer to pointers are bad news for us. 2717 Anything else, we see through */ 2718 if (!(POINTER_TYPE_P (TREE_TYPE (t)) 2719 && ! POINTER_TYPE_P (TREE_TYPE (op)))) 2720 { 2721 get_constraint_for (op, results); 2722 return; 2723 } 2724 2725 /* FALLTHRU */ 2726 } 2727 default: 2728 { 2729 temp.type = ADDRESSOF; 2730 temp.var = anything_id; 2731 temp.offset = 0; 2732 VEC_safe_push (ce_s, heap, *results, &temp); 2733 return; 2734 } 2735 } 2736 } 2737 case tcc_exceptional: 2738 { 2739 switch (TREE_CODE (t)) 2740 { 2741 case PHI_NODE: 2742 { 2743 get_constraint_for (PHI_RESULT (t), results); 2744 return; 2745 } 2746 break; 2747 case SSA_NAME: 2748 { 2749 struct constraint_expr temp; 2750 temp = get_constraint_exp_from_ssa_var (t); 2751 VEC_safe_push (ce_s, heap, *results, &temp); 2752 return; 2753 } 2754 break; 2755 default: 2756 { 2757 temp.type = ADDRESSOF; 2758 temp.var = anything_id; 2759 temp.offset = 0; 2760 VEC_safe_push (ce_s, heap, *results, &temp); 2761 return; 2762 } 2763 } 2764 } 2765 case tcc_declaration: 2766 { 2767 struct constraint_expr temp; 2768 temp = get_constraint_exp_from_ssa_var (t); 2769 VEC_safe_push (ce_s, heap, *results, &temp); 2770 return; 2771 } 2772 default: 2773 { 2774 temp.type = ADDRESSOF; 2775 temp.var = anything_id; 2776 temp.offset = 0; 2777 VEC_safe_push (ce_s, heap, *results, &temp); 2778 return; 2779 } 2780 } 2781} 2782 2783 2784/* Handle the structure copy case where we have a simple structure copy 2785 between LHS and RHS that is of SIZE (in bits) 2786 2787 For each field of the lhs variable (lhsfield) 2788 For each field of the rhs variable at lhsfield.offset (rhsfield) 2789 add the constraint lhsfield = rhsfield 2790 2791 If we fail due to some kind of type unsafety or other thing we 2792 can't handle, return false. We expect the caller to collapse the 2793 variable in that case. */ 2794 2795static bool 2796do_simple_structure_copy (const struct constraint_expr lhs, 2797 const struct constraint_expr rhs, 2798 const unsigned HOST_WIDE_INT size) 2799{ 2800 varinfo_t p = get_varinfo (lhs.var); 2801 unsigned HOST_WIDE_INT pstart, last; 2802 pstart = p->offset; 2803 last = p->offset + size; 2804 for (; p && p->offset < last; p = p->next) 2805 { 2806 varinfo_t q; 2807 struct constraint_expr templhs = lhs; 2808 struct constraint_expr temprhs = rhs; 2809 unsigned HOST_WIDE_INT fieldoffset; 2810 2811 templhs.var = p->id; 2812 q = get_varinfo (temprhs.var); 2813 fieldoffset = p->offset - pstart; 2814 q = first_vi_for_offset (q, q->offset + fieldoffset); 2815 if (!q) 2816 return false; 2817 temprhs.var = q->id; 2818 process_constraint (new_constraint (templhs, temprhs)); 2819 } 2820 return true; 2821} 2822 2823 2824/* Handle the structure copy case where we have a structure copy between a 2825 aggregate on the LHS and a dereference of a pointer on the RHS 2826 that is of SIZE (in bits) 2827 2828 For each field of the lhs variable (lhsfield) 2829 rhs.offset = lhsfield->offset 2830 add the constraint lhsfield = rhs 2831*/ 2832 2833static void 2834do_rhs_deref_structure_copy (const struct constraint_expr lhs, 2835 const struct constraint_expr rhs, 2836 const unsigned HOST_WIDE_INT size) 2837{ 2838 varinfo_t p = get_varinfo (lhs.var); 2839 unsigned HOST_WIDE_INT pstart,last; 2840 pstart = p->offset; 2841 last = p->offset + size; 2842 2843 for (; p && p->offset < last; p = p->next) 2844 { 2845 varinfo_t q; 2846 struct constraint_expr templhs = lhs; 2847 struct constraint_expr temprhs = rhs; 2848 unsigned HOST_WIDE_INT fieldoffset; 2849 2850 2851 if (templhs.type == SCALAR) 2852 templhs.var = p->id; 2853 else 2854 templhs.offset = p->offset; 2855 2856 q = get_varinfo (temprhs.var); 2857 fieldoffset = p->offset - pstart; 2858 temprhs.offset += fieldoffset; 2859 process_constraint (new_constraint (templhs, temprhs)); 2860 } 2861} 2862 2863/* Handle the structure copy case where we have a structure copy 2864 between a aggregate on the RHS and a dereference of a pointer on 2865 the LHS that is of SIZE (in bits) 2866 2867 For each field of the rhs variable (rhsfield) 2868 lhs.offset = rhsfield->offset 2869 add the constraint lhs = rhsfield 2870*/ 2871 2872static void 2873do_lhs_deref_structure_copy (const struct constraint_expr lhs, 2874 const struct constraint_expr rhs, 2875 const unsigned HOST_WIDE_INT size) 2876{ 2877 varinfo_t p = get_varinfo (rhs.var); 2878 unsigned HOST_WIDE_INT pstart,last; 2879 pstart = p->offset; 2880 last = p->offset + size; 2881 2882 for (; p && p->offset < last; p = p->next) 2883 { 2884 varinfo_t q; 2885 struct constraint_expr templhs = lhs; 2886 struct constraint_expr temprhs = rhs; 2887 unsigned HOST_WIDE_INT fieldoffset; 2888 2889 2890 if (temprhs.type == SCALAR) 2891 temprhs.var = p->id; 2892 else 2893 temprhs.offset = p->offset; 2894 2895 q = get_varinfo (templhs.var); 2896 fieldoffset = p->offset - pstart; 2897 templhs.offset += fieldoffset; 2898 process_constraint (new_constraint (templhs, temprhs)); 2899 } 2900} 2901 2902/* Sometimes, frontends like to give us bad type information. This 2903 function will collapse all the fields from VAR to the end of VAR, 2904 into VAR, so that we treat those fields as a single variable. 2905 We return the variable they were collapsed into. */ 2906 2907static unsigned int 2908collapse_rest_of_var (unsigned int var) 2909{ 2910 varinfo_t currvar = get_varinfo (var); 2911 varinfo_t field; 2912 2913 for (field = currvar->next; field; field = field->next) 2914 { 2915 if (dump_file) 2916 fprintf (dump_file, "Type safety: Collapsing var %s into %s\n", 2917 field->name, currvar->name); 2918 2919 gcc_assert (!field->collapsed_to); 2920 field->collapsed_to = currvar; 2921 } 2922 2923 currvar->next = NULL; 2924 currvar->size = currvar->fullsize - currvar->offset; 2925 2926 return currvar->id; 2927} 2928 2929/* Handle aggregate copies by expanding into copies of the respective 2930 fields of the structures. */ 2931 2932static void 2933do_structure_copy (tree lhsop, tree rhsop) 2934{ 2935 struct constraint_expr lhs, rhs, tmp; 2936 VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL; 2937 varinfo_t p; 2938 unsigned HOST_WIDE_INT lhssize; 2939 unsigned HOST_WIDE_INT rhssize; 2940 2941 get_constraint_for (lhsop, &lhsc); 2942 get_constraint_for (rhsop, &rhsc); 2943 gcc_assert (VEC_length (ce_s, lhsc) == 1); 2944 gcc_assert (VEC_length (ce_s, rhsc) == 1); 2945 lhs = *(VEC_last (ce_s, lhsc)); 2946 rhs = *(VEC_last (ce_s, rhsc)); 2947 2948 VEC_free (ce_s, heap, lhsc); 2949 VEC_free (ce_s, heap, rhsc); 2950 2951 /* If we have special var = x, swap it around. */ 2952 if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var)) 2953 { 2954 tmp = lhs; 2955 lhs = rhs; 2956 rhs = tmp; 2957 } 2958 2959 /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's 2960 possible it's something we could handle. However, most cases falling 2961 into this are dealing with transparent unions, which are slightly 2962 weird. */ 2963 if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var)) 2964 { 2965 rhs.type = ADDRESSOF; 2966 rhs.var = anything_id; 2967 } 2968 2969 /* If the RHS is a special var, or an addressof, set all the LHS fields to 2970 that special var. */ 2971 if (rhs.var <= integer_id) 2972 { 2973 for (p = get_varinfo (lhs.var); p; p = p->next) 2974 { 2975 struct constraint_expr templhs = lhs; 2976 struct constraint_expr temprhs = rhs; 2977 2978 if (templhs.type == SCALAR ) 2979 templhs.var = p->id; 2980 else 2981 templhs.offset += p->offset; 2982 process_constraint (new_constraint (templhs, temprhs)); 2983 } 2984 } 2985 else 2986 { 2987 tree rhstype = TREE_TYPE (rhsop); 2988 tree lhstype = TREE_TYPE (lhsop); 2989 tree rhstypesize; 2990 tree lhstypesize; 2991 2992 lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype); 2993 rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype); 2994 2995 /* If we have a variably sized types on the rhs or lhs, and a deref 2996 constraint, add the constraint, lhsconstraint = &ANYTHING. 2997 This is conservatively correct because either the lhs is an unknown 2998 sized var (if the constraint is SCALAR), or the lhs is a DEREF 2999 constraint, and every variable it can point to must be unknown sized 3000 anyway, so we don't need to worry about fields at all. */ 3001 if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST) 3002 || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST)) 3003 { 3004 rhs.var = anything_id; 3005 rhs.type = ADDRESSOF; 3006 rhs.offset = 0; 3007 process_constraint (new_constraint (lhs, rhs)); 3008 return; 3009 } 3010 3011 /* The size only really matters insofar as we don't set more or less of 3012 the variable. If we hit an unknown size var, the size should be the 3013 whole darn thing. */ 3014 if (get_varinfo (rhs.var)->is_unknown_size_var) 3015 rhssize = ~0; 3016 else 3017 rhssize = TREE_INT_CST_LOW (rhstypesize); 3018 3019 if (get_varinfo (lhs.var)->is_unknown_size_var) 3020 lhssize = ~0; 3021 else 3022 lhssize = TREE_INT_CST_LOW (lhstypesize); 3023 3024 3025 if (rhs.type == SCALAR && lhs.type == SCALAR) 3026 { 3027 if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize))) 3028 { 3029 lhs.var = collapse_rest_of_var (lhs.var); 3030 rhs.var = collapse_rest_of_var (rhs.var); 3031 lhs.offset = 0; 3032 rhs.offset = 0; 3033 lhs.type = SCALAR; 3034 rhs.type = SCALAR; 3035 process_constraint (new_constraint (lhs, rhs)); 3036 } 3037 } 3038 else if (lhs.type != DEREF && rhs.type == DEREF) 3039 do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize)); 3040 else if (lhs.type == DEREF && rhs.type != DEREF) 3041 do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize)); 3042 else 3043 { 3044 tree pointedtotype = lhstype; 3045 tree tmpvar; 3046 3047 gcc_assert (rhs.type == DEREF && lhs.type == DEREF); 3048 tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp"); 3049 do_structure_copy (tmpvar, rhsop); 3050 do_structure_copy (lhsop, tmpvar); 3051 } 3052 } 3053} 3054 3055/* Update related alias information kept in AI. This is used when 3056 building name tags, alias sets and deciding grouping heuristics. 3057 STMT is the statement to process. This function also updates 3058 ADDRESSABLE_VARS. */ 3059 3060static void 3061update_alias_info (tree stmt, struct alias_info *ai) 3062{ 3063 bitmap addr_taken; 3064 use_operand_p use_p; 3065 ssa_op_iter iter; 3066 enum escape_type stmt_escape_type = is_escape_site (stmt); 3067 tree op; 3068 3069 if (stmt_escape_type == ESCAPE_TO_CALL 3070 || stmt_escape_type == ESCAPE_TO_PURE_CONST) 3071 { 3072 ai->num_calls_found++; 3073 if (stmt_escape_type == ESCAPE_TO_PURE_CONST) 3074 ai->num_pure_const_calls_found++; 3075 } 3076 3077 /* Mark all the variables whose address are taken by the statement. */ 3078 addr_taken = addresses_taken (stmt); 3079 if (addr_taken) 3080 { 3081 bitmap_ior_into (addressable_vars, addr_taken); 3082 3083 /* If STMT is an escape point, all the addresses taken by it are 3084 call-clobbered. */ 3085 if (stmt_escape_type != NO_ESCAPE) 3086 { 3087 bitmap_iterator bi; 3088 unsigned i; 3089 3090 EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi) 3091 { 3092 tree rvar = referenced_var (i); 3093 if (!unmodifiable_var_p (rvar)) 3094 mark_call_clobbered (rvar, stmt_escape_type); 3095 } 3096 } 3097 } 3098 3099 /* Process each operand use. If an operand may be aliased, keep 3100 track of how many times it's being used. For pointers, determine 3101 whether they are dereferenced by the statement, or whether their 3102 value escapes, etc. */ 3103 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE) 3104 { 3105 tree op, var; 3106 var_ann_t v_ann; 3107 struct ptr_info_def *pi; 3108 bool is_store, is_potential_deref; 3109 unsigned num_uses, num_derefs; 3110 3111 op = USE_FROM_PTR (use_p); 3112 3113 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it 3114 to the set of addressable variables. */ 3115 if (TREE_CODE (op) == ADDR_EXPR) 3116 { 3117 gcc_assert (TREE_CODE (stmt) == PHI_NODE); 3118 3119 /* PHI nodes don't have annotations for pinning the set 3120 of addresses taken, so we collect them here. 3121 3122 FIXME, should we allow PHI nodes to have annotations 3123 so that they can be treated like regular statements? 3124 Currently, they are treated as second-class 3125 statements. */ 3126 add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars); 3127 continue; 3128 } 3129 3130 /* Ignore constants. */ 3131 if (TREE_CODE (op) != SSA_NAME) 3132 continue; 3133 3134 var = SSA_NAME_VAR (op); 3135 v_ann = var_ann (var); 3136 3137 /* The base variable of an ssa name must be a GIMPLE register, and thus 3138 it cannot be aliased. */ 3139 gcc_assert (!may_be_aliased (var)); 3140 3141 /* We are only interested in pointers. */ 3142 if (!POINTER_TYPE_P (TREE_TYPE (op))) 3143 continue; 3144 3145 pi = get_ptr_info (op); 3146 3147 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */ 3148 if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op))) 3149 { 3150 SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)); 3151 VEC_safe_push (tree, heap, ai->processed_ptrs, op); 3152 } 3153 3154 /* If STMT is a PHI node, then it will not have pointer 3155 dereferences and it will not be an escape point. */ 3156 if (TREE_CODE (stmt) == PHI_NODE) 3157 continue; 3158 3159 /* Determine whether OP is a dereferenced pointer, and if STMT 3160 is an escape point, whether OP escapes. */ 3161 count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store); 3162 3163 /* Handle a corner case involving address expressions of the 3164 form '&PTR->FLD'. The problem with these expressions is that 3165 they do not represent a dereference of PTR. However, if some 3166 other transformation propagates them into an INDIRECT_REF 3167 expression, we end up with '*(&PTR->FLD)' which is folded 3168 into 'PTR->FLD'. 3169 3170 So, if the original code had no other dereferences of PTR, 3171 the aliaser will not create memory tags for it, and when 3172 &PTR->FLD gets propagated to INDIRECT_REF expressions, the 3173 memory operations will receive no V_MAY_DEF/VUSE operands. 3174 3175 One solution would be to have count_uses_and_derefs consider 3176 &PTR->FLD a dereference of PTR. But that is wrong, since it 3177 is not really a dereference but an offset calculation. 3178 3179 What we do here is to recognize these special ADDR_EXPR 3180 nodes. Since these expressions are never GIMPLE values (they 3181 are not GIMPLE invariants), they can only appear on the RHS 3182 of an assignment and their base address is always an 3183 INDIRECT_REF expression. */ 3184 is_potential_deref = false; 3185 if (TREE_CODE (stmt) == MODIFY_EXPR 3186 && TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR 3187 && !is_gimple_val (TREE_OPERAND (stmt, 1))) 3188 { 3189 /* If the RHS if of the form &PTR->FLD and PTR == OP, then 3190 this represents a potential dereference of PTR. */ 3191 tree rhs = TREE_OPERAND (stmt, 1); 3192 tree base = get_base_address (TREE_OPERAND (rhs, 0)); 3193 if (TREE_CODE (base) == INDIRECT_REF 3194 && TREE_OPERAND (base, 0) == op) 3195 is_potential_deref = true; 3196 } 3197 3198 if (num_derefs > 0 || is_potential_deref) 3199 { 3200 /* Mark OP as dereferenced. In a subsequent pass, 3201 dereferenced pointers that point to a set of 3202 variables will be assigned a name tag to alias 3203 all the variables OP points to. */ 3204 pi->is_dereferenced = 1; 3205 3206 /* Keep track of how many time we've dereferenced each 3207 pointer. */ 3208 NUM_REFERENCES_INC (v_ann); 3209 3210 /* If this is a store operation, mark OP as being 3211 dereferenced to store, otherwise mark it as being 3212 dereferenced to load. */ 3213 if (is_store) 3214 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var)); 3215 else 3216 bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var)); 3217 } 3218 3219 if (stmt_escape_type != NO_ESCAPE && num_derefs < num_uses) 3220 { 3221 /* If STMT is an escape point and STMT contains at 3222 least one direct use of OP, then the value of OP 3223 escapes and so the pointed-to variables need to 3224 be marked call-clobbered. */ 3225 pi->value_escapes_p = 1; 3226 pi->escape_mask |= stmt_escape_type; 3227 3228 /* If the statement makes a function call, assume 3229 that pointer OP will be dereferenced in a store 3230 operation inside the called function. */ 3231 if (get_call_expr_in (stmt) 3232 || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL) 3233 { 3234 bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var)); 3235 pi->is_dereferenced = 1; 3236 } 3237 } 3238 } 3239 3240 if (TREE_CODE (stmt) == PHI_NODE) 3241 return; 3242 3243 /* Update reference counter for definitions to any 3244 potentially aliased variable. This is used in the alias 3245 grouping heuristics. */ 3246 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF) 3247 { 3248 tree var = SSA_NAME_VAR (op); 3249 var_ann_t ann = var_ann (var); 3250 bitmap_set_bit (ai->written_vars, DECL_UID (var)); 3251 if (may_be_aliased (var)) 3252 NUM_REFERENCES_INC (ann); 3253 3254 } 3255 3256 /* Mark variables in V_MAY_DEF operands as being written to. */ 3257 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS) 3258 { 3259 tree var = DECL_P (op) ? op : SSA_NAME_VAR (op); 3260 bitmap_set_bit (ai->written_vars, DECL_UID (var)); 3261 } 3262} 3263 3264 3265/* Handle pointer arithmetic EXPR when creating aliasing constraints. 3266 Expressions of the type PTR + CST can be handled in two ways: 3267 3268 1- If the constraint for PTR is ADDRESSOF for a non-structure 3269 variable, then we can use it directly because adding or 3270 subtracting a constant may not alter the original ADDRESSOF 3271 constraint (i.e., pointer arithmetic may not legally go outside 3272 an object's boundaries). 3273 3274 2- If the constraint for PTR is ADDRESSOF for a structure variable, 3275 then if CST is a compile-time constant that can be used as an 3276 offset, we can determine which sub-variable will be pointed-to 3277 by the expression. 3278 3279 Return true if the expression is handled. For any other kind of 3280 expression, return false so that each operand can be added as a 3281 separate constraint by the caller. */ 3282 3283static bool 3284handle_ptr_arith (VEC (ce_s, heap) *lhsc, tree expr) 3285{ 3286 tree op0, op1; 3287 struct constraint_expr *c, *c2; 3288 unsigned int i = 0; 3289 unsigned int j = 0; 3290 VEC (ce_s, heap) *temp = NULL; 3291 unsigned int rhsoffset = 0; 3292 3293 if (TREE_CODE (expr) != PLUS_EXPR 3294 && TREE_CODE (expr) != MINUS_EXPR) 3295 return false; 3296 3297 op0 = TREE_OPERAND (expr, 0); 3298 op1 = TREE_OPERAND (expr, 1); 3299 3300 get_constraint_for (op0, &temp); 3301 if (POINTER_TYPE_P (TREE_TYPE (op0)) 3302 && TREE_CODE (op1) == INTEGER_CST 3303 && TREE_CODE (expr) == PLUS_EXPR) 3304 { 3305 rhsoffset = TREE_INT_CST_LOW (op1) * BITS_PER_UNIT; 3306 } 3307 else 3308 return false; 3309 3310 for (i = 0; VEC_iterate (ce_s, lhsc, i, c); i++) 3311 for (j = 0; VEC_iterate (ce_s, temp, j, c2); j++) 3312 { 3313 if (c2->type == ADDRESSOF && rhsoffset != 0) 3314 { 3315 varinfo_t temp = get_varinfo (c2->var); 3316 3317 /* An access one after the end of an array is valid, 3318 so simply punt on accesses we cannot resolve. */ 3319 temp = first_vi_for_offset (temp, rhsoffset); 3320 if (temp == NULL) 3321 continue; 3322 c2->var = temp->id; 3323 c2->offset = 0; 3324 } 3325 else 3326 c2->offset = rhsoffset; 3327 process_constraint (new_constraint (*c, *c2)); 3328 } 3329 3330 VEC_free (ce_s, heap, temp); 3331 3332 return true; 3333} 3334 3335 3336/* Walk statement T setting up aliasing constraints according to the 3337 references found in T. This function is the main part of the 3338 constraint builder. AI points to auxiliary alias information used 3339 when building alias sets and computing alias grouping heuristics. */ 3340 3341static void 3342find_func_aliases (tree origt) 3343{ 3344 tree t = origt; 3345 VEC(ce_s, heap) *lhsc = NULL; 3346 VEC(ce_s, heap) *rhsc = NULL; 3347 struct constraint_expr *c; 3348 3349 if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0)) 3350 t = TREE_OPERAND (t, 0); 3351 3352 /* Now build constraints expressions. */ 3353 if (TREE_CODE (t) == PHI_NODE) 3354 { 3355 gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t)))); 3356 3357 /* Only care about pointers and structures containing 3358 pointers. */ 3359 if (could_have_pointers (PHI_RESULT (t))) 3360 { 3361 int i; 3362 unsigned int j; 3363 3364 /* For a phi node, assign all the arguments to 3365 the result. */ 3366 get_constraint_for (PHI_RESULT (t), &lhsc); 3367 for (i = 0; i < PHI_NUM_ARGS (t); i++) 3368 { 3369 tree rhstype; 3370 tree strippedrhs = PHI_ARG_DEF (t, i); 3371 3372 STRIP_NOPS (strippedrhs); 3373 rhstype = TREE_TYPE (strippedrhs); 3374 get_constraint_for (PHI_ARG_DEF (t, i), &rhsc); 3375 3376 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++) 3377 { 3378 struct constraint_expr *c2; 3379 while (VEC_length (ce_s, rhsc) > 0) 3380 { 3381 c2 = VEC_last (ce_s, rhsc); 3382 process_constraint (new_constraint (*c, *c2)); 3383 VEC_pop (ce_s, rhsc); 3384 } 3385 } 3386 } 3387 } 3388 } 3389 /* In IPA mode, we need to generate constraints to pass call 3390 arguments through their calls. There are two case, either a 3391 modify_expr when we are returning a value, or just a plain 3392 call_expr when we are not. */ 3393 else if (in_ipa_mode 3394 && ((TREE_CODE (t) == MODIFY_EXPR 3395 && TREE_CODE (TREE_OPERAND (t, 1)) == CALL_EXPR 3396 && !(call_expr_flags (TREE_OPERAND (t, 1)) 3397 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))) 3398 || (TREE_CODE (t) == CALL_EXPR 3399 && !(call_expr_flags (t) 3400 & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))))) 3401 { 3402 tree lhsop; 3403 tree rhsop; 3404 unsigned int varid; 3405 tree arglist; 3406 varinfo_t fi; 3407 int i = 1; 3408 tree decl; 3409 if (TREE_CODE (t) == MODIFY_EXPR) 3410 { 3411 lhsop = TREE_OPERAND (t, 0); 3412 rhsop = TREE_OPERAND (t, 1); 3413 } 3414 else 3415 { 3416 lhsop = NULL; 3417 rhsop = t; 3418 } 3419 decl = get_callee_fndecl (rhsop); 3420 3421 /* If we can directly resolve the function being called, do so. 3422 Otherwise, it must be some sort of indirect expression that 3423 we should still be able to handle. */ 3424 if (decl) 3425 { 3426 varid = get_id_for_tree (decl); 3427 } 3428 else 3429 { 3430 decl = TREE_OPERAND (rhsop, 0); 3431 varid = get_id_for_tree (decl); 3432 } 3433 3434 /* Assign all the passed arguments to the appropriate incoming 3435 parameters of the function. */ 3436 fi = get_varinfo (varid); 3437 arglist = TREE_OPERAND (rhsop, 1); 3438 3439 for (;arglist; arglist = TREE_CHAIN (arglist)) 3440 { 3441 tree arg = TREE_VALUE (arglist); 3442 struct constraint_expr lhs ; 3443 struct constraint_expr *rhsp; 3444 3445 get_constraint_for (arg, &rhsc); 3446 if (TREE_CODE (decl) != FUNCTION_DECL) 3447 { 3448 lhs.type = DEREF; 3449 lhs.var = fi->id; 3450 lhs.offset = i; 3451 } 3452 else 3453 { 3454 lhs.type = SCALAR; 3455 lhs.var = first_vi_for_offset (fi, i)->id; 3456 lhs.offset = 0; 3457 } 3458 while (VEC_length (ce_s, rhsc) != 0) 3459 { 3460 rhsp = VEC_last (ce_s, rhsc); 3461 process_constraint (new_constraint (lhs, *rhsp)); 3462 VEC_pop (ce_s, rhsc); 3463 } 3464 i++; 3465 } 3466 /* If we are returning a value, assign it to the result. */ 3467 if (lhsop) 3468 { 3469 struct constraint_expr rhs; 3470 struct constraint_expr *lhsp; 3471 unsigned int j = 0; 3472 3473 get_constraint_for (lhsop, &lhsc); 3474 if (TREE_CODE (decl) != FUNCTION_DECL) 3475 { 3476 rhs.type = DEREF; 3477 rhs.var = fi->id; 3478 rhs.offset = i; 3479 } 3480 else 3481 { 3482 rhs.type = SCALAR; 3483 rhs.var = first_vi_for_offset (fi, i)->id; 3484 rhs.offset = 0; 3485 } 3486 for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++) 3487 process_constraint (new_constraint (*lhsp, rhs)); 3488 } 3489 } 3490 /* Otherwise, just a regular assignment statement. */ 3491 else if (TREE_CODE (t) == MODIFY_EXPR) 3492 { 3493 tree lhsop = TREE_OPERAND (t, 0); 3494 tree rhsop = TREE_OPERAND (t, 1); 3495 int i; 3496 3497 if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop)) 3498 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE) 3499 && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop)) 3500 || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE)) 3501 { 3502 do_structure_copy (lhsop, rhsop); 3503 } 3504 else 3505 { 3506 /* Only care about operations with pointers, structures 3507 containing pointers, dereferences, and call expressions. */ 3508 if (could_have_pointers (lhsop) 3509 || TREE_CODE (rhsop) == CALL_EXPR) 3510 { 3511 get_constraint_for (lhsop, &lhsc); 3512 switch (TREE_CODE_CLASS (TREE_CODE (rhsop))) 3513 { 3514 /* RHS that consist of unary operations, 3515 exceptional types, or bare decls/constants, get 3516 handled directly by get_constraint_for. */ 3517 case tcc_reference: 3518 case tcc_declaration: 3519 case tcc_constant: 3520 case tcc_exceptional: 3521 case tcc_expression: 3522 case tcc_unary: 3523 { 3524 unsigned int j; 3525 3526 get_constraint_for (rhsop, &rhsc); 3527 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++) 3528 { 3529 struct constraint_expr *c2; 3530 unsigned int k; 3531 3532 for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++) 3533 process_constraint (new_constraint (*c, *c2)); 3534 } 3535 3536 } 3537 break; 3538 3539 case tcc_binary: 3540 { 3541 /* For pointer arithmetic of the form 3542 PTR + CST, we can simply use PTR's 3543 constraint because pointer arithmetic is 3544 not allowed to go out of bounds. */ 3545 if (handle_ptr_arith (lhsc, rhsop)) 3546 break; 3547 } 3548 /* FALLTHRU */ 3549 3550 /* Otherwise, walk each operand. Notice that we 3551 can't use the operand interface because we need 3552 to process expressions other than simple operands 3553 (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */ 3554 default: 3555 for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++) 3556 { 3557 tree op = TREE_OPERAND (rhsop, i); 3558 unsigned int j; 3559 3560 gcc_assert (VEC_length (ce_s, rhsc) == 0); 3561 get_constraint_for (op, &rhsc); 3562 for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++) 3563 { 3564 struct constraint_expr *c2; 3565 while (VEC_length (ce_s, rhsc) > 0) 3566 { 3567 c2 = VEC_last (ce_s, rhsc); 3568 process_constraint (new_constraint (*c, *c2)); 3569 VEC_pop (ce_s, rhsc); 3570 } 3571 } 3572 } 3573 } 3574 } 3575 } 3576 } 3577 3578 /* After promoting variables and computing aliasing we will 3579 need to re-scan most statements. FIXME: Try to minimize the 3580 number of statements re-scanned. It's not really necessary to 3581 re-scan *all* statements. */ 3582 mark_stmt_modified (origt); 3583 VEC_free (ce_s, heap, rhsc); 3584 VEC_free (ce_s, heap, lhsc); 3585} 3586 3587 3588/* Find the first varinfo in the same variable as START that overlaps with 3589 OFFSET. 3590 Effectively, walk the chain of fields for the variable START to find the 3591 first field that overlaps with OFFSET. 3592 Return NULL if we can't find one. */ 3593 3594static varinfo_t 3595first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset) 3596{ 3597 varinfo_t curr = start; 3598 while (curr) 3599 { 3600 /* We may not find a variable in the field list with the actual 3601 offset when when we have glommed a structure to a variable. 3602 In that case, however, offset should still be within the size 3603 of the variable. */ 3604 if (offset >= curr->offset && offset < (curr->offset + curr->size)) 3605 return curr; 3606 curr = curr->next; 3607 } 3608 return NULL; 3609} 3610 3611 3612/* Insert the varinfo FIELD into the field list for BASE, at the front 3613 of the list. */ 3614 3615static void 3616insert_into_field_list (varinfo_t base, varinfo_t field) 3617{ 3618 varinfo_t prev = base; 3619 varinfo_t curr = base->next; 3620 3621 field->next = curr; 3622 prev->next = field; 3623} 3624 3625/* Insert the varinfo FIELD into the field list for BASE, ordered by 3626 offset. */ 3627 3628static void 3629insert_into_field_list_sorted (varinfo_t base, varinfo_t field) 3630{ 3631 varinfo_t prev = base; 3632 varinfo_t curr = base->next; 3633 3634 if (curr == NULL) 3635 { 3636 prev->next = field; 3637 field->next = NULL; 3638 } 3639 else 3640 { 3641 while (curr) 3642 { 3643 if (field->offset <= curr->offset) 3644 break; 3645 prev = curr; 3646 curr = curr->next; 3647 } 3648 field->next = prev->next; 3649 prev->next = field; 3650 } 3651} 3652 3653/* qsort comparison function for two fieldoff's PA and PB */ 3654 3655static int 3656fieldoff_compare (const void *pa, const void *pb) 3657{ 3658 const fieldoff_s *foa = (const fieldoff_s *)pa; 3659 const fieldoff_s *fob = (const fieldoff_s *)pb; 3660 HOST_WIDE_INT foasize, fobsize; 3661 3662 if (foa->offset != fob->offset) 3663 return foa->offset - fob->offset; 3664 3665 foasize = TREE_INT_CST_LOW (foa->size); 3666 fobsize = TREE_INT_CST_LOW (fob->size); 3667 return foasize - fobsize; 3668} 3669 3670/* Sort a fieldstack according to the field offset and sizes. */ 3671void 3672sort_fieldstack (VEC(fieldoff_s,heap) *fieldstack) 3673{ 3674 qsort (VEC_address (fieldoff_s, fieldstack), 3675 VEC_length (fieldoff_s, fieldstack), 3676 sizeof (fieldoff_s), 3677 fieldoff_compare); 3678} 3679 3680/* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields 3681 of TYPE onto fieldstack, recording their offsets along the way. 3682 OFFSET is used to keep track of the offset in this entire structure, rather 3683 than just the immediately containing structure. Returns the number 3684 of fields pushed. 3685 HAS_UNION is set to true if we find a union type as a field of 3686 TYPE. */ 3687 3688int 3689push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack, 3690 HOST_WIDE_INT offset, bool *has_union) 3691{ 3692 tree field; 3693 int count = 0; 3694 3695 if (TREE_CODE (type) == COMPLEX_TYPE) 3696 { 3697 fieldoff_s *real_part, *img_part; 3698 real_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL); 3699 real_part->type = TREE_TYPE (type); 3700 real_part->size = TYPE_SIZE (TREE_TYPE (type)); 3701 real_part->offset = offset; 3702 real_part->decl = NULL_TREE; 3703 3704 img_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL); 3705 img_part->type = TREE_TYPE (type); 3706 img_part->size = TYPE_SIZE (TREE_TYPE (type)); 3707 img_part->offset = offset + TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type))); 3708 img_part->decl = NULL_TREE; 3709 3710 return 2; 3711 } 3712 3713 if (TREE_CODE (type) == ARRAY_TYPE) 3714 { 3715 tree sz = TYPE_SIZE (type); 3716 tree elsz = TYPE_SIZE (TREE_TYPE (type)); 3717 HOST_WIDE_INT nr; 3718 int i; 3719 3720 if (! sz 3721 || ! host_integerp (sz, 1) 3722 || TREE_INT_CST_LOW (sz) == 0 3723 || ! elsz 3724 || ! host_integerp (elsz, 1) 3725 || TREE_INT_CST_LOW (elsz) == 0) 3726 return 0; 3727 3728 nr = TREE_INT_CST_LOW (sz) / TREE_INT_CST_LOW (elsz); 3729 if (nr > SALIAS_MAX_ARRAY_ELEMENTS) 3730 return 0; 3731 3732 for (i = 0; i < nr; ++i) 3733 { 3734 bool push = false; 3735 int pushed = 0; 3736 3737 if (has_union 3738 && (TREE_CODE (TREE_TYPE (type)) == QUAL_UNION_TYPE 3739 || TREE_CODE (TREE_TYPE (type)) == UNION_TYPE)) 3740 *has_union = true; 3741 3742 if (!AGGREGATE_TYPE_P (TREE_TYPE (type))) /* var_can_have_subvars */ 3743 push = true; 3744 else if (!(pushed = push_fields_onto_fieldstack 3745 (TREE_TYPE (type), fieldstack, 3746 offset + i * TREE_INT_CST_LOW (elsz), has_union))) 3747 /* Empty structures may have actual size, like in C++. So 3748 see if we didn't push any subfields and the size is 3749 nonzero, push the field onto the stack */ 3750 push = true; 3751 3752 if (push) 3753 { 3754 fieldoff_s *pair; 3755 3756 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL); 3757 pair->type = TREE_TYPE (type); 3758 pair->size = elsz; 3759 pair->decl = NULL_TREE; 3760 pair->offset = offset + i * TREE_INT_CST_LOW (elsz); 3761 count++; 3762 } 3763 else 3764 count += pushed; 3765 } 3766 3767 return count; 3768 } 3769 3770 for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field)) 3771 if (TREE_CODE (field) == FIELD_DECL) 3772 { 3773 bool push = false; 3774 int pushed = 0; 3775 3776 if (has_union 3777 && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE 3778 || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)) 3779 *has_union = true; 3780 3781 if (!var_can_have_subvars (field)) 3782 push = true; 3783 else if (!(pushed = push_fields_onto_fieldstack 3784 (TREE_TYPE (field), fieldstack, 3785 offset + bitpos_of_field (field), has_union)) 3786 && DECL_SIZE (field) 3787 && !integer_zerop (DECL_SIZE (field))) 3788 /* Empty structures may have actual size, like in C++. So 3789 see if we didn't push any subfields and the size is 3790 nonzero, push the field onto the stack */ 3791 push = true; 3792 3793 if (push) 3794 { 3795 fieldoff_s *pair; 3796 3797 pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL); 3798 pair->type = TREE_TYPE (field); 3799 pair->size = DECL_SIZE (field); 3800 pair->decl = field; 3801 pair->offset = offset + bitpos_of_field (field); 3802 count++; 3803 } 3804 else 3805 count += pushed; 3806 } 3807 3808 return count; 3809} 3810 3811/* Create a constraint from ESCAPED_VARS variable to VI. */ 3812static void 3813make_constraint_from_escaped (varinfo_t vi) 3814{ 3815 struct constraint_expr lhs, rhs; 3816 3817 lhs.var = vi->id; 3818 lhs.offset = 0; 3819 lhs.type = SCALAR; 3820 3821 rhs.var = escaped_vars_id; 3822 rhs.offset = 0; 3823 rhs.type = SCALAR; 3824 process_constraint (new_constraint (lhs, rhs)); 3825} 3826 3827/* Create a constraint to the ESCAPED_VARS variable from constraint 3828 expression RHS. */ 3829 3830static void 3831make_constraint_to_escaped (struct constraint_expr rhs) 3832{ 3833 struct constraint_expr lhs; 3834 3835 lhs.var = escaped_vars_id; 3836 lhs.offset = 0; 3837 lhs.type = SCALAR; 3838 3839 process_constraint (new_constraint (lhs, rhs)); 3840} 3841 3842/* Count the number of arguments DECL has, and set IS_VARARGS to true 3843 if it is a varargs function. */ 3844 3845static unsigned int 3846count_num_arguments (tree decl, bool *is_varargs) 3847{ 3848 unsigned int i = 0; 3849 tree t; 3850 3851 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl)); 3852 t; 3853 t = TREE_CHAIN (t)) 3854 { 3855 if (TREE_VALUE (t) == void_type_node) 3856 break; 3857 i++; 3858 } 3859 3860 if (!t) 3861 *is_varargs = true; 3862 return i; 3863} 3864 3865/* Creation function node for DECL, using NAME, and return the index 3866 of the variable we've created for the function. */ 3867 3868static unsigned int 3869create_function_info_for (tree decl, const char *name) 3870{ 3871 unsigned int index = VEC_length (varinfo_t, varmap); 3872 varinfo_t vi; 3873 tree arg; 3874 unsigned int i; 3875 bool is_varargs = false; 3876 3877 /* Create the variable info. */ 3878 3879 vi = new_var_info (decl, index, name, index); 3880 vi->decl = decl; 3881 vi->offset = 0; 3882 vi->has_union = 0; 3883 vi->size = 1; 3884 vi->fullsize = count_num_arguments (decl, &is_varargs) + 1; 3885 insert_id_for_tree (vi->decl, index); 3886 VEC_safe_push (varinfo_t, heap, varmap, vi); 3887 3888 stats.total_vars++; 3889 3890 /* If it's varargs, we don't know how many arguments it has, so we 3891 can't do much. 3892 */ 3893 if (is_varargs) 3894 { 3895 vi->fullsize = ~0; 3896 vi->size = ~0; 3897 vi->is_unknown_size_var = true; 3898 return index; 3899 } 3900 3901 3902 arg = DECL_ARGUMENTS (decl); 3903 3904 /* Set up variables for each argument. */ 3905 for (i = 1; i < vi->fullsize; i++) 3906 { 3907 varinfo_t argvi; 3908 const char *newname; 3909 char *tempname; 3910 unsigned int newindex; 3911 tree argdecl = decl; 3912 3913 if (arg) 3914 argdecl = arg; 3915 3916 newindex = VEC_length (varinfo_t, varmap); 3917 asprintf (&tempname, "%s.arg%d", name, i-1); 3918 newname = ggc_strdup (tempname); 3919 free (tempname); 3920 3921 argvi = new_var_info (argdecl, newindex,newname, newindex); 3922 argvi->decl = argdecl; 3923 VEC_safe_push (varinfo_t, heap, varmap, argvi); 3924 argvi->offset = i; 3925 argvi->size = 1; 3926 argvi->fullsize = vi->fullsize; 3927 argvi->has_union = false; 3928 insert_into_field_list_sorted (vi, argvi); 3929 stats.total_vars ++; 3930 if (arg) 3931 { 3932 insert_id_for_tree (arg, newindex); 3933 arg = TREE_CHAIN (arg); 3934 } 3935 } 3936 3937 /* Create a variable for the return var. */ 3938 if (DECL_RESULT (decl) != NULL 3939 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl)))) 3940 { 3941 varinfo_t resultvi; 3942 const char *newname; 3943 char *tempname; 3944 unsigned int newindex; 3945 tree resultdecl = decl; 3946 3947 vi->fullsize ++; 3948 3949 if (DECL_RESULT (decl)) 3950 resultdecl = DECL_RESULT (decl); 3951 3952 newindex = VEC_length (varinfo_t, varmap); 3953 asprintf (&tempname, "%s.result", name); 3954 newname = ggc_strdup (tempname); 3955 free (tempname); 3956 3957 resultvi = new_var_info (resultdecl, newindex, newname, newindex); 3958 resultvi->decl = resultdecl; 3959 VEC_safe_push (varinfo_t, heap, varmap, resultvi); 3960 resultvi->offset = i; 3961 resultvi->size = 1; 3962 resultvi->fullsize = vi->fullsize; 3963 resultvi->has_union = false; 3964 insert_into_field_list_sorted (vi, resultvi); 3965 stats.total_vars ++; 3966 if (DECL_RESULT (decl)) 3967 insert_id_for_tree (DECL_RESULT (decl), newindex); 3968 } 3969 return index; 3970} 3971 3972 3973/* Return true if FIELDSTACK contains fields that overlap. 3974 FIELDSTACK is assumed to be sorted by offset. */ 3975 3976static bool 3977check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack) 3978{ 3979 fieldoff_s *fo = NULL; 3980 unsigned int i; 3981 HOST_WIDE_INT lastoffset = -1; 3982 3983 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++) 3984 { 3985 if (fo->offset == lastoffset) 3986 return true; 3987 lastoffset = fo->offset; 3988 } 3989 return false; 3990} 3991 3992/* This function is called through walk_tree to walk global 3993 initializers looking for constraints we need to add to the 3994 constraint list. */ 3995 3996static tree 3997find_global_initializers (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, 3998 void *viv) 3999{ 4000 varinfo_t vi = (varinfo_t)viv; 4001 tree t = *tp; 4002 4003 switch (TREE_CODE (t)) 4004 { 4005 /* Dereferences and addressofs are the only important things 4006 here, and i don't even remember if dereferences are legal 4007 here in initializers. */ 4008 case INDIRECT_REF: 4009 case ADDR_EXPR: 4010 { 4011 struct constraint_expr *c; 4012 size_t i; 4013 4014 VEC(ce_s, heap) *rhsc = NULL; 4015 get_constraint_for (t, &rhsc); 4016 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) 4017 { 4018 struct constraint_expr lhs; 4019 4020 lhs.var = vi->id; 4021 lhs.type = SCALAR; 4022 lhs.offset = 0; 4023 process_constraint (new_constraint (lhs, *c)); 4024 } 4025 4026 VEC_free (ce_s, heap, rhsc); 4027 } 4028 break; 4029 case VAR_DECL: 4030 /* We might not have walked this because we skip 4031 DECL_EXTERNALs during the initial scan. */ 4032 if (referenced_vars) 4033 { 4034 get_var_ann (t); 4035 if (referenced_var_check_and_insert (t)) 4036 mark_sym_for_renaming (t); 4037 } 4038 break; 4039 default: 4040 break; 4041 } 4042 return NULL_TREE; 4043} 4044 4045/* Create a varinfo structure for NAME and DECL, and add it to VARMAP. 4046 This will also create any varinfo structures necessary for fields 4047 of DECL. */ 4048 4049static unsigned int 4050create_variable_info_for (tree decl, const char *name) 4051{ 4052 unsigned int index = VEC_length (varinfo_t, varmap); 4053 varinfo_t vi; 4054 tree decltype = TREE_TYPE (decl); 4055 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype); 4056 bool notokay = false; 4057 bool hasunion; 4058 bool is_global = DECL_P (decl) ? is_global_var (decl) : false; 4059 VEC (fieldoff_s,heap) *fieldstack = NULL; 4060 4061 if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode) 4062 return create_function_info_for (decl, name); 4063 4064 hasunion = TREE_CODE (decltype) == UNION_TYPE 4065 || TREE_CODE (decltype) == QUAL_UNION_TYPE; 4066 if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion) 4067 { 4068 push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion); 4069 if (hasunion) 4070 { 4071 VEC_free (fieldoff_s, heap, fieldstack); 4072 notokay = true; 4073 } 4074 } 4075 4076 4077 /* If the variable doesn't have subvars, we may end up needing to 4078 sort the field list and create fake variables for all the 4079 fields. */ 4080 vi = new_var_info (decl, index, name, index); 4081 vi->decl = decl; 4082 vi->offset = 0; 4083 vi->has_union = hasunion; 4084 if (!declsize 4085 || TREE_CODE (declsize) != INTEGER_CST 4086 || TREE_CODE (decltype) == UNION_TYPE 4087 || TREE_CODE (decltype) == QUAL_UNION_TYPE) 4088 { 4089 vi->is_unknown_size_var = true; 4090 vi->fullsize = ~0; 4091 vi->size = ~0; 4092 } 4093 else 4094 { 4095 vi->fullsize = TREE_INT_CST_LOW (declsize); 4096 vi->size = vi->fullsize; 4097 } 4098 4099 insert_id_for_tree (vi->decl, index); 4100 VEC_safe_push (varinfo_t, heap, varmap, vi); 4101 if (is_global && (!flag_whole_program || !in_ipa_mode)) 4102 { 4103 make_constraint_from_escaped (vi); 4104 4105 /* If the variable can't be aliased, there is no point in 4106 putting it in the set of nonlocal vars. */ 4107 if (may_be_aliased (vi->decl)) 4108 { 4109 struct constraint_expr rhs; 4110 rhs.var = index; 4111 rhs.type = ADDRESSOF; 4112 rhs.offset = 0; 4113 make_constraint_to_escaped (rhs); 4114 } 4115 4116 if (TREE_CODE (decl) != FUNCTION_DECL && DECL_INITIAL (decl)) 4117 { 4118 walk_tree_without_duplicates (&DECL_INITIAL (decl), 4119 find_global_initializers, 4120 (void *)vi); 4121 } 4122 } 4123 4124 stats.total_vars++; 4125 if (use_field_sensitive 4126 && !notokay 4127 && !vi->is_unknown_size_var 4128 && var_can_have_subvars (decl) 4129 && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE) 4130 { 4131 unsigned int newindex = VEC_length (varinfo_t, varmap); 4132 fieldoff_s *fo = NULL; 4133 unsigned int i; 4134 4135 for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++) 4136 { 4137 if (! fo->size 4138 || TREE_CODE (fo->size) != INTEGER_CST 4139 || fo->offset < 0) 4140 { 4141 notokay = true; 4142 break; 4143 } 4144 } 4145 4146 /* We can't sort them if we have a field with a variable sized type, 4147 which will make notokay = true. In that case, we are going to return 4148 without creating varinfos for the fields anyway, so sorting them is a 4149 waste to boot. */ 4150 if (!notokay) 4151 { 4152 sort_fieldstack (fieldstack); 4153 /* Due to some C++ FE issues, like PR 22488, we might end up 4154 what appear to be overlapping fields even though they, 4155 in reality, do not overlap. Until the C++ FE is fixed, 4156 we will simply disable field-sensitivity for these cases. */ 4157 notokay = check_for_overlaps (fieldstack); 4158 } 4159 4160 4161 if (VEC_length (fieldoff_s, fieldstack) != 0) 4162 fo = VEC_index (fieldoff_s, fieldstack, 0); 4163 4164 if (fo == NULL || notokay) 4165 { 4166 vi->is_unknown_size_var = 1; 4167 vi->fullsize = ~0; 4168 vi->size = ~0; 4169 VEC_free (fieldoff_s, heap, fieldstack); 4170 return index; 4171 } 4172 4173 vi->size = TREE_INT_CST_LOW (fo->size); 4174 vi->offset = fo->offset; 4175 for (i = VEC_length (fieldoff_s, fieldstack) - 1; 4176 i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo); 4177 i--) 4178 { 4179 varinfo_t newvi; 4180 const char *newname = "NULL"; 4181 char *tempname; 4182 4183 newindex = VEC_length (varinfo_t, varmap); 4184 if (dump_file) 4185 { 4186 if (fo->decl) 4187 asprintf (&tempname, "%s.%s", 4188 vi->name, alias_get_name (fo->decl)); 4189 else 4190 asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC, 4191 vi->name, fo->offset); 4192 newname = ggc_strdup (tempname); 4193 free (tempname); 4194 } 4195 newvi = new_var_info (decl, newindex, newname, newindex); 4196 newvi->offset = fo->offset; 4197 newvi->size = TREE_INT_CST_LOW (fo->size); 4198 newvi->fullsize = vi->fullsize; 4199 insert_into_field_list (vi, newvi); 4200 VEC_safe_push (varinfo_t, heap, varmap, newvi); 4201 if (is_global && (!flag_whole_program || !in_ipa_mode)) 4202 { 4203 /* If the variable can't be aliased, there is no point in 4204 putting it in the set of nonlocal vars. */ 4205 if (may_be_aliased (vi->decl)) 4206 { 4207 struct constraint_expr rhs; 4208 4209 rhs.var = newindex; 4210 rhs.type = ADDRESSOF; 4211 rhs.offset = 0; 4212 make_constraint_to_escaped (rhs); 4213 } 4214 make_constraint_from_escaped (newvi); 4215 } 4216 4217 stats.total_vars++; 4218 } 4219 VEC_free (fieldoff_s, heap, fieldstack); 4220 } 4221 return index; 4222} 4223 4224/* Print out the points-to solution for VAR to FILE. */ 4225 4226void 4227dump_solution_for_var (FILE *file, unsigned int var) 4228{ 4229 varinfo_t vi = get_varinfo (var); 4230 unsigned int i; 4231 bitmap_iterator bi; 4232 4233 fprintf (file, "%s = { ", vi->name); 4234 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (vi->node)->solution, 0, i, bi) 4235 { 4236 fprintf (file, "%s ", get_varinfo (i)->name); 4237 } 4238 fprintf (file, "}\n"); 4239} 4240 4241/* Print the points-to solution for VAR to stdout. */ 4242 4243void 4244debug_solution_for_var (unsigned int var) 4245{ 4246 dump_solution_for_var (stdout, var); 4247} 4248 4249/* Create varinfo structures for all of the variables in the 4250 function for intraprocedural mode. */ 4251 4252static void 4253intra_create_variable_infos (void) 4254{ 4255 tree t; 4256 struct constraint_expr lhs, rhs; 4257 varinfo_t nonlocal_vi; 4258 4259 /* For each incoming pointer argument arg, ARG = ESCAPED_VARS or a 4260 dummy variable if flag_argument_noalias > 2. */ 4261 for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t)) 4262 { 4263 varinfo_t p; 4264 unsigned int arg_id; 4265 4266 if (!could_have_pointers (t)) 4267 continue; 4268 4269 arg_id = get_id_for_tree (t); 4270 4271 /* With flag_argument_noalias greater than two means that the incoming 4272 argument cannot alias anything except for itself so create a HEAP 4273 variable. */ 4274 if (POINTER_TYPE_P (TREE_TYPE (t)) 4275 && flag_argument_noalias > 2) 4276 { 4277 varinfo_t vi; 4278 tree heapvar = heapvar_lookup (t); 4279 unsigned int id; 4280 4281 lhs.offset = 0; 4282 lhs.type = SCALAR; 4283 lhs.var = get_id_for_tree (t); 4284 4285 if (heapvar == NULL_TREE) 4286 { 4287 heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)), 4288 "PARM_NOALIAS"); 4289 DECL_EXTERNAL (heapvar) = 1; 4290 if (referenced_vars) 4291 add_referenced_var (heapvar); 4292 heapvar_insert (t, heapvar); 4293 } 4294 id = get_id_for_tree (heapvar); 4295 vi = get_varinfo (id); 4296 vi->is_artificial_var = 1; 4297 vi->is_heap_var = 1; 4298 rhs.var = id; 4299 rhs.type = ADDRESSOF; 4300 rhs.offset = 0; 4301 for (p = get_varinfo (lhs.var); p; p = p->next) 4302 { 4303 struct constraint_expr temp = lhs; 4304 temp.var = p->id; 4305 process_constraint (new_constraint (temp, rhs)); 4306 } 4307 } 4308 else 4309 { 4310 for (p = get_varinfo (arg_id); p; p = p->next) 4311 make_constraint_from_escaped (p); 4312 } 4313 } 4314 if (!nonlocal_all) 4315 nonlocal_all = create_nonlocal_var (void_type_node); 4316 4317 /* Create variable info for the nonlocal var if it does not 4318 exist. */ 4319 nonlocal_vars_id = create_variable_info_for (nonlocal_all, 4320 get_name (nonlocal_all)); 4321 nonlocal_vi = get_varinfo (nonlocal_vars_id); 4322 nonlocal_vi->is_artificial_var = 1; 4323 nonlocal_vi->is_heap_var = 1; 4324 nonlocal_vi->is_unknown_size_var = 1; 4325 nonlocal_vi->directly_dereferenced = true; 4326 4327 rhs.var = nonlocal_vars_id; 4328 rhs.type = ADDRESSOF; 4329 rhs.offset = 0; 4330 4331 lhs.var = escaped_vars_id; 4332 lhs.type = SCALAR; 4333 lhs.offset = 0; 4334 4335 process_constraint (new_constraint (lhs, rhs)); 4336} 4337 4338/* Set bits in INTO corresponding to the variable uids in solution set 4339 FROM, which came from variable PTR. 4340 For variables that are actually dereferenced, we also use type 4341 based alias analysis to prune the points-to sets. */ 4342 4343static void 4344set_uids_in_ptset (tree ptr, bitmap into, bitmap from) 4345{ 4346 unsigned int i; 4347 bitmap_iterator bi; 4348 subvar_t sv; 4349 unsigned HOST_WIDE_INT ptr_alias_set = get_alias_set (TREE_TYPE (ptr)); 4350 4351 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi) 4352 { 4353 varinfo_t vi = get_varinfo (i); 4354 unsigned HOST_WIDE_INT var_alias_set; 4355 4356 /* The only artificial variables that are allowed in a may-alias 4357 set are heap variables. */ 4358 if (vi->is_artificial_var && !vi->is_heap_var) 4359 continue; 4360 4361 if (vi->has_union && get_subvars_for_var (vi->decl) != NULL) 4362 { 4363 /* Variables containing unions may need to be converted to 4364 their SFT's, because SFT's can have unions and we cannot. */ 4365 for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next) 4366 bitmap_set_bit (into, DECL_UID (sv->var)); 4367 } 4368 else if (TREE_CODE (vi->decl) == VAR_DECL 4369 || TREE_CODE (vi->decl) == PARM_DECL) 4370 { 4371 if (var_can_have_subvars (vi->decl) 4372 && get_subvars_for_var (vi->decl)) 4373 { 4374 /* If VI->DECL is an aggregate for which we created 4375 SFTs, add the SFT corresponding to VI->OFFSET. */ 4376 tree sft = get_subvar_at (vi->decl, vi->offset); 4377 if (sft) 4378 { 4379 var_alias_set = get_alias_set (sft); 4380 if (!vi->directly_dereferenced 4381 || alias_sets_conflict_p (ptr_alias_set, var_alias_set)) 4382 bitmap_set_bit (into, DECL_UID (sft)); 4383 } 4384 } 4385 else 4386 { 4387 /* Otherwise, just add VI->DECL to the alias set. 4388 Don't type prune artificial vars. */ 4389 if (vi->is_artificial_var) 4390 bitmap_set_bit (into, DECL_UID (vi->decl)); 4391 else 4392 { 4393 var_alias_set = get_alias_set (vi->decl); 4394 if (!vi->directly_dereferenced 4395 || alias_sets_conflict_p (ptr_alias_set, var_alias_set)) 4396 bitmap_set_bit (into, DECL_UID (vi->decl)); 4397 } 4398 } 4399 } 4400 } 4401} 4402 4403 4404static bool have_alias_info = false; 4405 4406/* Given a pointer variable P, fill in its points-to set, or return 4407 false if we can't. */ 4408 4409bool 4410find_what_p_points_to (tree p) 4411{ 4412 unsigned int id = 0; 4413 tree lookup_p = p; 4414 4415 if (!have_alias_info) 4416 return false; 4417 4418 /* For parameters, get at the points-to set for the actual parm 4419 decl. */ 4420 if (TREE_CODE (p) == SSA_NAME 4421 && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL 4422 && default_def (SSA_NAME_VAR (p)) == p) 4423 lookup_p = SSA_NAME_VAR (p); 4424 4425 if (lookup_id_for_tree (lookup_p, &id)) 4426 { 4427 varinfo_t vi = get_varinfo (id); 4428 4429 if (vi->is_artificial_var) 4430 return false; 4431 4432 /* See if this is a field or a structure. */ 4433 if (vi->size != vi->fullsize) 4434 { 4435 /* Nothing currently asks about structure fields directly, 4436 but when they do, we need code here to hand back the 4437 points-to set. */ 4438 if (!var_can_have_subvars (vi->decl) 4439 || get_subvars_for_var (vi->decl) == NULL) 4440 return false; 4441 } 4442 else 4443 { 4444 struct ptr_info_def *pi = get_ptr_info (p); 4445 unsigned int i; 4446 bitmap_iterator bi; 4447 4448 /* This variable may have been collapsed, let's get the real 4449 variable. */ 4450 vi = get_varinfo (vi->node); 4451 4452 /* Translate artificial variables into SSA_NAME_PTR_INFO 4453 attributes. */ 4454 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi) 4455 { 4456 varinfo_t vi = get_varinfo (i); 4457 4458 if (vi->is_artificial_var) 4459 { 4460 /* FIXME. READONLY should be handled better so that 4461 flow insensitive aliasing can disregard writable 4462 aliases. */ 4463 if (vi->id == nothing_id) 4464 pi->pt_null = 1; 4465 else if (vi->id == anything_id) 4466 pi->pt_anything = 1; 4467 else if (vi->id == readonly_id) 4468 pi->pt_anything = 1; 4469 else if (vi->id == integer_id) 4470 pi->pt_anything = 1; 4471 else if (vi->is_heap_var) 4472 pi->pt_global_mem = 1; 4473 } 4474 } 4475 4476 if (pi->pt_anything) 4477 return false; 4478 4479 if (!pi->pt_vars) 4480 pi->pt_vars = BITMAP_GGC_ALLOC (); 4481 4482 set_uids_in_ptset (vi->decl, pi->pt_vars, vi->solution); 4483 4484 if (bitmap_empty_p (pi->pt_vars)) 4485 pi->pt_vars = NULL; 4486 4487 return true; 4488 } 4489 } 4490 4491 return false; 4492} 4493 4494 4495 4496/* Dump points-to information to OUTFILE. */ 4497 4498void 4499dump_sa_points_to_info (FILE *outfile) 4500{ 4501 unsigned int i; 4502 4503 fprintf (outfile, "\nPoints-to sets\n\n"); 4504 4505 if (dump_flags & TDF_STATS) 4506 { 4507 fprintf (outfile, "Stats:\n"); 4508 fprintf (outfile, "Total vars: %d\n", stats.total_vars); 4509 fprintf (outfile, "Statically unified vars: %d\n", 4510 stats.unified_vars_static); 4511 fprintf (outfile, "Collapsed vars: %d\n", stats.collapsed_vars); 4512 fprintf (outfile, "Dynamically unified vars: %d\n", 4513 stats.unified_vars_dynamic); 4514 fprintf (outfile, "Iterations: %d\n", stats.iterations); 4515 fprintf (outfile, "Number of edges: %d\n", stats.num_edges); 4516 } 4517 4518 for (i = 0; i < VEC_length (varinfo_t, varmap); i++) 4519 dump_solution_for_var (outfile, i); 4520} 4521 4522 4523/* Debug points-to information to stderr. */ 4524 4525void 4526debug_sa_points_to_info (void) 4527{ 4528 dump_sa_points_to_info (stderr); 4529} 4530 4531 4532/* Initialize the always-existing constraint variables for NULL 4533 ANYTHING, READONLY, and INTEGER */ 4534 4535static void 4536init_base_vars (void) 4537{ 4538 struct constraint_expr lhs, rhs; 4539 4540 /* Create the NULL variable, used to represent that a variable points 4541 to NULL. */ 4542 nothing_tree = create_tmp_var_raw (void_type_node, "NULL"); 4543 var_nothing = new_var_info (nothing_tree, 0, "NULL", 0); 4544 insert_id_for_tree (nothing_tree, 0); 4545 var_nothing->is_artificial_var = 1; 4546 var_nothing->offset = 0; 4547 var_nothing->size = ~0; 4548 var_nothing->fullsize = ~0; 4549 var_nothing->is_special_var = 1; 4550 nothing_id = 0; 4551 VEC_safe_push (varinfo_t, heap, varmap, var_nothing); 4552 4553 /* Create the ANYTHING variable, used to represent that a variable 4554 points to some unknown piece of memory. */ 4555 anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING"); 4556 var_anything = new_var_info (anything_tree, 1, "ANYTHING", 1); 4557 insert_id_for_tree (anything_tree, 1); 4558 var_anything->is_artificial_var = 1; 4559 var_anything->size = ~0; 4560 var_anything->offset = 0; 4561 var_anything->next = NULL; 4562 var_anything->fullsize = ~0; 4563 var_anything->is_special_var = 1; 4564 anything_id = 1; 4565 4566 /* Anything points to anything. This makes deref constraints just 4567 work in the presence of linked list and other p = *p type loops, 4568 by saying that *ANYTHING = ANYTHING. */ 4569 VEC_safe_push (varinfo_t, heap, varmap, var_anything); 4570 lhs.type = SCALAR; 4571 lhs.var = anything_id; 4572 lhs.offset = 0; 4573 rhs.type = ADDRESSOF; 4574 rhs.var = anything_id; 4575 rhs.offset = 0; 4576 var_anything->address_taken = true; 4577 4578 /* This specifically does not use process_constraint because 4579 process_constraint ignores all anything = anything constraints, since all 4580 but this one are redundant. */ 4581 VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs)); 4582 4583 /* Create the READONLY variable, used to represent that a variable 4584 points to readonly memory. */ 4585 readonly_tree = create_tmp_var_raw (void_type_node, "READONLY"); 4586 var_readonly = new_var_info (readonly_tree, 2, "READONLY", 2); 4587 var_readonly->is_artificial_var = 1; 4588 var_readonly->offset = 0; 4589 var_readonly->size = ~0; 4590 var_readonly->fullsize = ~0; 4591 var_readonly->next = NULL; 4592 var_readonly->is_special_var = 1; 4593 insert_id_for_tree (readonly_tree, 2); 4594 readonly_id = 2; 4595 VEC_safe_push (varinfo_t, heap, varmap, var_readonly); 4596 4597 /* readonly memory points to anything, in order to make deref 4598 easier. In reality, it points to anything the particular 4599 readonly variable can point to, but we don't track this 4600 separately. */ 4601 lhs.type = SCALAR; 4602 lhs.var = readonly_id; 4603 lhs.offset = 0; 4604 rhs.type = ADDRESSOF; 4605 rhs.var = anything_id; 4606 rhs.offset = 0; 4607 4608 process_constraint (new_constraint (lhs, rhs)); 4609 4610 /* Create the INTEGER variable, used to represent that a variable points 4611 to an INTEGER. */ 4612 integer_tree = create_tmp_var_raw (void_type_node, "INTEGER"); 4613 var_integer = new_var_info (integer_tree, 3, "INTEGER", 3); 4614 insert_id_for_tree (integer_tree, 3); 4615 var_integer->is_artificial_var = 1; 4616 var_integer->size = ~0; 4617 var_integer->fullsize = ~0; 4618 var_integer->offset = 0; 4619 var_integer->next = NULL; 4620 var_integer->is_special_var = 1; 4621 integer_id = 3; 4622 VEC_safe_push (varinfo_t, heap, varmap, var_integer); 4623 4624 /* INTEGER = ANYTHING, because we don't know where a dereference of 4625 a random integer will point to. */ 4626 lhs.type = SCALAR; 4627 lhs.var = integer_id; 4628 lhs.offset = 0; 4629 rhs.type = ADDRESSOF; 4630 rhs.var = anything_id; 4631 rhs.offset = 0; 4632 process_constraint (new_constraint (lhs, rhs)); 4633 4634 /* Create the ESCAPED_VARS variable used to represent variables that 4635 escape this function. */ 4636 escaped_vars_tree = create_tmp_var_raw (void_type_node, "ESCAPED_VARS"); 4637 var_escaped_vars = new_var_info (escaped_vars_tree, 4, "ESCAPED_VARS", 4); 4638 insert_id_for_tree (escaped_vars_tree, 4); 4639 var_escaped_vars->is_artificial_var = 1; 4640 var_escaped_vars->size = ~0; 4641 var_escaped_vars->fullsize = ~0; 4642 var_escaped_vars->offset = 0; 4643 var_escaped_vars->next = NULL; 4644 escaped_vars_id = 4; 4645 VEC_safe_push (varinfo_t, heap, varmap, var_escaped_vars); 4646 4647 /* ESCAPED_VARS = *ESCAPED_VARS */ 4648 lhs.type = SCALAR; 4649 lhs.var = escaped_vars_id; 4650 lhs.offset = 0; 4651 rhs.type = DEREF; 4652 rhs.var = escaped_vars_id; 4653 rhs.offset = 0; 4654 process_constraint (new_constraint (lhs, rhs)); 4655 4656} 4657 4658/* Initialize things necessary to perform PTA */ 4659 4660static void 4661init_alias_vars (void) 4662{ 4663 bitmap_obstack_initialize (&ptabitmap_obstack); 4664 bitmap_obstack_initialize (&predbitmap_obstack); 4665 4666 constraint_pool = create_alloc_pool ("Constraint pool", 4667 sizeof (struct constraint), 30); 4668 variable_info_pool = create_alloc_pool ("Variable info pool", 4669 sizeof (struct variable_info), 30); 4670 constraint_edge_pool = create_alloc_pool ("Constraint edges", 4671 sizeof (struct constraint_edge), 30); 4672 4673 constraints = VEC_alloc (constraint_t, heap, 8); 4674 varmap = VEC_alloc (varinfo_t, heap, 8); 4675 id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free); 4676 memset (&stats, 0, sizeof (stats)); 4677 4678 init_base_vars (); 4679} 4680 4681/* Given a statement STMT, generate necessary constraints to 4682 escaped_vars for the escaping variables. */ 4683 4684static void 4685find_escape_constraints (tree stmt) 4686{ 4687 enum escape_type stmt_escape_type = is_escape_site (stmt); 4688 tree rhs; 4689 VEC(ce_s, heap) *rhsc = NULL; 4690 struct constraint_expr *c; 4691 size_t i; 4692 4693 if (stmt_escape_type == NO_ESCAPE) 4694 return; 4695 4696 if (TREE_CODE (stmt) == RETURN_EXPR) 4697 { 4698 /* Returns are either bare, with an embedded MODIFY_EXPR, or 4699 just a plain old expression. */ 4700 if (!TREE_OPERAND (stmt, 0)) 4701 return; 4702 if (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) 4703 rhs = TREE_OPERAND (TREE_OPERAND (stmt, 0), 1); 4704 else 4705 rhs = TREE_OPERAND (stmt, 0); 4706 4707 get_constraint_for (rhs, &rhsc); 4708 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) 4709 make_constraint_to_escaped (*c); 4710 VEC_free (ce_s, heap, rhsc); 4711 return; 4712 } 4713 else if (TREE_CODE (stmt) == ASM_EXPR) 4714 { 4715 /* Whatever the inputs of the ASM are, escape. */ 4716 tree arg; 4717 4718 for (arg = ASM_INPUTS (stmt); arg; arg = TREE_CHAIN (arg)) 4719 { 4720 rhsc = NULL; 4721 get_constraint_for (TREE_VALUE (arg), &rhsc); 4722 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) 4723 make_constraint_to_escaped (*c); 4724 VEC_free (ce_s, heap, rhsc); 4725 } 4726 return; 4727 } 4728 else if (TREE_CODE (stmt) == CALL_EXPR 4729 || (TREE_CODE (stmt) == MODIFY_EXPR 4730 && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR)) 4731 { 4732 /* Calls cause all of the arguments passed in to escape. */ 4733 tree arg; 4734 4735 if (TREE_CODE (stmt) == MODIFY_EXPR) 4736 stmt = TREE_OPERAND (stmt, 1); 4737 for (arg = TREE_OPERAND (stmt, 1); arg; arg = TREE_CHAIN (arg)) 4738 { 4739 if (POINTER_TYPE_P (TREE_TYPE (TREE_VALUE (arg)))) 4740 { 4741 rhsc = NULL; 4742 get_constraint_for (TREE_VALUE (arg), &rhsc); 4743 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) 4744 make_constraint_to_escaped (*c); 4745 VEC_free (ce_s, heap, rhsc); 4746 } 4747 } 4748 return; 4749 } 4750 else 4751 { 4752 gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR); 4753 } 4754 4755 gcc_assert (stmt_escape_type == ESCAPE_BAD_CAST 4756 || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL 4757 || stmt_escape_type == ESCAPE_UNKNOWN); 4758 rhs = TREE_OPERAND (stmt, 1); 4759 4760 /* Look through casts for the real escaping variable. 4761 Constants don't really escape, so ignore them. 4762 Otherwise, whatever escapes must be on our RHS. */ 4763 if (TREE_CODE (rhs) == NOP_EXPR 4764 || TREE_CODE (rhs) == CONVERT_EXPR 4765 || TREE_CODE (rhs) == NON_LVALUE_EXPR) 4766 { 4767 get_constraint_for (TREE_OPERAND (rhs, 0), &rhsc); 4768 } 4769 else if (CONSTANT_CLASS_P (rhs)) 4770 return; 4771 else 4772 { 4773 get_constraint_for (rhs, &rhsc); 4774 } 4775 for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) 4776 make_constraint_to_escaped (*c); 4777 VEC_free (ce_s, heap, rhsc); 4778} 4779 4780/* Create points-to sets for the current function. See the comments 4781 at the start of the file for an algorithmic overview. */ 4782 4783void 4784compute_points_to_sets (struct alias_info *ai) 4785{ 4786 basic_block bb; 4787 4788 timevar_push (TV_TREE_PTA); 4789 4790 init_alias_vars (); 4791 4792 intra_create_variable_infos (); 4793 4794 /* Now walk all statements and derive aliases. */ 4795 FOR_EACH_BB (bb) 4796 { 4797 block_stmt_iterator bsi; 4798 tree phi; 4799 4800 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) 4801 { 4802 if (is_gimple_reg (PHI_RESULT (phi))) 4803 { 4804 find_func_aliases (phi); 4805 /* Update various related attributes like escaped 4806 addresses, pointer dereferences for loads and stores. 4807 This is used when creating name tags and alias 4808 sets. */ 4809 update_alias_info (phi, ai); 4810 } 4811 } 4812 4813 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 4814 { 4815 tree stmt = bsi_stmt (bsi); 4816 4817 find_func_aliases (stmt); 4818 find_escape_constraints (stmt); 4819 /* Update various related attributes like escaped 4820 addresses, pointer dereferences for loads and stores. 4821 This is used when creating name tags and alias 4822 sets. */ 4823 update_alias_info (stmt, ai); 4824 } 4825 } 4826 4827 build_constraint_graph (); 4828 4829 if (dump_file) 4830 { 4831 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n"); 4832 dump_constraints (dump_file); 4833 } 4834 4835 if (dump_file) 4836 fprintf (dump_file, 4837 "\nCollapsing static cycles and doing variable " 4838 "substitution:\n"); 4839 4840 find_and_collapse_graph_cycles (graph, false); 4841 perform_var_substitution (graph); 4842 4843 if (dump_file) 4844 fprintf (dump_file, "\nSolving graph:\n"); 4845 4846 solve_graph (graph); 4847 4848 if (dump_file) 4849 dump_sa_points_to_info (dump_file); 4850 4851 have_alias_info = true; 4852 4853 timevar_pop (TV_TREE_PTA); 4854} 4855 4856 4857/* Delete created points-to sets. */ 4858 4859void 4860delete_points_to_sets (void) 4861{ 4862 varinfo_t v; 4863 int i; 4864 4865 htab_delete (id_for_tree); 4866 bitmap_obstack_release (&ptabitmap_obstack); 4867 bitmap_obstack_release (&predbitmap_obstack); 4868 VEC_free (constraint_t, heap, constraints); 4869 4870 for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++) 4871 { 4872 /* Nonlocal vars may add more varinfos. */ 4873 if (i >= graph_size) 4874 break; 4875 4876 VEC_free (constraint_edge_t, heap, graph->succs[i]); 4877 VEC_free (constraint_edge_t, heap, graph->preds[i]); 4878 VEC_free (constraint_t, heap, v->complex); 4879 } 4880 free (graph->zero_weight_preds); 4881 free (graph->zero_weight_succs); 4882 free (graph->succs); 4883 free (graph->preds); 4884 free (graph); 4885 4886 VEC_free (varinfo_t, heap, varmap); 4887 free_alloc_pool (variable_info_pool); 4888 free_alloc_pool (constraint_pool); 4889 free_alloc_pool (constraint_edge_pool); 4890 4891 have_alias_info = false; 4892} 4893 4894/* Return true if we should execute IPA PTA. */ 4895static bool 4896gate_ipa_pta (void) 4897{ 4898 return (flag_unit_at_a_time != 0 4899 && flag_ipa_pta 4900 /* Don't bother doing anything if the program has errors. */ 4901 && !(errorcount || sorrycount)); 4902} 4903 4904/* Execute the driver for IPA PTA. */ 4905static unsigned int 4906ipa_pta_execute (void) 4907{ 4908 struct cgraph_node *node; 4909 in_ipa_mode = 1; 4910 init_alias_heapvars (); 4911 init_alias_vars (); 4912 4913 for (node = cgraph_nodes; node; node = node->next) 4914 { 4915 if (!node->analyzed || cgraph_is_master_clone (node)) 4916 { 4917 unsigned int varid; 4918 4919 varid = create_function_info_for (node->decl, 4920 cgraph_node_name (node)); 4921 if (node->local.externally_visible) 4922 { 4923 varinfo_t fi = get_varinfo (varid); 4924 for (; fi; fi = fi->next) 4925 make_constraint_from_escaped (fi); 4926 } 4927 } 4928 } 4929 for (node = cgraph_nodes; node; node = node->next) 4930 { 4931 if (node->analyzed && cgraph_is_master_clone (node)) 4932 { 4933 struct function *cfun = DECL_STRUCT_FUNCTION (node->decl); 4934 basic_block bb; 4935 tree old_func_decl = current_function_decl; 4936 if (dump_file) 4937 fprintf (dump_file, 4938 "Generating constraints for %s\n", 4939 cgraph_node_name (node)); 4940 push_cfun (cfun); 4941 current_function_decl = node->decl; 4942 4943 FOR_EACH_BB_FN (bb, cfun) 4944 { 4945 block_stmt_iterator bsi; 4946 tree phi; 4947 4948 for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) 4949 { 4950 if (is_gimple_reg (PHI_RESULT (phi))) 4951 { 4952 find_func_aliases (phi); 4953 } 4954 } 4955 4956 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 4957 { 4958 tree stmt = bsi_stmt (bsi); 4959 find_func_aliases (stmt); 4960 } 4961 } 4962 current_function_decl = old_func_decl; 4963 pop_cfun (); 4964 } 4965 else 4966 { 4967 /* Make point to anything. */ 4968 } 4969 } 4970 4971 build_constraint_graph (); 4972 4973 if (dump_file) 4974 { 4975 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n"); 4976 dump_constraints (dump_file); 4977 } 4978 4979 if (dump_file) 4980 fprintf (dump_file, 4981 "\nCollapsing static cycles and doing variable " 4982 "substitution:\n"); 4983 4984 find_and_collapse_graph_cycles (graph, false); 4985 perform_var_substitution (graph); 4986 4987 if (dump_file) 4988 fprintf (dump_file, "\nSolving graph:\n"); 4989 4990 solve_graph (graph); 4991 4992 if (dump_file) 4993 dump_sa_points_to_info (dump_file); 4994 in_ipa_mode = 0; 4995 delete_alias_heapvars (); 4996 delete_points_to_sets (); 4997 return 0; 4998} 4999 5000struct tree_opt_pass pass_ipa_pta = 5001{ 5002 "pta", /* name */ 5003 gate_ipa_pta, /* gate */ 5004 ipa_pta_execute, /* execute */ 5005 NULL, /* sub */ 5006 NULL, /* next */ 5007 0, /* static_pass_number */ 5008 TV_IPA_PTA, /* tv_id */ 5009 0, /* properties_required */ 5010 0, /* properties_provided */ 5011 0, /* properties_destroyed */ 5012 0, /* todo_flags_start */ 5013 0, /* todo_flags_finish */ 5014 0 /* letter */ 5015}; 5016 5017/* Initialize the heapvar for statement mapping. */ 5018void 5019init_alias_heapvars (void) 5020{ 5021 heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq, 5022 NULL); 5023 nonlocal_all = NULL_TREE; 5024} 5025 5026void 5027delete_alias_heapvars (void) 5028{ 5029 nonlocal_all = NULL_TREE; 5030 htab_delete (heapvar_for_stmt); 5031} 5032 5033 5034#include "gt-tree-ssa-structalias.h" 5035