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