1 /* Tree based points-to analysis 2 Copyright (C) 2005-2016 Free Software Foundation, Inc. 3 Contributed by Daniel Berlin <dberlin@dberlin.org> 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify 8 under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 3 of the License, or 10 (at your option) any later version. 11 12 GCC is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "backend.h" 25 #include "rtl.h" 26 #include "tree.h" 27 #include "gimple.h" 28 #include "alloc-pool.h" 29 #include "tree-pass.h" 30 #include "ssa.h" 31 #include "cgraph.h" 32 #include "tree-pretty-print.h" 33 #include "diagnostic-core.h" 34 #include "fold-const.h" 35 #include "stor-layout.h" 36 #include "stmt.h" 37 #include "gimple-iterator.h" 38 #include "tree-into-ssa.h" 39 #include "tree-dfa.h" 40 #include "params.h" 41 #include "gimple-walk.h" 42 43 /* The idea behind this analyzer is to generate set constraints from the 44 program, then solve the resulting constraints in order to generate the 45 points-to sets. 46 47 Set constraints are a way of modeling program analysis problems that 48 involve sets. They consist of an inclusion constraint language, 49 describing the variables (each variable is a set) and operations that 50 are involved on the variables, and a set of rules that derive facts 51 from these operations. To solve a system of set constraints, you derive 52 all possible facts under the rules, which gives you the correct sets 53 as a consequence. 54 55 See "Efficient Field-sensitive pointer analysis for C" by "David 56 J. Pearce and Paul H. J. Kelly and Chris Hankin, at 57 http://citeseer.ist.psu.edu/pearce04efficient.html 58 59 Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines 60 of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at 61 http://citeseer.ist.psu.edu/heintze01ultrafast.html 62 63 There are three types of real constraint expressions, DEREF, 64 ADDRESSOF, and SCALAR. Each constraint expression consists 65 of a constraint type, a variable, and an offset. 66 67 SCALAR is a constraint expression type used to represent x, whether 68 it appears on the LHS or the RHS of a statement. 69 DEREF is a constraint expression type used to represent *x, whether 70 it appears on the LHS or the RHS of a statement. 71 ADDRESSOF is a constraint expression used to represent &x, whether 72 it appears on the LHS or the RHS of a statement. 73 74 Each pointer variable in the program is assigned an integer id, and 75 each field of a structure variable is assigned an integer id as well. 76 77 Structure variables are linked to their list of fields through a "next 78 field" in each variable that points to the next field in offset 79 order. 80 Each variable for a structure field has 81 82 1. "size", that tells the size in bits of that field. 83 2. "fullsize, that tells the size in bits of the entire structure. 84 3. "offset", that tells the offset in bits from the beginning of the 85 structure to this field. 86 87 Thus, 88 struct f 89 { 90 int a; 91 int b; 92 } foo; 93 int *bar; 94 95 looks like 96 97 foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b 98 foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL 99 bar -> id 3, size 32, offset 0, fullsize 32, next NULL 100 101 102 In order to solve the system of set constraints, the following is 103 done: 104 105 1. Each constraint variable x has a solution set associated with it, 106 Sol(x). 107 108 2. Constraints are separated into direct, copy, and complex. 109 Direct constraints are ADDRESSOF constraints that require no extra 110 processing, such as P = &Q 111 Copy constraints are those of the form P = Q. 112 Complex constraints are all the constraints involving dereferences 113 and offsets (including offsetted copies). 114 115 3. All direct constraints of the form P = &Q are processed, such 116 that Q is added to Sol(P) 117 118 4. All complex constraints for a given constraint variable are stored in a 119 linked list attached to that variable's node. 120 121 5. A directed graph is built out of the copy constraints. Each 122 constraint variable is a node in the graph, and an edge from 123 Q to P is added for each copy constraint of the form P = Q 124 125 6. The graph is then walked, and solution sets are 126 propagated along the copy edges, such that an edge from Q to P 127 causes Sol(P) <- Sol(P) union Sol(Q). 128 129 7. As we visit each node, all complex constraints associated with 130 that node are processed by adding appropriate copy edges to the graph, or the 131 appropriate variables to the solution set. 132 133 8. The process of walking the graph is iterated until no solution 134 sets change. 135 136 Prior to walking the graph in steps 6 and 7, We perform static 137 cycle elimination on the constraint graph, as well 138 as off-line variable substitution. 139 140 TODO: Adding offsets to pointer-to-structures can be handled (IE not punted 141 on and turned into anything), but isn't. You can just see what offset 142 inside the pointed-to struct it's going to access. 143 144 TODO: Constant bounded arrays can be handled as if they were structs of the 145 same number of elements. 146 147 TODO: Modeling heap and incoming pointers becomes much better if we 148 add fields to them as we discover them, which we could do. 149 150 TODO: We could handle unions, but to be honest, it's probably not 151 worth the pain or slowdown. */ 152 153 /* IPA-PTA optimizations possible. 154 155 When the indirect function called is ANYTHING we can add disambiguation 156 based on the function signatures (or simply the parameter count which 157 is the varinfo size). We also do not need to consider functions that 158 do not have their address taken. 159 160 The is_global_var bit which marks escape points is overly conservative 161 in IPA mode. Split it to is_escape_point and is_global_var - only 162 externally visible globals are escape points in IPA mode. 163 There is now is_ipa_escape_point but this is only used in a few 164 selected places. 165 166 The way we introduce DECL_PT_UID to avoid fixing up all points-to 167 sets in the translation unit when we copy a DECL during inlining 168 pessimizes precision. The advantage is that the DECL_PT_UID keeps 169 compile-time and memory usage overhead low - the points-to sets 170 do not grow or get unshared as they would during a fixup phase. 171 An alternative solution is to delay IPA PTA until after all 172 inlining transformations have been applied. 173 174 The way we propagate clobber/use information isn't optimized. 175 It should use a new complex constraint that properly filters 176 out local variables of the callee (though that would make 177 the sets invalid after inlining). OTOH we might as well 178 admit defeat to WHOPR and simply do all the clobber/use analysis 179 and propagation after PTA finished but before we threw away 180 points-to information for memory variables. WHOPR and PTA 181 do not play along well anyway - the whole constraint solving 182 would need to be done in WPA phase and it will be very interesting 183 to apply the results to local SSA names during LTRANS phase. 184 185 We probably should compute a per-function unit-ESCAPE solution 186 propagating it simply like the clobber / uses solutions. The 187 solution can go alongside the non-IPA espaced solution and be 188 used to query which vars escape the unit through a function. 189 This is also required to make the escaped-HEAP trick work in IPA mode. 190 191 We never put function decls in points-to sets so we do not 192 keep the set of called functions for indirect calls. 193 194 And probably more. */ 195 196 static bool use_field_sensitive = true; 197 static int in_ipa_mode = 0; 198 199 /* Used for predecessor bitmaps. */ 200 static bitmap_obstack predbitmap_obstack; 201 202 /* Used for points-to sets. */ 203 static bitmap_obstack pta_obstack; 204 205 /* Used for oldsolution members of variables. */ 206 static bitmap_obstack oldpta_obstack; 207 208 /* Used for per-solver-iteration bitmaps. */ 209 static bitmap_obstack iteration_obstack; 210 211 static unsigned int create_variable_info_for (tree, const char *, bool); 212 typedef struct constraint_graph *constraint_graph_t; 213 static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool); 214 215 struct constraint; 216 typedef struct constraint *constraint_t; 217 218 219 #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \ 220 if (a) \ 221 EXECUTE_IF_SET_IN_BITMAP (a, b, c, d) 222 223 static struct constraint_stats 224 { 225 unsigned int total_vars; 226 unsigned int nonpointer_vars; 227 unsigned int unified_vars_static; 228 unsigned int unified_vars_dynamic; 229 unsigned int iterations; 230 unsigned int num_edges; 231 unsigned int num_implicit_edges; 232 unsigned int points_to_sets_created; 233 } stats; 234 235 struct variable_info 236 { 237 /* ID of this variable */ 238 unsigned int id; 239 240 /* True if this is a variable created by the constraint analysis, such as 241 heap variables and constraints we had to break up. */ 242 unsigned int is_artificial_var : 1; 243 244 /* True if this is a special variable whose solution set should not be 245 changed. */ 246 unsigned int is_special_var : 1; 247 248 /* True for variables whose size is not known or variable. */ 249 unsigned int is_unknown_size_var : 1; 250 251 /* True for (sub-)fields that represent a whole variable. */ 252 unsigned int is_full_var : 1; 253 254 /* True if this is a heap variable. */ 255 unsigned int is_heap_var : 1; 256 257 /* True if this field may contain pointers. */ 258 unsigned int may_have_pointers : 1; 259 260 /* True if this field has only restrict qualified pointers. */ 261 unsigned int only_restrict_pointers : 1; 262 263 /* True if this represents a heap var created for a restrict qualified 264 pointer. */ 265 unsigned int is_restrict_var : 1; 266 267 /* True if this represents a global variable. */ 268 unsigned int is_global_var : 1; 269 270 /* True if this represents a module escape point for IPA analysis. */ 271 unsigned int is_ipa_escape_point : 1; 272 273 /* True if this represents a IPA function info. */ 274 unsigned int is_fn_info : 1; 275 276 /* ??? Store somewhere better. */ 277 unsigned short ruid; 278 279 /* The ID of the variable for the next field in this structure 280 or zero for the last field in this structure. */ 281 unsigned next; 282 283 /* The ID of the variable for the first field in this structure. */ 284 unsigned head; 285 286 /* Offset of this variable, in bits, from the base variable */ 287 unsigned HOST_WIDE_INT offset; 288 289 /* Size of the variable, in bits. */ 290 unsigned HOST_WIDE_INT size; 291 292 /* Full size of the base variable, in bits. */ 293 unsigned HOST_WIDE_INT fullsize; 294 295 /* Name of this variable */ 296 const char *name; 297 298 /* Tree that this variable is associated with. */ 299 tree decl; 300 301 /* Points-to set for this variable. */ 302 bitmap solution; 303 304 /* Old points-to set for this variable. */ 305 bitmap oldsolution; 306 }; 307 typedef struct variable_info *varinfo_t; 308 309 static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT); 310 static varinfo_t first_or_preceding_vi_for_offset (varinfo_t, 311 unsigned HOST_WIDE_INT); 312 static varinfo_t lookup_vi_for_tree (tree); 313 static inline bool type_can_have_subvars (const_tree); 314 static void make_param_constraints (varinfo_t); 315 316 /* Pool of variable info structures. */ 317 static object_allocator<variable_info> variable_info_pool 318 ("Variable info pool"); 319 320 /* Map varinfo to final pt_solution. */ 321 static hash_map<varinfo_t, pt_solution *> *final_solutions; 322 struct obstack final_solutions_obstack; 323 324 /* Table of variable info structures for constraint variables. 325 Indexed directly by variable info id. */ 326 static vec<varinfo_t> varmap; 327 328 /* Return the varmap element N */ 329 330 static inline varinfo_t 331 get_varinfo (unsigned int n) 332 { 333 return varmap[n]; 334 } 335 336 /* Return the next variable in the list of sub-variables of VI 337 or NULL if VI is the last sub-variable. */ 338 339 static inline varinfo_t 340 vi_next (varinfo_t vi) 341 { 342 return get_varinfo (vi->next); 343 } 344 345 /* Static IDs for the special variables. Variable ID zero is unused 346 and used as terminator for the sub-variable chain. */ 347 enum { nothing_id = 1, anything_id = 2, string_id = 3, 348 escaped_id = 4, nonlocal_id = 5, 349 storedanything_id = 6, integer_id = 7 }; 350 351 /* Return a new variable info structure consisting for a variable 352 named NAME, and using constraint graph node NODE. Append it 353 to the vector of variable info structures. */ 354 355 static varinfo_t 356 new_var_info (tree t, const char *name, bool add_id) 357 { 358 unsigned index = varmap.length (); 359 varinfo_t ret = variable_info_pool.allocate (); 360 361 if (dump_file && add_id) 362 { 363 char *tempname = xasprintf ("%s(%d)", name, index); 364 name = ggc_strdup (tempname); 365 free (tempname); 366 } 367 368 ret->id = index; 369 ret->name = name; 370 ret->decl = t; 371 /* Vars without decl are artificial and do not have sub-variables. */ 372 ret->is_artificial_var = (t == NULL_TREE); 373 ret->is_special_var = false; 374 ret->is_unknown_size_var = false; 375 ret->is_full_var = (t == NULL_TREE); 376 ret->is_heap_var = false; 377 ret->may_have_pointers = true; 378 ret->only_restrict_pointers = false; 379 ret->is_restrict_var = false; 380 ret->ruid = 0; 381 ret->is_global_var = (t == NULL_TREE); 382 ret->is_ipa_escape_point = false; 383 ret->is_fn_info = false; 384 if (t && DECL_P (t)) 385 ret->is_global_var = (is_global_var (t) 386 /* We have to treat even local register variables 387 as escape points. */ 388 || (TREE_CODE (t) == VAR_DECL 389 && DECL_HARD_REGISTER (t))); 390 ret->solution = BITMAP_ALLOC (&pta_obstack); 391 ret->oldsolution = NULL; 392 ret->next = 0; 393 ret->head = ret->id; 394 395 stats.total_vars++; 396 397 varmap.safe_push (ret); 398 399 return ret; 400 } 401 402 /* A map mapping call statements to per-stmt variables for uses 403 and clobbers specific to the call. */ 404 static hash_map<gimple *, varinfo_t> *call_stmt_vars; 405 406 /* Lookup or create the variable for the call statement CALL. */ 407 408 static varinfo_t 409 get_call_vi (gcall *call) 410 { 411 varinfo_t vi, vi2; 412 413 bool existed; 414 varinfo_t *slot_p = &call_stmt_vars->get_or_insert (call, &existed); 415 if (existed) 416 return *slot_p; 417 418 vi = new_var_info (NULL_TREE, "CALLUSED", true); 419 vi->offset = 0; 420 vi->size = 1; 421 vi->fullsize = 2; 422 vi->is_full_var = true; 423 424 vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED", true); 425 vi2->offset = 1; 426 vi2->size = 1; 427 vi2->fullsize = 2; 428 vi2->is_full_var = true; 429 430 vi->next = vi2->id; 431 432 *slot_p = vi; 433 return vi; 434 } 435 436 /* Lookup the variable for the call statement CALL representing 437 the uses. Returns NULL if there is nothing special about this call. */ 438 439 static varinfo_t 440 lookup_call_use_vi (gcall *call) 441 { 442 varinfo_t *slot_p = call_stmt_vars->get (call); 443 if (slot_p) 444 return *slot_p; 445 446 return NULL; 447 } 448 449 /* Lookup the variable for the call statement CALL representing 450 the clobbers. Returns NULL if there is nothing special about this call. */ 451 452 static varinfo_t 453 lookup_call_clobber_vi (gcall *call) 454 { 455 varinfo_t uses = lookup_call_use_vi (call); 456 if (!uses) 457 return NULL; 458 459 return vi_next (uses); 460 } 461 462 /* Lookup or create the variable for the call statement CALL representing 463 the uses. */ 464 465 static varinfo_t 466 get_call_use_vi (gcall *call) 467 { 468 return get_call_vi (call); 469 } 470 471 /* Lookup or create the variable for the call statement CALL representing 472 the clobbers. */ 473 474 static varinfo_t ATTRIBUTE_UNUSED 475 get_call_clobber_vi (gcall *call) 476 { 477 return vi_next (get_call_vi (call)); 478 } 479 480 481 enum constraint_expr_type {SCALAR, DEREF, ADDRESSOF}; 482 483 /* An expression that appears in a constraint. */ 484 485 struct constraint_expr 486 { 487 /* Constraint type. */ 488 constraint_expr_type type; 489 490 /* Variable we are referring to in the constraint. */ 491 unsigned int var; 492 493 /* Offset, in bits, of this constraint from the beginning of 494 variables it ends up referring to. 495 496 IOW, in a deref constraint, we would deref, get the result set, 497 then add OFFSET to each member. */ 498 HOST_WIDE_INT offset; 499 }; 500 501 /* Use 0x8000... as special unknown offset. */ 502 #define UNKNOWN_OFFSET HOST_WIDE_INT_MIN 503 504 typedef struct constraint_expr ce_s; 505 static void get_constraint_for_1 (tree, vec<ce_s> *, bool, bool); 506 static void get_constraint_for (tree, vec<ce_s> *); 507 static void get_constraint_for_rhs (tree, vec<ce_s> *); 508 static void do_deref (vec<ce_s> *); 509 510 /* Our set constraints are made up of two constraint expressions, one 511 LHS, and one RHS. 512 513 As described in the introduction, our set constraints each represent an 514 operation between set valued variables. 515 */ 516 struct constraint 517 { 518 struct constraint_expr lhs; 519 struct constraint_expr rhs; 520 }; 521 522 /* List of constraints that we use to build the constraint graph from. */ 523 524 static vec<constraint_t> constraints; 525 static object_allocator<constraint> constraint_pool ("Constraint pool"); 526 527 /* The constraint graph is represented as an array of bitmaps 528 containing successor nodes. */ 529 530 struct constraint_graph 531 { 532 /* Size of this graph, which may be different than the number of 533 nodes in the variable map. */ 534 unsigned int size; 535 536 /* Explicit successors of each node. */ 537 bitmap *succs; 538 539 /* Implicit predecessors of each node (Used for variable 540 substitution). */ 541 bitmap *implicit_preds; 542 543 /* Explicit predecessors of each node (Used for variable substitution). */ 544 bitmap *preds; 545 546 /* Indirect cycle representatives, or -1 if the node has no indirect 547 cycles. */ 548 int *indirect_cycles; 549 550 /* Representative node for a node. rep[a] == a unless the node has 551 been unified. */ 552 unsigned int *rep; 553 554 /* Equivalence class representative for a label. This is used for 555 variable substitution. */ 556 int *eq_rep; 557 558 /* Pointer equivalence label for a node. All nodes with the same 559 pointer equivalence label can be unified together at some point 560 (either during constraint optimization or after the constraint 561 graph is built). */ 562 unsigned int *pe; 563 564 /* Pointer equivalence representative for a label. This is used to 565 handle nodes that are pointer equivalent but not location 566 equivalent. We can unite these once the addressof constraints 567 are transformed into initial points-to sets. */ 568 int *pe_rep; 569 570 /* Pointer equivalence label for each node, used during variable 571 substitution. */ 572 unsigned int *pointer_label; 573 574 /* Location equivalence label for each node, used during location 575 equivalence finding. */ 576 unsigned int *loc_label; 577 578 /* Pointed-by set for each node, used during location equivalence 579 finding. This is pointed-by rather than pointed-to, because it 580 is constructed using the predecessor graph. */ 581 bitmap *pointed_by; 582 583 /* Points to sets for pointer equivalence. This is *not* the actual 584 points-to sets for nodes. */ 585 bitmap *points_to; 586 587 /* Bitmap of nodes where the bit is set if the node is a direct 588 node. Used for variable substitution. */ 589 sbitmap direct_nodes; 590 591 /* Bitmap of nodes where the bit is set if the node is address 592 taken. Used for variable substitution. */ 593 bitmap address_taken; 594 595 /* Vector of complex constraints for each graph node. Complex 596 constraints are those involving dereferences or offsets that are 597 not 0. */ 598 vec<constraint_t> *complex; 599 }; 600 601 static constraint_graph_t graph; 602 603 /* During variable substitution and the offline version of indirect 604 cycle finding, we create nodes to represent dereferences and 605 address taken constraints. These represent where these start and 606 end. */ 607 #define FIRST_REF_NODE (varmap).length () 608 #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1)) 609 610 /* Return the representative node for NODE, if NODE has been unioned 611 with another NODE. 612 This function performs path compression along the way to finding 613 the representative. */ 614 615 static unsigned int 616 find (unsigned int node) 617 { 618 gcc_checking_assert (node < graph->size); 619 if (graph->rep[node] != node) 620 return graph->rep[node] = find (graph->rep[node]); 621 return node; 622 } 623 624 /* Union the TO and FROM nodes to the TO nodes. 625 Note that at some point in the future, we may want to do 626 union-by-rank, in which case we are going to have to return the 627 node we unified to. */ 628 629 static bool 630 unite (unsigned int to, unsigned int from) 631 { 632 gcc_checking_assert (to < graph->size && from < graph->size); 633 if (to != from && graph->rep[from] != to) 634 { 635 graph->rep[from] = to; 636 return true; 637 } 638 return false; 639 } 640 641 /* Create a new constraint consisting of LHS and RHS expressions. */ 642 643 static constraint_t 644 new_constraint (const struct constraint_expr lhs, 645 const struct constraint_expr rhs) 646 { 647 constraint_t ret = constraint_pool.allocate (); 648 ret->lhs = lhs; 649 ret->rhs = rhs; 650 return ret; 651 } 652 653 /* Print out constraint C to FILE. */ 654 655 static void 656 dump_constraint (FILE *file, constraint_t c) 657 { 658 if (c->lhs.type == ADDRESSOF) 659 fprintf (file, "&"); 660 else if (c->lhs.type == DEREF) 661 fprintf (file, "*"); 662 fprintf (file, "%s", get_varinfo (c->lhs.var)->name); 663 if (c->lhs.offset == UNKNOWN_OFFSET) 664 fprintf (file, " + UNKNOWN"); 665 else if (c->lhs.offset != 0) 666 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset); 667 fprintf (file, " = "); 668 if (c->rhs.type == ADDRESSOF) 669 fprintf (file, "&"); 670 else if (c->rhs.type == DEREF) 671 fprintf (file, "*"); 672 fprintf (file, "%s", get_varinfo (c->rhs.var)->name); 673 if (c->rhs.offset == UNKNOWN_OFFSET) 674 fprintf (file, " + UNKNOWN"); 675 else if (c->rhs.offset != 0) 676 fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset); 677 } 678 679 680 void debug_constraint (constraint_t); 681 void debug_constraints (void); 682 void debug_constraint_graph (void); 683 void debug_solution_for_var (unsigned int); 684 void debug_sa_points_to_info (void); 685 686 /* Print out constraint C to stderr. */ 687 688 DEBUG_FUNCTION void 689 debug_constraint (constraint_t c) 690 { 691 dump_constraint (stderr, c); 692 fprintf (stderr, "\n"); 693 } 694 695 /* Print out all constraints to FILE */ 696 697 static void 698 dump_constraints (FILE *file, int from) 699 { 700 int i; 701 constraint_t c; 702 for (i = from; constraints.iterate (i, &c); i++) 703 if (c) 704 { 705 dump_constraint (file, c); 706 fprintf (file, "\n"); 707 } 708 } 709 710 /* Print out all constraints to stderr. */ 711 712 DEBUG_FUNCTION void 713 debug_constraints (void) 714 { 715 dump_constraints (stderr, 0); 716 } 717 718 /* Print the constraint graph in dot format. */ 719 720 static void 721 dump_constraint_graph (FILE *file) 722 { 723 unsigned int i; 724 725 /* Only print the graph if it has already been initialized: */ 726 if (!graph) 727 return; 728 729 /* Prints the header of the dot file: */ 730 fprintf (file, "strict digraph {\n"); 731 fprintf (file, " node [\n shape = box\n ]\n"); 732 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n"); 733 fprintf (file, "\n // List of nodes and complex constraints in " 734 "the constraint graph:\n"); 735 736 /* The next lines print the nodes in the graph together with the 737 complex constraints attached to them. */ 738 for (i = 1; i < graph->size; i++) 739 { 740 if (i == FIRST_REF_NODE) 741 continue; 742 if (find (i) != i) 743 continue; 744 if (i < FIRST_REF_NODE) 745 fprintf (file, "\"%s\"", get_varinfo (i)->name); 746 else 747 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name); 748 if (graph->complex[i].exists ()) 749 { 750 unsigned j; 751 constraint_t c; 752 fprintf (file, " [label=\"\\N\\n"); 753 for (j = 0; graph->complex[i].iterate (j, &c); ++j) 754 { 755 dump_constraint (file, c); 756 fprintf (file, "\\l"); 757 } 758 fprintf (file, "\"]"); 759 } 760 fprintf (file, ";\n"); 761 } 762 763 /* Go over the edges. */ 764 fprintf (file, "\n // Edges in the constraint graph:\n"); 765 for (i = 1; i < graph->size; i++) 766 { 767 unsigned j; 768 bitmap_iterator bi; 769 if (find (i) != i) 770 continue; 771 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi) 772 { 773 unsigned to = find (j); 774 if (i == to) 775 continue; 776 if (i < FIRST_REF_NODE) 777 fprintf (file, "\"%s\"", get_varinfo (i)->name); 778 else 779 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name); 780 fprintf (file, " -> "); 781 if (to < FIRST_REF_NODE) 782 fprintf (file, "\"%s\"", get_varinfo (to)->name); 783 else 784 fprintf (file, "\"*%s\"", get_varinfo (to - FIRST_REF_NODE)->name); 785 fprintf (file, ";\n"); 786 } 787 } 788 789 /* Prints the tail of the dot file. */ 790 fprintf (file, "}\n"); 791 } 792 793 /* Print out the constraint graph to stderr. */ 794 795 DEBUG_FUNCTION void 796 debug_constraint_graph (void) 797 { 798 dump_constraint_graph (stderr); 799 } 800 801 /* SOLVER FUNCTIONS 802 803 The solver is a simple worklist solver, that works on the following 804 algorithm: 805 806 sbitmap changed_nodes = all zeroes; 807 changed_count = 0; 808 For each node that is not already collapsed: 809 changed_count++; 810 set bit in changed nodes 811 812 while (changed_count > 0) 813 { 814 compute topological ordering for constraint graph 815 816 find and collapse cycles in the constraint graph (updating 817 changed if necessary) 818 819 for each node (n) in the graph in topological order: 820 changed_count--; 821 822 Process each complex constraint associated with the node, 823 updating changed if necessary. 824 825 For each outgoing edge from n, propagate the solution from n to 826 the destination of the edge, updating changed as necessary. 827 828 } */ 829 830 /* Return true if two constraint expressions A and B are equal. */ 831 832 static bool 833 constraint_expr_equal (struct constraint_expr a, struct constraint_expr b) 834 { 835 return a.type == b.type && a.var == b.var && a.offset == b.offset; 836 } 837 838 /* Return true if constraint expression A is less than constraint expression 839 B. This is just arbitrary, but consistent, in order to give them an 840 ordering. */ 841 842 static bool 843 constraint_expr_less (struct constraint_expr a, struct constraint_expr b) 844 { 845 if (a.type == b.type) 846 { 847 if (a.var == b.var) 848 return a.offset < b.offset; 849 else 850 return a.var < b.var; 851 } 852 else 853 return a.type < b.type; 854 } 855 856 /* Return true if constraint A is less than constraint B. This is just 857 arbitrary, but consistent, in order to give them an ordering. */ 858 859 static bool 860 constraint_less (const constraint_t &a, const constraint_t &b) 861 { 862 if (constraint_expr_less (a->lhs, b->lhs)) 863 return true; 864 else if (constraint_expr_less (b->lhs, a->lhs)) 865 return false; 866 else 867 return constraint_expr_less (a->rhs, b->rhs); 868 } 869 870 /* Return true if two constraints A and B are equal. */ 871 872 static bool 873 constraint_equal (struct constraint a, struct constraint b) 874 { 875 return constraint_expr_equal (a.lhs, b.lhs) 876 && constraint_expr_equal (a.rhs, b.rhs); 877 } 878 879 880 /* Find a constraint LOOKFOR in the sorted constraint vector VEC */ 881 882 static constraint_t 883 constraint_vec_find (vec<constraint_t> vec, 884 struct constraint lookfor) 885 { 886 unsigned int place; 887 constraint_t found; 888 889 if (!vec.exists ()) 890 return NULL; 891 892 place = vec.lower_bound (&lookfor, constraint_less); 893 if (place >= vec.length ()) 894 return NULL; 895 found = vec[place]; 896 if (!constraint_equal (*found, lookfor)) 897 return NULL; 898 return found; 899 } 900 901 /* Union two constraint vectors, TO and FROM. Put the result in TO. 902 Returns true of TO set is changed. */ 903 904 static bool 905 constraint_set_union (vec<constraint_t> *to, 906 vec<constraint_t> *from) 907 { 908 int i; 909 constraint_t c; 910 bool any_change = false; 911 912 FOR_EACH_VEC_ELT (*from, i, c) 913 { 914 if (constraint_vec_find (*to, *c) == NULL) 915 { 916 unsigned int place = to->lower_bound (c, constraint_less); 917 to->safe_insert (place, c); 918 any_change = true; 919 } 920 } 921 return any_change; 922 } 923 924 /* Expands the solution in SET to all sub-fields of variables included. */ 925 926 static bitmap 927 solution_set_expand (bitmap set, bitmap *expanded) 928 { 929 bitmap_iterator bi; 930 unsigned j; 931 932 if (*expanded) 933 return *expanded; 934 935 *expanded = BITMAP_ALLOC (&iteration_obstack); 936 937 /* In a first pass expand to the head of the variables we need to 938 add all sub-fields off. This avoids quadratic behavior. */ 939 EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi) 940 { 941 varinfo_t v = get_varinfo (j); 942 if (v->is_artificial_var 943 || v->is_full_var) 944 continue; 945 bitmap_set_bit (*expanded, v->head); 946 } 947 948 /* In the second pass now expand all head variables with subfields. */ 949 EXECUTE_IF_SET_IN_BITMAP (*expanded, 0, j, bi) 950 { 951 varinfo_t v = get_varinfo (j); 952 if (v->head != j) 953 continue; 954 for (v = vi_next (v); v != NULL; v = vi_next (v)) 955 bitmap_set_bit (*expanded, v->id); 956 } 957 958 /* And finally set the rest of the bits from SET. */ 959 bitmap_ior_into (*expanded, set); 960 961 return *expanded; 962 } 963 964 /* Union solution sets TO and DELTA, and add INC to each member of DELTA in the 965 process. */ 966 967 static bool 968 set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc, 969 bitmap *expanded_delta) 970 { 971 bool changed = false; 972 bitmap_iterator bi; 973 unsigned int i; 974 975 /* If the solution of DELTA contains anything it is good enough to transfer 976 this to TO. */ 977 if (bitmap_bit_p (delta, anything_id)) 978 return bitmap_set_bit (to, anything_id); 979 980 /* If the offset is unknown we have to expand the solution to 981 all subfields. */ 982 if (inc == UNKNOWN_OFFSET) 983 { 984 delta = solution_set_expand (delta, expanded_delta); 985 changed |= bitmap_ior_into (to, delta); 986 return changed; 987 } 988 989 /* For non-zero offset union the offsetted solution into the destination. */ 990 EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi) 991 { 992 varinfo_t vi = get_varinfo (i); 993 994 /* If this is a variable with just one field just set its bit 995 in the result. */ 996 if (vi->is_artificial_var 997 || vi->is_unknown_size_var 998 || vi->is_full_var) 999 changed |= bitmap_set_bit (to, i); 1000 else 1001 { 1002 HOST_WIDE_INT fieldoffset = vi->offset + inc; 1003 unsigned HOST_WIDE_INT size = vi->size; 1004 1005 /* If the offset makes the pointer point to before the 1006 variable use offset zero for the field lookup. */ 1007 if (fieldoffset < 0) 1008 vi = get_varinfo (vi->head); 1009 else 1010 vi = first_or_preceding_vi_for_offset (vi, fieldoffset); 1011 1012 do 1013 { 1014 changed |= bitmap_set_bit (to, vi->id); 1015 if (vi->is_full_var 1016 || vi->next == 0) 1017 break; 1018 1019 /* We have to include all fields that overlap the current field 1020 shifted by inc. */ 1021 vi = vi_next (vi); 1022 } 1023 while (vi->offset < fieldoffset + size); 1024 } 1025 } 1026 1027 return changed; 1028 } 1029 1030 /* Insert constraint C into the list of complex constraints for graph 1031 node VAR. */ 1032 1033 static void 1034 insert_into_complex (constraint_graph_t graph, 1035 unsigned int var, constraint_t c) 1036 { 1037 vec<constraint_t> complex = graph->complex[var]; 1038 unsigned int place = complex.lower_bound (c, constraint_less); 1039 1040 /* Only insert constraints that do not already exist. */ 1041 if (place >= complex.length () 1042 || !constraint_equal (*c, *complex[place])) 1043 graph->complex[var].safe_insert (place, c); 1044 } 1045 1046 1047 /* Condense two variable nodes into a single variable node, by moving 1048 all associated info from FROM to TO. Returns true if TO node's 1049 constraint set changes after the merge. */ 1050 1051 static bool 1052 merge_node_constraints (constraint_graph_t graph, unsigned int to, 1053 unsigned int from) 1054 { 1055 unsigned int i; 1056 constraint_t c; 1057 bool any_change = false; 1058 1059 gcc_checking_assert (find (from) == to); 1060 1061 /* Move all complex constraints from src node into to node */ 1062 FOR_EACH_VEC_ELT (graph->complex[from], i, c) 1063 { 1064 /* In complex constraints for node FROM, we may have either 1065 a = *FROM, and *FROM = a, or an offseted constraint which are 1066 always added to the rhs node's constraints. */ 1067 1068 if (c->rhs.type == DEREF) 1069 c->rhs.var = to; 1070 else if (c->lhs.type == DEREF) 1071 c->lhs.var = to; 1072 else 1073 c->rhs.var = to; 1074 1075 } 1076 any_change = constraint_set_union (&graph->complex[to], 1077 &graph->complex[from]); 1078 graph->complex[from].release (); 1079 return any_change; 1080 } 1081 1082 1083 /* Remove edges involving NODE from GRAPH. */ 1084 1085 static void 1086 clear_edges_for_node (constraint_graph_t graph, unsigned int node) 1087 { 1088 if (graph->succs[node]) 1089 BITMAP_FREE (graph->succs[node]); 1090 } 1091 1092 /* Merge GRAPH nodes FROM and TO into node TO. */ 1093 1094 static void 1095 merge_graph_nodes (constraint_graph_t graph, unsigned int to, 1096 unsigned int from) 1097 { 1098 if (graph->indirect_cycles[from] != -1) 1099 { 1100 /* If we have indirect cycles with the from node, and we have 1101 none on the to node, the to node has indirect cycles from the 1102 from node now that they are unified. 1103 If indirect cycles exist on both, unify the nodes that they 1104 are in a cycle with, since we know they are in a cycle with 1105 each other. */ 1106 if (graph->indirect_cycles[to] == -1) 1107 graph->indirect_cycles[to] = graph->indirect_cycles[from]; 1108 } 1109 1110 /* Merge all the successor edges. */ 1111 if (graph->succs[from]) 1112 { 1113 if (!graph->succs[to]) 1114 graph->succs[to] = BITMAP_ALLOC (&pta_obstack); 1115 bitmap_ior_into (graph->succs[to], 1116 graph->succs[from]); 1117 } 1118 1119 clear_edges_for_node (graph, from); 1120 } 1121 1122 1123 /* Add an indirect graph edge to GRAPH, going from TO to FROM if 1124 it doesn't exist in the graph already. */ 1125 1126 static void 1127 add_implicit_graph_edge (constraint_graph_t graph, unsigned int to, 1128 unsigned int from) 1129 { 1130 if (to == from) 1131 return; 1132 1133 if (!graph->implicit_preds[to]) 1134 graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack); 1135 1136 if (bitmap_set_bit (graph->implicit_preds[to], from)) 1137 stats.num_implicit_edges++; 1138 } 1139 1140 /* Add a predecessor graph edge to GRAPH, going from TO to FROM if 1141 it doesn't exist in the graph already. 1142 Return false if the edge already existed, true otherwise. */ 1143 1144 static void 1145 add_pred_graph_edge (constraint_graph_t graph, unsigned int to, 1146 unsigned int from) 1147 { 1148 if (!graph->preds[to]) 1149 graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack); 1150 bitmap_set_bit (graph->preds[to], from); 1151 } 1152 1153 /* Add a graph edge to GRAPH, going from FROM to TO if 1154 it doesn't exist in the graph already. 1155 Return false if the edge already existed, true otherwise. */ 1156 1157 static bool 1158 add_graph_edge (constraint_graph_t graph, unsigned int to, 1159 unsigned int from) 1160 { 1161 if (to == from) 1162 { 1163 return false; 1164 } 1165 else 1166 { 1167 bool r = false; 1168 1169 if (!graph->succs[from]) 1170 graph->succs[from] = BITMAP_ALLOC (&pta_obstack); 1171 if (bitmap_set_bit (graph->succs[from], to)) 1172 { 1173 r = true; 1174 if (to < FIRST_REF_NODE && from < FIRST_REF_NODE) 1175 stats.num_edges++; 1176 } 1177 return r; 1178 } 1179 } 1180 1181 1182 /* Initialize the constraint graph structure to contain SIZE nodes. */ 1183 1184 static void 1185 init_graph (unsigned int size) 1186 { 1187 unsigned int j; 1188 1189 graph = XCNEW (struct constraint_graph); 1190 graph->size = size; 1191 graph->succs = XCNEWVEC (bitmap, graph->size); 1192 graph->indirect_cycles = XNEWVEC (int, graph->size); 1193 graph->rep = XNEWVEC (unsigned int, graph->size); 1194 /* ??? Macros do not support template types with multiple arguments, 1195 so we use a typedef to work around it. */ 1196 typedef vec<constraint_t> vec_constraint_t_heap; 1197 graph->complex = XCNEWVEC (vec_constraint_t_heap, size); 1198 graph->pe = XCNEWVEC (unsigned int, graph->size); 1199 graph->pe_rep = XNEWVEC (int, graph->size); 1200 1201 for (j = 0; j < graph->size; j++) 1202 { 1203 graph->rep[j] = j; 1204 graph->pe_rep[j] = -1; 1205 graph->indirect_cycles[j] = -1; 1206 } 1207 } 1208 1209 /* Build the constraint graph, adding only predecessor edges right now. */ 1210 1211 static void 1212 build_pred_graph (void) 1213 { 1214 int i; 1215 constraint_t c; 1216 unsigned int j; 1217 1218 graph->implicit_preds = XCNEWVEC (bitmap, graph->size); 1219 graph->preds = XCNEWVEC (bitmap, graph->size); 1220 graph->pointer_label = XCNEWVEC (unsigned int, graph->size); 1221 graph->loc_label = XCNEWVEC (unsigned int, graph->size); 1222 graph->pointed_by = XCNEWVEC (bitmap, graph->size); 1223 graph->points_to = XCNEWVEC (bitmap, graph->size); 1224 graph->eq_rep = XNEWVEC (int, graph->size); 1225 graph->direct_nodes = sbitmap_alloc (graph->size); 1226 graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack); 1227 bitmap_clear (graph->direct_nodes); 1228 1229 for (j = 1; j < FIRST_REF_NODE; j++) 1230 { 1231 if (!get_varinfo (j)->is_special_var) 1232 bitmap_set_bit (graph->direct_nodes, j); 1233 } 1234 1235 for (j = 0; j < graph->size; j++) 1236 graph->eq_rep[j] = -1; 1237 1238 for (j = 0; j < varmap.length (); j++) 1239 graph->indirect_cycles[j] = -1; 1240 1241 FOR_EACH_VEC_ELT (constraints, i, c) 1242 { 1243 struct constraint_expr lhs = c->lhs; 1244 struct constraint_expr rhs = c->rhs; 1245 unsigned int lhsvar = lhs.var; 1246 unsigned int rhsvar = rhs.var; 1247 1248 if (lhs.type == DEREF) 1249 { 1250 /* *x = y. */ 1251 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR) 1252 add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); 1253 } 1254 else if (rhs.type == DEREF) 1255 { 1256 /* x = *y */ 1257 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR) 1258 add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar); 1259 else 1260 bitmap_clear_bit (graph->direct_nodes, lhsvar); 1261 } 1262 else if (rhs.type == ADDRESSOF) 1263 { 1264 varinfo_t v; 1265 1266 /* x = &y */ 1267 if (graph->points_to[lhsvar] == NULL) 1268 graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack); 1269 bitmap_set_bit (graph->points_to[lhsvar], rhsvar); 1270 1271 if (graph->pointed_by[rhsvar] == NULL) 1272 graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack); 1273 bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar); 1274 1275 /* Implicitly, *x = y */ 1276 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); 1277 1278 /* All related variables are no longer direct nodes. */ 1279 bitmap_clear_bit (graph->direct_nodes, rhsvar); 1280 v = get_varinfo (rhsvar); 1281 if (!v->is_full_var) 1282 { 1283 v = get_varinfo (v->head); 1284 do 1285 { 1286 bitmap_clear_bit (graph->direct_nodes, v->id); 1287 v = vi_next (v); 1288 } 1289 while (v != NULL); 1290 } 1291 bitmap_set_bit (graph->address_taken, rhsvar); 1292 } 1293 else if (lhsvar > anything_id 1294 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0) 1295 { 1296 /* x = y */ 1297 add_pred_graph_edge (graph, lhsvar, rhsvar); 1298 /* Implicitly, *x = *y */ 1299 add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, 1300 FIRST_REF_NODE + rhsvar); 1301 } 1302 else if (lhs.offset != 0 || rhs.offset != 0) 1303 { 1304 if (rhs.offset != 0) 1305 bitmap_clear_bit (graph->direct_nodes, lhs.var); 1306 else if (lhs.offset != 0) 1307 bitmap_clear_bit (graph->direct_nodes, rhs.var); 1308 } 1309 } 1310 } 1311 1312 /* Build the constraint graph, adding successor edges. */ 1313 1314 static void 1315 build_succ_graph (void) 1316 { 1317 unsigned i, t; 1318 constraint_t c; 1319 1320 FOR_EACH_VEC_ELT (constraints, i, c) 1321 { 1322 struct constraint_expr lhs; 1323 struct constraint_expr rhs; 1324 unsigned int lhsvar; 1325 unsigned int rhsvar; 1326 1327 if (!c) 1328 continue; 1329 1330 lhs = c->lhs; 1331 rhs = c->rhs; 1332 lhsvar = find (lhs.var); 1333 rhsvar = find (rhs.var); 1334 1335 if (lhs.type == DEREF) 1336 { 1337 if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR) 1338 add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); 1339 } 1340 else if (rhs.type == DEREF) 1341 { 1342 if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR) 1343 add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar); 1344 } 1345 else if (rhs.type == ADDRESSOF) 1346 { 1347 /* x = &y */ 1348 gcc_checking_assert (find (rhs.var) == rhs.var); 1349 bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar); 1350 } 1351 else if (lhsvar > anything_id 1352 && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0) 1353 { 1354 add_graph_edge (graph, lhsvar, rhsvar); 1355 } 1356 } 1357 1358 /* Add edges from STOREDANYTHING to all non-direct nodes that can 1359 receive pointers. */ 1360 t = find (storedanything_id); 1361 for (i = integer_id + 1; i < FIRST_REF_NODE; ++i) 1362 { 1363 if (!bitmap_bit_p (graph->direct_nodes, i) 1364 && get_varinfo (i)->may_have_pointers) 1365 add_graph_edge (graph, find (i), t); 1366 } 1367 1368 /* Everything stored to ANYTHING also potentially escapes. */ 1369 add_graph_edge (graph, find (escaped_id), t); 1370 } 1371 1372 1373 /* Changed variables on the last iteration. */ 1374 static bitmap changed; 1375 1376 /* Strongly Connected Component visitation info. */ 1377 1378 struct scc_info 1379 { 1380 sbitmap visited; 1381 sbitmap deleted; 1382 unsigned int *dfs; 1383 unsigned int *node_mapping; 1384 int current_index; 1385 vec<unsigned> scc_stack; 1386 }; 1387 1388 1389 /* Recursive routine to find strongly connected components in GRAPH. 1390 SI is the SCC info to store the information in, and N is the id of current 1391 graph node we are processing. 1392 1393 This is Tarjan's strongly connected component finding algorithm, as 1394 modified by Nuutila to keep only non-root nodes on the stack. 1395 The algorithm can be found in "On finding the strongly connected 1396 connected components in a directed graph" by Esko Nuutila and Eljas 1397 Soisalon-Soininen, in Information Processing Letters volume 49, 1398 number 1, pages 9-14. */ 1399 1400 static void 1401 scc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n) 1402 { 1403 unsigned int i; 1404 bitmap_iterator bi; 1405 unsigned int my_dfs; 1406 1407 bitmap_set_bit (si->visited, n); 1408 si->dfs[n] = si->current_index ++; 1409 my_dfs = si->dfs[n]; 1410 1411 /* Visit all the successors. */ 1412 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi) 1413 { 1414 unsigned int w; 1415 1416 if (i > LAST_REF_NODE) 1417 break; 1418 1419 w = find (i); 1420 if (bitmap_bit_p (si->deleted, w)) 1421 continue; 1422 1423 if (!bitmap_bit_p (si->visited, w)) 1424 scc_visit (graph, si, w); 1425 1426 unsigned int t = find (w); 1427 gcc_checking_assert (find (n) == n); 1428 if (si->dfs[t] < si->dfs[n]) 1429 si->dfs[n] = si->dfs[t]; 1430 } 1431 1432 /* See if any components have been identified. */ 1433 if (si->dfs[n] == my_dfs) 1434 { 1435 if (si->scc_stack.length () > 0 1436 && si->dfs[si->scc_stack.last ()] >= my_dfs) 1437 { 1438 bitmap scc = BITMAP_ALLOC (NULL); 1439 unsigned int lowest_node; 1440 bitmap_iterator bi; 1441 1442 bitmap_set_bit (scc, n); 1443 1444 while (si->scc_stack.length () != 0 1445 && si->dfs[si->scc_stack.last ()] >= my_dfs) 1446 { 1447 unsigned int w = si->scc_stack.pop (); 1448 1449 bitmap_set_bit (scc, w); 1450 } 1451 1452 lowest_node = bitmap_first_set_bit (scc); 1453 gcc_assert (lowest_node < FIRST_REF_NODE); 1454 1455 /* Collapse the SCC nodes into a single node, and mark the 1456 indirect cycles. */ 1457 EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi) 1458 { 1459 if (i < FIRST_REF_NODE) 1460 { 1461 if (unite (lowest_node, i)) 1462 unify_nodes (graph, lowest_node, i, false); 1463 } 1464 else 1465 { 1466 unite (lowest_node, i); 1467 graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node; 1468 } 1469 } 1470 } 1471 bitmap_set_bit (si->deleted, n); 1472 } 1473 else 1474 si->scc_stack.safe_push (n); 1475 } 1476 1477 /* Unify node FROM into node TO, updating the changed count if 1478 necessary when UPDATE_CHANGED is true. */ 1479 1480 static void 1481 unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from, 1482 bool update_changed) 1483 { 1484 gcc_checking_assert (to != from && find (to) == to); 1485 1486 if (dump_file && (dump_flags & TDF_DETAILS)) 1487 fprintf (dump_file, "Unifying %s to %s\n", 1488 get_varinfo (from)->name, 1489 get_varinfo (to)->name); 1490 1491 if (update_changed) 1492 stats.unified_vars_dynamic++; 1493 else 1494 stats.unified_vars_static++; 1495 1496 merge_graph_nodes (graph, to, from); 1497 if (merge_node_constraints (graph, to, from)) 1498 { 1499 if (update_changed) 1500 bitmap_set_bit (changed, to); 1501 } 1502 1503 /* Mark TO as changed if FROM was changed. If TO was already marked 1504 as changed, decrease the changed count. */ 1505 1506 if (update_changed 1507 && bitmap_clear_bit (changed, from)) 1508 bitmap_set_bit (changed, to); 1509 varinfo_t fromvi = get_varinfo (from); 1510 if (fromvi->solution) 1511 { 1512 /* If the solution changes because of the merging, we need to mark 1513 the variable as changed. */ 1514 varinfo_t tovi = get_varinfo (to); 1515 if (bitmap_ior_into (tovi->solution, fromvi->solution)) 1516 { 1517 if (update_changed) 1518 bitmap_set_bit (changed, to); 1519 } 1520 1521 BITMAP_FREE (fromvi->solution); 1522 if (fromvi->oldsolution) 1523 BITMAP_FREE (fromvi->oldsolution); 1524 1525 if (stats.iterations > 0 1526 && tovi->oldsolution) 1527 BITMAP_FREE (tovi->oldsolution); 1528 } 1529 if (graph->succs[to]) 1530 bitmap_clear_bit (graph->succs[to], to); 1531 } 1532 1533 /* Information needed to compute the topological ordering of a graph. */ 1534 1535 struct topo_info 1536 { 1537 /* sbitmap of visited nodes. */ 1538 sbitmap visited; 1539 /* Array that stores the topological order of the graph, *in 1540 reverse*. */ 1541 vec<unsigned> topo_order; 1542 }; 1543 1544 1545 /* Initialize and return a topological info structure. */ 1546 1547 static struct topo_info * 1548 init_topo_info (void) 1549 { 1550 size_t size = graph->size; 1551 struct topo_info *ti = XNEW (struct topo_info); 1552 ti->visited = sbitmap_alloc (size); 1553 bitmap_clear (ti->visited); 1554 ti->topo_order.create (1); 1555 return ti; 1556 } 1557 1558 1559 /* Free the topological sort info pointed to by TI. */ 1560 1561 static void 1562 free_topo_info (struct topo_info *ti) 1563 { 1564 sbitmap_free (ti->visited); 1565 ti->topo_order.release (); 1566 free (ti); 1567 } 1568 1569 /* Visit the graph in topological order, and store the order in the 1570 topo_info structure. */ 1571 1572 static void 1573 topo_visit (constraint_graph_t graph, struct topo_info *ti, 1574 unsigned int n) 1575 { 1576 bitmap_iterator bi; 1577 unsigned int j; 1578 1579 bitmap_set_bit (ti->visited, n); 1580 1581 if (graph->succs[n]) 1582 EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi) 1583 { 1584 if (!bitmap_bit_p (ti->visited, j)) 1585 topo_visit (graph, ti, j); 1586 } 1587 1588 ti->topo_order.safe_push (n); 1589 } 1590 1591 /* Process a constraint C that represents x = *(y + off), using DELTA as the 1592 starting solution for y. */ 1593 1594 static void 1595 do_sd_constraint (constraint_graph_t graph, constraint_t c, 1596 bitmap delta, bitmap *expanded_delta) 1597 { 1598 unsigned int lhs = c->lhs.var; 1599 bool flag = false; 1600 bitmap sol = get_varinfo (lhs)->solution; 1601 unsigned int j; 1602 bitmap_iterator bi; 1603 HOST_WIDE_INT roffset = c->rhs.offset; 1604 1605 /* Our IL does not allow this. */ 1606 gcc_checking_assert (c->lhs.offset == 0); 1607 1608 /* If the solution of Y contains anything it is good enough to transfer 1609 this to the LHS. */ 1610 if (bitmap_bit_p (delta, anything_id)) 1611 { 1612 flag |= bitmap_set_bit (sol, anything_id); 1613 goto done; 1614 } 1615 1616 /* If we do not know at with offset the rhs is dereferenced compute 1617 the reachability set of DELTA, conservatively assuming it is 1618 dereferenced at all valid offsets. */ 1619 if (roffset == UNKNOWN_OFFSET) 1620 { 1621 delta = solution_set_expand (delta, expanded_delta); 1622 /* No further offset processing is necessary. */ 1623 roffset = 0; 1624 } 1625 1626 /* For each variable j in delta (Sol(y)), add 1627 an edge in the graph from j to x, and union Sol(j) into Sol(x). */ 1628 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) 1629 { 1630 varinfo_t v = get_varinfo (j); 1631 HOST_WIDE_INT fieldoffset = v->offset + roffset; 1632 unsigned HOST_WIDE_INT size = v->size; 1633 unsigned int t; 1634 1635 if (v->is_full_var) 1636 ; 1637 else if (roffset != 0) 1638 { 1639 if (fieldoffset < 0) 1640 v = get_varinfo (v->head); 1641 else 1642 v = first_or_preceding_vi_for_offset (v, fieldoffset); 1643 } 1644 1645 /* We have to include all fields that overlap the current field 1646 shifted by roffset. */ 1647 do 1648 { 1649 t = find (v->id); 1650 1651 /* Adding edges from the special vars is pointless. 1652 They don't have sets that can change. */ 1653 if (get_varinfo (t)->is_special_var) 1654 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution); 1655 /* Merging the solution from ESCAPED needlessly increases 1656 the set. Use ESCAPED as representative instead. */ 1657 else if (v->id == escaped_id) 1658 flag |= bitmap_set_bit (sol, escaped_id); 1659 else if (v->may_have_pointers 1660 && add_graph_edge (graph, lhs, t)) 1661 flag |= bitmap_ior_into (sol, get_varinfo (t)->solution); 1662 1663 if (v->is_full_var 1664 || v->next == 0) 1665 break; 1666 1667 v = vi_next (v); 1668 } 1669 while (v->offset < fieldoffset + size); 1670 } 1671 1672 done: 1673 /* If the LHS solution changed, mark the var as changed. */ 1674 if (flag) 1675 { 1676 get_varinfo (lhs)->solution = sol; 1677 bitmap_set_bit (changed, lhs); 1678 } 1679 } 1680 1681 /* Process a constraint C that represents *(x + off) = y using DELTA 1682 as the starting solution for x. */ 1683 1684 static void 1685 do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta) 1686 { 1687 unsigned int rhs = c->rhs.var; 1688 bitmap sol = get_varinfo (rhs)->solution; 1689 unsigned int j; 1690 bitmap_iterator bi; 1691 HOST_WIDE_INT loff = c->lhs.offset; 1692 bool escaped_p = false; 1693 1694 /* Our IL does not allow this. */ 1695 gcc_checking_assert (c->rhs.offset == 0); 1696 1697 /* If the solution of y contains ANYTHING simply use the ANYTHING 1698 solution. This avoids needlessly increasing the points-to sets. */ 1699 if (bitmap_bit_p (sol, anything_id)) 1700 sol = get_varinfo (find (anything_id))->solution; 1701 1702 /* If the solution for x contains ANYTHING we have to merge the 1703 solution of y into all pointer variables which we do via 1704 STOREDANYTHING. */ 1705 if (bitmap_bit_p (delta, anything_id)) 1706 { 1707 unsigned t = find (storedanything_id); 1708 if (add_graph_edge (graph, t, rhs)) 1709 { 1710 if (bitmap_ior_into (get_varinfo (t)->solution, sol)) 1711 bitmap_set_bit (changed, t); 1712 } 1713 return; 1714 } 1715 1716 /* If we do not know at with offset the rhs is dereferenced compute 1717 the reachability set of DELTA, conservatively assuming it is 1718 dereferenced at all valid offsets. */ 1719 if (loff == UNKNOWN_OFFSET) 1720 { 1721 delta = solution_set_expand (delta, expanded_delta); 1722 loff = 0; 1723 } 1724 1725 /* For each member j of delta (Sol(x)), add an edge from y to j and 1726 union Sol(y) into Sol(j) */ 1727 EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) 1728 { 1729 varinfo_t v = get_varinfo (j); 1730 unsigned int t; 1731 HOST_WIDE_INT fieldoffset = v->offset + loff; 1732 unsigned HOST_WIDE_INT size = v->size; 1733 1734 if (v->is_full_var) 1735 ; 1736 else if (loff != 0) 1737 { 1738 if (fieldoffset < 0) 1739 v = get_varinfo (v->head); 1740 else 1741 v = first_or_preceding_vi_for_offset (v, fieldoffset); 1742 } 1743 1744 /* We have to include all fields that overlap the current field 1745 shifted by loff. */ 1746 do 1747 { 1748 if (v->may_have_pointers) 1749 { 1750 /* If v is a global variable then this is an escape point. */ 1751 if (v->is_global_var 1752 && !escaped_p) 1753 { 1754 t = find (escaped_id); 1755 if (add_graph_edge (graph, t, rhs) 1756 && bitmap_ior_into (get_varinfo (t)->solution, sol)) 1757 bitmap_set_bit (changed, t); 1758 /* Enough to let rhs escape once. */ 1759 escaped_p = true; 1760 } 1761 1762 if (v->is_special_var) 1763 break; 1764 1765 t = find (v->id); 1766 if (add_graph_edge (graph, t, rhs) 1767 && bitmap_ior_into (get_varinfo (t)->solution, sol)) 1768 bitmap_set_bit (changed, t); 1769 } 1770 1771 if (v->is_full_var 1772 || v->next == 0) 1773 break; 1774 1775 v = vi_next (v); 1776 } 1777 while (v->offset < fieldoffset + size); 1778 } 1779 } 1780 1781 /* Handle a non-simple (simple meaning requires no iteration), 1782 constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */ 1783 1784 static void 1785 do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta, 1786 bitmap *expanded_delta) 1787 { 1788 if (c->lhs.type == DEREF) 1789 { 1790 if (c->rhs.type == ADDRESSOF) 1791 { 1792 gcc_unreachable (); 1793 } 1794 else 1795 { 1796 /* *x = y */ 1797 do_ds_constraint (c, delta, expanded_delta); 1798 } 1799 } 1800 else if (c->rhs.type == DEREF) 1801 { 1802 /* x = *y */ 1803 if (!(get_varinfo (c->lhs.var)->is_special_var)) 1804 do_sd_constraint (graph, c, delta, expanded_delta); 1805 } 1806 else 1807 { 1808 bitmap tmp; 1809 bool flag = false; 1810 1811 gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR 1812 && c->rhs.offset != 0 && c->lhs.offset == 0); 1813 tmp = get_varinfo (c->lhs.var)->solution; 1814 1815 flag = set_union_with_increment (tmp, delta, c->rhs.offset, 1816 expanded_delta); 1817 1818 if (flag) 1819 bitmap_set_bit (changed, c->lhs.var); 1820 } 1821 } 1822 1823 /* Initialize and return a new SCC info structure. */ 1824 1825 static struct scc_info * 1826 init_scc_info (size_t size) 1827 { 1828 struct scc_info *si = XNEW (struct scc_info); 1829 size_t i; 1830 1831 si->current_index = 0; 1832 si->visited = sbitmap_alloc (size); 1833 bitmap_clear (si->visited); 1834 si->deleted = sbitmap_alloc (size); 1835 bitmap_clear (si->deleted); 1836 si->node_mapping = XNEWVEC (unsigned int, size); 1837 si->dfs = XCNEWVEC (unsigned int, size); 1838 1839 for (i = 0; i < size; i++) 1840 si->node_mapping[i] = i; 1841 1842 si->scc_stack.create (1); 1843 return si; 1844 } 1845 1846 /* Free an SCC info structure pointed to by SI */ 1847 1848 static void 1849 free_scc_info (struct scc_info *si) 1850 { 1851 sbitmap_free (si->visited); 1852 sbitmap_free (si->deleted); 1853 free (si->node_mapping); 1854 free (si->dfs); 1855 si->scc_stack.release (); 1856 free (si); 1857 } 1858 1859 1860 /* Find indirect cycles in GRAPH that occur, using strongly connected 1861 components, and note them in the indirect cycles map. 1862 1863 This technique comes from Ben Hardekopf and Calvin Lin, 1864 "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of 1865 Lines of Code", submitted to PLDI 2007. */ 1866 1867 static void 1868 find_indirect_cycles (constraint_graph_t graph) 1869 { 1870 unsigned int i; 1871 unsigned int size = graph->size; 1872 struct scc_info *si = init_scc_info (size); 1873 1874 for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ ) 1875 if (!bitmap_bit_p (si->visited, i) && find (i) == i) 1876 scc_visit (graph, si, i); 1877 1878 free_scc_info (si); 1879 } 1880 1881 /* Compute a topological ordering for GRAPH, and store the result in the 1882 topo_info structure TI. */ 1883 1884 static void 1885 compute_topo_order (constraint_graph_t graph, 1886 struct topo_info *ti) 1887 { 1888 unsigned int i; 1889 unsigned int size = graph->size; 1890 1891 for (i = 0; i != size; ++i) 1892 if (!bitmap_bit_p (ti->visited, i) && find (i) == i) 1893 topo_visit (graph, ti, i); 1894 } 1895 1896 /* Structure used to for hash value numbering of pointer equivalence 1897 classes. */ 1898 1899 typedef struct equiv_class_label 1900 { 1901 hashval_t hashcode; 1902 unsigned int equivalence_class; 1903 bitmap labels; 1904 } *equiv_class_label_t; 1905 typedef const struct equiv_class_label *const_equiv_class_label_t; 1906 1907 /* Equiv_class_label hashtable helpers. */ 1908 1909 struct equiv_class_hasher : free_ptr_hash <equiv_class_label> 1910 { 1911 static inline hashval_t hash (const equiv_class_label *); 1912 static inline bool equal (const equiv_class_label *, 1913 const equiv_class_label *); 1914 }; 1915 1916 /* Hash function for a equiv_class_label_t */ 1917 1918 inline hashval_t 1919 equiv_class_hasher::hash (const equiv_class_label *ecl) 1920 { 1921 return ecl->hashcode; 1922 } 1923 1924 /* Equality function for two equiv_class_label_t's. */ 1925 1926 inline bool 1927 equiv_class_hasher::equal (const equiv_class_label *eql1, 1928 const equiv_class_label *eql2) 1929 { 1930 return (eql1->hashcode == eql2->hashcode 1931 && bitmap_equal_p (eql1->labels, eql2->labels)); 1932 } 1933 1934 /* A hashtable for mapping a bitmap of labels->pointer equivalence 1935 classes. */ 1936 static hash_table<equiv_class_hasher> *pointer_equiv_class_table; 1937 1938 /* A hashtable for mapping a bitmap of labels->location equivalence 1939 classes. */ 1940 static hash_table<equiv_class_hasher> *location_equiv_class_table; 1941 1942 /* Lookup a equivalence class in TABLE by the bitmap of LABELS with 1943 hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS 1944 is equivalent to. */ 1945 1946 static equiv_class_label * 1947 equiv_class_lookup_or_add (hash_table<equiv_class_hasher> *table, 1948 bitmap labels) 1949 { 1950 equiv_class_label **slot; 1951 equiv_class_label ecl; 1952 1953 ecl.labels = labels; 1954 ecl.hashcode = bitmap_hash (labels); 1955 slot = table->find_slot (&ecl, INSERT); 1956 if (!*slot) 1957 { 1958 *slot = XNEW (struct equiv_class_label); 1959 (*slot)->labels = labels; 1960 (*slot)->hashcode = ecl.hashcode; 1961 (*slot)->equivalence_class = 0; 1962 } 1963 1964 return *slot; 1965 } 1966 1967 /* Perform offline variable substitution. 1968 1969 This is a worst case quadratic time way of identifying variables 1970 that must have equivalent points-to sets, including those caused by 1971 static cycles, and single entry subgraphs, in the constraint graph. 1972 1973 The technique is described in "Exploiting Pointer and Location 1974 Equivalence to Optimize Pointer Analysis. In the 14th International 1975 Static Analysis Symposium (SAS), August 2007." It is known as the 1976 "HU" algorithm, and is equivalent to value numbering the collapsed 1977 constraint graph including evaluating unions. 1978 1979 The general method of finding equivalence classes is as follows: 1980 Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints. 1981 Initialize all non-REF nodes to be direct nodes. 1982 For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh 1983 variable} 1984 For each constraint containing the dereference, we also do the same 1985 thing. 1986 1987 We then compute SCC's in the graph and unify nodes in the same SCC, 1988 including pts sets. 1989 1990 For each non-collapsed node x: 1991 Visit all unvisited explicit incoming edges. 1992 Ignoring all non-pointers, set pts(x) = Union of pts(a) for y 1993 where y->x. 1994 Lookup the equivalence class for pts(x). 1995 If we found one, equivalence_class(x) = found class. 1996 Otherwise, equivalence_class(x) = new class, and new_class is 1997 added to the lookup table. 1998 1999 All direct nodes with the same equivalence class can be replaced 2000 with a single representative node. 2001 All unlabeled nodes (label == 0) are not pointers and all edges 2002 involving them can be eliminated. 2003 We perform these optimizations during rewrite_constraints 2004 2005 In addition to pointer equivalence class finding, we also perform 2006 location equivalence class finding. This is the set of variables 2007 that always appear together in points-to sets. We use this to 2008 compress the size of the points-to sets. */ 2009 2010 /* Current maximum pointer equivalence class id. */ 2011 static int pointer_equiv_class; 2012 2013 /* Current maximum location equivalence class id. */ 2014 static int location_equiv_class; 2015 2016 /* Recursive routine to find strongly connected components in GRAPH, 2017 and label it's nodes with DFS numbers. */ 2018 2019 static void 2020 condense_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n) 2021 { 2022 unsigned int i; 2023 bitmap_iterator bi; 2024 unsigned int my_dfs; 2025 2026 gcc_checking_assert (si->node_mapping[n] == n); 2027 bitmap_set_bit (si->visited, n); 2028 si->dfs[n] = si->current_index ++; 2029 my_dfs = si->dfs[n]; 2030 2031 /* Visit all the successors. */ 2032 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) 2033 { 2034 unsigned int w = si->node_mapping[i]; 2035 2036 if (bitmap_bit_p (si->deleted, w)) 2037 continue; 2038 2039 if (!bitmap_bit_p (si->visited, w)) 2040 condense_visit (graph, si, w); 2041 2042 unsigned int t = si->node_mapping[w]; 2043 gcc_checking_assert (si->node_mapping[n] == n); 2044 if (si->dfs[t] < si->dfs[n]) 2045 si->dfs[n] = si->dfs[t]; 2046 } 2047 2048 /* Visit all the implicit predecessors. */ 2049 EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi) 2050 { 2051 unsigned int w = si->node_mapping[i]; 2052 2053 if (bitmap_bit_p (si->deleted, w)) 2054 continue; 2055 2056 if (!bitmap_bit_p (si->visited, w)) 2057 condense_visit (graph, si, w); 2058 2059 unsigned int t = si->node_mapping[w]; 2060 gcc_assert (si->node_mapping[n] == n); 2061 if (si->dfs[t] < si->dfs[n]) 2062 si->dfs[n] = si->dfs[t]; 2063 } 2064 2065 /* See if any components have been identified. */ 2066 if (si->dfs[n] == my_dfs) 2067 { 2068 while (si->scc_stack.length () != 0 2069 && si->dfs[si->scc_stack.last ()] >= my_dfs) 2070 { 2071 unsigned int w = si->scc_stack.pop (); 2072 si->node_mapping[w] = n; 2073 2074 if (!bitmap_bit_p (graph->direct_nodes, w)) 2075 bitmap_clear_bit (graph->direct_nodes, n); 2076 2077 /* Unify our nodes. */ 2078 if (graph->preds[w]) 2079 { 2080 if (!graph->preds[n]) 2081 graph->preds[n] = BITMAP_ALLOC (&predbitmap_obstack); 2082 bitmap_ior_into (graph->preds[n], graph->preds[w]); 2083 } 2084 if (graph->implicit_preds[w]) 2085 { 2086 if (!graph->implicit_preds[n]) 2087 graph->implicit_preds[n] = BITMAP_ALLOC (&predbitmap_obstack); 2088 bitmap_ior_into (graph->implicit_preds[n], 2089 graph->implicit_preds[w]); 2090 } 2091 if (graph->points_to[w]) 2092 { 2093 if (!graph->points_to[n]) 2094 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack); 2095 bitmap_ior_into (graph->points_to[n], 2096 graph->points_to[w]); 2097 } 2098 } 2099 bitmap_set_bit (si->deleted, n); 2100 } 2101 else 2102 si->scc_stack.safe_push (n); 2103 } 2104 2105 /* Label pointer equivalences. 2106 2107 This performs a value numbering of the constraint graph to 2108 discover which variables will always have the same points-to sets 2109 under the current set of constraints. 2110 2111 The way it value numbers is to store the set of points-to bits 2112 generated by the constraints and graph edges. This is just used as a 2113 hash and equality comparison. The *actual set of points-to bits* is 2114 completely irrelevant, in that we don't care about being able to 2115 extract them later. 2116 2117 The equality values (currently bitmaps) just have to satisfy a few 2118 constraints, the main ones being: 2119 1. The combining operation must be order independent. 2120 2. The end result of a given set of operations must be unique iff the 2121 combination of input values is unique 2122 3. Hashable. */ 2123 2124 static void 2125 label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n) 2126 { 2127 unsigned int i, first_pred; 2128 bitmap_iterator bi; 2129 2130 bitmap_set_bit (si->visited, n); 2131 2132 /* Label and union our incoming edges's points to sets. */ 2133 first_pred = -1U; 2134 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) 2135 { 2136 unsigned int w = si->node_mapping[i]; 2137 if (!bitmap_bit_p (si->visited, w)) 2138 label_visit (graph, si, w); 2139 2140 /* Skip unused edges */ 2141 if (w == n || graph->pointer_label[w] == 0) 2142 continue; 2143 2144 if (graph->points_to[w]) 2145 { 2146 if (!graph->points_to[n]) 2147 { 2148 if (first_pred == -1U) 2149 first_pred = w; 2150 else 2151 { 2152 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack); 2153 bitmap_ior (graph->points_to[n], 2154 graph->points_to[first_pred], 2155 graph->points_to[w]); 2156 } 2157 } 2158 else 2159 bitmap_ior_into (graph->points_to[n], graph->points_to[w]); 2160 } 2161 } 2162 2163 /* Indirect nodes get fresh variables and a new pointer equiv class. */ 2164 if (!bitmap_bit_p (graph->direct_nodes, n)) 2165 { 2166 if (!graph->points_to[n]) 2167 { 2168 graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack); 2169 if (first_pred != -1U) 2170 bitmap_copy (graph->points_to[n], graph->points_to[first_pred]); 2171 } 2172 bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n); 2173 graph->pointer_label[n] = pointer_equiv_class++; 2174 equiv_class_label_t ecl; 2175 ecl = equiv_class_lookup_or_add (pointer_equiv_class_table, 2176 graph->points_to[n]); 2177 ecl->equivalence_class = graph->pointer_label[n]; 2178 return; 2179 } 2180 2181 /* If there was only a single non-empty predecessor the pointer equiv 2182 class is the same. */ 2183 if (!graph->points_to[n]) 2184 { 2185 if (first_pred != -1U) 2186 { 2187 graph->pointer_label[n] = graph->pointer_label[first_pred]; 2188 graph->points_to[n] = graph->points_to[first_pred]; 2189 } 2190 return; 2191 } 2192 2193 if (!bitmap_empty_p (graph->points_to[n])) 2194 { 2195 equiv_class_label_t ecl; 2196 ecl = equiv_class_lookup_or_add (pointer_equiv_class_table, 2197 graph->points_to[n]); 2198 if (ecl->equivalence_class == 0) 2199 ecl->equivalence_class = pointer_equiv_class++; 2200 else 2201 { 2202 BITMAP_FREE (graph->points_to[n]); 2203 graph->points_to[n] = ecl->labels; 2204 } 2205 graph->pointer_label[n] = ecl->equivalence_class; 2206 } 2207 } 2208 2209 /* Print the pred graph in dot format. */ 2210 2211 static void 2212 dump_pred_graph (struct scc_info *si, FILE *file) 2213 { 2214 unsigned int i; 2215 2216 /* Only print the graph if it has already been initialized: */ 2217 if (!graph) 2218 return; 2219 2220 /* Prints the header of the dot file: */ 2221 fprintf (file, "strict digraph {\n"); 2222 fprintf (file, " node [\n shape = box\n ]\n"); 2223 fprintf (file, " edge [\n fontsize = \"12\"\n ]\n"); 2224 fprintf (file, "\n // List of nodes and complex constraints in " 2225 "the constraint graph:\n"); 2226 2227 /* The next lines print the nodes in the graph together with the 2228 complex constraints attached to them. */ 2229 for (i = 1; i < graph->size; i++) 2230 { 2231 if (i == FIRST_REF_NODE) 2232 continue; 2233 if (si->node_mapping[i] != i) 2234 continue; 2235 if (i < FIRST_REF_NODE) 2236 fprintf (file, "\"%s\"", get_varinfo (i)->name); 2237 else 2238 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name); 2239 if (graph->points_to[i] 2240 && !bitmap_empty_p (graph->points_to[i])) 2241 { 2242 fprintf (file, "[label=\"%s = {", get_varinfo (i)->name); 2243 unsigned j; 2244 bitmap_iterator bi; 2245 EXECUTE_IF_SET_IN_BITMAP (graph->points_to[i], 0, j, bi) 2246 fprintf (file, " %d", j); 2247 fprintf (file, " }\"]"); 2248 } 2249 fprintf (file, ";\n"); 2250 } 2251 2252 /* Go over the edges. */ 2253 fprintf (file, "\n // Edges in the constraint graph:\n"); 2254 for (i = 1; i < graph->size; i++) 2255 { 2256 unsigned j; 2257 bitmap_iterator bi; 2258 if (si->node_mapping[i] != i) 2259 continue; 2260 EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[i], 0, j, bi) 2261 { 2262 unsigned from = si->node_mapping[j]; 2263 if (from < FIRST_REF_NODE) 2264 fprintf (file, "\"%s\"", get_varinfo (from)->name); 2265 else 2266 fprintf (file, "\"*%s\"", get_varinfo (from - FIRST_REF_NODE)->name); 2267 fprintf (file, " -> "); 2268 if (i < FIRST_REF_NODE) 2269 fprintf (file, "\"%s\"", get_varinfo (i)->name); 2270 else 2271 fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name); 2272 fprintf (file, ";\n"); 2273 } 2274 } 2275 2276 /* Prints the tail of the dot file. */ 2277 fprintf (file, "}\n"); 2278 } 2279 2280 /* Perform offline variable substitution, discovering equivalence 2281 classes, and eliminating non-pointer variables. */ 2282 2283 static struct scc_info * 2284 perform_var_substitution (constraint_graph_t graph) 2285 { 2286 unsigned int i; 2287 unsigned int size = graph->size; 2288 struct scc_info *si = init_scc_info (size); 2289 2290 bitmap_obstack_initialize (&iteration_obstack); 2291 pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511); 2292 location_equiv_class_table 2293 = new hash_table<equiv_class_hasher> (511); 2294 pointer_equiv_class = 1; 2295 location_equiv_class = 1; 2296 2297 /* Condense the nodes, which means to find SCC's, count incoming 2298 predecessors, and unite nodes in SCC's. */ 2299 for (i = 1; i < FIRST_REF_NODE; i++) 2300 if (!bitmap_bit_p (si->visited, si->node_mapping[i])) 2301 condense_visit (graph, si, si->node_mapping[i]); 2302 2303 if (dump_file && (dump_flags & TDF_GRAPH)) 2304 { 2305 fprintf (dump_file, "\n\n// The constraint graph before var-substitution " 2306 "in dot format:\n"); 2307 dump_pred_graph (si, dump_file); 2308 fprintf (dump_file, "\n\n"); 2309 } 2310 2311 bitmap_clear (si->visited); 2312 /* Actually the label the nodes for pointer equivalences */ 2313 for (i = 1; i < FIRST_REF_NODE; i++) 2314 if (!bitmap_bit_p (si->visited, si->node_mapping[i])) 2315 label_visit (graph, si, si->node_mapping[i]); 2316 2317 /* Calculate location equivalence labels. */ 2318 for (i = 1; i < FIRST_REF_NODE; i++) 2319 { 2320 bitmap pointed_by; 2321 bitmap_iterator bi; 2322 unsigned int j; 2323 2324 if (!graph->pointed_by[i]) 2325 continue; 2326 pointed_by = BITMAP_ALLOC (&iteration_obstack); 2327 2328 /* Translate the pointed-by mapping for pointer equivalence 2329 labels. */ 2330 EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi) 2331 { 2332 bitmap_set_bit (pointed_by, 2333 graph->pointer_label[si->node_mapping[j]]); 2334 } 2335 /* The original pointed_by is now dead. */ 2336 BITMAP_FREE (graph->pointed_by[i]); 2337 2338 /* Look up the location equivalence label if one exists, or make 2339 one otherwise. */ 2340 equiv_class_label_t ecl; 2341 ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by); 2342 if (ecl->equivalence_class == 0) 2343 ecl->equivalence_class = location_equiv_class++; 2344 else 2345 { 2346 if (dump_file && (dump_flags & TDF_DETAILS)) 2347 fprintf (dump_file, "Found location equivalence for node %s\n", 2348 get_varinfo (i)->name); 2349 BITMAP_FREE (pointed_by); 2350 } 2351 graph->loc_label[i] = ecl->equivalence_class; 2352 2353 } 2354 2355 if (dump_file && (dump_flags & TDF_DETAILS)) 2356 for (i = 1; i < FIRST_REF_NODE; i++) 2357 { 2358 unsigned j = si->node_mapping[i]; 2359 if (j != i) 2360 { 2361 fprintf (dump_file, "%s node id %d ", 2362 bitmap_bit_p (graph->direct_nodes, i) 2363 ? "Direct" : "Indirect", i); 2364 if (i < FIRST_REF_NODE) 2365 fprintf (dump_file, "\"%s\"", get_varinfo (i)->name); 2366 else 2367 fprintf (dump_file, "\"*%s\"", 2368 get_varinfo (i - FIRST_REF_NODE)->name); 2369 fprintf (dump_file, " mapped to SCC leader node id %d ", j); 2370 if (j < FIRST_REF_NODE) 2371 fprintf (dump_file, "\"%s\"\n", get_varinfo (j)->name); 2372 else 2373 fprintf (dump_file, "\"*%s\"\n", 2374 get_varinfo (j - FIRST_REF_NODE)->name); 2375 } 2376 else 2377 { 2378 fprintf (dump_file, 2379 "Equivalence classes for %s node id %d ", 2380 bitmap_bit_p (graph->direct_nodes, i) 2381 ? "direct" : "indirect", i); 2382 if (i < FIRST_REF_NODE) 2383 fprintf (dump_file, "\"%s\"", get_varinfo (i)->name); 2384 else 2385 fprintf (dump_file, "\"*%s\"", 2386 get_varinfo (i - FIRST_REF_NODE)->name); 2387 fprintf (dump_file, 2388 ": pointer %d, location %d\n", 2389 graph->pointer_label[i], graph->loc_label[i]); 2390 } 2391 } 2392 2393 /* Quickly eliminate our non-pointer variables. */ 2394 2395 for (i = 1; i < FIRST_REF_NODE; i++) 2396 { 2397 unsigned int node = si->node_mapping[i]; 2398 2399 if (graph->pointer_label[node] == 0) 2400 { 2401 if (dump_file && (dump_flags & TDF_DETAILS)) 2402 fprintf (dump_file, 2403 "%s is a non-pointer variable, eliminating edges.\n", 2404 get_varinfo (node)->name); 2405 stats.nonpointer_vars++; 2406 clear_edges_for_node (graph, node); 2407 } 2408 } 2409 2410 return si; 2411 } 2412 2413 /* Free information that was only necessary for variable 2414 substitution. */ 2415 2416 static void 2417 free_var_substitution_info (struct scc_info *si) 2418 { 2419 free_scc_info (si); 2420 free (graph->pointer_label); 2421 free (graph->loc_label); 2422 free (graph->pointed_by); 2423 free (graph->points_to); 2424 free (graph->eq_rep); 2425 sbitmap_free (graph->direct_nodes); 2426 delete pointer_equiv_class_table; 2427 pointer_equiv_class_table = NULL; 2428 delete location_equiv_class_table; 2429 location_equiv_class_table = NULL; 2430 bitmap_obstack_release (&iteration_obstack); 2431 } 2432 2433 /* Return an existing node that is equivalent to NODE, which has 2434 equivalence class LABEL, if one exists. Return NODE otherwise. */ 2435 2436 static unsigned int 2437 find_equivalent_node (constraint_graph_t graph, 2438 unsigned int node, unsigned int label) 2439 { 2440 /* If the address version of this variable is unused, we can 2441 substitute it for anything else with the same label. 2442 Otherwise, we know the pointers are equivalent, but not the 2443 locations, and we can unite them later. */ 2444 2445 if (!bitmap_bit_p (graph->address_taken, node)) 2446 { 2447 gcc_checking_assert (label < graph->size); 2448 2449 if (graph->eq_rep[label] != -1) 2450 { 2451 /* Unify the two variables since we know they are equivalent. */ 2452 if (unite (graph->eq_rep[label], node)) 2453 unify_nodes (graph, graph->eq_rep[label], node, false); 2454 return graph->eq_rep[label]; 2455 } 2456 else 2457 { 2458 graph->eq_rep[label] = node; 2459 graph->pe_rep[label] = node; 2460 } 2461 } 2462 else 2463 { 2464 gcc_checking_assert (label < graph->size); 2465 graph->pe[node] = label; 2466 if (graph->pe_rep[label] == -1) 2467 graph->pe_rep[label] = node; 2468 } 2469 2470 return node; 2471 } 2472 2473 /* Unite pointer equivalent but not location equivalent nodes in 2474 GRAPH. This may only be performed once variable substitution is 2475 finished. */ 2476 2477 static void 2478 unite_pointer_equivalences (constraint_graph_t graph) 2479 { 2480 unsigned int i; 2481 2482 /* Go through the pointer equivalences and unite them to their 2483 representative, if they aren't already. */ 2484 for (i = 1; i < FIRST_REF_NODE; i++) 2485 { 2486 unsigned int label = graph->pe[i]; 2487 if (label) 2488 { 2489 int label_rep = graph->pe_rep[label]; 2490 2491 if (label_rep == -1) 2492 continue; 2493 2494 label_rep = find (label_rep); 2495 if (label_rep >= 0 && unite (label_rep, find (i))) 2496 unify_nodes (graph, label_rep, i, false); 2497 } 2498 } 2499 } 2500 2501 /* Move complex constraints to the GRAPH nodes they belong to. */ 2502 2503 static void 2504 move_complex_constraints (constraint_graph_t graph) 2505 { 2506 int i; 2507 constraint_t c; 2508 2509 FOR_EACH_VEC_ELT (constraints, i, c) 2510 { 2511 if (c) 2512 { 2513 struct constraint_expr lhs = c->lhs; 2514 struct constraint_expr rhs = c->rhs; 2515 2516 if (lhs.type == DEREF) 2517 { 2518 insert_into_complex (graph, lhs.var, c); 2519 } 2520 else if (rhs.type == DEREF) 2521 { 2522 if (!(get_varinfo (lhs.var)->is_special_var)) 2523 insert_into_complex (graph, rhs.var, c); 2524 } 2525 else if (rhs.type != ADDRESSOF && lhs.var > anything_id 2526 && (lhs.offset != 0 || rhs.offset != 0)) 2527 { 2528 insert_into_complex (graph, rhs.var, c); 2529 } 2530 } 2531 } 2532 } 2533 2534 2535 /* Optimize and rewrite complex constraints while performing 2536 collapsing of equivalent nodes. SI is the SCC_INFO that is the 2537 result of perform_variable_substitution. */ 2538 2539 static void 2540 rewrite_constraints (constraint_graph_t graph, 2541 struct scc_info *si) 2542 { 2543 int i; 2544 constraint_t c; 2545 2546 if (flag_checking) 2547 { 2548 for (unsigned int j = 0; j < graph->size; j++) 2549 gcc_assert (find (j) == j); 2550 } 2551 2552 FOR_EACH_VEC_ELT (constraints, i, c) 2553 { 2554 struct constraint_expr lhs = c->lhs; 2555 struct constraint_expr rhs = c->rhs; 2556 unsigned int lhsvar = find (lhs.var); 2557 unsigned int rhsvar = find (rhs.var); 2558 unsigned int lhsnode, rhsnode; 2559 unsigned int lhslabel, rhslabel; 2560 2561 lhsnode = si->node_mapping[lhsvar]; 2562 rhsnode = si->node_mapping[rhsvar]; 2563 lhslabel = graph->pointer_label[lhsnode]; 2564 rhslabel = graph->pointer_label[rhsnode]; 2565 2566 /* See if it is really a non-pointer variable, and if so, ignore 2567 the constraint. */ 2568 if (lhslabel == 0) 2569 { 2570 if (dump_file && (dump_flags & TDF_DETAILS)) 2571 { 2572 2573 fprintf (dump_file, "%s is a non-pointer variable," 2574 "ignoring constraint:", 2575 get_varinfo (lhs.var)->name); 2576 dump_constraint (dump_file, c); 2577 fprintf (dump_file, "\n"); 2578 } 2579 constraints[i] = NULL; 2580 continue; 2581 } 2582 2583 if (rhslabel == 0) 2584 { 2585 if (dump_file && (dump_flags & TDF_DETAILS)) 2586 { 2587 2588 fprintf (dump_file, "%s is a non-pointer variable," 2589 "ignoring constraint:", 2590 get_varinfo (rhs.var)->name); 2591 dump_constraint (dump_file, c); 2592 fprintf (dump_file, "\n"); 2593 } 2594 constraints[i] = NULL; 2595 continue; 2596 } 2597 2598 lhsvar = find_equivalent_node (graph, lhsvar, lhslabel); 2599 rhsvar = find_equivalent_node (graph, rhsvar, rhslabel); 2600 c->lhs.var = lhsvar; 2601 c->rhs.var = rhsvar; 2602 } 2603 } 2604 2605 /* Eliminate indirect cycles involving NODE. Return true if NODE was 2606 part of an SCC, false otherwise. */ 2607 2608 static bool 2609 eliminate_indirect_cycles (unsigned int node) 2610 { 2611 if (graph->indirect_cycles[node] != -1 2612 && !bitmap_empty_p (get_varinfo (node)->solution)) 2613 { 2614 unsigned int i; 2615 auto_vec<unsigned> queue; 2616 int queuepos; 2617 unsigned int to = find (graph->indirect_cycles[node]); 2618 bitmap_iterator bi; 2619 2620 /* We can't touch the solution set and call unify_nodes 2621 at the same time, because unify_nodes is going to do 2622 bitmap unions into it. */ 2623 2624 EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi) 2625 { 2626 if (find (i) == i && i != to) 2627 { 2628 if (unite (to, i)) 2629 queue.safe_push (i); 2630 } 2631 } 2632 2633 for (queuepos = 0; 2634 queue.iterate (queuepos, &i); 2635 queuepos++) 2636 { 2637 unify_nodes (graph, to, i, true); 2638 } 2639 return true; 2640 } 2641 return false; 2642 } 2643 2644 /* Solve the constraint graph GRAPH using our worklist solver. 2645 This is based on the PW* family of solvers from the "Efficient Field 2646 Sensitive Pointer Analysis for C" paper. 2647 It works by iterating over all the graph nodes, processing the complex 2648 constraints and propagating the copy constraints, until everything stops 2649 changed. This corresponds to steps 6-8 in the solving list given above. */ 2650 2651 static void 2652 solve_graph (constraint_graph_t graph) 2653 { 2654 unsigned int size = graph->size; 2655 unsigned int i; 2656 bitmap pts; 2657 2658 changed = BITMAP_ALLOC (NULL); 2659 2660 /* Mark all initial non-collapsed nodes as changed. */ 2661 for (i = 1; i < size; i++) 2662 { 2663 varinfo_t ivi = get_varinfo (i); 2664 if (find (i) == i && !bitmap_empty_p (ivi->solution) 2665 && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i])) 2666 || graph->complex[i].length () > 0)) 2667 bitmap_set_bit (changed, i); 2668 } 2669 2670 /* Allocate a bitmap to be used to store the changed bits. */ 2671 pts = BITMAP_ALLOC (&pta_obstack); 2672 2673 while (!bitmap_empty_p (changed)) 2674 { 2675 unsigned int i; 2676 struct topo_info *ti = init_topo_info (); 2677 stats.iterations++; 2678 2679 bitmap_obstack_initialize (&iteration_obstack); 2680 2681 compute_topo_order (graph, ti); 2682 2683 while (ti->topo_order.length () != 0) 2684 { 2685 2686 i = ti->topo_order.pop (); 2687 2688 /* If this variable is not a representative, skip it. */ 2689 if (find (i) != i) 2690 continue; 2691 2692 /* In certain indirect cycle cases, we may merge this 2693 variable to another. */ 2694 if (eliminate_indirect_cycles (i) && find (i) != i) 2695 continue; 2696 2697 /* If the node has changed, we need to process the 2698 complex constraints and outgoing edges again. */ 2699 if (bitmap_clear_bit (changed, i)) 2700 { 2701 unsigned int j; 2702 constraint_t c; 2703 bitmap solution; 2704 vec<constraint_t> complex = graph->complex[i]; 2705 varinfo_t vi = get_varinfo (i); 2706 bool solution_empty; 2707 2708 /* Compute the changed set of solution bits. If anything 2709 is in the solution just propagate that. */ 2710 if (bitmap_bit_p (vi->solution, anything_id)) 2711 { 2712 /* If anything is also in the old solution there is 2713 nothing to do. 2714 ??? But we shouldn't ended up with "changed" set ... */ 2715 if (vi->oldsolution 2716 && bitmap_bit_p (vi->oldsolution, anything_id)) 2717 continue; 2718 bitmap_copy (pts, get_varinfo (find (anything_id))->solution); 2719 } 2720 else if (vi->oldsolution) 2721 bitmap_and_compl (pts, vi->solution, vi->oldsolution); 2722 else 2723 bitmap_copy (pts, vi->solution); 2724 2725 if (bitmap_empty_p (pts)) 2726 continue; 2727 2728 if (vi->oldsolution) 2729 bitmap_ior_into (vi->oldsolution, pts); 2730 else 2731 { 2732 vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack); 2733 bitmap_copy (vi->oldsolution, pts); 2734 } 2735 2736 solution = vi->solution; 2737 solution_empty = bitmap_empty_p (solution); 2738 2739 /* Process the complex constraints */ 2740 bitmap expanded_pts = NULL; 2741 FOR_EACH_VEC_ELT (complex, j, c) 2742 { 2743 /* XXX: This is going to unsort the constraints in 2744 some cases, which will occasionally add duplicate 2745 constraints during unification. This does not 2746 affect correctness. */ 2747 c->lhs.var = find (c->lhs.var); 2748 c->rhs.var = find (c->rhs.var); 2749 2750 /* The only complex constraint that can change our 2751 solution to non-empty, given an empty solution, 2752 is a constraint where the lhs side is receiving 2753 some set from elsewhere. */ 2754 if (!solution_empty || c->lhs.type != DEREF) 2755 do_complex_constraint (graph, c, pts, &expanded_pts); 2756 } 2757 BITMAP_FREE (expanded_pts); 2758 2759 solution_empty = bitmap_empty_p (solution); 2760 2761 if (!solution_empty) 2762 { 2763 bitmap_iterator bi; 2764 unsigned eff_escaped_id = find (escaped_id); 2765 2766 /* Propagate solution to all successors. */ 2767 EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 2768 0, j, bi) 2769 { 2770 bitmap tmp; 2771 bool flag; 2772 2773 unsigned int to = find (j); 2774 tmp = get_varinfo (to)->solution; 2775 flag = false; 2776 2777 /* Don't try to propagate to ourselves. */ 2778 if (to == i) 2779 continue; 2780 2781 /* If we propagate from ESCAPED use ESCAPED as 2782 placeholder. */ 2783 if (i == eff_escaped_id) 2784 flag = bitmap_set_bit (tmp, escaped_id); 2785 else 2786 flag = bitmap_ior_into (tmp, pts); 2787 2788 if (flag) 2789 bitmap_set_bit (changed, to); 2790 } 2791 } 2792 } 2793 } 2794 free_topo_info (ti); 2795 bitmap_obstack_release (&iteration_obstack); 2796 } 2797 2798 BITMAP_FREE (pts); 2799 BITMAP_FREE (changed); 2800 bitmap_obstack_release (&oldpta_obstack); 2801 } 2802 2803 /* Map from trees to variable infos. */ 2804 static hash_map<tree, varinfo_t> *vi_for_tree; 2805 2806 2807 /* Insert ID as the variable id for tree T in the vi_for_tree map. */ 2808 2809 static void 2810 insert_vi_for_tree (tree t, varinfo_t vi) 2811 { 2812 gcc_assert (vi); 2813 gcc_assert (!vi_for_tree->put (t, vi)); 2814 } 2815 2816 /* Find the variable info for tree T in VI_FOR_TREE. If T does not 2817 exist in the map, return NULL, otherwise, return the varinfo we found. */ 2818 2819 static varinfo_t 2820 lookup_vi_for_tree (tree t) 2821 { 2822 varinfo_t *slot = vi_for_tree->get (t); 2823 if (slot == NULL) 2824 return NULL; 2825 2826 return *slot; 2827 } 2828 2829 /* Return a printable name for DECL */ 2830 2831 static const char * 2832 alias_get_name (tree decl) 2833 { 2834 const char *res = NULL; 2835 char *temp; 2836 2837 if (!dump_file) 2838 return "NULL"; 2839 2840 if (TREE_CODE (decl) == SSA_NAME) 2841 { 2842 res = get_name (decl); 2843 if (res) 2844 temp = xasprintf ("%s_%u", res, SSA_NAME_VERSION (decl)); 2845 else 2846 temp = xasprintf ("_%u", SSA_NAME_VERSION (decl)); 2847 res = ggc_strdup (temp); 2848 free (temp); 2849 } 2850 else if (DECL_P (decl)) 2851 { 2852 if (DECL_ASSEMBLER_NAME_SET_P (decl)) 2853 res = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl)); 2854 else 2855 { 2856 res = get_name (decl); 2857 if (!res) 2858 { 2859 temp = xasprintf ("D.%u", DECL_UID (decl)); 2860 res = ggc_strdup (temp); 2861 free (temp); 2862 } 2863 } 2864 } 2865 if (res != NULL) 2866 return res; 2867 2868 return "NULL"; 2869 } 2870 2871 /* Find the variable id for tree T in the map. 2872 If T doesn't exist in the map, create an entry for it and return it. */ 2873 2874 static varinfo_t 2875 get_vi_for_tree (tree t) 2876 { 2877 varinfo_t *slot = vi_for_tree->get (t); 2878 if (slot == NULL) 2879 { 2880 unsigned int id = create_variable_info_for (t, alias_get_name (t), false); 2881 return get_varinfo (id); 2882 } 2883 2884 return *slot; 2885 } 2886 2887 /* Get a scalar constraint expression for a new temporary variable. */ 2888 2889 static struct constraint_expr 2890 new_scalar_tmp_constraint_exp (const char *name, bool add_id) 2891 { 2892 struct constraint_expr tmp; 2893 varinfo_t vi; 2894 2895 vi = new_var_info (NULL_TREE, name, add_id); 2896 vi->offset = 0; 2897 vi->size = -1; 2898 vi->fullsize = -1; 2899 vi->is_full_var = 1; 2900 2901 tmp.var = vi->id; 2902 tmp.type = SCALAR; 2903 tmp.offset = 0; 2904 2905 return tmp; 2906 } 2907 2908 /* Get a constraint expression vector from an SSA_VAR_P node. 2909 If address_p is true, the result will be taken its address of. */ 2910 2911 static void 2912 get_constraint_for_ssa_var (tree t, vec<ce_s> *results, bool address_p) 2913 { 2914 struct constraint_expr cexpr; 2915 varinfo_t vi; 2916 2917 /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */ 2918 gcc_assert (TREE_CODE (t) == SSA_NAME || DECL_P (t)); 2919 2920 /* For parameters, get at the points-to set for the actual parm 2921 decl. */ 2922 if (TREE_CODE (t) == SSA_NAME 2923 && SSA_NAME_IS_DEFAULT_DEF (t) 2924 && (TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL 2925 || TREE_CODE (SSA_NAME_VAR (t)) == RESULT_DECL)) 2926 { 2927 get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p); 2928 return; 2929 } 2930 2931 /* For global variables resort to the alias target. */ 2932 if (TREE_CODE (t) == VAR_DECL 2933 && (TREE_STATIC (t) || DECL_EXTERNAL (t))) 2934 { 2935 varpool_node *node = varpool_node::get (t); 2936 if (node && node->alias && node->analyzed) 2937 { 2938 node = node->ultimate_alias_target (); 2939 /* Canonicalize the PT uid of all aliases to the ultimate target. 2940 ??? Hopefully the set of aliases can't change in a way that 2941 changes the ultimate alias target. */ 2942 gcc_assert ((! DECL_PT_UID_SET_P (node->decl) 2943 || DECL_PT_UID (node->decl) == DECL_UID (node->decl)) 2944 && (! DECL_PT_UID_SET_P (t) 2945 || DECL_PT_UID (t) == DECL_UID (node->decl))); 2946 DECL_PT_UID (t) = DECL_UID (node->decl); 2947 t = node->decl; 2948 } 2949 } 2950 2951 vi = get_vi_for_tree (t); 2952 cexpr.var = vi->id; 2953 cexpr.type = SCALAR; 2954 cexpr.offset = 0; 2955 2956 /* If we are not taking the address of the constraint expr, add all 2957 sub-fiels of the variable as well. */ 2958 if (!address_p 2959 && !vi->is_full_var) 2960 { 2961 for (; vi; vi = vi_next (vi)) 2962 { 2963 cexpr.var = vi->id; 2964 results->safe_push (cexpr); 2965 } 2966 return; 2967 } 2968 2969 results->safe_push (cexpr); 2970 } 2971 2972 /* Process constraint T, performing various simplifications and then 2973 adding it to our list of overall constraints. */ 2974 2975 static void 2976 process_constraint (constraint_t t) 2977 { 2978 struct constraint_expr rhs = t->rhs; 2979 struct constraint_expr lhs = t->lhs; 2980 2981 gcc_assert (rhs.var < varmap.length ()); 2982 gcc_assert (lhs.var < varmap.length ()); 2983 2984 /* If we didn't get any useful constraint from the lhs we get 2985 &ANYTHING as fallback from get_constraint_for. Deal with 2986 it here by turning it into *ANYTHING. */ 2987 if (lhs.type == ADDRESSOF 2988 && lhs.var == anything_id) 2989 lhs.type = DEREF; 2990 2991 /* ADDRESSOF on the lhs is invalid. */ 2992 gcc_assert (lhs.type != ADDRESSOF); 2993 2994 /* We shouldn't add constraints from things that cannot have pointers. 2995 It's not completely trivial to avoid in the callers, so do it here. */ 2996 if (rhs.type != ADDRESSOF 2997 && !get_varinfo (rhs.var)->may_have_pointers) 2998 return; 2999 3000 /* Likewise adding to the solution of a non-pointer var isn't useful. */ 3001 if (!get_varinfo (lhs.var)->may_have_pointers) 3002 return; 3003 3004 /* This can happen in our IR with things like n->a = *p */ 3005 if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id) 3006 { 3007 /* Split into tmp = *rhs, *lhs = tmp */ 3008 struct constraint_expr tmplhs; 3009 tmplhs = new_scalar_tmp_constraint_exp ("doubledereftmp", true); 3010 process_constraint (new_constraint (tmplhs, rhs)); 3011 process_constraint (new_constraint (lhs, tmplhs)); 3012 } 3013 else if ((rhs.type != SCALAR || rhs.offset != 0) && lhs.type == DEREF) 3014 { 3015 /* Split into tmp = &rhs, *lhs = tmp */ 3016 struct constraint_expr tmplhs; 3017 tmplhs = new_scalar_tmp_constraint_exp ("derefaddrtmp", true); 3018 process_constraint (new_constraint (tmplhs, rhs)); 3019 process_constraint (new_constraint (lhs, tmplhs)); 3020 } 3021 else 3022 { 3023 gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0); 3024 constraints.safe_push (t); 3025 } 3026 } 3027 3028 3029 /* Return the position, in bits, of FIELD_DECL from the beginning of its 3030 structure. */ 3031 3032 static HOST_WIDE_INT 3033 bitpos_of_field (const tree fdecl) 3034 { 3035 if (!tree_fits_shwi_p (DECL_FIELD_OFFSET (fdecl)) 3036 || !tree_fits_shwi_p (DECL_FIELD_BIT_OFFSET (fdecl))) 3037 return -1; 3038 3039 return (tree_to_shwi (DECL_FIELD_OFFSET (fdecl)) * BITS_PER_UNIT 3040 + tree_to_shwi (DECL_FIELD_BIT_OFFSET (fdecl))); 3041 } 3042 3043 3044 /* Get constraint expressions for offsetting PTR by OFFSET. Stores the 3045 resulting constraint expressions in *RESULTS. */ 3046 3047 static void 3048 get_constraint_for_ptr_offset (tree ptr, tree offset, 3049 vec<ce_s> *results) 3050 { 3051 struct constraint_expr c; 3052 unsigned int j, n; 3053 HOST_WIDE_INT rhsoffset; 3054 3055 /* If we do not do field-sensitive PTA adding offsets to pointers 3056 does not change the points-to solution. */ 3057 if (!use_field_sensitive) 3058 { 3059 get_constraint_for_rhs (ptr, results); 3060 return; 3061 } 3062 3063 /* If the offset is not a non-negative integer constant that fits 3064 in a HOST_WIDE_INT, we have to fall back to a conservative 3065 solution which includes all sub-fields of all pointed-to 3066 variables of ptr. */ 3067 if (offset == NULL_TREE 3068 || TREE_CODE (offset) != INTEGER_CST) 3069 rhsoffset = UNKNOWN_OFFSET; 3070 else 3071 { 3072 /* Sign-extend the offset. */ 3073 offset_int soffset = offset_int::from (offset, SIGNED); 3074 if (!wi::fits_shwi_p (soffset)) 3075 rhsoffset = UNKNOWN_OFFSET; 3076 else 3077 { 3078 /* Make sure the bit-offset also fits. */ 3079 HOST_WIDE_INT rhsunitoffset = soffset.to_shwi (); 3080 rhsoffset = rhsunitoffset * BITS_PER_UNIT; 3081 if (rhsunitoffset != rhsoffset / BITS_PER_UNIT) 3082 rhsoffset = UNKNOWN_OFFSET; 3083 } 3084 } 3085 3086 get_constraint_for_rhs (ptr, results); 3087 if (rhsoffset == 0) 3088 return; 3089 3090 /* As we are eventually appending to the solution do not use 3091 vec::iterate here. */ 3092 n = results->length (); 3093 for (j = 0; j < n; j++) 3094 { 3095 varinfo_t curr; 3096 c = (*results)[j]; 3097 curr = get_varinfo (c.var); 3098 3099 if (c.type == ADDRESSOF 3100 /* If this varinfo represents a full variable just use it. */ 3101 && curr->is_full_var) 3102 ; 3103 else if (c.type == ADDRESSOF 3104 /* If we do not know the offset add all subfields. */ 3105 && rhsoffset == UNKNOWN_OFFSET) 3106 { 3107 varinfo_t temp = get_varinfo (curr->head); 3108 do 3109 { 3110 struct constraint_expr c2; 3111 c2.var = temp->id; 3112 c2.type = ADDRESSOF; 3113 c2.offset = 0; 3114 if (c2.var != c.var) 3115 results->safe_push (c2); 3116 temp = vi_next (temp); 3117 } 3118 while (temp); 3119 } 3120 else if (c.type == ADDRESSOF) 3121 { 3122 varinfo_t temp; 3123 unsigned HOST_WIDE_INT offset = curr->offset + rhsoffset; 3124 3125 /* If curr->offset + rhsoffset is less than zero adjust it. */ 3126 if (rhsoffset < 0 3127 && curr->offset < offset) 3128 offset = 0; 3129 3130 /* We have to include all fields that overlap the current 3131 field shifted by rhsoffset. And we include at least 3132 the last or the first field of the variable to represent 3133 reachability of off-bound addresses, in particular &object + 1, 3134 conservatively correct. */ 3135 temp = first_or_preceding_vi_for_offset (curr, offset); 3136 c.var = temp->id; 3137 c.offset = 0; 3138 temp = vi_next (temp); 3139 while (temp 3140 && temp->offset < offset + curr->size) 3141 { 3142 struct constraint_expr c2; 3143 c2.var = temp->id; 3144 c2.type = ADDRESSOF; 3145 c2.offset = 0; 3146 results->safe_push (c2); 3147 temp = vi_next (temp); 3148 } 3149 } 3150 else if (c.type == SCALAR) 3151 { 3152 gcc_assert (c.offset == 0); 3153 c.offset = rhsoffset; 3154 } 3155 else 3156 /* We shouldn't get any DEREFs here. */ 3157 gcc_unreachable (); 3158 3159 (*results)[j] = c; 3160 } 3161 } 3162 3163 3164 /* Given a COMPONENT_REF T, return the constraint_expr vector for it. 3165 If address_p is true the result will be taken its address of. 3166 If lhs_p is true then the constraint expression is assumed to be used 3167 as the lhs. */ 3168 3169 static void 3170 get_constraint_for_component_ref (tree t, vec<ce_s> *results, 3171 bool address_p, bool lhs_p) 3172 { 3173 tree orig_t = t; 3174 HOST_WIDE_INT bitsize = -1; 3175 HOST_WIDE_INT bitmaxsize = -1; 3176 HOST_WIDE_INT bitpos; 3177 bool reverse; 3178 tree forzero; 3179 3180 /* Some people like to do cute things like take the address of 3181 &0->a.b */ 3182 forzero = t; 3183 while (handled_component_p (forzero) 3184 || INDIRECT_REF_P (forzero) 3185 || TREE_CODE (forzero) == MEM_REF) 3186 forzero = TREE_OPERAND (forzero, 0); 3187 3188 if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero)) 3189 { 3190 struct constraint_expr temp; 3191 3192 temp.offset = 0; 3193 temp.var = integer_id; 3194 temp.type = SCALAR; 3195 results->safe_push (temp); 3196 return; 3197 } 3198 3199 t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize, &reverse); 3200 3201 /* Pretend to take the address of the base, we'll take care of 3202 adding the required subset of sub-fields below. */ 3203 get_constraint_for_1 (t, results, true, lhs_p); 3204 gcc_assert (results->length () == 1); 3205 struct constraint_expr &result = results->last (); 3206 3207 if (result.type == SCALAR 3208 && get_varinfo (result.var)->is_full_var) 3209 /* For single-field vars do not bother about the offset. */ 3210 result.offset = 0; 3211 else if (result.type == SCALAR) 3212 { 3213 /* In languages like C, you can access one past the end of an 3214 array. You aren't allowed to dereference it, so we can 3215 ignore this constraint. When we handle pointer subtraction, 3216 we may have to do something cute here. */ 3217 3218 if ((unsigned HOST_WIDE_INT)bitpos < get_varinfo (result.var)->fullsize 3219 && bitmaxsize != 0) 3220 { 3221 /* It's also not true that the constraint will actually start at the 3222 right offset, it may start in some padding. We only care about 3223 setting the constraint to the first actual field it touches, so 3224 walk to find it. */ 3225 struct constraint_expr cexpr = result; 3226 varinfo_t curr; 3227 results->pop (); 3228 cexpr.offset = 0; 3229 for (curr = get_varinfo (cexpr.var); curr; curr = vi_next (curr)) 3230 { 3231 if (ranges_overlap_p (curr->offset, curr->size, 3232 bitpos, bitmaxsize)) 3233 { 3234 cexpr.var = curr->id; 3235 results->safe_push (cexpr); 3236 if (address_p) 3237 break; 3238 } 3239 } 3240 /* If we are going to take the address of this field then 3241 to be able to compute reachability correctly add at least 3242 the last field of the variable. */ 3243 if (address_p && results->length () == 0) 3244 { 3245 curr = get_varinfo (cexpr.var); 3246 while (curr->next != 0) 3247 curr = vi_next (curr); 3248 cexpr.var = curr->id; 3249 results->safe_push (cexpr); 3250 } 3251 else if (results->length () == 0) 3252 /* Assert that we found *some* field there. The user couldn't be 3253 accessing *only* padding. */ 3254 /* Still the user could access one past the end of an array 3255 embedded in a struct resulting in accessing *only* padding. */ 3256 /* Or accessing only padding via type-punning to a type 3257 that has a filed just in padding space. */ 3258 { 3259 cexpr.type = SCALAR; 3260 cexpr.var = anything_id; 3261 cexpr.offset = 0; 3262 results->safe_push (cexpr); 3263 } 3264 } 3265 else if (bitmaxsize == 0) 3266 { 3267 if (dump_file && (dump_flags & TDF_DETAILS)) 3268 fprintf (dump_file, "Access to zero-sized part of variable," 3269 "ignoring\n"); 3270 } 3271 else 3272 if (dump_file && (dump_flags & TDF_DETAILS)) 3273 fprintf (dump_file, "Access to past the end of variable, ignoring\n"); 3274 } 3275 else if (result.type == DEREF) 3276 { 3277 /* If we do not know exactly where the access goes say so. Note 3278 that only for non-structure accesses we know that we access 3279 at most one subfiled of any variable. */ 3280 if (bitpos == -1 3281 || bitsize != bitmaxsize 3282 || AGGREGATE_TYPE_P (TREE_TYPE (orig_t)) 3283 || result.offset == UNKNOWN_OFFSET) 3284 result.offset = UNKNOWN_OFFSET; 3285 else 3286 result.offset += bitpos; 3287 } 3288 else if (result.type == ADDRESSOF) 3289 { 3290 /* We can end up here for component references on a 3291 VIEW_CONVERT_EXPR <>(&foobar). */ 3292 result.type = SCALAR; 3293 result.var = anything_id; 3294 result.offset = 0; 3295 } 3296 else 3297 gcc_unreachable (); 3298 } 3299 3300 3301 /* Dereference the constraint expression CONS, and return the result. 3302 DEREF (ADDRESSOF) = SCALAR 3303 DEREF (SCALAR) = DEREF 3304 DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp)) 3305 This is needed so that we can handle dereferencing DEREF constraints. */ 3306 3307 static void 3308 do_deref (vec<ce_s> *constraints) 3309 { 3310 struct constraint_expr *c; 3311 unsigned int i = 0; 3312 3313 FOR_EACH_VEC_ELT (*constraints, i, c) 3314 { 3315 if (c->type == SCALAR) 3316 c->type = DEREF; 3317 else if (c->type == ADDRESSOF) 3318 c->type = SCALAR; 3319 else if (c->type == DEREF) 3320 { 3321 struct constraint_expr tmplhs; 3322 tmplhs = new_scalar_tmp_constraint_exp ("dereftmp", true); 3323 process_constraint (new_constraint (tmplhs, *c)); 3324 c->var = tmplhs.var; 3325 } 3326 else 3327 gcc_unreachable (); 3328 } 3329 } 3330 3331 /* Given a tree T, return the constraint expression for taking the 3332 address of it. */ 3333 3334 static void 3335 get_constraint_for_address_of (tree t, vec<ce_s> *results) 3336 { 3337 struct constraint_expr *c; 3338 unsigned int i; 3339 3340 get_constraint_for_1 (t, results, true, true); 3341 3342 FOR_EACH_VEC_ELT (*results, i, c) 3343 { 3344 if (c->type == DEREF) 3345 c->type = SCALAR; 3346 else 3347 c->type = ADDRESSOF; 3348 } 3349 } 3350 3351 /* Given a tree T, return the constraint expression for it. */ 3352 3353 static void 3354 get_constraint_for_1 (tree t, vec<ce_s> *results, bool address_p, 3355 bool lhs_p) 3356 { 3357 struct constraint_expr temp; 3358 3359 /* x = integer is all glommed to a single variable, which doesn't 3360 point to anything by itself. That is, of course, unless it is an 3361 integer constant being treated as a pointer, in which case, we 3362 will return that this is really the addressof anything. This 3363 happens below, since it will fall into the default case. The only 3364 case we know something about an integer treated like a pointer is 3365 when it is the NULL pointer, and then we just say it points to 3366 NULL. 3367 3368 Do not do that if -fno-delete-null-pointer-checks though, because 3369 in that case *NULL does not fail, so it _should_ alias *anything. 3370 It is not worth adding a new option or renaming the existing one, 3371 since this case is relatively obscure. */ 3372 if ((TREE_CODE (t) == INTEGER_CST 3373 && integer_zerop (t)) 3374 /* The only valid CONSTRUCTORs in gimple with pointer typed 3375 elements are zero-initializer. But in IPA mode we also 3376 process global initializers, so verify at least. */ 3377 || (TREE_CODE (t) == CONSTRUCTOR 3378 && CONSTRUCTOR_NELTS (t) == 0)) 3379 { 3380 if (flag_delete_null_pointer_checks) 3381 temp.var = nothing_id; 3382 else 3383 temp.var = nonlocal_id; 3384 temp.type = ADDRESSOF; 3385 temp.offset = 0; 3386 results->safe_push (temp); 3387 return; 3388 } 3389 3390 /* String constants are read-only, ideally we'd have a CONST_DECL 3391 for those. */ 3392 if (TREE_CODE (t) == STRING_CST) 3393 { 3394 temp.var = string_id; 3395 temp.type = SCALAR; 3396 temp.offset = 0; 3397 results->safe_push (temp); 3398 return; 3399 } 3400 3401 switch (TREE_CODE_CLASS (TREE_CODE (t))) 3402 { 3403 case tcc_expression: 3404 { 3405 switch (TREE_CODE (t)) 3406 { 3407 case ADDR_EXPR: 3408 get_constraint_for_address_of (TREE_OPERAND (t, 0), results); 3409 return; 3410 default:; 3411 } 3412 break; 3413 } 3414 case tcc_reference: 3415 { 3416 switch (TREE_CODE (t)) 3417 { 3418 case MEM_REF: 3419 { 3420 struct constraint_expr cs; 3421 varinfo_t vi, curr; 3422 get_constraint_for_ptr_offset (TREE_OPERAND (t, 0), 3423 TREE_OPERAND (t, 1), results); 3424 do_deref (results); 3425 3426 /* If we are not taking the address then make sure to process 3427 all subvariables we might access. */ 3428 if (address_p) 3429 return; 3430 3431 cs = results->last (); 3432 if (cs.type == DEREF 3433 && type_can_have_subvars (TREE_TYPE (t))) 3434 { 3435 /* For dereferences this means we have to defer it 3436 to solving time. */ 3437 results->last ().offset = UNKNOWN_OFFSET; 3438 return; 3439 } 3440 if (cs.type != SCALAR) 3441 return; 3442 3443 vi = get_varinfo (cs.var); 3444 curr = vi_next (vi); 3445 if (!vi->is_full_var 3446 && curr) 3447 { 3448 unsigned HOST_WIDE_INT size; 3449 if (tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (t)))) 3450 size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (t))); 3451 else 3452 size = -1; 3453 for (; curr; curr = vi_next (curr)) 3454 { 3455 if (curr->offset - vi->offset < size) 3456 { 3457 cs.var = curr->id; 3458 results->safe_push (cs); 3459 } 3460 else 3461 break; 3462 } 3463 } 3464 return; 3465 } 3466 case ARRAY_REF: 3467 case ARRAY_RANGE_REF: 3468 case COMPONENT_REF: 3469 case IMAGPART_EXPR: 3470 case REALPART_EXPR: 3471 case BIT_FIELD_REF: 3472 get_constraint_for_component_ref (t, results, address_p, lhs_p); 3473 return; 3474 case VIEW_CONVERT_EXPR: 3475 get_constraint_for_1 (TREE_OPERAND (t, 0), results, address_p, 3476 lhs_p); 3477 return; 3478 /* We are missing handling for TARGET_MEM_REF here. */ 3479 default:; 3480 } 3481 break; 3482 } 3483 case tcc_exceptional: 3484 { 3485 switch (TREE_CODE (t)) 3486 { 3487 case SSA_NAME: 3488 { 3489 get_constraint_for_ssa_var (t, results, address_p); 3490 return; 3491 } 3492 case CONSTRUCTOR: 3493 { 3494 unsigned int i; 3495 tree val; 3496 auto_vec<ce_s> tmp; 3497 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (t), i, val) 3498 { 3499 struct constraint_expr *rhsp; 3500 unsigned j; 3501 get_constraint_for_1 (val, &tmp, address_p, lhs_p); 3502 FOR_EACH_VEC_ELT (tmp, j, rhsp) 3503 results->safe_push (*rhsp); 3504 tmp.truncate (0); 3505 } 3506 /* We do not know whether the constructor was complete, 3507 so technically we have to add &NOTHING or &ANYTHING 3508 like we do for an empty constructor as well. */ 3509 return; 3510 } 3511 default:; 3512 } 3513 break; 3514 } 3515 case tcc_declaration: 3516 { 3517 get_constraint_for_ssa_var (t, results, address_p); 3518 return; 3519 } 3520 case tcc_constant: 3521 { 3522 /* We cannot refer to automatic variables through constants. */ 3523 temp.type = ADDRESSOF; 3524 temp.var = nonlocal_id; 3525 temp.offset = 0; 3526 results->safe_push (temp); 3527 return; 3528 } 3529 default:; 3530 } 3531 3532 /* The default fallback is a constraint from anything. */ 3533 temp.type = ADDRESSOF; 3534 temp.var = anything_id; 3535 temp.offset = 0; 3536 results->safe_push (temp); 3537 } 3538 3539 /* Given a gimple tree T, return the constraint expression vector for it. */ 3540 3541 static void 3542 get_constraint_for (tree t, vec<ce_s> *results) 3543 { 3544 gcc_assert (results->length () == 0); 3545 3546 get_constraint_for_1 (t, results, false, true); 3547 } 3548 3549 /* Given a gimple tree T, return the constraint expression vector for it 3550 to be used as the rhs of a constraint. */ 3551 3552 static void 3553 get_constraint_for_rhs (tree t, vec<ce_s> *results) 3554 { 3555 gcc_assert (results->length () == 0); 3556 3557 get_constraint_for_1 (t, results, false, false); 3558 } 3559 3560 3561 /* Efficiently generates constraints from all entries in *RHSC to all 3562 entries in *LHSC. */ 3563 3564 static void 3565 process_all_all_constraints (vec<ce_s> lhsc, 3566 vec<ce_s> rhsc) 3567 { 3568 struct constraint_expr *lhsp, *rhsp; 3569 unsigned i, j; 3570 3571 if (lhsc.length () <= 1 || rhsc.length () <= 1) 3572 { 3573 FOR_EACH_VEC_ELT (lhsc, i, lhsp) 3574 FOR_EACH_VEC_ELT (rhsc, j, rhsp) 3575 process_constraint (new_constraint (*lhsp, *rhsp)); 3576 } 3577 else 3578 { 3579 struct constraint_expr tmp; 3580 tmp = new_scalar_tmp_constraint_exp ("allalltmp", true); 3581 FOR_EACH_VEC_ELT (rhsc, i, rhsp) 3582 process_constraint (new_constraint (tmp, *rhsp)); 3583 FOR_EACH_VEC_ELT (lhsc, i, lhsp) 3584 process_constraint (new_constraint (*lhsp, tmp)); 3585 } 3586 } 3587 3588 /* Handle aggregate copies by expanding into copies of the respective 3589 fields of the structures. */ 3590 3591 static void 3592 do_structure_copy (tree lhsop, tree rhsop) 3593 { 3594 struct constraint_expr *lhsp, *rhsp; 3595 auto_vec<ce_s> lhsc; 3596 auto_vec<ce_s> rhsc; 3597 unsigned j; 3598 3599 get_constraint_for (lhsop, &lhsc); 3600 get_constraint_for_rhs (rhsop, &rhsc); 3601 lhsp = &lhsc[0]; 3602 rhsp = &rhsc[0]; 3603 if (lhsp->type == DEREF 3604 || (lhsp->type == ADDRESSOF && lhsp->var == anything_id) 3605 || rhsp->type == DEREF) 3606 { 3607 if (lhsp->type == DEREF) 3608 { 3609 gcc_assert (lhsc.length () == 1); 3610 lhsp->offset = UNKNOWN_OFFSET; 3611 } 3612 if (rhsp->type == DEREF) 3613 { 3614 gcc_assert (rhsc.length () == 1); 3615 rhsp->offset = UNKNOWN_OFFSET; 3616 } 3617 process_all_all_constraints (lhsc, rhsc); 3618 } 3619 else if (lhsp->type == SCALAR 3620 && (rhsp->type == SCALAR 3621 || rhsp->type == ADDRESSOF)) 3622 { 3623 HOST_WIDE_INT lhssize, lhsmaxsize, lhsoffset; 3624 HOST_WIDE_INT rhssize, rhsmaxsize, rhsoffset; 3625 bool reverse; 3626 unsigned k = 0; 3627 get_ref_base_and_extent (lhsop, &lhsoffset, &lhssize, &lhsmaxsize, 3628 &reverse); 3629 get_ref_base_and_extent (rhsop, &rhsoffset, &rhssize, &rhsmaxsize, 3630 &reverse); 3631 for (j = 0; lhsc.iterate (j, &lhsp);) 3632 { 3633 varinfo_t lhsv, rhsv; 3634 rhsp = &rhsc[k]; 3635 lhsv = get_varinfo (lhsp->var); 3636 rhsv = get_varinfo (rhsp->var); 3637 if (lhsv->may_have_pointers 3638 && (lhsv->is_full_var 3639 || rhsv->is_full_var 3640 || ranges_overlap_p (lhsv->offset + rhsoffset, lhsv->size, 3641 rhsv->offset + lhsoffset, rhsv->size))) 3642 process_constraint (new_constraint (*lhsp, *rhsp)); 3643 if (!rhsv->is_full_var 3644 && (lhsv->is_full_var 3645 || (lhsv->offset + rhsoffset + lhsv->size 3646 > rhsv->offset + lhsoffset + rhsv->size))) 3647 { 3648 ++k; 3649 if (k >= rhsc.length ()) 3650 break; 3651 } 3652 else 3653 ++j; 3654 } 3655 } 3656 else 3657 gcc_unreachable (); 3658 } 3659 3660 /* Create constraints ID = { rhsc }. */ 3661 3662 static void 3663 make_constraints_to (unsigned id, vec<ce_s> rhsc) 3664 { 3665 struct constraint_expr *c; 3666 struct constraint_expr includes; 3667 unsigned int j; 3668 3669 includes.var = id; 3670 includes.offset = 0; 3671 includes.type = SCALAR; 3672 3673 FOR_EACH_VEC_ELT (rhsc, j, c) 3674 process_constraint (new_constraint (includes, *c)); 3675 } 3676 3677 /* Create a constraint ID = OP. */ 3678 3679 static void 3680 make_constraint_to (unsigned id, tree op) 3681 { 3682 auto_vec<ce_s> rhsc; 3683 get_constraint_for_rhs (op, &rhsc); 3684 make_constraints_to (id, rhsc); 3685 } 3686 3687 /* Create a constraint ID = &FROM. */ 3688 3689 static void 3690 make_constraint_from (varinfo_t vi, int from) 3691 { 3692 struct constraint_expr lhs, rhs; 3693 3694 lhs.var = vi->id; 3695 lhs.offset = 0; 3696 lhs.type = SCALAR; 3697 3698 rhs.var = from; 3699 rhs.offset = 0; 3700 rhs.type = ADDRESSOF; 3701 process_constraint (new_constraint (lhs, rhs)); 3702 } 3703 3704 /* Create a constraint ID = FROM. */ 3705 3706 static void 3707 make_copy_constraint (varinfo_t vi, int from) 3708 { 3709 struct constraint_expr lhs, rhs; 3710 3711 lhs.var = vi->id; 3712 lhs.offset = 0; 3713 lhs.type = SCALAR; 3714 3715 rhs.var = from; 3716 rhs.offset = 0; 3717 rhs.type = SCALAR; 3718 process_constraint (new_constraint (lhs, rhs)); 3719 } 3720 3721 /* Make constraints necessary to make OP escape. */ 3722 3723 static void 3724 make_escape_constraint (tree op) 3725 { 3726 make_constraint_to (escaped_id, op); 3727 } 3728 3729 /* Add constraints to that the solution of VI is transitively closed. */ 3730 3731 static void 3732 make_transitive_closure_constraints (varinfo_t vi) 3733 { 3734 struct constraint_expr lhs, rhs; 3735 3736 /* VAR = *(VAR + UNKNOWN); */ 3737 lhs.type = SCALAR; 3738 lhs.var = vi->id; 3739 lhs.offset = 0; 3740 rhs.type = DEREF; 3741 rhs.var = vi->id; 3742 rhs.offset = UNKNOWN_OFFSET; 3743 process_constraint (new_constraint (lhs, rhs)); 3744 } 3745 3746 /* Add constraints to that the solution of VI has all subvariables added. */ 3747 3748 static void 3749 make_any_offset_constraints (varinfo_t vi) 3750 { 3751 struct constraint_expr lhs, rhs; 3752 3753 /* VAR = VAR + UNKNOWN; */ 3754 lhs.type = SCALAR; 3755 lhs.var = vi->id; 3756 lhs.offset = 0; 3757 rhs.type = SCALAR; 3758 rhs.var = vi->id; 3759 rhs.offset = UNKNOWN_OFFSET; 3760 process_constraint (new_constraint (lhs, rhs)); 3761 } 3762 3763 /* Temporary storage for fake var decls. */ 3764 struct obstack fake_var_decl_obstack; 3765 3766 /* Build a fake VAR_DECL acting as referrer to a DECL_UID. */ 3767 3768 static tree 3769 build_fake_var_decl (tree type) 3770 { 3771 tree decl = (tree) XOBNEW (&fake_var_decl_obstack, struct tree_var_decl); 3772 memset (decl, 0, sizeof (struct tree_var_decl)); 3773 TREE_SET_CODE (decl, VAR_DECL); 3774 TREE_TYPE (decl) = type; 3775 DECL_UID (decl) = allocate_decl_uid (); 3776 SET_DECL_PT_UID (decl, -1); 3777 layout_decl (decl, 0); 3778 return decl; 3779 } 3780 3781 /* Create a new artificial heap variable with NAME. 3782 Return the created variable. */ 3783 3784 static varinfo_t 3785 make_heapvar (const char *name, bool add_id) 3786 { 3787 varinfo_t vi; 3788 tree heapvar; 3789 3790 heapvar = build_fake_var_decl (ptr_type_node); 3791 DECL_EXTERNAL (heapvar) = 1; 3792 3793 vi = new_var_info (heapvar, name, add_id); 3794 vi->is_artificial_var = true; 3795 vi->is_heap_var = true; 3796 vi->is_unknown_size_var = true; 3797 vi->offset = 0; 3798 vi->fullsize = ~0; 3799 vi->size = ~0; 3800 vi->is_full_var = true; 3801 insert_vi_for_tree (heapvar, vi); 3802 3803 return vi; 3804 } 3805 3806 /* Create a new artificial heap variable with NAME and make a 3807 constraint from it to LHS. Set flags according to a tag used 3808 for tracking restrict pointers. */ 3809 3810 static varinfo_t 3811 make_constraint_from_restrict (varinfo_t lhs, const char *name, bool add_id) 3812 { 3813 varinfo_t vi = make_heapvar (name, add_id); 3814 vi->is_restrict_var = 1; 3815 vi->is_global_var = 1; 3816 vi->may_have_pointers = 1; 3817 make_constraint_from (lhs, vi->id); 3818 return vi; 3819 } 3820 3821 /* Create a new artificial heap variable with NAME and make a 3822 constraint from it to LHS. Set flags according to a tag used 3823 for tracking restrict pointers and make the artificial heap 3824 point to global memory. */ 3825 3826 static varinfo_t 3827 make_constraint_from_global_restrict (varinfo_t lhs, const char *name, 3828 bool add_id) 3829 { 3830 varinfo_t vi = make_constraint_from_restrict (lhs, name, add_id); 3831 make_copy_constraint (vi, nonlocal_id); 3832 return vi; 3833 } 3834 3835 /* In IPA mode there are varinfos for different aspects of reach 3836 function designator. One for the points-to set of the return 3837 value, one for the variables that are clobbered by the function, 3838 one for its uses and one for each parameter (including a single 3839 glob for remaining variadic arguments). */ 3840 3841 enum { fi_clobbers = 1, fi_uses = 2, 3842 fi_static_chain = 3, fi_result = 4, fi_parm_base = 5 }; 3843 3844 /* Get a constraint for the requested part of a function designator FI 3845 when operating in IPA mode. */ 3846 3847 static struct constraint_expr 3848 get_function_part_constraint (varinfo_t fi, unsigned part) 3849 { 3850 struct constraint_expr c; 3851 3852 gcc_assert (in_ipa_mode); 3853 3854 if (fi->id == anything_id) 3855 { 3856 /* ??? We probably should have a ANYFN special variable. */ 3857 c.var = anything_id; 3858 c.offset = 0; 3859 c.type = SCALAR; 3860 } 3861 else if (TREE_CODE (fi->decl) == FUNCTION_DECL) 3862 { 3863 varinfo_t ai = first_vi_for_offset (fi, part); 3864 if (ai) 3865 c.var = ai->id; 3866 else 3867 c.var = anything_id; 3868 c.offset = 0; 3869 c.type = SCALAR; 3870 } 3871 else 3872 { 3873 c.var = fi->id; 3874 c.offset = part; 3875 c.type = DEREF; 3876 } 3877 3878 return c; 3879 } 3880 3881 /* For non-IPA mode, generate constraints necessary for a call on the 3882 RHS. */ 3883 3884 static void 3885 handle_rhs_call (gcall *stmt, vec<ce_s> *results) 3886 { 3887 struct constraint_expr rhsc; 3888 unsigned i; 3889 bool returns_uses = false; 3890 3891 for (i = 0; i < gimple_call_num_args (stmt); ++i) 3892 { 3893 tree arg = gimple_call_arg (stmt, i); 3894 int flags = gimple_call_arg_flags (stmt, i); 3895 3896 /* If the argument is not used we can ignore it. */ 3897 if (flags & EAF_UNUSED) 3898 continue; 3899 3900 /* As we compute ESCAPED context-insensitive we do not gain 3901 any precision with just EAF_NOCLOBBER but not EAF_NOESCAPE 3902 set. The argument would still get clobbered through the 3903 escape solution. */ 3904 if ((flags & EAF_NOCLOBBER) 3905 && (flags & EAF_NOESCAPE)) 3906 { 3907 varinfo_t uses = get_call_use_vi (stmt); 3908 varinfo_t tem = new_var_info (NULL_TREE, "callarg", true); 3909 make_constraint_to (tem->id, arg); 3910 make_any_offset_constraints (tem); 3911 if (!(flags & EAF_DIRECT)) 3912 make_transitive_closure_constraints (tem); 3913 make_copy_constraint (uses, tem->id); 3914 returns_uses = true; 3915 } 3916 else if (flags & EAF_NOESCAPE) 3917 { 3918 struct constraint_expr lhs, rhs; 3919 varinfo_t uses = get_call_use_vi (stmt); 3920 varinfo_t clobbers = get_call_clobber_vi (stmt); 3921 varinfo_t tem = new_var_info (NULL_TREE, "callarg", true); 3922 make_constraint_to (tem->id, arg); 3923 make_any_offset_constraints (tem); 3924 if (!(flags & EAF_DIRECT)) 3925 make_transitive_closure_constraints (tem); 3926 make_copy_constraint (uses, tem->id); 3927 make_copy_constraint (clobbers, tem->id); 3928 /* Add *tem = nonlocal, do not add *tem = callused as 3929 EAF_NOESCAPE parameters do not escape to other parameters 3930 and all other uses appear in NONLOCAL as well. */ 3931 lhs.type = DEREF; 3932 lhs.var = tem->id; 3933 lhs.offset = 0; 3934 rhs.type = SCALAR; 3935 rhs.var = nonlocal_id; 3936 rhs.offset = 0; 3937 process_constraint (new_constraint (lhs, rhs)); 3938 returns_uses = true; 3939 } 3940 else 3941 make_escape_constraint (arg); 3942 } 3943 3944 /* If we added to the calls uses solution make sure we account for 3945 pointers to it to be returned. */ 3946 if (returns_uses) 3947 { 3948 rhsc.var = get_call_use_vi (stmt)->id; 3949 rhsc.offset = UNKNOWN_OFFSET; 3950 rhsc.type = SCALAR; 3951 results->safe_push (rhsc); 3952 } 3953 3954 /* The static chain escapes as well. */ 3955 if (gimple_call_chain (stmt)) 3956 make_escape_constraint (gimple_call_chain (stmt)); 3957 3958 /* And if we applied NRV the address of the return slot escapes as well. */ 3959 if (gimple_call_return_slot_opt_p (stmt) 3960 && gimple_call_lhs (stmt) != NULL_TREE 3961 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt)))) 3962 { 3963 auto_vec<ce_s> tmpc; 3964 struct constraint_expr lhsc, *c; 3965 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc); 3966 lhsc.var = escaped_id; 3967 lhsc.offset = 0; 3968 lhsc.type = SCALAR; 3969 FOR_EACH_VEC_ELT (tmpc, i, c) 3970 process_constraint (new_constraint (lhsc, *c)); 3971 } 3972 3973 /* Regular functions return nonlocal memory. */ 3974 rhsc.var = nonlocal_id; 3975 rhsc.offset = 0; 3976 rhsc.type = SCALAR; 3977 results->safe_push (rhsc); 3978 } 3979 3980 /* For non-IPA mode, generate constraints necessary for a call 3981 that returns a pointer and assigns it to LHS. This simply makes 3982 the LHS point to global and escaped variables. */ 3983 3984 static void 3985 handle_lhs_call (gcall *stmt, tree lhs, int flags, vec<ce_s> rhsc, 3986 tree fndecl) 3987 { 3988 auto_vec<ce_s> lhsc; 3989 3990 get_constraint_for (lhs, &lhsc); 3991 /* If the store is to a global decl make sure to 3992 add proper escape constraints. */ 3993 lhs = get_base_address (lhs); 3994 if (lhs 3995 && DECL_P (lhs) 3996 && is_global_var (lhs)) 3997 { 3998 struct constraint_expr tmpc; 3999 tmpc.var = escaped_id; 4000 tmpc.offset = 0; 4001 tmpc.type = SCALAR; 4002 lhsc.safe_push (tmpc); 4003 } 4004 4005 /* If the call returns an argument unmodified override the rhs 4006 constraints. */ 4007 if (flags & ERF_RETURNS_ARG 4008 && (flags & ERF_RETURN_ARG_MASK) < gimple_call_num_args (stmt)) 4009 { 4010 tree arg; 4011 rhsc.create (0); 4012 arg = gimple_call_arg (stmt, flags & ERF_RETURN_ARG_MASK); 4013 get_constraint_for (arg, &rhsc); 4014 process_all_all_constraints (lhsc, rhsc); 4015 rhsc.release (); 4016 } 4017 else if (flags & ERF_NOALIAS) 4018 { 4019 varinfo_t vi; 4020 struct constraint_expr tmpc; 4021 rhsc.create (0); 4022 vi = make_heapvar ("HEAP", true); 4023 /* We are marking allocated storage local, we deal with it becoming 4024 global by escaping and setting of vars_contains_escaped_heap. */ 4025 DECL_EXTERNAL (vi->decl) = 0; 4026 vi->is_global_var = 0; 4027 /* If this is not a real malloc call assume the memory was 4028 initialized and thus may point to global memory. All 4029 builtin functions with the malloc attribute behave in a sane way. */ 4030 if (!fndecl 4031 || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL) 4032 make_constraint_from (vi, nonlocal_id); 4033 tmpc.var = vi->id; 4034 tmpc.offset = 0; 4035 tmpc.type = ADDRESSOF; 4036 rhsc.safe_push (tmpc); 4037 process_all_all_constraints (lhsc, rhsc); 4038 rhsc.release (); 4039 } 4040 else 4041 process_all_all_constraints (lhsc, rhsc); 4042 } 4043 4044 /* For non-IPA mode, generate constraints necessary for a call of a 4045 const function that returns a pointer in the statement STMT. */ 4046 4047 static void 4048 handle_const_call (gcall *stmt, vec<ce_s> *results) 4049 { 4050 struct constraint_expr rhsc; 4051 unsigned int k; 4052 bool need_uses = false; 4053 4054 /* Treat nested const functions the same as pure functions as far 4055 as the static chain is concerned. */ 4056 if (gimple_call_chain (stmt)) 4057 { 4058 varinfo_t uses = get_call_use_vi (stmt); 4059 make_constraint_to (uses->id, gimple_call_chain (stmt)); 4060 need_uses = true; 4061 } 4062 4063 /* And if we applied NRV the address of the return slot escapes as well. */ 4064 if (gimple_call_return_slot_opt_p (stmt) 4065 && gimple_call_lhs (stmt) != NULL_TREE 4066 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt)))) 4067 { 4068 varinfo_t uses = get_call_use_vi (stmt); 4069 auto_vec<ce_s> tmpc; 4070 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc); 4071 make_constraints_to (uses->id, tmpc); 4072 need_uses = true; 4073 } 4074 4075 if (need_uses) 4076 { 4077 varinfo_t uses = get_call_use_vi (stmt); 4078 make_any_offset_constraints (uses); 4079 make_transitive_closure_constraints (uses); 4080 rhsc.var = uses->id; 4081 rhsc.offset = 0; 4082 rhsc.type = SCALAR; 4083 results->safe_push (rhsc); 4084 } 4085 4086 /* May return offsetted arguments. */ 4087 varinfo_t tem = NULL; 4088 if (gimple_call_num_args (stmt) != 0) 4089 tem = new_var_info (NULL_TREE, "callarg", true); 4090 for (k = 0; k < gimple_call_num_args (stmt); ++k) 4091 { 4092 tree arg = gimple_call_arg (stmt, k); 4093 auto_vec<ce_s> argc; 4094 get_constraint_for_rhs (arg, &argc); 4095 make_constraints_to (tem->id, argc); 4096 } 4097 if (tem) 4098 { 4099 ce_s ce; 4100 ce.type = SCALAR; 4101 ce.var = tem->id; 4102 ce.offset = UNKNOWN_OFFSET; 4103 results->safe_push (ce); 4104 } 4105 4106 /* May return addresses of globals. */ 4107 rhsc.var = nonlocal_id; 4108 rhsc.offset = 0; 4109 rhsc.type = ADDRESSOF; 4110 results->safe_push (rhsc); 4111 } 4112 4113 /* For non-IPA mode, generate constraints necessary for a call to a 4114 pure function in statement STMT. */ 4115 4116 static void 4117 handle_pure_call (gcall *stmt, vec<ce_s> *results) 4118 { 4119 struct constraint_expr rhsc; 4120 unsigned i; 4121 varinfo_t uses = NULL; 4122 4123 /* Memory reached from pointer arguments is call-used. */ 4124 for (i = 0; i < gimple_call_num_args (stmt); ++i) 4125 { 4126 tree arg = gimple_call_arg (stmt, i); 4127 if (!uses) 4128 { 4129 uses = get_call_use_vi (stmt); 4130 make_any_offset_constraints (uses); 4131 make_transitive_closure_constraints (uses); 4132 } 4133 make_constraint_to (uses->id, arg); 4134 } 4135 4136 /* The static chain is used as well. */ 4137 if (gimple_call_chain (stmt)) 4138 { 4139 if (!uses) 4140 { 4141 uses = get_call_use_vi (stmt); 4142 make_any_offset_constraints (uses); 4143 make_transitive_closure_constraints (uses); 4144 } 4145 make_constraint_to (uses->id, gimple_call_chain (stmt)); 4146 } 4147 4148 /* And if we applied NRV the address of the return slot. */ 4149 if (gimple_call_return_slot_opt_p (stmt) 4150 && gimple_call_lhs (stmt) != NULL_TREE 4151 && TREE_ADDRESSABLE (TREE_TYPE (gimple_call_lhs (stmt)))) 4152 { 4153 if (!uses) 4154 { 4155 uses = get_call_use_vi (stmt); 4156 make_any_offset_constraints (uses); 4157 make_transitive_closure_constraints (uses); 4158 } 4159 auto_vec<ce_s> tmpc; 4160 get_constraint_for_address_of (gimple_call_lhs (stmt), &tmpc); 4161 make_constraints_to (uses->id, tmpc); 4162 } 4163 4164 /* Pure functions may return call-used and nonlocal memory. */ 4165 if (uses) 4166 { 4167 rhsc.var = uses->id; 4168 rhsc.offset = 0; 4169 rhsc.type = SCALAR; 4170 results->safe_push (rhsc); 4171 } 4172 rhsc.var = nonlocal_id; 4173 rhsc.offset = 0; 4174 rhsc.type = SCALAR; 4175 results->safe_push (rhsc); 4176 } 4177 4178 4179 /* Return the varinfo for the callee of CALL. */ 4180 4181 static varinfo_t 4182 get_fi_for_callee (gcall *call) 4183 { 4184 tree decl, fn = gimple_call_fn (call); 4185 4186 if (fn && TREE_CODE (fn) == OBJ_TYPE_REF) 4187 fn = OBJ_TYPE_REF_EXPR (fn); 4188 4189 /* If we can directly resolve the function being called, do so. 4190 Otherwise, it must be some sort of indirect expression that 4191 we should still be able to handle. */ 4192 decl = gimple_call_addr_fndecl (fn); 4193 if (decl) 4194 return get_vi_for_tree (decl); 4195 4196 /* If the function is anything other than a SSA name pointer we have no 4197 clue and should be getting ANYFN (well, ANYTHING for now). */ 4198 if (!fn || TREE_CODE (fn) != SSA_NAME) 4199 return get_varinfo (anything_id); 4200 4201 if (SSA_NAME_IS_DEFAULT_DEF (fn) 4202 && (TREE_CODE (SSA_NAME_VAR (fn)) == PARM_DECL 4203 || TREE_CODE (SSA_NAME_VAR (fn)) == RESULT_DECL)) 4204 fn = SSA_NAME_VAR (fn); 4205 4206 return get_vi_for_tree (fn); 4207 } 4208 4209 /* Create constraints for assigning call argument ARG to the incoming parameter 4210 INDEX of function FI. */ 4211 4212 static void 4213 find_func_aliases_for_call_arg (varinfo_t fi, unsigned index, tree arg) 4214 { 4215 struct constraint_expr lhs; 4216 lhs = get_function_part_constraint (fi, fi_parm_base + index); 4217 4218 auto_vec<ce_s, 2> rhsc; 4219 get_constraint_for_rhs (arg, &rhsc); 4220 4221 unsigned j; 4222 struct constraint_expr *rhsp; 4223 FOR_EACH_VEC_ELT (rhsc, j, rhsp) 4224 process_constraint (new_constraint (lhs, *rhsp)); 4225 } 4226 4227 /* Return true if FNDECL may be part of another lto partition. */ 4228 4229 static bool 4230 fndecl_maybe_in_other_partition (tree fndecl) 4231 { 4232 cgraph_node *fn_node = cgraph_node::get (fndecl); 4233 if (fn_node == NULL) 4234 return true; 4235 4236 return fn_node->in_other_partition; 4237 } 4238 4239 /* Create constraints for the builtin call T. Return true if the call 4240 was handled, otherwise false. */ 4241 4242 static bool 4243 find_func_aliases_for_builtin_call (struct function *fn, gcall *t) 4244 { 4245 tree fndecl = gimple_call_fndecl (t); 4246 auto_vec<ce_s, 2> lhsc; 4247 auto_vec<ce_s, 4> rhsc; 4248 varinfo_t fi; 4249 4250 if (gimple_call_builtin_p (t, BUILT_IN_NORMAL)) 4251 /* ??? All builtins that are handled here need to be handled 4252 in the alias-oracle query functions explicitly! */ 4253 switch (DECL_FUNCTION_CODE (fndecl)) 4254 { 4255 /* All the following functions return a pointer to the same object 4256 as their first argument points to. The functions do not add 4257 to the ESCAPED solution. The functions make the first argument 4258 pointed to memory point to what the second argument pointed to 4259 memory points to. */ 4260 case BUILT_IN_STRCPY: 4261 case BUILT_IN_STRNCPY: 4262 case BUILT_IN_BCOPY: 4263 case BUILT_IN_MEMCPY: 4264 case BUILT_IN_MEMMOVE: 4265 case BUILT_IN_MEMPCPY: 4266 case BUILT_IN_STPCPY: 4267 case BUILT_IN_STPNCPY: 4268 case BUILT_IN_STRCAT: 4269 case BUILT_IN_STRNCAT: 4270 case BUILT_IN_STRCPY_CHK: 4271 case BUILT_IN_STRNCPY_CHK: 4272 case BUILT_IN_MEMCPY_CHK: 4273 case BUILT_IN_MEMMOVE_CHK: 4274 case BUILT_IN_MEMPCPY_CHK: 4275 case BUILT_IN_STPCPY_CHK: 4276 case BUILT_IN_STPNCPY_CHK: 4277 case BUILT_IN_STRCAT_CHK: 4278 case BUILT_IN_STRNCAT_CHK: 4279 case BUILT_IN_TM_MEMCPY: 4280 case BUILT_IN_TM_MEMMOVE: 4281 { 4282 tree res = gimple_call_lhs (t); 4283 tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl) 4284 == BUILT_IN_BCOPY ? 1 : 0)); 4285 tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (fndecl) 4286 == BUILT_IN_BCOPY ? 0 : 1)); 4287 if (res != NULL_TREE) 4288 { 4289 get_constraint_for (res, &lhsc); 4290 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY 4291 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY 4292 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY 4293 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_MEMPCPY_CHK 4294 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPCPY_CHK 4295 || DECL_FUNCTION_CODE (fndecl) == BUILT_IN_STPNCPY_CHK) 4296 get_constraint_for_ptr_offset (dest, NULL_TREE, &rhsc); 4297 else 4298 get_constraint_for (dest, &rhsc); 4299 process_all_all_constraints (lhsc, rhsc); 4300 lhsc.truncate (0); 4301 rhsc.truncate (0); 4302 } 4303 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc); 4304 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc); 4305 do_deref (&lhsc); 4306 do_deref (&rhsc); 4307 process_all_all_constraints (lhsc, rhsc); 4308 return true; 4309 } 4310 case BUILT_IN_MEMSET: 4311 case BUILT_IN_MEMSET_CHK: 4312 case BUILT_IN_TM_MEMSET: 4313 { 4314 tree res = gimple_call_lhs (t); 4315 tree dest = gimple_call_arg (t, 0); 4316 unsigned i; 4317 ce_s *lhsp; 4318 struct constraint_expr ac; 4319 if (res != NULL_TREE) 4320 { 4321 get_constraint_for (res, &lhsc); 4322 get_constraint_for (dest, &rhsc); 4323 process_all_all_constraints (lhsc, rhsc); 4324 lhsc.truncate (0); 4325 } 4326 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc); 4327 do_deref (&lhsc); 4328 if (flag_delete_null_pointer_checks 4329 && integer_zerop (gimple_call_arg (t, 1))) 4330 { 4331 ac.type = ADDRESSOF; 4332 ac.var = nothing_id; 4333 } 4334 else 4335 { 4336 ac.type = SCALAR; 4337 ac.var = integer_id; 4338 } 4339 ac.offset = 0; 4340 FOR_EACH_VEC_ELT (lhsc, i, lhsp) 4341 process_constraint (new_constraint (*lhsp, ac)); 4342 return true; 4343 } 4344 case BUILT_IN_POSIX_MEMALIGN: 4345 { 4346 tree ptrptr = gimple_call_arg (t, 0); 4347 get_constraint_for (ptrptr, &lhsc); 4348 do_deref (&lhsc); 4349 varinfo_t vi = make_heapvar ("HEAP", true); 4350 /* We are marking allocated storage local, we deal with it becoming 4351 global by escaping and setting of vars_contains_escaped_heap. */ 4352 DECL_EXTERNAL (vi->decl) = 0; 4353 vi->is_global_var = 0; 4354 struct constraint_expr tmpc; 4355 tmpc.var = vi->id; 4356 tmpc.offset = 0; 4357 tmpc.type = ADDRESSOF; 4358 rhsc.safe_push (tmpc); 4359 process_all_all_constraints (lhsc, rhsc); 4360 return true; 4361 } 4362 case BUILT_IN_ASSUME_ALIGNED: 4363 { 4364 tree res = gimple_call_lhs (t); 4365 tree dest = gimple_call_arg (t, 0); 4366 if (res != NULL_TREE) 4367 { 4368 get_constraint_for (res, &lhsc); 4369 get_constraint_for (dest, &rhsc); 4370 process_all_all_constraints (lhsc, rhsc); 4371 } 4372 return true; 4373 } 4374 /* All the following functions do not return pointers, do not 4375 modify the points-to sets of memory reachable from their 4376 arguments and do not add to the ESCAPED solution. */ 4377 case BUILT_IN_SINCOS: 4378 case BUILT_IN_SINCOSF: 4379 case BUILT_IN_SINCOSL: 4380 case BUILT_IN_FREXP: 4381 case BUILT_IN_FREXPF: 4382 case BUILT_IN_FREXPL: 4383 case BUILT_IN_GAMMA_R: 4384 case BUILT_IN_GAMMAF_R: 4385 case BUILT_IN_GAMMAL_R: 4386 case BUILT_IN_LGAMMA_R: 4387 case BUILT_IN_LGAMMAF_R: 4388 case BUILT_IN_LGAMMAL_R: 4389 case BUILT_IN_MODF: 4390 case BUILT_IN_MODFF: 4391 case BUILT_IN_MODFL: 4392 case BUILT_IN_REMQUO: 4393 case BUILT_IN_REMQUOF: 4394 case BUILT_IN_REMQUOL: 4395 case BUILT_IN_FREE: 4396 return true; 4397 case BUILT_IN_STRDUP: 4398 case BUILT_IN_STRNDUP: 4399 case BUILT_IN_REALLOC: 4400 if (gimple_call_lhs (t)) 4401 { 4402 handle_lhs_call (t, gimple_call_lhs (t), 4403 gimple_call_return_flags (t) | ERF_NOALIAS, 4404 vNULL, fndecl); 4405 get_constraint_for_ptr_offset (gimple_call_lhs (t), 4406 NULL_TREE, &lhsc); 4407 get_constraint_for_ptr_offset (gimple_call_arg (t, 0), 4408 NULL_TREE, &rhsc); 4409 do_deref (&lhsc); 4410 do_deref (&rhsc); 4411 process_all_all_constraints (lhsc, rhsc); 4412 lhsc.truncate (0); 4413 rhsc.truncate (0); 4414 /* For realloc the resulting pointer can be equal to the 4415 argument as well. But only doing this wouldn't be 4416 correct because with ptr == 0 realloc behaves like malloc. */ 4417 if (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_REALLOC) 4418 { 4419 get_constraint_for (gimple_call_lhs (t), &lhsc); 4420 get_constraint_for (gimple_call_arg (t, 0), &rhsc); 4421 process_all_all_constraints (lhsc, rhsc); 4422 } 4423 return true; 4424 } 4425 break; 4426 /* String / character search functions return a pointer into the 4427 source string or NULL. */ 4428 case BUILT_IN_INDEX: 4429 case BUILT_IN_STRCHR: 4430 case BUILT_IN_STRRCHR: 4431 case BUILT_IN_MEMCHR: 4432 case BUILT_IN_STRSTR: 4433 case BUILT_IN_STRPBRK: 4434 if (gimple_call_lhs (t)) 4435 { 4436 tree src = gimple_call_arg (t, 0); 4437 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc); 4438 constraint_expr nul; 4439 nul.var = nothing_id; 4440 nul.offset = 0; 4441 nul.type = ADDRESSOF; 4442 rhsc.safe_push (nul); 4443 get_constraint_for (gimple_call_lhs (t), &lhsc); 4444 process_all_all_constraints (lhsc, rhsc); 4445 } 4446 return true; 4447 /* Trampolines are special - they set up passing the static 4448 frame. */ 4449 case BUILT_IN_INIT_TRAMPOLINE: 4450 { 4451 tree tramp = gimple_call_arg (t, 0); 4452 tree nfunc = gimple_call_arg (t, 1); 4453 tree frame = gimple_call_arg (t, 2); 4454 unsigned i; 4455 struct constraint_expr lhs, *rhsp; 4456 if (in_ipa_mode) 4457 { 4458 varinfo_t nfi = NULL; 4459 gcc_assert (TREE_CODE (nfunc) == ADDR_EXPR); 4460 nfi = lookup_vi_for_tree (TREE_OPERAND (nfunc, 0)); 4461 if (nfi) 4462 { 4463 lhs = get_function_part_constraint (nfi, fi_static_chain); 4464 get_constraint_for (frame, &rhsc); 4465 FOR_EACH_VEC_ELT (rhsc, i, rhsp) 4466 process_constraint (new_constraint (lhs, *rhsp)); 4467 rhsc.truncate (0); 4468 4469 /* Make the frame point to the function for 4470 the trampoline adjustment call. */ 4471 get_constraint_for (tramp, &lhsc); 4472 do_deref (&lhsc); 4473 get_constraint_for (nfunc, &rhsc); 4474 process_all_all_constraints (lhsc, rhsc); 4475 4476 return true; 4477 } 4478 } 4479 /* Else fallthru to generic handling which will let 4480 the frame escape. */ 4481 break; 4482 } 4483 case BUILT_IN_ADJUST_TRAMPOLINE: 4484 { 4485 tree tramp = gimple_call_arg (t, 0); 4486 tree res = gimple_call_lhs (t); 4487 if (in_ipa_mode && res) 4488 { 4489 get_constraint_for (res, &lhsc); 4490 get_constraint_for (tramp, &rhsc); 4491 do_deref (&rhsc); 4492 process_all_all_constraints (lhsc, rhsc); 4493 } 4494 return true; 4495 } 4496 CASE_BUILT_IN_TM_STORE (1): 4497 CASE_BUILT_IN_TM_STORE (2): 4498 CASE_BUILT_IN_TM_STORE (4): 4499 CASE_BUILT_IN_TM_STORE (8): 4500 CASE_BUILT_IN_TM_STORE (FLOAT): 4501 CASE_BUILT_IN_TM_STORE (DOUBLE): 4502 CASE_BUILT_IN_TM_STORE (LDOUBLE): 4503 CASE_BUILT_IN_TM_STORE (M64): 4504 CASE_BUILT_IN_TM_STORE (M128): 4505 CASE_BUILT_IN_TM_STORE (M256): 4506 { 4507 tree addr = gimple_call_arg (t, 0); 4508 tree src = gimple_call_arg (t, 1); 4509 4510 get_constraint_for (addr, &lhsc); 4511 do_deref (&lhsc); 4512 get_constraint_for (src, &rhsc); 4513 process_all_all_constraints (lhsc, rhsc); 4514 return true; 4515 } 4516 CASE_BUILT_IN_TM_LOAD (1): 4517 CASE_BUILT_IN_TM_LOAD (2): 4518 CASE_BUILT_IN_TM_LOAD (4): 4519 CASE_BUILT_IN_TM_LOAD (8): 4520 CASE_BUILT_IN_TM_LOAD (FLOAT): 4521 CASE_BUILT_IN_TM_LOAD (DOUBLE): 4522 CASE_BUILT_IN_TM_LOAD (LDOUBLE): 4523 CASE_BUILT_IN_TM_LOAD (M64): 4524 CASE_BUILT_IN_TM_LOAD (M128): 4525 CASE_BUILT_IN_TM_LOAD (M256): 4526 { 4527 tree dest = gimple_call_lhs (t); 4528 tree addr = gimple_call_arg (t, 0); 4529 4530 get_constraint_for (dest, &lhsc); 4531 get_constraint_for (addr, &rhsc); 4532 do_deref (&rhsc); 4533 process_all_all_constraints (lhsc, rhsc); 4534 return true; 4535 } 4536 /* Variadic argument handling needs to be handled in IPA 4537 mode as well. */ 4538 case BUILT_IN_VA_START: 4539 { 4540 tree valist = gimple_call_arg (t, 0); 4541 struct constraint_expr rhs, *lhsp; 4542 unsigned i; 4543 get_constraint_for (valist, &lhsc); 4544 do_deref (&lhsc); 4545 /* The va_list gets access to pointers in variadic 4546 arguments. Which we know in the case of IPA analysis 4547 and otherwise are just all nonlocal variables. */ 4548 if (in_ipa_mode) 4549 { 4550 fi = lookup_vi_for_tree (fn->decl); 4551 rhs = get_function_part_constraint (fi, ~0); 4552 rhs.type = ADDRESSOF; 4553 } 4554 else 4555 { 4556 rhs.var = nonlocal_id; 4557 rhs.type = ADDRESSOF; 4558 rhs.offset = 0; 4559 } 4560 FOR_EACH_VEC_ELT (lhsc, i, lhsp) 4561 process_constraint (new_constraint (*lhsp, rhs)); 4562 /* va_list is clobbered. */ 4563 make_constraint_to (get_call_clobber_vi (t)->id, valist); 4564 return true; 4565 } 4566 /* va_end doesn't have any effect that matters. */ 4567 case BUILT_IN_VA_END: 4568 return true; 4569 /* Alternate return. Simply give up for now. */ 4570 case BUILT_IN_RETURN: 4571 { 4572 fi = NULL; 4573 if (!in_ipa_mode 4574 || !(fi = get_vi_for_tree (fn->decl))) 4575 make_constraint_from (get_varinfo (escaped_id), anything_id); 4576 else if (in_ipa_mode 4577 && fi != NULL) 4578 { 4579 struct constraint_expr lhs, rhs; 4580 lhs = get_function_part_constraint (fi, fi_result); 4581 rhs.var = anything_id; 4582 rhs.offset = 0; 4583 rhs.type = SCALAR; 4584 process_constraint (new_constraint (lhs, rhs)); 4585 } 4586 return true; 4587 } 4588 case BUILT_IN_GOMP_PARALLEL: 4589 case BUILT_IN_GOACC_PARALLEL: 4590 { 4591 if (in_ipa_mode) 4592 { 4593 unsigned int fnpos, argpos; 4594 switch (DECL_FUNCTION_CODE (fndecl)) 4595 { 4596 case BUILT_IN_GOMP_PARALLEL: 4597 /* __builtin_GOMP_parallel (fn, data, num_threads, flags). */ 4598 fnpos = 0; 4599 argpos = 1; 4600 break; 4601 case BUILT_IN_GOACC_PARALLEL: 4602 /* __builtin_GOACC_parallel (device, fn, mapnum, hostaddrs, 4603 sizes, kinds, ...). */ 4604 fnpos = 1; 4605 argpos = 3; 4606 break; 4607 default: 4608 gcc_unreachable (); 4609 } 4610 4611 tree fnarg = gimple_call_arg (t, fnpos); 4612 gcc_assert (TREE_CODE (fnarg) == ADDR_EXPR); 4613 tree fndecl = TREE_OPERAND (fnarg, 0); 4614 if (fndecl_maybe_in_other_partition (fndecl)) 4615 /* Fallthru to general call handling. */ 4616 break; 4617 4618 tree arg = gimple_call_arg (t, argpos); 4619 4620 varinfo_t fi = get_vi_for_tree (fndecl); 4621 find_func_aliases_for_call_arg (fi, 0, arg); 4622 return true; 4623 } 4624 /* Else fallthru to generic call handling. */ 4625 break; 4626 } 4627 /* printf-style functions may have hooks to set pointers to 4628 point to somewhere into the generated string. Leave them 4629 for a later exercise... */ 4630 default: 4631 /* Fallthru to general call handling. */; 4632 } 4633 4634 return false; 4635 } 4636 4637 /* Create constraints for the call T. */ 4638 4639 static void 4640 find_func_aliases_for_call (struct function *fn, gcall *t) 4641 { 4642 tree fndecl = gimple_call_fndecl (t); 4643 varinfo_t fi; 4644 4645 if (fndecl != NULL_TREE 4646 && DECL_BUILT_IN (fndecl) 4647 && find_func_aliases_for_builtin_call (fn, t)) 4648 return; 4649 4650 fi = get_fi_for_callee (t); 4651 if (!in_ipa_mode 4652 || (fndecl && !fi->is_fn_info)) 4653 { 4654 auto_vec<ce_s, 16> rhsc; 4655 int flags = gimple_call_flags (t); 4656 4657 /* Const functions can return their arguments and addresses 4658 of global memory but not of escaped memory. */ 4659 if (flags & (ECF_CONST|ECF_NOVOPS)) 4660 { 4661 if (gimple_call_lhs (t)) 4662 handle_const_call (t, &rhsc); 4663 } 4664 /* Pure functions can return addresses in and of memory 4665 reachable from their arguments, but they are not an escape 4666 point for reachable memory of their arguments. */ 4667 else if (flags & (ECF_PURE|ECF_LOOPING_CONST_OR_PURE)) 4668 handle_pure_call (t, &rhsc); 4669 else 4670 handle_rhs_call (t, &rhsc); 4671 if (gimple_call_lhs (t)) 4672 handle_lhs_call (t, gimple_call_lhs (t), 4673 gimple_call_return_flags (t), rhsc, fndecl); 4674 } 4675 else 4676 { 4677 auto_vec<ce_s, 2> rhsc; 4678 tree lhsop; 4679 unsigned j; 4680 4681 /* Assign all the passed arguments to the appropriate incoming 4682 parameters of the function. */ 4683 for (j = 0; j < gimple_call_num_args (t); j++) 4684 { 4685 tree arg = gimple_call_arg (t, j); 4686 find_func_aliases_for_call_arg (fi, j, arg); 4687 } 4688 4689 /* If we are returning a value, assign it to the result. */ 4690 lhsop = gimple_call_lhs (t); 4691 if (lhsop) 4692 { 4693 auto_vec<ce_s, 2> lhsc; 4694 struct constraint_expr rhs; 4695 struct constraint_expr *lhsp; 4696 bool aggr_p = aggregate_value_p (lhsop, gimple_call_fntype (t)); 4697 4698 get_constraint_for (lhsop, &lhsc); 4699 rhs = get_function_part_constraint (fi, fi_result); 4700 if (aggr_p) 4701 { 4702 auto_vec<ce_s, 2> tem; 4703 tem.quick_push (rhs); 4704 do_deref (&tem); 4705 gcc_checking_assert (tem.length () == 1); 4706 rhs = tem[0]; 4707 } 4708 FOR_EACH_VEC_ELT (lhsc, j, lhsp) 4709 process_constraint (new_constraint (*lhsp, rhs)); 4710 4711 /* If we pass the result decl by reference, honor that. */ 4712 if (aggr_p) 4713 { 4714 struct constraint_expr lhs; 4715 struct constraint_expr *rhsp; 4716 4717 get_constraint_for_address_of (lhsop, &rhsc); 4718 lhs = get_function_part_constraint (fi, fi_result); 4719 FOR_EACH_VEC_ELT (rhsc, j, rhsp) 4720 process_constraint (new_constraint (lhs, *rhsp)); 4721 rhsc.truncate (0); 4722 } 4723 } 4724 4725 /* If we use a static chain, pass it along. */ 4726 if (gimple_call_chain (t)) 4727 { 4728 struct constraint_expr lhs; 4729 struct constraint_expr *rhsp; 4730 4731 get_constraint_for (gimple_call_chain (t), &rhsc); 4732 lhs = get_function_part_constraint (fi, fi_static_chain); 4733 FOR_EACH_VEC_ELT (rhsc, j, rhsp) 4734 process_constraint (new_constraint (lhs, *rhsp)); 4735 } 4736 } 4737 } 4738 4739 /* Walk statement T setting up aliasing constraints according to the 4740 references found in T. This function is the main part of the 4741 constraint builder. AI points to auxiliary alias information used 4742 when building alias sets and computing alias grouping heuristics. */ 4743 4744 static void 4745 find_func_aliases (struct function *fn, gimple *origt) 4746 { 4747 gimple *t = origt; 4748 auto_vec<ce_s, 16> lhsc; 4749 auto_vec<ce_s, 16> rhsc; 4750 struct constraint_expr *c; 4751 varinfo_t fi; 4752 4753 /* Now build constraints expressions. */ 4754 if (gimple_code (t) == GIMPLE_PHI) 4755 { 4756 size_t i; 4757 unsigned int j; 4758 4759 /* For a phi node, assign all the arguments to 4760 the result. */ 4761 get_constraint_for (gimple_phi_result (t), &lhsc); 4762 for (i = 0; i < gimple_phi_num_args (t); i++) 4763 { 4764 tree strippedrhs = PHI_ARG_DEF (t, i); 4765 4766 STRIP_NOPS (strippedrhs); 4767 get_constraint_for_rhs (gimple_phi_arg_def (t, i), &rhsc); 4768 4769 FOR_EACH_VEC_ELT (lhsc, j, c) 4770 { 4771 struct constraint_expr *c2; 4772 while (rhsc.length () > 0) 4773 { 4774 c2 = &rhsc.last (); 4775 process_constraint (new_constraint (*c, *c2)); 4776 rhsc.pop (); 4777 } 4778 } 4779 } 4780 } 4781 /* In IPA mode, we need to generate constraints to pass call 4782 arguments through their calls. There are two cases, 4783 either a GIMPLE_CALL returning a value, or just a plain 4784 GIMPLE_CALL when we are not. 4785 4786 In non-ipa mode, we need to generate constraints for each 4787 pointer passed by address. */ 4788 else if (is_gimple_call (t)) 4789 find_func_aliases_for_call (fn, as_a <gcall *> (t)); 4790 4791 /* Otherwise, just a regular assignment statement. Only care about 4792 operations with pointer result, others are dealt with as escape 4793 points if they have pointer operands. */ 4794 else if (is_gimple_assign (t)) 4795 { 4796 /* Otherwise, just a regular assignment statement. */ 4797 tree lhsop = gimple_assign_lhs (t); 4798 tree rhsop = (gimple_num_ops (t) == 2) ? gimple_assign_rhs1 (t) : NULL; 4799 4800 if (rhsop && TREE_CLOBBER_P (rhsop)) 4801 /* Ignore clobbers, they don't actually store anything into 4802 the LHS. */ 4803 ; 4804 else if (rhsop && AGGREGATE_TYPE_P (TREE_TYPE (lhsop))) 4805 do_structure_copy (lhsop, rhsop); 4806 else 4807 { 4808 enum tree_code code = gimple_assign_rhs_code (t); 4809 4810 get_constraint_for (lhsop, &lhsc); 4811 4812 if (code == POINTER_PLUS_EXPR) 4813 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t), 4814 gimple_assign_rhs2 (t), &rhsc); 4815 else if (code == BIT_AND_EXPR 4816 && TREE_CODE (gimple_assign_rhs2 (t)) == INTEGER_CST) 4817 { 4818 /* Aligning a pointer via a BIT_AND_EXPR is offsetting 4819 the pointer. Handle it by offsetting it by UNKNOWN. */ 4820 get_constraint_for_ptr_offset (gimple_assign_rhs1 (t), 4821 NULL_TREE, &rhsc); 4822 } 4823 else if ((CONVERT_EXPR_CODE_P (code) 4824 && !(POINTER_TYPE_P (gimple_expr_type (t)) 4825 && !POINTER_TYPE_P (TREE_TYPE (rhsop)))) 4826 || gimple_assign_single_p (t)) 4827 get_constraint_for_rhs (rhsop, &rhsc); 4828 else if (code == COND_EXPR) 4829 { 4830 /* The result is a merge of both COND_EXPR arms. */ 4831 auto_vec<ce_s, 2> tmp; 4832 struct constraint_expr *rhsp; 4833 unsigned i; 4834 get_constraint_for_rhs (gimple_assign_rhs2 (t), &rhsc); 4835 get_constraint_for_rhs (gimple_assign_rhs3 (t), &tmp); 4836 FOR_EACH_VEC_ELT (tmp, i, rhsp) 4837 rhsc.safe_push (*rhsp); 4838 } 4839 else if (truth_value_p (code)) 4840 /* Truth value results are not pointer (parts). Or at least 4841 very unreasonable obfuscation of a part. */ 4842 ; 4843 else 4844 { 4845 /* All other operations are merges. */ 4846 auto_vec<ce_s, 4> tmp; 4847 struct constraint_expr *rhsp; 4848 unsigned i, j; 4849 get_constraint_for_rhs (gimple_assign_rhs1 (t), &rhsc); 4850 for (i = 2; i < gimple_num_ops (t); ++i) 4851 { 4852 get_constraint_for_rhs (gimple_op (t, i), &tmp); 4853 FOR_EACH_VEC_ELT (tmp, j, rhsp) 4854 rhsc.safe_push (*rhsp); 4855 tmp.truncate (0); 4856 } 4857 } 4858 process_all_all_constraints (lhsc, rhsc); 4859 } 4860 /* If there is a store to a global variable the rhs escapes. */ 4861 if ((lhsop = get_base_address (lhsop)) != NULL_TREE 4862 && DECL_P (lhsop)) 4863 { 4864 varinfo_t vi = get_vi_for_tree (lhsop); 4865 if ((! in_ipa_mode && vi->is_global_var) 4866 || vi->is_ipa_escape_point) 4867 make_escape_constraint (rhsop); 4868 } 4869 } 4870 /* Handle escapes through return. */ 4871 else if (gimple_code (t) == GIMPLE_RETURN 4872 && gimple_return_retval (as_a <greturn *> (t)) != NULL_TREE) 4873 { 4874 greturn *return_stmt = as_a <greturn *> (t); 4875 fi = NULL; 4876 if (!in_ipa_mode 4877 || !(fi = get_vi_for_tree (fn->decl))) 4878 make_escape_constraint (gimple_return_retval (return_stmt)); 4879 else if (in_ipa_mode) 4880 { 4881 struct constraint_expr lhs ; 4882 struct constraint_expr *rhsp; 4883 unsigned i; 4884 4885 lhs = get_function_part_constraint (fi, fi_result); 4886 get_constraint_for_rhs (gimple_return_retval (return_stmt), &rhsc); 4887 FOR_EACH_VEC_ELT (rhsc, i, rhsp) 4888 process_constraint (new_constraint (lhs, *rhsp)); 4889 } 4890 } 4891 /* Handle asms conservatively by adding escape constraints to everything. */ 4892 else if (gasm *asm_stmt = dyn_cast <gasm *> (t)) 4893 { 4894 unsigned i, noutputs; 4895 const char **oconstraints; 4896 const char *constraint; 4897 bool allows_mem, allows_reg, is_inout; 4898 4899 noutputs = gimple_asm_noutputs (asm_stmt); 4900 oconstraints = XALLOCAVEC (const char *, noutputs); 4901 4902 for (i = 0; i < noutputs; ++i) 4903 { 4904 tree link = gimple_asm_output_op (asm_stmt, i); 4905 tree op = TREE_VALUE (link); 4906 4907 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); 4908 oconstraints[i] = constraint; 4909 parse_output_constraint (&constraint, i, 0, 0, &allows_mem, 4910 &allows_reg, &is_inout); 4911 4912 /* A memory constraint makes the address of the operand escape. */ 4913 if (!allows_reg && allows_mem) 4914 make_escape_constraint (build_fold_addr_expr (op)); 4915 4916 /* The asm may read global memory, so outputs may point to 4917 any global memory. */ 4918 if (op) 4919 { 4920 auto_vec<ce_s, 2> lhsc; 4921 struct constraint_expr rhsc, *lhsp; 4922 unsigned j; 4923 get_constraint_for (op, &lhsc); 4924 rhsc.var = nonlocal_id; 4925 rhsc.offset = 0; 4926 rhsc.type = SCALAR; 4927 FOR_EACH_VEC_ELT (lhsc, j, lhsp) 4928 process_constraint (new_constraint (*lhsp, rhsc)); 4929 } 4930 } 4931 for (i = 0; i < gimple_asm_ninputs (asm_stmt); ++i) 4932 { 4933 tree link = gimple_asm_input_op (asm_stmt, i); 4934 tree op = TREE_VALUE (link); 4935 4936 constraint = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); 4937 4938 parse_input_constraint (&constraint, 0, 0, noutputs, 0, oconstraints, 4939 &allows_mem, &allows_reg); 4940 4941 /* A memory constraint makes the address of the operand escape. */ 4942 if (!allows_reg && allows_mem) 4943 make_escape_constraint (build_fold_addr_expr (op)); 4944 /* Strictly we'd only need the constraint to ESCAPED if 4945 the asm clobbers memory, otherwise using something 4946 along the lines of per-call clobbers/uses would be enough. */ 4947 else if (op) 4948 make_escape_constraint (op); 4949 } 4950 } 4951 } 4952 4953 4954 /* Create a constraint adding to the clobber set of FI the memory 4955 pointed to by PTR. */ 4956 4957 static void 4958 process_ipa_clobber (varinfo_t fi, tree ptr) 4959 { 4960 vec<ce_s> ptrc = vNULL; 4961 struct constraint_expr *c, lhs; 4962 unsigned i; 4963 get_constraint_for_rhs (ptr, &ptrc); 4964 lhs = get_function_part_constraint (fi, fi_clobbers); 4965 FOR_EACH_VEC_ELT (ptrc, i, c) 4966 process_constraint (new_constraint (lhs, *c)); 4967 ptrc.release (); 4968 } 4969 4970 /* Walk statement T setting up clobber and use constraints according to the 4971 references found in T. This function is a main part of the 4972 IPA constraint builder. */ 4973 4974 static void 4975 find_func_clobbers (struct function *fn, gimple *origt) 4976 { 4977 gimple *t = origt; 4978 auto_vec<ce_s, 16> lhsc; 4979 auto_vec<ce_s, 16> rhsc; 4980 varinfo_t fi; 4981 4982 /* Add constraints for clobbered/used in IPA mode. 4983 We are not interested in what automatic variables are clobbered 4984 or used as we only use the information in the caller to which 4985 they do not escape. */ 4986 gcc_assert (in_ipa_mode); 4987 4988 /* If the stmt refers to memory in any way it better had a VUSE. */ 4989 if (gimple_vuse (t) == NULL_TREE) 4990 return; 4991 4992 /* We'd better have function information for the current function. */ 4993 fi = lookup_vi_for_tree (fn->decl); 4994 gcc_assert (fi != NULL); 4995 4996 /* Account for stores in assignments and calls. */ 4997 if (gimple_vdef (t) != NULL_TREE 4998 && gimple_has_lhs (t)) 4999 { 5000 tree lhs = gimple_get_lhs (t); 5001 tree tem = lhs; 5002 while (handled_component_p (tem)) 5003 tem = TREE_OPERAND (tem, 0); 5004 if ((DECL_P (tem) 5005 && !auto_var_in_fn_p (tem, fn->decl)) 5006 || INDIRECT_REF_P (tem) 5007 || (TREE_CODE (tem) == MEM_REF 5008 && !(TREE_CODE (TREE_OPERAND (tem, 0)) == ADDR_EXPR 5009 && auto_var_in_fn_p 5010 (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), fn->decl)))) 5011 { 5012 struct constraint_expr lhsc, *rhsp; 5013 unsigned i; 5014 lhsc = get_function_part_constraint (fi, fi_clobbers); 5015 get_constraint_for_address_of (lhs, &rhsc); 5016 FOR_EACH_VEC_ELT (rhsc, i, rhsp) 5017 process_constraint (new_constraint (lhsc, *rhsp)); 5018 rhsc.truncate (0); 5019 } 5020 } 5021 5022 /* Account for uses in assigments and returns. */ 5023 if (gimple_assign_single_p (t) 5024 || (gimple_code (t) == GIMPLE_RETURN 5025 && gimple_return_retval (as_a <greturn *> (t)) != NULL_TREE)) 5026 { 5027 tree rhs = (gimple_assign_single_p (t) 5028 ? gimple_assign_rhs1 (t) 5029 : gimple_return_retval (as_a <greturn *> (t))); 5030 tree tem = rhs; 5031 while (handled_component_p (tem)) 5032 tem = TREE_OPERAND (tem, 0); 5033 if ((DECL_P (tem) 5034 && !auto_var_in_fn_p (tem, fn->decl)) 5035 || INDIRECT_REF_P (tem) 5036 || (TREE_CODE (tem) == MEM_REF 5037 && !(TREE_CODE (TREE_OPERAND (tem, 0)) == ADDR_EXPR 5038 && auto_var_in_fn_p 5039 (TREE_OPERAND (TREE_OPERAND (tem, 0), 0), fn->decl)))) 5040 { 5041 struct constraint_expr lhs, *rhsp; 5042 unsigned i; 5043 lhs = get_function_part_constraint (fi, fi_uses); 5044 get_constraint_for_address_of (rhs, &rhsc); 5045 FOR_EACH_VEC_ELT (rhsc, i, rhsp) 5046 process_constraint (new_constraint (lhs, *rhsp)); 5047 rhsc.truncate (0); 5048 } 5049 } 5050 5051 if (gcall *call_stmt = dyn_cast <gcall *> (t)) 5052 { 5053 varinfo_t cfi = NULL; 5054 tree decl = gimple_call_fndecl (t); 5055 struct constraint_expr lhs, rhs; 5056 unsigned i, j; 5057 5058 /* For builtins we do not have separate function info. For those 5059 we do not generate escapes for we have to generate clobbers/uses. */ 5060 if (gimple_call_builtin_p (t, BUILT_IN_NORMAL)) 5061 switch (DECL_FUNCTION_CODE (decl)) 5062 { 5063 /* The following functions use and clobber memory pointed to 5064 by their arguments. */ 5065 case BUILT_IN_STRCPY: 5066 case BUILT_IN_STRNCPY: 5067 case BUILT_IN_BCOPY: 5068 case BUILT_IN_MEMCPY: 5069 case BUILT_IN_MEMMOVE: 5070 case BUILT_IN_MEMPCPY: 5071 case BUILT_IN_STPCPY: 5072 case BUILT_IN_STPNCPY: 5073 case BUILT_IN_STRCAT: 5074 case BUILT_IN_STRNCAT: 5075 case BUILT_IN_STRCPY_CHK: 5076 case BUILT_IN_STRNCPY_CHK: 5077 case BUILT_IN_MEMCPY_CHK: 5078 case BUILT_IN_MEMMOVE_CHK: 5079 case BUILT_IN_MEMPCPY_CHK: 5080 case BUILT_IN_STPCPY_CHK: 5081 case BUILT_IN_STPNCPY_CHK: 5082 case BUILT_IN_STRCAT_CHK: 5083 case BUILT_IN_STRNCAT_CHK: 5084 { 5085 tree dest = gimple_call_arg (t, (DECL_FUNCTION_CODE (decl) 5086 == BUILT_IN_BCOPY ? 1 : 0)); 5087 tree src = gimple_call_arg (t, (DECL_FUNCTION_CODE (decl) 5088 == BUILT_IN_BCOPY ? 0 : 1)); 5089 unsigned i; 5090 struct constraint_expr *rhsp, *lhsp; 5091 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc); 5092 lhs = get_function_part_constraint (fi, fi_clobbers); 5093 FOR_EACH_VEC_ELT (lhsc, i, lhsp) 5094 process_constraint (new_constraint (lhs, *lhsp)); 5095 get_constraint_for_ptr_offset (src, NULL_TREE, &rhsc); 5096 lhs = get_function_part_constraint (fi, fi_uses); 5097 FOR_EACH_VEC_ELT (rhsc, i, rhsp) 5098 process_constraint (new_constraint (lhs, *rhsp)); 5099 return; 5100 } 5101 /* The following function clobbers memory pointed to by 5102 its argument. */ 5103 case BUILT_IN_MEMSET: 5104 case BUILT_IN_MEMSET_CHK: 5105 case BUILT_IN_POSIX_MEMALIGN: 5106 { 5107 tree dest = gimple_call_arg (t, 0); 5108 unsigned i; 5109 ce_s *lhsp; 5110 get_constraint_for_ptr_offset (dest, NULL_TREE, &lhsc); 5111 lhs = get_function_part_constraint (fi, fi_clobbers); 5112 FOR_EACH_VEC_ELT (lhsc, i, lhsp) 5113 process_constraint (new_constraint (lhs, *lhsp)); 5114 return; 5115 } 5116 /* The following functions clobber their second and third 5117 arguments. */ 5118 case BUILT_IN_SINCOS: 5119 case BUILT_IN_SINCOSF: 5120 case BUILT_IN_SINCOSL: 5121 { 5122 process_ipa_clobber (fi, gimple_call_arg (t, 1)); 5123 process_ipa_clobber (fi, gimple_call_arg (t, 2)); 5124 return; 5125 } 5126 /* The following functions clobber their second argument. */ 5127 case BUILT_IN_FREXP: 5128 case BUILT_IN_FREXPF: 5129 case BUILT_IN_FREXPL: 5130 case BUILT_IN_LGAMMA_R: 5131 case BUILT_IN_LGAMMAF_R: 5132 case BUILT_IN_LGAMMAL_R: 5133 case BUILT_IN_GAMMA_R: 5134 case BUILT_IN_GAMMAF_R: 5135 case BUILT_IN_GAMMAL_R: 5136 case BUILT_IN_MODF: 5137 case BUILT_IN_MODFF: 5138 case BUILT_IN_MODFL: 5139 { 5140 process_ipa_clobber (fi, gimple_call_arg (t, 1)); 5141 return; 5142 } 5143 /* The following functions clobber their third argument. */ 5144 case BUILT_IN_REMQUO: 5145 case BUILT_IN_REMQUOF: 5146 case BUILT_IN_REMQUOL: 5147 { 5148 process_ipa_clobber (fi, gimple_call_arg (t, 2)); 5149 return; 5150 } 5151 /* The following functions neither read nor clobber memory. */ 5152 case BUILT_IN_ASSUME_ALIGNED: 5153 case BUILT_IN_FREE: 5154 return; 5155 /* Trampolines are of no interest to us. */ 5156 case BUILT_IN_INIT_TRAMPOLINE: 5157 case BUILT_IN_ADJUST_TRAMPOLINE: 5158 return; 5159 case BUILT_IN_VA_START: 5160 case BUILT_IN_VA_END: 5161 return; 5162 case BUILT_IN_GOMP_PARALLEL: 5163 case BUILT_IN_GOACC_PARALLEL: 5164 { 5165 unsigned int fnpos, argpos; 5166 unsigned int implicit_use_args[2]; 5167 unsigned int num_implicit_use_args = 0; 5168 switch (DECL_FUNCTION_CODE (decl)) 5169 { 5170 case BUILT_IN_GOMP_PARALLEL: 5171 /* __builtin_GOMP_parallel (fn, data, num_threads, flags). */ 5172 fnpos = 0; 5173 argpos = 1; 5174 break; 5175 case BUILT_IN_GOACC_PARALLEL: 5176 /* __builtin_GOACC_parallel (device, fn, mapnum, hostaddrs, 5177 sizes, kinds, ...). */ 5178 fnpos = 1; 5179 argpos = 3; 5180 implicit_use_args[num_implicit_use_args++] = 4; 5181 implicit_use_args[num_implicit_use_args++] = 5; 5182 break; 5183 default: 5184 gcc_unreachable (); 5185 } 5186 5187 tree fnarg = gimple_call_arg (t, fnpos); 5188 gcc_assert (TREE_CODE (fnarg) == ADDR_EXPR); 5189 tree fndecl = TREE_OPERAND (fnarg, 0); 5190 if (fndecl_maybe_in_other_partition (fndecl)) 5191 /* Fallthru to general call handling. */ 5192 break; 5193 5194 varinfo_t cfi = get_vi_for_tree (fndecl); 5195 5196 tree arg = gimple_call_arg (t, argpos); 5197 5198 /* Parameter passed by value is used. */ 5199 lhs = get_function_part_constraint (fi, fi_uses); 5200 struct constraint_expr *rhsp; 5201 get_constraint_for (arg, &rhsc); 5202 FOR_EACH_VEC_ELT (rhsc, j, rhsp) 5203 process_constraint (new_constraint (lhs, *rhsp)); 5204 rhsc.truncate (0); 5205 5206 /* Handle parameters used by the call, but not used in cfi, as 5207 implicitly used by cfi. */ 5208 lhs = get_function_part_constraint (cfi, fi_uses); 5209 for (unsigned i = 0; i < num_implicit_use_args; ++i) 5210 { 5211 tree arg = gimple_call_arg (t, implicit_use_args[i]); 5212 get_constraint_for (arg, &rhsc); 5213 FOR_EACH_VEC_ELT (rhsc, j, rhsp) 5214 process_constraint (new_constraint (lhs, *rhsp)); 5215 rhsc.truncate (0); 5216 } 5217 5218 /* The caller clobbers what the callee does. */ 5219 lhs = get_function_part_constraint (fi, fi_clobbers); 5220 rhs = get_function_part_constraint (cfi, fi_clobbers); 5221 process_constraint (new_constraint (lhs, rhs)); 5222 5223 /* The caller uses what the callee does. */ 5224 lhs = get_function_part_constraint (fi, fi_uses); 5225 rhs = get_function_part_constraint (cfi, fi_uses); 5226 process_constraint (new_constraint (lhs, rhs)); 5227 5228 return; 5229 } 5230 /* printf-style functions may have hooks to set pointers to 5231 point to somewhere into the generated string. Leave them 5232 for a later exercise... */ 5233 default: 5234 /* Fallthru to general call handling. */; 5235 } 5236 5237 /* Parameters passed by value are used. */ 5238 lhs = get_function_part_constraint (fi, fi_uses); 5239 for (i = 0; i < gimple_call_num_args (t); i++) 5240 { 5241 struct constraint_expr *rhsp; 5242 tree arg = gimple_call_arg (t, i); 5243 5244 if (TREE_CODE (arg) == SSA_NAME 5245 || is_gimple_min_invariant (arg)) 5246 continue; 5247 5248 get_constraint_for_address_of (arg, &rhsc); 5249 FOR_EACH_VEC_ELT (rhsc, j, rhsp) 5250 process_constraint (new_constraint (lhs, *rhsp)); 5251 rhsc.truncate (0); 5252 } 5253 5254 /* Build constraints for propagating clobbers/uses along the 5255 callgraph edges. */ 5256 cfi = get_fi_for_callee (call_stmt); 5257 if (cfi->id == anything_id) 5258 { 5259 if (gimple_vdef (t)) 5260 make_constraint_from (first_vi_for_offset (fi, fi_clobbers), 5261 anything_id); 5262 make_constraint_from (first_vi_for_offset (fi, fi_uses), 5263 anything_id); 5264 return; 5265 } 5266 5267 /* For callees without function info (that's external functions), 5268 ESCAPED is clobbered and used. */ 5269 if (gimple_call_fndecl (t) 5270 && !cfi->is_fn_info) 5271 { 5272 varinfo_t vi; 5273 5274 if (gimple_vdef (t)) 5275 make_copy_constraint (first_vi_for_offset (fi, fi_clobbers), 5276 escaped_id); 5277 make_copy_constraint (first_vi_for_offset (fi, fi_uses), escaped_id); 5278 5279 /* Also honor the call statement use/clobber info. */ 5280 if ((vi = lookup_call_clobber_vi (call_stmt)) != NULL) 5281 make_copy_constraint (first_vi_for_offset (fi, fi_clobbers), 5282 vi->id); 5283 if ((vi = lookup_call_use_vi (call_stmt)) != NULL) 5284 make_copy_constraint (first_vi_for_offset (fi, fi_uses), 5285 vi->id); 5286 return; 5287 } 5288 5289 /* Otherwise the caller clobbers and uses what the callee does. 5290 ??? This should use a new complex constraint that filters 5291 local variables of the callee. */ 5292 if (gimple_vdef (t)) 5293 { 5294 lhs = get_function_part_constraint (fi, fi_clobbers); 5295 rhs = get_function_part_constraint (cfi, fi_clobbers); 5296 process_constraint (new_constraint (lhs, rhs)); 5297 } 5298 lhs = get_function_part_constraint (fi, fi_uses); 5299 rhs = get_function_part_constraint (cfi, fi_uses); 5300 process_constraint (new_constraint (lhs, rhs)); 5301 } 5302 else if (gimple_code (t) == GIMPLE_ASM) 5303 { 5304 /* ??? Ick. We can do better. */ 5305 if (gimple_vdef (t)) 5306 make_constraint_from (first_vi_for_offset (fi, fi_clobbers), 5307 anything_id); 5308 make_constraint_from (first_vi_for_offset (fi, fi_uses), 5309 anything_id); 5310 } 5311 } 5312 5313 5314 /* Find the first varinfo in the same variable as START that overlaps with 5315 OFFSET. Return NULL if we can't find one. */ 5316 5317 static varinfo_t 5318 first_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset) 5319 { 5320 /* If the offset is outside of the variable, bail out. */ 5321 if (offset >= start->fullsize) 5322 return NULL; 5323 5324 /* If we cannot reach offset from start, lookup the first field 5325 and start from there. */ 5326 if (start->offset > offset) 5327 start = get_varinfo (start->head); 5328 5329 while (start) 5330 { 5331 /* We may not find a variable in the field list with the actual 5332 offset when we have glommed a structure to a variable. 5333 In that case, however, offset should still be within the size 5334 of the variable. */ 5335 if (offset >= start->offset 5336 && (offset - start->offset) < start->size) 5337 return start; 5338 5339 start = vi_next (start); 5340 } 5341 5342 return NULL; 5343 } 5344 5345 /* Find the first varinfo in the same variable as START that overlaps with 5346 OFFSET. If there is no such varinfo the varinfo directly preceding 5347 OFFSET is returned. */ 5348 5349 static varinfo_t 5350 first_or_preceding_vi_for_offset (varinfo_t start, 5351 unsigned HOST_WIDE_INT offset) 5352 { 5353 /* If we cannot reach offset from start, lookup the first field 5354 and start from there. */ 5355 if (start->offset > offset) 5356 start = get_varinfo (start->head); 5357 5358 /* We may not find a variable in the field list with the actual 5359 offset when we have glommed a structure to a variable. 5360 In that case, however, offset should still be within the size 5361 of the variable. 5362 If we got beyond the offset we look for return the field 5363 directly preceding offset which may be the last field. */ 5364 while (start->next 5365 && offset >= start->offset 5366 && !((offset - start->offset) < start->size)) 5367 start = vi_next (start); 5368 5369 return start; 5370 } 5371 5372 5373 /* This structure is used during pushing fields onto the fieldstack 5374 to track the offset of the field, since bitpos_of_field gives it 5375 relative to its immediate containing type, and we want it relative 5376 to the ultimate containing object. */ 5377 5378 struct fieldoff 5379 { 5380 /* Offset from the base of the base containing object to this field. */ 5381 HOST_WIDE_INT offset; 5382 5383 /* Size, in bits, of the field. */ 5384 unsigned HOST_WIDE_INT size; 5385 5386 unsigned has_unknown_size : 1; 5387 5388 unsigned must_have_pointers : 1; 5389 5390 unsigned may_have_pointers : 1; 5391 5392 unsigned only_restrict_pointers : 1; 5393 5394 tree restrict_pointed_type; 5395 }; 5396 typedef struct fieldoff fieldoff_s; 5397 5398 5399 /* qsort comparison function for two fieldoff's PA and PB */ 5400 5401 static int 5402 fieldoff_compare (const void *pa, const void *pb) 5403 { 5404 const fieldoff_s *foa = (const fieldoff_s *)pa; 5405 const fieldoff_s *fob = (const fieldoff_s *)pb; 5406 unsigned HOST_WIDE_INT foasize, fobsize; 5407 5408 if (foa->offset < fob->offset) 5409 return -1; 5410 else if (foa->offset > fob->offset) 5411 return 1; 5412 5413 foasize = foa->size; 5414 fobsize = fob->size; 5415 if (foasize < fobsize) 5416 return -1; 5417 else if (foasize > fobsize) 5418 return 1; 5419 return 0; 5420 } 5421 5422 /* Sort a fieldstack according to the field offset and sizes. */ 5423 static void 5424 sort_fieldstack (vec<fieldoff_s> fieldstack) 5425 { 5426 fieldstack.qsort (fieldoff_compare); 5427 } 5428 5429 /* Return true if T is a type that can have subvars. */ 5430 5431 static inline bool 5432 type_can_have_subvars (const_tree t) 5433 { 5434 /* Aggregates without overlapping fields can have subvars. */ 5435 return TREE_CODE (t) == RECORD_TYPE; 5436 } 5437 5438 /* Return true if V is a tree that we can have subvars for. 5439 Normally, this is any aggregate type. Also complex 5440 types which are not gimple registers can have subvars. */ 5441 5442 static inline bool 5443 var_can_have_subvars (const_tree v) 5444 { 5445 /* Volatile variables should never have subvars. */ 5446 if (TREE_THIS_VOLATILE (v)) 5447 return false; 5448 5449 /* Non decls or memory tags can never have subvars. */ 5450 if (!DECL_P (v)) 5451 return false; 5452 5453 return type_can_have_subvars (TREE_TYPE (v)); 5454 } 5455 5456 /* Return true if T is a type that does contain pointers. */ 5457 5458 static bool 5459 type_must_have_pointers (tree type) 5460 { 5461 if (POINTER_TYPE_P (type)) 5462 return true; 5463 5464 if (TREE_CODE (type) == ARRAY_TYPE) 5465 return type_must_have_pointers (TREE_TYPE (type)); 5466 5467 /* A function or method can have pointers as arguments, so track 5468 those separately. */ 5469 if (TREE_CODE (type) == FUNCTION_TYPE 5470 || TREE_CODE (type) == METHOD_TYPE) 5471 return true; 5472 5473 return false; 5474 } 5475 5476 static bool 5477 field_must_have_pointers (tree t) 5478 { 5479 return type_must_have_pointers (TREE_TYPE (t)); 5480 } 5481 5482 /* Given a TYPE, and a vector of field offsets FIELDSTACK, push all 5483 the fields of TYPE onto fieldstack, recording their offsets along 5484 the way. 5485 5486 OFFSET is used to keep track of the offset in this entire 5487 structure, rather than just the immediately containing structure. 5488 Returns false if the caller is supposed to handle the field we 5489 recursed for. */ 5490 5491 static bool 5492 push_fields_onto_fieldstack (tree type, vec<fieldoff_s> *fieldstack, 5493 HOST_WIDE_INT offset) 5494 { 5495 tree field; 5496 bool empty_p = true; 5497 5498 if (TREE_CODE (type) != RECORD_TYPE) 5499 return false; 5500 5501 /* If the vector of fields is growing too big, bail out early. 5502 Callers check for vec::length <= MAX_FIELDS_FOR_FIELD_SENSITIVE, make 5503 sure this fails. */ 5504 if (fieldstack->length () > MAX_FIELDS_FOR_FIELD_SENSITIVE) 5505 return false; 5506 5507 for (field = TYPE_FIELDS (type); field; field = DECL_CHAIN (field)) 5508 if (TREE_CODE (field) == FIELD_DECL) 5509 { 5510 bool push = false; 5511 HOST_WIDE_INT foff = bitpos_of_field (field); 5512 tree field_type = TREE_TYPE (field); 5513 5514 if (!var_can_have_subvars (field) 5515 || TREE_CODE (field_type) == QUAL_UNION_TYPE 5516 || TREE_CODE (field_type) == UNION_TYPE) 5517 push = true; 5518 else if (!push_fields_onto_fieldstack 5519 (field_type, fieldstack, offset + foff) 5520 && (DECL_SIZE (field) 5521 && !integer_zerop (DECL_SIZE (field)))) 5522 /* Empty structures may have actual size, like in C++. So 5523 see if we didn't push any subfields and the size is 5524 nonzero, push the field onto the stack. */ 5525 push = true; 5526 5527 if (push) 5528 { 5529 fieldoff_s *pair = NULL; 5530 bool has_unknown_size = false; 5531 bool must_have_pointers_p; 5532 5533 if (!fieldstack->is_empty ()) 5534 pair = &fieldstack->last (); 5535 5536 /* If there isn't anything at offset zero, create sth. */ 5537 if (!pair 5538 && offset + foff != 0) 5539 { 5540 fieldoff_s e 5541 = {0, offset + foff, false, false, true, false, NULL_TREE}; 5542 pair = fieldstack->safe_push (e); 5543 } 5544 5545 if (!DECL_SIZE (field) 5546 || !tree_fits_uhwi_p (DECL_SIZE (field))) 5547 has_unknown_size = true; 5548 5549 /* If adjacent fields do not contain pointers merge them. */ 5550 must_have_pointers_p = field_must_have_pointers (field); 5551 if (pair 5552 && !has_unknown_size 5553 && !must_have_pointers_p 5554 && !pair->must_have_pointers 5555 && !pair->has_unknown_size 5556 && pair->offset + (HOST_WIDE_INT)pair->size == offset + foff) 5557 { 5558 pair->size += tree_to_uhwi (DECL_SIZE (field)); 5559 } 5560 else 5561 { 5562 fieldoff_s e; 5563 e.offset = offset + foff; 5564 e.has_unknown_size = has_unknown_size; 5565 if (!has_unknown_size) 5566 e.size = tree_to_uhwi (DECL_SIZE (field)); 5567 else 5568 e.size = -1; 5569 e.must_have_pointers = must_have_pointers_p; 5570 e.may_have_pointers = true; 5571 e.only_restrict_pointers 5572 = (!has_unknown_size 5573 && POINTER_TYPE_P (field_type) 5574 && TYPE_RESTRICT (field_type)); 5575 if (e.only_restrict_pointers) 5576 e.restrict_pointed_type = TREE_TYPE (field_type); 5577 fieldstack->safe_push (e); 5578 } 5579 } 5580 5581 empty_p = false; 5582 } 5583 5584 return !empty_p; 5585 } 5586 5587 /* Count the number of arguments DECL has, and set IS_VARARGS to true 5588 if it is a varargs function. */ 5589 5590 static unsigned int 5591 count_num_arguments (tree decl, bool *is_varargs) 5592 { 5593 unsigned int num = 0; 5594 tree t; 5595 5596 /* Capture named arguments for K&R functions. They do not 5597 have a prototype and thus no TYPE_ARG_TYPES. */ 5598 for (t = DECL_ARGUMENTS (decl); t; t = DECL_CHAIN (t)) 5599 ++num; 5600 5601 /* Check if the function has variadic arguments. */ 5602 for (t = TYPE_ARG_TYPES (TREE_TYPE (decl)); t; t = TREE_CHAIN (t)) 5603 if (TREE_VALUE (t) == void_type_node) 5604 break; 5605 if (!t) 5606 *is_varargs = true; 5607 5608 return num; 5609 } 5610 5611 /* Creation function node for DECL, using NAME, and return the index 5612 of the variable we've created for the function. If NONLOCAL_p, create 5613 initial constraints. */ 5614 5615 static varinfo_t 5616 create_function_info_for (tree decl, const char *name, bool add_id, 5617 bool nonlocal_p) 5618 { 5619 struct function *fn = DECL_STRUCT_FUNCTION (decl); 5620 varinfo_t vi, prev_vi; 5621 tree arg; 5622 unsigned int i; 5623 bool is_varargs = false; 5624 unsigned int num_args = count_num_arguments (decl, &is_varargs); 5625 5626 /* Create the variable info. */ 5627 5628 vi = new_var_info (decl, name, add_id); 5629 vi->offset = 0; 5630 vi->size = 1; 5631 vi->fullsize = fi_parm_base + num_args; 5632 vi->is_fn_info = 1; 5633 vi->may_have_pointers = false; 5634 if (is_varargs) 5635 vi->fullsize = ~0; 5636 insert_vi_for_tree (vi->decl, vi); 5637 5638 prev_vi = vi; 5639 5640 /* Create a variable for things the function clobbers and one for 5641 things the function uses. */ 5642 { 5643 varinfo_t clobbervi, usevi; 5644 const char *newname; 5645 char *tempname; 5646 5647 tempname = xasprintf ("%s.clobber", name); 5648 newname = ggc_strdup (tempname); 5649 free (tempname); 5650 5651 clobbervi = new_var_info (NULL, newname, false); 5652 clobbervi->offset = fi_clobbers; 5653 clobbervi->size = 1; 5654 clobbervi->fullsize = vi->fullsize; 5655 clobbervi->is_full_var = true; 5656 clobbervi->is_global_var = false; 5657 5658 gcc_assert (prev_vi->offset < clobbervi->offset); 5659 prev_vi->next = clobbervi->id; 5660 prev_vi = clobbervi; 5661 5662 tempname = xasprintf ("%s.use", name); 5663 newname = ggc_strdup (tempname); 5664 free (tempname); 5665 5666 usevi = new_var_info (NULL, newname, false); 5667 usevi->offset = fi_uses; 5668 usevi->size = 1; 5669 usevi->fullsize = vi->fullsize; 5670 usevi->is_full_var = true; 5671 usevi->is_global_var = false; 5672 5673 gcc_assert (prev_vi->offset < usevi->offset); 5674 prev_vi->next = usevi->id; 5675 prev_vi = usevi; 5676 } 5677 5678 /* And one for the static chain. */ 5679 if (fn->static_chain_decl != NULL_TREE) 5680 { 5681 varinfo_t chainvi; 5682 const char *newname; 5683 char *tempname; 5684 5685 tempname = xasprintf ("%s.chain", name); 5686 newname = ggc_strdup (tempname); 5687 free (tempname); 5688 5689 chainvi = new_var_info (fn->static_chain_decl, newname, false); 5690 chainvi->offset = fi_static_chain; 5691 chainvi->size = 1; 5692 chainvi->fullsize = vi->fullsize; 5693 chainvi->is_full_var = true; 5694 chainvi->is_global_var = false; 5695 5696 insert_vi_for_tree (fn->static_chain_decl, chainvi); 5697 5698 if (nonlocal_p 5699 && chainvi->may_have_pointers) 5700 make_constraint_from (chainvi, nonlocal_id); 5701 5702 gcc_assert (prev_vi->offset < chainvi->offset); 5703 prev_vi->next = chainvi->id; 5704 prev_vi = chainvi; 5705 } 5706 5707 /* Create a variable for the return var. */ 5708 if (DECL_RESULT (decl) != NULL 5709 || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl)))) 5710 { 5711 varinfo_t resultvi; 5712 const char *newname; 5713 char *tempname; 5714 tree resultdecl = decl; 5715 5716 if (DECL_RESULT (decl)) 5717 resultdecl = DECL_RESULT (decl); 5718 5719 tempname = xasprintf ("%s.result", name); 5720 newname = ggc_strdup (tempname); 5721 free (tempname); 5722 5723 resultvi = new_var_info (resultdecl, newname, false); 5724 resultvi->offset = fi_result; 5725 resultvi->size = 1; 5726 resultvi->fullsize = vi->fullsize; 5727 resultvi->is_full_var = true; 5728 if (DECL_RESULT (decl)) 5729 resultvi->may_have_pointers = true; 5730 5731 if (DECL_RESULT (decl)) 5732 insert_vi_for_tree (DECL_RESULT (decl), resultvi); 5733 5734 if (nonlocal_p 5735 && DECL_RESULT (decl) 5736 && DECL_BY_REFERENCE (DECL_RESULT (decl))) 5737 make_constraint_from (resultvi, nonlocal_id); 5738 5739 gcc_assert (prev_vi->offset < resultvi->offset); 5740 prev_vi->next = resultvi->id; 5741 prev_vi = resultvi; 5742 } 5743 5744 /* We also need to make function return values escape. Nothing 5745 escapes by returning from main though. */ 5746 if (nonlocal_p 5747 && !MAIN_NAME_P (DECL_NAME (decl))) 5748 { 5749 varinfo_t fi, rvi; 5750 fi = lookup_vi_for_tree (decl); 5751 rvi = first_vi_for_offset (fi, fi_result); 5752 if (rvi && rvi->offset == fi_result) 5753 make_copy_constraint (get_varinfo (escaped_id), rvi->id); 5754 } 5755 5756 /* Set up variables for each argument. */ 5757 arg = DECL_ARGUMENTS (decl); 5758 for (i = 0; i < num_args; i++) 5759 { 5760 varinfo_t argvi; 5761 const char *newname; 5762 char *tempname; 5763 tree argdecl = decl; 5764 5765 if (arg) 5766 argdecl = arg; 5767 5768 tempname = xasprintf ("%s.arg%d", name, i); 5769 newname = ggc_strdup (tempname); 5770 free (tempname); 5771 5772 argvi = new_var_info (argdecl, newname, false); 5773 argvi->offset = fi_parm_base + i; 5774 argvi->size = 1; 5775 argvi->is_full_var = true; 5776 argvi->fullsize = vi->fullsize; 5777 if (arg) 5778 argvi->may_have_pointers = true; 5779 5780 if (arg) 5781 insert_vi_for_tree (arg, argvi); 5782 5783 if (nonlocal_p 5784 && argvi->may_have_pointers) 5785 make_constraint_from (argvi, nonlocal_id); 5786 5787 gcc_assert (prev_vi->offset < argvi->offset); 5788 prev_vi->next = argvi->id; 5789 prev_vi = argvi; 5790 if (arg) 5791 arg = DECL_CHAIN (arg); 5792 } 5793 5794 /* Add one representative for all further args. */ 5795 if (is_varargs) 5796 { 5797 varinfo_t argvi; 5798 const char *newname; 5799 char *tempname; 5800 tree decl; 5801 5802 tempname = xasprintf ("%s.varargs", name); 5803 newname = ggc_strdup (tempname); 5804 free (tempname); 5805 5806 /* We need sth that can be pointed to for va_start. */ 5807 decl = build_fake_var_decl (ptr_type_node); 5808 5809 argvi = new_var_info (decl, newname, false); 5810 argvi->offset = fi_parm_base + num_args; 5811 argvi->size = ~0; 5812 argvi->is_full_var = true; 5813 argvi->is_heap_var = true; 5814 argvi->fullsize = vi->fullsize; 5815 5816 if (nonlocal_p 5817 && argvi->may_have_pointers) 5818 make_constraint_from (argvi, nonlocal_id); 5819 5820 gcc_assert (prev_vi->offset < argvi->offset); 5821 prev_vi->next = argvi->id; 5822 prev_vi = argvi; 5823 } 5824 5825 return vi; 5826 } 5827 5828 5829 /* Return true if FIELDSTACK contains fields that overlap. 5830 FIELDSTACK is assumed to be sorted by offset. */ 5831 5832 static bool 5833 check_for_overlaps (vec<fieldoff_s> fieldstack) 5834 { 5835 fieldoff_s *fo = NULL; 5836 unsigned int i; 5837 HOST_WIDE_INT lastoffset = -1; 5838 5839 FOR_EACH_VEC_ELT (fieldstack, i, fo) 5840 { 5841 if (fo->offset == lastoffset) 5842 return true; 5843 lastoffset = fo->offset; 5844 } 5845 return false; 5846 } 5847 5848 /* Create a varinfo structure for NAME and DECL, and add it to VARMAP. 5849 This will also create any varinfo structures necessary for fields 5850 of DECL. DECL is a function parameter if HANDLE_PARAM is set. 5851 HANDLED_STRUCT_TYPE is used to register struct types reached by following 5852 restrict pointers. This is needed to prevent infinite recursion. */ 5853 5854 static varinfo_t 5855 create_variable_info_for_1 (tree decl, const char *name, bool add_id, 5856 bool handle_param, bitmap handled_struct_type) 5857 { 5858 varinfo_t vi, newvi; 5859 tree decl_type = TREE_TYPE (decl); 5860 tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decl_type); 5861 auto_vec<fieldoff_s> fieldstack; 5862 fieldoff_s *fo; 5863 unsigned int i; 5864 5865 if (!declsize 5866 || !tree_fits_uhwi_p (declsize)) 5867 { 5868 vi = new_var_info (decl, name, add_id); 5869 vi->offset = 0; 5870 vi->size = ~0; 5871 vi->fullsize = ~0; 5872 vi->is_unknown_size_var = true; 5873 vi->is_full_var = true; 5874 vi->may_have_pointers = true; 5875 return vi; 5876 } 5877 5878 /* Collect field information. */ 5879 if (use_field_sensitive 5880 && var_can_have_subvars (decl) 5881 /* ??? Force us to not use subfields for globals in IPA mode. 5882 Else we'd have to parse arbitrary initializers. */ 5883 && !(in_ipa_mode 5884 && is_global_var (decl))) 5885 { 5886 fieldoff_s *fo = NULL; 5887 bool notokay = false; 5888 unsigned int i; 5889 5890 push_fields_onto_fieldstack (decl_type, &fieldstack, 0); 5891 5892 for (i = 0; !notokay && fieldstack.iterate (i, &fo); i++) 5893 if (fo->has_unknown_size 5894 || fo->offset < 0) 5895 { 5896 notokay = true; 5897 break; 5898 } 5899 5900 /* We can't sort them if we have a field with a variable sized type, 5901 which will make notokay = true. In that case, we are going to return 5902 without creating varinfos for the fields anyway, so sorting them is a 5903 waste to boot. */ 5904 if (!notokay) 5905 { 5906 sort_fieldstack (fieldstack); 5907 /* Due to some C++ FE issues, like PR 22488, we might end up 5908 what appear to be overlapping fields even though they, 5909 in reality, do not overlap. Until the C++ FE is fixed, 5910 we will simply disable field-sensitivity for these cases. */ 5911 notokay = check_for_overlaps (fieldstack); 5912 } 5913 5914 if (notokay) 5915 fieldstack.release (); 5916 } 5917 5918 /* If we didn't end up collecting sub-variables create a full 5919 variable for the decl. */ 5920 if (fieldstack.length () == 0 5921 || fieldstack.length () > MAX_FIELDS_FOR_FIELD_SENSITIVE) 5922 { 5923 vi = new_var_info (decl, name, add_id); 5924 vi->offset = 0; 5925 vi->may_have_pointers = true; 5926 vi->fullsize = tree_to_uhwi (declsize); 5927 vi->size = vi->fullsize; 5928 vi->is_full_var = true; 5929 if (POINTER_TYPE_P (decl_type) 5930 && TYPE_RESTRICT (decl_type)) 5931 vi->only_restrict_pointers = 1; 5932 if (vi->only_restrict_pointers 5933 && !type_contains_placeholder_p (TREE_TYPE (decl_type)) 5934 && handle_param 5935 && !bitmap_bit_p (handled_struct_type, 5936 TYPE_UID (TREE_TYPE (decl_type)))) 5937 { 5938 varinfo_t rvi; 5939 tree heapvar = build_fake_var_decl (TREE_TYPE (decl_type)); 5940 DECL_EXTERNAL (heapvar) = 1; 5941 if (var_can_have_subvars (heapvar)) 5942 bitmap_set_bit (handled_struct_type, 5943 TYPE_UID (TREE_TYPE (decl_type))); 5944 rvi = create_variable_info_for_1 (heapvar, "PARM_NOALIAS", true, 5945 true, handled_struct_type); 5946 if (var_can_have_subvars (heapvar)) 5947 bitmap_clear_bit (handled_struct_type, 5948 TYPE_UID (TREE_TYPE (decl_type))); 5949 rvi->is_restrict_var = 1; 5950 insert_vi_for_tree (heapvar, rvi); 5951 make_constraint_from (vi, rvi->id); 5952 make_param_constraints (rvi); 5953 } 5954 fieldstack.release (); 5955 return vi; 5956 } 5957 5958 vi = new_var_info (decl, name, add_id); 5959 vi->fullsize = tree_to_uhwi (declsize); 5960 if (fieldstack.length () == 1) 5961 vi->is_full_var = true; 5962 for (i = 0, newvi = vi; 5963 fieldstack.iterate (i, &fo); 5964 ++i, newvi = vi_next (newvi)) 5965 { 5966 const char *newname = NULL; 5967 char *tempname; 5968 5969 if (dump_file) 5970 { 5971 if (fieldstack.length () != 1) 5972 { 5973 tempname 5974 = xasprintf ("%s." HOST_WIDE_INT_PRINT_DEC 5975 "+" HOST_WIDE_INT_PRINT_DEC, name, 5976 fo->offset, fo->size); 5977 newname = ggc_strdup (tempname); 5978 free (tempname); 5979 } 5980 } 5981 else 5982 newname = "NULL"; 5983 5984 if (newname) 5985 newvi->name = newname; 5986 newvi->offset = fo->offset; 5987 newvi->size = fo->size; 5988 newvi->fullsize = vi->fullsize; 5989 newvi->may_have_pointers = fo->may_have_pointers; 5990 newvi->only_restrict_pointers = fo->only_restrict_pointers; 5991 if (handle_param 5992 && newvi->only_restrict_pointers 5993 && !type_contains_placeholder_p (fo->restrict_pointed_type) 5994 && !bitmap_bit_p (handled_struct_type, 5995 TYPE_UID (fo->restrict_pointed_type))) 5996 { 5997 varinfo_t rvi; 5998 tree heapvar = build_fake_var_decl (fo->restrict_pointed_type); 5999 DECL_EXTERNAL (heapvar) = 1; 6000 if (var_can_have_subvars (heapvar)) 6001 bitmap_set_bit (handled_struct_type, 6002 TYPE_UID (fo->restrict_pointed_type)); 6003 rvi = create_variable_info_for_1 (heapvar, "PARM_NOALIAS", true, 6004 true, handled_struct_type); 6005 if (var_can_have_subvars (heapvar)) 6006 bitmap_clear_bit (handled_struct_type, 6007 TYPE_UID (fo->restrict_pointed_type)); 6008 rvi->is_restrict_var = 1; 6009 insert_vi_for_tree (heapvar, rvi); 6010 make_constraint_from (newvi, rvi->id); 6011 make_param_constraints (rvi); 6012 } 6013 if (i + 1 < fieldstack.length ()) 6014 { 6015 varinfo_t tem = new_var_info (decl, name, false); 6016 newvi->next = tem->id; 6017 tem->head = vi->id; 6018 } 6019 } 6020 6021 return vi; 6022 } 6023 6024 static unsigned int 6025 create_variable_info_for (tree decl, const char *name, bool add_id) 6026 { 6027 varinfo_t vi = create_variable_info_for_1 (decl, name, add_id, false, NULL); 6028 unsigned int id = vi->id; 6029 6030 insert_vi_for_tree (decl, vi); 6031 6032 if (TREE_CODE (decl) != VAR_DECL) 6033 return id; 6034 6035 /* Create initial constraints for globals. */ 6036 for (; vi; vi = vi_next (vi)) 6037 { 6038 if (!vi->may_have_pointers 6039 || !vi->is_global_var) 6040 continue; 6041 6042 /* Mark global restrict qualified pointers. */ 6043 if ((POINTER_TYPE_P (TREE_TYPE (decl)) 6044 && TYPE_RESTRICT (TREE_TYPE (decl))) 6045 || vi->only_restrict_pointers) 6046 { 6047 varinfo_t rvi 6048 = make_constraint_from_global_restrict (vi, "GLOBAL_RESTRICT", 6049 true); 6050 /* ??? For now exclude reads from globals as restrict sources 6051 if those are not (indirectly) from incoming parameters. */ 6052 rvi->is_restrict_var = false; 6053 continue; 6054 } 6055 6056 /* In non-IPA mode the initializer from nonlocal is all we need. */ 6057 if (!in_ipa_mode 6058 || DECL_HARD_REGISTER (decl)) 6059 make_copy_constraint (vi, nonlocal_id); 6060 6061 /* In IPA mode parse the initializer and generate proper constraints 6062 for it. */ 6063 else 6064 { 6065 varpool_node *vnode = varpool_node::get (decl); 6066 6067 /* For escaped variables initialize them from nonlocal. */ 6068 if (!vnode->all_refs_explicit_p ()) 6069 make_copy_constraint (vi, nonlocal_id); 6070 6071 /* If this is a global variable with an initializer and we are in 6072 IPA mode generate constraints for it. */ 6073 ipa_ref *ref; 6074 for (unsigned idx = 0; vnode->iterate_reference (idx, ref); ++idx) 6075 { 6076 auto_vec<ce_s> rhsc; 6077 struct constraint_expr lhs, *rhsp; 6078 unsigned i; 6079 get_constraint_for_address_of (ref->referred->decl, &rhsc); 6080 lhs.var = vi->id; 6081 lhs.offset = 0; 6082 lhs.type = SCALAR; 6083 FOR_EACH_VEC_ELT (rhsc, i, rhsp) 6084 process_constraint (new_constraint (lhs, *rhsp)); 6085 /* If this is a variable that escapes from the unit 6086 the initializer escapes as well. */ 6087 if (!vnode->all_refs_explicit_p ()) 6088 { 6089 lhs.var = escaped_id; 6090 lhs.offset = 0; 6091 lhs.type = SCALAR; 6092 FOR_EACH_VEC_ELT (rhsc, i, rhsp) 6093 process_constraint (new_constraint (lhs, *rhsp)); 6094 } 6095 } 6096 } 6097 } 6098 6099 return id; 6100 } 6101 6102 /* Print out the points-to solution for VAR to FILE. */ 6103 6104 static void 6105 dump_solution_for_var (FILE *file, unsigned int var) 6106 { 6107 varinfo_t vi = get_varinfo (var); 6108 unsigned int i; 6109 bitmap_iterator bi; 6110 6111 /* Dump the solution for unified vars anyway, this avoids difficulties 6112 in scanning dumps in the testsuite. */ 6113 fprintf (file, "%s = { ", vi->name); 6114 vi = get_varinfo (find (var)); 6115 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi) 6116 fprintf (file, "%s ", get_varinfo (i)->name); 6117 fprintf (file, "}"); 6118 6119 /* But note when the variable was unified. */ 6120 if (vi->id != var) 6121 fprintf (file, " same as %s", vi->name); 6122 6123 fprintf (file, "\n"); 6124 } 6125 6126 /* Print the points-to solution for VAR to stderr. */ 6127 6128 DEBUG_FUNCTION void 6129 debug_solution_for_var (unsigned int var) 6130 { 6131 dump_solution_for_var (stderr, var); 6132 } 6133 6134 /* Register the constraints for function parameter related VI. */ 6135 6136 static void 6137 make_param_constraints (varinfo_t vi) 6138 { 6139 for (; vi; vi = vi_next (vi)) 6140 { 6141 if (vi->only_restrict_pointers) 6142 ; 6143 else if (vi->may_have_pointers) 6144 make_constraint_from (vi, nonlocal_id); 6145 6146 if (vi->is_full_var) 6147 break; 6148 } 6149 } 6150 6151 /* Create varinfo structures for all of the variables in the 6152 function for intraprocedural mode. */ 6153 6154 static void 6155 intra_create_variable_infos (struct function *fn) 6156 { 6157 tree t; 6158 bitmap handled_struct_type = NULL; 6159 6160 /* For each incoming pointer argument arg, create the constraint ARG 6161 = NONLOCAL or a dummy variable if it is a restrict qualified 6162 passed-by-reference argument. */ 6163 for (t = DECL_ARGUMENTS (fn->decl); t; t = DECL_CHAIN (t)) 6164 { 6165 if (handled_struct_type == NULL) 6166 handled_struct_type = BITMAP_ALLOC (NULL); 6167 6168 varinfo_t p 6169 = create_variable_info_for_1 (t, alias_get_name (t), false, true, 6170 handled_struct_type); 6171 insert_vi_for_tree (t, p); 6172 6173 make_param_constraints (p); 6174 } 6175 6176 if (handled_struct_type != NULL) 6177 BITMAP_FREE (handled_struct_type); 6178 6179 /* Add a constraint for a result decl that is passed by reference. */ 6180 if (DECL_RESULT (fn->decl) 6181 && DECL_BY_REFERENCE (DECL_RESULT (fn->decl))) 6182 { 6183 varinfo_t p, result_vi = get_vi_for_tree (DECL_RESULT (fn->decl)); 6184 6185 for (p = result_vi; p; p = vi_next (p)) 6186 make_constraint_from (p, nonlocal_id); 6187 } 6188 6189 /* Add a constraint for the incoming static chain parameter. */ 6190 if (fn->static_chain_decl != NULL_TREE) 6191 { 6192 varinfo_t p, chain_vi = get_vi_for_tree (fn->static_chain_decl); 6193 6194 for (p = chain_vi; p; p = vi_next (p)) 6195 make_constraint_from (p, nonlocal_id); 6196 } 6197 } 6198 6199 /* Structure used to put solution bitmaps in a hashtable so they can 6200 be shared among variables with the same points-to set. */ 6201 6202 typedef struct shared_bitmap_info 6203 { 6204 bitmap pt_vars; 6205 hashval_t hashcode; 6206 } *shared_bitmap_info_t; 6207 typedef const struct shared_bitmap_info *const_shared_bitmap_info_t; 6208 6209 /* Shared_bitmap hashtable helpers. */ 6210 6211 struct shared_bitmap_hasher : free_ptr_hash <shared_bitmap_info> 6212 { 6213 static inline hashval_t hash (const shared_bitmap_info *); 6214 static inline bool equal (const shared_bitmap_info *, 6215 const shared_bitmap_info *); 6216 }; 6217 6218 /* Hash function for a shared_bitmap_info_t */ 6219 6220 inline hashval_t 6221 shared_bitmap_hasher::hash (const shared_bitmap_info *bi) 6222 { 6223 return bi->hashcode; 6224 } 6225 6226 /* Equality function for two shared_bitmap_info_t's. */ 6227 6228 inline bool 6229 shared_bitmap_hasher::equal (const shared_bitmap_info *sbi1, 6230 const shared_bitmap_info *sbi2) 6231 { 6232 return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars); 6233 } 6234 6235 /* Shared_bitmap hashtable. */ 6236 6237 static hash_table<shared_bitmap_hasher> *shared_bitmap_table; 6238 6239 /* Lookup a bitmap in the shared bitmap hashtable, and return an already 6240 existing instance if there is one, NULL otherwise. */ 6241 6242 static bitmap 6243 shared_bitmap_lookup (bitmap pt_vars) 6244 { 6245 shared_bitmap_info **slot; 6246 struct shared_bitmap_info sbi; 6247 6248 sbi.pt_vars = pt_vars; 6249 sbi.hashcode = bitmap_hash (pt_vars); 6250 6251 slot = shared_bitmap_table->find_slot (&sbi, NO_INSERT); 6252 if (!slot) 6253 return NULL; 6254 else 6255 return (*slot)->pt_vars; 6256 } 6257 6258 6259 /* Add a bitmap to the shared bitmap hashtable. */ 6260 6261 static void 6262 shared_bitmap_add (bitmap pt_vars) 6263 { 6264 shared_bitmap_info **slot; 6265 shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info); 6266 6267 sbi->pt_vars = pt_vars; 6268 sbi->hashcode = bitmap_hash (pt_vars); 6269 6270 slot = shared_bitmap_table->find_slot (sbi, INSERT); 6271 gcc_assert (!*slot); 6272 *slot = sbi; 6273 } 6274 6275 6276 /* Set bits in INTO corresponding to the variable uids in solution set FROM. */ 6277 6278 static void 6279 set_uids_in_ptset (bitmap into, bitmap from, struct pt_solution *pt, 6280 tree fndecl) 6281 { 6282 unsigned int i; 6283 bitmap_iterator bi; 6284 varinfo_t escaped_vi = get_varinfo (find (escaped_id)); 6285 bool everything_escaped 6286 = escaped_vi->solution && bitmap_bit_p (escaped_vi->solution, anything_id); 6287 6288 EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi) 6289 { 6290 varinfo_t vi = get_varinfo (i); 6291 6292 /* The only artificial variables that are allowed in a may-alias 6293 set are heap variables. */ 6294 if (vi->is_artificial_var && !vi->is_heap_var) 6295 continue; 6296 6297 if (everything_escaped 6298 || (escaped_vi->solution 6299 && bitmap_bit_p (escaped_vi->solution, i))) 6300 { 6301 pt->vars_contains_escaped = true; 6302 pt->vars_contains_escaped_heap = vi->is_heap_var; 6303 } 6304 6305 if (TREE_CODE (vi->decl) == VAR_DECL 6306 || TREE_CODE (vi->decl) == PARM_DECL 6307 || TREE_CODE (vi->decl) == RESULT_DECL) 6308 { 6309 /* If we are in IPA mode we will not recompute points-to 6310 sets after inlining so make sure they stay valid. */ 6311 if (in_ipa_mode 6312 && !DECL_PT_UID_SET_P (vi->decl)) 6313 SET_DECL_PT_UID (vi->decl, DECL_UID (vi->decl)); 6314 6315 /* Add the decl to the points-to set. Note that the points-to 6316 set contains global variables. */ 6317 bitmap_set_bit (into, DECL_PT_UID (vi->decl)); 6318 if (vi->is_global_var 6319 /* In IPA mode the escaped_heap trick doesn't work as 6320 ESCAPED is escaped from the unit but 6321 pt_solution_includes_global needs to answer true for 6322 all variables not automatic within a function. 6323 For the same reason is_global_var is not the 6324 correct flag to track - local variables from other 6325 functions also need to be considered global. 6326 Conveniently all HEAP vars are not put in function 6327 scope. */ 6328 || (in_ipa_mode 6329 && fndecl 6330 && ! auto_var_in_fn_p (vi->decl, fndecl))) 6331 pt->vars_contains_nonlocal = true; 6332 } 6333 6334 else if (TREE_CODE (vi->decl) == FUNCTION_DECL 6335 || TREE_CODE (vi->decl) == LABEL_DECL) 6336 { 6337 /* Nothing should read/write from/to code so we can 6338 save bits by not including them in the points-to bitmaps. 6339 Still mark the points-to set as containing global memory 6340 to make code-patching possible - see PR70128. */ 6341 pt->vars_contains_nonlocal = true; 6342 } 6343 } 6344 } 6345 6346 6347 /* Compute the points-to solution *PT for the variable VI. */ 6348 6349 static struct pt_solution 6350 find_what_var_points_to (tree fndecl, varinfo_t orig_vi) 6351 { 6352 unsigned int i; 6353 bitmap_iterator bi; 6354 bitmap finished_solution; 6355 bitmap result; 6356 varinfo_t vi; 6357 struct pt_solution *pt; 6358 6359 /* This variable may have been collapsed, let's get the real 6360 variable. */ 6361 vi = get_varinfo (find (orig_vi->id)); 6362 6363 /* See if we have already computed the solution and return it. */ 6364 pt_solution **slot = &final_solutions->get_or_insert (vi); 6365 if (*slot != NULL) 6366 return **slot; 6367 6368 *slot = pt = XOBNEW (&final_solutions_obstack, struct pt_solution); 6369 memset (pt, 0, sizeof (struct pt_solution)); 6370 6371 /* Translate artificial variables into SSA_NAME_PTR_INFO 6372 attributes. */ 6373 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi) 6374 { 6375 varinfo_t vi = get_varinfo (i); 6376 6377 if (vi->is_artificial_var) 6378 { 6379 if (vi->id == nothing_id) 6380 pt->null = 1; 6381 else if (vi->id == escaped_id) 6382 { 6383 if (in_ipa_mode) 6384 pt->ipa_escaped = 1; 6385 else 6386 pt->escaped = 1; 6387 /* Expand some special vars of ESCAPED in-place here. */ 6388 varinfo_t evi = get_varinfo (find (escaped_id)); 6389 if (bitmap_bit_p (evi->solution, nonlocal_id)) 6390 pt->nonlocal = 1; 6391 } 6392 else if (vi->id == nonlocal_id) 6393 pt->nonlocal = 1; 6394 else if (vi->is_heap_var) 6395 /* We represent heapvars in the points-to set properly. */ 6396 ; 6397 else if (vi->id == string_id) 6398 /* Nobody cares - STRING_CSTs are read-only entities. */ 6399 ; 6400 else if (vi->id == anything_id 6401 || vi->id == integer_id) 6402 pt->anything = 1; 6403 } 6404 } 6405 6406 /* Instead of doing extra work, simply do not create 6407 elaborate points-to information for pt_anything pointers. */ 6408 if (pt->anything) 6409 return *pt; 6410 6411 /* Share the final set of variables when possible. */ 6412 finished_solution = BITMAP_GGC_ALLOC (); 6413 stats.points_to_sets_created++; 6414 6415 set_uids_in_ptset (finished_solution, vi->solution, pt, fndecl); 6416 result = shared_bitmap_lookup (finished_solution); 6417 if (!result) 6418 { 6419 shared_bitmap_add (finished_solution); 6420 pt->vars = finished_solution; 6421 } 6422 else 6423 { 6424 pt->vars = result; 6425 bitmap_clear (finished_solution); 6426 } 6427 6428 return *pt; 6429 } 6430 6431 /* Given a pointer variable P, fill in its points-to set. */ 6432 6433 static void 6434 find_what_p_points_to (tree fndecl, tree p) 6435 { 6436 struct ptr_info_def *pi; 6437 tree lookup_p = p; 6438 varinfo_t vi; 6439 6440 /* For parameters, get at the points-to set for the actual parm 6441 decl. */ 6442 if (TREE_CODE (p) == SSA_NAME 6443 && SSA_NAME_IS_DEFAULT_DEF (p) 6444 && (TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL 6445 || TREE_CODE (SSA_NAME_VAR (p)) == RESULT_DECL)) 6446 lookup_p = SSA_NAME_VAR (p); 6447 6448 vi = lookup_vi_for_tree (lookup_p); 6449 if (!vi) 6450 return; 6451 6452 pi = get_ptr_info (p); 6453 pi->pt = find_what_var_points_to (fndecl, vi); 6454 } 6455 6456 6457 /* Query statistics for points-to solutions. */ 6458 6459 static struct { 6460 unsigned HOST_WIDE_INT pt_solution_includes_may_alias; 6461 unsigned HOST_WIDE_INT pt_solution_includes_no_alias; 6462 unsigned HOST_WIDE_INT pt_solutions_intersect_may_alias; 6463 unsigned HOST_WIDE_INT pt_solutions_intersect_no_alias; 6464 } pta_stats; 6465 6466 void 6467 dump_pta_stats (FILE *s) 6468 { 6469 fprintf (s, "\nPTA query stats:\n"); 6470 fprintf (s, " pt_solution_includes: " 6471 HOST_WIDE_INT_PRINT_DEC" disambiguations, " 6472 HOST_WIDE_INT_PRINT_DEC" queries\n", 6473 pta_stats.pt_solution_includes_no_alias, 6474 pta_stats.pt_solution_includes_no_alias 6475 + pta_stats.pt_solution_includes_may_alias); 6476 fprintf (s, " pt_solutions_intersect: " 6477 HOST_WIDE_INT_PRINT_DEC" disambiguations, " 6478 HOST_WIDE_INT_PRINT_DEC" queries\n", 6479 pta_stats.pt_solutions_intersect_no_alias, 6480 pta_stats.pt_solutions_intersect_no_alias 6481 + pta_stats.pt_solutions_intersect_may_alias); 6482 } 6483 6484 6485 /* Reset the points-to solution *PT to a conservative default 6486 (point to anything). */ 6487 6488 void 6489 pt_solution_reset (struct pt_solution *pt) 6490 { 6491 memset (pt, 0, sizeof (struct pt_solution)); 6492 pt->anything = true; 6493 } 6494 6495 /* Set the points-to solution *PT to point only to the variables 6496 in VARS. VARS_CONTAINS_GLOBAL specifies whether that contains 6497 global variables and VARS_CONTAINS_RESTRICT specifies whether 6498 it contains restrict tag variables. */ 6499 6500 void 6501 pt_solution_set (struct pt_solution *pt, bitmap vars, 6502 bool vars_contains_nonlocal) 6503 { 6504 memset (pt, 0, sizeof (struct pt_solution)); 6505 pt->vars = vars; 6506 pt->vars_contains_nonlocal = vars_contains_nonlocal; 6507 pt->vars_contains_escaped 6508 = (cfun->gimple_df->escaped.anything 6509 || bitmap_intersect_p (cfun->gimple_df->escaped.vars, vars)); 6510 } 6511 6512 /* Set the points-to solution *PT to point only to the variable VAR. */ 6513 6514 void 6515 pt_solution_set_var (struct pt_solution *pt, tree var) 6516 { 6517 memset (pt, 0, sizeof (struct pt_solution)); 6518 pt->vars = BITMAP_GGC_ALLOC (); 6519 bitmap_set_bit (pt->vars, DECL_PT_UID (var)); 6520 pt->vars_contains_nonlocal = is_global_var (var); 6521 pt->vars_contains_escaped 6522 = (cfun->gimple_df->escaped.anything 6523 || bitmap_bit_p (cfun->gimple_df->escaped.vars, DECL_PT_UID (var))); 6524 } 6525 6526 /* Computes the union of the points-to solutions *DEST and *SRC and 6527 stores the result in *DEST. This changes the points-to bitmap 6528 of *DEST and thus may not be used if that might be shared. 6529 The points-to bitmap of *SRC and *DEST will not be shared after 6530 this function if they were not before. */ 6531 6532 static void 6533 pt_solution_ior_into (struct pt_solution *dest, struct pt_solution *src) 6534 { 6535 dest->anything |= src->anything; 6536 if (dest->anything) 6537 { 6538 pt_solution_reset (dest); 6539 return; 6540 } 6541 6542 dest->nonlocal |= src->nonlocal; 6543 dest->escaped |= src->escaped; 6544 dest->ipa_escaped |= src->ipa_escaped; 6545 dest->null |= src->null; 6546 dest->vars_contains_nonlocal |= src->vars_contains_nonlocal; 6547 dest->vars_contains_escaped |= src->vars_contains_escaped; 6548 dest->vars_contains_escaped_heap |= src->vars_contains_escaped_heap; 6549 if (!src->vars) 6550 return; 6551 6552 if (!dest->vars) 6553 dest->vars = BITMAP_GGC_ALLOC (); 6554 bitmap_ior_into (dest->vars, src->vars); 6555 } 6556 6557 /* Return true if the points-to solution *PT is empty. */ 6558 6559 bool 6560 pt_solution_empty_p (struct pt_solution *pt) 6561 { 6562 if (pt->anything 6563 || pt->nonlocal) 6564 return false; 6565 6566 if (pt->vars 6567 && !bitmap_empty_p (pt->vars)) 6568 return false; 6569 6570 /* If the solution includes ESCAPED, check if that is empty. */ 6571 if (pt->escaped 6572 && !pt_solution_empty_p (&cfun->gimple_df->escaped)) 6573 return false; 6574 6575 /* If the solution includes ESCAPED, check if that is empty. */ 6576 if (pt->ipa_escaped 6577 && !pt_solution_empty_p (&ipa_escaped_pt)) 6578 return false; 6579 6580 return true; 6581 } 6582 6583 /* Return true if the points-to solution *PT only point to a single var, and 6584 return the var uid in *UID. */ 6585 6586 bool 6587 pt_solution_singleton_p (struct pt_solution *pt, unsigned *uid) 6588 { 6589 if (pt->anything || pt->nonlocal || pt->escaped || pt->ipa_escaped 6590 || pt->null || pt->vars == NULL 6591 || !bitmap_single_bit_set_p (pt->vars)) 6592 return false; 6593 6594 *uid = bitmap_first_set_bit (pt->vars); 6595 return true; 6596 } 6597 6598 /* Return true if the points-to solution *PT includes global memory. */ 6599 6600 bool 6601 pt_solution_includes_global (struct pt_solution *pt) 6602 { 6603 if (pt->anything 6604 || pt->nonlocal 6605 || pt->vars_contains_nonlocal 6606 /* The following is a hack to make the malloc escape hack work. 6607 In reality we'd need different sets for escaped-through-return 6608 and escaped-to-callees and passes would need to be updated. */ 6609 || pt->vars_contains_escaped_heap) 6610 return true; 6611 6612 /* 'escaped' is also a placeholder so we have to look into it. */ 6613 if (pt->escaped) 6614 return pt_solution_includes_global (&cfun->gimple_df->escaped); 6615 6616 if (pt->ipa_escaped) 6617 return pt_solution_includes_global (&ipa_escaped_pt); 6618 6619 return false; 6620 } 6621 6622 /* Return true if the points-to solution *PT includes the variable 6623 declaration DECL. */ 6624 6625 static bool 6626 pt_solution_includes_1 (struct pt_solution *pt, const_tree decl) 6627 { 6628 if (pt->anything) 6629 return true; 6630 6631 if (pt->nonlocal 6632 && is_global_var (decl)) 6633 return true; 6634 6635 if (pt->vars 6636 && bitmap_bit_p (pt->vars, DECL_PT_UID (decl))) 6637 return true; 6638 6639 /* If the solution includes ESCAPED, check it. */ 6640 if (pt->escaped 6641 && pt_solution_includes_1 (&cfun->gimple_df->escaped, decl)) 6642 return true; 6643 6644 /* If the solution includes ESCAPED, check it. */ 6645 if (pt->ipa_escaped 6646 && pt_solution_includes_1 (&ipa_escaped_pt, decl)) 6647 return true; 6648 6649 return false; 6650 } 6651 6652 bool 6653 pt_solution_includes (struct pt_solution *pt, const_tree decl) 6654 { 6655 bool res = pt_solution_includes_1 (pt, decl); 6656 if (res) 6657 ++pta_stats.pt_solution_includes_may_alias; 6658 else 6659 ++pta_stats.pt_solution_includes_no_alias; 6660 return res; 6661 } 6662 6663 /* Return true if both points-to solutions PT1 and PT2 have a non-empty 6664 intersection. */ 6665 6666 static bool 6667 pt_solutions_intersect_1 (struct pt_solution *pt1, struct pt_solution *pt2) 6668 { 6669 if (pt1->anything || pt2->anything) 6670 return true; 6671 6672 /* If either points to unknown global memory and the other points to 6673 any global memory they alias. */ 6674 if ((pt1->nonlocal 6675 && (pt2->nonlocal 6676 || pt2->vars_contains_nonlocal)) 6677 || (pt2->nonlocal 6678 && pt1->vars_contains_nonlocal)) 6679 return true; 6680 6681 /* If either points to all escaped memory and the other points to 6682 any escaped memory they alias. */ 6683 if ((pt1->escaped 6684 && (pt2->escaped 6685 || pt2->vars_contains_escaped)) 6686 || (pt2->escaped 6687 && pt1->vars_contains_escaped)) 6688 return true; 6689 6690 /* Check the escaped solution if required. 6691 ??? Do we need to check the local against the IPA escaped sets? */ 6692 if ((pt1->ipa_escaped || pt2->ipa_escaped) 6693 && !pt_solution_empty_p (&ipa_escaped_pt)) 6694 { 6695 /* If both point to escaped memory and that solution 6696 is not empty they alias. */ 6697 if (pt1->ipa_escaped && pt2->ipa_escaped) 6698 return true; 6699 6700 /* If either points to escaped memory see if the escaped solution 6701 intersects with the other. */ 6702 if ((pt1->ipa_escaped 6703 && pt_solutions_intersect_1 (&ipa_escaped_pt, pt2)) 6704 || (pt2->ipa_escaped 6705 && pt_solutions_intersect_1 (&ipa_escaped_pt, pt1))) 6706 return true; 6707 } 6708 6709 /* Now both pointers alias if their points-to solution intersects. */ 6710 return (pt1->vars 6711 && pt2->vars 6712 && bitmap_intersect_p (pt1->vars, pt2->vars)); 6713 } 6714 6715 bool 6716 pt_solutions_intersect (struct pt_solution *pt1, struct pt_solution *pt2) 6717 { 6718 bool res = pt_solutions_intersect_1 (pt1, pt2); 6719 if (res) 6720 ++pta_stats.pt_solutions_intersect_may_alias; 6721 else 6722 ++pta_stats.pt_solutions_intersect_no_alias; 6723 return res; 6724 } 6725 6726 6727 /* Dump points-to information to OUTFILE. */ 6728 6729 static void 6730 dump_sa_points_to_info (FILE *outfile) 6731 { 6732 unsigned int i; 6733 6734 fprintf (outfile, "\nPoints-to sets\n\n"); 6735 6736 if (dump_flags & TDF_STATS) 6737 { 6738 fprintf (outfile, "Stats:\n"); 6739 fprintf (outfile, "Total vars: %d\n", stats.total_vars); 6740 fprintf (outfile, "Non-pointer vars: %d\n", 6741 stats.nonpointer_vars); 6742 fprintf (outfile, "Statically unified vars: %d\n", 6743 stats.unified_vars_static); 6744 fprintf (outfile, "Dynamically unified vars: %d\n", 6745 stats.unified_vars_dynamic); 6746 fprintf (outfile, "Iterations: %d\n", stats.iterations); 6747 fprintf (outfile, "Number of edges: %d\n", stats.num_edges); 6748 fprintf (outfile, "Number of implicit edges: %d\n", 6749 stats.num_implicit_edges); 6750 } 6751 6752 for (i = 1; i < varmap.length (); i++) 6753 { 6754 varinfo_t vi = get_varinfo (i); 6755 if (!vi->may_have_pointers) 6756 continue; 6757 dump_solution_for_var (outfile, i); 6758 } 6759 } 6760 6761 6762 /* Debug points-to information to stderr. */ 6763 6764 DEBUG_FUNCTION void 6765 debug_sa_points_to_info (void) 6766 { 6767 dump_sa_points_to_info (stderr); 6768 } 6769 6770 6771 /* Initialize the always-existing constraint variables for NULL 6772 ANYTHING, READONLY, and INTEGER */ 6773 6774 static void 6775 init_base_vars (void) 6776 { 6777 struct constraint_expr lhs, rhs; 6778 varinfo_t var_anything; 6779 varinfo_t var_nothing; 6780 varinfo_t var_string; 6781 varinfo_t var_escaped; 6782 varinfo_t var_nonlocal; 6783 varinfo_t var_storedanything; 6784 varinfo_t var_integer; 6785 6786 /* Variable ID zero is reserved and should be NULL. */ 6787 varmap.safe_push (NULL); 6788 6789 /* Create the NULL variable, used to represent that a variable points 6790 to NULL. */ 6791 var_nothing = new_var_info (NULL_TREE, "NULL", false); 6792 gcc_assert (var_nothing->id == nothing_id); 6793 var_nothing->is_artificial_var = 1; 6794 var_nothing->offset = 0; 6795 var_nothing->size = ~0; 6796 var_nothing->fullsize = ~0; 6797 var_nothing->is_special_var = 1; 6798 var_nothing->may_have_pointers = 0; 6799 var_nothing->is_global_var = 0; 6800 6801 /* Create the ANYTHING variable, used to represent that a variable 6802 points to some unknown piece of memory. */ 6803 var_anything = new_var_info (NULL_TREE, "ANYTHING", false); 6804 gcc_assert (var_anything->id == anything_id); 6805 var_anything->is_artificial_var = 1; 6806 var_anything->size = ~0; 6807 var_anything->offset = 0; 6808 var_anything->fullsize = ~0; 6809 var_anything->is_special_var = 1; 6810 6811 /* Anything points to anything. This makes deref constraints just 6812 work in the presence of linked list and other p = *p type loops, 6813 by saying that *ANYTHING = ANYTHING. */ 6814 lhs.type = SCALAR; 6815 lhs.var = anything_id; 6816 lhs.offset = 0; 6817 rhs.type = ADDRESSOF; 6818 rhs.var = anything_id; 6819 rhs.offset = 0; 6820 6821 /* This specifically does not use process_constraint because 6822 process_constraint ignores all anything = anything constraints, since all 6823 but this one are redundant. */ 6824 constraints.safe_push (new_constraint (lhs, rhs)); 6825 6826 /* Create the STRING variable, used to represent that a variable 6827 points to a string literal. String literals don't contain 6828 pointers so STRING doesn't point to anything. */ 6829 var_string = new_var_info (NULL_TREE, "STRING", false); 6830 gcc_assert (var_string->id == string_id); 6831 var_string->is_artificial_var = 1; 6832 var_string->offset = 0; 6833 var_string->size = ~0; 6834 var_string->fullsize = ~0; 6835 var_string->is_special_var = 1; 6836 var_string->may_have_pointers = 0; 6837 6838 /* Create the ESCAPED variable, used to represent the set of escaped 6839 memory. */ 6840 var_escaped = new_var_info (NULL_TREE, "ESCAPED", false); 6841 gcc_assert (var_escaped->id == escaped_id); 6842 var_escaped->is_artificial_var = 1; 6843 var_escaped->offset = 0; 6844 var_escaped->size = ~0; 6845 var_escaped->fullsize = ~0; 6846 var_escaped->is_special_var = 0; 6847 6848 /* Create the NONLOCAL variable, used to represent the set of nonlocal 6849 memory. */ 6850 var_nonlocal = new_var_info (NULL_TREE, "NONLOCAL", false); 6851 gcc_assert (var_nonlocal->id == nonlocal_id); 6852 var_nonlocal->is_artificial_var = 1; 6853 var_nonlocal->offset = 0; 6854 var_nonlocal->size = ~0; 6855 var_nonlocal->fullsize = ~0; 6856 var_nonlocal->is_special_var = 1; 6857 6858 /* ESCAPED = *ESCAPED, because escaped is may-deref'd at calls, etc. */ 6859 lhs.type = SCALAR; 6860 lhs.var = escaped_id; 6861 lhs.offset = 0; 6862 rhs.type = DEREF; 6863 rhs.var = escaped_id; 6864 rhs.offset = 0; 6865 process_constraint (new_constraint (lhs, rhs)); 6866 6867 /* ESCAPED = ESCAPED + UNKNOWN_OFFSET, because if a sub-field escapes the 6868 whole variable escapes. */ 6869 lhs.type = SCALAR; 6870 lhs.var = escaped_id; 6871 lhs.offset = 0; 6872 rhs.type = SCALAR; 6873 rhs.var = escaped_id; 6874 rhs.offset = UNKNOWN_OFFSET; 6875 process_constraint (new_constraint (lhs, rhs)); 6876 6877 /* *ESCAPED = NONLOCAL. This is true because we have to assume 6878 everything pointed to by escaped points to what global memory can 6879 point to. */ 6880 lhs.type = DEREF; 6881 lhs.var = escaped_id; 6882 lhs.offset = 0; 6883 rhs.type = SCALAR; 6884 rhs.var = nonlocal_id; 6885 rhs.offset = 0; 6886 process_constraint (new_constraint (lhs, rhs)); 6887 6888 /* NONLOCAL = &NONLOCAL, NONLOCAL = &ESCAPED. This is true because 6889 global memory may point to global memory and escaped memory. */ 6890 lhs.type = SCALAR; 6891 lhs.var = nonlocal_id; 6892 lhs.offset = 0; 6893 rhs.type = ADDRESSOF; 6894 rhs.var = nonlocal_id; 6895 rhs.offset = 0; 6896 process_constraint (new_constraint (lhs, rhs)); 6897 rhs.type = ADDRESSOF; 6898 rhs.var = escaped_id; 6899 rhs.offset = 0; 6900 process_constraint (new_constraint (lhs, rhs)); 6901 6902 /* Create the STOREDANYTHING variable, used to represent the set of 6903 variables stored to *ANYTHING. */ 6904 var_storedanything = new_var_info (NULL_TREE, "STOREDANYTHING", false); 6905 gcc_assert (var_storedanything->id == storedanything_id); 6906 var_storedanything->is_artificial_var = 1; 6907 var_storedanything->offset = 0; 6908 var_storedanything->size = ~0; 6909 var_storedanything->fullsize = ~0; 6910 var_storedanything->is_special_var = 0; 6911 6912 /* Create the INTEGER variable, used to represent that a variable points 6913 to what an INTEGER "points to". */ 6914 var_integer = new_var_info (NULL_TREE, "INTEGER", false); 6915 gcc_assert (var_integer->id == integer_id); 6916 var_integer->is_artificial_var = 1; 6917 var_integer->size = ~0; 6918 var_integer->fullsize = ~0; 6919 var_integer->offset = 0; 6920 var_integer->is_special_var = 1; 6921 6922 /* INTEGER = ANYTHING, because we don't know where a dereference of 6923 a random integer will point to. */ 6924 lhs.type = SCALAR; 6925 lhs.var = integer_id; 6926 lhs.offset = 0; 6927 rhs.type = ADDRESSOF; 6928 rhs.var = anything_id; 6929 rhs.offset = 0; 6930 process_constraint (new_constraint (lhs, rhs)); 6931 } 6932 6933 /* Initialize things necessary to perform PTA */ 6934 6935 static void 6936 init_alias_vars (void) 6937 { 6938 use_field_sensitive = (MAX_FIELDS_FOR_FIELD_SENSITIVE > 1); 6939 6940 bitmap_obstack_initialize (&pta_obstack); 6941 bitmap_obstack_initialize (&oldpta_obstack); 6942 bitmap_obstack_initialize (&predbitmap_obstack); 6943 6944 constraints.create (8); 6945 varmap.create (8); 6946 vi_for_tree = new hash_map<tree, varinfo_t>; 6947 call_stmt_vars = new hash_map<gimple *, varinfo_t>; 6948 6949 memset (&stats, 0, sizeof (stats)); 6950 shared_bitmap_table = new hash_table<shared_bitmap_hasher> (511); 6951 init_base_vars (); 6952 6953 gcc_obstack_init (&fake_var_decl_obstack); 6954 6955 final_solutions = new hash_map<varinfo_t, pt_solution *>; 6956 gcc_obstack_init (&final_solutions_obstack); 6957 } 6958 6959 /* Remove the REF and ADDRESS edges from GRAPH, as well as all the 6960 predecessor edges. */ 6961 6962 static void 6963 remove_preds_and_fake_succs (constraint_graph_t graph) 6964 { 6965 unsigned int i; 6966 6967 /* Clear the implicit ref and address nodes from the successor 6968 lists. */ 6969 for (i = 1; i < FIRST_REF_NODE; i++) 6970 { 6971 if (graph->succs[i]) 6972 bitmap_clear_range (graph->succs[i], FIRST_REF_NODE, 6973 FIRST_REF_NODE * 2); 6974 } 6975 6976 /* Free the successor list for the non-ref nodes. */ 6977 for (i = FIRST_REF_NODE + 1; i < graph->size; i++) 6978 { 6979 if (graph->succs[i]) 6980 BITMAP_FREE (graph->succs[i]); 6981 } 6982 6983 /* Now reallocate the size of the successor list as, and blow away 6984 the predecessor bitmaps. */ 6985 graph->size = varmap.length (); 6986 graph->succs = XRESIZEVEC (bitmap, graph->succs, graph->size); 6987 6988 free (graph->implicit_preds); 6989 graph->implicit_preds = NULL; 6990 free (graph->preds); 6991 graph->preds = NULL; 6992 bitmap_obstack_release (&predbitmap_obstack); 6993 } 6994 6995 /* Solve the constraint set. */ 6996 6997 static void 6998 solve_constraints (void) 6999 { 7000 struct scc_info *si; 7001 7002 if (dump_file) 7003 fprintf (dump_file, 7004 "\nCollapsing static cycles and doing variable " 7005 "substitution\n"); 7006 7007 init_graph (varmap.length () * 2); 7008 7009 if (dump_file) 7010 fprintf (dump_file, "Building predecessor graph\n"); 7011 build_pred_graph (); 7012 7013 if (dump_file) 7014 fprintf (dump_file, "Detecting pointer and location " 7015 "equivalences\n"); 7016 si = perform_var_substitution (graph); 7017 7018 if (dump_file) 7019 fprintf (dump_file, "Rewriting constraints and unifying " 7020 "variables\n"); 7021 rewrite_constraints (graph, si); 7022 7023 build_succ_graph (); 7024 7025 free_var_substitution_info (si); 7026 7027 /* Attach complex constraints to graph nodes. */ 7028 move_complex_constraints (graph); 7029 7030 if (dump_file) 7031 fprintf (dump_file, "Uniting pointer but not location equivalent " 7032 "variables\n"); 7033 unite_pointer_equivalences (graph); 7034 7035 if (dump_file) 7036 fprintf (dump_file, "Finding indirect cycles\n"); 7037 find_indirect_cycles (graph); 7038 7039 /* Implicit nodes and predecessors are no longer necessary at this 7040 point. */ 7041 remove_preds_and_fake_succs (graph); 7042 7043 if (dump_file && (dump_flags & TDF_GRAPH)) 7044 { 7045 fprintf (dump_file, "\n\n// The constraint graph before solve-graph " 7046 "in dot format:\n"); 7047 dump_constraint_graph (dump_file); 7048 fprintf (dump_file, "\n\n"); 7049 } 7050 7051 if (dump_file) 7052 fprintf (dump_file, "Solving graph\n"); 7053 7054 solve_graph (graph); 7055 7056 if (dump_file && (dump_flags & TDF_GRAPH)) 7057 { 7058 fprintf (dump_file, "\n\n// The constraint graph after solve-graph " 7059 "in dot format:\n"); 7060 dump_constraint_graph (dump_file); 7061 fprintf (dump_file, "\n\n"); 7062 } 7063 7064 if (dump_file) 7065 dump_sa_points_to_info (dump_file); 7066 } 7067 7068 /* Create points-to sets for the current function. See the comments 7069 at the start of the file for an algorithmic overview. */ 7070 7071 static void 7072 compute_points_to_sets (void) 7073 { 7074 basic_block bb; 7075 unsigned i; 7076 varinfo_t vi; 7077 7078 timevar_push (TV_TREE_PTA); 7079 7080 init_alias_vars (); 7081 7082 intra_create_variable_infos (cfun); 7083 7084 /* Now walk all statements and build the constraint set. */ 7085 FOR_EACH_BB_FN (bb, cfun) 7086 { 7087 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); 7088 gsi_next (&gsi)) 7089 { 7090 gphi *phi = gsi.phi (); 7091 7092 if (! virtual_operand_p (gimple_phi_result (phi))) 7093 find_func_aliases (cfun, phi); 7094 } 7095 7096 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); 7097 gsi_next (&gsi)) 7098 { 7099 gimple *stmt = gsi_stmt (gsi); 7100 7101 find_func_aliases (cfun, stmt); 7102 } 7103 } 7104 7105 if (dump_file) 7106 { 7107 fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n"); 7108 dump_constraints (dump_file, 0); 7109 } 7110 7111 /* From the constraints compute the points-to sets. */ 7112 solve_constraints (); 7113 7114 /* Compute the points-to set for ESCAPED used for call-clobber analysis. */ 7115 cfun->gimple_df->escaped = find_what_var_points_to (cfun->decl, 7116 get_varinfo (escaped_id)); 7117 7118 /* Make sure the ESCAPED solution (which is used as placeholder in 7119 other solutions) does not reference itself. This simplifies 7120 points-to solution queries. */ 7121 cfun->gimple_df->escaped.escaped = 0; 7122 7123 /* Compute the points-to sets for pointer SSA_NAMEs. */ 7124 for (i = 0; i < num_ssa_names; ++i) 7125 { 7126 tree ptr = ssa_name (i); 7127 if (ptr 7128 && POINTER_TYPE_P (TREE_TYPE (ptr))) 7129 find_what_p_points_to (cfun->decl, ptr); 7130 } 7131 7132 /* Compute the call-used/clobbered sets. */ 7133 FOR_EACH_BB_FN (bb, cfun) 7134 { 7135 gimple_stmt_iterator gsi; 7136 7137 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 7138 { 7139 gcall *stmt; 7140 struct pt_solution *pt; 7141 7142 stmt = dyn_cast <gcall *> (gsi_stmt (gsi)); 7143 if (!stmt) 7144 continue; 7145 7146 pt = gimple_call_use_set (stmt); 7147 if (gimple_call_flags (stmt) & ECF_CONST) 7148 memset (pt, 0, sizeof (struct pt_solution)); 7149 else if ((vi = lookup_call_use_vi (stmt)) != NULL) 7150 { 7151 *pt = find_what_var_points_to (cfun->decl, vi); 7152 /* Escaped (and thus nonlocal) variables are always 7153 implicitly used by calls. */ 7154 /* ??? ESCAPED can be empty even though NONLOCAL 7155 always escaped. */ 7156 pt->nonlocal = 1; 7157 pt->escaped = 1; 7158 } 7159 else 7160 { 7161 /* If there is nothing special about this call then 7162 we have made everything that is used also escape. */ 7163 *pt = cfun->gimple_df->escaped; 7164 pt->nonlocal = 1; 7165 } 7166 7167 pt = gimple_call_clobber_set (stmt); 7168 if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS)) 7169 memset (pt, 0, sizeof (struct pt_solution)); 7170 else if ((vi = lookup_call_clobber_vi (stmt)) != NULL) 7171 { 7172 *pt = find_what_var_points_to (cfun->decl, vi); 7173 /* Escaped (and thus nonlocal) variables are always 7174 implicitly clobbered by calls. */ 7175 /* ??? ESCAPED can be empty even though NONLOCAL 7176 always escaped. */ 7177 pt->nonlocal = 1; 7178 pt->escaped = 1; 7179 } 7180 else 7181 { 7182 /* If there is nothing special about this call then 7183 we have made everything that is used also escape. */ 7184 *pt = cfun->gimple_df->escaped; 7185 pt->nonlocal = 1; 7186 } 7187 } 7188 } 7189 7190 timevar_pop (TV_TREE_PTA); 7191 } 7192 7193 7194 /* Delete created points-to sets. */ 7195 7196 static void 7197 delete_points_to_sets (void) 7198 { 7199 unsigned int i; 7200 7201 delete shared_bitmap_table; 7202 shared_bitmap_table = NULL; 7203 if (dump_file && (dump_flags & TDF_STATS)) 7204 fprintf (dump_file, "Points to sets created:%d\n", 7205 stats.points_to_sets_created); 7206 7207 delete vi_for_tree; 7208 delete call_stmt_vars; 7209 bitmap_obstack_release (&pta_obstack); 7210 constraints.release (); 7211 7212 for (i = 0; i < graph->size; i++) 7213 graph->complex[i].release (); 7214 free (graph->complex); 7215 7216 free (graph->rep); 7217 free (graph->succs); 7218 free (graph->pe); 7219 free (graph->pe_rep); 7220 free (graph->indirect_cycles); 7221 free (graph); 7222 7223 varmap.release (); 7224 variable_info_pool.release (); 7225 constraint_pool.release (); 7226 7227 obstack_free (&fake_var_decl_obstack, NULL); 7228 7229 delete final_solutions; 7230 obstack_free (&final_solutions_obstack, NULL); 7231 } 7232 7233 struct vls_data 7234 { 7235 unsigned short clique; 7236 bitmap rvars; 7237 }; 7238 7239 /* Mark "other" loads and stores as belonging to CLIQUE and with 7240 base zero. */ 7241 7242 static bool 7243 visit_loadstore (gimple *, tree base, tree ref, void *data) 7244 { 7245 unsigned short clique = ((vls_data *) data)->clique; 7246 bitmap rvars = ((vls_data *) data)->rvars; 7247 if (TREE_CODE (base) == MEM_REF 7248 || TREE_CODE (base) == TARGET_MEM_REF) 7249 { 7250 tree ptr = TREE_OPERAND (base, 0); 7251 if (TREE_CODE (ptr) == SSA_NAME) 7252 { 7253 /* For parameters, get at the points-to set for the actual parm 7254 decl. */ 7255 if (SSA_NAME_IS_DEFAULT_DEF (ptr) 7256 && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL 7257 || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL)) 7258 ptr = SSA_NAME_VAR (ptr); 7259 7260 /* We need to make sure 'ptr' doesn't include any of 7261 the restrict tags we added bases for in its points-to set. */ 7262 varinfo_t vi = lookup_vi_for_tree (ptr); 7263 if (! vi) 7264 return false; 7265 7266 vi = get_varinfo (find (vi->id)); 7267 if (bitmap_intersect_p (rvars, vi->solution)) 7268 return false; 7269 } 7270 7271 /* Do not overwrite existing cliques (that includes clique, base 7272 pairs we just set). */ 7273 if (MR_DEPENDENCE_CLIQUE (base) == 0) 7274 { 7275 MR_DEPENDENCE_CLIQUE (base) = clique; 7276 MR_DEPENDENCE_BASE (base) = 0; 7277 } 7278 } 7279 7280 /* For plain decl accesses see whether they are accesses to globals 7281 and rewrite them to MEM_REFs with { clique, 0 }. */ 7282 if (TREE_CODE (base) == VAR_DECL 7283 && is_global_var (base) 7284 /* ??? We can't rewrite a plain decl with the walk_stmt_load_store 7285 ops callback. */ 7286 && base != ref) 7287 { 7288 tree *basep = &ref; 7289 while (handled_component_p (*basep)) 7290 basep = &TREE_OPERAND (*basep, 0); 7291 gcc_assert (TREE_CODE (*basep) == VAR_DECL); 7292 tree ptr = build_fold_addr_expr (*basep); 7293 tree zero = build_int_cst (TREE_TYPE (ptr), 0); 7294 *basep = build2 (MEM_REF, TREE_TYPE (*basep), ptr, zero); 7295 MR_DEPENDENCE_CLIQUE (*basep) = clique; 7296 MR_DEPENDENCE_BASE (*basep) = 0; 7297 } 7298 7299 return false; 7300 } 7301 7302 /* If REF is a MEM_REF then assign a clique, base pair to it, updating 7303 CLIQUE, *RESTRICT_VAR and LAST_RUID. Return whether dependence info 7304 was assigned to REF. */ 7305 7306 static bool 7307 maybe_set_dependence_info (tree ref, tree ptr, 7308 unsigned short &clique, varinfo_t restrict_var, 7309 unsigned short &last_ruid) 7310 { 7311 while (handled_component_p (ref)) 7312 ref = TREE_OPERAND (ref, 0); 7313 if ((TREE_CODE (ref) == MEM_REF 7314 || TREE_CODE (ref) == TARGET_MEM_REF) 7315 && TREE_OPERAND (ref, 0) == ptr) 7316 { 7317 /* Do not overwrite existing cliques. This avoids overwriting dependence 7318 info inlined from a function with restrict parameters inlined 7319 into a function with restrict parameters. This usually means we 7320 prefer to be precise in innermost loops. */ 7321 if (MR_DEPENDENCE_CLIQUE (ref) == 0) 7322 { 7323 if (clique == 0) 7324 clique = ++cfun->last_clique; 7325 if (restrict_var->ruid == 0) 7326 restrict_var->ruid = ++last_ruid; 7327 MR_DEPENDENCE_CLIQUE (ref) = clique; 7328 MR_DEPENDENCE_BASE (ref) = restrict_var->ruid; 7329 return true; 7330 } 7331 } 7332 return false; 7333 } 7334 7335 /* Compute the set of independend memory references based on restrict 7336 tags and their conservative propagation to the points-to sets. */ 7337 7338 static void 7339 compute_dependence_clique (void) 7340 { 7341 unsigned short clique = 0; 7342 unsigned short last_ruid = 0; 7343 bitmap rvars = BITMAP_ALLOC (NULL); 7344 for (unsigned i = 0; i < num_ssa_names; ++i) 7345 { 7346 tree ptr = ssa_name (i); 7347 if (!ptr || !POINTER_TYPE_P (TREE_TYPE (ptr))) 7348 continue; 7349 7350 /* Avoid all this when ptr is not dereferenced? */ 7351 tree p = ptr; 7352 if (SSA_NAME_IS_DEFAULT_DEF (ptr) 7353 && (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL 7354 || TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL)) 7355 p = SSA_NAME_VAR (ptr); 7356 varinfo_t vi = lookup_vi_for_tree (p); 7357 if (!vi) 7358 continue; 7359 vi = get_varinfo (find (vi->id)); 7360 bitmap_iterator bi; 7361 unsigned j; 7362 varinfo_t restrict_var = NULL; 7363 EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, j, bi) 7364 { 7365 varinfo_t oi = get_varinfo (j); 7366 if (oi->is_restrict_var) 7367 { 7368 if (restrict_var) 7369 { 7370 if (dump_file && (dump_flags & TDF_DETAILS)) 7371 { 7372 fprintf (dump_file, "found restrict pointed-to " 7373 "for "); 7374 print_generic_expr (dump_file, ptr, 0); 7375 fprintf (dump_file, " but not exclusively\n"); 7376 } 7377 restrict_var = NULL; 7378 break; 7379 } 7380 restrict_var = oi; 7381 } 7382 /* NULL is the only other valid points-to entry. */ 7383 else if (oi->id != nothing_id) 7384 { 7385 restrict_var = NULL; 7386 break; 7387 } 7388 } 7389 /* Ok, found that ptr must(!) point to a single(!) restrict 7390 variable. */ 7391 /* ??? PTA isn't really a proper propagation engine to compute 7392 this property. 7393 ??? We could handle merging of two restricts by unifying them. */ 7394 if (restrict_var) 7395 { 7396 /* Now look at possible dereferences of ptr. */ 7397 imm_use_iterator ui; 7398 gimple *use_stmt; 7399 bool used = false; 7400 FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr) 7401 { 7402 /* ??? Calls and asms. */ 7403 if (!gimple_assign_single_p (use_stmt)) 7404 continue; 7405 used |= maybe_set_dependence_info (gimple_assign_lhs (use_stmt), 7406 ptr, clique, restrict_var, 7407 last_ruid); 7408 used |= maybe_set_dependence_info (gimple_assign_rhs1 (use_stmt), 7409 ptr, clique, restrict_var, 7410 last_ruid); 7411 } 7412 if (used) 7413 bitmap_set_bit (rvars, restrict_var->id); 7414 } 7415 } 7416 7417 if (clique != 0) 7418 { 7419 /* Assign the BASE id zero to all accesses not based on a restrict 7420 pointer. That way they get disambiguated against restrict 7421 accesses but not against each other. */ 7422 /* ??? For restricts derived from globals (thus not incoming 7423 parameters) we can't restrict scoping properly thus the following 7424 is too aggressive there. For now we have excluded those globals from 7425 getting into the MR_DEPENDENCE machinery. */ 7426 vls_data data = { clique, rvars }; 7427 basic_block bb; 7428 FOR_EACH_BB_FN (bb, cfun) 7429 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); 7430 !gsi_end_p (gsi); gsi_next (&gsi)) 7431 { 7432 gimple *stmt = gsi_stmt (gsi); 7433 walk_stmt_load_store_ops (stmt, &data, 7434 visit_loadstore, visit_loadstore); 7435 } 7436 } 7437 7438 BITMAP_FREE (rvars); 7439 } 7440 7441 /* Compute points-to information for every SSA_NAME pointer in the 7442 current function and compute the transitive closure of escaped 7443 variables to re-initialize the call-clobber states of local variables. */ 7444 7445 unsigned int 7446 compute_may_aliases (void) 7447 { 7448 if (cfun->gimple_df->ipa_pta) 7449 { 7450 if (dump_file) 7451 { 7452 fprintf (dump_file, "\nNot re-computing points-to information " 7453 "because IPA points-to information is available.\n\n"); 7454 7455 /* But still dump what we have remaining it. */ 7456 dump_alias_info (dump_file); 7457 } 7458 7459 return 0; 7460 } 7461 7462 /* For each pointer P_i, determine the sets of variables that P_i may 7463 point-to. Compute the reachability set of escaped and call-used 7464 variables. */ 7465 compute_points_to_sets (); 7466 7467 /* Debugging dumps. */ 7468 if (dump_file) 7469 dump_alias_info (dump_file); 7470 7471 /* Compute restrict-based memory disambiguations. */ 7472 compute_dependence_clique (); 7473 7474 /* Deallocate memory used by aliasing data structures and the internal 7475 points-to solution. */ 7476 delete_points_to_sets (); 7477 7478 gcc_assert (!need_ssa_update_p (cfun)); 7479 7480 return 0; 7481 } 7482 7483 /* A dummy pass to cause points-to information to be computed via 7484 TODO_rebuild_alias. */ 7485 7486 namespace { 7487 7488 const pass_data pass_data_build_alias = 7489 { 7490 GIMPLE_PASS, /* type */ 7491 "alias", /* name */ 7492 OPTGROUP_NONE, /* optinfo_flags */ 7493 TV_NONE, /* tv_id */ 7494 ( PROP_cfg | PROP_ssa ), /* properties_required */ 7495 0, /* properties_provided */ 7496 0, /* properties_destroyed */ 7497 0, /* todo_flags_start */ 7498 TODO_rebuild_alias, /* todo_flags_finish */ 7499 }; 7500 7501 class pass_build_alias : public gimple_opt_pass 7502 { 7503 public: 7504 pass_build_alias (gcc::context *ctxt) 7505 : gimple_opt_pass (pass_data_build_alias, ctxt) 7506 {} 7507 7508 /* opt_pass methods: */ 7509 virtual bool gate (function *) { return flag_tree_pta; } 7510 7511 }; // class pass_build_alias 7512 7513 } // anon namespace 7514 7515 gimple_opt_pass * 7516 make_pass_build_alias (gcc::context *ctxt) 7517 { 7518 return new pass_build_alias (ctxt); 7519 } 7520 7521 /* A dummy pass to cause points-to information to be computed via 7522 TODO_rebuild_alias. */ 7523 7524 namespace { 7525 7526 const pass_data pass_data_build_ealias = 7527 { 7528 GIMPLE_PASS, /* type */ 7529 "ealias", /* name */ 7530 OPTGROUP_NONE, /* optinfo_flags */ 7531 TV_NONE, /* tv_id */ 7532 ( PROP_cfg | PROP_ssa ), /* properties_required */ 7533 0, /* properties_provided */ 7534 0, /* properties_destroyed */ 7535 0, /* todo_flags_start */ 7536 TODO_rebuild_alias, /* todo_flags_finish */ 7537 }; 7538 7539 class pass_build_ealias : public gimple_opt_pass 7540 { 7541 public: 7542 pass_build_ealias (gcc::context *ctxt) 7543 : gimple_opt_pass (pass_data_build_ealias, ctxt) 7544 {} 7545 7546 /* opt_pass methods: */ 7547 virtual bool gate (function *) { return flag_tree_pta; } 7548 7549 }; // class pass_build_ealias 7550 7551 } // anon namespace 7552 7553 gimple_opt_pass * 7554 make_pass_build_ealias (gcc::context *ctxt) 7555 { 7556 return new pass_build_ealias (ctxt); 7557 } 7558 7559 7560 /* IPA PTA solutions for ESCAPED. */ 7561 struct pt_solution ipa_escaped_pt 7562 = { true, false, false, false, false, false, false, false, NULL }; 7563 7564 /* Associate node with varinfo DATA. Worker for 7565 cgraph_for_symbol_thunks_and_aliases. */ 7566 static bool 7567 associate_varinfo_to_alias (struct cgraph_node *node, void *data) 7568 { 7569 if ((node->alias || node->thunk.thunk_p) 7570 && node->analyzed) 7571 insert_vi_for_tree (node->decl, (varinfo_t)data); 7572 return false; 7573 } 7574 7575 /* Compute whether node is refered to non-locally. Worker for 7576 cgraph_for_symbol_thunks_and_aliases. */ 7577 static bool 7578 refered_from_nonlocal_fn (struct cgraph_node *node, void *data) 7579 { 7580 bool *nonlocal_p = (bool *)data; 7581 *nonlocal_p |= (node->used_from_other_partition 7582 || node->externally_visible 7583 || node->force_output); 7584 return false; 7585 } 7586 7587 /* Same for varpool nodes. */ 7588 static bool 7589 refered_from_nonlocal_var (struct varpool_node *node, void *data) 7590 { 7591 bool *nonlocal_p = (bool *)data; 7592 *nonlocal_p |= (node->used_from_other_partition 7593 || node->externally_visible 7594 || node->force_output); 7595 return false; 7596 } 7597 7598 /* Execute the driver for IPA PTA. */ 7599 static unsigned int 7600 ipa_pta_execute (void) 7601 { 7602 struct cgraph_node *node; 7603 varpool_node *var; 7604 unsigned int from = 0; 7605 7606 in_ipa_mode = 1; 7607 7608 init_alias_vars (); 7609 7610 if (dump_file && (dump_flags & TDF_DETAILS)) 7611 { 7612 symtab_node::dump_table (dump_file); 7613 fprintf (dump_file, "\n"); 7614 } 7615 7616 if (dump_file) 7617 { 7618 fprintf (dump_file, "Generating generic constraints\n\n"); 7619 dump_constraints (dump_file, from); 7620 fprintf (dump_file, "\n"); 7621 from = constraints.length (); 7622 } 7623 7624 /* Build the constraints. */ 7625 FOR_EACH_DEFINED_FUNCTION (node) 7626 { 7627 varinfo_t vi; 7628 /* Nodes without a body are not interesting. Especially do not 7629 visit clones at this point for now - we get duplicate decls 7630 there for inline clones at least. */ 7631 if (!node->has_gimple_body_p () || node->global.inlined_to) 7632 continue; 7633 node->get_body (); 7634 7635 gcc_assert (!node->clone_of); 7636 7637 /* When parallelizing a code region, we split the region off into a 7638 separate function, to be run by several threads in parallel. So for a 7639 function foo, we split off a region into a function 7640 foo._0 (void *foodata), and replace the region with some variant of a 7641 function call run_on_threads (&foo._0, data). The '&foo._0' sets the 7642 address_taken bit for function foo._0, which would make it non-local. 7643 But for the purpose of ipa-pta, we can regard the run_on_threads call 7644 as a local call foo._0 (data), so we ignore address_taken on nodes 7645 with parallelized_function set. 7646 Note: this is only safe, if foo and foo._0 are in the same lto 7647 partition. */ 7648 bool node_address_taken = ((node->parallelized_function 7649 && !node->used_from_other_partition) 7650 ? false 7651 : node->address_taken); 7652 7653 /* For externally visible or attribute used annotated functions use 7654 local constraints for their arguments. 7655 For local functions we see all callers and thus do not need initial 7656 constraints for parameters. */ 7657 bool nonlocal_p = (node->used_from_other_partition 7658 || node->externally_visible 7659 || node->force_output 7660 || node_address_taken); 7661 node->call_for_symbol_thunks_and_aliases (refered_from_nonlocal_fn, 7662 &nonlocal_p, true); 7663 7664 vi = create_function_info_for (node->decl, 7665 alias_get_name (node->decl), false, 7666 nonlocal_p); 7667 if (dump_file 7668 && from != constraints.length ()) 7669 { 7670 fprintf (dump_file, 7671 "Generating intial constraints for %s", node->name ()); 7672 if (DECL_ASSEMBLER_NAME_SET_P (node->decl)) 7673 fprintf (dump_file, " (%s)", 7674 IDENTIFIER_POINTER 7675 (DECL_ASSEMBLER_NAME (node->decl))); 7676 fprintf (dump_file, "\n\n"); 7677 dump_constraints (dump_file, from); 7678 fprintf (dump_file, "\n"); 7679 7680 from = constraints.length (); 7681 } 7682 7683 node->call_for_symbol_thunks_and_aliases 7684 (associate_varinfo_to_alias, vi, true); 7685 } 7686 7687 /* Create constraints for global variables and their initializers. */ 7688 FOR_EACH_VARIABLE (var) 7689 { 7690 if (var->alias && var->analyzed) 7691 continue; 7692 7693 varinfo_t vi = get_vi_for_tree (var->decl); 7694 7695 /* For the purpose of IPA PTA unit-local globals are not 7696 escape points. */ 7697 bool nonlocal_p = (var->used_from_other_partition 7698 || var->externally_visible 7699 || var->force_output); 7700 var->call_for_symbol_and_aliases (refered_from_nonlocal_var, 7701 &nonlocal_p, true); 7702 if (nonlocal_p) 7703 vi->is_ipa_escape_point = true; 7704 } 7705 7706 if (dump_file 7707 && from != constraints.length ()) 7708 { 7709 fprintf (dump_file, 7710 "Generating constraints for global initializers\n\n"); 7711 dump_constraints (dump_file, from); 7712 fprintf (dump_file, "\n"); 7713 from = constraints.length (); 7714 } 7715 7716 FOR_EACH_DEFINED_FUNCTION (node) 7717 { 7718 struct function *func; 7719 basic_block bb; 7720 7721 /* Nodes without a body are not interesting. */ 7722 if (!node->has_gimple_body_p () || node->clone_of) 7723 continue; 7724 7725 if (dump_file) 7726 { 7727 fprintf (dump_file, 7728 "Generating constraints for %s", node->name ()); 7729 if (DECL_ASSEMBLER_NAME_SET_P (node->decl)) 7730 fprintf (dump_file, " (%s)", 7731 IDENTIFIER_POINTER 7732 (DECL_ASSEMBLER_NAME (node->decl))); 7733 fprintf (dump_file, "\n"); 7734 } 7735 7736 func = DECL_STRUCT_FUNCTION (node->decl); 7737 gcc_assert (cfun == NULL); 7738 7739 /* Build constriants for the function body. */ 7740 FOR_EACH_BB_FN (bb, func) 7741 { 7742 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); 7743 gsi_next (&gsi)) 7744 { 7745 gphi *phi = gsi.phi (); 7746 7747 if (! virtual_operand_p (gimple_phi_result (phi))) 7748 find_func_aliases (func, phi); 7749 } 7750 7751 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); 7752 gsi_next (&gsi)) 7753 { 7754 gimple *stmt = gsi_stmt (gsi); 7755 7756 find_func_aliases (func, stmt); 7757 find_func_clobbers (func, stmt); 7758 } 7759 } 7760 7761 if (dump_file) 7762 { 7763 fprintf (dump_file, "\n"); 7764 dump_constraints (dump_file, from); 7765 fprintf (dump_file, "\n"); 7766 from = constraints.length (); 7767 } 7768 } 7769 7770 /* From the constraints compute the points-to sets. */ 7771 solve_constraints (); 7772 7773 /* Compute the global points-to sets for ESCAPED. 7774 ??? Note that the computed escape set is not correct 7775 for the whole unit as we fail to consider graph edges to 7776 externally visible functions. */ 7777 ipa_escaped_pt = find_what_var_points_to (NULL, get_varinfo (escaped_id)); 7778 7779 /* Make sure the ESCAPED solution (which is used as placeholder in 7780 other solutions) does not reference itself. This simplifies 7781 points-to solution queries. */ 7782 ipa_escaped_pt.ipa_escaped = 0; 7783 7784 /* Assign the points-to sets to the SSA names in the unit. */ 7785 FOR_EACH_DEFINED_FUNCTION (node) 7786 { 7787 tree ptr; 7788 struct function *fn; 7789 unsigned i; 7790 basic_block bb; 7791 7792 /* Nodes without a body are not interesting. */ 7793 if (!node->has_gimple_body_p () || node->clone_of) 7794 continue; 7795 7796 fn = DECL_STRUCT_FUNCTION (node->decl); 7797 7798 /* Compute the points-to sets for pointer SSA_NAMEs. */ 7799 FOR_EACH_VEC_ELT (*fn->gimple_df->ssa_names, i, ptr) 7800 { 7801 if (ptr 7802 && POINTER_TYPE_P (TREE_TYPE (ptr))) 7803 find_what_p_points_to (node->decl, ptr); 7804 } 7805 7806 /* Compute the call-use and call-clobber sets for indirect calls 7807 and calls to external functions. */ 7808 FOR_EACH_BB_FN (bb, fn) 7809 { 7810 gimple_stmt_iterator gsi; 7811 7812 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 7813 { 7814 gcall *stmt; 7815 struct pt_solution *pt; 7816 varinfo_t vi, fi; 7817 tree decl; 7818 7819 stmt = dyn_cast <gcall *> (gsi_stmt (gsi)); 7820 if (!stmt) 7821 continue; 7822 7823 /* Handle direct calls to functions with body. */ 7824 decl = gimple_call_fndecl (stmt); 7825 7826 { 7827 tree called_decl = NULL_TREE; 7828 if (gimple_call_builtin_p (stmt, BUILT_IN_GOMP_PARALLEL)) 7829 called_decl = TREE_OPERAND (gimple_call_arg (stmt, 0), 0); 7830 else if (gimple_call_builtin_p (stmt, BUILT_IN_GOACC_PARALLEL)) 7831 called_decl = TREE_OPERAND (gimple_call_arg (stmt, 1), 0); 7832 7833 if (called_decl != NULL_TREE 7834 && !fndecl_maybe_in_other_partition (called_decl)) 7835 decl = called_decl; 7836 } 7837 7838 if (decl 7839 && (fi = lookup_vi_for_tree (decl)) 7840 && fi->is_fn_info) 7841 { 7842 *gimple_call_clobber_set (stmt) 7843 = find_what_var_points_to 7844 (node->decl, first_vi_for_offset (fi, fi_clobbers)); 7845 *gimple_call_use_set (stmt) 7846 = find_what_var_points_to 7847 (node->decl, first_vi_for_offset (fi, fi_uses)); 7848 } 7849 /* Handle direct calls to external functions. */ 7850 else if (decl) 7851 { 7852 pt = gimple_call_use_set (stmt); 7853 if (gimple_call_flags (stmt) & ECF_CONST) 7854 memset (pt, 0, sizeof (struct pt_solution)); 7855 else if ((vi = lookup_call_use_vi (stmt)) != NULL) 7856 { 7857 *pt = find_what_var_points_to (node->decl, vi); 7858 /* Escaped (and thus nonlocal) variables are always 7859 implicitly used by calls. */ 7860 /* ??? ESCAPED can be empty even though NONLOCAL 7861 always escaped. */ 7862 pt->nonlocal = 1; 7863 pt->ipa_escaped = 1; 7864 } 7865 else 7866 { 7867 /* If there is nothing special about this call then 7868 we have made everything that is used also escape. */ 7869 *pt = ipa_escaped_pt; 7870 pt->nonlocal = 1; 7871 } 7872 7873 pt = gimple_call_clobber_set (stmt); 7874 if (gimple_call_flags (stmt) & (ECF_CONST|ECF_PURE|ECF_NOVOPS)) 7875 memset (pt, 0, sizeof (struct pt_solution)); 7876 else if ((vi = lookup_call_clobber_vi (stmt)) != NULL) 7877 { 7878 *pt = find_what_var_points_to (node->decl, vi); 7879 /* Escaped (and thus nonlocal) variables are always 7880 implicitly clobbered by calls. */ 7881 /* ??? ESCAPED can be empty even though NONLOCAL 7882 always escaped. */ 7883 pt->nonlocal = 1; 7884 pt->ipa_escaped = 1; 7885 } 7886 else 7887 { 7888 /* If there is nothing special about this call then 7889 we have made everything that is used also escape. */ 7890 *pt = ipa_escaped_pt; 7891 pt->nonlocal = 1; 7892 } 7893 } 7894 /* Handle indirect calls. */ 7895 else if (!decl 7896 && (fi = get_fi_for_callee (stmt))) 7897 { 7898 /* We need to accumulate all clobbers/uses of all possible 7899 callees. */ 7900 fi = get_varinfo (find (fi->id)); 7901 /* If we cannot constrain the set of functions we'll end up 7902 calling we end up using/clobbering everything. */ 7903 if (bitmap_bit_p (fi->solution, anything_id) 7904 || bitmap_bit_p (fi->solution, nonlocal_id) 7905 || bitmap_bit_p (fi->solution, escaped_id)) 7906 { 7907 pt_solution_reset (gimple_call_clobber_set (stmt)); 7908 pt_solution_reset (gimple_call_use_set (stmt)); 7909 } 7910 else 7911 { 7912 bitmap_iterator bi; 7913 unsigned i; 7914 struct pt_solution *uses, *clobbers; 7915 7916 uses = gimple_call_use_set (stmt); 7917 clobbers = gimple_call_clobber_set (stmt); 7918 memset (uses, 0, sizeof (struct pt_solution)); 7919 memset (clobbers, 0, sizeof (struct pt_solution)); 7920 EXECUTE_IF_SET_IN_BITMAP (fi->solution, 0, i, bi) 7921 { 7922 struct pt_solution sol; 7923 7924 vi = get_varinfo (i); 7925 if (!vi->is_fn_info) 7926 { 7927 /* ??? We could be more precise here? */ 7928 uses->nonlocal = 1; 7929 uses->ipa_escaped = 1; 7930 clobbers->nonlocal = 1; 7931 clobbers->ipa_escaped = 1; 7932 continue; 7933 } 7934 7935 if (!uses->anything) 7936 { 7937 sol = find_what_var_points_to 7938 (node->decl, 7939 first_vi_for_offset (vi, fi_uses)); 7940 pt_solution_ior_into (uses, &sol); 7941 } 7942 if (!clobbers->anything) 7943 { 7944 sol = find_what_var_points_to 7945 (node->decl, 7946 first_vi_for_offset (vi, fi_clobbers)); 7947 pt_solution_ior_into (clobbers, &sol); 7948 } 7949 } 7950 } 7951 } 7952 } 7953 } 7954 7955 fn->gimple_df->ipa_pta = true; 7956 7957 /* We have to re-set the final-solution cache after each function 7958 because what is a "global" is dependent on function context. */ 7959 final_solutions->empty (); 7960 obstack_free (&final_solutions_obstack, NULL); 7961 gcc_obstack_init (&final_solutions_obstack); 7962 } 7963 7964 delete_points_to_sets (); 7965 7966 in_ipa_mode = 0; 7967 7968 return 0; 7969 } 7970 7971 namespace { 7972 7973 const pass_data pass_data_ipa_pta = 7974 { 7975 SIMPLE_IPA_PASS, /* type */ 7976 "pta", /* name */ 7977 OPTGROUP_NONE, /* optinfo_flags */ 7978 TV_IPA_PTA, /* tv_id */ 7979 0, /* properties_required */ 7980 0, /* properties_provided */ 7981 0, /* properties_destroyed */ 7982 0, /* todo_flags_start */ 7983 0, /* todo_flags_finish */ 7984 }; 7985 7986 class pass_ipa_pta : public simple_ipa_opt_pass 7987 { 7988 public: 7989 pass_ipa_pta (gcc::context *ctxt) 7990 : simple_ipa_opt_pass (pass_data_ipa_pta, ctxt) 7991 {} 7992 7993 /* opt_pass methods: */ 7994 virtual bool gate (function *) 7995 { 7996 return (optimize 7997 && flag_ipa_pta 7998 /* Don't bother doing anything if the program has errors. */ 7999 && !seen_error ()); 8000 } 8001 8002 opt_pass * clone () { return new pass_ipa_pta (m_ctxt); } 8003 8004 virtual unsigned int execute (function *) { return ipa_pta_execute (); } 8005 8006 }; // class pass_ipa_pta 8007 8008 } // anon namespace 8009 8010 simple_ipa_opt_pass * 8011 make_pass_ipa_pta (gcc::context *ctxt) 8012 { 8013 return new pass_ipa_pta (ctxt); 8014 } 8015