1169689Skan/* Tree based points-to analysis 2169689Skan Copyright (C) 2005, 2006 Free Software Foundation, Inc. 3169689Skan Contributed by Daniel Berlin <dberlin@dberlin.org> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify 8169689Skanunder the terms of the GNU General Public License as published by 9169689Skanthe Free Software Foundation; either version 2 of the License, or 10169689Skan(at your option) any later version. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, 13169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 14169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15169689SkanGNU General Public License for more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; if not, write to the Free Software 19169689SkanFoundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 20169689Skan*/ 21169689Skan 22169689Skan#include "config.h" 23169689Skan#include "system.h" 24169689Skan#include "coretypes.h" 25169689Skan#include "tm.h" 26169689Skan#include "ggc.h" 27169689Skan#include "obstack.h" 28169689Skan#include "bitmap.h" 29169689Skan#include "flags.h" 30169689Skan#include "rtl.h" 31169689Skan#include "tm_p.h" 32169689Skan#include "hard-reg-set.h" 33169689Skan#include "basic-block.h" 34169689Skan#include "output.h" 35169689Skan#include "errors.h" 36169689Skan#include "diagnostic.h" 37169689Skan#include "tree.h" 38169689Skan#include "c-common.h" 39169689Skan#include "tree-flow.h" 40169689Skan#include "tree-inline.h" 41169689Skan#include "varray.h" 42169689Skan#include "c-tree.h" 43169689Skan#include "tree-gimple.h" 44169689Skan#include "hashtab.h" 45169689Skan#include "function.h" 46169689Skan#include "cgraph.h" 47169689Skan#include "tree-pass.h" 48169689Skan#include "timevar.h" 49169689Skan#include "alloc-pool.h" 50169689Skan#include "splay-tree.h" 51169689Skan#include "params.h" 52169689Skan#include "tree-ssa-structalias.h" 53169689Skan#include "cgraph.h" 54171825Skan#include "pointer-set.h" 55169689Skan 56169689Skan/* The idea behind this analyzer is to generate set constraints from the 57169689Skan program, then solve the resulting constraints in order to generate the 58171825Skan points-to sets. 59169689Skan 60169689Skan Set constraints are a way of modeling program analysis problems that 61169689Skan involve sets. They consist of an inclusion constraint language, 62169689Skan describing the variables (each variable is a set) and operations that 63169689Skan are involved on the variables, and a set of rules that derive facts 64169689Skan from these operations. To solve a system of set constraints, you derive 65169689Skan all possible facts under the rules, which gives you the correct sets 66169689Skan as a consequence. 67169689Skan 68169689Skan See "Efficient Field-sensitive pointer analysis for C" by "David 69169689Skan J. Pearce and Paul H. J. Kelly and Chris Hankin, at 70169689Skan http://citeseer.ist.psu.edu/pearce04efficient.html 71169689Skan 72169689Skan Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines 73169689Skan of C Code in a Second" by ""Nevin Heintze and Olivier Tardieu" at 74171825Skan http://citeseer.ist.psu.edu/heintze01ultrafast.html 75169689Skan 76171825Skan There are three types of real constraint expressions, DEREF, 77171825Skan ADDRESSOF, and SCALAR. Each constraint expression consists 78171825Skan of a constraint type, a variable, and an offset. 79171825Skan 80169689Skan SCALAR is a constraint expression type used to represent x, whether 81169689Skan it appears on the LHS or the RHS of a statement. 82169689Skan DEREF is a constraint expression type used to represent *x, whether 83171825Skan it appears on the LHS or the RHS of a statement. 84169689Skan ADDRESSOF is a constraint expression used to represent &x, whether 85169689Skan it appears on the LHS or the RHS of a statement. 86171825Skan 87169689Skan Each pointer variable in the program is assigned an integer id, and 88169689Skan each field of a structure variable is assigned an integer id as well. 89171825Skan 90169689Skan Structure variables are linked to their list of fields through a "next 91169689Skan field" in each variable that points to the next field in offset 92171825Skan order. 93171825Skan Each variable for a structure field has 94169689Skan 95169689Skan 1. "size", that tells the size in bits of that field. 96169689Skan 2. "fullsize, that tells the size in bits of the entire structure. 97169689Skan 3. "offset", that tells the offset in bits from the beginning of the 98169689Skan structure to this field. 99169689Skan 100171825Skan Thus, 101169689Skan struct f 102169689Skan { 103169689Skan int a; 104169689Skan int b; 105169689Skan } foo; 106169689Skan int *bar; 107169689Skan 108169689Skan looks like 109169689Skan 110169689Skan foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b 111169689Skan foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL 112169689Skan bar -> id 3, size 32, offset 0, fullsize 32, next NULL 113169689Skan 114171825Skan 115169689Skan In order to solve the system of set constraints, the following is 116169689Skan done: 117169689Skan 118169689Skan 1. Each constraint variable x has a solution set associated with it, 119169689Skan Sol(x). 120171825Skan 121169689Skan 2. Constraints are separated into direct, copy, and complex. 122169689Skan Direct constraints are ADDRESSOF constraints that require no extra 123169689Skan processing, such as P = &Q 124169689Skan Copy constraints are those of the form P = Q. 125171825Skan Complex constraints are all the constraints involving dereferences 126171825Skan and offsets (including offsetted copies). 127171825Skan 128169689Skan 3. All direct constraints of the form P = &Q are processed, such 129171825Skan that Q is added to Sol(P) 130169689Skan 131169689Skan 4. All complex constraints for a given constraint variable are stored in a 132171825Skan linked list attached to that variable's node. 133169689Skan 134169689Skan 5. A directed graph is built out of the copy constraints. Each 135171825Skan constraint variable is a node in the graph, and an edge from 136169689Skan Q to P is added for each copy constraint of the form P = Q 137171825Skan 138169689Skan 6. The graph is then walked, and solution sets are 139169689Skan propagated along the copy edges, such that an edge from Q to P 140169689Skan causes Sol(P) <- Sol(P) union Sol(Q). 141171825Skan 142169689Skan 7. As we visit each node, all complex constraints associated with 143169689Skan that node are processed by adding appropriate copy edges to the graph, or the 144171825Skan appropriate variables to the solution set. 145169689Skan 146169689Skan 8. The process of walking the graph is iterated until no solution 147169689Skan sets change. 148169689Skan 149169689Skan Prior to walking the graph in steps 6 and 7, We perform static 150171825Skan cycle elimination on the constraint graph, as well 151169689Skan as off-line variable substitution. 152171825Skan 153169689Skan TODO: Adding offsets to pointer-to-structures can be handled (IE not punted 154169689Skan on and turned into anything), but isn't. You can just see what offset 155169689Skan inside the pointed-to struct it's going to access. 156171825Skan 157169689Skan TODO: Constant bounded arrays can be handled as if they were structs of the 158171825Skan same number of elements. 159169689Skan 160169689Skan TODO: Modeling heap and incoming pointers becomes much better if we 161169689Skan add fields to them as we discover them, which we could do. 162169689Skan 163169689Skan TODO: We could handle unions, but to be honest, it's probably not 164169689Skan worth the pain or slowdown. */ 165169689Skan 166171825Skanstatic GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map))) htab_t heapvar_for_stmt; 167169689Skan 168169689Skan/* One variable to represent all non-local accesses. */ 169169689Skantree nonlocal_all; 170169689Skan 171169689Skanstatic bool use_field_sensitive = true; 172169689Skanstatic int in_ipa_mode = 0; 173171825Skan 174171825Skan/* Used for predecessor bitmaps. */ 175169689Skanstatic bitmap_obstack predbitmap_obstack; 176171825Skan 177171825Skan/* Used for points-to sets. */ 178171825Skanstatic bitmap_obstack pta_obstack; 179171825Skan 180171825Skan/* Used for oldsolution members of variables. */ 181171825Skanstatic bitmap_obstack oldpta_obstack; 182171825Skan 183171825Skan/* Used for per-solver-iteration bitmaps. */ 184169689Skanstatic bitmap_obstack iteration_obstack; 185169689Skan 186169689Skanstatic unsigned int create_variable_info_for (tree, const char *); 187171825Skantypedef struct constraint_graph *constraint_graph_t; 188171825Skanstatic void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool); 189169689Skan 190169689SkanDEF_VEC_P(constraint_t); 191169689SkanDEF_VEC_ALLOC_P(constraint_t,heap); 192169689Skan 193169689Skan#define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \ 194169689Skan if (a) \ 195169689Skan EXECUTE_IF_SET_IN_BITMAP (a, b, c, d) 196169689Skan 197169689Skanstatic struct constraint_stats 198169689Skan{ 199169689Skan unsigned int total_vars; 200171825Skan unsigned int nonpointer_vars; 201169689Skan unsigned int unified_vars_static; 202169689Skan unsigned int unified_vars_dynamic; 203169689Skan unsigned int iterations; 204169689Skan unsigned int num_edges; 205171825Skan unsigned int num_implicit_edges; 206171825Skan unsigned int points_to_sets_created; 207169689Skan} stats; 208169689Skan 209169689Skanstruct variable_info 210169689Skan{ 211169689Skan /* ID of this variable */ 212169689Skan unsigned int id; 213169689Skan 214169689Skan /* Name of this variable */ 215169689Skan const char *name; 216169689Skan 217169689Skan /* Tree that this variable is associated with. */ 218169689Skan tree decl; 219169689Skan 220169689Skan /* Offset of this variable, in bits, from the base variable */ 221171825Skan unsigned HOST_WIDE_INT offset; 222169689Skan 223169689Skan /* Size of the variable, in bits. */ 224169689Skan unsigned HOST_WIDE_INT size; 225169689Skan 226169689Skan /* Full size of the base variable, in bits. */ 227169689Skan unsigned HOST_WIDE_INT fullsize; 228169689Skan 229169689Skan /* A link to the variable for the next field in this structure. */ 230169689Skan struct variable_info *next; 231169689Skan 232169689Skan /* True if the variable is directly the target of a dereference. 233169689Skan This is used to track which variables are *actually* dereferenced 234171825Skan so we can prune their points to listed. */ 235169689Skan unsigned int directly_dereferenced:1; 236169689Skan 237169689Skan /* True if this is a variable created by the constraint analysis, such as 238169689Skan heap variables and constraints we had to break up. */ 239169689Skan unsigned int is_artificial_var:1; 240171825Skan 241169689Skan /* True if this is a special variable whose solution set should not be 242169689Skan changed. */ 243169689Skan unsigned int is_special_var:1; 244169689Skan 245169689Skan /* True for variables whose size is not known or variable. */ 246171825Skan unsigned int is_unknown_size_var:1; 247169689Skan 248169689Skan /* True for variables that have unions somewhere in them. */ 249169689Skan unsigned int has_union:1; 250169689Skan 251169689Skan /* True if this is a heap variable. */ 252169689Skan unsigned int is_heap_var:1; 253169689Skan 254169689Skan /* Points-to set for this variable. */ 255169689Skan bitmap solution; 256169689Skan 257171825Skan /* Old points-to set for this variable. */ 258171825Skan bitmap oldsolution; 259171825Skan 260169689Skan /* Variable ids represented by this node. */ 261169689Skan bitmap variables; 262169689Skan 263171825Skan /* Variable id this was collapsed to due to type unsafety. This 264171825Skan should be unused completely after build_succ_graph, or something 265171825Skan is broken. */ 266169689Skan struct variable_info *collapsed_to; 267169689Skan}; 268169689Skantypedef struct variable_info *varinfo_t; 269169689Skan 270169689Skanstatic varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT); 271169689Skan 272169689Skan/* Pool of variable info structures. */ 273169689Skanstatic alloc_pool variable_info_pool; 274169689Skan 275169689SkanDEF_VEC_P(varinfo_t); 276169689Skan 277169689SkanDEF_VEC_ALLOC_P(varinfo_t, heap); 278169689Skan 279171825Skan/* Table of variable info structures for constraint variables. 280171825Skan Indexed directly by variable info id. */ 281169689Skanstatic VEC(varinfo_t,heap) *varmap; 282169689Skan 283169689Skan/* Return the varmap element N */ 284169689Skan 285169689Skanstatic inline varinfo_t 286169689Skanget_varinfo (unsigned int n) 287169689Skan{ 288171825Skan return VEC_index (varinfo_t, varmap, n); 289169689Skan} 290169689Skan 291169689Skan/* Return the varmap element N, following the collapsed_to link. */ 292169689Skan 293169689Skanstatic inline varinfo_t 294169689Skanget_varinfo_fc (unsigned int n) 295169689Skan{ 296171825Skan varinfo_t v = VEC_index (varinfo_t, varmap, n); 297169689Skan 298169689Skan if (v->collapsed_to) 299169689Skan return v->collapsed_to; 300169689Skan return v; 301169689Skan} 302169689Skan 303169689Skan/* Variable that represents the unknown pointer. */ 304169689Skanstatic varinfo_t var_anything; 305169689Skanstatic tree anything_tree; 306169689Skanstatic unsigned int anything_id; 307169689Skan 308169689Skan/* Variable that represents the NULL pointer. */ 309169689Skanstatic varinfo_t var_nothing; 310169689Skanstatic tree nothing_tree; 311169689Skanstatic unsigned int nothing_id; 312169689Skan 313169689Skan/* Variable that represents read only memory. */ 314169689Skanstatic varinfo_t var_readonly; 315169689Skanstatic tree readonly_tree; 316169689Skanstatic unsigned int readonly_id; 317169689Skan 318169689Skan/* Variable that represents integers. This is used for when people do things 319169689Skan like &0->a.b. */ 320169689Skanstatic varinfo_t var_integer; 321169689Skanstatic tree integer_tree; 322169689Skanstatic unsigned int integer_id; 323169689Skan 324169689Skan/* Variable that represents escaped variables. This is used to give 325169689Skan incoming pointer variables a better set than ANYTHING. */ 326169689Skanstatic varinfo_t var_escaped_vars; 327169689Skanstatic tree escaped_vars_tree; 328169689Skanstatic unsigned int escaped_vars_id; 329169689Skan 330169689Skan/* Variable that represents non-local variables before we expand it to 331169689Skan one for each type. */ 332169689Skanstatic unsigned int nonlocal_vars_id; 333169689Skan/* Lookup a heap var for FROM, and return it if we find one. */ 334169689Skan 335171825Skanstatic tree 336169689Skanheapvar_lookup (tree from) 337169689Skan{ 338169689Skan struct tree_map *h, in; 339169689Skan in.from = from; 340169689Skan 341169689Skan h = htab_find_with_hash (heapvar_for_stmt, &in, htab_hash_pointer (from)); 342169689Skan if (h) 343169689Skan return h->to; 344169689Skan return NULL_TREE; 345169689Skan} 346169689Skan 347169689Skan/* Insert a mapping FROM->TO in the heap var for statement 348169689Skan hashtable. */ 349169689Skan 350169689Skanstatic void 351169689Skanheapvar_insert (tree from, tree to) 352169689Skan{ 353169689Skan struct tree_map *h; 354169689Skan void **loc; 355169689Skan 356169689Skan h = ggc_alloc (sizeof (struct tree_map)); 357169689Skan h->hash = htab_hash_pointer (from); 358169689Skan h->from = from; 359169689Skan h->to = to; 360169689Skan loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT); 361169689Skan *(struct tree_map **) loc = h; 362169689Skan} 363169689Skan 364169689Skan/* Return a new variable info structure consisting for a variable 365169689Skan named NAME, and using constraint graph node NODE. */ 366169689Skan 367169689Skanstatic varinfo_t 368171825Skannew_var_info (tree t, unsigned int id, const char *name) 369169689Skan{ 370169689Skan varinfo_t ret = pool_alloc (variable_info_pool); 371169689Skan 372169689Skan ret->id = id; 373169689Skan ret->name = name; 374169689Skan ret->decl = t; 375169689Skan ret->directly_dereferenced = false; 376169689Skan ret->is_artificial_var = false; 377169689Skan ret->is_heap_var = false; 378169689Skan ret->is_special_var = false; 379169689Skan ret->is_unknown_size_var = false; 380169689Skan ret->has_union = false; 381171825Skan ret->solution = BITMAP_ALLOC (&pta_obstack); 382171825Skan ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack); 383169689Skan ret->next = NULL; 384169689Skan ret->collapsed_to = NULL; 385169689Skan return ret; 386169689Skan} 387169689Skan 388169689Skantypedef enum {SCALAR, DEREF, ADDRESSOF} constraint_expr_type; 389169689Skan 390169689Skan/* An expression that appears in a constraint. */ 391169689Skan 392171825Skanstruct constraint_expr 393169689Skan{ 394169689Skan /* Constraint type. */ 395169689Skan constraint_expr_type type; 396169689Skan 397169689Skan /* Variable we are referring to in the constraint. */ 398169689Skan unsigned int var; 399169689Skan 400169689Skan /* Offset, in bits, of this constraint from the beginning of 401169689Skan variables it ends up referring to. 402169689Skan 403169689Skan IOW, in a deref constraint, we would deref, get the result set, 404169689Skan then add OFFSET to each member. */ 405169689Skan unsigned HOST_WIDE_INT offset; 406169689Skan}; 407169689Skan 408169689Skantypedef struct constraint_expr ce_s; 409169689SkanDEF_VEC_O(ce_s); 410169689SkanDEF_VEC_ALLOC_O(ce_s, heap); 411169689Skanstatic void get_constraint_for (tree, VEC(ce_s, heap) **); 412169689Skanstatic void do_deref (VEC (ce_s, heap) **); 413169689Skan 414169689Skan/* Our set constraints are made up of two constraint expressions, one 415171825Skan LHS, and one RHS. 416169689Skan 417169689Skan As described in the introduction, our set constraints each represent an 418169689Skan operation between set valued variables. 419169689Skan*/ 420169689Skanstruct constraint 421169689Skan{ 422169689Skan struct constraint_expr lhs; 423169689Skan struct constraint_expr rhs; 424169689Skan}; 425169689Skan 426169689Skan/* List of constraints that we use to build the constraint graph from. */ 427169689Skan 428169689Skanstatic VEC(constraint_t,heap) *constraints; 429169689Skanstatic alloc_pool constraint_pool; 430169689Skan 431169689Skan 432171825SkanDEF_VEC_I(int); 433171825SkanDEF_VEC_ALLOC_I(int, heap); 434171825Skan 435171825Skan/* The constraint graph is represented as an array of bitmaps 436171825Skan containing successor nodes. */ 437171825Skan 438171825Skanstruct constraint_graph 439169689Skan{ 440171825Skan /* Size of this graph, which may be different than the number of 441171825Skan nodes in the variable map. */ 442171825Skan unsigned int size; 443169689Skan 444171825Skan /* Explicit successors of each node. */ 445171825Skan bitmap *succs; 446169689Skan 447171825Skan /* Implicit predecessors of each node (Used for variable 448171825Skan substitution). */ 449171825Skan bitmap *implicit_preds; 450169689Skan 451171825Skan /* Explicit predecessors of each node (Used for variable substitution). */ 452171825Skan bitmap *preds; 453169689Skan 454171825Skan /* Indirect cycle representatives, or -1 if the node has no indirect 455171825Skan cycles. */ 456171825Skan int *indirect_cycles; 457169689Skan 458171825Skan /* Representative node for a node. rep[a] == a unless the node has 459171825Skan been unified. */ 460171825Skan unsigned int *rep; 461169689Skan 462171825Skan /* Equivalence class representative for a node. This is used for 463171825Skan variable substitution. */ 464171825Skan int *eq_rep; 465169689Skan 466171825Skan /* Label for each node, used during variable substitution. */ 467171825Skan unsigned int *label; 468171825Skan 469171825Skan /* Bitmap of nodes where the bit is set if the node is a direct 470171825Skan node. Used for variable substitution. */ 471171825Skan sbitmap direct_nodes; 472171825Skan 473171825Skan /* Vector of complex constraints for each graph node. Complex 474171825Skan constraints are those involving dereferences or offsets that are 475171825Skan not 0. */ 476171825Skan VEC(constraint_t,heap) **complex; 477169689Skan}; 478169689Skan 479169689Skanstatic constraint_graph_t graph; 480169689Skan 481171825Skan/* During variable substitution and the offline version of indirect 482171825Skan cycle finding, we create nodes to represent dereferences and 483171825Skan address taken constraints. These represent where these start and 484171825Skan end. */ 485171825Skan#define FIRST_REF_NODE (VEC_length (varinfo_t, varmap)) 486171825Skan#define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1)) 487171825Skan#define FIRST_ADDR_NODE (LAST_REF_NODE + 1) 488171825Skan 489171825Skan/* Return the representative node for NODE, if NODE has been unioned 490171825Skan with another NODE. 491171825Skan This function performs path compression along the way to finding 492171825Skan the representative. */ 493171825Skan 494171825Skanstatic unsigned int 495171825Skanfind (unsigned int node) 496171825Skan{ 497171825Skan gcc_assert (node < graph->size); 498171825Skan if (graph->rep[node] != node) 499171825Skan return graph->rep[node] = find (graph->rep[node]); 500171825Skan return node; 501171825Skan} 502171825Skan 503171825Skan/* Union the TO and FROM nodes to the TO nodes. 504171825Skan Note that at some point in the future, we may want to do 505171825Skan union-by-rank, in which case we are going to have to return the 506171825Skan node we unified to. */ 507171825Skan 508171825Skanstatic bool 509171825Skanunite (unsigned int to, unsigned int from) 510171825Skan{ 511171825Skan gcc_assert (to < graph->size && from < graph->size); 512171825Skan if (to != from && graph->rep[from] != to) 513171825Skan { 514171825Skan graph->rep[from] = to; 515171825Skan return true; 516171825Skan } 517171825Skan return false; 518171825Skan} 519171825Skan 520169689Skan/* Create a new constraint consisting of LHS and RHS expressions. */ 521169689Skan 522171825Skanstatic constraint_t 523169689Skannew_constraint (const struct constraint_expr lhs, 524169689Skan const struct constraint_expr rhs) 525169689Skan{ 526169689Skan constraint_t ret = pool_alloc (constraint_pool); 527169689Skan ret->lhs = lhs; 528169689Skan ret->rhs = rhs; 529169689Skan return ret; 530169689Skan} 531169689Skan 532169689Skan/* Print out constraint C to FILE. */ 533169689Skan 534169689Skanvoid 535169689Skandump_constraint (FILE *file, constraint_t c) 536169689Skan{ 537169689Skan if (c->lhs.type == ADDRESSOF) 538169689Skan fprintf (file, "&"); 539169689Skan else if (c->lhs.type == DEREF) 540171825Skan fprintf (file, "*"); 541169689Skan fprintf (file, "%s", get_varinfo_fc (c->lhs.var)->name); 542169689Skan if (c->lhs.offset != 0) 543169689Skan fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset); 544169689Skan fprintf (file, " = "); 545169689Skan if (c->rhs.type == ADDRESSOF) 546169689Skan fprintf (file, "&"); 547169689Skan else if (c->rhs.type == DEREF) 548169689Skan fprintf (file, "*"); 549169689Skan fprintf (file, "%s", get_varinfo_fc (c->rhs.var)->name); 550169689Skan if (c->rhs.offset != 0) 551169689Skan fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset); 552169689Skan fprintf (file, "\n"); 553169689Skan} 554169689Skan 555169689Skan/* Print out constraint C to stderr. */ 556169689Skan 557169689Skanvoid 558169689Skandebug_constraint (constraint_t c) 559169689Skan{ 560169689Skan dump_constraint (stderr, c); 561169689Skan} 562169689Skan 563169689Skan/* Print out all constraints to FILE */ 564169689Skan 565169689Skanvoid 566169689Skandump_constraints (FILE *file) 567169689Skan{ 568169689Skan int i; 569169689Skan constraint_t c; 570169689Skan for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) 571169689Skan dump_constraint (file, c); 572169689Skan} 573169689Skan 574169689Skan/* Print out all constraints to stderr. */ 575169689Skan 576169689Skanvoid 577169689Skandebug_constraints (void) 578169689Skan{ 579169689Skan dump_constraints (stderr); 580169689Skan} 581169689Skan 582171825Skan/* SOLVER FUNCTIONS 583169689Skan 584169689Skan The solver is a simple worklist solver, that works on the following 585169689Skan algorithm: 586169689Skan 587171825Skan sbitmap changed_nodes = all zeroes; 588171825Skan changed_count = 0; 589171825Skan For each node that is not already collapsed: 590171825Skan changed_count++; 591171825Skan set bit in changed nodes 592171825Skan 593169689Skan while (changed_count > 0) 594169689Skan { 595169689Skan compute topological ordering for constraint graph 596171825Skan 597169689Skan find and collapse cycles in the constraint graph (updating 598169689Skan changed if necessary) 599171825Skan 600169689Skan for each node (n) in the graph in topological order: 601169689Skan changed_count--; 602169689Skan 603169689Skan Process each complex constraint associated with the node, 604169689Skan updating changed if necessary. 605169689Skan 606169689Skan For each outgoing edge from n, propagate the solution from n to 607169689Skan the destination of the edge, updating changed as necessary. 608169689Skan 609169689Skan } */ 610169689Skan 611169689Skan/* Return true if two constraint expressions A and B are equal. */ 612169689Skan 613169689Skanstatic bool 614169689Skanconstraint_expr_equal (struct constraint_expr a, struct constraint_expr b) 615169689Skan{ 616169689Skan return a.type == b.type && a.var == b.var && a.offset == b.offset; 617169689Skan} 618169689Skan 619169689Skan/* Return true if constraint expression A is less than constraint expression 620169689Skan B. This is just arbitrary, but consistent, in order to give them an 621169689Skan ordering. */ 622169689Skan 623169689Skanstatic bool 624169689Skanconstraint_expr_less (struct constraint_expr a, struct constraint_expr b) 625169689Skan{ 626169689Skan if (a.type == b.type) 627169689Skan { 628169689Skan if (a.var == b.var) 629169689Skan return a.offset < b.offset; 630169689Skan else 631169689Skan return a.var < b.var; 632169689Skan } 633169689Skan else 634169689Skan return a.type < b.type; 635169689Skan} 636169689Skan 637169689Skan/* Return true if constraint A is less than constraint B. This is just 638169689Skan arbitrary, but consistent, in order to give them an ordering. */ 639169689Skan 640169689Skanstatic bool 641169689Skanconstraint_less (const constraint_t a, const constraint_t b) 642169689Skan{ 643169689Skan if (constraint_expr_less (a->lhs, b->lhs)) 644169689Skan return true; 645169689Skan else if (constraint_expr_less (b->lhs, a->lhs)) 646169689Skan return false; 647169689Skan else 648169689Skan return constraint_expr_less (a->rhs, b->rhs); 649169689Skan} 650169689Skan 651169689Skan/* Return true if two constraints A and B are equal. */ 652171825Skan 653169689Skanstatic bool 654169689Skanconstraint_equal (struct constraint a, struct constraint b) 655169689Skan{ 656171825Skan return constraint_expr_equal (a.lhs, b.lhs) 657169689Skan && constraint_expr_equal (a.rhs, b.rhs); 658169689Skan} 659169689Skan 660169689Skan 661169689Skan/* Find a constraint LOOKFOR in the sorted constraint vector VEC */ 662169689Skan 663169689Skanstatic constraint_t 664169689Skanconstraint_vec_find (VEC(constraint_t,heap) *vec, 665169689Skan struct constraint lookfor) 666169689Skan{ 667171825Skan unsigned int place; 668169689Skan constraint_t found; 669169689Skan 670169689Skan if (vec == NULL) 671169689Skan return NULL; 672169689Skan 673169689Skan place = VEC_lower_bound (constraint_t, vec, &lookfor, constraint_less); 674169689Skan if (place >= VEC_length (constraint_t, vec)) 675169689Skan return NULL; 676169689Skan found = VEC_index (constraint_t, vec, place); 677169689Skan if (!constraint_equal (*found, lookfor)) 678169689Skan return NULL; 679169689Skan return found; 680169689Skan} 681169689Skan 682169689Skan/* Union two constraint vectors, TO and FROM. Put the result in TO. */ 683169689Skan 684169689Skanstatic void 685169689Skanconstraint_set_union (VEC(constraint_t,heap) **to, 686169689Skan VEC(constraint_t,heap) **from) 687169689Skan{ 688169689Skan int i; 689169689Skan constraint_t c; 690169689Skan 691169689Skan for (i = 0; VEC_iterate (constraint_t, *from, i, c); i++) 692169689Skan { 693169689Skan if (constraint_vec_find (*to, *c) == NULL) 694169689Skan { 695169689Skan unsigned int place = VEC_lower_bound (constraint_t, *to, c, 696169689Skan constraint_less); 697169689Skan VEC_safe_insert (constraint_t, heap, *to, place, c); 698169689Skan } 699169689Skan } 700169689Skan} 701169689Skan 702169689Skan/* Take a solution set SET, add OFFSET to each member of the set, and 703169689Skan overwrite SET with the result when done. */ 704169689Skan 705169689Skanstatic void 706169689Skansolution_set_add (bitmap set, unsigned HOST_WIDE_INT offset) 707169689Skan{ 708169689Skan bitmap result = BITMAP_ALLOC (&iteration_obstack); 709169689Skan unsigned int i; 710169689Skan bitmap_iterator bi; 711171825Skan unsigned HOST_WIDE_INT min = -1, max = 0; 712169689Skan 713171825Skan /* Compute set of vars we can reach from set + offset. */ 714171825Skan 715169689Skan EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi) 716169689Skan { 717171825Skan if (get_varinfo (i)->is_artificial_var 718171825Skan || get_varinfo (i)->has_union 719171825Skan || get_varinfo (i)->is_unknown_size_var) 720171825Skan continue; 721171825Skan 722171825Skan if (get_varinfo (i)->offset + offset < min) 723171825Skan min = get_varinfo (i)->offset + offset; 724171825Skan if (get_varinfo (i)->offset + get_varinfo (i)->size + offset > max) 725171825Skan { 726171825Skan max = get_varinfo (i)->offset + get_varinfo (i)->size + offset; 727171825Skan if (max > get_varinfo (i)->fullsize) 728171825Skan max = get_varinfo (i)->fullsize; 729171825Skan } 730171825Skan } 731171825Skan 732171825Skan EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi) 733171825Skan { 734169689Skan /* If this is a properly sized variable, only add offset if it's 735169689Skan less than end. Otherwise, it is globbed to a single 736169689Skan variable. */ 737171825Skan 738171825Skan if (get_varinfo (i)->offset + get_varinfo (i)->size - 1 >= min 739171825Skan && get_varinfo (i)->offset < max) 740169689Skan { 741171825Skan bitmap_set_bit (result, i); 742169689Skan } 743171825Skan else if (get_varinfo (i)->is_artificial_var 744169689Skan || get_varinfo (i)->has_union 745169689Skan || get_varinfo (i)->is_unknown_size_var) 746169689Skan { 747169689Skan bitmap_set_bit (result, i); 748169689Skan } 749169689Skan } 750171825Skan 751171825Skan bitmap_copy (set, result); 752169689Skan BITMAP_FREE (result); 753169689Skan} 754169689Skan 755169689Skan/* Union solution sets TO and FROM, and add INC to each member of FROM in the 756169689Skan process. */ 757169689Skan 758169689Skanstatic bool 759169689Skanset_union_with_increment (bitmap to, bitmap from, unsigned HOST_WIDE_INT inc) 760169689Skan{ 761169689Skan if (inc == 0) 762169689Skan return bitmap_ior_into (to, from); 763169689Skan else 764169689Skan { 765169689Skan bitmap tmp; 766169689Skan bool res; 767169689Skan 768169689Skan tmp = BITMAP_ALLOC (&iteration_obstack); 769169689Skan bitmap_copy (tmp, from); 770169689Skan solution_set_add (tmp, inc); 771169689Skan res = bitmap_ior_into (to, tmp); 772169689Skan BITMAP_FREE (tmp); 773169689Skan return res; 774169689Skan } 775169689Skan} 776169689Skan 777171825Skan/* Insert constraint C into the list of complex constraints for graph 778171825Skan node VAR. */ 779169689Skan 780169689Skanstatic void 781171825Skaninsert_into_complex (constraint_graph_t graph, 782171825Skan unsigned int var, constraint_t c) 783169689Skan{ 784171825Skan VEC (constraint_t, heap) *complex = graph->complex[var]; 785171825Skan unsigned int place = VEC_lower_bound (constraint_t, complex, c, 786169689Skan constraint_less); 787169689Skan 788171825Skan /* Only insert constraints that do not already exist. */ 789171825Skan if (place >= VEC_length (constraint_t, complex) 790171825Skan || !constraint_equal (*c, *VEC_index (constraint_t, complex, place))) 791171825Skan VEC_safe_insert (constraint_t, heap, graph->complex[var], place, c); 792169689Skan} 793169689Skan 794169689Skan 795169689Skan/* Condense two variable nodes into a single variable node, by moving 796169689Skan all associated info from SRC to TO. */ 797169689Skan 798171825Skanstatic void 799171825Skanmerge_node_constraints (constraint_graph_t graph, unsigned int to, 800171825Skan unsigned int from) 801169689Skan{ 802169689Skan unsigned int i; 803169689Skan constraint_t c; 804171825Skan 805171825Skan gcc_assert (find (from) == to); 806171825Skan 807169689Skan /* Move all complex constraints from src node into to node */ 808171825Skan for (i = 0; VEC_iterate (constraint_t, graph->complex[from], i, c); i++) 809169689Skan { 810169689Skan /* In complex constraints for node src, we may have either 811171825Skan a = *src, and *src = a, or an offseted constraint which are 812171825Skan always added to the rhs node's constraints. */ 813171825Skan 814169689Skan if (c->rhs.type == DEREF) 815169689Skan c->rhs.var = to; 816171825Skan else if (c->lhs.type == DEREF) 817171825Skan c->lhs.var = to; 818169689Skan else 819171825Skan c->rhs.var = to; 820169689Skan } 821171825Skan constraint_set_union (&graph->complex[to], &graph->complex[from]); 822171825Skan VEC_free (constraint_t, heap, graph->complex[from]); 823171825Skan graph->complex[from] = NULL; 824169689Skan} 825169689Skan 826169689Skan 827169689Skan/* Remove edges involving NODE from GRAPH. */ 828169689Skan 829169689Skanstatic void 830169689Skanclear_edges_for_node (constraint_graph_t graph, unsigned int node) 831169689Skan{ 832171825Skan if (graph->succs[node]) 833171825Skan BITMAP_FREE (graph->succs[node]); 834169689Skan} 835169689Skan 836169689Skan/* Merge GRAPH nodes FROM and TO into node TO. */ 837169689Skan 838169689Skanstatic void 839171825Skanmerge_graph_nodes (constraint_graph_t graph, unsigned int to, 840169689Skan unsigned int from) 841169689Skan{ 842171825Skan if (graph->indirect_cycles[from] != -1) 843169689Skan { 844171825Skan /* If we have indirect cycles with the from node, and we have 845171825Skan none on the to node, the to node has indirect cycles from the 846171825Skan from node now that they are unified. 847171825Skan If indirect cycles exist on both, unify the nodes that they 848171825Skan are in a cycle with, since we know they are in a cycle with 849171825Skan each other. */ 850171825Skan if (graph->indirect_cycles[to] == -1) 851169689Skan { 852171825Skan graph->indirect_cycles[to] = graph->indirect_cycles[from]; 853169689Skan } 854171825Skan else 855171825Skan { 856171825Skan unsigned int tonode = find (graph->indirect_cycles[to]); 857171825Skan unsigned int fromnode = find (graph->indirect_cycles[from]); 858169689Skan 859171825Skan if (unite (tonode, fromnode)) 860171825Skan unify_nodes (graph, tonode, fromnode, true); 861169689Skan } 862169689Skan } 863169689Skan 864171825Skan /* Merge all the successor edges. */ 865171825Skan if (graph->succs[from]) 866169689Skan { 867171825Skan if (!graph->succs[to]) 868171825Skan graph->succs[to] = BITMAP_ALLOC (&pta_obstack); 869171825Skan bitmap_ior_into (graph->succs[to], 870171825Skan graph->succs[from]); 871171825Skan } 872169689Skan 873171825Skan clear_edges_for_node (graph, from); 874171825Skan} 875169689Skan 876169689Skan 877171825Skan/* Add an indirect graph edge to GRAPH, going from TO to FROM if 878171825Skan it doesn't exist in the graph already. */ 879169689Skan 880171825Skanstatic void 881171825Skanadd_implicit_graph_edge (constraint_graph_t graph, unsigned int to, 882171825Skan unsigned int from) 883171825Skan{ 884171825Skan if (to == from) 885171825Skan return; 886169689Skan 887171825Skan if (!graph->implicit_preds[to]) 888171825Skan graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack); 889169689Skan 890171825Skan if (!bitmap_bit_p (graph->implicit_preds[to], from)) 891171825Skan { 892171825Skan stats.num_implicit_edges++; 893171825Skan bitmap_set_bit (graph->implicit_preds[to], from); 894169689Skan } 895169689Skan} 896169689Skan 897171825Skan/* Add a predecessor graph edge to GRAPH, going from TO to FROM if 898169689Skan it doesn't exist in the graph already. 899169689Skan Return false if the edge already existed, true otherwise. */ 900169689Skan 901171825Skanstatic void 902171825Skanadd_pred_graph_edge (constraint_graph_t graph, unsigned int to, 903171825Skan unsigned int from) 904171825Skan{ 905171825Skan if (!graph->preds[to]) 906171825Skan graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack); 907171825Skan if (!bitmap_bit_p (graph->preds[to], from)) 908171825Skan bitmap_set_bit (graph->preds[to], from); 909171825Skan} 910171825Skan 911171825Skan/* Add a graph edge to GRAPH, going from FROM to TO if 912171825Skan it doesn't exist in the graph already. 913171825Skan Return false if the edge already existed, true otherwise. */ 914171825Skan 915169689Skanstatic bool 916171825Skanadd_graph_edge (constraint_graph_t graph, unsigned int to, 917171825Skan unsigned int from) 918169689Skan{ 919171825Skan if (to == from) 920169689Skan { 921169689Skan return false; 922169689Skan } 923169689Skan else 924169689Skan { 925169689Skan bool r = false; 926169689Skan 927171825Skan if (!graph->succs[from]) 928171825Skan graph->succs[from] = BITMAP_ALLOC (&pta_obstack); 929171825Skan if (!bitmap_bit_p (graph->succs[from], to)) 930169689Skan { 931171825Skan r = true; 932171825Skan if (to < FIRST_REF_NODE && from < FIRST_REF_NODE) 933171825Skan stats.num_edges++; 934171825Skan bitmap_set_bit (graph->succs[from], to); 935169689Skan } 936169689Skan return r; 937169689Skan } 938169689Skan} 939169689Skan 940169689Skan 941169689Skan/* Return true if {DEST.SRC} is an existing graph edge in GRAPH. */ 942169689Skan 943169689Skanstatic bool 944171825Skanvalid_graph_edge (constraint_graph_t graph, unsigned int src, 945169689Skan unsigned int dest) 946169689Skan{ 947171825Skan return (graph->succs[dest] 948171825Skan && bitmap_bit_p (graph->succs[dest], src)); 949169689Skan} 950169689Skan 951171825Skan/* Build the constraint graph, adding only predecessor edges right now. */ 952169689Skan 953169689Skanstatic void 954171825Skanbuild_pred_graph (void) 955169689Skan{ 956171825Skan int i; 957169689Skan constraint_t c; 958171825Skan unsigned int j; 959169689Skan 960169689Skan graph = XNEW (struct constraint_graph); 961171825Skan graph->size = (VEC_length (varinfo_t, varmap)) * 3; 962171825Skan graph->succs = XCNEWVEC (bitmap, graph->size); 963171825Skan graph->implicit_preds = XCNEWVEC (bitmap, graph->size); 964171825Skan graph->preds = XCNEWVEC (bitmap, graph->size); 965171825Skan graph->indirect_cycles = XNEWVEC (int, VEC_length (varinfo_t, varmap)); 966171825Skan graph->label = XCNEWVEC (unsigned int, graph->size); 967171825Skan graph->rep = XNEWVEC (unsigned int, graph->size); 968171825Skan graph->eq_rep = XNEWVEC (int, graph->size); 969171825Skan graph->complex = XCNEWVEC (VEC(constraint_t, heap) *, 970171825Skan VEC_length (varinfo_t, varmap)); 971171825Skan graph->direct_nodes = sbitmap_alloc (graph->size); 972171825Skan sbitmap_zero (graph->direct_nodes); 973169689Skan 974171825Skan for (j = 0; j < FIRST_REF_NODE; j++) 975171825Skan { 976171825Skan if (!get_varinfo (j)->is_special_var) 977171825Skan SET_BIT (graph->direct_nodes, j); 978171825Skan } 979171825Skan 980171825Skan for (j = 0; j < graph->size; j++) 981171825Skan { 982171825Skan graph->rep[j] = j; 983171825Skan graph->eq_rep[j] = -1; 984171825Skan } 985171825Skan 986171825Skan for (j = 0; j < VEC_length (varinfo_t, varmap); j++) 987171825Skan graph->indirect_cycles[j] = -1; 988171825Skan 989169689Skan for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) 990169689Skan { 991169689Skan struct constraint_expr lhs = c->lhs; 992169689Skan struct constraint_expr rhs = c->rhs; 993169689Skan unsigned int lhsvar = get_varinfo_fc (lhs.var)->id; 994169689Skan unsigned int rhsvar = get_varinfo_fc (rhs.var)->id; 995169689Skan 996169689Skan if (lhs.type == DEREF) 997169689Skan { 998171825Skan /* *x = y. */ 999171825Skan if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR) 1000171825Skan add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); 1001171825Skan if (rhs.type == ADDRESSOF) 1002171825Skan RESET_BIT (graph->direct_nodes, rhsvar); 1003169689Skan } 1004169689Skan else if (rhs.type == DEREF) 1005169689Skan { 1006171825Skan /* x = *y */ 1007171825Skan if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR) 1008171825Skan add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar); 1009171825Skan else 1010171825Skan RESET_BIT (graph->direct_nodes, lhsvar); 1011169689Skan } 1012169689Skan else if (rhs.type == ADDRESSOF) 1013169689Skan { 1014169689Skan /* x = &y */ 1015171825Skan add_pred_graph_edge (graph, lhsvar, FIRST_ADDR_NODE + rhsvar); 1016171825Skan /* Implicitly, *x = y */ 1017171825Skan add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); 1018171825Skan 1019171825Skan RESET_BIT (graph->direct_nodes, rhsvar); 1020171825Skan } 1021171825Skan else if (lhsvar > anything_id 1022171825Skan && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0) 1023171825Skan { 1024171825Skan /* x = y */ 1025171825Skan add_pred_graph_edge (graph, lhsvar, rhsvar); 1026171825Skan /* Implicitly, *x = *y */ 1027171825Skan add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, 1028171825Skan FIRST_REF_NODE + rhsvar); 1029171825Skan } 1030171825Skan else if (lhs.offset != 0 || rhs.offset != 0) 1031171825Skan { 1032171825Skan if (rhs.offset != 0) 1033171825Skan RESET_BIT (graph->direct_nodes, lhs.var); 1034171825Skan if (lhs.offset != 0) 1035171825Skan RESET_BIT (graph->direct_nodes, rhs.var); 1036171825Skan } 1037171825Skan } 1038171825Skan} 1039171825Skan 1040171825Skan/* Build the constraint graph, adding successor edges. */ 1041171825Skan 1042171825Skanstatic void 1043171825Skanbuild_succ_graph (void) 1044171825Skan{ 1045171825Skan int i; 1046171825Skan constraint_t c; 1047171825Skan 1048171825Skan for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) 1049171825Skan { 1050171825Skan struct constraint_expr lhs; 1051171825Skan struct constraint_expr rhs; 1052171825Skan unsigned int lhsvar; 1053171825Skan unsigned int rhsvar; 1054171825Skan 1055171825Skan if (!c) 1056171825Skan continue; 1057171825Skan 1058171825Skan lhs = c->lhs; 1059171825Skan rhs = c->rhs; 1060171825Skan lhsvar = find (get_varinfo_fc (lhs.var)->id); 1061171825Skan rhsvar = find (get_varinfo_fc (rhs.var)->id); 1062171825Skan 1063171825Skan if (lhs.type == DEREF) 1064171825Skan { 1065171825Skan if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR) 1066171825Skan add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); 1067171825Skan } 1068171825Skan else if (rhs.type == DEREF) 1069171825Skan { 1070171825Skan if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR) 1071171825Skan add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar); 1072171825Skan } 1073171825Skan else if (rhs.type == ADDRESSOF) 1074171825Skan { 1075171825Skan /* x = &y */ 1076171825Skan gcc_assert (find (get_varinfo_fc (rhs.var)->id) 1077171825Skan == get_varinfo_fc (rhs.var)->id); 1078169689Skan bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar); 1079169689Skan } 1080171825Skan else if (lhsvar > anything_id 1081171825Skan && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0) 1082169689Skan { 1083171825Skan add_graph_edge (graph, lhsvar, rhsvar); 1084169689Skan } 1085169689Skan } 1086169689Skan} 1087169689Skan 1088169689Skan 1089169689Skan/* Changed variables on the last iteration. */ 1090169689Skanstatic unsigned int changed_count; 1091169689Skanstatic sbitmap changed; 1092169689Skan 1093169689SkanDEF_VEC_I(unsigned); 1094169689SkanDEF_VEC_ALLOC_I(unsigned,heap); 1095169689Skan 1096169689Skan 1097169689Skan/* Strongly Connected Component visitation info. */ 1098169689Skan 1099169689Skanstruct scc_info 1100169689Skan{ 1101169689Skan sbitmap visited; 1102171825Skan sbitmap roots; 1103171825Skan unsigned int *dfs; 1104171825Skan unsigned int *node_mapping; 1105169689Skan int current_index; 1106169689Skan VEC(unsigned,heap) *scc_stack; 1107169689Skan}; 1108169689Skan 1109169689Skan 1110169689Skan/* Recursive routine to find strongly connected components in GRAPH. 1111169689Skan SI is the SCC info to store the information in, and N is the id of current 1112169689Skan graph node we are processing. 1113171825Skan 1114169689Skan This is Tarjan's strongly connected component finding algorithm, as 1115171825Skan modified by Nuutila to keep only non-root nodes on the stack. 1116169689Skan The algorithm can be found in "On finding the strongly connected 1117169689Skan connected components in a directed graph" by Esko Nuutila and Eljas 1118169689Skan Soisalon-Soininen, in Information Processing Letters volume 49, 1119169689Skan number 1, pages 9-14. */ 1120169689Skan 1121169689Skanstatic void 1122169689Skanscc_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n) 1123169689Skan{ 1124169689Skan unsigned int i; 1125169689Skan bitmap_iterator bi; 1126171825Skan unsigned int my_dfs; 1127169689Skan 1128169689Skan SET_BIT (si->visited, n); 1129171825Skan si->dfs[n] = si->current_index ++; 1130171825Skan my_dfs = si->dfs[n]; 1131171825Skan 1132169689Skan /* Visit all the successors. */ 1133171825Skan EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi) 1134169689Skan { 1135171825Skan unsigned int w; 1136171825Skan 1137171825Skan if (i > LAST_REF_NODE) 1138171825Skan break; 1139171825Skan 1140171825Skan w = find (i); 1141171825Skan if (TEST_BIT (si->roots, w)) 1142171825Skan continue; 1143171825Skan 1144169689Skan if (!TEST_BIT (si->visited, w)) 1145169689Skan scc_visit (graph, si, w); 1146171825Skan { 1147171825Skan unsigned int t = find (w); 1148171825Skan unsigned int nnode = find (n); 1149171825Skan gcc_assert (nnode == n); 1150171825Skan 1151171825Skan if (si->dfs[t] < si->dfs[nnode]) 1152171825Skan si->dfs[n] = si->dfs[t]; 1153171825Skan } 1154169689Skan } 1155171825Skan 1156169689Skan /* See if any components have been identified. */ 1157171825Skan if (si->dfs[n] == my_dfs) 1158169689Skan { 1159171825Skan if (VEC_length (unsigned, si->scc_stack) > 0 1160171825Skan && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs) 1161169689Skan { 1162171825Skan bitmap scc = BITMAP_ALLOC (NULL); 1163171825Skan bool have_ref_node = n >= FIRST_REF_NODE; 1164171825Skan unsigned int lowest_node; 1165171825Skan bitmap_iterator bi; 1166169689Skan 1167171825Skan bitmap_set_bit (scc, n); 1168169689Skan 1169171825Skan while (VEC_length (unsigned, si->scc_stack) != 0 1170171825Skan && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs) 1171171825Skan { 1172171825Skan unsigned int w = VEC_pop (unsigned, si->scc_stack); 1173169689Skan 1174171825Skan bitmap_set_bit (scc, w); 1175171825Skan if (w >= FIRST_REF_NODE) 1176171825Skan have_ref_node = true; 1177171825Skan } 1178169689Skan 1179171825Skan lowest_node = bitmap_first_set_bit (scc); 1180171825Skan gcc_assert (lowest_node < FIRST_REF_NODE); 1181171825Skan EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi) 1182171825Skan { 1183171825Skan if (i < FIRST_REF_NODE) 1184171825Skan { 1185171825Skan /* Mark this node for collapsing. */ 1186171825Skan if (unite (lowest_node, i)) 1187171825Skan unify_nodes (graph, lowest_node, i, false); 1188171825Skan } 1189171825Skan else 1190171825Skan { 1191171825Skan unite (lowest_node, i); 1192171825Skan graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node; 1193171825Skan } 1194171825Skan } 1195169689Skan } 1196171825Skan SET_BIT (si->roots, n); 1197169689Skan } 1198171825Skan else 1199171825Skan VEC_safe_push (unsigned, heap, si->scc_stack, n); 1200169689Skan} 1201169689Skan 1202171825Skan/* Unify node FROM into node TO, updating the changed count if 1203171825Skan necessary when UPDATE_CHANGED is true. */ 1204169689Skan 1205169689Skanstatic void 1206171825Skanunify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from, 1207171825Skan bool update_changed) 1208169689Skan{ 1209169689Skan 1210171825Skan gcc_assert (to != from && find (to) == to); 1211171825Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1212171825Skan fprintf (dump_file, "Unifying %s to %s\n", 1213171825Skan get_varinfo (from)->name, 1214171825Skan get_varinfo (to)->name); 1215169689Skan 1216171825Skan if (update_changed) 1217171825Skan stats.unified_vars_dynamic++; 1218171825Skan else 1219171825Skan stats.unified_vars_static++; 1220169689Skan 1221171825Skan merge_graph_nodes (graph, to, from); 1222171825Skan merge_node_constraints (graph, to, from); 1223169689Skan 1224171825Skan if (update_changed && TEST_BIT (changed, from)) 1225169689Skan { 1226171825Skan RESET_BIT (changed, from); 1227171825Skan if (!TEST_BIT (changed, to)) 1228171825Skan SET_BIT (changed, to); 1229169689Skan else 1230169689Skan { 1231171825Skan gcc_assert (changed_count > 0); 1232171825Skan changed_count--; 1233169689Skan } 1234171825Skan } 1235169689Skan 1236171825Skan /* If the solution changes because of the merging, we need to mark 1237171825Skan the variable as changed. */ 1238171825Skan if (bitmap_ior_into (get_varinfo (to)->solution, 1239171825Skan get_varinfo (from)->solution)) 1240171825Skan { 1241171825Skan if (update_changed && !TEST_BIT (changed, to)) 1242169689Skan { 1243171825Skan SET_BIT (changed, to); 1244171825Skan changed_count++; 1245169689Skan } 1246169689Skan } 1247171825Skan 1248171825Skan BITMAP_FREE (get_varinfo (from)->solution); 1249171825Skan BITMAP_FREE (get_varinfo (from)->oldsolution); 1250171825Skan 1251171825Skan if (stats.iterations > 0) 1252171825Skan { 1253171825Skan BITMAP_FREE (get_varinfo (to)->oldsolution); 1254171825Skan get_varinfo (to)->oldsolution = BITMAP_ALLOC (&oldpta_obstack); 1255171825Skan } 1256171825Skan 1257171825Skan if (valid_graph_edge (graph, to, to)) 1258171825Skan { 1259171825Skan if (graph->succs[to]) 1260171825Skan bitmap_clear_bit (graph->succs[to], to); 1261171825Skan } 1262169689Skan} 1263169689Skan 1264169689Skan/* Information needed to compute the topological ordering of a graph. */ 1265169689Skan 1266169689Skanstruct topo_info 1267169689Skan{ 1268169689Skan /* sbitmap of visited nodes. */ 1269169689Skan sbitmap visited; 1270169689Skan /* Array that stores the topological order of the graph, *in 1271169689Skan reverse*. */ 1272169689Skan VEC(unsigned,heap) *topo_order; 1273169689Skan}; 1274169689Skan 1275169689Skan 1276169689Skan/* Initialize and return a topological info structure. */ 1277169689Skan 1278169689Skanstatic struct topo_info * 1279169689Skaninit_topo_info (void) 1280169689Skan{ 1281169689Skan size_t size = VEC_length (varinfo_t, varmap); 1282169689Skan struct topo_info *ti = XNEW (struct topo_info); 1283169689Skan ti->visited = sbitmap_alloc (size); 1284169689Skan sbitmap_zero (ti->visited); 1285169689Skan ti->topo_order = VEC_alloc (unsigned, heap, 1); 1286169689Skan return ti; 1287169689Skan} 1288169689Skan 1289169689Skan 1290169689Skan/* Free the topological sort info pointed to by TI. */ 1291169689Skan 1292169689Skanstatic void 1293169689Skanfree_topo_info (struct topo_info *ti) 1294169689Skan{ 1295169689Skan sbitmap_free (ti->visited); 1296169689Skan VEC_free (unsigned, heap, ti->topo_order); 1297169689Skan free (ti); 1298169689Skan} 1299169689Skan 1300169689Skan/* Visit the graph in topological order, and store the order in the 1301169689Skan topo_info structure. */ 1302169689Skan 1303169689Skanstatic void 1304169689Skantopo_visit (constraint_graph_t graph, struct topo_info *ti, 1305169689Skan unsigned int n) 1306169689Skan{ 1307169689Skan bitmap_iterator bi; 1308169689Skan unsigned int j; 1309169689Skan 1310169689Skan SET_BIT (ti->visited, n); 1311169689Skan 1312171825Skan if (graph->succs[n]) 1313171825Skan EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi) 1314169689Skan { 1315169689Skan if (!TEST_BIT (ti->visited, j)) 1316169689Skan topo_visit (graph, ti, j); 1317169689Skan } 1318171825Skan 1319169689Skan VEC_safe_push (unsigned, heap, ti->topo_order, n); 1320169689Skan} 1321169689Skan 1322169689Skan/* Return true if variable N + OFFSET is a legal field of N. */ 1323169689Skan 1324171825Skanstatic bool 1325169689Skantype_safe (unsigned int n, unsigned HOST_WIDE_INT *offset) 1326169689Skan{ 1327169689Skan varinfo_t ninfo = get_varinfo (n); 1328169689Skan 1329169689Skan /* For things we've globbed to single variables, any offset into the 1330169689Skan variable acts like the entire variable, so that it becomes offset 1331169689Skan 0. */ 1332169689Skan if (ninfo->is_special_var 1333169689Skan || ninfo->is_artificial_var 1334169689Skan || ninfo->is_unknown_size_var) 1335169689Skan { 1336169689Skan *offset = 0; 1337169689Skan return true; 1338169689Skan } 1339169689Skan return (get_varinfo (n)->offset + *offset) < get_varinfo (n)->fullsize; 1340169689Skan} 1341169689Skan 1342169689Skan/* Process a constraint C that represents *x = &y. */ 1343169689Skan 1344169689Skanstatic void 1345169689Skando_da_constraint (constraint_graph_t graph ATTRIBUTE_UNUSED, 1346169689Skan constraint_t c, bitmap delta) 1347169689Skan{ 1348169689Skan unsigned int rhs = c->rhs.var; 1349169689Skan unsigned int j; 1350169689Skan bitmap_iterator bi; 1351169689Skan 1352169689Skan /* For each member j of Delta (Sol(x)), add x to Sol(j) */ 1353169689Skan EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) 1354169689Skan { 1355169689Skan unsigned HOST_WIDE_INT offset = c->lhs.offset; 1356169689Skan if (type_safe (j, &offset) && !(get_varinfo (j)->is_special_var)) 1357169689Skan { 1358169689Skan /* *x != NULL && *x != ANYTHING*/ 1359169689Skan varinfo_t v; 1360169689Skan unsigned int t; 1361169689Skan bitmap sol; 1362169689Skan unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + offset; 1363169689Skan 1364169689Skan v = first_vi_for_offset (get_varinfo (j), fieldoffset); 1365169689Skan if (!v) 1366169689Skan continue; 1367171825Skan t = find (v->id); 1368169689Skan sol = get_varinfo (t)->solution; 1369169689Skan if (!bitmap_bit_p (sol, rhs)) 1370171825Skan { 1371169689Skan bitmap_set_bit (sol, rhs); 1372169689Skan if (!TEST_BIT (changed, t)) 1373169689Skan { 1374169689Skan SET_BIT (changed, t); 1375169689Skan changed_count++; 1376169689Skan } 1377169689Skan } 1378169689Skan } 1379169689Skan else if (0 && dump_file && !(get_varinfo (j)->is_special_var)) 1380169689Skan fprintf (dump_file, "Untypesafe usage in do_da_constraint.\n"); 1381171825Skan 1382169689Skan } 1383169689Skan} 1384169689Skan 1385169689Skan/* Process a constraint C that represents x = *y, using DELTA as the 1386169689Skan starting solution. */ 1387169689Skan 1388169689Skanstatic void 1389169689Skando_sd_constraint (constraint_graph_t graph, constraint_t c, 1390169689Skan bitmap delta) 1391169689Skan{ 1392171825Skan unsigned int lhs = find (c->lhs.var); 1393169689Skan bool flag = false; 1394169689Skan bitmap sol = get_varinfo (lhs)->solution; 1395169689Skan unsigned int j; 1396169689Skan bitmap_iterator bi; 1397169689Skan 1398169689Skan if (bitmap_bit_p (delta, anything_id)) 1399169689Skan { 1400169689Skan flag = !bitmap_bit_p (sol, anything_id); 1401169689Skan if (flag) 1402169689Skan bitmap_set_bit (sol, anything_id); 1403169689Skan goto done; 1404169689Skan } 1405171825Skan /* For each variable j in delta (Sol(y)), add 1406169689Skan an edge in the graph from j to x, and union Sol(j) into Sol(x). */ 1407169689Skan EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) 1408169689Skan { 1409169689Skan unsigned HOST_WIDE_INT roffset = c->rhs.offset; 1410169689Skan if (type_safe (j, &roffset)) 1411169689Skan { 1412169689Skan varinfo_t v; 1413169689Skan unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + roffset; 1414169689Skan unsigned int t; 1415169689Skan 1416169689Skan v = first_vi_for_offset (get_varinfo (j), fieldoffset); 1417169689Skan if (!v) 1418169689Skan continue; 1419171825Skan t = find (v->id); 1420169689Skan 1421169689Skan /* Adding edges from the special vars is pointless. 1422169689Skan They don't have sets that can change. */ 1423169689Skan if (get_varinfo (t) ->is_special_var) 1424169689Skan flag |= bitmap_ior_into (sol, get_varinfo (t)->solution); 1425171825Skan else if (add_graph_edge (graph, lhs, t)) 1426169689Skan flag |= bitmap_ior_into (sol, get_varinfo (t)->solution); 1427169689Skan } 1428169689Skan else if (0 && dump_file && !(get_varinfo (j)->is_special_var)) 1429169689Skan fprintf (dump_file, "Untypesafe usage in do_sd_constraint\n"); 1430171825Skan 1431169689Skan } 1432169689Skan 1433169689Skandone: 1434169689Skan /* If the LHS solution changed, mark the var as changed. */ 1435169689Skan if (flag) 1436169689Skan { 1437169689Skan get_varinfo (lhs)->solution = sol; 1438169689Skan if (!TEST_BIT (changed, lhs)) 1439169689Skan { 1440169689Skan SET_BIT (changed, lhs); 1441169689Skan changed_count++; 1442169689Skan } 1443171825Skan } 1444169689Skan} 1445169689Skan 1446169689Skan/* Process a constraint C that represents *x = y. */ 1447169689Skan 1448169689Skanstatic void 1449171825Skando_ds_constraint (constraint_t c, bitmap delta) 1450169689Skan{ 1451171825Skan unsigned int rhs = find (c->rhs.var); 1452169689Skan unsigned HOST_WIDE_INT roff = c->rhs.offset; 1453169689Skan bitmap sol = get_varinfo (rhs)->solution; 1454169689Skan unsigned int j; 1455169689Skan bitmap_iterator bi; 1456169689Skan 1457169689Skan if (bitmap_bit_p (sol, anything_id)) 1458169689Skan { 1459169689Skan EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) 1460169689Skan { 1461169689Skan varinfo_t jvi = get_varinfo (j); 1462169689Skan unsigned int t; 1463169689Skan unsigned int loff = c->lhs.offset; 1464169689Skan unsigned HOST_WIDE_INT fieldoffset = jvi->offset + loff; 1465169689Skan varinfo_t v; 1466169689Skan 1467169689Skan v = first_vi_for_offset (get_varinfo (j), fieldoffset); 1468169689Skan if (!v) 1469169689Skan continue; 1470171825Skan t = find (v->id); 1471171825Skan 1472169689Skan if (!bitmap_bit_p (get_varinfo (t)->solution, anything_id)) 1473169689Skan { 1474169689Skan bitmap_set_bit (get_varinfo (t)->solution, anything_id); 1475169689Skan if (!TEST_BIT (changed, t)) 1476169689Skan { 1477169689Skan SET_BIT (changed, t); 1478169689Skan changed_count++; 1479169689Skan } 1480169689Skan } 1481169689Skan } 1482169689Skan return; 1483169689Skan } 1484169689Skan 1485169689Skan /* For each member j of delta (Sol(x)), add an edge from y to j and 1486169689Skan union Sol(y) into Sol(j) */ 1487169689Skan EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) 1488169689Skan { 1489169689Skan unsigned HOST_WIDE_INT loff = c->lhs.offset; 1490171825Skan if (type_safe (j, &loff) && !(get_varinfo (j)->is_special_var)) 1491169689Skan { 1492169689Skan varinfo_t v; 1493169689Skan unsigned int t; 1494169689Skan unsigned HOST_WIDE_INT fieldoffset = get_varinfo (j)->offset + loff; 1495171825Skan bitmap tmp; 1496169689Skan 1497169689Skan v = first_vi_for_offset (get_varinfo (j), fieldoffset); 1498169689Skan if (!v) 1499169689Skan continue; 1500171825Skan t = find (v->id); 1501171825Skan tmp = get_varinfo (t)->solution; 1502171825Skan 1503171825Skan if (set_union_with_increment (tmp, sol, roff)) 1504169689Skan { 1505171825Skan get_varinfo (t)->solution = tmp; 1506171825Skan if (t == rhs) 1507171825Skan sol = get_varinfo (rhs)->solution; 1508171825Skan if (!TEST_BIT (changed, t)) 1509169689Skan { 1510171825Skan SET_BIT (changed, t); 1511171825Skan changed_count++; 1512169689Skan } 1513169689Skan } 1514171825Skan } 1515169689Skan else if (0 && dump_file && !(get_varinfo (j)->is_special_var)) 1516169689Skan fprintf (dump_file, "Untypesafe usage in do_ds_constraint\n"); 1517169689Skan } 1518169689Skan} 1519169689Skan 1520171825Skan/* Handle a non-simple (simple meaning requires no iteration), 1521171825Skan constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */ 1522171825Skan 1523169689Skanstatic void 1524169689Skando_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta) 1525169689Skan{ 1526169689Skan if (c->lhs.type == DEREF) 1527169689Skan { 1528169689Skan if (c->rhs.type == ADDRESSOF) 1529169689Skan { 1530169689Skan /* *x = &y */ 1531169689Skan do_da_constraint (graph, c, delta); 1532169689Skan } 1533169689Skan else 1534169689Skan { 1535169689Skan /* *x = y */ 1536171825Skan do_ds_constraint (c, delta); 1537169689Skan } 1538169689Skan } 1539171825Skan else if (c->rhs.type == DEREF) 1540169689Skan { 1541169689Skan /* x = *y */ 1542169689Skan if (!(get_varinfo (c->lhs.var)->is_special_var)) 1543169689Skan do_sd_constraint (graph, c, delta); 1544169689Skan } 1545171825Skan else 1546171825Skan { 1547171825Skan bitmap tmp; 1548171825Skan bitmap solution; 1549171825Skan bool flag = false; 1550171825Skan unsigned int t; 1551171825Skan 1552171825Skan gcc_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR); 1553171825Skan t = find (c->rhs.var); 1554171825Skan solution = get_varinfo (t)->solution; 1555171825Skan t = find (c->lhs.var); 1556171825Skan tmp = get_varinfo (t)->solution; 1557171825Skan 1558171825Skan flag = set_union_with_increment (tmp, solution, c->rhs.offset); 1559171825Skan 1560171825Skan if (flag) 1561171825Skan { 1562171825Skan get_varinfo (t)->solution = tmp; 1563171825Skan if (!TEST_BIT (changed, t)) 1564171825Skan { 1565171825Skan SET_BIT (changed, t); 1566171825Skan changed_count++; 1567171825Skan } 1568171825Skan } 1569171825Skan } 1570169689Skan} 1571169689Skan 1572169689Skan/* Initialize and return a new SCC info structure. */ 1573169689Skan 1574169689Skanstatic struct scc_info * 1575171825Skaninit_scc_info (size_t size) 1576169689Skan{ 1577169689Skan struct scc_info *si = XNEW (struct scc_info); 1578171825Skan size_t i; 1579169689Skan 1580169689Skan si->current_index = 0; 1581169689Skan si->visited = sbitmap_alloc (size); 1582169689Skan sbitmap_zero (si->visited); 1583171825Skan si->roots = sbitmap_alloc (size); 1584171825Skan sbitmap_zero (si->roots); 1585171825Skan si->node_mapping = XNEWVEC (unsigned int, size); 1586171825Skan si->dfs = XCNEWVEC (unsigned int, size); 1587171825Skan 1588171825Skan for (i = 0; i < size; i++) 1589171825Skan si->node_mapping[i] = i; 1590171825Skan 1591169689Skan si->scc_stack = VEC_alloc (unsigned, heap, 1); 1592169689Skan return si; 1593169689Skan} 1594169689Skan 1595169689Skan/* Free an SCC info structure pointed to by SI */ 1596169689Skan 1597169689Skanstatic void 1598169689Skanfree_scc_info (struct scc_info *si) 1599171825Skan{ 1600169689Skan sbitmap_free (si->visited); 1601171825Skan sbitmap_free (si->roots); 1602171825Skan free (si->node_mapping); 1603171825Skan free (si->dfs); 1604169689Skan VEC_free (unsigned, heap, si->scc_stack); 1605171825Skan free (si); 1606169689Skan} 1607169689Skan 1608169689Skan 1609171825Skan/* Find indirect cycles in GRAPH that occur, using strongly connected 1610171825Skan components, and note them in the indirect cycles map. 1611169689Skan 1612171825Skan This technique comes from Ben Hardekopf and Calvin Lin, 1613171825Skan "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of 1614171825Skan Lines of Code", submitted to PLDI 2007. */ 1615171825Skan 1616169689Skanstatic void 1617171825Skanfind_indirect_cycles (constraint_graph_t graph) 1618169689Skan{ 1619169689Skan unsigned int i; 1620171825Skan unsigned int size = graph->size; 1621171825Skan struct scc_info *si = init_scc_info (size); 1622169689Skan 1623171825Skan for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ ) 1624171825Skan if (!TEST_BIT (si->visited, i) && find (i) == i) 1625169689Skan scc_visit (graph, si, i); 1626171825Skan 1627169689Skan free_scc_info (si); 1628169689Skan} 1629169689Skan 1630169689Skan/* Compute a topological ordering for GRAPH, and store the result in the 1631169689Skan topo_info structure TI. */ 1632169689Skan 1633171825Skanstatic void 1634169689Skancompute_topo_order (constraint_graph_t graph, 1635169689Skan struct topo_info *ti) 1636169689Skan{ 1637169689Skan unsigned int i; 1638169689Skan unsigned int size = VEC_length (varinfo_t, varmap); 1639171825Skan 1640169689Skan for (i = 0; i != size; ++i) 1641171825Skan if (!TEST_BIT (ti->visited, i) && find (i) == i) 1642169689Skan topo_visit (graph, ti, i); 1643169689Skan} 1644169689Skan 1645171825Skan/* Perform offline variable substitution. 1646169689Skan 1647169689Skan This is a linear time way of identifying variables that must have 1648169689Skan equivalent points-to sets, including those caused by static cycles, 1649169689Skan and single entry subgraphs, in the constraint graph. 1650169689Skan 1651169689Skan The technique is described in "Off-line variable substitution for 1652169689Skan scaling points-to analysis" by Atanas Rountev and Satish Chandra, 1653171825Skan in "ACM SIGPLAN Notices" volume 35, number 5, pages 47-56. 1654169689Skan 1655171825Skan There is an optimal way to do this involving hash based value 1656171825Skan numbering, once the technique is published i will implement it 1657171825Skan here. 1658171825Skan 1659171825Skan The general method of finding equivalence classes is as follows: 1660171825Skan Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints. 1661171825Skan Add fake nodes (ADDRESS nodes) and edges for a = &b constraints. 1662171825Skan Initialize all non-REF/ADDRESS nodes to be direct nodes 1663171825Skan For each SCC in the predecessor graph: 1664171825Skan for each member (x) of the SCC 1665171825Skan if x is not a direct node: 1666171825Skan set rootnode(SCC) to be not a direct node 1667171825Skan collapse node x into rootnode(SCC). 1668171825Skan if rootnode(SCC) is not a direct node: 1669171825Skan label rootnode(SCC) with a new equivalence class 1670171825Skan else: 1671171825Skan if all labeled predecessors of rootnode(SCC) have the same 1672171825Skan label: 1673171825Skan label rootnode(SCC) with this label 1674171825Skan else: 1675171825Skan label rootnode(SCC) with a new equivalence class 1676171825Skan 1677171825Skan All direct nodes with the same equivalence class can be replaced 1678171825Skan with a single representative node. 1679171825Skan All unlabeled nodes (label == 0) are not pointers and all edges 1680171825Skan involving them can be eliminated. 1681171825Skan We perform these optimizations during move_complex_constraints. 1682171825Skan*/ 1683171825Skan 1684171825Skanstatic int equivalence_class; 1685171825Skan 1686171825Skan/* Recursive routine to find strongly connected components in GRAPH, 1687171825Skan and label it's nodes with equivalence classes. 1688171825Skan This is used during variable substitution to find cycles involving 1689171825Skan the regular or implicit predecessors, and label them as equivalent. 1690171825Skan The SCC finding algorithm used is the same as that for scc_visit. */ 1691171825Skan 1692169689Skanstatic void 1693171825Skanlabel_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n) 1694169689Skan{ 1695171825Skan unsigned int i; 1696171825Skan bitmap_iterator bi; 1697171825Skan unsigned int my_dfs; 1698171825Skan 1699171825Skan gcc_assert (si->node_mapping[n] == n); 1700171825Skan SET_BIT (si->visited, n); 1701171825Skan si->dfs[n] = si->current_index ++; 1702171825Skan my_dfs = si->dfs[n]; 1703171825Skan 1704171825Skan /* Visit all the successors. */ 1705171825Skan EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) 1706169689Skan { 1707171825Skan unsigned int w = si->node_mapping[i]; 1708169689Skan 1709171825Skan if (TEST_BIT (si->roots, w)) 1710169689Skan continue; 1711169689Skan 1712171825Skan if (!TEST_BIT (si->visited, w)) 1713171825Skan label_visit (graph, si, w); 1714171825Skan { 1715171825Skan unsigned int t = si->node_mapping[w]; 1716171825Skan unsigned int nnode = si->node_mapping[n]; 1717171825Skan gcc_assert (nnode == n); 1718169689Skan 1719171825Skan if (si->dfs[t] < si->dfs[nnode]) 1720171825Skan si->dfs[n] = si->dfs[t]; 1721171825Skan } 1722171825Skan } 1723169689Skan 1724171825Skan /* Visit all the implicit predecessors. */ 1725171825Skan EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi) 1726171825Skan { 1727171825Skan unsigned int w = si->node_mapping[i]; 1728169689Skan 1729171825Skan if (TEST_BIT (si->roots, w)) 1730171825Skan continue; 1731169689Skan 1732171825Skan if (!TEST_BIT (si->visited, w)) 1733171825Skan label_visit (graph, si, w); 1734171825Skan { 1735171825Skan unsigned int t = si->node_mapping[w]; 1736171825Skan unsigned int nnode = si->node_mapping[n]; 1737171825Skan gcc_assert (nnode == n); 1738169689Skan 1739171825Skan if (si->dfs[t] < si->dfs[nnode]) 1740171825Skan si->dfs[n] = si->dfs[t]; 1741171825Skan } 1742171825Skan } 1743169689Skan 1744171825Skan /* See if any components have been identified. */ 1745171825Skan if (si->dfs[n] == my_dfs) 1746171825Skan { 1747171825Skan while (VEC_length (unsigned, si->scc_stack) != 0 1748171825Skan && si->dfs[VEC_last (unsigned, si->scc_stack)] >= my_dfs) 1749171825Skan { 1750171825Skan unsigned int w = VEC_pop (unsigned, si->scc_stack); 1751171825Skan si->node_mapping[w] = n; 1752169689Skan 1753171825Skan if (!TEST_BIT (graph->direct_nodes, w)) 1754171825Skan RESET_BIT (graph->direct_nodes, n); 1755171825Skan } 1756171825Skan SET_BIT (si->roots, n); 1757171825Skan 1758171825Skan if (!TEST_BIT (graph->direct_nodes, n)) 1759169689Skan { 1760171825Skan graph->label[n] = equivalence_class++; 1761171825Skan } 1762171825Skan else 1763171825Skan { 1764171825Skan unsigned int size = 0; 1765171825Skan unsigned int firstlabel = ~0; 1766171825Skan 1767171825Skan EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) 1768171825Skan { 1769171825Skan unsigned int j = si->node_mapping[i]; 1770171825Skan 1771171825Skan if (j == n || graph->label[j] == 0) 1772171825Skan continue; 1773171825Skan 1774171825Skan if (firstlabel == (unsigned int)~0) 1775171825Skan { 1776171825Skan firstlabel = graph->label[j]; 1777171825Skan size++; 1778171825Skan } 1779171825Skan else if (graph->label[j] != firstlabel) 1780171825Skan size++; 1781171825Skan } 1782171825Skan 1783171825Skan if (size == 0) 1784171825Skan graph->label[n] = 0; 1785171825Skan else if (size == 1) 1786171825Skan graph->label[n] = firstlabel; 1787171825Skan else 1788171825Skan graph->label[n] = equivalence_class++; 1789171825Skan } 1790171825Skan } 1791171825Skan else 1792171825Skan VEC_safe_push (unsigned, heap, si->scc_stack, n); 1793171825Skan} 1794171825Skan 1795171825Skan/* Perform offline variable substitution, discovering equivalence 1796171825Skan classes, and eliminating non-pointer variables. */ 1797171825Skan 1798171825Skanstatic struct scc_info * 1799171825Skanperform_var_substitution (constraint_graph_t graph) 1800171825Skan{ 1801171825Skan unsigned int i; 1802171825Skan unsigned int size = graph->size; 1803171825Skan struct scc_info *si = init_scc_info (size); 1804171825Skan 1805171825Skan bitmap_obstack_initialize (&iteration_obstack); 1806171825Skan equivalence_class = 0; 1807171825Skan 1808171825Skan /* We only need to visit the non-address nodes for labeling 1809171825Skan purposes, as the address nodes will never have any predecessors, 1810171825Skan because &x never appears on the LHS of a constraint. */ 1811171825Skan for (i = 0; i < LAST_REF_NODE; i++) 1812171825Skan if (!TEST_BIT (si->visited, si->node_mapping[i])) 1813171825Skan label_visit (graph, si, si->node_mapping[i]); 1814171825Skan 1815171825Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1816171825Skan for (i = 0; i < FIRST_REF_NODE; i++) 1817171825Skan { 1818171825Skan bool direct_node = TEST_BIT (graph->direct_nodes, i); 1819171825Skan fprintf (dump_file, 1820171825Skan "Equivalence class for %s node id %d:%s is %d\n", 1821171825Skan direct_node ? "Direct node" : "Indirect node", i, 1822171825Skan get_varinfo (i)->name, 1823171825Skan graph->label[si->node_mapping[i]]); 1824171825Skan } 1825171825Skan 1826171825Skan /* Quickly eliminate our non-pointer variables. */ 1827171825Skan 1828171825Skan for (i = 0; i < FIRST_REF_NODE; i++) 1829171825Skan { 1830171825Skan unsigned int node = si->node_mapping[i]; 1831171825Skan 1832171825Skan if (graph->label[node] == 0 && TEST_BIT (graph->direct_nodes, node)) 1833171825Skan { 1834169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1835171825Skan fprintf (dump_file, 1836171825Skan "%s is a non-pointer variable, eliminating edges.\n", 1837171825Skan get_varinfo (node)->name); 1838171825Skan stats.nonpointer_vars++; 1839171825Skan clear_edges_for_node (graph, node); 1840169689Skan } 1841169689Skan } 1842171825Skan return si; 1843171825Skan} 1844169689Skan 1845171825Skan/* Free information that was only necessary for variable 1846171825Skan substitution. */ 1847171825Skan 1848171825Skanstatic void 1849171825Skanfree_var_substitution_info (struct scc_info *si) 1850171825Skan{ 1851171825Skan free_scc_info (si); 1852171825Skan free (graph->label); 1853171825Skan free (graph->eq_rep); 1854171825Skan sbitmap_free (graph->direct_nodes); 1855169689Skan bitmap_obstack_release (&iteration_obstack); 1856169689Skan} 1857169689Skan 1858171825Skan/* Return an existing node that is equivalent to NODE, which has 1859171825Skan equivalence class LABEL, if one exists. Return NODE otherwise. */ 1860171825Skan 1861171825Skanstatic unsigned int 1862171825Skanfind_equivalent_node (constraint_graph_t graph, 1863171825Skan unsigned int node, unsigned int label) 1864171825Skan{ 1865171825Skan /* If the address version of this variable is unused, we can 1866171825Skan substitute it for anything else with the same label. 1867171825Skan Otherwise, we know the pointers are equivalent, but not the 1868171825Skan locations. */ 1869171825Skan 1870171825Skan if (graph->label[FIRST_ADDR_NODE + node] == 0) 1871171825Skan { 1872171825Skan gcc_assert (label < graph->size); 1873171825Skan 1874171825Skan if (graph->eq_rep[label] != -1) 1875171825Skan { 1876171825Skan /* Unify the two variables since we know they are equivalent. */ 1877171825Skan if (unite (graph->eq_rep[label], node)) 1878171825Skan unify_nodes (graph, graph->eq_rep[label], node, false); 1879171825Skan return graph->eq_rep[label]; 1880171825Skan } 1881171825Skan else 1882171825Skan { 1883171825Skan graph->eq_rep[label] = node; 1884171825Skan } 1885171825Skan } 1886171825Skan return node; 1887171825Skan} 1888171825Skan 1889171825Skan/* Move complex constraints to the appropriate nodes, and collapse 1890171825Skan variables we've discovered are equivalent during variable 1891171825Skan substitution. SI is the SCC_INFO that is the result of 1892171825Skan perform_variable_substitution. */ 1893171825Skan 1894171825Skanstatic void 1895171825Skanmove_complex_constraints (constraint_graph_t graph, 1896171825Skan struct scc_info *si) 1897171825Skan{ 1898171825Skan int i; 1899171825Skan unsigned int j; 1900171825Skan constraint_t c; 1901171825Skan 1902171825Skan for (j = 0; j < graph->size; j++) 1903171825Skan gcc_assert (find (j) == j); 1904171825Skan 1905171825Skan for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) 1906171825Skan { 1907171825Skan struct constraint_expr lhs = c->lhs; 1908171825Skan struct constraint_expr rhs = c->rhs; 1909171825Skan unsigned int lhsvar = find (get_varinfo_fc (lhs.var)->id); 1910171825Skan unsigned int rhsvar = find (get_varinfo_fc (rhs.var)->id); 1911171825Skan unsigned int lhsnode, rhsnode; 1912171825Skan unsigned int lhslabel, rhslabel; 1913171825Skan 1914171825Skan lhsnode = si->node_mapping[lhsvar]; 1915171825Skan rhsnode = si->node_mapping[rhsvar]; 1916171825Skan lhslabel = graph->label[lhsnode]; 1917171825Skan rhslabel = graph->label[rhsnode]; 1918171825Skan 1919171825Skan /* See if it is really a non-pointer variable, and if so, ignore 1920171825Skan the constraint. */ 1921171825Skan if (lhslabel == 0) 1922171825Skan { 1923171825Skan if (!TEST_BIT (graph->direct_nodes, lhsnode)) 1924171825Skan lhslabel = graph->label[lhsnode] = equivalence_class++; 1925171825Skan else 1926171825Skan { 1927171825Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1928171825Skan { 1929171825Skan 1930171825Skan fprintf (dump_file, "%s is a non-pointer variable," 1931171825Skan "ignoring constraint:", 1932171825Skan get_varinfo (lhs.var)->name); 1933171825Skan dump_constraint (dump_file, c); 1934171825Skan } 1935171825Skan VEC_replace (constraint_t, constraints, i, NULL); 1936171825Skan continue; 1937171825Skan } 1938171825Skan } 1939171825Skan 1940171825Skan if (rhslabel == 0) 1941171825Skan { 1942171825Skan if (!TEST_BIT (graph->direct_nodes, rhsnode)) 1943171825Skan rhslabel = graph->label[rhsnode] = equivalence_class++; 1944171825Skan else 1945171825Skan { 1946171825Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1947171825Skan { 1948171825Skan 1949171825Skan fprintf (dump_file, "%s is a non-pointer variable," 1950171825Skan "ignoring constraint:", 1951171825Skan get_varinfo (rhs.var)->name); 1952171825Skan dump_constraint (dump_file, c); 1953171825Skan } 1954171825Skan VEC_replace (constraint_t, constraints, i, NULL); 1955171825Skan continue; 1956171825Skan } 1957171825Skan } 1958171825Skan 1959171825Skan lhsvar = find_equivalent_node (graph, lhsvar, lhslabel); 1960171825Skan rhsvar = find_equivalent_node (graph, rhsvar, rhslabel); 1961171825Skan c->lhs.var = lhsvar; 1962171825Skan c->rhs.var = rhsvar; 1963171825Skan 1964171825Skan if (lhs.type == DEREF) 1965171825Skan { 1966171825Skan if (rhs.type == ADDRESSOF || rhsvar > anything_id) 1967171825Skan insert_into_complex (graph, lhsvar, c); 1968171825Skan } 1969171825Skan else if (rhs.type == DEREF) 1970171825Skan { 1971171825Skan if (!(get_varinfo (lhsvar)->is_special_var)) 1972171825Skan insert_into_complex (graph, rhsvar, c); 1973171825Skan } 1974171825Skan else if (rhs.type != ADDRESSOF && lhsvar > anything_id 1975171825Skan && (lhs.offset != 0 || rhs.offset != 0)) 1976171825Skan { 1977171825Skan insert_into_complex (graph, rhsvar, c); 1978171825Skan } 1979171825Skan 1980171825Skan } 1981171825Skan} 1982171825Skan 1983171825Skan/* Eliminate indirect cycles involving NODE. Return true if NODE was 1984171825Skan part of an SCC, false otherwise. */ 1985171825Skan 1986171825Skanstatic bool 1987171825Skaneliminate_indirect_cycles (unsigned int node) 1988171825Skan{ 1989171825Skan if (graph->indirect_cycles[node] != -1 1990171825Skan && !bitmap_empty_p (get_varinfo (node)->solution)) 1991171825Skan { 1992171825Skan unsigned int i; 1993171825Skan VEC(unsigned,heap) *queue = NULL; 1994171825Skan int queuepos; 1995171825Skan unsigned int to = find (graph->indirect_cycles[node]); 1996171825Skan bitmap_iterator bi; 1997171825Skan 1998171825Skan /* We can't touch the solution set and call unify_nodes 1999171825Skan at the same time, because unify_nodes is going to do 2000171825Skan bitmap unions into it. */ 2001171825Skan 2002171825Skan EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi) 2003171825Skan { 2004171825Skan if (find (i) == i && i != to) 2005171825Skan { 2006171825Skan if (unite (to, i)) 2007171825Skan VEC_safe_push (unsigned, heap, queue, i); 2008171825Skan } 2009171825Skan } 2010171825Skan 2011171825Skan for (queuepos = 0; 2012171825Skan VEC_iterate (unsigned, queue, queuepos, i); 2013171825Skan queuepos++) 2014171825Skan { 2015171825Skan unify_nodes (graph, to, i, true); 2016171825Skan } 2017171825Skan VEC_free (unsigned, heap, queue); 2018171825Skan return true; 2019171825Skan } 2020171825Skan return false; 2021171825Skan} 2022171825Skan 2023169689Skan/* Solve the constraint graph GRAPH using our worklist solver. 2024169689Skan This is based on the PW* family of solvers from the "Efficient Field 2025169689Skan Sensitive Pointer Analysis for C" paper. 2026169689Skan It works by iterating over all the graph nodes, processing the complex 2027169689Skan constraints and propagating the copy constraints, until everything stops 2028169689Skan changed. This corresponds to steps 6-8 in the solving list given above. */ 2029169689Skan 2030169689Skanstatic void 2031169689Skansolve_graph (constraint_graph_t graph) 2032169689Skan{ 2033169689Skan unsigned int size = VEC_length (varinfo_t, varmap); 2034169689Skan unsigned int i; 2035171825Skan bitmap pts; 2036169689Skan 2037171825Skan changed_count = 0; 2038169689Skan changed = sbitmap_alloc (size); 2039171825Skan sbitmap_zero (changed); 2040171825Skan 2041171825Skan /* Mark all initial non-collapsed nodes as changed. */ 2042169689Skan for (i = 0; i < size; i++) 2043171825Skan { 2044171825Skan varinfo_t ivi = get_varinfo (i); 2045171825Skan if (find (i) == i && !bitmap_empty_p (ivi->solution) 2046171825Skan && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i])) 2047171825Skan || VEC_length (constraint_t, graph->complex[i]) > 0)) 2048171825Skan { 2049171825Skan SET_BIT (changed, i); 2050171825Skan changed_count++; 2051171825Skan } 2052171825Skan } 2053171825Skan 2054171825Skan /* Allocate a bitmap to be used to store the changed bits. */ 2055171825Skan pts = BITMAP_ALLOC (&pta_obstack); 2056171825Skan 2057169689Skan while (changed_count > 0) 2058169689Skan { 2059169689Skan unsigned int i; 2060169689Skan struct topo_info *ti = init_topo_info (); 2061169689Skan stats.iterations++; 2062169689Skan 2063169689Skan bitmap_obstack_initialize (&iteration_obstack); 2064169689Skan 2065169689Skan compute_topo_order (graph, ti); 2066169689Skan 2067169689Skan while (VEC_length (unsigned, ti->topo_order) != 0) 2068169689Skan { 2069171825Skan 2070169689Skan i = VEC_pop (unsigned, ti->topo_order); 2071169689Skan 2072171825Skan /* If this variable is not a representative, skip it. */ 2073171825Skan if (find (i) != i) 2074171825Skan continue; 2075171825Skan 2076171825Skan /* In certain indirect cycle cases, we may merge this 2077171825Skan variable to another. */ 2078171825Skan if (eliminate_indirect_cycles (i) && find (i) != i) 2079171825Skan continue; 2080171825Skan 2081169689Skan /* If the node has changed, we need to process the 2082169689Skan complex constraints and outgoing edges again. */ 2083169689Skan if (TEST_BIT (changed, i)) 2084169689Skan { 2085169689Skan unsigned int j; 2086169689Skan constraint_t c; 2087169689Skan bitmap solution; 2088171825Skan VEC(constraint_t,heap) *complex = graph->complex[i]; 2089169689Skan bool solution_empty; 2090169689Skan 2091169689Skan RESET_BIT (changed, i); 2092169689Skan changed_count--; 2093169689Skan 2094171825Skan /* Compute the changed set of solution bits. */ 2095171825Skan bitmap_and_compl (pts, get_varinfo (i)->solution, 2096171825Skan get_varinfo (i)->oldsolution); 2097171825Skan 2098171825Skan if (bitmap_empty_p (pts)) 2099171825Skan continue; 2100171825Skan 2101171825Skan bitmap_ior_into (get_varinfo (i)->oldsolution, pts); 2102171825Skan 2103169689Skan solution = get_varinfo (i)->solution; 2104169689Skan solution_empty = bitmap_empty_p (solution); 2105169689Skan 2106169689Skan /* Process the complex constraints */ 2107169689Skan for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++) 2108169689Skan { 2109169689Skan /* The only complex constraint that can change our 2110169689Skan solution to non-empty, given an empty solution, 2111169689Skan is a constraint where the lhs side is receiving 2112169689Skan some set from elsewhere. */ 2113169689Skan if (!solution_empty || c->lhs.type != DEREF) 2114171825Skan do_complex_constraint (graph, c, pts); 2115169689Skan } 2116169689Skan 2117169689Skan solution_empty = bitmap_empty_p (solution); 2118169689Skan 2119169689Skan if (!solution_empty) 2120169689Skan { 2121171825Skan bitmap_iterator bi; 2122171825Skan 2123169689Skan /* Propagate solution to all successors. */ 2124171825Skan EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 2125169689Skan 0, j, bi) 2126169689Skan { 2127171825Skan bitmap tmp; 2128171825Skan bool flag; 2129169689Skan 2130171825Skan unsigned int to = find (j); 2131171825Skan tmp = get_varinfo (to)->solution; 2132171825Skan flag = false; 2133169689Skan 2134171825Skan /* Don't try to propagate to ourselves. */ 2135171825Skan if (to == i) 2136171825Skan continue; 2137171825Skan 2138171825Skan flag = set_union_with_increment (tmp, pts, 0); 2139171825Skan 2140169689Skan if (flag) 2141169689Skan { 2142171825Skan get_varinfo (to)->solution = tmp; 2143171825Skan if (!TEST_BIT (changed, to)) 2144169689Skan { 2145171825Skan SET_BIT (changed, to); 2146169689Skan changed_count++; 2147169689Skan } 2148169689Skan } 2149169689Skan } 2150169689Skan } 2151169689Skan } 2152169689Skan } 2153169689Skan free_topo_info (ti); 2154169689Skan bitmap_obstack_release (&iteration_obstack); 2155169689Skan } 2156169689Skan 2157171825Skan BITMAP_FREE (pts); 2158169689Skan sbitmap_free (changed); 2159171825Skan bitmap_obstack_release (&oldpta_obstack); 2160169689Skan} 2161169689Skan 2162171825Skan/* Map from trees to variable infos. */ 2163171825Skanstatic struct pointer_map_t *vi_for_tree; 2164169689Skan 2165169689Skan 2166171825Skan/* Insert ID as the variable id for tree T in the vi_for_tree map. */ 2167169689Skan 2168171825Skanstatic void 2169171825Skaninsert_vi_for_tree (tree t, varinfo_t vi) 2170169689Skan{ 2171171825Skan void **slot = pointer_map_insert (vi_for_tree, t); 2172171825Skan gcc_assert (vi); 2173169689Skan gcc_assert (*slot == NULL); 2174171825Skan *slot = vi; 2175169689Skan} 2176169689Skan 2177171825Skan/* Find the variable info for tree T in VI_FOR_TREE. If T does not 2178171825Skan exist in the map, return NULL, otherwise, return the varinfo we found. */ 2179169689Skan 2180171825Skanstatic varinfo_t 2181171825Skanlookup_vi_for_tree (tree t) 2182169689Skan{ 2183171825Skan void **slot = pointer_map_contains (vi_for_tree, t); 2184171825Skan if (slot == NULL) 2185171825Skan return NULL; 2186169689Skan 2187171825Skan return (varinfo_t) *slot; 2188169689Skan} 2189169689Skan 2190169689Skan/* Return a printable name for DECL */ 2191169689Skan 2192169689Skanstatic const char * 2193169689Skanalias_get_name (tree decl) 2194169689Skan{ 2195169689Skan const char *res = get_name (decl); 2196169689Skan char *temp; 2197169689Skan int num_printed = 0; 2198169689Skan 2199169689Skan if (res != NULL) 2200169689Skan return res; 2201169689Skan 2202169689Skan res = "NULL"; 2203169689Skan if (!dump_file) 2204169689Skan return res; 2205169689Skan 2206169689Skan if (TREE_CODE (decl) == SSA_NAME) 2207169689Skan { 2208171825Skan num_printed = asprintf (&temp, "%s_%u", 2209169689Skan alias_get_name (SSA_NAME_VAR (decl)), 2210169689Skan SSA_NAME_VERSION (decl)); 2211169689Skan } 2212169689Skan else if (DECL_P (decl)) 2213169689Skan { 2214169689Skan num_printed = asprintf (&temp, "D.%u", DECL_UID (decl)); 2215169689Skan } 2216169689Skan if (num_printed > 0) 2217169689Skan { 2218169689Skan res = ggc_strdup (temp); 2219169689Skan free (temp); 2220169689Skan } 2221169689Skan return res; 2222169689Skan} 2223169689Skan 2224171825Skan/* Find the variable id for tree T in the map. 2225171825Skan If T doesn't exist in the map, create an entry for it and return it. */ 2226169689Skan 2227171825Skanstatic varinfo_t 2228171825Skanget_vi_for_tree (tree t) 2229169689Skan{ 2230171825Skan void **slot = pointer_map_contains (vi_for_tree, t); 2231171825Skan if (slot == NULL) 2232171825Skan return get_varinfo (create_variable_info_for (t, alias_get_name (t))); 2233169689Skan 2234171825Skan return (varinfo_t) *slot; 2235169689Skan} 2236169689Skan 2237169689Skan/* Get a constraint expression from an SSA_VAR_P node. */ 2238169689Skan 2239169689Skanstatic struct constraint_expr 2240169689Skanget_constraint_exp_from_ssa_var (tree t) 2241169689Skan{ 2242169689Skan struct constraint_expr cexpr; 2243169689Skan 2244169689Skan gcc_assert (SSA_VAR_P (t) || DECL_P (t)); 2245169689Skan 2246169689Skan /* For parameters, get at the points-to set for the actual parm 2247169689Skan decl. */ 2248171825Skan if (TREE_CODE (t) == SSA_NAME 2249171825Skan && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL 2250169689Skan && default_def (SSA_NAME_VAR (t)) == t) 2251169689Skan return get_constraint_exp_from_ssa_var (SSA_NAME_VAR (t)); 2252169689Skan 2253169689Skan cexpr.type = SCALAR; 2254171825Skan 2255171825Skan cexpr.var = get_vi_for_tree (t)->id; 2256169689Skan /* If we determine the result is "anything", and we know this is readonly, 2257169689Skan say it points to readonly memory instead. */ 2258169689Skan if (cexpr.var == anything_id && TREE_READONLY (t)) 2259169689Skan { 2260169689Skan cexpr.type = ADDRESSOF; 2261169689Skan cexpr.var = readonly_id; 2262169689Skan } 2263171825Skan 2264169689Skan cexpr.offset = 0; 2265169689Skan return cexpr; 2266169689Skan} 2267169689Skan 2268169689Skan/* Process a completed constraint T, and add it to the constraint 2269169689Skan list. */ 2270169689Skan 2271169689Skanstatic void 2272169689Skanprocess_constraint (constraint_t t) 2273169689Skan{ 2274169689Skan struct constraint_expr rhs = t->rhs; 2275169689Skan struct constraint_expr lhs = t->lhs; 2276169689Skan 2277169689Skan gcc_assert (rhs.var < VEC_length (varinfo_t, varmap)); 2278169689Skan gcc_assert (lhs.var < VEC_length (varinfo_t, varmap)); 2279169689Skan 2280169689Skan if (lhs.type == DEREF) 2281169689Skan get_varinfo (lhs.var)->directly_dereferenced = true; 2282169689Skan if (rhs.type == DEREF) 2283169689Skan get_varinfo (rhs.var)->directly_dereferenced = true; 2284171825Skan 2285171825Skan if (!use_field_sensitive) 2286171825Skan { 2287171825Skan t->rhs.offset = 0; 2288171825Skan t->lhs.offset = 0; 2289171825Skan } 2290171825Skan 2291169689Skan /* ANYTHING == ANYTHING is pointless. */ 2292169689Skan if (lhs.var == anything_id && rhs.var == anything_id) 2293169689Skan return; 2294169689Skan 2295169689Skan /* If we have &ANYTHING = something, convert to SOMETHING = &ANYTHING) */ 2296169689Skan else if (lhs.var == anything_id && lhs.type == ADDRESSOF) 2297169689Skan { 2298169689Skan rhs = t->lhs; 2299169689Skan t->lhs = t->rhs; 2300169689Skan t->rhs = rhs; 2301169689Skan process_constraint (t); 2302171825Skan } 2303169689Skan /* This can happen in our IR with things like n->a = *p */ 2304169689Skan else if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id) 2305169689Skan { 2306169689Skan /* Split into tmp = *rhs, *lhs = tmp */ 2307169689Skan tree rhsdecl = get_varinfo (rhs.var)->decl; 2308169689Skan tree pointertype = TREE_TYPE (rhsdecl); 2309169689Skan tree pointedtotype = TREE_TYPE (pointertype); 2310169689Skan tree tmpvar = create_tmp_var_raw (pointedtotype, "doubledereftmp"); 2311169689Skan struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar); 2312171825Skan 2313169689Skan /* If this is an aggregate of known size, we should have passed 2314169689Skan this off to do_structure_copy, and it should have broken it 2315169689Skan up. */ 2316171825Skan gcc_assert (!AGGREGATE_TYPE_P (pointedtotype) 2317169689Skan || get_varinfo (rhs.var)->is_unknown_size_var); 2318171825Skan 2319169689Skan process_constraint (new_constraint (tmplhs, rhs)); 2320169689Skan process_constraint (new_constraint (lhs, tmplhs)); 2321169689Skan } 2322169689Skan else 2323169689Skan { 2324171825Skan gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0); 2325169689Skan VEC_safe_push (constraint_t, heap, constraints, t); 2326169689Skan } 2327169689Skan} 2328169689Skan 2329169689Skan/* Return true if T is a variable of a type that could contain 2330169689Skan pointers. */ 2331169689Skan 2332169689Skanstatic bool 2333169689Skancould_have_pointers (tree t) 2334169689Skan{ 2335169689Skan tree type = TREE_TYPE (t); 2336171825Skan 2337171825Skan if (POINTER_TYPE_P (type) 2338171825Skan || AGGREGATE_TYPE_P (type) 2339169689Skan || TREE_CODE (type) == COMPLEX_TYPE) 2340169689Skan return true; 2341171825Skan 2342169689Skan return false; 2343169689Skan} 2344169689Skan 2345169689Skan/* Return the position, in bits, of FIELD_DECL from the beginning of its 2346169689Skan structure. */ 2347169689Skan 2348169689Skanstatic unsigned HOST_WIDE_INT 2349169689Skanbitpos_of_field (const tree fdecl) 2350169689Skan{ 2351169689Skan 2352169689Skan if (TREE_CODE (DECL_FIELD_OFFSET (fdecl)) != INTEGER_CST 2353169689Skan || TREE_CODE (DECL_FIELD_BIT_OFFSET (fdecl)) != INTEGER_CST) 2354169689Skan return -1; 2355171825Skan 2356171825Skan return (tree_low_cst (DECL_FIELD_OFFSET (fdecl), 1) * 8) 2357171825Skan + tree_low_cst (DECL_FIELD_BIT_OFFSET (fdecl), 1); 2358169689Skan} 2359169689Skan 2360169689Skan 2361169689Skan/* Return true if an access to [ACCESSPOS, ACCESSSIZE] 2362169689Skan overlaps with a field at [FIELDPOS, FIELDSIZE] */ 2363169689Skan 2364169689Skanstatic bool 2365169689Skanoffset_overlaps_with_access (const unsigned HOST_WIDE_INT fieldpos, 2366169689Skan const unsigned HOST_WIDE_INT fieldsize, 2367169689Skan const unsigned HOST_WIDE_INT accesspos, 2368169689Skan const unsigned HOST_WIDE_INT accesssize) 2369169689Skan{ 2370169689Skan if (fieldpos == accesspos && fieldsize == accesssize) 2371169689Skan return true; 2372169689Skan if (accesspos >= fieldpos && accesspos < (fieldpos + fieldsize)) 2373169689Skan return true; 2374169689Skan if (accesspos < fieldpos && (accesspos + accesssize > fieldpos)) 2375169689Skan return true; 2376171825Skan 2377169689Skan return false; 2378169689Skan} 2379169689Skan 2380169689Skan/* Given a COMPONENT_REF T, return the constraint_expr for it. */ 2381169689Skan 2382169689Skanstatic void 2383169689Skanget_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results) 2384169689Skan{ 2385169689Skan tree orig_t = t; 2386169689Skan HOST_WIDE_INT bitsize = -1; 2387169689Skan HOST_WIDE_INT bitmaxsize = -1; 2388169689Skan HOST_WIDE_INT bitpos; 2389169689Skan tree forzero; 2390169689Skan struct constraint_expr *result; 2391169689Skan unsigned int beforelength = VEC_length (ce_s, *results); 2392169689Skan 2393169689Skan /* Some people like to do cute things like take the address of 2394169689Skan &0->a.b */ 2395169689Skan forzero = t; 2396169689Skan while (!SSA_VAR_P (forzero) && !CONSTANT_CLASS_P (forzero)) 2397169689Skan forzero = TREE_OPERAND (forzero, 0); 2398169689Skan 2399171825Skan if (CONSTANT_CLASS_P (forzero) && integer_zerop (forzero)) 2400169689Skan { 2401169689Skan struct constraint_expr temp; 2402171825Skan 2403169689Skan temp.offset = 0; 2404169689Skan temp.var = integer_id; 2405169689Skan temp.type = SCALAR; 2406169689Skan VEC_safe_push (ce_s, heap, *results, &temp); 2407169689Skan return; 2408169689Skan } 2409171825Skan 2410169689Skan t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize); 2411169689Skan 2412171825Skan /* String constants are readonly, so there is nothing to really do 2413169689Skan here. */ 2414169689Skan if (TREE_CODE (t) == STRING_CST) 2415169689Skan return; 2416169689Skan 2417169689Skan get_constraint_for (t, results); 2418169689Skan result = VEC_last (ce_s, *results); 2419169689Skan result->offset = bitpos; 2420169689Skan 2421169689Skan gcc_assert (beforelength + 1 == VEC_length (ce_s, *results)); 2422169689Skan 2423169689Skan /* This can also happen due to weird offsetof type macros. */ 2424169689Skan if (TREE_CODE (t) != ADDR_EXPR && result->type == ADDRESSOF) 2425169689Skan result->type = SCALAR; 2426171825Skan 2427169689Skan if (result->type == SCALAR) 2428169689Skan { 2429169689Skan /* In languages like C, you can access one past the end of an 2430169689Skan array. You aren't allowed to dereference it, so we can 2431169689Skan ignore this constraint. When we handle pointer subtraction, 2432169689Skan we may have to do something cute here. */ 2433171825Skan 2434169689Skan if (result->offset < get_varinfo (result->var)->fullsize 2435169689Skan && bitmaxsize != 0) 2436169689Skan { 2437169689Skan /* It's also not true that the constraint will actually start at the 2438169689Skan right offset, it may start in some padding. We only care about 2439169689Skan setting the constraint to the first actual field it touches, so 2440171825Skan walk to find it. */ 2441169689Skan varinfo_t curr; 2442169689Skan for (curr = get_varinfo (result->var); curr; curr = curr->next) 2443169689Skan { 2444169689Skan if (offset_overlaps_with_access (curr->offset, curr->size, 2445169689Skan result->offset, bitmaxsize)) 2446169689Skan { 2447169689Skan result->var = curr->id; 2448169689Skan break; 2449169689Skan } 2450169689Skan } 2451169689Skan /* assert that we found *some* field there. The user couldn't be 2452169689Skan accessing *only* padding. */ 2453169689Skan /* Still the user could access one past the end of an array 2454169689Skan embedded in a struct resulting in accessing *only* padding. */ 2455169689Skan gcc_assert (curr || ref_contains_array_ref (orig_t)); 2456169689Skan } 2457169689Skan else if (bitmaxsize == 0) 2458169689Skan { 2459169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2460169689Skan fprintf (dump_file, "Access to zero-sized part of variable," 2461169689Skan "ignoring\n"); 2462169689Skan } 2463169689Skan else 2464169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2465169689Skan fprintf (dump_file, "Access to past the end of variable, ignoring\n"); 2466169689Skan 2467169689Skan result->offset = 0; 2468169689Skan } 2469169689Skan} 2470169689Skan 2471169689Skan 2472169689Skan/* Dereference the constraint expression CONS, and return the result. 2473169689Skan DEREF (ADDRESSOF) = SCALAR 2474169689Skan DEREF (SCALAR) = DEREF 2475169689Skan DEREF (DEREF) = (temp = DEREF1; result = DEREF(temp)) 2476169689Skan This is needed so that we can handle dereferencing DEREF constraints. */ 2477169689Skan 2478169689Skanstatic void 2479169689Skando_deref (VEC (ce_s, heap) **constraints) 2480169689Skan{ 2481169689Skan struct constraint_expr *c; 2482169689Skan unsigned int i = 0; 2483171825Skan 2484169689Skan for (i = 0; VEC_iterate (ce_s, *constraints, i, c); i++) 2485169689Skan { 2486169689Skan if (c->type == SCALAR) 2487169689Skan c->type = DEREF; 2488169689Skan else if (c->type == ADDRESSOF) 2489169689Skan c->type = SCALAR; 2490169689Skan else if (c->type == DEREF) 2491169689Skan { 2492169689Skan tree tmpvar = create_tmp_var_raw (ptr_type_node, "dereftmp"); 2493169689Skan struct constraint_expr tmplhs = get_constraint_exp_from_ssa_var (tmpvar); 2494169689Skan process_constraint (new_constraint (tmplhs, *c)); 2495169689Skan c->var = tmplhs.var; 2496169689Skan } 2497169689Skan else 2498169689Skan gcc_unreachable (); 2499169689Skan } 2500169689Skan} 2501169689Skan 2502169689Skan/* Create a nonlocal variable of TYPE to represent nonlocals we can 2503169689Skan alias. */ 2504169689Skan 2505169689Skanstatic tree 2506169689Skancreate_nonlocal_var (tree type) 2507169689Skan{ 2508169689Skan tree nonlocal = create_tmp_var_raw (type, "NONLOCAL"); 2509169689Skan 2510169689Skan if (referenced_vars) 2511169689Skan add_referenced_var (nonlocal); 2512169689Skan 2513169689Skan DECL_EXTERNAL (nonlocal) = 1; 2514169689Skan return nonlocal; 2515169689Skan} 2516169689Skan 2517169689Skan/* Given a tree T, return the constraint expression for it. */ 2518169689Skan 2519169689Skanstatic void 2520169689Skanget_constraint_for (tree t, VEC (ce_s, heap) **results) 2521169689Skan{ 2522169689Skan struct constraint_expr temp; 2523169689Skan 2524169689Skan /* x = integer is all glommed to a single variable, which doesn't 2525169689Skan point to anything by itself. That is, of course, unless it is an 2526169689Skan integer constant being treated as a pointer, in which case, we 2527169689Skan will return that this is really the addressof anything. This 2528169689Skan happens below, since it will fall into the default case. The only 2529169689Skan case we know something about an integer treated like a pointer is 2530169689Skan when it is the NULL pointer, and then we just say it points to 2531169689Skan NULL. */ 2532169689Skan if (TREE_CODE (t) == INTEGER_CST 2533169689Skan && !POINTER_TYPE_P (TREE_TYPE (t))) 2534169689Skan { 2535169689Skan temp.var = integer_id; 2536169689Skan temp.type = SCALAR; 2537169689Skan temp.offset = 0; 2538169689Skan VEC_safe_push (ce_s, heap, *results, &temp); 2539169689Skan return; 2540169689Skan } 2541169689Skan else if (TREE_CODE (t) == INTEGER_CST 2542169689Skan && integer_zerop (t)) 2543169689Skan { 2544169689Skan temp.var = nothing_id; 2545169689Skan temp.type = ADDRESSOF; 2546169689Skan temp.offset = 0; 2547169689Skan VEC_safe_push (ce_s, heap, *results, &temp); 2548169689Skan return; 2549169689Skan } 2550169689Skan 2551169689Skan switch (TREE_CODE_CLASS (TREE_CODE (t))) 2552169689Skan { 2553169689Skan case tcc_expression: 2554169689Skan { 2555169689Skan switch (TREE_CODE (t)) 2556169689Skan { 2557169689Skan case ADDR_EXPR: 2558169689Skan { 2559169689Skan struct constraint_expr *c; 2560169689Skan unsigned int i; 2561169689Skan tree exp = TREE_OPERAND (t, 0); 2562169689Skan tree pttype = TREE_TYPE (TREE_TYPE (t)); 2563169689Skan 2564169689Skan get_constraint_for (exp, results); 2565171825Skan 2566169689Skan /* Make sure we capture constraints to all elements 2567169689Skan of an array. */ 2568169689Skan if ((handled_component_p (exp) 2569169689Skan && ref_contains_array_ref (exp)) 2570169689Skan || TREE_CODE (TREE_TYPE (exp)) == ARRAY_TYPE) 2571169689Skan { 2572169689Skan struct constraint_expr *origrhs; 2573169689Skan varinfo_t origvar; 2574169689Skan struct constraint_expr tmp; 2575169689Skan 2576169689Skan if (VEC_length (ce_s, *results) == 0) 2577169689Skan return; 2578171825Skan 2579169689Skan gcc_assert (VEC_length (ce_s, *results) == 1); 2580169689Skan origrhs = VEC_last (ce_s, *results); 2581169689Skan tmp = *origrhs; 2582169689Skan VEC_pop (ce_s, *results); 2583169689Skan origvar = get_varinfo (origrhs->var); 2584169689Skan for (; origvar; origvar = origvar->next) 2585169689Skan { 2586169689Skan tmp.var = origvar->id; 2587169689Skan VEC_safe_push (ce_s, heap, *results, &tmp); 2588169689Skan } 2589169689Skan } 2590169689Skan else if (VEC_length (ce_s, *results) == 1 2591169689Skan && (AGGREGATE_TYPE_P (pttype) 2592169689Skan || TREE_CODE (pttype) == COMPLEX_TYPE)) 2593169689Skan { 2594169689Skan struct constraint_expr *origrhs; 2595169689Skan varinfo_t origvar; 2596169689Skan struct constraint_expr tmp; 2597169689Skan 2598169689Skan gcc_assert (VEC_length (ce_s, *results) == 1); 2599169689Skan origrhs = VEC_last (ce_s, *results); 2600169689Skan tmp = *origrhs; 2601169689Skan VEC_pop (ce_s, *results); 2602169689Skan origvar = get_varinfo (origrhs->var); 2603169689Skan for (; origvar; origvar = origvar->next) 2604169689Skan { 2605169689Skan tmp.var = origvar->id; 2606169689Skan VEC_safe_push (ce_s, heap, *results, &tmp); 2607169689Skan } 2608169689Skan } 2609171825Skan 2610169689Skan for (i = 0; VEC_iterate (ce_s, *results, i, c); i++) 2611169689Skan { 2612169689Skan if (c->type == DEREF) 2613169689Skan c->type = SCALAR; 2614171825Skan else 2615169689Skan c->type = ADDRESSOF; 2616169689Skan } 2617169689Skan return; 2618169689Skan } 2619169689Skan break; 2620169689Skan case CALL_EXPR: 2621169689Skan /* XXX: In interprocedural mode, if we didn't have the 2622169689Skan body, we would need to do *each pointer argument = 2623169689Skan &ANYTHING added. */ 2624169689Skan if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)) 2625169689Skan { 2626169689Skan varinfo_t vi; 2627169689Skan tree heapvar = heapvar_lookup (t); 2628171825Skan 2629169689Skan if (heapvar == NULL) 2630171825Skan { 2631169689Skan heapvar = create_tmp_var_raw (ptr_type_node, "HEAP"); 2632169689Skan DECL_EXTERNAL (heapvar) = 1; 2633169689Skan if (referenced_vars) 2634169689Skan add_referenced_var (heapvar); 2635169689Skan heapvar_insert (t, heapvar); 2636169689Skan } 2637169689Skan 2638169689Skan temp.var = create_variable_info_for (heapvar, 2639169689Skan alias_get_name (heapvar)); 2640171825Skan 2641169689Skan vi = get_varinfo (temp.var); 2642169689Skan vi->is_artificial_var = 1; 2643169689Skan vi->is_heap_var = 1; 2644169689Skan temp.type = ADDRESSOF; 2645169689Skan temp.offset = 0; 2646169689Skan VEC_safe_push (ce_s, heap, *results, &temp); 2647169689Skan return; 2648169689Skan } 2649169689Skan else 2650169689Skan { 2651169689Skan temp.var = escaped_vars_id; 2652169689Skan temp.type = SCALAR; 2653169689Skan temp.offset = 0; 2654169689Skan VEC_safe_push (ce_s, heap, *results, &temp); 2655169689Skan return; 2656169689Skan } 2657169689Skan break; 2658169689Skan default: 2659169689Skan { 2660169689Skan temp.type = ADDRESSOF; 2661169689Skan temp.var = anything_id; 2662169689Skan temp.offset = 0; 2663169689Skan VEC_safe_push (ce_s, heap, *results, &temp); 2664169689Skan return; 2665169689Skan } 2666169689Skan } 2667169689Skan } 2668169689Skan case tcc_reference: 2669169689Skan { 2670169689Skan switch (TREE_CODE (t)) 2671169689Skan { 2672169689Skan case INDIRECT_REF: 2673169689Skan { 2674169689Skan get_constraint_for (TREE_OPERAND (t, 0), results); 2675169689Skan do_deref (results); 2676169689Skan return; 2677169689Skan } 2678169689Skan case ARRAY_REF: 2679169689Skan case ARRAY_RANGE_REF: 2680169689Skan case COMPONENT_REF: 2681169689Skan get_constraint_for_component_ref (t, results); 2682169689Skan return; 2683169689Skan default: 2684169689Skan { 2685169689Skan temp.type = ADDRESSOF; 2686169689Skan temp.var = anything_id; 2687169689Skan temp.offset = 0; 2688169689Skan VEC_safe_push (ce_s, heap, *results, &temp); 2689169689Skan return; 2690169689Skan } 2691169689Skan } 2692169689Skan } 2693169689Skan case tcc_unary: 2694169689Skan { 2695169689Skan switch (TREE_CODE (t)) 2696169689Skan { 2697169689Skan case NOP_EXPR: 2698169689Skan case CONVERT_EXPR: 2699169689Skan case NON_LVALUE_EXPR: 2700169689Skan { 2701169689Skan tree op = TREE_OPERAND (t, 0); 2702171825Skan 2703169689Skan /* Cast from non-pointer to pointers are bad news for us. 2704169689Skan Anything else, we see through */ 2705169689Skan if (!(POINTER_TYPE_P (TREE_TYPE (t)) 2706169689Skan && ! POINTER_TYPE_P (TREE_TYPE (op)))) 2707169689Skan { 2708169689Skan get_constraint_for (op, results); 2709169689Skan return; 2710169689Skan } 2711169689Skan 2712169689Skan /* FALLTHRU */ 2713169689Skan } 2714169689Skan default: 2715169689Skan { 2716169689Skan temp.type = ADDRESSOF; 2717169689Skan temp.var = anything_id; 2718169689Skan temp.offset = 0; 2719169689Skan VEC_safe_push (ce_s, heap, *results, &temp); 2720169689Skan return; 2721169689Skan } 2722169689Skan } 2723169689Skan } 2724169689Skan case tcc_exceptional: 2725169689Skan { 2726169689Skan switch (TREE_CODE (t)) 2727169689Skan { 2728171825Skan case PHI_NODE: 2729169689Skan { 2730169689Skan get_constraint_for (PHI_RESULT (t), results); 2731169689Skan return; 2732169689Skan } 2733169689Skan break; 2734169689Skan case SSA_NAME: 2735169689Skan { 2736169689Skan struct constraint_expr temp; 2737169689Skan temp = get_constraint_exp_from_ssa_var (t); 2738169689Skan VEC_safe_push (ce_s, heap, *results, &temp); 2739169689Skan return; 2740169689Skan } 2741169689Skan break; 2742169689Skan default: 2743169689Skan { 2744169689Skan temp.type = ADDRESSOF; 2745169689Skan temp.var = anything_id; 2746169689Skan temp.offset = 0; 2747169689Skan VEC_safe_push (ce_s, heap, *results, &temp); 2748169689Skan return; 2749169689Skan } 2750169689Skan } 2751169689Skan } 2752169689Skan case tcc_declaration: 2753169689Skan { 2754169689Skan struct constraint_expr temp; 2755169689Skan temp = get_constraint_exp_from_ssa_var (t); 2756169689Skan VEC_safe_push (ce_s, heap, *results, &temp); 2757169689Skan return; 2758169689Skan } 2759169689Skan default: 2760169689Skan { 2761169689Skan temp.type = ADDRESSOF; 2762169689Skan temp.var = anything_id; 2763169689Skan temp.offset = 0; 2764169689Skan VEC_safe_push (ce_s, heap, *results, &temp); 2765169689Skan return; 2766169689Skan } 2767169689Skan } 2768169689Skan} 2769169689Skan 2770169689Skan 2771169689Skan/* Handle the structure copy case where we have a simple structure copy 2772171825Skan between LHS and RHS that is of SIZE (in bits) 2773171825Skan 2774169689Skan For each field of the lhs variable (lhsfield) 2775169689Skan For each field of the rhs variable at lhsfield.offset (rhsfield) 2776169689Skan add the constraint lhsfield = rhsfield 2777169689Skan 2778169689Skan If we fail due to some kind of type unsafety or other thing we 2779169689Skan can't handle, return false. We expect the caller to collapse the 2780169689Skan variable in that case. */ 2781169689Skan 2782169689Skanstatic bool 2783169689Skando_simple_structure_copy (const struct constraint_expr lhs, 2784169689Skan const struct constraint_expr rhs, 2785169689Skan const unsigned HOST_WIDE_INT size) 2786169689Skan{ 2787169689Skan varinfo_t p = get_varinfo (lhs.var); 2788169689Skan unsigned HOST_WIDE_INT pstart, last; 2789169689Skan pstart = p->offset; 2790169689Skan last = p->offset + size; 2791169689Skan for (; p && p->offset < last; p = p->next) 2792169689Skan { 2793169689Skan varinfo_t q; 2794169689Skan struct constraint_expr templhs = lhs; 2795169689Skan struct constraint_expr temprhs = rhs; 2796169689Skan unsigned HOST_WIDE_INT fieldoffset; 2797169689Skan 2798171825Skan templhs.var = p->id; 2799169689Skan q = get_varinfo (temprhs.var); 2800169689Skan fieldoffset = p->offset - pstart; 2801169689Skan q = first_vi_for_offset (q, q->offset + fieldoffset); 2802169689Skan if (!q) 2803169689Skan return false; 2804169689Skan temprhs.var = q->id; 2805169689Skan process_constraint (new_constraint (templhs, temprhs)); 2806169689Skan } 2807169689Skan return true; 2808169689Skan} 2809169689Skan 2810169689Skan 2811169689Skan/* Handle the structure copy case where we have a structure copy between a 2812169689Skan aggregate on the LHS and a dereference of a pointer on the RHS 2813171825Skan that is of SIZE (in bits) 2814171825Skan 2815169689Skan For each field of the lhs variable (lhsfield) 2816169689Skan rhs.offset = lhsfield->offset 2817169689Skan add the constraint lhsfield = rhs 2818169689Skan*/ 2819169689Skan 2820169689Skanstatic void 2821169689Skando_rhs_deref_structure_copy (const struct constraint_expr lhs, 2822169689Skan const struct constraint_expr rhs, 2823169689Skan const unsigned HOST_WIDE_INT size) 2824169689Skan{ 2825169689Skan varinfo_t p = get_varinfo (lhs.var); 2826169689Skan unsigned HOST_WIDE_INT pstart,last; 2827169689Skan pstart = p->offset; 2828169689Skan last = p->offset + size; 2829169689Skan 2830169689Skan for (; p && p->offset < last; p = p->next) 2831169689Skan { 2832169689Skan varinfo_t q; 2833169689Skan struct constraint_expr templhs = lhs; 2834169689Skan struct constraint_expr temprhs = rhs; 2835169689Skan unsigned HOST_WIDE_INT fieldoffset; 2836169689Skan 2837169689Skan 2838169689Skan if (templhs.type == SCALAR) 2839171825Skan templhs.var = p->id; 2840169689Skan else 2841169689Skan templhs.offset = p->offset; 2842171825Skan 2843169689Skan q = get_varinfo (temprhs.var); 2844171825Skan fieldoffset = p->offset - pstart; 2845169689Skan temprhs.offset += fieldoffset; 2846169689Skan process_constraint (new_constraint (templhs, temprhs)); 2847169689Skan } 2848169689Skan} 2849169689Skan 2850169689Skan/* Handle the structure copy case where we have a structure copy 2851169689Skan between a aggregate on the RHS and a dereference of a pointer on 2852171825Skan the LHS that is of SIZE (in bits) 2853169689Skan 2854169689Skan For each field of the rhs variable (rhsfield) 2855169689Skan lhs.offset = rhsfield->offset 2856169689Skan add the constraint lhs = rhsfield 2857169689Skan*/ 2858169689Skan 2859169689Skanstatic void 2860169689Skando_lhs_deref_structure_copy (const struct constraint_expr lhs, 2861169689Skan const struct constraint_expr rhs, 2862169689Skan const unsigned HOST_WIDE_INT size) 2863169689Skan{ 2864169689Skan varinfo_t p = get_varinfo (rhs.var); 2865169689Skan unsigned HOST_WIDE_INT pstart,last; 2866169689Skan pstart = p->offset; 2867169689Skan last = p->offset + size; 2868169689Skan 2869169689Skan for (; p && p->offset < last; p = p->next) 2870169689Skan { 2871169689Skan varinfo_t q; 2872169689Skan struct constraint_expr templhs = lhs; 2873169689Skan struct constraint_expr temprhs = rhs; 2874169689Skan unsigned HOST_WIDE_INT fieldoffset; 2875169689Skan 2876169689Skan 2877169689Skan if (temprhs.type == SCALAR) 2878171825Skan temprhs.var = p->id; 2879169689Skan else 2880169689Skan temprhs.offset = p->offset; 2881171825Skan 2882169689Skan q = get_varinfo (templhs.var); 2883171825Skan fieldoffset = p->offset - pstart; 2884169689Skan templhs.offset += fieldoffset; 2885169689Skan process_constraint (new_constraint (templhs, temprhs)); 2886169689Skan } 2887169689Skan} 2888169689Skan 2889169689Skan/* Sometimes, frontends like to give us bad type information. This 2890169689Skan function will collapse all the fields from VAR to the end of VAR, 2891171825Skan into VAR, so that we treat those fields as a single variable. 2892169689Skan We return the variable they were collapsed into. */ 2893169689Skan 2894169689Skanstatic unsigned int 2895169689Skancollapse_rest_of_var (unsigned int var) 2896169689Skan{ 2897169689Skan varinfo_t currvar = get_varinfo (var); 2898169689Skan varinfo_t field; 2899169689Skan 2900169689Skan for (field = currvar->next; field; field = field->next) 2901169689Skan { 2902169689Skan if (dump_file) 2903171825Skan fprintf (dump_file, "Type safety: Collapsing var %s into %s\n", 2904169689Skan field->name, currvar->name); 2905171825Skan 2906169689Skan gcc_assert (!field->collapsed_to); 2907169689Skan field->collapsed_to = currvar; 2908169689Skan } 2909169689Skan 2910169689Skan currvar->next = NULL; 2911169689Skan currvar->size = currvar->fullsize - currvar->offset; 2912171825Skan 2913169689Skan return currvar->id; 2914169689Skan} 2915169689Skan 2916169689Skan/* Handle aggregate copies by expanding into copies of the respective 2917169689Skan fields of the structures. */ 2918169689Skan 2919169689Skanstatic void 2920169689Skando_structure_copy (tree lhsop, tree rhsop) 2921169689Skan{ 2922169689Skan struct constraint_expr lhs, rhs, tmp; 2923169689Skan VEC (ce_s, heap) *lhsc = NULL, *rhsc = NULL; 2924169689Skan varinfo_t p; 2925169689Skan unsigned HOST_WIDE_INT lhssize; 2926169689Skan unsigned HOST_WIDE_INT rhssize; 2927169689Skan 2928169689Skan get_constraint_for (lhsop, &lhsc); 2929169689Skan get_constraint_for (rhsop, &rhsc); 2930169689Skan gcc_assert (VEC_length (ce_s, lhsc) == 1); 2931169689Skan gcc_assert (VEC_length (ce_s, rhsc) == 1); 2932169689Skan lhs = *(VEC_last (ce_s, lhsc)); 2933169689Skan rhs = *(VEC_last (ce_s, rhsc)); 2934171825Skan 2935169689Skan VEC_free (ce_s, heap, lhsc); 2936169689Skan VEC_free (ce_s, heap, rhsc); 2937169689Skan 2938169689Skan /* If we have special var = x, swap it around. */ 2939169689Skan if (lhs.var <= integer_id && !(get_varinfo (rhs.var)->is_special_var)) 2940169689Skan { 2941169689Skan tmp = lhs; 2942169689Skan lhs = rhs; 2943169689Skan rhs = tmp; 2944169689Skan } 2945171825Skan 2946169689Skan /* This is fairly conservative for the RHS == ADDRESSOF case, in that it's 2947169689Skan possible it's something we could handle. However, most cases falling 2948169689Skan into this are dealing with transparent unions, which are slightly 2949169689Skan weird. */ 2950169689Skan if (rhs.type == ADDRESSOF && !(get_varinfo (rhs.var)->is_special_var)) 2951169689Skan { 2952169689Skan rhs.type = ADDRESSOF; 2953169689Skan rhs.var = anything_id; 2954169689Skan } 2955169689Skan 2956169689Skan /* If the RHS is a special var, or an addressof, set all the LHS fields to 2957169689Skan that special var. */ 2958169689Skan if (rhs.var <= integer_id) 2959169689Skan { 2960169689Skan for (p = get_varinfo (lhs.var); p; p = p->next) 2961169689Skan { 2962169689Skan struct constraint_expr templhs = lhs; 2963169689Skan struct constraint_expr temprhs = rhs; 2964169689Skan 2965169689Skan if (templhs.type == SCALAR ) 2966169689Skan templhs.var = p->id; 2967169689Skan else 2968169689Skan templhs.offset += p->offset; 2969169689Skan process_constraint (new_constraint (templhs, temprhs)); 2970169689Skan } 2971169689Skan } 2972169689Skan else 2973169689Skan { 2974169689Skan tree rhstype = TREE_TYPE (rhsop); 2975169689Skan tree lhstype = TREE_TYPE (lhsop); 2976169689Skan tree rhstypesize; 2977169689Skan tree lhstypesize; 2978169689Skan 2979169689Skan lhstypesize = DECL_P (lhsop) ? DECL_SIZE (lhsop) : TYPE_SIZE (lhstype); 2980169689Skan rhstypesize = DECL_P (rhsop) ? DECL_SIZE (rhsop) : TYPE_SIZE (rhstype); 2981169689Skan 2982169689Skan /* If we have a variably sized types on the rhs or lhs, and a deref 2983169689Skan constraint, add the constraint, lhsconstraint = &ANYTHING. 2984169689Skan This is conservatively correct because either the lhs is an unknown 2985169689Skan sized var (if the constraint is SCALAR), or the lhs is a DEREF 2986169689Skan constraint, and every variable it can point to must be unknown sized 2987169689Skan anyway, so we don't need to worry about fields at all. */ 2988169689Skan if ((rhs.type == DEREF && TREE_CODE (rhstypesize) != INTEGER_CST) 2989169689Skan || (lhs.type == DEREF && TREE_CODE (lhstypesize) != INTEGER_CST)) 2990169689Skan { 2991169689Skan rhs.var = anything_id; 2992169689Skan rhs.type = ADDRESSOF; 2993169689Skan rhs.offset = 0; 2994169689Skan process_constraint (new_constraint (lhs, rhs)); 2995169689Skan return; 2996169689Skan } 2997169689Skan 2998169689Skan /* The size only really matters insofar as we don't set more or less of 2999169689Skan the variable. If we hit an unknown size var, the size should be the 3000169689Skan whole darn thing. */ 3001169689Skan if (get_varinfo (rhs.var)->is_unknown_size_var) 3002169689Skan rhssize = ~0; 3003169689Skan else 3004169689Skan rhssize = TREE_INT_CST_LOW (rhstypesize); 3005169689Skan 3006169689Skan if (get_varinfo (lhs.var)->is_unknown_size_var) 3007169689Skan lhssize = ~0; 3008169689Skan else 3009169689Skan lhssize = TREE_INT_CST_LOW (lhstypesize); 3010169689Skan 3011171825Skan 3012171825Skan if (rhs.type == SCALAR && lhs.type == SCALAR) 3013169689Skan { 3014169689Skan if (!do_simple_structure_copy (lhs, rhs, MIN (lhssize, rhssize))) 3015171825Skan { 3016169689Skan lhs.var = collapse_rest_of_var (lhs.var); 3017169689Skan rhs.var = collapse_rest_of_var (rhs.var); 3018169689Skan lhs.offset = 0; 3019169689Skan rhs.offset = 0; 3020169689Skan lhs.type = SCALAR; 3021169689Skan rhs.type = SCALAR; 3022169689Skan process_constraint (new_constraint (lhs, rhs)); 3023169689Skan } 3024169689Skan } 3025169689Skan else if (lhs.type != DEREF && rhs.type == DEREF) 3026169689Skan do_rhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize)); 3027169689Skan else if (lhs.type == DEREF && rhs.type != DEREF) 3028169689Skan do_lhs_deref_structure_copy (lhs, rhs, MIN (lhssize, rhssize)); 3029169689Skan else 3030169689Skan { 3031169689Skan tree pointedtotype = lhstype; 3032171825Skan tree tmpvar; 3033169689Skan 3034169689Skan gcc_assert (rhs.type == DEREF && lhs.type == DEREF); 3035169689Skan tmpvar = create_tmp_var_raw (pointedtotype, "structcopydereftmp"); 3036169689Skan do_structure_copy (tmpvar, rhsop); 3037169689Skan do_structure_copy (lhsop, tmpvar); 3038169689Skan } 3039169689Skan } 3040169689Skan} 3041169689Skan 3042171825Skan 3043169689Skan/* Update related alias information kept in AI. This is used when 3044169689Skan building name tags, alias sets and deciding grouping heuristics. 3045169689Skan STMT is the statement to process. This function also updates 3046169689Skan ADDRESSABLE_VARS. */ 3047169689Skan 3048169689Skanstatic void 3049169689Skanupdate_alias_info (tree stmt, struct alias_info *ai) 3050169689Skan{ 3051169689Skan bitmap addr_taken; 3052169689Skan use_operand_p use_p; 3053169689Skan ssa_op_iter iter; 3054169689Skan enum escape_type stmt_escape_type = is_escape_site (stmt); 3055169689Skan tree op; 3056169689Skan 3057169689Skan if (stmt_escape_type == ESCAPE_TO_CALL 3058169689Skan || stmt_escape_type == ESCAPE_TO_PURE_CONST) 3059169689Skan { 3060169689Skan ai->num_calls_found++; 3061169689Skan if (stmt_escape_type == ESCAPE_TO_PURE_CONST) 3062169689Skan ai->num_pure_const_calls_found++; 3063169689Skan } 3064169689Skan 3065169689Skan /* Mark all the variables whose address are taken by the statement. */ 3066169689Skan addr_taken = addresses_taken (stmt); 3067169689Skan if (addr_taken) 3068169689Skan { 3069169689Skan bitmap_ior_into (addressable_vars, addr_taken); 3070169689Skan 3071169689Skan /* If STMT is an escape point, all the addresses taken by it are 3072169689Skan call-clobbered. */ 3073169689Skan if (stmt_escape_type != NO_ESCAPE) 3074169689Skan { 3075169689Skan bitmap_iterator bi; 3076169689Skan unsigned i; 3077169689Skan 3078169689Skan EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi) 3079169689Skan { 3080169689Skan tree rvar = referenced_var (i); 3081169689Skan if (!unmodifiable_var_p (rvar)) 3082169689Skan mark_call_clobbered (rvar, stmt_escape_type); 3083169689Skan } 3084169689Skan } 3085169689Skan } 3086169689Skan 3087169689Skan /* Process each operand use. If an operand may be aliased, keep 3088169689Skan track of how many times it's being used. For pointers, determine 3089169689Skan whether they are dereferenced by the statement, or whether their 3090169689Skan value escapes, etc. */ 3091169689Skan FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE) 3092169689Skan { 3093169689Skan tree op, var; 3094169689Skan var_ann_t v_ann; 3095169689Skan struct ptr_info_def *pi; 3096169689Skan bool is_store, is_potential_deref; 3097169689Skan unsigned num_uses, num_derefs; 3098169689Skan 3099169689Skan op = USE_FROM_PTR (use_p); 3100169689Skan 3101169689Skan /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it 3102169689Skan to the set of addressable variables. */ 3103169689Skan if (TREE_CODE (op) == ADDR_EXPR) 3104169689Skan { 3105169689Skan gcc_assert (TREE_CODE (stmt) == PHI_NODE); 3106169689Skan 3107169689Skan /* PHI nodes don't have annotations for pinning the set 3108169689Skan of addresses taken, so we collect them here. 3109169689Skan 3110169689Skan FIXME, should we allow PHI nodes to have annotations 3111169689Skan so that they can be treated like regular statements? 3112169689Skan Currently, they are treated as second-class 3113169689Skan statements. */ 3114169689Skan add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars); 3115169689Skan continue; 3116169689Skan } 3117169689Skan 3118169689Skan /* Ignore constants. */ 3119169689Skan if (TREE_CODE (op) != SSA_NAME) 3120169689Skan continue; 3121169689Skan 3122169689Skan var = SSA_NAME_VAR (op); 3123169689Skan v_ann = var_ann (var); 3124169689Skan 3125169689Skan /* The base variable of an ssa name must be a GIMPLE register, and thus 3126169689Skan it cannot be aliased. */ 3127169689Skan gcc_assert (!may_be_aliased (var)); 3128169689Skan 3129169689Skan /* We are only interested in pointers. */ 3130169689Skan if (!POINTER_TYPE_P (TREE_TYPE (op))) 3131169689Skan continue; 3132169689Skan 3133169689Skan pi = get_ptr_info (op); 3134169689Skan 3135169689Skan /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */ 3136169689Skan if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op))) 3137169689Skan { 3138169689Skan SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)); 3139169689Skan VEC_safe_push (tree, heap, ai->processed_ptrs, op); 3140169689Skan } 3141169689Skan 3142169689Skan /* If STMT is a PHI node, then it will not have pointer 3143169689Skan dereferences and it will not be an escape point. */ 3144169689Skan if (TREE_CODE (stmt) == PHI_NODE) 3145169689Skan continue; 3146169689Skan 3147169689Skan /* Determine whether OP is a dereferenced pointer, and if STMT 3148169689Skan is an escape point, whether OP escapes. */ 3149169689Skan count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store); 3150169689Skan 3151169689Skan /* Handle a corner case involving address expressions of the 3152169689Skan form '&PTR->FLD'. The problem with these expressions is that 3153169689Skan they do not represent a dereference of PTR. However, if some 3154169689Skan other transformation propagates them into an INDIRECT_REF 3155169689Skan expression, we end up with '*(&PTR->FLD)' which is folded 3156169689Skan into 'PTR->FLD'. 3157169689Skan 3158169689Skan So, if the original code had no other dereferences of PTR, 3159169689Skan the aliaser will not create memory tags for it, and when 3160169689Skan &PTR->FLD gets propagated to INDIRECT_REF expressions, the 3161169689Skan memory operations will receive no V_MAY_DEF/VUSE operands. 3162169689Skan 3163169689Skan One solution would be to have count_uses_and_derefs consider 3164169689Skan &PTR->FLD a dereference of PTR. But that is wrong, since it 3165169689Skan is not really a dereference but an offset calculation. 3166169689Skan 3167169689Skan What we do here is to recognize these special ADDR_EXPR 3168169689Skan nodes. Since these expressions are never GIMPLE values (they 3169169689Skan are not GIMPLE invariants), they can only appear on the RHS 3170169689Skan of an assignment and their base address is always an 3171169689Skan INDIRECT_REF expression. */ 3172169689Skan is_potential_deref = false; 3173169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR 3174169689Skan && TREE_CODE (TREE_OPERAND (stmt, 1)) == ADDR_EXPR 3175169689Skan && !is_gimple_val (TREE_OPERAND (stmt, 1))) 3176169689Skan { 3177169689Skan /* If the RHS if of the form &PTR->FLD and PTR == OP, then 3178169689Skan this represents a potential dereference of PTR. */ 3179169689Skan tree rhs = TREE_OPERAND (stmt, 1); 3180169689Skan tree base = get_base_address (TREE_OPERAND (rhs, 0)); 3181169689Skan if (TREE_CODE (base) == INDIRECT_REF 3182169689Skan && TREE_OPERAND (base, 0) == op) 3183169689Skan is_potential_deref = true; 3184169689Skan } 3185169689Skan 3186169689Skan if (num_derefs > 0 || is_potential_deref) 3187169689Skan { 3188169689Skan /* Mark OP as dereferenced. In a subsequent pass, 3189169689Skan dereferenced pointers that point to a set of 3190169689Skan variables will be assigned a name tag to alias 3191169689Skan all the variables OP points to. */ 3192169689Skan pi->is_dereferenced = 1; 3193169689Skan 3194169689Skan /* Keep track of how many time we've dereferenced each 3195169689Skan pointer. */ 3196169689Skan NUM_REFERENCES_INC (v_ann); 3197169689Skan 3198169689Skan /* If this is a store operation, mark OP as being 3199169689Skan dereferenced to store, otherwise mark it as being 3200169689Skan dereferenced to load. */ 3201169689Skan if (is_store) 3202169689Skan bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var)); 3203169689Skan else 3204169689Skan bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var)); 3205169689Skan } 3206169689Skan 3207169689Skan if (stmt_escape_type != NO_ESCAPE && num_derefs < num_uses) 3208169689Skan { 3209169689Skan /* If STMT is an escape point and STMT contains at 3210169689Skan least one direct use of OP, then the value of OP 3211169689Skan escapes and so the pointed-to variables need to 3212169689Skan be marked call-clobbered. */ 3213169689Skan pi->value_escapes_p = 1; 3214169689Skan pi->escape_mask |= stmt_escape_type; 3215169689Skan 3216169689Skan /* If the statement makes a function call, assume 3217169689Skan that pointer OP will be dereferenced in a store 3218169689Skan operation inside the called function. */ 3219169689Skan if (get_call_expr_in (stmt) 3220169689Skan || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL) 3221169689Skan { 3222169689Skan bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var)); 3223169689Skan pi->is_dereferenced = 1; 3224169689Skan } 3225169689Skan } 3226169689Skan } 3227169689Skan 3228169689Skan if (TREE_CODE (stmt) == PHI_NODE) 3229169689Skan return; 3230169689Skan 3231169689Skan /* Update reference counter for definitions to any 3232169689Skan potentially aliased variable. This is used in the alias 3233169689Skan grouping heuristics. */ 3234169689Skan FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF) 3235169689Skan { 3236169689Skan tree var = SSA_NAME_VAR (op); 3237169689Skan var_ann_t ann = var_ann (var); 3238169689Skan bitmap_set_bit (ai->written_vars, DECL_UID (var)); 3239169689Skan if (may_be_aliased (var)) 3240169689Skan NUM_REFERENCES_INC (ann); 3241169689Skan 3242169689Skan } 3243169689Skan 3244169689Skan /* Mark variables in V_MAY_DEF operands as being written to. */ 3245169689Skan FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS) 3246169689Skan { 3247169689Skan tree var = DECL_P (op) ? op : SSA_NAME_VAR (op); 3248169689Skan bitmap_set_bit (ai->written_vars, DECL_UID (var)); 3249169689Skan } 3250169689Skan} 3251169689Skan 3252169689Skan/* Handle pointer arithmetic EXPR when creating aliasing constraints. 3253169689Skan Expressions of the type PTR + CST can be handled in two ways: 3254169689Skan 3255169689Skan 1- If the constraint for PTR is ADDRESSOF for a non-structure 3256169689Skan variable, then we can use it directly because adding or 3257169689Skan subtracting a constant may not alter the original ADDRESSOF 3258169689Skan constraint (i.e., pointer arithmetic may not legally go outside 3259169689Skan an object's boundaries). 3260169689Skan 3261169689Skan 2- If the constraint for PTR is ADDRESSOF for a structure variable, 3262169689Skan then if CST is a compile-time constant that can be used as an 3263169689Skan offset, we can determine which sub-variable will be pointed-to 3264169689Skan by the expression. 3265169689Skan 3266169689Skan Return true if the expression is handled. For any other kind of 3267169689Skan expression, return false so that each operand can be added as a 3268169689Skan separate constraint by the caller. */ 3269169689Skan 3270169689Skanstatic bool 3271169689Skanhandle_ptr_arith (VEC (ce_s, heap) *lhsc, tree expr) 3272169689Skan{ 3273169689Skan tree op0, op1; 3274169689Skan struct constraint_expr *c, *c2; 3275169689Skan unsigned int i = 0; 3276169689Skan unsigned int j = 0; 3277169689Skan VEC (ce_s, heap) *temp = NULL; 3278171825Skan unsigned HOST_WIDE_INT rhsoffset = 0; 3279169689Skan 3280169689Skan if (TREE_CODE (expr) != PLUS_EXPR 3281169689Skan && TREE_CODE (expr) != MINUS_EXPR) 3282169689Skan return false; 3283169689Skan 3284169689Skan op0 = TREE_OPERAND (expr, 0); 3285169689Skan op1 = TREE_OPERAND (expr, 1); 3286169689Skan 3287169689Skan get_constraint_for (op0, &temp); 3288169689Skan if (POINTER_TYPE_P (TREE_TYPE (op0)) 3289171825Skan && host_integerp (op1, 1) 3290169689Skan && TREE_CODE (expr) == PLUS_EXPR) 3291169689Skan { 3292171825Skan if ((TREE_INT_CST_LOW (op1) * BITS_PER_UNIT) / BITS_PER_UNIT 3293171825Skan != TREE_INT_CST_LOW (op1)) 3294171825Skan return false; 3295169689Skan rhsoffset = TREE_INT_CST_LOW (op1) * BITS_PER_UNIT; 3296169689Skan } 3297169689Skan else 3298169689Skan return false; 3299169689Skan 3300171825Skan 3301169689Skan for (i = 0; VEC_iterate (ce_s, lhsc, i, c); i++) 3302169689Skan for (j = 0; VEC_iterate (ce_s, temp, j, c2); j++) 3303169689Skan { 3304169689Skan if (c2->type == ADDRESSOF && rhsoffset != 0) 3305169689Skan { 3306169689Skan varinfo_t temp = get_varinfo (c2->var); 3307169689Skan 3308169689Skan /* An access one after the end of an array is valid, 3309169689Skan so simply punt on accesses we cannot resolve. */ 3310169689Skan temp = first_vi_for_offset (temp, rhsoffset); 3311169689Skan if (temp == NULL) 3312169689Skan continue; 3313169689Skan c2->var = temp->id; 3314169689Skan c2->offset = 0; 3315169689Skan } 3316169689Skan else 3317169689Skan c2->offset = rhsoffset; 3318169689Skan process_constraint (new_constraint (*c, *c2)); 3319169689Skan } 3320169689Skan 3321169689Skan VEC_free (ce_s, heap, temp); 3322169689Skan 3323169689Skan return true; 3324169689Skan} 3325169689Skan 3326169689Skan 3327169689Skan/* Walk statement T setting up aliasing constraints according to the 3328169689Skan references found in T. This function is the main part of the 3329169689Skan constraint builder. AI points to auxiliary alias information used 3330169689Skan when building alias sets and computing alias grouping heuristics. */ 3331169689Skan 3332169689Skanstatic void 3333169689Skanfind_func_aliases (tree origt) 3334169689Skan{ 3335169689Skan tree t = origt; 3336169689Skan VEC(ce_s, heap) *lhsc = NULL; 3337169689Skan VEC(ce_s, heap) *rhsc = NULL; 3338169689Skan struct constraint_expr *c; 3339169689Skan 3340169689Skan if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0)) 3341169689Skan t = TREE_OPERAND (t, 0); 3342169689Skan 3343169689Skan /* Now build constraints expressions. */ 3344169689Skan if (TREE_CODE (t) == PHI_NODE) 3345169689Skan { 3346169689Skan gcc_assert (!AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t)))); 3347169689Skan 3348169689Skan /* Only care about pointers and structures containing 3349169689Skan pointers. */ 3350169689Skan if (could_have_pointers (PHI_RESULT (t))) 3351169689Skan { 3352169689Skan int i; 3353169689Skan unsigned int j; 3354171825Skan 3355169689Skan /* For a phi node, assign all the arguments to 3356169689Skan the result. */ 3357169689Skan get_constraint_for (PHI_RESULT (t), &lhsc); 3358169689Skan for (i = 0; i < PHI_NUM_ARGS (t); i++) 3359171825Skan { 3360169689Skan tree rhstype; 3361169689Skan tree strippedrhs = PHI_ARG_DEF (t, i); 3362169689Skan 3363169689Skan STRIP_NOPS (strippedrhs); 3364169689Skan rhstype = TREE_TYPE (strippedrhs); 3365169689Skan get_constraint_for (PHI_ARG_DEF (t, i), &rhsc); 3366169689Skan 3367169689Skan for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++) 3368169689Skan { 3369169689Skan struct constraint_expr *c2; 3370169689Skan while (VEC_length (ce_s, rhsc) > 0) 3371169689Skan { 3372169689Skan c2 = VEC_last (ce_s, rhsc); 3373169689Skan process_constraint (new_constraint (*c, *c2)); 3374169689Skan VEC_pop (ce_s, rhsc); 3375169689Skan } 3376169689Skan } 3377169689Skan } 3378169689Skan } 3379169689Skan } 3380169689Skan /* In IPA mode, we need to generate constraints to pass call 3381169689Skan arguments through their calls. There are two case, either a 3382169689Skan modify_expr when we are returning a value, or just a plain 3383169689Skan call_expr when we are not. */ 3384169689Skan else if (in_ipa_mode 3385169689Skan && ((TREE_CODE (t) == MODIFY_EXPR 3386169689Skan && TREE_CODE (TREE_OPERAND (t, 1)) == CALL_EXPR 3387169689Skan && !(call_expr_flags (TREE_OPERAND (t, 1)) 3388169689Skan & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))) 3389169689Skan || (TREE_CODE (t) == CALL_EXPR 3390169689Skan && !(call_expr_flags (t) 3391169689Skan & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))))) 3392169689Skan { 3393169689Skan tree lhsop; 3394169689Skan tree rhsop; 3395169689Skan tree arglist; 3396169689Skan varinfo_t fi; 3397169689Skan int i = 1; 3398169689Skan tree decl; 3399169689Skan if (TREE_CODE (t) == MODIFY_EXPR) 3400169689Skan { 3401169689Skan lhsop = TREE_OPERAND (t, 0); 3402169689Skan rhsop = TREE_OPERAND (t, 1); 3403169689Skan } 3404169689Skan else 3405169689Skan { 3406169689Skan lhsop = NULL; 3407169689Skan rhsop = t; 3408169689Skan } 3409169689Skan decl = get_callee_fndecl (rhsop); 3410169689Skan 3411169689Skan /* If we can directly resolve the function being called, do so. 3412169689Skan Otherwise, it must be some sort of indirect expression that 3413169689Skan we should still be able to handle. */ 3414169689Skan if (decl) 3415169689Skan { 3416171825Skan fi = get_vi_for_tree (decl); 3417169689Skan } 3418169689Skan else 3419169689Skan { 3420169689Skan decl = TREE_OPERAND (rhsop, 0); 3421171825Skan fi = get_vi_for_tree (decl); 3422169689Skan } 3423169689Skan 3424169689Skan /* Assign all the passed arguments to the appropriate incoming 3425169689Skan parameters of the function. */ 3426169689Skan arglist = TREE_OPERAND (rhsop, 1); 3427169689Skan 3428169689Skan for (;arglist; arglist = TREE_CHAIN (arglist)) 3429169689Skan { 3430169689Skan tree arg = TREE_VALUE (arglist); 3431169689Skan struct constraint_expr lhs ; 3432169689Skan struct constraint_expr *rhsp; 3433169689Skan 3434169689Skan get_constraint_for (arg, &rhsc); 3435169689Skan if (TREE_CODE (decl) != FUNCTION_DECL) 3436169689Skan { 3437169689Skan lhs.type = DEREF; 3438169689Skan lhs.var = fi->id; 3439169689Skan lhs.offset = i; 3440169689Skan } 3441169689Skan else 3442169689Skan { 3443169689Skan lhs.type = SCALAR; 3444169689Skan lhs.var = first_vi_for_offset (fi, i)->id; 3445169689Skan lhs.offset = 0; 3446169689Skan } 3447169689Skan while (VEC_length (ce_s, rhsc) != 0) 3448169689Skan { 3449169689Skan rhsp = VEC_last (ce_s, rhsc); 3450169689Skan process_constraint (new_constraint (lhs, *rhsp)); 3451169689Skan VEC_pop (ce_s, rhsc); 3452169689Skan } 3453169689Skan i++; 3454169689Skan } 3455171825Skan 3456169689Skan /* If we are returning a value, assign it to the result. */ 3457169689Skan if (lhsop) 3458169689Skan { 3459169689Skan struct constraint_expr rhs; 3460169689Skan struct constraint_expr *lhsp; 3461169689Skan unsigned int j = 0; 3462171825Skan 3463169689Skan get_constraint_for (lhsop, &lhsc); 3464169689Skan if (TREE_CODE (decl) != FUNCTION_DECL) 3465169689Skan { 3466169689Skan rhs.type = DEREF; 3467169689Skan rhs.var = fi->id; 3468169689Skan rhs.offset = i; 3469169689Skan } 3470169689Skan else 3471169689Skan { 3472169689Skan rhs.type = SCALAR; 3473169689Skan rhs.var = first_vi_for_offset (fi, i)->id; 3474169689Skan rhs.offset = 0; 3475169689Skan } 3476169689Skan for (j = 0; VEC_iterate (ce_s, lhsc, j, lhsp); j++) 3477169689Skan process_constraint (new_constraint (*lhsp, rhs)); 3478171825Skan } 3479169689Skan } 3480169689Skan /* Otherwise, just a regular assignment statement. */ 3481169689Skan else if (TREE_CODE (t) == MODIFY_EXPR) 3482169689Skan { 3483169689Skan tree lhsop = TREE_OPERAND (t, 0); 3484169689Skan tree rhsop = TREE_OPERAND (t, 1); 3485169689Skan int i; 3486169689Skan 3487171825Skan if ((AGGREGATE_TYPE_P (TREE_TYPE (lhsop)) 3488169689Skan || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE) 3489169689Skan && (AGGREGATE_TYPE_P (TREE_TYPE (rhsop)) 3490169689Skan || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE)) 3491169689Skan { 3492169689Skan do_structure_copy (lhsop, rhsop); 3493169689Skan } 3494169689Skan else 3495169689Skan { 3496169689Skan /* Only care about operations with pointers, structures 3497169689Skan containing pointers, dereferences, and call expressions. */ 3498169689Skan if (could_have_pointers (lhsop) 3499169689Skan || TREE_CODE (rhsop) == CALL_EXPR) 3500169689Skan { 3501169689Skan get_constraint_for (lhsop, &lhsc); 3502169689Skan switch (TREE_CODE_CLASS (TREE_CODE (rhsop))) 3503169689Skan { 3504169689Skan /* RHS that consist of unary operations, 3505169689Skan exceptional types, or bare decls/constants, get 3506171825Skan handled directly by get_constraint_for. */ 3507169689Skan case tcc_reference: 3508169689Skan case tcc_declaration: 3509169689Skan case tcc_constant: 3510169689Skan case tcc_exceptional: 3511169689Skan case tcc_expression: 3512169689Skan case tcc_unary: 3513169689Skan { 3514169689Skan unsigned int j; 3515169689Skan 3516169689Skan get_constraint_for (rhsop, &rhsc); 3517169689Skan for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++) 3518169689Skan { 3519169689Skan struct constraint_expr *c2; 3520169689Skan unsigned int k; 3521171825Skan 3522169689Skan for (k = 0; VEC_iterate (ce_s, rhsc, k, c2); k++) 3523169689Skan process_constraint (new_constraint (*c, *c2)); 3524169689Skan } 3525169689Skan 3526169689Skan } 3527169689Skan break; 3528169689Skan 3529169689Skan case tcc_binary: 3530169689Skan { 3531169689Skan /* For pointer arithmetic of the form 3532169689Skan PTR + CST, we can simply use PTR's 3533169689Skan constraint because pointer arithmetic is 3534169689Skan not allowed to go out of bounds. */ 3535169689Skan if (handle_ptr_arith (lhsc, rhsop)) 3536169689Skan break; 3537169689Skan } 3538169689Skan /* FALLTHRU */ 3539169689Skan 3540169689Skan /* Otherwise, walk each operand. Notice that we 3541169689Skan can't use the operand interface because we need 3542169689Skan to process expressions other than simple operands 3543169689Skan (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */ 3544169689Skan default: 3545169689Skan for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++) 3546169689Skan { 3547169689Skan tree op = TREE_OPERAND (rhsop, i); 3548169689Skan unsigned int j; 3549169689Skan 3550169689Skan gcc_assert (VEC_length (ce_s, rhsc) == 0); 3551169689Skan get_constraint_for (op, &rhsc); 3552169689Skan for (j = 0; VEC_iterate (ce_s, lhsc, j, c); j++) 3553169689Skan { 3554169689Skan struct constraint_expr *c2; 3555169689Skan while (VEC_length (ce_s, rhsc) > 0) 3556169689Skan { 3557169689Skan c2 = VEC_last (ce_s, rhsc); 3558169689Skan process_constraint (new_constraint (*c, *c2)); 3559169689Skan VEC_pop (ce_s, rhsc); 3560169689Skan } 3561169689Skan } 3562169689Skan } 3563171825Skan } 3564169689Skan } 3565169689Skan } 3566169689Skan } 3567169689Skan 3568169689Skan /* After promoting variables and computing aliasing we will 3569169689Skan need to re-scan most statements. FIXME: Try to minimize the 3570169689Skan number of statements re-scanned. It's not really necessary to 3571171825Skan re-scan *all* statements. */ 3572169689Skan mark_stmt_modified (origt); 3573169689Skan VEC_free (ce_s, heap, rhsc); 3574169689Skan VEC_free (ce_s, heap, lhsc); 3575169689Skan} 3576169689Skan 3577169689Skan 3578169689Skan/* Find the first varinfo in the same variable as START that overlaps with 3579169689Skan OFFSET. 3580169689Skan Effectively, walk the chain of fields for the variable START to find the 3581169689Skan first field that overlaps with OFFSET. 3582169689Skan Return NULL if we can't find one. */ 3583169689Skan 3584171825Skanstatic varinfo_t 3585169689Skanfirst_vi_for_offset (varinfo_t start, unsigned HOST_WIDE_INT offset) 3586169689Skan{ 3587169689Skan varinfo_t curr = start; 3588169689Skan while (curr) 3589169689Skan { 3590169689Skan /* We may not find a variable in the field list with the actual 3591169689Skan offset when when we have glommed a structure to a variable. 3592169689Skan In that case, however, offset should still be within the size 3593169689Skan of the variable. */ 3594169689Skan if (offset >= curr->offset && offset < (curr->offset + curr->size)) 3595169689Skan return curr; 3596169689Skan curr = curr->next; 3597169689Skan } 3598169689Skan return NULL; 3599169689Skan} 3600169689Skan 3601169689Skan 3602169689Skan/* Insert the varinfo FIELD into the field list for BASE, at the front 3603169689Skan of the list. */ 3604169689Skan 3605169689Skanstatic void 3606169689Skaninsert_into_field_list (varinfo_t base, varinfo_t field) 3607169689Skan{ 3608169689Skan varinfo_t prev = base; 3609169689Skan varinfo_t curr = base->next; 3610171825Skan 3611169689Skan field->next = curr; 3612169689Skan prev->next = field; 3613169689Skan} 3614169689Skan 3615169689Skan/* Insert the varinfo FIELD into the field list for BASE, ordered by 3616169689Skan offset. */ 3617169689Skan 3618169689Skanstatic void 3619169689Skaninsert_into_field_list_sorted (varinfo_t base, varinfo_t field) 3620169689Skan{ 3621169689Skan varinfo_t prev = base; 3622169689Skan varinfo_t curr = base->next; 3623171825Skan 3624169689Skan if (curr == NULL) 3625169689Skan { 3626169689Skan prev->next = field; 3627169689Skan field->next = NULL; 3628169689Skan } 3629169689Skan else 3630169689Skan { 3631169689Skan while (curr) 3632169689Skan { 3633169689Skan if (field->offset <= curr->offset) 3634169689Skan break; 3635169689Skan prev = curr; 3636169689Skan curr = curr->next; 3637169689Skan } 3638169689Skan field->next = prev->next; 3639169689Skan prev->next = field; 3640169689Skan } 3641169689Skan} 3642169689Skan 3643169689Skan/* qsort comparison function for two fieldoff's PA and PB */ 3644169689Skan 3645171825Skanstatic int 3646169689Skanfieldoff_compare (const void *pa, const void *pb) 3647169689Skan{ 3648169689Skan const fieldoff_s *foa = (const fieldoff_s *)pa; 3649169689Skan const fieldoff_s *fob = (const fieldoff_s *)pb; 3650169689Skan HOST_WIDE_INT foasize, fobsize; 3651171825Skan 3652169689Skan if (foa->offset != fob->offset) 3653169689Skan return foa->offset - fob->offset; 3654169689Skan 3655169689Skan foasize = TREE_INT_CST_LOW (foa->size); 3656169689Skan fobsize = TREE_INT_CST_LOW (fob->size); 3657169689Skan return foasize - fobsize; 3658169689Skan} 3659169689Skan 3660169689Skan/* Sort a fieldstack according to the field offset and sizes. */ 3661169689Skanvoid 3662169689Skansort_fieldstack (VEC(fieldoff_s,heap) *fieldstack) 3663169689Skan{ 3664171825Skan qsort (VEC_address (fieldoff_s, fieldstack), 3665171825Skan VEC_length (fieldoff_s, fieldstack), 3666169689Skan sizeof (fieldoff_s), 3667169689Skan fieldoff_compare); 3668169689Skan} 3669169689Skan 3670169689Skan/* Given a TYPE, and a vector of field offsets FIELDSTACK, push all the fields 3671169689Skan of TYPE onto fieldstack, recording their offsets along the way. 3672169689Skan OFFSET is used to keep track of the offset in this entire structure, rather 3673169689Skan than just the immediately containing structure. Returns the number 3674169689Skan of fields pushed. 3675169689Skan HAS_UNION is set to true if we find a union type as a field of 3676169689Skan TYPE. */ 3677169689Skan 3678169689Skanint 3679171825Skanpush_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack, 3680169689Skan HOST_WIDE_INT offset, bool *has_union) 3681169689Skan{ 3682169689Skan tree field; 3683169689Skan int count = 0; 3684171825Skan unsigned HOST_WIDE_INT minoffset = -1; 3685171825Skan 3686169689Skan if (TREE_CODE (type) == COMPLEX_TYPE) 3687169689Skan { 3688169689Skan fieldoff_s *real_part, *img_part; 3689169689Skan real_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL); 3690169689Skan real_part->type = TREE_TYPE (type); 3691169689Skan real_part->size = TYPE_SIZE (TREE_TYPE (type)); 3692169689Skan real_part->offset = offset; 3693169689Skan real_part->decl = NULL_TREE; 3694171825Skan 3695169689Skan img_part = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL); 3696169689Skan img_part->type = TREE_TYPE (type); 3697169689Skan img_part->size = TYPE_SIZE (TREE_TYPE (type)); 3698169689Skan img_part->offset = offset + TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (type))); 3699169689Skan img_part->decl = NULL_TREE; 3700171825Skan 3701169689Skan return 2; 3702169689Skan } 3703169689Skan 3704169689Skan if (TREE_CODE (type) == ARRAY_TYPE) 3705169689Skan { 3706169689Skan tree sz = TYPE_SIZE (type); 3707169689Skan tree elsz = TYPE_SIZE (TREE_TYPE (type)); 3708169689Skan HOST_WIDE_INT nr; 3709169689Skan int i; 3710169689Skan 3711169689Skan if (! sz 3712169689Skan || ! host_integerp (sz, 1) 3713169689Skan || TREE_INT_CST_LOW (sz) == 0 3714169689Skan || ! elsz 3715169689Skan || ! host_integerp (elsz, 1) 3716169689Skan || TREE_INT_CST_LOW (elsz) == 0) 3717169689Skan return 0; 3718169689Skan 3719169689Skan nr = TREE_INT_CST_LOW (sz) / TREE_INT_CST_LOW (elsz); 3720169689Skan if (nr > SALIAS_MAX_ARRAY_ELEMENTS) 3721169689Skan return 0; 3722169689Skan 3723169689Skan for (i = 0; i < nr; ++i) 3724169689Skan { 3725169689Skan bool push = false; 3726169689Skan int pushed = 0; 3727171825Skan 3728171825Skan if (has_union 3729169689Skan && (TREE_CODE (TREE_TYPE (type)) == QUAL_UNION_TYPE 3730169689Skan || TREE_CODE (TREE_TYPE (type)) == UNION_TYPE)) 3731169689Skan *has_union = true; 3732171825Skan 3733169689Skan if (!AGGREGATE_TYPE_P (TREE_TYPE (type))) /* var_can_have_subvars */ 3734169689Skan push = true; 3735169689Skan else if (!(pushed = push_fields_onto_fieldstack 3736169689Skan (TREE_TYPE (type), fieldstack, 3737169689Skan offset + i * TREE_INT_CST_LOW (elsz), has_union))) 3738169689Skan /* Empty structures may have actual size, like in C++. So 3739169689Skan see if we didn't push any subfields and the size is 3740169689Skan nonzero, push the field onto the stack */ 3741169689Skan push = true; 3742169689Skan 3743169689Skan if (push) 3744169689Skan { 3745169689Skan fieldoff_s *pair; 3746169689Skan 3747169689Skan pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL); 3748169689Skan pair->type = TREE_TYPE (type); 3749169689Skan pair->size = elsz; 3750169689Skan pair->decl = NULL_TREE; 3751169689Skan pair->offset = offset + i * TREE_INT_CST_LOW (elsz); 3752169689Skan count++; 3753169689Skan } 3754169689Skan else 3755169689Skan count += pushed; 3756169689Skan } 3757169689Skan 3758169689Skan return count; 3759169689Skan } 3760169689Skan 3761169689Skan for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field)) 3762169689Skan if (TREE_CODE (field) == FIELD_DECL) 3763169689Skan { 3764169689Skan bool push = false; 3765169689Skan int pushed = 0; 3766171825Skan 3767171825Skan if (has_union 3768169689Skan && (TREE_CODE (TREE_TYPE (field)) == QUAL_UNION_TYPE 3769169689Skan || TREE_CODE (TREE_TYPE (field)) == UNION_TYPE)) 3770169689Skan *has_union = true; 3771171825Skan 3772169689Skan if (!var_can_have_subvars (field)) 3773169689Skan push = true; 3774169689Skan else if (!(pushed = push_fields_onto_fieldstack 3775169689Skan (TREE_TYPE (field), fieldstack, 3776169689Skan offset + bitpos_of_field (field), has_union)) 3777169689Skan && DECL_SIZE (field) 3778169689Skan && !integer_zerop (DECL_SIZE (field))) 3779169689Skan /* Empty structures may have actual size, like in C++. So 3780169689Skan see if we didn't push any subfields and the size is 3781169689Skan nonzero, push the field onto the stack */ 3782169689Skan push = true; 3783171825Skan 3784169689Skan if (push) 3785169689Skan { 3786169689Skan fieldoff_s *pair; 3787169689Skan 3788169689Skan pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL); 3789169689Skan pair->type = TREE_TYPE (field); 3790169689Skan pair->size = DECL_SIZE (field); 3791169689Skan pair->decl = field; 3792169689Skan pair->offset = offset + bitpos_of_field (field); 3793169689Skan count++; 3794169689Skan } 3795169689Skan else 3796169689Skan count += pushed; 3797171825Skan 3798171825Skan if (bitpos_of_field (field) < minoffset) 3799171825Skan minoffset = bitpos_of_field (field); 3800169689Skan } 3801169689Skan 3802171825Skan /* We need to create a fake subvar for empty bases. But _only_ for non-empty 3803171825Skan classes. */ 3804171825Skan if (minoffset != 0 && count != 0) 3805171825Skan { 3806171825Skan fieldoff_s *pair; 3807171825Skan 3808171825Skan pair = VEC_safe_push (fieldoff_s, heap, *fieldstack, NULL); 3809171825Skan pair->type = void_type_node; 3810171825Skan pair->size = build_int_cst (size_type_node, minoffset); 3811171825Skan pair->decl = NULL; 3812171825Skan pair->offset = offset; 3813171825Skan count++; 3814171825Skan } 3815171825Skan 3816169689Skan return count; 3817169689Skan} 3818169689Skan 3819169689Skan/* Create a constraint from ESCAPED_VARS variable to VI. */ 3820169689Skanstatic void 3821169689Skanmake_constraint_from_escaped (varinfo_t vi) 3822169689Skan{ 3823169689Skan struct constraint_expr lhs, rhs; 3824169689Skan 3825169689Skan lhs.var = vi->id; 3826169689Skan lhs.offset = 0; 3827169689Skan lhs.type = SCALAR; 3828169689Skan 3829169689Skan rhs.var = escaped_vars_id; 3830169689Skan rhs.offset = 0; 3831169689Skan rhs.type = SCALAR; 3832169689Skan process_constraint (new_constraint (lhs, rhs)); 3833169689Skan} 3834169689Skan 3835169689Skan/* Create a constraint to the ESCAPED_VARS variable from constraint 3836169689Skan expression RHS. */ 3837169689Skan 3838169689Skanstatic void 3839169689Skanmake_constraint_to_escaped (struct constraint_expr rhs) 3840169689Skan{ 3841169689Skan struct constraint_expr lhs; 3842169689Skan 3843169689Skan lhs.var = escaped_vars_id; 3844169689Skan lhs.offset = 0; 3845169689Skan lhs.type = SCALAR; 3846169689Skan 3847169689Skan process_constraint (new_constraint (lhs, rhs)); 3848169689Skan} 3849169689Skan 3850169689Skan/* Count the number of arguments DECL has, and set IS_VARARGS to true 3851169689Skan if it is a varargs function. */ 3852169689Skan 3853169689Skanstatic unsigned int 3854169689Skancount_num_arguments (tree decl, bool *is_varargs) 3855169689Skan{ 3856169689Skan unsigned int i = 0; 3857169689Skan tree t; 3858169689Skan 3859171825Skan for (t = TYPE_ARG_TYPES (TREE_TYPE (decl)); 3860169689Skan t; 3861169689Skan t = TREE_CHAIN (t)) 3862171825Skan { 3863169689Skan if (TREE_VALUE (t) == void_type_node) 3864169689Skan break; 3865169689Skan i++; 3866169689Skan } 3867171825Skan 3868169689Skan if (!t) 3869169689Skan *is_varargs = true; 3870169689Skan return i; 3871169689Skan} 3872169689Skan 3873169689Skan/* Creation function node for DECL, using NAME, and return the index 3874169689Skan of the variable we've created for the function. */ 3875169689Skan 3876169689Skanstatic unsigned int 3877169689Skancreate_function_info_for (tree decl, const char *name) 3878169689Skan{ 3879169689Skan unsigned int index = VEC_length (varinfo_t, varmap); 3880169689Skan varinfo_t vi; 3881171825Skan tree arg; 3882169689Skan unsigned int i; 3883169689Skan bool is_varargs = false; 3884169689Skan 3885169689Skan /* Create the variable info. */ 3886169689Skan 3887171825Skan vi = new_var_info (decl, index, name); 3888169689Skan vi->decl = decl; 3889169689Skan vi->offset = 0; 3890169689Skan vi->has_union = 0; 3891169689Skan vi->size = 1; 3892169689Skan vi->fullsize = count_num_arguments (decl, &is_varargs) + 1; 3893171825Skan insert_vi_for_tree (vi->decl, vi); 3894169689Skan VEC_safe_push (varinfo_t, heap, varmap, vi); 3895169689Skan 3896169689Skan stats.total_vars++; 3897169689Skan 3898169689Skan /* If it's varargs, we don't know how many arguments it has, so we 3899169689Skan can't do much. 3900169689Skan */ 3901169689Skan if (is_varargs) 3902169689Skan { 3903169689Skan vi->fullsize = ~0; 3904169689Skan vi->size = ~0; 3905169689Skan vi->is_unknown_size_var = true; 3906169689Skan return index; 3907169689Skan } 3908169689Skan 3909171825Skan 3910169689Skan arg = DECL_ARGUMENTS (decl); 3911169689Skan 3912169689Skan /* Set up variables for each argument. */ 3913169689Skan for (i = 1; i < vi->fullsize; i++) 3914171825Skan { 3915169689Skan varinfo_t argvi; 3916169689Skan const char *newname; 3917169689Skan char *tempname; 3918169689Skan unsigned int newindex; 3919169689Skan tree argdecl = decl; 3920169689Skan 3921169689Skan if (arg) 3922169689Skan argdecl = arg; 3923171825Skan 3924169689Skan newindex = VEC_length (varinfo_t, varmap); 3925169689Skan asprintf (&tempname, "%s.arg%d", name, i-1); 3926169689Skan newname = ggc_strdup (tempname); 3927169689Skan free (tempname); 3928169689Skan 3929171825Skan argvi = new_var_info (argdecl, newindex, newname); 3930169689Skan argvi->decl = argdecl; 3931169689Skan VEC_safe_push (varinfo_t, heap, varmap, argvi); 3932169689Skan argvi->offset = i; 3933169689Skan argvi->size = 1; 3934169689Skan argvi->fullsize = vi->fullsize; 3935169689Skan argvi->has_union = false; 3936169689Skan insert_into_field_list_sorted (vi, argvi); 3937169689Skan stats.total_vars ++; 3938169689Skan if (arg) 3939169689Skan { 3940171825Skan insert_vi_for_tree (arg, argvi); 3941169689Skan arg = TREE_CHAIN (arg); 3942169689Skan } 3943169689Skan } 3944169689Skan 3945169689Skan /* Create a variable for the return var. */ 3946169689Skan if (DECL_RESULT (decl) != NULL 3947169689Skan || !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (decl)))) 3948169689Skan { 3949169689Skan varinfo_t resultvi; 3950169689Skan const char *newname; 3951169689Skan char *tempname; 3952169689Skan unsigned int newindex; 3953169689Skan tree resultdecl = decl; 3954169689Skan 3955169689Skan vi->fullsize ++; 3956169689Skan 3957169689Skan if (DECL_RESULT (decl)) 3958169689Skan resultdecl = DECL_RESULT (decl); 3959171825Skan 3960169689Skan newindex = VEC_length (varinfo_t, varmap); 3961169689Skan asprintf (&tempname, "%s.result", name); 3962169689Skan newname = ggc_strdup (tempname); 3963169689Skan free (tempname); 3964169689Skan 3965171825Skan resultvi = new_var_info (resultdecl, newindex, newname); 3966169689Skan resultvi->decl = resultdecl; 3967169689Skan VEC_safe_push (varinfo_t, heap, varmap, resultvi); 3968169689Skan resultvi->offset = i; 3969169689Skan resultvi->size = 1; 3970169689Skan resultvi->fullsize = vi->fullsize; 3971169689Skan resultvi->has_union = false; 3972169689Skan insert_into_field_list_sorted (vi, resultvi); 3973169689Skan stats.total_vars ++; 3974169689Skan if (DECL_RESULT (decl)) 3975171825Skan insert_vi_for_tree (DECL_RESULT (decl), resultvi); 3976169689Skan } 3977169689Skan return index; 3978171825Skan} 3979169689Skan 3980169689Skan 3981171825Skan/* Return true if FIELDSTACK contains fields that overlap. 3982169689Skan FIELDSTACK is assumed to be sorted by offset. */ 3983169689Skan 3984169689Skanstatic bool 3985169689Skancheck_for_overlaps (VEC (fieldoff_s,heap) *fieldstack) 3986169689Skan{ 3987169689Skan fieldoff_s *fo = NULL; 3988169689Skan unsigned int i; 3989169689Skan HOST_WIDE_INT lastoffset = -1; 3990169689Skan 3991169689Skan for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++) 3992169689Skan { 3993169689Skan if (fo->offset == lastoffset) 3994169689Skan return true; 3995169689Skan lastoffset = fo->offset; 3996169689Skan } 3997169689Skan return false; 3998169689Skan} 3999169689Skan 4000169689Skan/* This function is called through walk_tree to walk global 4001169689Skan initializers looking for constraints we need to add to the 4002169689Skan constraint list. */ 4003169689Skan 4004169689Skanstatic tree 4005169689Skanfind_global_initializers (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, 4006169689Skan void *viv) 4007169689Skan{ 4008169689Skan varinfo_t vi = (varinfo_t)viv; 4009169689Skan tree t = *tp; 4010169689Skan 4011169689Skan switch (TREE_CODE (t)) 4012169689Skan { 4013169689Skan /* Dereferences and addressofs are the only important things 4014169689Skan here, and i don't even remember if dereferences are legal 4015169689Skan here in initializers. */ 4016169689Skan case INDIRECT_REF: 4017169689Skan case ADDR_EXPR: 4018169689Skan { 4019169689Skan struct constraint_expr *c; 4020169689Skan size_t i; 4021169689Skan 4022169689Skan VEC(ce_s, heap) *rhsc = NULL; 4023169689Skan get_constraint_for (t, &rhsc); 4024169689Skan for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) 4025169689Skan { 4026169689Skan struct constraint_expr lhs; 4027169689Skan 4028169689Skan lhs.var = vi->id; 4029169689Skan lhs.type = SCALAR; 4030169689Skan lhs.offset = 0; 4031169689Skan process_constraint (new_constraint (lhs, *c)); 4032169689Skan } 4033169689Skan 4034169689Skan VEC_free (ce_s, heap, rhsc); 4035169689Skan } 4036169689Skan break; 4037169689Skan case VAR_DECL: 4038169689Skan /* We might not have walked this because we skip 4039169689Skan DECL_EXTERNALs during the initial scan. */ 4040169689Skan if (referenced_vars) 4041169689Skan { 4042169689Skan get_var_ann (t); 4043169689Skan if (referenced_var_check_and_insert (t)) 4044169689Skan mark_sym_for_renaming (t); 4045169689Skan } 4046169689Skan break; 4047169689Skan default: 4048169689Skan break; 4049169689Skan } 4050169689Skan return NULL_TREE; 4051169689Skan} 4052169689Skan 4053169689Skan/* Create a varinfo structure for NAME and DECL, and add it to VARMAP. 4054169689Skan This will also create any varinfo structures necessary for fields 4055169689Skan of DECL. */ 4056169689Skan 4057169689Skanstatic unsigned int 4058169689Skancreate_variable_info_for (tree decl, const char *name) 4059169689Skan{ 4060169689Skan unsigned int index = VEC_length (varinfo_t, varmap); 4061169689Skan varinfo_t vi; 4062169689Skan tree decltype = TREE_TYPE (decl); 4063169689Skan tree declsize = DECL_P (decl) ? DECL_SIZE (decl) : TYPE_SIZE (decltype); 4064169689Skan bool notokay = false; 4065169689Skan bool hasunion; 4066169689Skan bool is_global = DECL_P (decl) ? is_global_var (decl) : false; 4067169689Skan VEC (fieldoff_s,heap) *fieldstack = NULL; 4068171825Skan 4069169689Skan if (TREE_CODE (decl) == FUNCTION_DECL && in_ipa_mode) 4070169689Skan return create_function_info_for (decl, name); 4071169689Skan 4072169689Skan hasunion = TREE_CODE (decltype) == UNION_TYPE 4073171825Skan || TREE_CODE (decltype) == QUAL_UNION_TYPE; 4074169689Skan if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion) 4075169689Skan { 4076169689Skan push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion); 4077169689Skan if (hasunion) 4078169689Skan { 4079169689Skan VEC_free (fieldoff_s, heap, fieldstack); 4080169689Skan notokay = true; 4081169689Skan } 4082169689Skan } 4083169689Skan 4084171825Skan 4085169689Skan /* If the variable doesn't have subvars, we may end up needing to 4086169689Skan sort the field list and create fake variables for all the 4087169689Skan fields. */ 4088171825Skan vi = new_var_info (decl, index, name); 4089169689Skan vi->decl = decl; 4090169689Skan vi->offset = 0; 4091169689Skan vi->has_union = hasunion; 4092169689Skan if (!declsize 4093169689Skan || TREE_CODE (declsize) != INTEGER_CST 4094169689Skan || TREE_CODE (decltype) == UNION_TYPE 4095169689Skan || TREE_CODE (decltype) == QUAL_UNION_TYPE) 4096169689Skan { 4097169689Skan vi->is_unknown_size_var = true; 4098169689Skan vi->fullsize = ~0; 4099169689Skan vi->size = ~0; 4100169689Skan } 4101169689Skan else 4102169689Skan { 4103169689Skan vi->fullsize = TREE_INT_CST_LOW (declsize); 4104169689Skan vi->size = vi->fullsize; 4105169689Skan } 4106171825Skan 4107171825Skan insert_vi_for_tree (vi->decl, vi); 4108169689Skan VEC_safe_push (varinfo_t, heap, varmap, vi); 4109169689Skan if (is_global && (!flag_whole_program || !in_ipa_mode)) 4110169689Skan { 4111169689Skan make_constraint_from_escaped (vi); 4112169689Skan 4113169689Skan /* If the variable can't be aliased, there is no point in 4114169689Skan putting it in the set of nonlocal vars. */ 4115169689Skan if (may_be_aliased (vi->decl)) 4116169689Skan { 4117169689Skan struct constraint_expr rhs; 4118169689Skan rhs.var = index; 4119169689Skan rhs.type = ADDRESSOF; 4120169689Skan rhs.offset = 0; 4121169689Skan make_constraint_to_escaped (rhs); 4122169689Skan } 4123169689Skan 4124169689Skan if (TREE_CODE (decl) != FUNCTION_DECL && DECL_INITIAL (decl)) 4125169689Skan { 4126169689Skan walk_tree_without_duplicates (&DECL_INITIAL (decl), 4127169689Skan find_global_initializers, 4128169689Skan (void *)vi); 4129169689Skan } 4130169689Skan } 4131169689Skan 4132169689Skan stats.total_vars++; 4133171825Skan if (use_field_sensitive 4134171825Skan && !notokay 4135171825Skan && !vi->is_unknown_size_var 4136169689Skan && var_can_have_subvars (decl) 4137169689Skan && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE) 4138169689Skan { 4139169689Skan unsigned int newindex = VEC_length (varinfo_t, varmap); 4140169689Skan fieldoff_s *fo = NULL; 4141169689Skan unsigned int i; 4142169689Skan 4143169689Skan for (i = 0; !notokay && VEC_iterate (fieldoff_s, fieldstack, i, fo); i++) 4144169689Skan { 4145169689Skan if (! fo->size 4146169689Skan || TREE_CODE (fo->size) != INTEGER_CST 4147169689Skan || fo->offset < 0) 4148169689Skan { 4149169689Skan notokay = true; 4150169689Skan break; 4151169689Skan } 4152169689Skan } 4153169689Skan 4154169689Skan /* We can't sort them if we have a field with a variable sized type, 4155169689Skan which will make notokay = true. In that case, we are going to return 4156169689Skan without creating varinfos for the fields anyway, so sorting them is a 4157169689Skan waste to boot. */ 4158169689Skan if (!notokay) 4159171825Skan { 4160169689Skan sort_fieldstack (fieldstack); 4161169689Skan /* Due to some C++ FE issues, like PR 22488, we might end up 4162169689Skan what appear to be overlapping fields even though they, 4163169689Skan in reality, do not overlap. Until the C++ FE is fixed, 4164169689Skan we will simply disable field-sensitivity for these cases. */ 4165169689Skan notokay = check_for_overlaps (fieldstack); 4166169689Skan } 4167171825Skan 4168171825Skan 4169169689Skan if (VEC_length (fieldoff_s, fieldstack) != 0) 4170169689Skan fo = VEC_index (fieldoff_s, fieldstack, 0); 4171169689Skan 4172169689Skan if (fo == NULL || notokay) 4173169689Skan { 4174169689Skan vi->is_unknown_size_var = 1; 4175169689Skan vi->fullsize = ~0; 4176169689Skan vi->size = ~0; 4177169689Skan VEC_free (fieldoff_s, heap, fieldstack); 4178169689Skan return index; 4179169689Skan } 4180171825Skan 4181169689Skan vi->size = TREE_INT_CST_LOW (fo->size); 4182169689Skan vi->offset = fo->offset; 4183171825Skan for (i = VEC_length (fieldoff_s, fieldstack) - 1; 4184171825Skan i >= 1 && VEC_iterate (fieldoff_s, fieldstack, i, fo); 4185169689Skan i--) 4186169689Skan { 4187169689Skan varinfo_t newvi; 4188169689Skan const char *newname = "NULL"; 4189169689Skan char *tempname; 4190169689Skan 4191169689Skan newindex = VEC_length (varinfo_t, varmap); 4192169689Skan if (dump_file) 4193169689Skan { 4194169689Skan if (fo->decl) 4195171825Skan asprintf (&tempname, "%s.%s", 4196169689Skan vi->name, alias_get_name (fo->decl)); 4197169689Skan else 4198171825Skan asprintf (&tempname, "%s." HOST_WIDE_INT_PRINT_DEC, 4199169689Skan vi->name, fo->offset); 4200169689Skan newname = ggc_strdup (tempname); 4201169689Skan free (tempname); 4202169689Skan } 4203171825Skan newvi = new_var_info (decl, newindex, newname); 4204169689Skan newvi->offset = fo->offset; 4205169689Skan newvi->size = TREE_INT_CST_LOW (fo->size); 4206169689Skan newvi->fullsize = vi->fullsize; 4207169689Skan insert_into_field_list (vi, newvi); 4208169689Skan VEC_safe_push (varinfo_t, heap, varmap, newvi); 4209169689Skan if (is_global && (!flag_whole_program || !in_ipa_mode)) 4210169689Skan { 4211169689Skan /* If the variable can't be aliased, there is no point in 4212169689Skan putting it in the set of nonlocal vars. */ 4213169689Skan if (may_be_aliased (vi->decl)) 4214169689Skan { 4215169689Skan struct constraint_expr rhs; 4216169689Skan 4217169689Skan rhs.var = newindex; 4218169689Skan rhs.type = ADDRESSOF; 4219169689Skan rhs.offset = 0; 4220169689Skan make_constraint_to_escaped (rhs); 4221169689Skan } 4222169689Skan make_constraint_from_escaped (newvi); 4223169689Skan } 4224169689Skan 4225169689Skan stats.total_vars++; 4226169689Skan } 4227169689Skan VEC_free (fieldoff_s, heap, fieldstack); 4228169689Skan } 4229169689Skan return index; 4230169689Skan} 4231169689Skan 4232169689Skan/* Print out the points-to solution for VAR to FILE. */ 4233169689Skan 4234169689Skanvoid 4235169689Skandump_solution_for_var (FILE *file, unsigned int var) 4236169689Skan{ 4237169689Skan varinfo_t vi = get_varinfo (var); 4238169689Skan unsigned int i; 4239171825Skan bitmap_iterator bi; 4240171825Skan 4241171825Skan if (find (var) != var) 4242169689Skan { 4243171825Skan varinfo_t vipt = get_varinfo (find (var)); 4244171825Skan fprintf (file, "%s = same as %s\n", vi->name, vipt->name); 4245169689Skan } 4246171825Skan else 4247171825Skan { 4248171825Skan fprintf (file, "%s = { ", vi->name); 4249171825Skan EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi) 4250171825Skan { 4251171825Skan fprintf (file, "%s ", get_varinfo (i)->name); 4252171825Skan } 4253171825Skan fprintf (file, "}\n"); 4254171825Skan } 4255169689Skan} 4256169689Skan 4257169689Skan/* Print the points-to solution for VAR to stdout. */ 4258169689Skan 4259169689Skanvoid 4260169689Skandebug_solution_for_var (unsigned int var) 4261169689Skan{ 4262169689Skan dump_solution_for_var (stdout, var); 4263169689Skan} 4264169689Skan 4265169689Skan/* Create varinfo structures for all of the variables in the 4266169689Skan function for intraprocedural mode. */ 4267169689Skan 4268169689Skanstatic void 4269169689Skanintra_create_variable_infos (void) 4270169689Skan{ 4271169689Skan tree t; 4272169689Skan struct constraint_expr lhs, rhs; 4273169689Skan varinfo_t nonlocal_vi; 4274169689Skan 4275169689Skan /* For each incoming pointer argument arg, ARG = ESCAPED_VARS or a 4276169689Skan dummy variable if flag_argument_noalias > 2. */ 4277169689Skan for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t)) 4278169689Skan { 4279169689Skan varinfo_t p; 4280169689Skan unsigned int arg_id; 4281169689Skan 4282169689Skan if (!could_have_pointers (t)) 4283169689Skan continue; 4284169689Skan 4285171825Skan arg_id = get_vi_for_tree (t)->id; 4286169689Skan 4287169689Skan /* With flag_argument_noalias greater than two means that the incoming 4288169689Skan argument cannot alias anything except for itself so create a HEAP 4289169689Skan variable. */ 4290169689Skan if (POINTER_TYPE_P (TREE_TYPE (t)) 4291169689Skan && flag_argument_noalias > 2) 4292169689Skan { 4293169689Skan varinfo_t vi; 4294169689Skan tree heapvar = heapvar_lookup (t); 4295169689Skan 4296169689Skan lhs.offset = 0; 4297169689Skan lhs.type = SCALAR; 4298171825Skan lhs.var = get_vi_for_tree (t)->id; 4299169689Skan 4300169689Skan if (heapvar == NULL_TREE) 4301169689Skan { 4302169689Skan heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)), 4303169689Skan "PARM_NOALIAS"); 4304169689Skan DECL_EXTERNAL (heapvar) = 1; 4305169689Skan if (referenced_vars) 4306169689Skan add_referenced_var (heapvar); 4307169689Skan heapvar_insert (t, heapvar); 4308169689Skan } 4309171825Skan 4310171825Skan vi = get_vi_for_tree (heapvar); 4311169689Skan vi->is_artificial_var = 1; 4312169689Skan vi->is_heap_var = 1; 4313171825Skan rhs.var = vi->id; 4314169689Skan rhs.type = ADDRESSOF; 4315169689Skan rhs.offset = 0; 4316169689Skan for (p = get_varinfo (lhs.var); p; p = p->next) 4317169689Skan { 4318169689Skan struct constraint_expr temp = lhs; 4319169689Skan temp.var = p->id; 4320169689Skan process_constraint (new_constraint (temp, rhs)); 4321169689Skan } 4322169689Skan } 4323169689Skan else 4324169689Skan { 4325169689Skan for (p = get_varinfo (arg_id); p; p = p->next) 4326169689Skan make_constraint_from_escaped (p); 4327169689Skan } 4328169689Skan } 4329169689Skan if (!nonlocal_all) 4330169689Skan nonlocal_all = create_nonlocal_var (void_type_node); 4331169689Skan 4332169689Skan /* Create variable info for the nonlocal var if it does not 4333169689Skan exist. */ 4334169689Skan nonlocal_vars_id = create_variable_info_for (nonlocal_all, 4335169689Skan get_name (nonlocal_all)); 4336169689Skan nonlocal_vi = get_varinfo (nonlocal_vars_id); 4337169689Skan nonlocal_vi->is_artificial_var = 1; 4338169689Skan nonlocal_vi->is_heap_var = 1; 4339169689Skan nonlocal_vi->is_unknown_size_var = 1; 4340169689Skan nonlocal_vi->directly_dereferenced = true; 4341169689Skan 4342169689Skan rhs.var = nonlocal_vars_id; 4343169689Skan rhs.type = ADDRESSOF; 4344169689Skan rhs.offset = 0; 4345169689Skan 4346169689Skan lhs.var = escaped_vars_id; 4347169689Skan lhs.type = SCALAR; 4348169689Skan lhs.offset = 0; 4349169689Skan 4350169689Skan process_constraint (new_constraint (lhs, rhs)); 4351169689Skan} 4352169689Skan 4353220150Smm/* Structure used to put solution bitmaps in a hashtable so they can 4354220150Smm be shared among variables with the same points-to set. */ 4355220150Smm 4356220150Smmtypedef struct shared_bitmap_info 4357220150Smm{ 4358220150Smm bitmap pt_vars; 4359220150Smm hashval_t hashcode; 4360220150Smm} *shared_bitmap_info_t; 4361220150Smm 4362220150Smmstatic htab_t shared_bitmap_table; 4363220150Smm 4364220150Smm/* Hash function for a shared_bitmap_info_t */ 4365220150Smm 4366220150Smmstatic hashval_t 4367220150Smmshared_bitmap_hash (const void *p) 4368220150Smm{ 4369220150Smm const shared_bitmap_info_t bi = (shared_bitmap_info_t) p; 4370220150Smm return bi->hashcode; 4371220150Smm} 4372220150Smm 4373220150Smm/* Equality function for two shared_bitmap_info_t's. */ 4374220150Smm 4375220150Smmstatic int 4376220150Smmshared_bitmap_eq (const void *p1, const void *p2) 4377220150Smm{ 4378220150Smm const shared_bitmap_info_t sbi1 = (shared_bitmap_info_t) p1; 4379220150Smm const shared_bitmap_info_t sbi2 = (shared_bitmap_info_t) p2; 4380220150Smm return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars); 4381220150Smm} 4382220150Smm 4383220150Smm/* Lookup a bitmap in the shared bitmap hashtable, and return an already 4384220150Smm existing instance if there is one, NULL otherwise. */ 4385220150Smm 4386220150Smmstatic bitmap 4387220150Smmshared_bitmap_lookup (bitmap pt_vars) 4388220150Smm{ 4389220150Smm void **slot; 4390220150Smm struct shared_bitmap_info sbi; 4391220150Smm 4392220150Smm sbi.pt_vars = pt_vars; 4393220150Smm sbi.hashcode = bitmap_hash (pt_vars); 4394220150Smm 4395220150Smm slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi, 4396220150Smm sbi.hashcode, NO_INSERT); 4397220150Smm if (!slot) 4398220150Smm return NULL; 4399220150Smm else 4400220150Smm return ((shared_bitmap_info_t) *slot)->pt_vars; 4401220150Smm} 4402220150Smm 4403220150Smm 4404220150Smm/* Add a bitmap to the shared bitmap hashtable. */ 4405220150Smm 4406220150Smmstatic void 4407220150Smmshared_bitmap_add (bitmap pt_vars) 4408220150Smm{ 4409220150Smm void **slot; 4410220150Smm shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info); 4411220150Smm 4412220150Smm sbi->pt_vars = pt_vars; 4413220150Smm sbi->hashcode = bitmap_hash (pt_vars); 4414220150Smm 4415220150Smm slot = htab_find_slot_with_hash (shared_bitmap_table, sbi, 4416220150Smm sbi->hashcode, INSERT); 4417220150Smm gcc_assert (!*slot); 4418220150Smm *slot = (void *) sbi; 4419220150Smm} 4420220150Smm 4421220150Smm 4422169689Skan/* Set bits in INTO corresponding to the variable uids in solution set 4423169689Skan FROM, which came from variable PTR. 4424169689Skan For variables that are actually dereferenced, we also use type 4425169689Skan based alias analysis to prune the points-to sets. */ 4426169689Skan 4427169689Skanstatic void 4428169689Skanset_uids_in_ptset (tree ptr, bitmap into, bitmap from) 4429169689Skan{ 4430169689Skan unsigned int i; 4431169689Skan bitmap_iterator bi; 4432169689Skan subvar_t sv; 4433169689Skan unsigned HOST_WIDE_INT ptr_alias_set = get_alias_set (TREE_TYPE (ptr)); 4434169689Skan 4435169689Skan EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi) 4436169689Skan { 4437169689Skan varinfo_t vi = get_varinfo (i); 4438169689Skan unsigned HOST_WIDE_INT var_alias_set; 4439169689Skan 4440169689Skan /* The only artificial variables that are allowed in a may-alias 4441169689Skan set are heap variables. */ 4442169689Skan if (vi->is_artificial_var && !vi->is_heap_var) 4443169689Skan continue; 4444169689Skan 4445169689Skan if (vi->has_union && get_subvars_for_var (vi->decl) != NULL) 4446169689Skan { 4447169689Skan /* Variables containing unions may need to be converted to 4448169689Skan their SFT's, because SFT's can have unions and we cannot. */ 4449169689Skan for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next) 4450169689Skan bitmap_set_bit (into, DECL_UID (sv->var)); 4451169689Skan } 4452169689Skan else if (TREE_CODE (vi->decl) == VAR_DECL 4453171825Skan || TREE_CODE (vi->decl) == PARM_DECL 4454171825Skan || TREE_CODE (vi->decl) == RESULT_DECL) 4455169689Skan { 4456169689Skan if (var_can_have_subvars (vi->decl) 4457169689Skan && get_subvars_for_var (vi->decl)) 4458169689Skan { 4459169689Skan /* If VI->DECL is an aggregate for which we created 4460169689Skan SFTs, add the SFT corresponding to VI->OFFSET. */ 4461169689Skan tree sft = get_subvar_at (vi->decl, vi->offset); 4462169689Skan if (sft) 4463169689Skan { 4464169689Skan var_alias_set = get_alias_set (sft); 4465169689Skan if (!vi->directly_dereferenced 4466169689Skan || alias_sets_conflict_p (ptr_alias_set, var_alias_set)) 4467169689Skan bitmap_set_bit (into, DECL_UID (sft)); 4468169689Skan } 4469169689Skan } 4470169689Skan else 4471169689Skan { 4472169689Skan /* Otherwise, just add VI->DECL to the alias set. 4473169689Skan Don't type prune artificial vars. */ 4474169689Skan if (vi->is_artificial_var) 4475169689Skan bitmap_set_bit (into, DECL_UID (vi->decl)); 4476169689Skan else 4477169689Skan { 4478169689Skan var_alias_set = get_alias_set (vi->decl); 4479169689Skan if (!vi->directly_dereferenced 4480169689Skan || alias_sets_conflict_p (ptr_alias_set, var_alias_set)) 4481169689Skan bitmap_set_bit (into, DECL_UID (vi->decl)); 4482169689Skan } 4483169689Skan } 4484169689Skan } 4485169689Skan } 4486169689Skan} 4487169689Skan 4488169689Skan 4489169689Skanstatic bool have_alias_info = false; 4490169689Skan 4491169689Skan/* Given a pointer variable P, fill in its points-to set, or return 4492169689Skan false if we can't. */ 4493169689Skan 4494169689Skanbool 4495169689Skanfind_what_p_points_to (tree p) 4496169689Skan{ 4497169689Skan tree lookup_p = p; 4498171825Skan varinfo_t vi; 4499169689Skan 4500169689Skan if (!have_alias_info) 4501169689Skan return false; 4502169689Skan 4503169689Skan /* For parameters, get at the points-to set for the actual parm 4504169689Skan decl. */ 4505169689Skan if (TREE_CODE (p) == SSA_NAME 4506169689Skan && TREE_CODE (SSA_NAME_VAR (p)) == PARM_DECL 4507169689Skan && default_def (SSA_NAME_VAR (p)) == p) 4508169689Skan lookup_p = SSA_NAME_VAR (p); 4509169689Skan 4510171825Skan vi = lookup_vi_for_tree (lookup_p); 4511171825Skan if (vi) 4512169689Skan { 4513171825Skan 4514169689Skan if (vi->is_artificial_var) 4515169689Skan return false; 4516169689Skan 4517169689Skan /* See if this is a field or a structure. */ 4518169689Skan if (vi->size != vi->fullsize) 4519169689Skan { 4520169689Skan /* Nothing currently asks about structure fields directly, 4521169689Skan but when they do, we need code here to hand back the 4522169689Skan points-to set. */ 4523169689Skan if (!var_can_have_subvars (vi->decl) 4524169689Skan || get_subvars_for_var (vi->decl) == NULL) 4525169689Skan return false; 4526169689Skan } 4527169689Skan else 4528169689Skan { 4529169689Skan struct ptr_info_def *pi = get_ptr_info (p); 4530169689Skan unsigned int i; 4531169689Skan bitmap_iterator bi; 4532220150Smm bitmap finished_solution; 4533220150Smm bitmap result; 4534220150Smm 4535169689Skan /* This variable may have been collapsed, let's get the real 4536169689Skan variable. */ 4537171825Skan vi = get_varinfo (find (vi->id)); 4538169689Skan 4539169689Skan /* Translate artificial variables into SSA_NAME_PTR_INFO 4540169689Skan attributes. */ 4541169689Skan EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi) 4542169689Skan { 4543169689Skan varinfo_t vi = get_varinfo (i); 4544169689Skan 4545169689Skan if (vi->is_artificial_var) 4546169689Skan { 4547169689Skan /* FIXME. READONLY should be handled better so that 4548169689Skan flow insensitive aliasing can disregard writable 4549169689Skan aliases. */ 4550169689Skan if (vi->id == nothing_id) 4551169689Skan pi->pt_null = 1; 4552169689Skan else if (vi->id == anything_id) 4553169689Skan pi->pt_anything = 1; 4554169689Skan else if (vi->id == readonly_id) 4555169689Skan pi->pt_anything = 1; 4556169689Skan else if (vi->id == integer_id) 4557169689Skan pi->pt_anything = 1; 4558169689Skan else if (vi->is_heap_var) 4559169689Skan pi->pt_global_mem = 1; 4560169689Skan } 4561169689Skan } 4562169689Skan 4563169689Skan if (pi->pt_anything) 4564169689Skan return false; 4565169689Skan 4566220150Smm finished_solution = BITMAP_GGC_ALLOC (); 4567220150Smm set_uids_in_ptset (vi->decl, finished_solution, vi->solution); 4568220150Smm result = shared_bitmap_lookup (finished_solution); 4569169689Skan 4570220150Smm if (!result) 4571220150Smm { 4572220150Smm shared_bitmap_add (finished_solution); 4573220150Smm pi->pt_vars = finished_solution; 4574220150Smm } 4575220150Smm else 4576220150Smm { 4577220150Smm pi->pt_vars = result; 4578220150Smm bitmap_clear (finished_solution); 4579220150Smm } 4580169689Skan 4581169689Skan if (bitmap_empty_p (pi->pt_vars)) 4582169689Skan pi->pt_vars = NULL; 4583169689Skan 4584169689Skan return true; 4585169689Skan } 4586169689Skan } 4587169689Skan 4588169689Skan return false; 4589169689Skan} 4590169689Skan 4591169689Skan 4592169689Skan 4593169689Skan/* Dump points-to information to OUTFILE. */ 4594169689Skan 4595169689Skanvoid 4596169689Skandump_sa_points_to_info (FILE *outfile) 4597169689Skan{ 4598169689Skan unsigned int i; 4599169689Skan 4600169689Skan fprintf (outfile, "\nPoints-to sets\n\n"); 4601169689Skan 4602169689Skan if (dump_flags & TDF_STATS) 4603169689Skan { 4604169689Skan fprintf (outfile, "Stats:\n"); 4605169689Skan fprintf (outfile, "Total vars: %d\n", stats.total_vars); 4606171825Skan fprintf (outfile, "Non-pointer vars: %d\n", 4607171825Skan stats.nonpointer_vars); 4608169689Skan fprintf (outfile, "Statically unified vars: %d\n", 4609169689Skan stats.unified_vars_static); 4610169689Skan fprintf (outfile, "Dynamically unified vars: %d\n", 4611169689Skan stats.unified_vars_dynamic); 4612169689Skan fprintf (outfile, "Iterations: %d\n", stats.iterations); 4613169689Skan fprintf (outfile, "Number of edges: %d\n", stats.num_edges); 4614171825Skan fprintf (outfile, "Number of implicit edges: %d\n", 4615171825Skan stats.num_implicit_edges); 4616169689Skan } 4617169689Skan 4618169689Skan for (i = 0; i < VEC_length (varinfo_t, varmap); i++) 4619169689Skan dump_solution_for_var (outfile, i); 4620169689Skan} 4621169689Skan 4622169689Skan 4623169689Skan/* Debug points-to information to stderr. */ 4624169689Skan 4625169689Skanvoid 4626169689Skandebug_sa_points_to_info (void) 4627169689Skan{ 4628169689Skan dump_sa_points_to_info (stderr); 4629169689Skan} 4630169689Skan 4631169689Skan 4632169689Skan/* Initialize the always-existing constraint variables for NULL 4633169689Skan ANYTHING, READONLY, and INTEGER */ 4634169689Skan 4635169689Skanstatic void 4636169689Skaninit_base_vars (void) 4637169689Skan{ 4638169689Skan struct constraint_expr lhs, rhs; 4639169689Skan 4640169689Skan /* Create the NULL variable, used to represent that a variable points 4641169689Skan to NULL. */ 4642169689Skan nothing_tree = create_tmp_var_raw (void_type_node, "NULL"); 4643171825Skan var_nothing = new_var_info (nothing_tree, 0, "NULL"); 4644171825Skan insert_vi_for_tree (nothing_tree, var_nothing); 4645169689Skan var_nothing->is_artificial_var = 1; 4646169689Skan var_nothing->offset = 0; 4647169689Skan var_nothing->size = ~0; 4648169689Skan var_nothing->fullsize = ~0; 4649169689Skan var_nothing->is_special_var = 1; 4650169689Skan nothing_id = 0; 4651169689Skan VEC_safe_push (varinfo_t, heap, varmap, var_nothing); 4652169689Skan 4653169689Skan /* Create the ANYTHING variable, used to represent that a variable 4654169689Skan points to some unknown piece of memory. */ 4655169689Skan anything_tree = create_tmp_var_raw (void_type_node, "ANYTHING"); 4656171825Skan var_anything = new_var_info (anything_tree, 1, "ANYTHING"); 4657171825Skan insert_vi_for_tree (anything_tree, var_anything); 4658169689Skan var_anything->is_artificial_var = 1; 4659169689Skan var_anything->size = ~0; 4660169689Skan var_anything->offset = 0; 4661169689Skan var_anything->next = NULL; 4662169689Skan var_anything->fullsize = ~0; 4663169689Skan var_anything->is_special_var = 1; 4664169689Skan anything_id = 1; 4665169689Skan 4666169689Skan /* Anything points to anything. This makes deref constraints just 4667169689Skan work in the presence of linked list and other p = *p type loops, 4668169689Skan by saying that *ANYTHING = ANYTHING. */ 4669169689Skan VEC_safe_push (varinfo_t, heap, varmap, var_anything); 4670169689Skan lhs.type = SCALAR; 4671169689Skan lhs.var = anything_id; 4672169689Skan lhs.offset = 0; 4673169689Skan rhs.type = ADDRESSOF; 4674169689Skan rhs.var = anything_id; 4675169689Skan rhs.offset = 0; 4676169689Skan 4677169689Skan /* This specifically does not use process_constraint because 4678169689Skan process_constraint ignores all anything = anything constraints, since all 4679169689Skan but this one are redundant. */ 4680169689Skan VEC_safe_push (constraint_t, heap, constraints, new_constraint (lhs, rhs)); 4681169689Skan 4682169689Skan /* Create the READONLY variable, used to represent that a variable 4683169689Skan points to readonly memory. */ 4684169689Skan readonly_tree = create_tmp_var_raw (void_type_node, "READONLY"); 4685171825Skan var_readonly = new_var_info (readonly_tree, 2, "READONLY"); 4686169689Skan var_readonly->is_artificial_var = 1; 4687169689Skan var_readonly->offset = 0; 4688169689Skan var_readonly->size = ~0; 4689169689Skan var_readonly->fullsize = ~0; 4690169689Skan var_readonly->next = NULL; 4691169689Skan var_readonly->is_special_var = 1; 4692171825Skan insert_vi_for_tree (readonly_tree, var_readonly); 4693169689Skan readonly_id = 2; 4694169689Skan VEC_safe_push (varinfo_t, heap, varmap, var_readonly); 4695169689Skan 4696169689Skan /* readonly memory points to anything, in order to make deref 4697169689Skan easier. In reality, it points to anything the particular 4698169689Skan readonly variable can point to, but we don't track this 4699169689Skan separately. */ 4700169689Skan lhs.type = SCALAR; 4701169689Skan lhs.var = readonly_id; 4702169689Skan lhs.offset = 0; 4703169689Skan rhs.type = ADDRESSOF; 4704169689Skan rhs.var = anything_id; 4705169689Skan rhs.offset = 0; 4706169689Skan 4707169689Skan process_constraint (new_constraint (lhs, rhs)); 4708169689Skan 4709169689Skan /* Create the INTEGER variable, used to represent that a variable points 4710169689Skan to an INTEGER. */ 4711169689Skan integer_tree = create_tmp_var_raw (void_type_node, "INTEGER"); 4712171825Skan var_integer = new_var_info (integer_tree, 3, "INTEGER"); 4713171825Skan insert_vi_for_tree (integer_tree, var_integer); 4714169689Skan var_integer->is_artificial_var = 1; 4715169689Skan var_integer->size = ~0; 4716169689Skan var_integer->fullsize = ~0; 4717169689Skan var_integer->offset = 0; 4718169689Skan var_integer->next = NULL; 4719169689Skan var_integer->is_special_var = 1; 4720169689Skan integer_id = 3; 4721169689Skan VEC_safe_push (varinfo_t, heap, varmap, var_integer); 4722169689Skan 4723169689Skan /* INTEGER = ANYTHING, because we don't know where a dereference of 4724169689Skan a random integer will point to. */ 4725169689Skan lhs.type = SCALAR; 4726169689Skan lhs.var = integer_id; 4727169689Skan lhs.offset = 0; 4728169689Skan rhs.type = ADDRESSOF; 4729169689Skan rhs.var = anything_id; 4730169689Skan rhs.offset = 0; 4731169689Skan process_constraint (new_constraint (lhs, rhs)); 4732169689Skan 4733169689Skan /* Create the ESCAPED_VARS variable used to represent variables that 4734169689Skan escape this function. */ 4735169689Skan escaped_vars_tree = create_tmp_var_raw (void_type_node, "ESCAPED_VARS"); 4736171825Skan var_escaped_vars = new_var_info (escaped_vars_tree, 4, "ESCAPED_VARS"); 4737171825Skan insert_vi_for_tree (escaped_vars_tree, var_escaped_vars); 4738169689Skan var_escaped_vars->is_artificial_var = 1; 4739169689Skan var_escaped_vars->size = ~0; 4740169689Skan var_escaped_vars->fullsize = ~0; 4741169689Skan var_escaped_vars->offset = 0; 4742169689Skan var_escaped_vars->next = NULL; 4743169689Skan escaped_vars_id = 4; 4744169689Skan VEC_safe_push (varinfo_t, heap, varmap, var_escaped_vars); 4745169689Skan 4746169689Skan /* ESCAPED_VARS = *ESCAPED_VARS */ 4747169689Skan lhs.type = SCALAR; 4748169689Skan lhs.var = escaped_vars_id; 4749169689Skan lhs.offset = 0; 4750169689Skan rhs.type = DEREF; 4751169689Skan rhs.var = escaped_vars_id; 4752169689Skan rhs.offset = 0; 4753169689Skan process_constraint (new_constraint (lhs, rhs)); 4754169689Skan 4755169689Skan} 4756169689Skan 4757169689Skan/* Initialize things necessary to perform PTA */ 4758169689Skan 4759169689Skanstatic void 4760169689Skaninit_alias_vars (void) 4761169689Skan{ 4762171825Skan bitmap_obstack_initialize (&pta_obstack); 4763171825Skan bitmap_obstack_initialize (&oldpta_obstack); 4764169689Skan bitmap_obstack_initialize (&predbitmap_obstack); 4765169689Skan 4766171825Skan constraint_pool = create_alloc_pool ("Constraint pool", 4767169689Skan sizeof (struct constraint), 30); 4768169689Skan variable_info_pool = create_alloc_pool ("Variable info pool", 4769169689Skan sizeof (struct variable_info), 30); 4770169689Skan constraints = VEC_alloc (constraint_t, heap, 8); 4771169689Skan varmap = VEC_alloc (varinfo_t, heap, 8); 4772171825Skan vi_for_tree = pointer_map_create (); 4773171825Skan 4774169689Skan memset (&stats, 0, sizeof (stats)); 4775220150Smm shared_bitmap_table = htab_create (511, shared_bitmap_hash, 4776220150Smm shared_bitmap_eq, free); 4777169689Skan init_base_vars (); 4778169689Skan} 4779169689Skan 4780169689Skan/* Given a statement STMT, generate necessary constraints to 4781169689Skan escaped_vars for the escaping variables. */ 4782169689Skan 4783169689Skanstatic void 4784169689Skanfind_escape_constraints (tree stmt) 4785169689Skan{ 4786169689Skan enum escape_type stmt_escape_type = is_escape_site (stmt); 4787169689Skan tree rhs; 4788169689Skan VEC(ce_s, heap) *rhsc = NULL; 4789169689Skan struct constraint_expr *c; 4790169689Skan size_t i; 4791169689Skan 4792169689Skan if (stmt_escape_type == NO_ESCAPE) 4793169689Skan return; 4794169689Skan 4795169689Skan if (TREE_CODE (stmt) == RETURN_EXPR) 4796169689Skan { 4797169689Skan /* Returns are either bare, with an embedded MODIFY_EXPR, or 4798169689Skan just a plain old expression. */ 4799169689Skan if (!TREE_OPERAND (stmt, 0)) 4800169689Skan return; 4801169689Skan if (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) 4802169689Skan rhs = TREE_OPERAND (TREE_OPERAND (stmt, 0), 1); 4803169689Skan else 4804169689Skan rhs = TREE_OPERAND (stmt, 0); 4805169689Skan 4806169689Skan get_constraint_for (rhs, &rhsc); 4807169689Skan for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) 4808169689Skan make_constraint_to_escaped (*c); 4809169689Skan VEC_free (ce_s, heap, rhsc); 4810169689Skan return; 4811169689Skan } 4812169689Skan else if (TREE_CODE (stmt) == ASM_EXPR) 4813169689Skan { 4814169689Skan /* Whatever the inputs of the ASM are, escape. */ 4815169689Skan tree arg; 4816169689Skan 4817169689Skan for (arg = ASM_INPUTS (stmt); arg; arg = TREE_CHAIN (arg)) 4818169689Skan { 4819169689Skan rhsc = NULL; 4820169689Skan get_constraint_for (TREE_VALUE (arg), &rhsc); 4821169689Skan for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) 4822169689Skan make_constraint_to_escaped (*c); 4823169689Skan VEC_free (ce_s, heap, rhsc); 4824169689Skan } 4825169689Skan return; 4826169689Skan } 4827169689Skan else if (TREE_CODE (stmt) == CALL_EXPR 4828169689Skan || (TREE_CODE (stmt) == MODIFY_EXPR 4829169689Skan && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR)) 4830169689Skan { 4831169689Skan /* Calls cause all of the arguments passed in to escape. */ 4832169689Skan tree arg; 4833169689Skan 4834169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR) 4835169689Skan stmt = TREE_OPERAND (stmt, 1); 4836169689Skan for (arg = TREE_OPERAND (stmt, 1); arg; arg = TREE_CHAIN (arg)) 4837169689Skan { 4838169689Skan if (POINTER_TYPE_P (TREE_TYPE (TREE_VALUE (arg)))) 4839169689Skan { 4840169689Skan rhsc = NULL; 4841169689Skan get_constraint_for (TREE_VALUE (arg), &rhsc); 4842169689Skan for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) 4843169689Skan make_constraint_to_escaped (*c); 4844169689Skan VEC_free (ce_s, heap, rhsc); 4845169689Skan } 4846169689Skan } 4847169689Skan return; 4848169689Skan } 4849169689Skan else 4850169689Skan { 4851169689Skan gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR); 4852169689Skan } 4853169689Skan 4854169689Skan gcc_assert (stmt_escape_type == ESCAPE_BAD_CAST 4855169689Skan || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL 4856169689Skan || stmt_escape_type == ESCAPE_UNKNOWN); 4857169689Skan rhs = TREE_OPERAND (stmt, 1); 4858169689Skan 4859169689Skan /* Look through casts for the real escaping variable. 4860169689Skan Constants don't really escape, so ignore them. 4861169689Skan Otherwise, whatever escapes must be on our RHS. */ 4862169689Skan if (TREE_CODE (rhs) == NOP_EXPR 4863169689Skan || TREE_CODE (rhs) == CONVERT_EXPR 4864169689Skan || TREE_CODE (rhs) == NON_LVALUE_EXPR) 4865169689Skan { 4866169689Skan get_constraint_for (TREE_OPERAND (rhs, 0), &rhsc); 4867169689Skan } 4868169689Skan else if (CONSTANT_CLASS_P (rhs)) 4869169689Skan return; 4870169689Skan else 4871169689Skan { 4872169689Skan get_constraint_for (rhs, &rhsc); 4873169689Skan } 4874169689Skan for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) 4875169689Skan make_constraint_to_escaped (*c); 4876169689Skan VEC_free (ce_s, heap, rhsc); 4877169689Skan} 4878169689Skan 4879171825Skan 4880171825Skan/* Remove the REF and ADDRESS edges from GRAPH, as well as all the 4881171825Skan predecessor edges. */ 4882171825Skan 4883171825Skanstatic void 4884171825Skanremove_preds_and_fake_succs (constraint_graph_t graph) 4885171825Skan{ 4886171825Skan unsigned int i; 4887171825Skan 4888171825Skan /* Clear the implicit ref and address nodes from the successor 4889171825Skan lists. */ 4890171825Skan for (i = 0; i < FIRST_REF_NODE; i++) 4891171825Skan { 4892171825Skan if (graph->succs[i]) 4893171825Skan bitmap_clear_range (graph->succs[i], FIRST_REF_NODE, 4894171825Skan FIRST_REF_NODE * 2); 4895171825Skan } 4896171825Skan 4897171825Skan /* Free the successor list for the non-ref nodes. */ 4898171825Skan for (i = FIRST_REF_NODE; i < graph->size; i++) 4899171825Skan { 4900171825Skan if (graph->succs[i]) 4901171825Skan BITMAP_FREE (graph->succs[i]); 4902171825Skan } 4903171825Skan 4904171825Skan /* Now reallocate the size of the successor list as, and blow away 4905171825Skan the predecessor bitmaps. */ 4906171825Skan graph->size = VEC_length (varinfo_t, varmap); 4907171825Skan graph->succs = xrealloc (graph->succs, graph->size * sizeof (bitmap)); 4908171825Skan 4909171825Skan free (graph->implicit_preds); 4910171825Skan graph->implicit_preds = NULL; 4911171825Skan free (graph->preds); 4912171825Skan graph->preds = NULL; 4913171825Skan bitmap_obstack_release (&predbitmap_obstack); 4914171825Skan} 4915171825Skan 4916169689Skan/* Create points-to sets for the current function. See the comments 4917169689Skan at the start of the file for an algorithmic overview. */ 4918169689Skan 4919169689Skanvoid 4920169689Skancompute_points_to_sets (struct alias_info *ai) 4921169689Skan{ 4922169689Skan basic_block bb; 4923171825Skan struct scc_info *si; 4924169689Skan 4925169689Skan timevar_push (TV_TREE_PTA); 4926169689Skan 4927169689Skan init_alias_vars (); 4928171825Skan init_alias_heapvars (); 4929171825Skan 4930169689Skan intra_create_variable_infos (); 4931169689Skan 4932169689Skan /* Now walk all statements and derive aliases. */ 4933169689Skan FOR_EACH_BB (bb) 4934169689Skan { 4935169689Skan block_stmt_iterator bsi; 4936169689Skan tree phi; 4937169689Skan 4938169689Skan for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) 4939169689Skan { 4940169689Skan if (is_gimple_reg (PHI_RESULT (phi))) 4941169689Skan { 4942169689Skan find_func_aliases (phi); 4943169689Skan /* Update various related attributes like escaped 4944169689Skan addresses, pointer dereferences for loads and stores. 4945169689Skan This is used when creating name tags and alias 4946169689Skan sets. */ 4947169689Skan update_alias_info (phi, ai); 4948169689Skan } 4949169689Skan } 4950169689Skan 4951169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 4952169689Skan { 4953169689Skan tree stmt = bsi_stmt (bsi); 4954169689Skan 4955169689Skan find_func_aliases (stmt); 4956169689Skan find_escape_constraints (stmt); 4957169689Skan /* Update various related attributes like escaped 4958169689Skan addresses, pointer dereferences for loads and stores. 4959169689Skan This is used when creating name tags and alias 4960169689Skan sets. */ 4961169689Skan update_alias_info (stmt, ai); 4962169689Skan } 4963169689Skan } 4964169689Skan 4965169689Skan 4966169689Skan if (dump_file) 4967169689Skan { 4968169689Skan fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n"); 4969169689Skan dump_constraints (dump_file); 4970169689Skan } 4971171825Skan 4972169689Skan if (dump_file) 4973169689Skan fprintf (dump_file, 4974169689Skan "\nCollapsing static cycles and doing variable " 4975169689Skan "substitution:\n"); 4976171825Skan 4977171825Skan build_pred_graph (); 4978171825Skan si = perform_var_substitution (graph); 4979171825Skan move_complex_constraints (graph, si); 4980171825Skan free_var_substitution_info (si); 4981171825Skan 4982171825Skan build_succ_graph (); 4983171825Skan find_indirect_cycles (graph); 4984171825Skan 4985171825Skan /* Implicit nodes and predecessors are no longer necessary at this 4986171825Skan point. */ 4987171825Skan remove_preds_and_fake_succs (graph); 4988171825Skan 4989169689Skan if (dump_file) 4990169689Skan fprintf (dump_file, "\nSolving graph:\n"); 4991171825Skan 4992169689Skan solve_graph (graph); 4993171825Skan 4994169689Skan if (dump_file) 4995169689Skan dump_sa_points_to_info (dump_file); 4996169689Skan have_alias_info = true; 4997169689Skan 4998169689Skan timevar_pop (TV_TREE_PTA); 4999169689Skan} 5000169689Skan 5001169689Skan/* Delete created points-to sets. */ 5002169689Skan 5003169689Skanvoid 5004169689Skandelete_points_to_sets (void) 5005169689Skan{ 5006169689Skan varinfo_t v; 5007169689Skan int i; 5008171825Skan 5009220150Smm htab_delete (shared_bitmap_table); 5010171825Skan if (dump_file && (dump_flags & TDF_STATS)) 5011171825Skan fprintf (dump_file, "Points to sets created:%d\n", 5012171825Skan stats.points_to_sets_created); 5013171825Skan 5014171825Skan pointer_map_destroy (vi_for_tree); 5015171825Skan bitmap_obstack_release (&pta_obstack); 5016169689Skan VEC_free (constraint_t, heap, constraints); 5017171825Skan 5018169689Skan for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++) 5019171825Skan VEC_free (constraint_t, heap, graph->complex[i]); 5020171825Skan free (graph->complex); 5021169689Skan 5022171825Skan free (graph->rep); 5023169689Skan free (graph->succs); 5024171825Skan free (graph->indirect_cycles); 5025169689Skan free (graph); 5026169689Skan 5027169689Skan VEC_free (varinfo_t, heap, varmap); 5028169689Skan free_alloc_pool (variable_info_pool); 5029171825Skan free_alloc_pool (constraint_pool); 5030169689Skan have_alias_info = false; 5031169689Skan} 5032169689Skan 5033169689Skan/* Return true if we should execute IPA PTA. */ 5034169689Skanstatic bool 5035169689Skangate_ipa_pta (void) 5036169689Skan{ 5037169689Skan return (flag_unit_at_a_time != 0 5038169689Skan && flag_ipa_pta 5039169689Skan /* Don't bother doing anything if the program has errors. */ 5040169689Skan && !(errorcount || sorrycount)); 5041169689Skan} 5042169689Skan 5043169689Skan/* Execute the driver for IPA PTA. */ 5044169689Skanstatic unsigned int 5045169689Skanipa_pta_execute (void) 5046169689Skan{ 5047171825Skan#if 0 5048169689Skan struct cgraph_node *node; 5049169689Skan in_ipa_mode = 1; 5050169689Skan init_alias_heapvars (); 5051169689Skan init_alias_vars (); 5052169689Skan 5053169689Skan for (node = cgraph_nodes; node; node = node->next) 5054169689Skan { 5055169689Skan if (!node->analyzed || cgraph_is_master_clone (node)) 5056169689Skan { 5057169689Skan unsigned int varid; 5058169689Skan 5059169689Skan varid = create_function_info_for (node->decl, 5060169689Skan cgraph_node_name (node)); 5061169689Skan if (node->local.externally_visible) 5062169689Skan { 5063169689Skan varinfo_t fi = get_varinfo (varid); 5064169689Skan for (; fi; fi = fi->next) 5065169689Skan make_constraint_from_escaped (fi); 5066169689Skan } 5067169689Skan } 5068169689Skan } 5069169689Skan for (node = cgraph_nodes; node; node = node->next) 5070169689Skan { 5071169689Skan if (node->analyzed && cgraph_is_master_clone (node)) 5072169689Skan { 5073169689Skan struct function *cfun = DECL_STRUCT_FUNCTION (node->decl); 5074169689Skan basic_block bb; 5075169689Skan tree old_func_decl = current_function_decl; 5076169689Skan if (dump_file) 5077169689Skan fprintf (dump_file, 5078169689Skan "Generating constraints for %s\n", 5079169689Skan cgraph_node_name (node)); 5080169689Skan push_cfun (cfun); 5081169689Skan current_function_decl = node->decl; 5082169689Skan 5083169689Skan FOR_EACH_BB_FN (bb, cfun) 5084169689Skan { 5085169689Skan block_stmt_iterator bsi; 5086169689Skan tree phi; 5087169689Skan 5088169689Skan for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) 5089169689Skan { 5090169689Skan if (is_gimple_reg (PHI_RESULT (phi))) 5091169689Skan { 5092169689Skan find_func_aliases (phi); 5093169689Skan } 5094169689Skan } 5095169689Skan 5096169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 5097169689Skan { 5098169689Skan tree stmt = bsi_stmt (bsi); 5099169689Skan find_func_aliases (stmt); 5100169689Skan } 5101169689Skan } 5102169689Skan current_function_decl = old_func_decl; 5103169689Skan pop_cfun (); 5104169689Skan } 5105169689Skan else 5106169689Skan { 5107169689Skan /* Make point to anything. */ 5108169689Skan } 5109169689Skan } 5110169689Skan 5111169689Skan build_constraint_graph (); 5112169689Skan 5113169689Skan if (dump_file) 5114169689Skan { 5115169689Skan fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n"); 5116169689Skan dump_constraints (dump_file); 5117169689Skan } 5118169689Skan 5119169689Skan if (dump_file) 5120169689Skan fprintf (dump_file, 5121169689Skan "\nCollapsing static cycles and doing variable " 5122169689Skan "substitution:\n"); 5123169689Skan 5124169689Skan find_and_collapse_graph_cycles (graph, false); 5125169689Skan perform_var_substitution (graph); 5126169689Skan 5127169689Skan if (dump_file) 5128169689Skan fprintf (dump_file, "\nSolving graph:\n"); 5129169689Skan 5130169689Skan solve_graph (graph); 5131169689Skan 5132169689Skan if (dump_file) 5133169689Skan dump_sa_points_to_info (dump_file); 5134169689Skan in_ipa_mode = 0; 5135169689Skan delete_alias_heapvars (); 5136169689Skan delete_points_to_sets (); 5137171825Skan#endif 5138169689Skan return 0; 5139169689Skan} 5140169689Skan 5141169689Skanstruct tree_opt_pass pass_ipa_pta = 5142169689Skan{ 5143169689Skan "pta", /* name */ 5144169689Skan gate_ipa_pta, /* gate */ 5145169689Skan ipa_pta_execute, /* execute */ 5146169689Skan NULL, /* sub */ 5147169689Skan NULL, /* next */ 5148169689Skan 0, /* static_pass_number */ 5149169689Skan TV_IPA_PTA, /* tv_id */ 5150169689Skan 0, /* properties_required */ 5151169689Skan 0, /* properties_provided */ 5152169689Skan 0, /* properties_destroyed */ 5153169689Skan 0, /* todo_flags_start */ 5154169689Skan 0, /* todo_flags_finish */ 5155169689Skan 0 /* letter */ 5156169689Skan}; 5157169689Skan 5158169689Skan/* Initialize the heapvar for statement mapping. */ 5159169689Skanvoid 5160169689Skaninit_alias_heapvars (void) 5161169689Skan{ 5162171825Skan if (!heapvar_for_stmt) 5163171825Skan heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq, 5164171825Skan NULL); 5165169689Skan nonlocal_all = NULL_TREE; 5166169689Skan} 5167169689Skan 5168169689Skanvoid 5169169689Skandelete_alias_heapvars (void) 5170169689Skan{ 5171169689Skan nonlocal_all = NULL_TREE; 5172169689Skan htab_delete (heapvar_for_stmt); 5173171825Skan heapvar_for_stmt = NULL; 5174169689Skan} 5175169689Skan 5176169689Skan#include "gt-tree-ssa-structalias.h" 5177