| /* Tree based points-to analysis |
| Copyright (C) 2005-2022 Free Software Foundation, Inc. |
| Contributed by Daniel Berlin <dberlin@dberlin.org> |
| |
| This file is part of GCC. |
| |
| GCC is free software; you can redistribute it and/or modify |
| under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 3 of the License, or |
| (at your option) any later version. |
| |
| GCC is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| GNU General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GCC; see the file COPYING3. If not see |
| <http://www.gnu.org/licenses/>. */ |
| |
| #include "config.h" |
| #include "system.h" |
| #include "coretypes.h" |
| #include "backend.h" |
| #include "rtl.h" |
| #include "tree.h" |
| #include "gimple.h" |
| #include "alloc-pool.h" |
| #include "tree-pass.h" |
| #include "ssa.h" |
| #include "cgraph.h" |
| #include "tree-pretty-print.h" |
| #include "diagnostic-core.h" |
| #include "fold-const.h" |
| #include "stor-layout.h" |
| #include "stmt.h" |
| #include "gimple-iterator.h" |
| #include "tree-into-ssa.h" |
| #include "tree-dfa.h" |
| #include "gimple-walk.h" |
| #include "varasm.h" |
| #include "stringpool.h" |
| #include "attribs.h" |
| #include "tree-ssa.h" |
| #include "tree-cfg.h" |
| #include "gimple-range.h" |
| #include "ipa-modref-tree.h" |
| #include "ipa-modref.h" |
| #include "attr-fnspec.h" |
| |
| /* The idea behind this analyzer is to generate set constraints from the |
| program, then solve the resulting constraints in order to generate the |
| points-to sets. |
| |
| Set constraints are a way of modeling program analysis problems that |
| involve sets. They consist of an inclusion constraint language, |
| describing the variables (each variable is a set) and operations that |
| are involved on the variables, and a set of rules that derive facts |
| from these operations. To solve a system of set constraints, you derive |
| all possible facts under the rules, which gives you the correct sets |
| as a consequence. |
| |
| See "Efficient Field-sensitive pointer analysis for C" by "David |
| J. Pearce and Paul H. J. Kelly and Chris Hankin", at |
| http://citeseer.ist.psu.edu/pearce04efficient.html |
| |
| Also see "Ultra-fast Aliasing Analysis using CLA: A Million Lines |
| of C Code in a Second" by "Nevin Heintze and Olivier Tardieu" at |
| http://citeseer.ist.psu.edu/heintze01ultrafast.html |
| |
| There are three types of real constraint expressions, DEREF, |
| ADDRESSOF, and SCALAR. Each constraint expression consists |
| of a constraint type, a variable, and an offset. |
| |
| SCALAR is a constraint expression type used to represent x, whether |
| it appears on the LHS or the RHS of a statement. |
| DEREF is a constraint expression type used to represent *x, whether |
| it appears on the LHS or the RHS of a statement. |
| ADDRESSOF is a constraint expression used to represent &x, whether |
| it appears on the LHS or the RHS of a statement. |
| |
| Each pointer variable in the program is assigned an integer id, and |
| each field of a structure variable is assigned an integer id as well. |
| |
| Structure variables are linked to their list of fields through a "next |
| field" in each variable that points to the next field in offset |
| order. |
| Each variable for a structure field has |
| |
| 1. "size", that tells the size in bits of that field. |
| 2. "fullsize", that tells the size in bits of the entire structure. |
| 3. "offset", that tells the offset in bits from the beginning of the |
| structure to this field. |
| |
| Thus, |
| struct f |
| { |
| int a; |
| int b; |
| } foo; |
| int *bar; |
| |
| looks like |
| |
| foo.a -> id 1, size 32, offset 0, fullsize 64, next foo.b |
| foo.b -> id 2, size 32, offset 32, fullsize 64, next NULL |
| bar -> id 3, size 32, offset 0, fullsize 32, next NULL |
| |
| |
| In order to solve the system of set constraints, the following is |
| done: |
| |
| 1. Each constraint variable x has a solution set associated with it, |
| Sol(x). |
| |
| 2. Constraints are separated into direct, copy, and complex. |
| Direct constraints are ADDRESSOF constraints that require no extra |
| processing, such as P = &Q |
| Copy constraints are those of the form P = Q. |
| Complex constraints are all the constraints involving dereferences |
| and offsets (including offsetted copies). |
| |
| 3. All direct constraints of the form P = &Q are processed, such |
| that Q is added to Sol(P) |
| |
| 4. All complex constraints for a given constraint variable are stored in a |
| linked list attached to that variable's node. |
| |
| 5. A directed graph is built out of the copy constraints. Each |
| constraint variable is a node in the graph, and an edge from |
| Q to P is added for each copy constraint of the form P = Q |
| |
| 6. The graph is then walked, and solution sets are |
| propagated along the copy edges, such that an edge from Q to P |
| causes Sol(P) <- Sol(P) union Sol(Q). |
| |
| 7. As we visit each node, all complex constraints associated with |
| that node are processed by adding appropriate copy edges to the graph, or the |
| appropriate variables to the solution set. |
| |
| 8. The process of walking the graph is iterated until no solution |
| sets change. |
| |
| Prior to walking the graph in steps 6 and 7, We perform static |
| cycle elimination on the constraint graph, as well |
| as off-line variable substitution. |
| |
| TODO: Adding offsets to pointer-to-structures can be handled (IE not punted |
| on and turned into anything), but isn't. You can just see what offset |
| inside the pointed-to struct it's going to access. |
| |
| TODO: Constant bounded arrays can be handled as if they were structs of the |
| same number of elements. |
| |
| TODO: Modeling heap and incoming pointers becomes much better if we |
| add fields to them as we discover them, which we could do. |
| |
| TODO: We could handle unions, but to be honest, it's probably not |
| worth the pain or slowdown. */ |
| |
| /* IPA-PTA optimizations possible. |
| |
| When the indirect function called is ANYTHING we can add disambiguation |
| based on the function signatures (or simply the parameter count which |
| is the varinfo size). We also do not need to consider functions that |
| do not have their address taken. |
| |
| The is_global_var bit which marks escape points is overly conservative |
| in IPA mode. Split it to is_escape_point and is_global_var - only |
| externally visible globals are escape points in IPA mode. |
| There is now is_ipa_escape_point but this is only used in a few |
| selected places. |
| |
| The way we introduce DECL_PT_UID to avoid fixing up all points-to |
| sets in the translation unit when we copy a DECL during inlining |
| pessimizes precision. The advantage is that the DECL_PT_UID keeps |
| compile-time and memory usage overhead low - the points-to sets |
| do not grow or get unshared as they would during a fixup phase. |
| An alternative solution is to delay IPA PTA until after all |
| inlining transformations have been applied. |
| |
| The way we propagate clobber/use information isn't optimized. |
| It should use a new complex constraint that properly filters |
| out local variables of the callee (though that would make |
| the sets invalid after inlining). OTOH we might as well |
| admit defeat to WHOPR and simply do all the clobber/use analysis |
| and propagation after PTA finished but before we threw away |
| points-to information for memory variables. WHOPR and PTA |
| do not play along well anyway - the whole constraint solving |
| would need to be done in WPA phase and it will be very interesting |
| to apply the results to local SSA names during LTRANS phase. |
| |
| We probably should compute a per-function unit-ESCAPE solution |
| propagating it simply like the clobber / uses solutions. The |
| solution can go alongside the non-IPA escaped solution and be |
| used to query which vars escape the unit through a function. |
| This is also required to make the escaped-HEAP trick work in IPA mode. |
| |
| We never put function decls in points-to sets so we do not |
| keep the set of called functions for indirect calls. |
| |
| And probably more. */ |
| |
| static bool use_field_sensitive = true; |
| static int in_ipa_mode = 0; |
| |
| /* Used for predecessor bitmaps. */ |
| static bitmap_obstack predbitmap_obstack; |
| |
| /* Used for points-to sets. */ |
| static bitmap_obstack pta_obstack; |
| |
| /* Used for oldsolution members of variables. */ |
| static bitmap_obstack oldpta_obstack; |
| |
| /* Used for per-solver-iteration bitmaps. */ |
| static bitmap_obstack iteration_obstack; |
| |
| static unsigned int create_variable_info_for (tree, const char *, bool); |
| typedef struct constraint_graph *constraint_graph_t; |
| static void unify_nodes (constraint_graph_t, unsigned int, unsigned int, bool); |
| |
| struct constraint; |
| typedef struct constraint *constraint_t; |
| |
| |
| #define EXECUTE_IF_IN_NONNULL_BITMAP(a, b, c, d) \ |
| if (a) \ |
| EXECUTE_IF_SET_IN_BITMAP (a, b, c, d) |
| |
| static struct constraint_stats |
| { |
| unsigned int total_vars; |
| unsigned int nonpointer_vars; |
| unsigned int unified_vars_static; |
| unsigned int unified_vars_dynamic; |
| unsigned int iterations; |
| unsigned int num_edges; |
| unsigned int num_implicit_edges; |
| unsigned int points_to_sets_created; |
| } stats; |
| |
| struct variable_info |
| { |
| /* ID of this variable */ |
| unsigned int id; |
| |
| /* True if this is a variable created by the constraint analysis, such as |
| heap variables and constraints we had to break up. */ |
| unsigned int is_artificial_var : 1; |
| |
| /* True if this is a special variable whose solution set should not be |
| changed. */ |
| unsigned int is_special_var : 1; |
| |
| /* True for variables whose size is not known or variable. */ |
| unsigned int is_unknown_size_var : 1; |
| |
| /* True for (sub-)fields that represent a whole variable. */ |
| unsigned int is_full_var : 1; |
| |
| /* True if this is a heap variable. */ |
| unsigned int is_heap_var : 1; |
| |
| /* True if this is a register variable. */ |
| unsigned int is_reg_var : 1; |
| |
| /* True if this field may contain pointers. */ |
| unsigned int may_have_pointers : 1; |
| |
| /* True if this field has only restrict qualified pointers. */ |
| unsigned int only_restrict_pointers : 1; |
| |
| /* True if this represents a heap var created for a restrict qualified |
| pointer. */ |
| unsigned int is_restrict_var : 1; |
| |
| /* True if this represents a global variable. */ |
| unsigned int is_global_var : 1; |
| |
| /* True if this represents a module escape point for IPA analysis. */ |
| unsigned int is_ipa_escape_point : 1; |
| |
| /* True if this represents a IPA function info. */ |
| unsigned int is_fn_info : 1; |
| |
| /* True if this appears as RHS in a ADDRESSOF constraint. */ |
| unsigned int address_taken : 1; |
| |
| /* ??? Store somewhere better. */ |
| unsigned short ruid; |
| |
| /* The ID of the variable for the next field in this structure |
| or zero for the last field in this structure. */ |
| unsigned next; |
| |
| /* The ID of the variable for the first field in this structure. */ |
| unsigned head; |
| |
| /* Offset of this variable, in bits, from the base variable */ |
| unsigned HOST_WIDE_INT offset; |
| |
| /* Size of the variable, in bits. */ |
| unsigned HOST_WIDE_INT size; |
| |
| /* Full size of the base variable, in bits. */ |
| unsigned HOST_WIDE_INT fullsize; |
| |
| /* In IPA mode the shadow UID in case the variable needs to be duplicated in |
| the final points-to solution because it reaches its containing |
| function recursively. Zero if none is needed. */ |
| unsigned int shadow_var_uid; |
| |
| /* Name of this variable */ |
| const char *name; |
| |
| /* Tree that this variable is associated with. */ |
| tree decl; |
| |
| /* Points-to set for this variable. */ |
| bitmap solution; |
| |
| /* Old points-to set for this variable. */ |
| bitmap oldsolution; |
| }; |
| typedef struct variable_info *varinfo_t; |
| |
| static varinfo_t first_vi_for_offset (varinfo_t, unsigned HOST_WIDE_INT); |
| static varinfo_t first_or_preceding_vi_for_offset (varinfo_t, |
| unsigned HOST_WIDE_INT); |
| static varinfo_t lookup_vi_for_tree (tree); |
| static inline bool type_can_have_subvars (const_tree); |
| static void make_param_constraints (varinfo_t); |
| |
| /* Pool of variable info structures. */ |
| static object_allocator<variable_info> variable_info_pool |
| ("Variable info pool"); |
| |
| /* Map varinfo to final pt_solution. */ |
| static hash_map<varinfo_t, pt_solution *> *final_solutions; |
| struct obstack final_solutions_obstack; |
| |
| /* Table of variable info structures for constraint variables. |
| Indexed directly by variable info id. */ |
| static vec<varinfo_t> varmap; |
| |
| /* Return the varmap element N */ |
| |
| static inline varinfo_t |
| get_varinfo (unsigned int n) |
| { |
| return varmap[n]; |
| } |
| |
| /* Return the next variable in the list of sub-variables of VI |
| or NULL if VI is the last sub-variable. */ |
| |
| static inline varinfo_t |
| vi_next (varinfo_t vi) |
| { |
| return get_varinfo (vi->next); |
| } |
| |
| /* Static IDs for the special variables. Variable ID zero is unused |
| and used as terminator for the sub-variable chain. */ |
| enum { nothing_id = 1, anything_id = 2, string_id = 3, |
| escaped_id = 4, nonlocal_id = 5, |
| storedanything_id = 6, integer_id = 7 }; |
| |
| /* Return a new variable info structure consisting for a variable |
| named NAME, and using constraint graph node NODE. Append it |
| to the vector of variable info structures. */ |
| |
| static varinfo_t |
| new_var_info (tree t, const char *name, bool add_id) |
| { |
| unsigned index = varmap.length (); |
| varinfo_t ret = variable_info_pool.allocate (); |
| |
| if (dump_file && add_id) |
| { |
| char *tempname = xasprintf ("%s(%d)", name, index); |
| name = ggc_strdup (tempname); |
| free (tempname); |
| } |
| |
| ret->id = index; |
| ret->name = name; |
| ret->decl = t; |
| /* Vars without decl are artificial and do not have sub-variables. */ |
| ret->is_artificial_var = (t == NULL_TREE); |
| ret->is_special_var = false; |
| ret->is_unknown_size_var = false; |
| ret->is_full_var = (t == NULL_TREE); |
| ret->is_heap_var = false; |
| ret->may_have_pointers = true; |
| ret->only_restrict_pointers = false; |
| ret->is_restrict_var = false; |
| ret->ruid = 0; |
| ret->is_global_var = (t == NULL_TREE); |
| ret->is_ipa_escape_point = false; |
| ret->is_fn_info = false; |
| ret->address_taken = false; |
| if (t && DECL_P (t)) |
| ret->is_global_var = (is_global_var (t) |
| /* We have to treat even local register variables |
| as escape points. */ |
| || (VAR_P (t) && DECL_HARD_REGISTER (t))); |
| ret->is_reg_var = (t && TREE_CODE (t) == SSA_NAME); |
| ret->solution = BITMAP_ALLOC (&pta_obstack); |
| ret->oldsolution = NULL; |
| ret->next = 0; |
| ret->shadow_var_uid = 0; |
| ret->head = ret->id; |
| |
| stats.total_vars++; |
| |
| varmap.safe_push (ret); |
| |
| return ret; |
| } |
| |
| /* A map mapping call statements to per-stmt variables for uses |
| and clobbers specific to the call. */ |
| static hash_map<gimple *, varinfo_t> *call_stmt_vars; |
| |
| /* Lookup or create the variable for the call statement CALL. */ |
| |
| static varinfo_t |
| get_call_vi (gcall *call) |
| { |
| varinfo_t vi, vi2; |
| |
| bool existed; |
| varinfo_t *slot_p = &call_stmt_vars->get_or_insert (call, &existed); |
| if (existed) |
| return *slot_p; |
| |
| vi = new_var_info (NULL_TREE, "CALLUSED", true); |
| vi->offset = 0; |
| vi->size = 1; |
| vi->fullsize = 2; |
| vi->is_full_var = true; |
| vi->is_reg_var = true; |
| |
| vi2 = new_var_info (NULL_TREE, "CALLCLOBBERED", true); |
| vi2->offset = 1; |
| vi2->size = 1; |
| vi2->fullsize = 2; |
| vi2->is_full_var = true; |
| vi2->is_reg_var = true; |
| |
| vi->next = vi2->id; |
| |
| *slot_p = vi; |
| return vi; |
| } |
| |
| /* Lookup the variable for the call statement CALL representing |
| the uses. Returns NULL if there is nothing special about this call. */ |
| |
| static varinfo_t |
| lookup_call_use_vi (gcall *call) |
| { |
| varinfo_t *slot_p = call_stmt_vars->get (call); |
| if (slot_p) |
| return *slot_p; |
| |
| return NULL; |
| } |
| |
| /* Lookup the variable for the call statement CALL representing |
| the clobbers. Returns NULL if there is nothing special about this call. */ |
| |
| static varinfo_t |
| lookup_call_clobber_vi (gcall *call) |
| { |
| varinfo_t uses = lookup_call_use_vi (call); |
| if (!uses) |
| return NULL; |
| |
| return vi_next (uses); |
| } |
| |
| /* Lookup or create the variable for the call statement CALL representing |
| the uses. */ |
| |
| static varinfo_t |
| get_call_use_vi (gcall *call) |
| { |
| return get_call_vi (call); |
| } |
| |
| /* Lookup or create the variable for the call statement CALL representing |
| the clobbers. */ |
| |
| static varinfo_t ATTRIBUTE_UNUSED |
| get_call_clobber_vi (gcall *call) |
| { |
| return vi_next (get_call_vi (call)); |
| } |
| |
| |
| enum constraint_expr_type {SCALAR, DEREF, ADDRESSOF}; |
| |
| /* An expression that appears in a constraint. */ |
| |
| struct constraint_expr |
| { |
| /* Constraint type. */ |
| constraint_expr_type type; |
| |
| /* Variable we are referring to in the constraint. */ |
| unsigned int var; |
| |
| /* Offset, in bits, of this constraint from the beginning of |
| variables it ends up referring to. |
| |
| IOW, in a deref constraint, we would deref, get the result set, |
| then add OFFSET to each member. */ |
| HOST_WIDE_INT offset; |
| }; |
| |
| /* Use 0x8000... as special unknown offset. */ |
| #define UNKNOWN_OFFSET HOST_WIDE_INT_MIN |
| |
| typedef struct constraint_expr ce_s; |
| static void get_constraint_for_1 (tree, vec<ce_s> *, bool, bool); |
| static void get_constraint_for (tree, vec<ce_s> *); |
| static void get_constraint_for_rhs (tree, vec<ce_s> *); |
| static void do_deref (vec<ce_s> *); |
| |
| /* Our set constraints are made up of two constraint expressions, one |
| LHS, and one RHS. |
| |
| As described in the introduction, our set constraints each represent an |
| operation between set valued variables. |
| */ |
| struct constraint |
| { |
| struct constraint_expr lhs; |
| struct constraint_expr rhs; |
| }; |
| |
| /* List of constraints that we use to build the constraint graph from. */ |
| |
| static vec<constraint_t> constraints; |
| static object_allocator<constraint> constraint_pool ("Constraint pool"); |
| |
| /* The constraint graph is represented as an array of bitmaps |
| containing successor nodes. */ |
| |
| struct constraint_graph |
| { |
| /* Size of this graph, which may be different than the number of |
| nodes in the variable map. */ |
| unsigned int size; |
| |
| /* Explicit successors of each node. */ |
| bitmap *succs; |
| |
| /* Implicit predecessors of each node (Used for variable |
| substitution). */ |
| bitmap *implicit_preds; |
| |
| /* Explicit predecessors of each node (Used for variable substitution). */ |
| bitmap *preds; |
| |
| /* Indirect cycle representatives, or -1 if the node has no indirect |
| cycles. */ |
| int *indirect_cycles; |
| |
| /* Representative node for a node. rep[a] == a unless the node has |
| been unified. */ |
| unsigned int *rep; |
| |
| /* Equivalence class representative for a label. This is used for |
| variable substitution. */ |
| int *eq_rep; |
| |
| /* Pointer equivalence label for a node. All nodes with the same |
| pointer equivalence label can be unified together at some point |
| (either during constraint optimization or after the constraint |
| graph is built). */ |
| unsigned int *pe; |
| |
| /* Pointer equivalence representative for a label. This is used to |
| handle nodes that are pointer equivalent but not location |
| equivalent. We can unite these once the addressof constraints |
| are transformed into initial points-to sets. */ |
| int *pe_rep; |
| |
| /* Pointer equivalence label for each node, used during variable |
| substitution. */ |
| unsigned int *pointer_label; |
| |
| /* Location equivalence label for each node, used during location |
| equivalence finding. */ |
| unsigned int *loc_label; |
| |
| /* Pointed-by set for each node, used during location equivalence |
| finding. This is pointed-by rather than pointed-to, because it |
| is constructed using the predecessor graph. */ |
| bitmap *pointed_by; |
| |
| /* Points to sets for pointer equivalence. This is *not* the actual |
| points-to sets for nodes. */ |
| bitmap *points_to; |
| |
| /* Bitmap of nodes where the bit is set if the node is a direct |
| node. Used for variable substitution. */ |
| sbitmap direct_nodes; |
| |
| /* Bitmap of nodes where the bit is set if the node is address |
| taken. Used for variable substitution. */ |
| bitmap address_taken; |
| |
| /* Vector of complex constraints for each graph node. Complex |
| constraints are those involving dereferences or offsets that are |
| not 0. */ |
| vec<constraint_t> *complex; |
| }; |
| |
| static constraint_graph_t graph; |
| |
| /* During variable substitution and the offline version of indirect |
| cycle finding, we create nodes to represent dereferences and |
| address taken constraints. These represent where these start and |
| end. */ |
| #define FIRST_REF_NODE (varmap).length () |
| #define LAST_REF_NODE (FIRST_REF_NODE + (FIRST_REF_NODE - 1)) |
| |
| /* Return the representative node for NODE, if NODE has been unioned |
| with another NODE. |
| This function performs path compression along the way to finding |
| the representative. */ |
| |
| static unsigned int |
| find (unsigned int node) |
| { |
| gcc_checking_assert (node < graph->size); |
| if (graph->rep[node] != node) |
| return graph->rep[node] = find (graph->rep[node]); |
| return node; |
| } |
| |
| /* Union the TO and FROM nodes to the TO nodes. |
| Note that at some point in the future, we may want to do |
| union-by-rank, in which case we are going to have to return the |
| node we unified to. */ |
| |
| static bool |
| unite (unsigned int to, unsigned int from) |
| { |
| gcc_checking_assert (to < graph->size && from < graph->size); |
| if (to != from && graph->rep[from] != to) |
| { |
| graph->rep[from] = to; |
| return true; |
| } |
| return false; |
| } |
| |
| /* Create a new constraint consisting of LHS and RHS expressions. */ |
| |
| static constraint_t |
| new_constraint (const struct constraint_expr lhs, |
| const struct constraint_expr rhs) |
| { |
| constraint_t ret = constraint_pool.allocate (); |
| ret->lhs = lhs; |
| ret->rhs = rhs; |
| return ret; |
| } |
| |
| /* Print out constraint C to FILE. */ |
| |
| static void |
| dump_constraint (FILE *file, constraint_t c) |
| { |
| if (c->lhs.type == ADDRESSOF) |
| fprintf (file, "&"); |
| else if (c->lhs.type == DEREF) |
| fprintf (file, "*"); |
| if (dump_file) |
| fprintf (file, "%s", get_varinfo (c->lhs.var)->name); |
| else |
| fprintf (file, "V%d", c->lhs.var); |
| if (c->lhs.offset == UNKNOWN_OFFSET) |
| fprintf (file, " + UNKNOWN"); |
| else if (c->lhs.offset != 0) |
| fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->lhs.offset); |
| fprintf (file, " = "); |
| if (c->rhs.type == ADDRESSOF) |
| fprintf (file, "&"); |
| else if (c->rhs.type == DEREF) |
| fprintf (file, "*"); |
| if (dump_file) |
| fprintf (file, "%s", get_varinfo (c->rhs.var)->name); |
| else |
| fprintf (file, "V%d", c->rhs.var); |
| if (c->rhs.offset == UNKNOWN_OFFSET) |
| fprintf (file, " + UNKNOWN"); |
| else if (c->rhs.offset != 0) |
| fprintf (file, " + " HOST_WIDE_INT_PRINT_DEC, c->rhs.offset); |
| } |
| |
| |
| void debug_constraint (constraint_t); |
| void debug_constraints (void); |
| void debug_constraint_graph (void); |
| void debug_solution_for_var (unsigned int); |
| void debug_sa_points_to_info (void); |
| void debug_varinfo (varinfo_t); |
| void debug_varmap (void); |
| |
| /* Print out constraint C to stderr. */ |
| |
| DEBUG_FUNCTION void |
| debug_constraint (constraint_t c) |
| { |
| dump_constraint (stderr, c); |
| fprintf (stderr, "\n"); |
| } |
| |
| /* Print out all constraints to FILE */ |
| |
| static void |
| dump_constraints (FILE *file, int from) |
| { |
| int i; |
| constraint_t c; |
| for (i = from; constraints.iterate (i, &c); i++) |
| if (c) |
| { |
| dump_constraint (file, c); |
| fprintf (file, "\n"); |
| } |
| } |
| |
| /* Print out all constraints to stderr. */ |
| |
| DEBUG_FUNCTION void |
| debug_constraints (void) |
| { |
| dump_constraints (stderr, 0); |
| } |
| |
| /* Print the constraint graph in dot format. */ |
| |
| static void |
| dump_constraint_graph (FILE *file) |
| { |
| unsigned int i; |
| |
| /* Only print the graph if it has already been initialized: */ |
| if (!graph) |
| return; |
| |
| /* Prints the header of the dot file: */ |
| fprintf (file, "strict digraph {\n"); |
| fprintf (file, " node [\n shape = box\n ]\n"); |
| fprintf (file, " edge [\n fontsize = \"12\"\n ]\n"); |
| fprintf (file, "\n // List of nodes and complex constraints in " |
| "the constraint graph:\n"); |
| |
| /* The next lines print the nodes in the graph together with the |
| complex constraints attached to them. */ |
| for (i = 1; i < graph->size; i++) |
| { |
| if (i == FIRST_REF_NODE) |
| continue; |
| if (find (i) != i) |
| continue; |
| if (i < FIRST_REF_NODE) |
| fprintf (file, "\"%s\"", get_varinfo (i)->name); |
| else |
| fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name); |
| if (graph->complex[i].exists ()) |
| { |
| unsigned j; |
| constraint_t c; |
| fprintf (file, " [label=\"\\N\\n"); |
| for (j = 0; graph->complex[i].iterate (j, &c); ++j) |
| { |
| dump_constraint (file, c); |
| fprintf (file, "\\l"); |
| } |
| fprintf (file, "\"]"); |
| } |
| fprintf (file, ";\n"); |
| } |
| |
| /* Go over the edges. */ |
| fprintf (file, "\n // Edges in the constraint graph:\n"); |
| for (i = 1; i < graph->size; i++) |
| { |
| unsigned j; |
| bitmap_iterator bi; |
| if (find (i) != i) |
| continue; |
| EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi) |
| { |
| unsigned to = find (j); |
| if (i == to) |
| continue; |
| if (i < FIRST_REF_NODE) |
| fprintf (file, "\"%s\"", get_varinfo (i)->name); |
| else |
| fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name); |
| fprintf (file, " -> "); |
| if (to < FIRST_REF_NODE) |
| fprintf (file, "\"%s\"", get_varinfo (to)->name); |
| else |
| fprintf (file, "\"*%s\"", get_varinfo (to - FIRST_REF_NODE)->name); |
| fprintf (file, ";\n"); |
| } |
| } |
| |
| /* Prints the tail of the dot file. */ |
| fprintf (file, "}\n"); |
| } |
| |
| /* Print out the constraint graph to stderr. */ |
| |
| DEBUG_FUNCTION void |
| debug_constraint_graph (void) |
| { |
| dump_constraint_graph (stderr); |
| } |
| |
| /* SOLVER FUNCTIONS |
| |
| The solver is a simple worklist solver, that works on the following |
| algorithm: |
| |
| sbitmap changed_nodes = all zeroes; |
| changed_count = 0; |
| For each node that is not already collapsed: |
| changed_count++; |
| set bit in changed nodes |
| |
| while (changed_count > 0) |
| { |
| compute topological ordering for constraint graph |
| |
| find and collapse cycles in the constraint graph (updating |
| changed if necessary) |
| |
| for each node (n) in the graph in topological order: |
| changed_count--; |
| |
| Process each complex constraint associated with the node, |
| updating changed if necessary. |
| |
| For each outgoing edge from n, propagate the solution from n to |
| the destination of the edge, updating changed as necessary. |
| |
| } */ |
| |
| /* Return true if two constraint expressions A and B are equal. */ |
| |
| static bool |
| constraint_expr_equal (struct constraint_expr a, struct constraint_expr b) |
| { |
| return a.type == b.type && a.var == b.var && a.offset == b.offset; |
| } |
| |
| /* Return true if constraint expression A is less than constraint expression |
| B. This is just arbitrary, but consistent, in order to give them an |
| ordering. */ |
| |
| static bool |
| constraint_expr_less (struct constraint_expr a, struct constraint_expr b) |
| { |
| if (a.type == b.type) |
| { |
| if (a.var == b.var) |
| return a.offset < b.offset; |
| else |
| return a.var < b.var; |
| } |
| else |
| return a.type < b.type; |
| } |
| |
| /* Return true if constraint A is less than constraint B. This is just |
| arbitrary, but consistent, in order to give them an ordering. */ |
| |
| static bool |
| constraint_less (const constraint_t &a, const constraint_t &b) |
| { |
| if (constraint_expr_less (a->lhs, b->lhs)) |
| return true; |
| else if (constraint_expr_less (b->lhs, a->lhs)) |
| return false; |
| else |
| return constraint_expr_less (a->rhs, b->rhs); |
| } |
| |
| /* Return true if two constraints A and B are equal. */ |
| |
| static bool |
| constraint_equal (struct constraint a, struct constraint b) |
| { |
| return constraint_expr_equal (a.lhs, b.lhs) |
| && constraint_expr_equal (a.rhs, b.rhs); |
| } |
| |
| |
| /* Find a constraint LOOKFOR in the sorted constraint vector VEC */ |
| |
| static constraint_t |
| constraint_vec_find (vec<constraint_t> vec, |
| struct constraint lookfor) |
| { |
| unsigned int place; |
| constraint_t found; |
| |
| if (!vec.exists ()) |
| return NULL; |
| |
| place = vec.lower_bound (&lookfor, constraint_less); |
| if (place >= vec.length ()) |
| return NULL; |
| found = vec[place]; |
| if (!constraint_equal (*found, lookfor)) |
| return NULL; |
| return found; |
| } |
| |
| /* Union two constraint vectors, TO and FROM. Put the result in TO. |
| Returns true of TO set is changed. */ |
| |
| static bool |
| constraint_set_union (vec<constraint_t> *to, |
| vec<constraint_t> *from) |
| { |
| int i; |
| constraint_t c; |
| bool any_change = false; |
| |
| FOR_EACH_VEC_ELT (*from, i, c) |
| { |
| if (constraint_vec_find (*to, *c) == NULL) |
| { |
| unsigned int place = to->lower_bound (c, constraint_less); |
| to->safe_insert (place, c); |
| any_change = true; |
| } |
| } |
| return any_change; |
| } |
| |
| /* Expands the solution in SET to all sub-fields of variables included. */ |
| |
| static bitmap |
| solution_set_expand (bitmap set, bitmap *expanded) |
| { |
| bitmap_iterator bi; |
| unsigned j; |
| |
| if (*expanded) |
| return *expanded; |
| |
| *expanded = BITMAP_ALLOC (&iteration_obstack); |
| |
| /* In a first pass expand to the head of the variables we need to |
| add all sub-fields off. This avoids quadratic behavior. */ |
| EXECUTE_IF_SET_IN_BITMAP (set, 0, j, bi) |
| { |
| varinfo_t v = get_varinfo (j); |
| if (v->is_artificial_var |
| || v->is_full_var) |
| continue; |
| bitmap_set_bit (*expanded, v->head); |
| } |
| |
| /* In the second pass now expand all head variables with subfields. */ |
| EXECUTE_IF_SET_IN_BITMAP (*expanded, 0, j, bi) |
| { |
| varinfo_t v = get_varinfo (j); |
| if (v->head != j) |
| continue; |
| for (v = vi_next (v); v != NULL; v = vi_next (v)) |
| bitmap_set_bit (*expanded, v->id); |
| } |
| |
| /* And finally set the rest of the bits from SET. */ |
| bitmap_ior_into (*expanded, set); |
| |
| return *expanded; |
| } |
| |
| /* Union solution sets TO and DELTA, and add INC to each member of DELTA in the |
| process. */ |
| |
| static bool |
| set_union_with_increment (bitmap to, bitmap delta, HOST_WIDE_INT inc, |
| bitmap *expanded_delta) |
| { |
| bool changed = false; |
| bitmap_iterator bi; |
| unsigned int i; |
| |
| /* If the solution of DELTA contains anything it is good enough to transfer |
| this to TO. */ |
| if (bitmap_bit_p (delta, anything_id)) |
| return bitmap_set_bit (to, anything_id); |
| |
| /* If the offset is unknown we have to expand the solution to |
| all subfields. */ |
| if (inc == UNKNOWN_OFFSET) |
| { |
| delta = solution_set_expand (delta, expanded_delta); |
| changed |= bitmap_ior_into (to, delta); |
| return changed; |
| } |
| |
| /* For non-zero offset union the offsetted solution into the destination. */ |
| EXECUTE_IF_SET_IN_BITMAP (delta, 0, i, bi) |
| { |
| varinfo_t vi = get_varinfo (i); |
| |
| /* If this is a variable with just one field just set its bit |
| in the result. */ |
| if (vi->is_artificial_var |
| || vi->is_unknown_size_var |
| || vi->is_full_var) |
| changed |= bitmap_set_bit (to, i); |
| else |
| { |
| HOST_WIDE_INT fieldoffset = vi->offset + inc; |
| unsigned HOST_WIDE_INT size = vi->size; |
| |
| /* If the offset makes the pointer point to before the |
| variable use offset zero for the field lookup. */ |
| if (fieldoffset < 0) |
| vi = get_varinfo (vi->head); |
| else |
| vi = first_or_preceding_vi_for_offset (vi, fieldoffset); |
| |
| do |
| { |
| changed |= bitmap_set_bit (to, vi->id); |
| if (vi->is_full_var |
| || vi->next == 0) |
| break; |
| |
| /* We have to include all fields that overlap the current field |
| shifted by inc. */ |
| vi = vi_next (vi); |
| } |
| while (vi->offset < fieldoffset + size); |
| } |
| } |
| |
| return changed; |
| } |
| |
| /* Insert constraint C into the list of complex constraints for graph |
| node VAR. */ |
| |
| static void |
| insert_into_complex (constraint_graph_t graph, |
| unsigned int var, constraint_t c) |
| { |
| vec<constraint_t> complex = graph->complex[var]; |
| unsigned int place = complex.lower_bound (c, constraint_less); |
| |
| /* Only insert constraints that do not already exist. */ |
| if (place >= complex.length () |
| || !constraint_equal (*c, *complex[place])) |
| graph->complex[var].safe_insert (place, c); |
| } |
| |
| |
| /* Condense two variable nodes into a single variable node, by moving |
| all associated info from FROM to TO. Returns true if TO node's |
| constraint set changes after the merge. */ |
| |
| static bool |
| merge_node_constraints (constraint_graph_t graph, unsigned int to, |
| unsigned int from) |
| { |
| unsigned int i; |
| constraint_t c; |
| bool any_change = false; |
| |
| gcc_checking_assert (find (from) == to); |
| |
| /* Move all complex constraints from src node into to node */ |
| FOR_EACH_VEC_ELT (graph->complex[from], i, c) |
| { |
| /* In complex constraints for node FROM, we may have either |
| a = *FROM, and *FROM = a, or an offseted constraint which are |
| always added to the rhs node's constraints. */ |
| |
| if (c->rhs.type == DEREF) |
| c->rhs.var = to; |
| else if (c->lhs.type == DEREF) |
| c->lhs.var = to; |
| else |
| c->rhs.var = to; |
| |
| } |
| any_change = constraint_set_union (&graph->complex[to], |
| &graph->complex[from]); |
| graph->complex[from].release (); |
| return any_change; |
| } |
| |
| |
| /* Remove edges involving NODE from GRAPH. */ |
| |
| static void |
| clear_edges_for_node (constraint_graph_t graph, unsigned int node) |
| { |
| if (graph->succs[node]) |
| BITMAP_FREE (graph->succs[node]); |
| } |
| |
| /* Merge GRAPH nodes FROM and TO into node TO. */ |
| |
| static void |
| merge_graph_nodes (constraint_graph_t graph, unsigned int to, |
| unsigned int from) |
| { |
| if (graph->indirect_cycles[from] != -1) |
| { |
| /* If we have indirect cycles with the from node, and we have |
| none on the to node, the to node has indirect cycles from the |
| from node now that they are unified. |
| If indirect cycles exist on both, unify the nodes that they |
| are in a cycle with, since we know they are in a cycle with |
| each other. */ |
| if (graph->indirect_cycles[to] == -1) |
| graph->indirect_cycles[to] = graph->indirect_cycles[from]; |
| } |
| |
| /* Merge all the successor edges. */ |
| if (graph->succs[from]) |
| { |
| if (!graph->succs[to]) |
| graph->succs[to] = BITMAP_ALLOC (&pta_obstack); |
| bitmap_ior_into (graph->succs[to], |
| graph->succs[from]); |
| } |
| |
| clear_edges_for_node (graph, from); |
| } |
| |
| |
| /* Add an indirect graph edge to GRAPH, going from TO to FROM if |
| it doesn't exist in the graph already. */ |
| |
| static void |
| add_implicit_graph_edge (constraint_graph_t graph, unsigned int to, |
| unsigned int from) |
| { |
| if (to == from) |
| return; |
| |
| if (!graph->implicit_preds[to]) |
| graph->implicit_preds[to] = BITMAP_ALLOC (&predbitmap_obstack); |
| |
| if (bitmap_set_bit (graph->implicit_preds[to], from)) |
| stats.num_implicit_edges++; |
| } |
| |
| /* Add a predecessor graph edge to GRAPH, going from TO to FROM if |
| it doesn't exist in the graph already. |
| Return false if the edge already existed, true otherwise. */ |
| |
| static void |
| add_pred_graph_edge (constraint_graph_t graph, unsigned int to, |
| unsigned int from) |
| { |
| if (!graph->preds[to]) |
| graph->preds[to] = BITMAP_ALLOC (&predbitmap_obstack); |
| bitmap_set_bit (graph->preds[to], from); |
| } |
| |
| /* Add a graph edge to GRAPH, going from FROM to TO if |
| it doesn't exist in the graph already. |
| Return false if the edge already existed, true otherwise. */ |
| |
| static bool |
| add_graph_edge (constraint_graph_t graph, unsigned int to, |
| unsigned int from) |
| { |
| if (to == from) |
| { |
| return false; |
| } |
| else |
| { |
| bool r = false; |
| |
| if (!graph->succs[from]) |
| graph->succs[from] = BITMAP_ALLOC (&pta_obstack); |
| |
| /* The graph solving process does not avoid "triangles", thus |
| there can be multiple paths from a node to another involving |
| intermediate other nodes. That causes extra copying which is |
| most difficult to avoid when the intermediate node is ESCAPED |
| because there are no edges added from ESCAPED. Avoid |
| adding the direct edge FROM -> TO when we have FROM -> ESCAPED |
| and TO contains ESCAPED. |
| ??? Note this is only a heuristic, it does not prevent the |
| situation from occuring. The heuristic helps PR38474 and |
| PR99912 significantly. */ |
| if (to < FIRST_REF_NODE |
| && bitmap_bit_p (graph->succs[from], find (escaped_id)) |
| && bitmap_bit_p (get_varinfo (find (to))->solution, escaped_id)) |
| return false; |
| |
| if (bitmap_set_bit (graph->succs[from], to)) |
| { |
| r = true; |
| if (to < FIRST_REF_NODE && from < FIRST_REF_NODE) |
| stats.num_edges++; |
| } |
| return r; |
| } |
| } |
| |
| |
| /* Initialize the constraint graph structure to contain SIZE nodes. */ |
| |
| static void |
| init_graph (unsigned int size) |
| { |
| unsigned int j; |
| |
| graph = XCNEW (struct constraint_graph); |
| graph->size = size; |
| graph->succs = XCNEWVEC (bitmap, graph->size); |
| graph->indirect_cycles = XNEWVEC (int, graph->size); |
| graph->rep = XNEWVEC (unsigned int, graph->size); |
| /* ??? Macros do not support template types with multiple arguments, |
| so we use a typedef to work around it. */ |
| typedef vec<constraint_t> vec_constraint_t_heap; |
| graph->complex = XCNEWVEC (vec_constraint_t_heap, size); |
| graph->pe = XCNEWVEC (unsigned int, graph->size); |
| graph->pe_rep = XNEWVEC (int, graph->size); |
| |
| for (j = 0; j < graph->size; j++) |
| { |
| graph->rep[j] = j; |
| graph->pe_rep[j] = -1; |
| graph->indirect_cycles[j] = -1; |
| } |
| } |
| |
| /* Build the constraint graph, adding only predecessor edges right now. */ |
| |
| static void |
| build_pred_graph (void) |
| { |
| int i; |
| constraint_t c; |
| unsigned int j; |
| |
| graph->implicit_preds = XCNEWVEC (bitmap, graph->size); |
| graph->preds = XCNEWVEC (bitmap, graph->size); |
| graph->pointer_label = XCNEWVEC (unsigned int, graph->size); |
| graph->loc_label = XCNEWVEC (unsigned int, graph->size); |
| graph->pointed_by = XCNEWVEC (bitmap, graph->size); |
| graph->points_to = XCNEWVEC (bitmap, graph->size); |
| graph->eq_rep = XNEWVEC (int, graph->size); |
| graph->direct_nodes = sbitmap_alloc (graph->size); |
| graph->address_taken = BITMAP_ALLOC (&predbitmap_obstack); |
| bitmap_clear (graph->direct_nodes); |
| |
| for (j = 1; j < FIRST_REF_NODE; j++) |
| { |
| if (!get_varinfo (j)->is_special_var) |
| bitmap_set_bit (graph->direct_nodes, j); |
| } |
| |
| for (j = 0; j < graph->size; j++) |
| graph->eq_rep[j] = -1; |
| |
| for (j = 0; j < varmap.length (); j++) |
| graph->indirect_cycles[j] = -1; |
| |
| FOR_EACH_VEC_ELT (constraints, i, c) |
| { |
| struct constraint_expr lhs = c->lhs; |
| struct constraint_expr rhs = c->rhs; |
| unsigned int lhsvar = lhs.var; |
| unsigned int rhsvar = rhs.var; |
| |
| if (lhs.type == DEREF) |
| { |
| /* *x = y. */ |
| if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR) |
| add_pred_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); |
| } |
| else if (rhs.type == DEREF) |
| { |
| /* x = *y */ |
| if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR) |
| add_pred_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar); |
| else |
| bitmap_clear_bit (graph->direct_nodes, lhsvar); |
| } |
| else if (rhs.type == ADDRESSOF) |
| { |
| varinfo_t v; |
| |
| /* x = &y */ |
| if (graph->points_to[lhsvar] == NULL) |
| graph->points_to[lhsvar] = BITMAP_ALLOC (&predbitmap_obstack); |
| bitmap_set_bit (graph->points_to[lhsvar], rhsvar); |
| |
| if (graph->pointed_by[rhsvar] == NULL) |
| graph->pointed_by[rhsvar] = BITMAP_ALLOC (&predbitmap_obstack); |
| bitmap_set_bit (graph->pointed_by[rhsvar], lhsvar); |
| |
| /* Implicitly, *x = y */ |
| add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); |
| |
| /* All related variables are no longer direct nodes. */ |
| bitmap_clear_bit (graph->direct_nodes, rhsvar); |
| v = get_varinfo (rhsvar); |
| if (!v->is_full_var) |
| { |
| v = get_varinfo (v->head); |
| do |
| { |
| bitmap_clear_bit (graph->direct_nodes, v->id); |
| v = vi_next (v); |
| } |
| while (v != NULL); |
| } |
| bitmap_set_bit (graph->address_taken, rhsvar); |
| } |
| else if (lhsvar > anything_id |
| && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0) |
| { |
| /* x = y */ |
| add_pred_graph_edge (graph, lhsvar, rhsvar); |
| /* Implicitly, *x = *y */ |
| add_implicit_graph_edge (graph, FIRST_REF_NODE + lhsvar, |
| FIRST_REF_NODE + rhsvar); |
| } |
| else if (lhs.offset != 0 || rhs.offset != 0) |
| { |
| if (rhs.offset != 0) |
| bitmap_clear_bit (graph->direct_nodes, lhs.var); |
| else if (lhs.offset != 0) |
| bitmap_clear_bit (graph->direct_nodes, rhs.var); |
| } |
| } |
| } |
| |
| /* Build the constraint graph, adding successor edges. */ |
| |
| static void |
| build_succ_graph (void) |
| { |
| unsigned i, t; |
| constraint_t c; |
| |
| FOR_EACH_VEC_ELT (constraints, i, c) |
| { |
| struct constraint_expr lhs; |
| struct constraint_expr rhs; |
| unsigned int lhsvar; |
| unsigned int rhsvar; |
| |
| if (!c) |
| continue; |
| |
| lhs = c->lhs; |
| rhs = c->rhs; |
| lhsvar = find (lhs.var); |
| rhsvar = find (rhs.var); |
| |
| if (lhs.type == DEREF) |
| { |
| if (rhs.offset == 0 && lhs.offset == 0 && rhs.type == SCALAR) |
| add_graph_edge (graph, FIRST_REF_NODE + lhsvar, rhsvar); |
| } |
| else if (rhs.type == DEREF) |
| { |
| if (rhs.offset == 0 && lhs.offset == 0 && lhs.type == SCALAR) |
| add_graph_edge (graph, lhsvar, FIRST_REF_NODE + rhsvar); |
| } |
| else if (rhs.type == ADDRESSOF) |
| { |
| /* x = &y */ |
| gcc_checking_assert (find (rhs.var) == rhs.var); |
| bitmap_set_bit (get_varinfo (lhsvar)->solution, rhsvar); |
| } |
| else if (lhsvar > anything_id |
| && lhsvar != rhsvar && lhs.offset == 0 && rhs.offset == 0) |
| { |
| add_graph_edge (graph, lhsvar, rhsvar); |
| } |
| } |
| |
| /* Add edges from STOREDANYTHING to all non-direct nodes that can |
| receive pointers. */ |
| t = find (storedanything_id); |
| for (i = integer_id + 1; i < FIRST_REF_NODE; ++i) |
| { |
| if (!bitmap_bit_p (graph->direct_nodes, i) |
| && get_varinfo (i)->may_have_pointers) |
| add_graph_edge (graph, find (i), t); |
| } |
| |
| /* Everything stored to ANYTHING also potentially escapes. */ |
| add_graph_edge (graph, find (escaped_id), t); |
| } |
| |
| |
| /* Changed variables on the last iteration. */ |
| static bitmap changed; |
| |
| /* Strongly Connected Component visitation info. */ |
| |
| class scc_info |
| { |
| public: |
| scc_info (size_t size); |
| ~scc_info (); |
| |
| auto_sbitmap visited; |
| auto_sbitmap deleted; |
| unsigned int *dfs; |
| unsigned int *node_mapping; |
| int current_index; |
| auto_vec<unsigned> scc_stack; |
| }; |
| |
| |
| /* Recursive routine to find strongly connected components in GRAPH. |
| SI is the SCC info to store the information in, and N is the id of current |
| graph node we are processing. |
| |
| This is Tarjan's strongly connected component finding algorithm, as |
| modified by Nuutila to keep only non-root nodes on the stack. |
| The algorithm can be found in "On finding the strongly connected |
| connected components in a directed graph" by Esko Nuutila and Eljas |
| Soisalon-Soininen, in Information Processing Letters volume 49, |
| number 1, pages 9-14. */ |
| |
| static void |
| scc_visit (constraint_graph_t graph, class scc_info *si, unsigned int n) |
| { |
| unsigned int i; |
| bitmap_iterator bi; |
| unsigned int my_dfs; |
| |
| bitmap_set_bit (si->visited, n); |
| si->dfs[n] = si->current_index ++; |
| my_dfs = si->dfs[n]; |
| |
| /* Visit all the successors. */ |
| EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[n], 0, i, bi) |
| { |
| unsigned int w; |
| |
| if (i > LAST_REF_NODE) |
| break; |
| |
| w = find (i); |
| if (bitmap_bit_p (si->deleted, w)) |
| continue; |
| |
| if (!bitmap_bit_p (si->visited, w)) |
| scc_visit (graph, si, w); |
| |
| unsigned int t = find (w); |
| gcc_checking_assert (find (n) == n); |
| if (si->dfs[t] < si->dfs[n]) |
| si->dfs[n] = si->dfs[t]; |
| } |
| |
| /* See if any components have been identified. */ |
| if (si->dfs[n] == my_dfs) |
| { |
| if (si->scc_stack.length () > 0 |
| && si->dfs[si->scc_stack.last ()] >= my_dfs) |
| { |
| bitmap scc = BITMAP_ALLOC (NULL); |
| unsigned int lowest_node; |
| bitmap_iterator bi; |
| |
| bitmap_set_bit (scc, n); |
| |
| while (si->scc_stack.length () != 0 |
| && si->dfs[si->scc_stack.last ()] >= my_dfs) |
| { |
| unsigned int w = si->scc_stack.pop (); |
| |
| bitmap_set_bit (scc, w); |
| } |
| |
| lowest_node = bitmap_first_set_bit (scc); |
| gcc_assert (lowest_node < FIRST_REF_NODE); |
| |
| /* Collapse the SCC nodes into a single node, and mark the |
| indirect cycles. */ |
| EXECUTE_IF_SET_IN_BITMAP (scc, 0, i, bi) |
| { |
| if (i < FIRST_REF_NODE) |
| { |
| if (unite (lowest_node, i)) |
| unify_nodes (graph, lowest_node, i, false); |
| } |
| else |
| { |
| unite (lowest_node, i); |
| graph->indirect_cycles[i - FIRST_REF_NODE] = lowest_node; |
| } |
| } |
| } |
| bitmap_set_bit (si->deleted, n); |
| } |
| else |
| si->scc_stack.safe_push (n); |
| } |
| |
| /* Unify node FROM into node TO, updating the changed count if |
| necessary when UPDATE_CHANGED is true. */ |
| |
| static void |
| unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from, |
| bool update_changed) |
| { |
| gcc_checking_assert (to != from && find (to) == to); |
| |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| fprintf (dump_file, "Unifying %s to %s\n", |
| get_varinfo (from)->name, |
| get_varinfo (to)->name); |
| |
| if (update_changed) |
| stats.unified_vars_dynamic++; |
| else |
| stats.unified_vars_static++; |
| |
| merge_graph_nodes (graph, to, from); |
| if (merge_node_constraints (graph, to, from)) |
| { |
| if (update_changed) |
| bitmap_set_bit (changed, to); |
| } |
| |
| /* Mark TO as changed if FROM was changed. If TO was already marked |
| as changed, decrease the changed count. */ |
| |
| if (update_changed |
| && bitmap_clear_bit (changed, from)) |
| bitmap_set_bit (changed, to); |
| varinfo_t fromvi = get_varinfo (from); |
| if (fromvi->solution) |
| { |
| /* If the solution changes because of the merging, we need to mark |
| the variable as changed. */ |
| varinfo_t tovi = get_varinfo (to); |
| if (bitmap_ior_into (tovi->solution, fromvi->solution)) |
| { |
| if (update_changed) |
| bitmap_set_bit (changed, to); |
| } |
| |
| BITMAP_FREE (fromvi->solution); |
| if (fromvi->oldsolution) |
| BITMAP_FREE (fromvi->oldsolution); |
| |
| if (stats.iterations > 0 |
| && tovi->oldsolution) |
| BITMAP_FREE (tovi->oldsolution); |
| } |
| if (graph->succs[to]) |
| bitmap_clear_bit (graph->succs[to], to); |
| } |
| |
| /* Information needed to compute the topological ordering of a graph. */ |
| |
| struct topo_info |
| { |
| /* sbitmap of visited nodes. */ |
| sbitmap visited; |
| /* Array that stores the topological order of the graph, *in |
| reverse*. */ |
| vec<unsigned> topo_order; |
| }; |
| |
| |
| /* Initialize and return a topological info structure. */ |
| |
| static struct topo_info * |
| init_topo_info (void) |
| { |
| size_t size = graph->size; |
| struct topo_info *ti = XNEW (struct topo_info); |
| ti->visited = sbitmap_alloc (size); |
| bitmap_clear (ti->visited); |
| ti->topo_order.create (1); |
| return ti; |
| } |
| |
| |
| /* Free the topological sort info pointed to by TI. */ |
| |
| static void |
| free_topo_info (struct topo_info *ti) |
| { |
| sbitmap_free (ti->visited); |
| ti->topo_order.release (); |
| free (ti); |
| } |
| |
| /* Visit the graph in topological order, and store the order in the |
| topo_info structure. */ |
| |
| static void |
| topo_visit (constraint_graph_t graph, struct topo_info *ti, |
| unsigned int n) |
| { |
| bitmap_iterator bi; |
| unsigned int j; |
| |
| bitmap_set_bit (ti->visited, n); |
| |
| if (graph->succs[n]) |
| EXECUTE_IF_SET_IN_BITMAP (graph->succs[n], 0, j, bi) |
| { |
| if (!bitmap_bit_p (ti->visited, j)) |
| topo_visit (graph, ti, j); |
| } |
| |
| ti->topo_order.safe_push (n); |
| } |
| |
| /* Process a constraint C that represents x = *(y + off), using DELTA as the |
| starting solution for y. */ |
| |
| static void |
| do_sd_constraint (constraint_graph_t graph, constraint_t c, |
| bitmap delta, bitmap *expanded_delta) |
| { |
| unsigned int lhs = c->lhs.var; |
| bool flag = false; |
| bitmap sol = get_varinfo (lhs)->solution; |
| unsigned int j; |
| bitmap_iterator bi; |
| HOST_WIDE_INT roffset = c->rhs.offset; |
| |
| /* Our IL does not allow this. */ |
| gcc_checking_assert (c->lhs.offset == 0); |
| |
| /* If the solution of Y contains anything it is good enough to transfer |
| this to the LHS. */ |
| if (bitmap_bit_p (delta, anything_id)) |
| { |
| flag |= bitmap_set_bit (sol, anything_id); |
| goto done; |
| } |
| |
| /* If we do not know at with offset the rhs is dereferenced compute |
| the reachability set of DELTA, conservatively assuming it is |
| dereferenced at all valid offsets. */ |
| if (roffset == UNKNOWN_OFFSET) |
| { |
| delta = solution_set_expand (delta, expanded_delta); |
| /* No further offset processing is necessary. */ |
| roffset = 0; |
| } |
| |
| /* For each variable j in delta (Sol(y)), add |
| an edge in the graph from j to x, and union Sol(j) into Sol(x). */ |
| EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) |
| { |
| varinfo_t v = get_varinfo (j); |
| HOST_WIDE_INT fieldoffset = v->offset + roffset; |
| unsigned HOST_WIDE_INT size = v->size; |
| unsigned int t; |
| |
| if (v->is_full_var) |
| ; |
| else if (roffset != 0) |
| { |
| if (fieldoffset < 0) |
| v = get_varinfo (v->head); |
| else |
| v = first_or_preceding_vi_for_offset (v, fieldoffset); |
| } |
| |
| /* We have to include all fields that overlap the current field |
| shifted by roffset. */ |
| do |
| { |
| t = find (v->id); |
| |
| /* Adding edges from the special vars is pointless. |
| They don't have sets that can change. */ |
| if (get_varinfo (t)->is_special_var) |
| flag |= bitmap_ior_into (sol, get_varinfo (t)->solution); |
| /* Merging the solution from ESCAPED needlessly increases |
| the set. Use ESCAPED as representative instead. */ |
| else if (v->id == escaped_id) |
| flag |= bitmap_set_bit (sol, escaped_id); |
| else if (v->may_have_pointers |
| && add_graph_edge (graph, lhs, t)) |
| flag |= bitmap_ior_into (sol, get_varinfo (t)->solution); |
| |
| if (v->is_full_var |
| || v->next == 0) |
| break; |
| |
| v = vi_next (v); |
| } |
| while (v->offset < fieldoffset + size); |
| } |
| |
| done: |
| /* If the LHS solution changed, mark the var as changed. */ |
| if (flag) |
| { |
| get_varinfo (lhs)->solution = sol; |
| bitmap_set_bit (changed, lhs); |
| } |
| } |
| |
| /* Process a constraint C that represents *(x + off) = y using DELTA |
| as the starting solution for x. */ |
| |
| static void |
| do_ds_constraint (constraint_t c, bitmap delta, bitmap *expanded_delta) |
| { |
| unsigned int rhs = c->rhs.var; |
| bitmap sol = get_varinfo (rhs)->solution; |
| unsigned int j; |
| bitmap_iterator bi; |
| HOST_WIDE_INT loff = c->lhs.offset; |
| bool escaped_p = false; |
| |
| /* Our IL does not allow this. */ |
| gcc_checking_assert (c->rhs.offset == 0); |
| |
| /* If the solution of y contains ANYTHING simply use the ANYTHING |
| solution. This avoids needlessly increasing the points-to sets. */ |
| if (bitmap_bit_p (sol, anything_id)) |
| sol = get_varinfo (find (anything_id))->solution; |
| |
| /* If the solution for x contains ANYTHING we have to merge the |
| solution of y into all pointer variables which we do via |
| STOREDANYTHING. */ |
| if (bitmap_bit_p (delta, anything_id)) |
| { |
| unsigned t = find (storedanything_id); |
| if (add_graph_edge (graph, t, rhs)) |
| { |
| if (bitmap_ior_into (get_varinfo (t)->solution, sol)) |
| bitmap_set_bit (changed, t); |
| } |
| return; |
| } |
| |
| /* If we do not know at with offset the rhs is dereferenced compute |
| the reachability set of DELTA, conservatively assuming it is |
| dereferenced at all valid offsets. */ |
| if (loff == UNKNOWN_OFFSET) |
| { |
| delta = solution_set_expand (delta, expanded_delta); |
| loff = 0; |
| } |
| |
| /* For each member j of delta (Sol(x)), add an edge from y to j and |
| union Sol(y) into Sol(j) */ |
| EXECUTE_IF_SET_IN_BITMAP (delta, 0, j, bi) |
| { |
| varinfo_t v = get_varinfo (j); |
| unsigned int t; |
| HOST_WIDE_INT fieldoffset = v->offset + loff; |
| unsigned HOST_WIDE_INT size = v->size; |
| |
| if (v->is_full_var) |
| ; |
| else if (loff != 0) |
| { |
| if (fieldoffset < 0) |
| v = get_varinfo (v->head); |
| else |
| v = first_or_preceding_vi_for_offset (v, fieldoffset); |
| } |
| |
| /* We have to include all fields that overlap the current field |
| shifted by loff. */ |
| do |
| { |
| if (v->may_have_pointers) |
| { |
| /* If v is a global variable then this is an escape point. */ |
| if (v->is_global_var |
| && !escaped_p) |
| { |
| t = find (escaped_id); |
| if (add_graph_edge (graph, t, rhs) |
| && bitmap_ior_into (get_varinfo (t)->solution, sol)) |
| bitmap_set_bit (changed, t); |
| /* Enough to let rhs escape once. */ |
| escaped_p = true; |
| } |
| |
| if (v->is_special_var) |
| break; |
| |
| t = find (v->id); |
| if (add_graph_edge (graph, t, rhs) |
| && bitmap_ior_into (get_varinfo (t)->solution, sol)) |
| bitmap_set_bit (changed, t); |
| } |
| |
| if (v->is_full_var |
| || v->next == 0) |
| break; |
| |
| v = vi_next (v); |
| } |
| while (v->offset < fieldoffset + size); |
| } |
| } |
| |
| /* Handle a non-simple (simple meaning requires no iteration), |
| constraint (IE *x = &y, x = *y, *x = y, and x = y with offsets involved). */ |
| |
| static void |
| do_complex_constraint (constraint_graph_t graph, constraint_t c, bitmap delta, |
| bitmap *expanded_delta) |
| { |
| if (c->lhs.type == DEREF) |
| { |
| if (c->rhs.type == ADDRESSOF) |
| { |
| gcc_unreachable (); |
| } |
| else |
| { |
| /* *x = y */ |
| do_ds_constraint (c, delta, expanded_delta); |
| } |
| } |
| else if (c->rhs.type == DEREF) |
| { |
| /* x = *y */ |
| if (!(get_varinfo (c->lhs.var)->is_special_var)) |
| do_sd_constraint (graph, c, delta, expanded_delta); |
| } |
| else |
| { |
| bitmap tmp; |
| bool flag = false; |
| |
| gcc_checking_assert (c->rhs.type == SCALAR && c->lhs.type == SCALAR |
| && c->rhs.offset != 0 && c->lhs.offset == 0); |
| tmp = get_varinfo (c->lhs.var)->solution; |
| |
| flag = set_union_with_increment (tmp, delta, c->rhs.offset, |
| expanded_delta); |
| |
| if (flag) |
| bitmap_set_bit (changed, c->lhs.var); |
| } |
| } |
| |
| /* Initialize and return a new SCC info structure. */ |
| |
| scc_info::scc_info (size_t size) : |
| visited (size), deleted (size), current_index (0), scc_stack (1) |
| { |
| bitmap_clear (visited); |
| bitmap_clear (deleted); |
| node_mapping = XNEWVEC (unsigned int, size); |
| dfs = XCNEWVEC (unsigned int, size); |
| |
| for (size_t i = 0; i < size; i++) |
| node_mapping[i] = i; |
| } |
| |
| /* Free an SCC info structure pointed to by SI */ |
| |
| scc_info::~scc_info () |
| { |
| free (node_mapping); |
| free (dfs); |
| } |
| |
| |
| /* Find indirect cycles in GRAPH that occur, using strongly connected |
| components, and note them in the indirect cycles map. |
| |
| This technique comes from Ben Hardekopf and Calvin Lin, |
| "It Pays to be Lazy: Fast and Accurate Pointer Analysis for Millions of |
| Lines of Code", submitted to PLDI 2007. */ |
| |
| static void |
| find_indirect_cycles (constraint_graph_t graph) |
| { |
| unsigned int i; |
| unsigned int size = graph->size; |
| scc_info si (size); |
| |
| for (i = 0; i < MIN (LAST_REF_NODE, size); i ++ ) |
| if (!bitmap_bit_p (si.visited, i) && find (i) == i) |
| scc_visit (graph, &si, i); |
| } |
| |
| /* Compute a topological ordering for GRAPH, and store the result in the |
| topo_info structure TI. */ |
| |
| static void |
| compute_topo_order (constraint_graph_t graph, |
| struct topo_info *ti) |
| { |
| unsigned int i; |
| unsigned int size = graph->size; |
| |
| for (i = 0; i != size; ++i) |
| if (!bitmap_bit_p (ti->visited, i) && find (i) == i) |
| topo_visit (graph, ti, i); |
| } |
| |
| /* Structure used to for hash value numbering of pointer equivalence |
| classes. */ |
| |
| typedef struct equiv_class_label |
| { |
| hashval_t hashcode; |
| unsigned int equivalence_class; |
| bitmap labels; |
| } *equiv_class_label_t; |
| typedef const struct equiv_class_label *const_equiv_class_label_t; |
| |
| /* Equiv_class_label hashtable helpers. */ |
| |
| struct equiv_class_hasher : nofree_ptr_hash <equiv_class_label> |
| { |
| static inline hashval_t hash (const equiv_class_label *); |
| static inline bool equal (const equiv_class_label *, |
| const equiv_class_label *); |
| }; |
| |
| /* Hash function for a equiv_class_label_t */ |
| |
| inline hashval_t |
| equiv_class_hasher::hash (const equiv_class_label *ecl) |
| { |
| return ecl->hashcode; |
| } |
| |
| /* Equality function for two equiv_class_label_t's. */ |
| |
| inline bool |
| equiv_class_hasher::equal (const equiv_class_label *eql1, |
| const equiv_class_label *eql2) |
| { |
| return (eql1->hashcode == eql2->hashcode |
| && bitmap_equal_p (eql1->labels, eql2->labels)); |
| } |
| |
| /* A hashtable for mapping a bitmap of labels->pointer equivalence |
| classes. */ |
| static hash_table<equiv_class_hasher> *pointer_equiv_class_table; |
| |
| /* A hashtable for mapping a bitmap of labels->location equivalence |
| classes. */ |
| static hash_table<equiv_class_hasher> *location_equiv_class_table; |
| |
| struct obstack equiv_class_obstack; |
| |
| /* Lookup a equivalence class in TABLE by the bitmap of LABELS with |
| hash HAS it contains. Sets *REF_LABELS to the bitmap LABELS |
| is equivalent to. */ |
| |
| static equiv_class_label * |
| equiv_class_lookup_or_add (hash_table<equiv_class_hasher> *table, |
| bitmap labels) |
| { |
| equiv_class_label **slot; |
| equiv_class_label ecl; |
| |
| ecl.labels = labels; |
| ecl.hashcode = bitmap_hash (labels); |
| slot = table->find_slot (&ecl, INSERT); |
| if (!*slot) |
| { |
| *slot = XOBNEW (&equiv_class_obstack, struct equiv_class_label); |
| (*slot)->labels = labels; |
| (*slot)->hashcode = ecl.hashcode; |
| (*slot)->equivalence_class = 0; |
| } |
| |
| return *slot; |
| } |
| |
| /* Perform offline variable substitution. |
| |
| This is a worst case quadratic time way of identifying variables |
| that must have equivalent points-to sets, including those caused by |
| static cycles, and single entry subgraphs, in the constraint graph. |
| |
| The technique is described in "Exploiting Pointer and Location |
| Equivalence to Optimize Pointer Analysis. In the 14th International |
| Static Analysis Symposium (SAS), August 2007." It is known as the |
| "HU" algorithm, and is equivalent to value numbering the collapsed |
| constraint graph including evaluating unions. |
| |
| The general method of finding equivalence classes is as follows: |
| Add fake nodes (REF nodes) and edges for *a = b and a = *b constraints. |
| Initialize all non-REF nodes to be direct nodes. |
| For each constraint a = a U {b}, we set pts(a) = pts(a) u {fresh |
| variable} |
| For each constraint containing the dereference, we also do the same |
| thing. |
| |
| We then compute SCC's in the graph and unify nodes in the same SCC, |
| including pts sets. |
| |
| For each non-collapsed node x: |
| Visit all unvisited explicit incoming edges. |
| Ignoring all non-pointers, set pts(x) = Union of pts(a) for y |
| where y->x. |
| Lookup the equivalence class for pts(x). |
| If we found one, equivalence_class(x) = found class. |
| Otherwise, equivalence_class(x) = new class, and new_class is |
| added to the lookup table. |
| |
| All direct nodes with the same equivalence class can be replaced |
| with a single representative node. |
| All unlabeled nodes (label == 0) are not pointers and all edges |
| involving them can be eliminated. |
| We perform these optimizations during rewrite_constraints |
| |
| In addition to pointer equivalence class finding, we also perform |
| location equivalence class finding. This is the set of variables |
| that always appear together in points-to sets. We use this to |
| compress the size of the points-to sets. */ |
| |
| /* Current maximum pointer equivalence class id. */ |
| static int pointer_equiv_class; |
| |
| /* Current maximum location equivalence class id. */ |
| static int location_equiv_class; |
| |
| /* Recursive routine to find strongly connected components in GRAPH, |
| and label it's nodes with DFS numbers. */ |
| |
| static void |
| condense_visit (constraint_graph_t graph, class scc_info *si, unsigned int n) |
| { |
| unsigned int i; |
| bitmap_iterator bi; |
| unsigned int my_dfs; |
| |
| gcc_checking_assert (si->node_mapping[n] == n); |
| bitmap_set_bit (si->visited, n); |
| si->dfs[n] = si->current_index ++; |
| my_dfs = si->dfs[n]; |
| |
| /* Visit all the successors. */ |
| EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) |
| { |
| unsigned int w = si->node_mapping[i]; |
| |
| if (bitmap_bit_p (si->deleted, w)) |
| continue; |
| |
| if (!bitmap_bit_p (si->visited, w)) |
| condense_visit (graph, si, w); |
| |
| unsigned int t = si->node_mapping[w]; |
| gcc_checking_assert (si->node_mapping[n] == n); |
| if (si->dfs[t] < si->dfs[n]) |
| si->dfs[n] = si->dfs[t]; |
| } |
| |
| /* Visit all the implicit predecessors. */ |
| EXECUTE_IF_IN_NONNULL_BITMAP (graph->implicit_preds[n], 0, i, bi) |
| { |
| unsigned int w = si->node_mapping[i]; |
| |
| if (bitmap_bit_p (si->deleted, w)) |
| continue; |
| |
| if (!bitmap_bit_p (si->visited, w)) |
| condense_visit (graph, si, w); |
| |
| unsigned int t = si->node_mapping[w]; |
| gcc_assert (si->node_mapping[n] == n); |
| if (si->dfs[t] < si->dfs[n]) |
| si->dfs[n] = si->dfs[t]; |
| } |
| |
| /* See if any components have been identified. */ |
| if (si->dfs[n] == my_dfs) |
| { |
| if (si->scc_stack.length () != 0 |
| && si->dfs[si->scc_stack.last ()] >= my_dfs) |
| { |
| /* Find the first node of the SCC and do non-bitmap work. */ |
| bool direct_p = true; |
| unsigned first = si->scc_stack.length (); |
| do |
| { |
| --first; |
| unsigned int w = si->scc_stack[first]; |
| si->node_mapping[w] = n; |
| if (!bitmap_bit_p (graph->direct_nodes, w)) |
| direct_p = false; |
| } |
| while (first > 0 |
| && si->dfs[si->scc_stack[first - 1]] >= my_dfs); |
| if (!direct_p) |
| bitmap_clear_bit (graph->direct_nodes, n); |
| |
| /* Want to reduce to node n, push that first. */ |
| si->scc_stack.reserve (1); |
| si->scc_stack.quick_push (si->scc_stack[first]); |
| si->scc_stack[first] = n; |
| |
| unsigned scc_size = si->scc_stack.length () - first; |
| unsigned split = scc_size / 2; |
| unsigned carry = scc_size - split * 2; |
| while (split > 0) |
| { |
| for (unsigned i = 0; i < split; ++i) |
| { |
| unsigned a = si->scc_stack[first + i]; |
| unsigned b = si->scc_stack[first + split + carry + i]; |
| |
| /* Unify our nodes. */ |
| if (graph->preds[b]) |
| { |
| if (!graph->preds[a]) |
| std::swap (graph->preds[a], graph->preds[b]); |
| else |
| bitmap_ior_into_and_free (graph->preds[a], |
| &graph->preds[b]); |
| } |
| if (graph->implicit_preds[b]) |
| { |
| if (!graph->implicit_preds[a]) |
| std::swap (graph->implicit_preds[a], |
| graph->implicit_preds[b]); |
| else |
| bitmap_ior_into_and_free (graph->implicit_preds[a], |
| &graph->implicit_preds[b]); |
| } |
| if (graph->points_to[b]) |
| { |
| if (!graph->points_to[a]) |
| std::swap (graph->points_to[a], graph->points_to[b]); |
| else |
| bitmap_ior_into_and_free (graph->points_to[a], |
| &graph->points_to[b]); |
| } |
| } |
| unsigned remain = split + carry; |
| split = remain / 2; |
| carry = remain - split * 2; |
| } |
| /* Actually pop the SCC. */ |
| si->scc_stack.truncate (first); |
| } |
| bitmap_set_bit (si->deleted, n); |
| } |
| else |
| si->scc_stack.safe_push (n); |
| } |
| |
| /* Label pointer equivalences. |
| |
| This performs a value numbering of the constraint graph to |
| discover which variables will always have the same points-to sets |
| under the current set of constraints. |
| |
| The way it value numbers is to store the set of points-to bits |
| generated by the constraints and graph edges. This is just used as a |
| hash and equality comparison. The *actual set of points-to bits* is |
| completely irrelevant, in that we don't care about being able to |
| extract them later. |
| |
| The equality values (currently bitmaps) just have to satisfy a few |
| constraints, the main ones being: |
| 1. The combining operation must be order independent. |
| 2. The end result of a given set of operations must be unique iff the |
| combination of input values is unique |
| 3. Hashable. */ |
| |
| static void |
| label_visit (constraint_graph_t graph, class scc_info *si, unsigned int n) |
| { |
| unsigned int i, first_pred; |
| bitmap_iterator bi; |
| |
| bitmap_set_bit (si->visited, n); |
| |
| /* Label and union our incoming edges's points to sets. */ |
| first_pred = -1U; |
| EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi) |
| { |
| unsigned int w = si->node_mapping[i]; |
| if (!bitmap_bit_p (si->visited, w)) |
| label_visit (graph, si, w); |
| |
| /* Skip unused edges */ |
| if (w == n || graph->pointer_label[w] == 0) |
| continue; |
| |
| if (graph->points_to[w]) |
| { |
| if (!graph->points_to[n]) |
| { |
| if (first_pred == -1U) |
| first_pred = w; |
| else |
| { |
| graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack); |
| bitmap_ior (graph->points_to[n], |
| graph->points_to[first_pred], |
| graph->points_to[w]); |
| } |
| } |
| else |
| bitmap_ior_into (graph->points_to[n], graph->points_to[w]); |
| } |
| } |
| |
| /* Indirect nodes get fresh variables and a new pointer equiv class. */ |
| if (!bitmap_bit_p (graph->direct_nodes, n)) |
| { |
| if (!graph->points_to[n]) |
| { |
| graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack); |
| if (first_pred != -1U) |
| bitmap_copy (graph->points_to[n], graph->points_to[first_pred]); |
| } |
| bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n); |
| graph->pointer_label[n] = pointer_equiv_class++; |
| equiv_class_label_t ecl; |
| ecl = equiv_class_lookup_or_add (pointer_equiv_class_table, |
| graph->points_to[n]); |
| ecl->equivalence_class = graph->pointer_label[n]; |
| return; |
| } |
| |
| /* If there was only a single non-empty predecessor the pointer equiv |
| class is the same. */ |
| if (!graph->points_to[n]) |
| { |
| if (first_pred != -1U) |
| { |
| graph->pointer_label[n] = graph->pointer_label[first_pred]; |
| graph->points_to[n] = graph->points_to[first_pred]; |
| } |
| return; |
| } |
| |
| if (!bitmap_empty_p (graph->points_to[n])) |
| { |
| equiv_class_label_t ecl; |
| ecl = equiv_class_lookup_or_add (pointer_equiv_class_table, |
| graph->points_to[n]); |
| if (ecl->equivalence_class == 0) |
| ecl->equivalence_class = pointer_equiv_class++; |
| else |
| { |
| BITMAP_FREE (graph->points_to[n]); |
| graph->points_to[n] = ecl->labels; |
| } |
| graph->pointer_label[n] = ecl->equivalence_class; |
| } |
| } |
| |
| /* Print the pred graph in dot format. */ |
| |
| static void |
| dump_pred_graph (class scc_info *si, FILE *file) |
| { |
| unsigned int i; |
| |
| /* Only print the graph if it has already been initialized: */ |
| if (!graph) |
| return; |
| |
| /* Prints the header of the dot file: */ |
| fprintf (file, "strict digraph {\n"); |
| fprintf (file, " node [\n shape = box\n ]\n"); |
| fprintf (file, " edge [\n fontsize = \"12\"\n ]\n"); |
| fprintf (file, "\n // List of nodes and complex constraints in " |
| "the constraint graph:\n"); |
| |
| /* The next lines print the nodes in the graph together with the |
| complex constraints attached to them. */ |
| for (i = 1; i < graph->size; i++) |
| { |
| if (i == FIRST_REF_NODE) |
| continue; |
| if (si->node_mapping[i] != i) |
| continue; |
| if (i < FIRST_REF_NODE) |
| fprintf (file, "\"%s\"", get_varinfo (i)->name); |
| else |
| fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name); |
| if (graph->points_to[i] |
| && !bitmap_empty_p (graph->points_to[i])) |
| { |
| if (i < FIRST_REF_NODE) |
| fprintf (file, "[label=\"%s = {", get_varinfo (i)->name); |
| else |
| fprintf (file, "[label=\"*%s = {", |
| get_varinfo (i - FIRST_REF_NODE)->name); |
| unsigned j; |
| bitmap_iterator bi; |
| EXECUTE_IF_SET_IN_BITMAP (graph->points_to[i], 0, j, bi) |
| fprintf (file, " %d", j); |
| fprintf (file, " }\"]"); |
| } |
| fprintf (file, ";\n"); |
| } |
| |
| /* Go over the edges. */ |
| fprintf (file, "\n // Edges in the constraint graph:\n"); |
| for (i = 1; i < graph->size; i++) |
| { |
| unsigned j; |
| bitmap_iterator bi; |
| if (si->node_mapping[i] != i) |
| continue; |
| EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[i], 0, j, bi) |
| { |
| unsigned from = si->node_mapping[j]; |
| if (from < FIRST_REF_NODE) |
| fprintf (file, "\"%s\"", get_varinfo (from)->name); |
| else |
| fprintf (file, "\"*%s\"", get_varinfo (from - FIRST_REF_NODE)->name); |
| fprintf (file, " -> "); |
| if (i < FIRST_REF_NODE) |
| fprintf (file, "\"%s\"", get_varinfo (i)->name); |
| else |
| fprintf (file, "\"*%s\"", get_varinfo (i - FIRST_REF_NODE)->name); |
| fprintf (file, ";\n"); |
| } |
| } |
| |
| /* Prints the tail of the dot file. */ |
| fprintf (file, "}\n"); |
| } |
| |
| /* Perform offline variable substitution, discovering equivalence |
| classes, and eliminating non-pointer variables. */ |
| |
| static class scc_info * |
| perform_var_substitution (constraint_graph_t graph) |
| { |
| unsigned int i; |
| unsigned int size = graph->size; |
| scc_info *si = new scc_info (size); |
| |
| bitmap_obstack_initialize (&iteration_obstack); |
| gcc_obstack_init (&equiv_class_obstack); |
| pointer_equiv_class_table = new hash_table<equiv_class_hasher> (511); |
| location_equiv_class_table |
| = new hash_table<equiv_class_hasher> (511); |
| pointer_equiv_class = 1; |
| location_equiv_class = 1; |
| |
| /* Condense the nodes, which means to find SCC's, count incoming |
| predecessors, and unite nodes in SCC's. */ |
| for (i = 1; i < FIRST_REF_NODE; i++) |
| if (!bitmap_bit_p (si->visited, si->node_mapping[i])) |
| condense_visit (graph, si, si->node_mapping[i]); |
| |
| if (dump_file && (dump_flags & TDF_GRAPH)) |
| { |
| fprintf (dump_file, "\n\n// The constraint graph before var-substitution " |
| "in dot format:\n"); |
| dump_pred_graph (si, dump_file); |
| fprintf (dump_file, "\n\n"); |
| } |
| |
| bitmap_clear (si->visited); |
| /* Actually the label the nodes for pointer equivalences */ |
| for (i = 1; i < FIRST_REF_NODE; i++) |
| if (!bitmap_bit_p (si->visited, si->node_mapping[i])) |
| label_visit (graph, si, si->node_mapping[i]); |
| |
| /* Calculate location equivalence labels. */ |
| for (i = 1; i < FIRST_REF_NODE; i++) |
| { |
| bitmap pointed_by; |
| bitmap_iterator bi; |
| unsigned int j; |
| |
| if (!graph->pointed_by[i]) |
| continue; |
| pointed_by = BITMAP_ALLOC (&iteration_obstack); |
| |
| /* Translate the pointed-by mapping for pointer equivalence |
| labels. */ |
| EXECUTE_IF_SET_IN_BITMAP (graph->pointed_by[i], 0, j, bi) |
| { |
| bitmap_set_bit (pointed_by, |
| graph->pointer_label[si->node_mapping[j]]); |
| } |
| /* The original pointed_by is now dead. */ |
| BITMAP_FREE (graph->pointed_by[i]); |
| |
| /* Look up the location equivalence label if one exists, or make |
| one otherwise. */ |
| equiv_class_label_t ecl; |
| ecl = equiv_class_lookup_or_add (location_equiv_class_table, pointed_by); |
| if (ecl->equivalence_class == 0) |
| ecl->equivalence_class = location_equiv_class++; |
| else |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| fprintf (dump_file, "Found location equivalence for node %s\n", |
| get_varinfo (i)->name); |
| BITMAP_FREE (pointed_by); |
| } |
| graph->loc_label[i] = ecl->equivalence_class; |
| |
| } |
| |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| for (i = 1; i < FIRST_REF_NODE; i++) |
| { |
| unsigned j = si->node_mapping[i]; |
| if (j != i) |
| { |
| fprintf (dump_file, "%s node id %d ", |
| bitmap_bit_p (graph->direct_nodes, i) |
| ? "Direct" : "Indirect", i); |
| if (i < FIRST_REF_NODE) |
| fprintf (dump_file, "\"%s\"", get_varinfo (i)->name); |
| else |
| fprintf (dump_file, "\"*%s\"", |
| get_varinfo (i - FIRST_REF_NODE)->name); |
| fprintf (dump_file, " mapped to SCC leader node id %d ", j); |
| if (j < FIRST_REF_NODE) |
| fprintf (dump_file, "\"%s\"\n", get_varinfo (j)->name); |
| else |
| fprintf (dump_file, "\"*%s\"\n", |
| get_varinfo (j - FIRST_REF_NODE)->name); |
| } |
| else |
| { |
| fprintf (dump_file, |
| "Equivalence classes for %s node id %d ", |
| bitmap_bit_p (graph->direct_nodes, i) |
| ? "direct" : "indirect", i); |
| if (i < FIRST_REF_NODE) |
| fprintf (dump_file, "\"%s\"", get_varinfo (i)->name); |
| else |
| fprintf (dump_file, "\"*%s\"", |
| get_varinfo (i - FIRST_REF_NODE)->name); |
| fprintf (dump_file, |
| ": pointer %d, location %d\n", |
| graph->pointer_label[i], graph->loc_label[i]); |
| } |
| } |
| |
| /* Quickly eliminate our non-pointer variables. */ |
| |
| for (i = 1; i < FIRST_REF_NODE; i++) |
| { |
| unsigned int node = si->node_mapping[i]; |
| |
| if (graph->pointer_label[node] == 0) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| fprintf (dump_file, |
| "%s is a non-pointer variable, eliminating edges.\n", |
| get_varinfo (node)->name); |
| stats.nonpointer_vars++; |
| clear_edges_for_node (graph, node); |
| } |
| } |
| |
| return si; |
| } |
| |
| /* Free information that was only necessary for variable |
| substitution. */ |
| |
| static void |
| free_var_substitution_info (class scc_info *si) |
| { |
| delete si; |
| free (graph->pointer_label); |
| free (graph->loc_label); |
| free (graph->pointed_by); |
| free (graph->points_to); |
| free (graph->eq_rep); |
| sbitmap_free (graph->direct_nodes); |
| delete pointer_equiv_class_table; |
| pointer_equiv_class_table = NULL; |
| delete location_equiv_class_table; |
| location_equiv_class_table = NULL; |
| obstack_free (&equiv_class_obstack, NULL); |
| bitmap_obstack_release (&iteration_obstack); |
| } |
| |
| /* Return an existing node that is equivalent to NODE, which has |
| equivalence class LABEL, if one exists. Return NODE otherwise. */ |
| |
| static unsigned int |
| find_equivalent_node (constraint_graph_t graph, |
| unsigned int node, unsigned int label) |
| { |
| /* If the address version of this variable is unused, we can |
| substitute it for anything else with the same label. |
| Otherwise, we know the pointers are equivalent, but not the |
| locations, and we can unite them later. */ |
| |
| if (!bitmap_bit_p (graph->address_taken, node)) |
| { |
| gcc_checking_assert (label < graph->size); |
| |
| if (graph->eq_rep[label] != -1) |
| { |
| /* Unify the two variables since we know they are equivalent. */ |
| if (unite (graph->eq_rep[label], node)) |
| unify_nodes (graph, graph->eq_rep[label], node, false); |
| return graph->eq_rep[label]; |
| } |
| else |
| { |
| graph->eq_rep[label] = node; |
| graph->pe_rep[label] = node; |
| } |
| } |
| else |
| { |
| gcc_checking_assert (label < graph->size); |
| graph->pe[node] = label; |
| if (graph->pe_rep[label] == -1) |
| graph->pe_rep[label] = node; |
| } |
| |
| return node; |
| } |
| |
| /* Unite pointer equivalent but not location equivalent nodes in |
| GRAPH. This may only be performed once variable substitution is |
| finished. */ |
| |
| static void |
| unite_pointer_equivalences (constraint_graph_t graph) |
| { |
| unsigned int i; |
| |
| /* Go through the pointer equivalences and unite them to their |
| representative, if they aren't already. */ |
| for (i = 1; i < FIRST_REF_NODE; i++) |
| { |
| unsigned int label = graph->pe[i]; |
| if (label) |
| { |
| int label_rep = graph->pe_rep[label]; |
| |
| if (label_rep == -1) |
| continue; |
| |
| label_rep = find (label_rep); |
| if (label_rep >= 0 && unite (label_rep, find (i))) |
| unify_nodes (graph, label_rep, i, false); |
| } |
| } |
| } |
| |
| /* Move complex constraints to the GRAPH nodes they belong to. */ |
| |
| static void |
| move_complex_constraints (constraint_graph_t graph) |
| { |
| int i; |
| constraint_t c; |
| |
| FOR_EACH_VEC_ELT (constraints, i, c) |
| { |
| if (c) |
| { |
| struct constraint_expr lhs = c->lhs; |
| struct constraint_expr rhs = c->rhs; |
| |
| if (lhs.type == DEREF) |
| { |
| insert_into_complex (graph, lhs.var, c); |
| } |
| else if (rhs.type == DEREF) |
| { |
| if (!(get_varinfo (lhs.var)->is_special_var)) |
| insert_into_complex (graph, rhs.var, c); |
| } |
| else if (rhs.type != ADDRESSOF && lhs.var > anything_id |
| && (lhs.offset != 0 || rhs.offset != 0)) |
| { |
| insert_into_complex (graph, rhs.var, c); |
| } |
| } |
| } |
| } |
| |
| |
| /* Optimize and rewrite complex constraints while performing |
| collapsing of equivalent nodes. SI is the SCC_INFO that is the |
| result of perform_variable_substitution. */ |
| |
| static void |
| rewrite_constraints (constraint_graph_t graph, |
| class scc_info *si) |
| { |
| int i; |
| constraint_t c; |
| |
| if (flag_checking) |
| { |
| for (unsigned int j = 0; j < graph->size; j++) |
| gcc_assert (find (j) == j); |
| } |
| |
| FOR_EACH_VEC_ELT (constraints, i, c) |
| { |
| struct constraint_expr lhs = c->lhs; |
| struct constraint_expr rhs = c->rhs; |
| unsigned int lhsvar = find (lhs.var); |
| unsigned int rhsvar = find (rhs.var); |
| unsigned int lhsnode, rhsnode; |
| unsigned int lhslabel, rhslabel; |
| |
| lhsnode = si->node_mapping[lhsvar]; |
| rhsnode = si->node_mapping[rhsvar]; |
| lhslabel = graph->pointer_label[lhsnode]; |
| rhslabel = graph->pointer_label[rhsnode]; |
| |
| /* See if it is really a non-pointer variable, and if so, ignore |
| the constraint. */ |
| if (lhslabel == 0) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| |
| fprintf (dump_file, "%s is a non-pointer variable, " |
| "ignoring constraint:", |
| get_varinfo (lhs.var)->name); |
| dump_constraint (dump_file, c); |
| fprintf (dump_file, "\n"); |
| } |
| constraints[i] = NULL; |
| continue; |
| } |
| |
| if (rhslabel == 0) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| |
| fprintf (dump_file, "%s is a non-pointer variable, " |
| "ignoring constraint:", |
| get_varinfo (rhs.var)->name); |
| dump_constraint (dump_file, c); |
| fprintf (dump_file, "\n"); |
| } |
| constraints[i] = NULL; |
| continue; |
| } |
| |
| lhsvar = find_equivalent_node (graph, lhsvar, lhslabel); |
| rhsvar = find_equivalent_node (graph, rhsvar, rhslabel); |
| c->lhs.var = lhsvar; |
| c->rhs.var = rhsvar; |
| } |
| } |
| |
| /* Eliminate indirect cycles involving NODE. Return true if NODE was |
| part of an SCC, false otherwise. */ |
| |
| static bool |
| eliminate_indirect_cycles (unsigned int node) |
| { |
| if (graph->indirect_cycles[node] != -1 |
| && !bitmap_empty_p (get_varinfo (node)->solution)) |
| { |
| unsigned int i; |
| auto_vec<unsigned> queue; |
| int queuepos; |
| unsigned int to = find (graph->indirect_cycles[node]); |
| bitmap_iterator bi; |
| |
| /* We can't touch the solution set and call unify_nodes |
| at the same time, because unify_nodes is going to do |
| bitmap unions into it. */ |
| |
| EXECUTE_IF_SET_IN_BITMAP (get_varinfo (node)->solution, 0, i, bi) |
| { |
| if (find (i) == i && i != to) |
| { |
| if (unite (to, i)) |
| queue.safe_push (i); |
| } |
| } |
| |
| for (queuepos = 0; |
| queue.iterate (queuepos, &i); |
| queuepos++) |
| { |
| unify_nodes (graph, to, i, true); |
| } |
| return true; |
| } |
| return false; |
| } |
| |
| /* Solve the constraint graph GRAPH using our worklist solver. |
| This is based on the PW* family of solvers from the "Efficient Field |
| Sensitive Pointer Analysis for C" paper. |
| It works by iterating over all the graph nodes, processing the complex |
| constraints and propagating the copy constraints, until everything stops |
| changed. This corresponds to steps 6-8 in the solving list given above. */ |
| |
| static void |
| solve_graph (constraint_graph_t graph) |
| { |
| unsigned int size = graph->size; |
| unsigned int i; |
| bitmap pts; |
| |
| changed = BITMAP_ALLOC (NULL); |
| |
| /* Mark all initial non-collapsed nodes as changed. */ |
| for (i = 1; i < size; i++) |
| { |
| varinfo_t ivi = get_varinfo (i); |
| if (find (i) == i && !bitmap_empty_p (ivi->solution) |
| && ((graph->succs[i] && !bitmap_empty_p (graph->succs[i])) |
| || graph->complex[i].length () > 0)) |
| bitmap_set_bit (changed, i); |
| } |
| |
| /* Allocate a bitmap to be used to store the changed bits. */ |
| pts = BITMAP_ALLOC (&pta_obstack); |
| |
| while (!bitmap_empty_p (changed)) |
| { |
| unsigned int i; |
| struct topo_info *ti = init_topo_info (); |
| stats.iterations++; |
| |
| bitmap_obstack_initialize (&iteration_obstack); |
| |
| compute_topo_order (graph, ti); |
| |
| while (ti->topo_order.length () != 0) |
| { |
| |
| i = ti->topo_order.pop (); |
| |
| /* If this variable is not a representative, skip it. */ |
| if (find (i) != i) |
| continue; |
| |
| /* In certain indirect cycle cases, we may merge this |
| variable to another. */ |
| if (eliminate_indirect_cycles (i) && find (i) != i) |
| continue; |
| |
| /* If the node has changed, we need to process the |
| complex constraints and outgoing edges again. */ |
| if (bitmap_clear_bit (changed, i)) |
| { |
| unsigned int j; |
| constraint_t c; |
| bitmap solution; |
| vec<constraint_t> complex = graph->complex[i]; |
| varinfo_t vi = get_varinfo (i); |
| bool solution_empty; |
| |
| /* Compute the changed set of solution bits. If anything |
| is in the solution just propagate that. */ |
| if (bitmap_bit_p (vi->solution, anything_id)) |
| { |
| /* If anything is also in the old solution there is |
| nothing to do. |
| ??? But we shouldn't ended up with "changed" set ... */ |
| if (vi->oldsolution |
| && bitmap_bit_p (vi->oldsolution, anything_id)) |
| continue; |
| bitmap_copy (pts, get_varinfo (find (anything_id))->solution); |
| } |
| else if (vi->oldsolution) |
| bitmap_and_compl (pts, vi->solution, vi->oldsolution); |
| else |
| bitmap_copy (pts, vi->solution); |
| |
| if (bitmap_empty_p (pts)) |
| continue; |
| |
| if (vi->oldsolution) |
| bitmap_ior_into (vi->oldsolution, pts); |
| else |
| { |
| vi->oldsolution = BITMAP_ALLOC (&oldpta_obstack); |
| bitmap_copy (vi->oldsolution, pts); |
| } |
| |
| solution = vi->solution; |
| solution_empty = bitmap_empty_p (solution); |
| |
| /* Process the complex constraints */ |
| bitmap expanded_pts = NULL; |
| FOR_EACH_VEC_ELT (complex, j, c) |
| { |
| /* XXX: This is going to unsort the constraints in |
| some cases, which will occasionally add duplicate |
| constraints during unification. This does not |
| affect correctness. */ |
| c->lhs.var = find (c->lhs.var); |
| c->rhs.var = find (c->rhs.var); |
| |
| /* The only complex constraint that can change our |
| solution to non-empty, given an empty solution, |
| is a constraint where the lhs side is receiving |
| some set from elsewhere. */ |
| if (!solution_empty || c->lhs.type != DEREF) |
| do_complex_constraint (graph, c, pts, &expanded_pts); |
| } |
| BITMAP_FREE (expanded_pts); |
| |
| solution_empty = bitmap_empty_p (solution); |
| |
| if (!solution_empty) |
| { |
| bitmap_iterator bi; |
| unsigned eff_escaped_id = find (escaped_id); |
| |
| /* Propagate solution to all successors. */ |
| unsigned to_remove = ~0U; |
| EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], |
| 0, j, bi) |
| { |
| if (to_remove != ~0U) |
| { |
| bitmap_clear_bit (graph->succs[i], to_remove); |
| to_remove = ~0U; |
| } |
| unsigned int to = find (j); |
| if (to != j) |
| { |
| /* Update the succ graph, avoiding duplicate |
| work. */ |
| to_remove = j; |
| if (! bitmap_set_bit (graph->succs[i], to)) |
| continue; |
| /* We eventually end up processing 'to' twice |
| as it is undefined whether bitmap iteration |
| iterates over bits set during iteration. |
| Play safe instead of doing tricks. */ |
| } |
| /* Don't try to propagate to ourselves. */ |
| if (to == i) |
| continue; |
| |
| bitmap tmp = get_varinfo (to)->solution; |
| bool flag = false; |
| |
| /* If we propagate from ESCAPED use ESCAPED as |
| placeholder. */ |
| if (i == eff_escaped_id) |
| flag = bitmap_set_bit (tmp, escaped_id); |
| else |
| flag = bitmap_ior_into (tmp, pts); |
| |
| if (flag) |
| bitmap_set_bit (changed, to); |
| } |
| if (to_remove != ~0U) |
| bitmap_clear_bit (graph->succs[i], to_remove); |
| } |
| } |
| } |
| free_topo_info (ti); |
| bitmap_obstack_release (&iteration_obstack); |
| } |
| |
| BITMAP_FREE (pts); |
| BITMAP_FREE (changed); |
| bitmap_obstack_release (&oldpta_obstack); |
| } |
| |
| /* Map from trees to variable infos. */ |
| static hash_map<tree, varinfo_t> *vi_for_tree; |
| |
| |
| /* Insert ID as the variable id for tree T in the vi_for_tree map. */ |
| |
| static void |
| insert_vi_for_tree (tree t, varinfo_t vi) |
| { |
| gcc_assert (vi); |
| gcc_assert (!vi_for_tree->put (t, vi)); |
| } |
| |
| /* Find the variable info for tree T in VI_FOR_TREE. If T does not |
| exist in the map, return NULL, otherwise, return the varinfo we found. */ |
| |
| static varinfo_t |
| lookup_vi_for_tree (tree t) |
| { |
| varinfo_t *slot = vi_for_tree->get (t); |
| if (slot == NULL) |
| return NULL; |
| |
| return *slot; |
| } |
| |
| /* Return a printable name for DECL */ |
| |
| static const char * |
| alias_get_name (tree decl) |
| { |
| const char *res = "NULL"; |
| if (dump_file) |
| { |
| char *temp = NULL; |
| if (TREE_CODE (decl) == SSA_NAME) |
| { |
| res = get_name (decl); |
| temp = xasprintf ("%s_%u", res ? res : "", SSA_NAME_VERSION (decl)); |
| } |
| else if (HAS_DECL_ASSEMBLER_NAME_P (decl) |
| && DECL_ASSEMBLER_NAME_SET_P (decl)) |
| res = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME_RAW (decl)); |
| else if (DECL_P (decl)) |
| { |
| res = get_name (decl); |
| if (!res) |
| temp = xasprintf ("D.%u", DECL_UID (decl)); |
| } |
| |
| if (temp) |
| { |
| res = ggc_strdup (temp); |
| free (temp); |
| } |
| } |
| |
| return res; |
| } |
| |
| /* Find the variable id for tree T in the map. |
| If T doesn't exist in the map, create an entry for it and return it. */ |
| |
| static varinfo_t |
| get_vi_for_tree (tree t) |
| { |
| varinfo_t *slot = vi_for_tree->get (t); |
| if (slot == NULL) |
| { |
| unsigned int id = create_variable_info_for (t, alias_get_name (t), false); |
| return get_varinfo (id); |
| } |
| |
| return *slot; |
| } |
| |
| /* Get a scalar constraint expression for a new temporary variable. */ |
| |
| static struct constraint_expr |
| new_scalar_tmp_constraint_exp (const char *name, bool add_id) |
| { |
| struct constraint_expr tmp; |
| varinfo_t vi; |
| |
| vi = new_var_info (NULL_TREE, name, add_id); |
| vi->offset = 0; |
| vi->size = -1; |
| vi->fullsize = -1; |
| vi->is_full_var = 1; |
| vi->is_reg_var = 1; |
| |
| tmp.var = vi->id; |
| tmp.type = SCALAR; |
| tmp.offset = 0; |
| |
| return tmp; |
| } |
| |
| /* Get a constraint expression vector from an SSA_VAR_P node. |
| If address_p is true, the result will be taken its address of. */ |
| |
| static void |
| get_constraint_for_ssa_var (tree t, vec<ce_s> *results, bool address_p) |
| { |
| struct constraint_expr cexpr; |
| varinfo_t vi; |
| |
| /* We allow FUNCTION_DECLs here even though it doesn't make much sense. */ |
| gcc_assert (TREE_CODE (t) == SSA_NAME || DECL_P (t)); |
| |
| if (TREE_CODE (t) == SSA_NAME |
| && SSA_NAME_IS_DEFAULT_DEF (t)) |
| { |
| /* For parameters, get at the points-to set for the actual parm |
| decl. */ |
| if (TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL |
| || TREE_CODE (SSA_NAME_VAR (t)) == RESULT_DECL) |
| { |
| get_constraint_for_ssa_var (SSA_NAME_VAR (t), results, address_p); |
| return; |
| } |
| /* For undefined SSA names return nothing. */ |
| else if (!ssa_defined_default_def_p (t)) |
| { |
| cexpr.var = nothing_id; |
| cexpr.type = SCALAR; |
| cexpr.offset = 0; |
| results->safe_push (cexpr); |
| return; |
| } |
| } |
| |
| /* For global variables resort to the alias target. */ |
| if (VAR_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t))) |
| { |
| varpool_node *node = varpool_node::get (t); |
| if (node && node->alias && node->analyzed) |
| { |
| node = node->ultimate_alias_target (); |
| /* Canonicalize the PT uid of all aliases to the ultimate target. |
| ??? Hopefully the set of aliases can't change in a way that |
| changes the ultimate alias target. */ |
| gcc_assert ((! DECL_PT_UID_SET_P (node->decl) |
| || DECL_PT_UID (node->decl) == DECL_UID (node->decl)) |
| && (! DECL_PT_UID_SET_P (t) |
| || DECL_PT_UID (t) == DECL_UID (node->decl))); |
| DECL_PT_UID (t) = DECL_UID (node->decl); |
| t = node->decl; |
| } |
| |
| /* If this is decl may bind to NULL note that. */ |
| if (address_p |
| && (! node || ! node->nonzero_address ())) |
| { |
| cexpr.var = nothing_id; |
| cexpr.type = SCALAR; |
| cexpr.offset = 0; |
| results->safe_push (cexpr); |
| } |
| } |
| |
| vi = get_vi_for_tree (t); |
| cexpr.var = vi->id; |
| cexpr.type = SCALAR; |
| cexpr.offset = 0; |
| |
| /* If we are not taking the address of the constraint expr, add all |
| sub-fiels of the variable as well. */ |
| if (!address_p |
| && !vi->is_full_var) |
| { |
| for (; vi; vi = vi_next (vi)) |
| { |
| cexpr.var = vi->id; |
| results->safe_push (cexpr); |
| } |
| return; |
| } |
| |
| results->safe_push (cexpr); |
| } |
| |
| /* Process constraint T, performing various simplifications and then |
| adding it to our list of overall constraints. */ |
| |
| static void |
| process_constraint (constraint_t t) |
| { |
| struct constraint_expr rhs = t->rhs; |
| struct constraint_expr lhs = t->lhs; |
| |
| gcc_assert (rhs.var < varmap.length ()); |
| gcc_assert (lhs.var < varmap.length ()); |
| |
| /* If we didn't get any useful constraint from the lhs we get |
| &ANYTHING as fallback from get_constraint_for. Deal with |
| it here by turning it into *ANYTHING. */ |
| if (lhs.type == ADDRESSOF |
| && lhs.var == anything_id) |
| lhs.type = DEREF; |
| |
| /* ADDRESSOF on the lhs is invalid. */ |
| gcc_assert (lhs.type != ADDRESSOF); |
| |
| /* We shouldn't add constraints from things that cannot have pointers. |
| It's not completely trivial to avoid in the callers, so do it here. */ |
| if (rhs.type != ADDRESSOF |
| && !get_varinfo (rhs.var)->may_have_pointers) |
| return; |
| |
| /* Likewise adding to the solution of a non-pointer var isn't useful. */ |
| if (!get_varinfo (lhs.var)->may_have_pointers) |
| return; |
| |
| /* This can happen in our IR with things like n->a = *p */ |
| if (rhs.type == DEREF && lhs.type == DEREF && rhs.var != anything_id) |
| { |
| /* Split into tmp = *rhs, *lhs = tmp */ |
| struct constraint_expr tmplhs; |
| tmplhs = new_scalar_tmp_constraint_exp ("doubledereftmp", true); |
| process_constraint (new_constraint (tmplhs, rhs)); |
| process_constraint (new_constraint (lhs, tmplhs)); |
| } |
| else if ((rhs.type != SCALAR || rhs.offset != 0) && lhs.type == DEREF) |
| { |
| /* Split into tmp = &rhs, *lhs = tmp */ |
| struct constraint_expr tmplhs; |
| tmplhs = new_scalar_tmp_constraint_exp ("derefaddrtmp", true); |
| process_constraint (new_constraint (tmplhs, rhs)); |
| process_constraint (new_constraint (lhs, tmplhs)); |
| } |
| else |
| { |
| gcc_assert (rhs.type != ADDRESSOF || rhs.offset == 0); |
| if (rhs.type == ADDRESSOF) |
| get_varinfo (get_varinfo (rhs.var)->head)->address_taken = true; |
| constraints.safe_push (t); |
| } |
| } |
| |
| |
| /* Return the position, in bits, of FIELD_DECL from the beginning of its |
| structure. */ |
| |
| static HOST_WIDE_INT |
| bitpos_of_field (const tree fdecl) |
| { |
| if (!tree_fits_shwi_p (DECL_FIELD_OFFSET (fdecl)) |
| || !tree_fits_shwi_p (DECL_FIELD_BIT_OFFSET (fdecl))) |
| return -1; |
| |
| return (tree_to_shwi (DECL_FIELD_OFFSET (fdecl)) * BITS_PER_UNIT |
| + tree_to_shwi (DECL_FIELD_BIT_OFFSET (fdecl))); |
| } |
| |
| |
| /* Get constraint expressions for offsetting PTR by OFFSET. Stores the |
| resulting constraint expressions in *RESULTS. */ |
| |
| static void |
| get_constraint_for_ptr_offset (tree ptr, tree offset, |
| vec<ce_s> *results) |
| { |
| struct constraint_expr c; |
| unsigned int j, n; |
| HOST_WIDE_INT rhsoffset; |
| |
| /* If we do not do field-sensitive PTA adding offsets to pointers |
| does not change the points-to solution. */ |
| if (!use_field_sensitive) |
| { |
| get_constraint_for_rhs (ptr, results); |
| return; |
| } |
| |
| /* If the offset is not a non-negative integer constant that fits |
| in a HOST_WIDE_INT, we have to fall back to a conservative |
| solution which includes all sub-fields of all pointed-to |
| variables of ptr. */ |
| if (offset == NULL_TREE |
| || TREE_CODE (offset) != INTEGER_CST) |
| rhsoffset = UNKNOWN_OFFSET; |
| else |
| { |
| /* Sign-extend the offset. */ |
| offset_int soffset = offset_int::from (wi::to_wide (offset), SIGNED); |
| if (!wi::fits_shwi_p (soffset)) |
| rhsoffset = UNKNOWN_OFFSET; |
| else |
| { |
| /* Make sure the bit-offset also fits. */ |
| HOST_WIDE_INT rhsunitoffset = soffset.to_shwi (); |
| rhsoffset = rhsunitoffset * (unsigned HOST_WIDE_INT) BITS_PER_UNIT; |
| if (rhsunitoffset != rhsoffset / BITS_PER_UNIT) |
| rhsoffset = UNKNOWN_OFFSET; |
| } |
| } |
| |
| get_constraint_for_rhs (ptr, results); |
| if (rhsoffset == 0) |
| return; |
| |
| /* As we are eventually appending to the solution do not use |
| vec::iterate here. */ |
| n = results->length (); |
| for (j = 0; j < n; j++) |
| { |
| varinfo_t curr; |
| c = (*results)[j]; |
| curr = get_varinfo (c.var); |
| |
| if (c.type == ADDRESSOF |
| /* If this varinfo represents a full variable just use it. */ |
| && curr->is_full_var) |
| ; |
| else if (<
|