X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-ssa.c;h=24b5697f2203b11292d38427cf9fe8c3610146e0;hb=afdc9016cd75c0ac0c9f439dc7fd4d5a4a4392d7;hp=27b3a5b1bf007827b8fce1becce90632e170bb29;hpb=cbbefea46e5a749a5182df5770cc70f30e12aa2e;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-ssa.c b/gcc/tree-ssa.c index 27b3a5b1bf0..24b5697f220 100644 --- a/gcc/tree-ssa.c +++ b/gcc/tree-ssa.c @@ -36,35 +36,16 @@ Boston, MA 02111-1307, USA. */ #include "function.h" #include "diagnostic.h" #include "bitmap.h" +#include "pointer-set.h" #include "tree-flow.h" #include "tree-gimple.h" #include "tree-inline.h" #include "varray.h" #include "timevar.h" -#include "tree-alias-common.h" #include "hashtab.h" #include "tree-dump.h" #include "tree-pass.h" - -/* Remove edge E and remove the corresponding arguments from the PHI nodes - in E's destination block. */ - -void -ssa_remove_edge (edge e) -{ - tree phi, next; - - /* Remove the appropriate PHI arguments in E's destination block. */ - for (phi = phi_nodes (e->dest); phi; phi = next) - { - next = PHI_CHAIN (phi); - remove_phi_arg (phi, e->src); - } - - remove_edge (e); -} - /* Remove the corresponding arguments from the PHI nodes in E's destination block and redirect it to DEST. Return redirected edge. The list of removed arguments is stored in PENDING_STMT (e). */ @@ -83,7 +64,7 @@ ssa_redirect_edge (edge e, basic_block dest) next = PHI_CHAIN (phi); i = phi_arg_from_edge (phi, e); - if (i < 0) + if (PHI_ARG_DEF (phi, i) == NULL_TREE) continue; src = PHI_ARG_DEF (phi, i); @@ -91,8 +72,6 @@ ssa_redirect_edge (edge e, basic_block dest) node = build_tree_list (dst, src); *last = node; last = &TREE_CHAIN (node); - - remove_phi_arg_num (phi, i); } e = redirect_edge_succ_nodup (e, dest); @@ -101,6 +80,27 @@ ssa_redirect_edge (edge e, basic_block dest) return e; } +/* Add PHI arguments queued in PENDINT_STMT list on edge E to edge + E->dest. */ + +void +flush_pending_stmts (edge e) +{ + tree phi, arg; + + if (!PENDING_STMT (e)) + return; + + for (phi = phi_nodes (e->dest), arg = PENDING_STMT (e); + phi; + phi = PHI_CHAIN (phi), arg = TREE_CHAIN (arg)) + { + tree def = TREE_VALUE (arg); + add_phi_arg (phi, def, e); + } + + PENDING_STMT (e) = NULL; +} /* Return true if SSA_NAME is malformed and mark it visited. @@ -178,9 +178,9 @@ verify_def (basic_block bb, basic_block *definition_block, tree ssa_name, { error ("SSA_NAME_DEF_STMT is wrong"); fprintf (stderr, "Expected definition statement:\n"); - debug_generic_stmt (SSA_NAME_DEF_STMT (ssa_name)); + print_generic_stmt (stderr, SSA_NAME_DEF_STMT (ssa_name), TDF_VOPS); fprintf (stderr, "\nActual definition statement:\n"); - debug_generic_stmt (stmt); + print_generic_stmt (stderr, stmt, TDF_VOPS); goto err; } @@ -190,7 +190,7 @@ err: fprintf (stderr, "while verifying SSA_NAME "); print_generic_expr (stderr, ssa_name, 0); fprintf (stderr, " in statement\n"); - debug_generic_stmt (stmt); + print_generic_stmt (stderr, stmt, TDF_VOPS); return true; } @@ -208,11 +208,15 @@ err: arguments). IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a - V_MUST_DEF. */ + V_MUST_DEF. + + If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names + that are defined before STMT in basic block BB. */ static bool verify_use (basic_block bb, basic_block def_bb, tree ssa_name, - tree stmt, bool check_abnormal, bool is_virtual) + tree stmt, bool check_abnormal, bool is_virtual, + bitmap names_defined_in_bb) { bool err = false; @@ -233,6 +237,13 @@ verify_use (basic_block bb, basic_block def_bb, tree ssa_name, def_bb->index, bb->index); err = true; } + else if (bb == def_bb + && names_defined_in_bb != NULL + && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name))) + { + error ("Definition in block %i follows the use", def_bb->index); + err = true; + } if (check_abnormal && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name)) @@ -244,9 +255,9 @@ verify_use (basic_block bb, basic_block def_bb, tree ssa_name, if (err) { fprintf (stderr, "for SSA_NAME: "); - debug_generic_expr (ssa_name); + print_generic_expr (stderr, ssa_name, TDF_VOPS); fprintf (stderr, "in statement:\n"); - debug_generic_stmt (stmt); + print_generic_stmt (stderr, stmt, TDF_VOPS); } return err; @@ -256,8 +267,6 @@ verify_use (basic_block bb, basic_block def_bb, tree ssa_name, /* Return true if any of the arguments for PHI node PHI at block BB is malformed. - IDOM contains immediate dominator information for the flowgraph. - DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the block in that array slot contains the definition of SSA_NAME. */ @@ -267,71 +276,62 @@ verify_phi_args (tree phi, basic_block bb, basic_block *definition_block) { edge e; bool err = false; - int i, phi_num_args = PHI_NUM_ARGS (phi); + unsigned i, phi_num_args = PHI_NUM_ARGS (phi); - /* Mark all the incoming edges. */ - for (e = bb->pred; e; e = e->pred_next) - e->aux = (void *) 1; + if (EDGE_COUNT (bb->preds) != phi_num_args) + { + error ("Incoming edge count does not match number of PHI arguments\n"); + err = true; + goto error; + } for (i = 0; i < phi_num_args; i++) { tree op = PHI_ARG_DEF (phi, i); - e = PHI_ARG_EDGE (phi, i); - - if (TREE_CODE (op) == SSA_NAME) - err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op, - phi, e->flags & EDGE_ABNORMAL, - !is_gimple_reg (PHI_RESULT (phi))); + e = EDGE_PRED (bb, i); - if (e->dest != bb) + if (op == NULL_TREE) { - error ("Wrong edge %d->%d for PHI argument\n", - e->src->index, e->dest->index, bb->index); + error ("PHI argument is missing for edge %d->%d\n", + e->src->index, + e->dest->index); err = true; + goto error; } - if (e->aux == (void *) 0) + if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op)) { - error ("PHI argument flowing through dead edge %d->%d\n", - e->src->index, e->dest->index); + error ("PHI argument is not SSA_NAME, or invariant"); err = true; } - if (e->aux == (void *) 2) + if (TREE_CODE (op) == SSA_NAME) + err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op, + phi, e->flags & EDGE_ABNORMAL, + !is_gimple_reg (PHI_RESULT (phi)), + NULL); + + if (e->dest != bb) { - error ("PHI argument duplicated for edge %d->%d\n", e->src->index, - e->dest->index); + error ("Wrong edge %d->%d for PHI argument\n", + e->src->index, e->dest->index, bb->index); err = true; } if (err) { fprintf (stderr, "PHI argument\n"); - debug_generic_stmt (op); - goto error; - } - - e->aux = (void *) 2; - } - - for (e = bb->pred; e; e = e->pred_next) - { - if (e->aux != (void *) 2) - { - error ("No argument flowing through edge %d->%d\n", e->src->index, - e->dest->index); - err = true; + print_generic_stmt (stderr, op, TDF_VOPS); goto error; } - e->aux = (void *) 0; } error: if (err) { fprintf (stderr, "for PHI node\n"); - debug_generic_stmt (phi); + print_generic_stmt (stderr, phi, TDF_VOPS); } @@ -348,28 +348,25 @@ verify_flow_insensitive_alias_info (void) for (i = 0; i < num_referenced_vars; i++) { + size_t j; var_ann_t ann; + varray_type may_aliases; var = referenced_var (i); ann = var_ann (var); + may_aliases = ann->may_aliases; - if (ann->mem_tag_kind == TYPE_TAG || ann->mem_tag_kind == NAME_TAG) + for (j = 0; may_aliases && j < VARRAY_ACTIVE_SIZE (may_aliases); j++) { - size_t j; - varray_type may_aliases = ann->may_aliases; + tree alias = VARRAY_TREE (may_aliases, j); - for (j = 0; may_aliases && j < VARRAY_ACTIVE_SIZE (may_aliases); j++) - { - tree alias = VARRAY_TREE (may_aliases, j); + bitmap_set_bit (visited, var_ann (alias)->uid); - bitmap_set_bit (visited, var_ann (alias)->uid); - - if (!may_be_aliased (alias)) - { - error ("Non-addressable variable inside an alias set."); - debug_variable (alias); - goto err; - } + if (!may_be_aliased (alias)) + { + error ("Non-addressable variable inside an alias set."); + debug_variable (alias); + goto err; } } } @@ -407,51 +404,43 @@ verify_flow_sensitive_alias_info (void) for (i = 1; i < num_ssa_names; i++) { + tree var; var_ann_t ann; struct ptr_info_def *pi; + ptr = ssa_name (i); - ann = var_ann (SSA_NAME_VAR (ptr)); - pi = SSA_NAME_PTR_INFO (ptr); + if (!ptr) + continue; /* We only care for pointers that are actually referenced in the program. */ - if (!TREE_VISITED (ptr) || !POINTER_TYPE_P (TREE_TYPE (ptr))) + if (!POINTER_TYPE_P (TREE_TYPE (ptr)) || !TREE_VISITED (ptr)) continue; /* RESULT_DECL is special. If it's a GIMPLE register, then it is only written-to only once in the return statement. Otherwise, aggregate RESULT_DECLs may be written-to more than once in virtual operands. */ - if (TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL + var = SSA_NAME_VAR (ptr); + if (TREE_CODE (var) == RESULT_DECL && is_gimple_reg (ptr)) continue; + pi = SSA_NAME_PTR_INFO (ptr); if (pi == NULL) continue; + ann = var_ann (var); if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag) { error ("Dereferenced pointers should have a name or a type tag"); goto err; } - if (pi->pt_anything && (pi->pt_malloc || pi->pt_vars)) - { - error ("Pointers that point to anything should not point to malloc or other vars"); - goto err; - } - - if (pi->pt_malloc && pi->pt_vars) - { - error ("Pointers pointing to malloc get a unique tag and cannot point to other vars"); - goto err; - } - if (pi->name_mem_tag && !pi->pt_malloc - && (pi->pt_vars == NULL - || bitmap_first_set_bit (pi->pt_vars) < 0)) + && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars))) { error ("Pointers with a memory tag, should have points-to sets or point to malloc"); goto err; @@ -464,32 +453,6 @@ verify_flow_sensitive_alias_info (void) error ("Pointer escapes but its name tag is not call-clobbered."); goto err; } - - if (pi->name_mem_tag && pi->pt_vars) - { - size_t j; - - for (j = i + 1; j < num_ssa_names; j++) - { - tree ptr2 = ssa_name (j); - struct ptr_info_def *pi2 = SSA_NAME_PTR_INFO (ptr2); - - if (!POINTER_TYPE_P (TREE_TYPE (ptr2))) - continue; - - if (pi2 - && pi2->name_mem_tag - && pi2->pt_vars - && bitmap_first_set_bit (pi2->pt_vars) >= 0 - && pi->name_mem_tag != pi2->name_mem_tag - && bitmap_equal_p (pi->pt_vars, pi2->pt_vars)) - { - error ("Two pointers with different name tags and identical points-to sets"); - debug_variable (ptr2); - goto err; - } - } - } } return; @@ -499,17 +462,91 @@ err: internal_error ("verify_flow_sensitive_alias_info failed."); } +DEF_VEC_MALLOC_P (bitmap); -/* Verify the consistency of aliasing information. */ +/* Verify that all name tags have different points to sets. + This algorithm takes advantage of the fact that every variable with the + same name tag must have the same points-to set. + So we check a single variable for each name tag, and verify that its + points-to set is different from every other points-to set for other name + tags. */ static void -verify_alias_info (void) +verify_name_tags (void) { - if (aliases_computed_p) + size_t i; + size_t j; + bitmap first, second; + VEC (tree) *name_tag_reps = NULL; + VEC (bitmap) *pt_vars_for_reps = NULL; + + /* First we compute the name tag representatives and their points-to sets. */ + for (i = 0; i < num_ssa_names; i++) { - verify_flow_sensitive_alias_info (); - verify_flow_insensitive_alias_info (); + if (ssa_name (i)) + { + tree ptr = ssa_name (i); + struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); + if (!TREE_VISITED (ptr) + || !POINTER_TYPE_P (TREE_TYPE (ptr)) + || !pi + || !pi->name_mem_tag + || TREE_VISITED (pi->name_mem_tag)) + continue; + TREE_VISITED (pi->name_mem_tag) = 1; + if (pi->pt_vars != NULL) + { + VEC_safe_push (tree, name_tag_reps, ptr); + VEC_safe_push (bitmap, pt_vars_for_reps, pi->pt_vars); + } + } } + + /* Now compare all the representative bitmaps with all other representative + bitmaps, to verify that they are all different. */ + for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++) + { + for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++) + { + if (bitmap_equal_p (first, second)) + { + error ("Two different pointers with identical points-to sets but different name tags"); + debug_variable (VEC_index (tree, name_tag_reps, j)); + goto err; + } + } + } + + /* Lastly, clear out the visited flags. */ + for (i = 0; i < num_ssa_names; i++) + { + if (ssa_name (i)) + { + tree ptr = ssa_name (i); + struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); + if (!TREE_VISITED (ptr) + || !POINTER_TYPE_P (TREE_TYPE (ptr)) + || !pi + || !pi->name_mem_tag) + continue; + TREE_VISITED (pi->name_mem_tag) = 0; + } + } + VEC_free (bitmap, pt_vars_for_reps); + return; + +err: + debug_variable (VEC_index (tree, name_tag_reps, i)); + internal_error ("verify_name_tags failed"); +} +/* Verify the consistency of aliasing information. */ + +static void +verify_alias_info (void) +{ + verify_flow_sensitive_alias_info (); + verify_name_tags (); + verify_flow_insensitive_alias_info (); } @@ -522,73 +559,34 @@ verify_ssa (void) size_t i; basic_block bb; basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block)); + ssa_op_iter iter; + tree op; + enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS]; + bitmap names_defined_in_bb = BITMAP_XMALLOC (); timevar_push (TV_TREE_SSA_VERIFY); /* Keep track of SSA names present in the IL. */ for (i = 1; i < num_ssa_names; i++) - TREE_VISITED (ssa_name (i)) = 0; - - calculate_dominance_info (CDI_DOMINATORS); - - /* Verify and register all the SSA_NAME definitions found in the - function. */ - FOR_EACH_BB (bb) { - tree phi; - block_stmt_iterator bsi; - - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) - if (verify_def (bb, definition_block, PHI_RESULT (phi), phi, - !is_gimple_reg (PHI_RESULT (phi)))) - goto err; - - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + tree name = ssa_name (i); + if (name) { tree stmt; - stmt_ann_t ann; - unsigned int j; - v_may_def_optype v_may_defs; - v_must_def_optype v_must_defs; - def_optype defs; - - stmt = bsi_stmt (bsi); - ann = stmt_ann (stmt); - get_stmt_operands (stmt); - - v_may_defs = V_MAY_DEF_OPS (ann); - if (ann->makes_aliased_stores && NUM_V_MAY_DEFS (v_may_defs) == 0) - { - error ("Statement makes aliased stores, but has no V_MAY_DEFS"); - debug_generic_stmt (stmt); - goto err; - } - - for (j = 0; j < NUM_V_MAY_DEFS (v_may_defs); j++) - { - tree op = V_MAY_DEF_RESULT (v_may_defs, j); - if (verify_def (bb, definition_block, op, stmt, true)) - goto err; - } - - v_must_defs = STMT_V_MUST_DEF_OPS (stmt); - for (j = 0; j < NUM_V_MUST_DEFS (v_must_defs); j++) - { - tree op = V_MUST_DEF_OP (v_must_defs, j); - if (verify_def (bb, definition_block, op, stmt, true)) - goto err; - } + TREE_VISITED (name) = 0; - defs = DEF_OPS (ann); - for (j = 0; j < NUM_DEFS (defs); j++) + stmt = SSA_NAME_DEF_STMT (name); + if (!IS_EMPTY_STMT (stmt)) { - tree op = DEF_OP (defs, j); - if (verify_def (bb, definition_block, op, stmt, false)) - goto err; + basic_block bb = bb_for_stmt (stmt); + verify_def (bb, definition_block, + name, stmt, !is_gimple_reg (name)); + } } } + calculate_dominance_info (CDI_DOMINATORS); /* Now verify all the uses and make sure they agree with the definitions found in the previous pass. */ @@ -596,10 +594,11 @@ verify_ssa (void) { edge e; tree phi; + edge_iterator ei; block_stmt_iterator bsi; /* Make sure that all edges have a clear 'aux' field. */ - for (e = bb->pred; e; e = e->pred_next) + FOR_EACH_EDGE (e, ei, bb->preds) { if (e->aux) { @@ -611,52 +610,57 @@ verify_ssa (void) /* Verify the arguments for every PHI node in the block. */ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) - if (verify_phi_args (phi, bb, definition_block)) - goto err; + { + if (verify_phi_args (phi, bb, definition_block)) + goto err; + bitmap_set_bit (names_defined_in_bb, + SSA_NAME_VERSION (PHI_RESULT (phi))); + } /* Now verify all the uses and vuses in every statement of the block. */ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) { tree stmt = bsi_stmt (bsi); - stmt_ann_t ann = stmt_ann (stmt); - unsigned int j; - vuse_optype vuses; - v_may_def_optype v_may_defs; - use_optype uses; - - vuses = VUSE_OPS (ann); - for (j = 0; j < NUM_VUSES (vuses); j++) - { - tree op = VUSE_OP (vuses, j); - if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)], - op, stmt, false, true)) - goto err; - } - v_may_defs = V_MAY_DEF_OPS (ann); - for (j = 0; j < NUM_V_MAY_DEFS (v_may_defs); j++) + get_stmt_operands (stmt); + + if (stmt_ann (stmt)->makes_aliased_stores + && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0) + { + error ("Statement makes aliased stores, but has no V_MAY_DEFS"); + print_generic_stmt (stderr, stmt, TDF_VOPS); + goto err; + } + + FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) { - tree op = V_MAY_DEF_OP (v_may_defs, j); if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)], - op, stmt, false, true)) + op, stmt, false, !is_gimple_reg (op), + names_defined_in_bb)) goto err; } - uses = USE_OPS (ann); - for (j = 0; j < NUM_USES (uses); j++) + FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS) { - tree op = USE_OP (uses, j); - if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)], - op, stmt, false, false)) - goto err; + bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op)); } } + + bitmap_clear (names_defined_in_bb); } /* Finally, verify alias information. */ verify_alias_info (); free (definition_block); + /* Restore the dominance information to its prior known state, so + that we do not perturb the compiler's subsequent behavior. */ + if (orig_dom_state == DOM_NONE) + free_dominance_info (CDI_DOMINATORS); + else + dom_computed[CDI_DOMINATORS] = orig_dom_state; + + BITMAP_XFREE (names_defined_in_bb); timevar_pop (TV_TREE_SSA_VERIFY); return; @@ -677,7 +681,6 @@ init_tree_ssa (void) init_ssanames (); init_phinodes (); global_var = NULL_TREE; - aliases_computed_p = false; } @@ -693,13 +696,22 @@ delete_tree_ssa (void) /* Remove annotations from every tree in the function. */ FOR_EACH_BB (bb) for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) - bsi_stmt (bsi)->common.ann = NULL; + { + tree stmt = bsi_stmt (bsi); + release_defs (stmt); + ggc_free (stmt->common.ann); + stmt->common.ann = NULL; + } /* Remove annotations from every referenced variable. */ if (referenced_vars) { for (i = 0; i < num_referenced_vars; i++) - referenced_var (i)->common.ann = NULL; + { + tree var = referenced_var (i); + ggc_free (var->common.ann); + var->common.ann = NULL; + } referenced_vars = NULL; } @@ -710,7 +722,6 @@ delete_tree_ssa (void) global_var = NULL_TREE; BITMAP_XFREE (call_clobbered_vars); call_clobbered_vars = NULL; - aliases_computed_p = false; BITMAP_XFREE (addressable_vars); addressable_vars = NULL; } @@ -737,6 +748,9 @@ tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type) implement the ABI. */ else if (POINTER_TYPE_P (inner_type) && POINTER_TYPE_P (outer_type) + && TYPE_MODE (inner_type) == TYPE_MODE (outer_type) + && TYPE_REF_CAN_ALIAS_ALL (inner_type) + == TYPE_REF_CAN_ALIAS_ALL (outer_type) && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE) return true; @@ -744,6 +758,9 @@ tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type) so strip conversions that just switch between them. */ else if (POINTER_TYPE_P (inner_type) && POINTER_TYPE_P (outer_type) + && TYPE_MODE (inner_type) == TYPE_MODE (outer_type) + && TYPE_REF_CAN_ALIAS_ALL (inner_type) + == TYPE_REF_CAN_ALIAS_ALL (outer_type) && lang_hooks.types_compatible_p (TREE_TYPE (inner_type), TREE_TYPE (outer_type))) return true; @@ -798,12 +815,31 @@ tree_ssa_useless_type_conversion (tree expr) return false; } +/* Returns true if statement STMT may read memory. */ + +bool +stmt_references_memory_p (tree stmt) +{ + stmt_ann_t ann; + + get_stmt_operands (stmt); + ann = stmt_ann (stmt); + + if (ann->has_volatile_ops) + return true; + + return (NUM_VUSES (VUSE_OPS (ann)) > 0 + || NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) > 0 + || NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) > 0); +} /* Internal helper for walk_use_def_chains. VAR, FN and DATA are as described in walk_use_def_chains. - VISITED is a bitmap used to mark visited SSA_NAMEs to avoid - infinite loops. + VISITED is a pointer set used to mark visited SSA_NAMEs to avoid + infinite loops. We used to have a bitmap for this to just mark + SSA versions we had visited. But non-sparse bitmaps are way too + expensive, while sparse bitmaps may cause quadratic behavior. IS_DFS is true if the caller wants to perform a depth-first search when visiting PHI nodes. A DFS will visit each PHI argument and @@ -813,15 +849,13 @@ tree_ssa_useless_type_conversion (tree expr) static bool walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data, - bitmap visited, bool is_dfs) + struct pointer_set_t *visited, bool is_dfs) { tree def_stmt; - if (bitmap_bit_p (visited, SSA_NAME_VERSION (var))) + if (pointer_set_insert (visited, var)) return false; - bitmap_set_bit (visited, SSA_NAME_VERSION (var)); - def_stmt = SSA_NAME_DEF_STMT (var); if (TREE_CODE (def_stmt) != PHI_NODE) @@ -889,10 +923,7 @@ walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data, { tree def_stmt; -#if defined ENABLE_CHECKING - if (TREE_CODE (var) != SSA_NAME) - abort (); -#endif + gcc_assert (TREE_CODE (var) == SSA_NAME); def_stmt = SSA_NAME_DEF_STMT (var); @@ -902,9 +933,9 @@ walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data, (*fn) (var, def_stmt, data); else { - bitmap visited = BITMAP_XMALLOC (); + struct pointer_set_t *visited = pointer_set_create (); walk_use_def_chains_1 (var, fn, data, visited, is_dfs); - BITMAP_XFREE (visited); + pointer_set_destroy (visited); } } @@ -924,16 +955,15 @@ propagate_into_addr (tree stmt, tree var, tree *x, tree repl) return; addr_var = TREE_OPERAND (repl, 0); - while (TREE_CODE (*x) == ARRAY_REF - || TREE_CODE (*x) == COMPONENT_REF - || TREE_CODE (*x) == BIT_FIELD_REF) + while (handled_component_p (*x) + || TREE_CODE (*x) == REALPART_EXPR + || TREE_CODE (*x) == IMAGPART_EXPR) x = &TREE_OPERAND (*x, 0); if (TREE_CODE (*x) != INDIRECT_REF || TREE_OPERAND (*x, 0) != var) return; - modify_stmt (stmt); if (TREE_TYPE (*x) == TREE_TYPE (addr_var)) { *x = addr_var; @@ -941,6 +971,7 @@ propagate_into_addr (tree stmt, tree var, tree *x, tree repl) return; } + /* Frontends sometimes produce expressions like *&a instead of a[0]. Create a temporary variable to handle this case. */ ass_stmt = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, repl); @@ -961,14 +992,12 @@ propagate_into_addr (tree stmt, tree var, tree *x, tree repl) static void replace_immediate_uses (tree var, tree repl) { - use_optype uses; - vuse_optype vuses; - v_may_def_optype v_may_defs; int i, j, n; dataflow_t df; tree stmt; - stmt_ann_t ann; bool mark_new_vars; + ssa_op_iter iter; + use_operand_p use_p; df = get_immediate_uses (SSA_NAME_DEF_STMT (var)); n = num_immediate_uses (df); @@ -976,7 +1005,6 @@ replace_immediate_uses (tree var, tree repl) for (i = 0; i < n; i++) { stmt = immediate_use (df, i); - ann = stmt_ann (stmt); if (TREE_CODE (stmt) == PHI_NODE) { @@ -1002,25 +1030,44 @@ replace_immediate_uses (tree var, tree repl) propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 1), repl); } - uses = USE_OPS (ann); - for (j = 0; j < (int) NUM_USES (uses); j++) - if (USE_OP (uses, j) == var) + FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) + if (USE_FROM_PTR (use_p) == var) { - propagate_value (USE_OP_PTR (uses, j), repl); + propagate_value (use_p, repl); mark_new_vars = POINTER_TYPE_P (TREE_TYPE (repl)); } } else { - vuses = VUSE_OPS (ann); - for (j = 0; j < (int) NUM_VUSES (vuses); j++) - if (VUSE_OP (vuses, j) == var) - propagate_value (VUSE_OP_PTR (vuses, j), repl); - - v_may_defs = V_MAY_DEF_OPS (ann); - for (j = 0; j < (int) NUM_V_MAY_DEFS (v_may_defs); j++) - if (V_MAY_DEF_OP (v_may_defs, j) == var) - propagate_value (V_MAY_DEF_OP_PTR (v_may_defs, j), repl); + FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, + SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS) + if (USE_FROM_PTR (use_p) == var) + propagate_value (use_p, repl); + } + + /* FIXME. If REPL is a constant, we need to fold STMT. + However, fold_stmt wants a pointer to the statement, because + it may happen that it needs to replace the whole statement + with a new expression. Since the current def-use machinery + does not return pointers to statements, we call fold_stmt + with the address of a local temporary, if that call changes + the temporary then we fallback on looking for a proper + pointer to STMT by scanning STMT's basic block. + + Note that all this will become unnecessary soon. This + pass is being replaced with a proper copy propagation pass + for 4.1 (dnovillo, 2004-09-17). */ + if (TREE_CODE (repl) != SSA_NAME) + { + tree tmp = stmt; + fold_stmt (&tmp); + mark_new_vars = true; + if (tmp != stmt) + { + block_stmt_iterator si = bsi_for_stmt (stmt); + bsi_replace (&si, tmp, true); + stmt = bsi_stmt (si); + } } /* If REPL is a pointer, it may have different memory tags associated @@ -1091,7 +1138,7 @@ check_phi_redundancy (tree phi, tree *eq_to) } if (val - && !operand_equal_p (val, def, 0)) + && !operand_equal_for_phi_arg_p (val, def)) return; val = def; @@ -1099,8 +1146,7 @@ check_phi_redundancy (tree phi, tree *eq_to) /* At least one of the arguments should not be equal to the result, or something strange is happening. */ - if (!val) - abort (); + gcc_assert (val); if (get_eq_name (eq_to, res) == val) return; @@ -1166,7 +1212,7 @@ kill_redundant_phi_nodes (void) FOR_EACH_BB (bb) { - for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) { var = PHI_RESULT (phi); check_phi_redundancy (phi, eq_to); @@ -1210,13 +1256,14 @@ struct tree_opt_pass pass_redundant_phi = NULL, /* sub */ NULL, /* next */ 0, /* static_pass_number */ - 0, /* tv_id */ - PROP_cfg | PROP_ssa, /* properties_required */ + TV_TREE_REDPHI, /* tv_id */ + PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ TODO_dump_func | TODO_rename_vars - | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */ + | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */ + 0 /* letter */ }; /* Emit warnings for uninitialized variables. This is done in two passes. @@ -1253,7 +1300,7 @@ warn_uninit (tree t, const char *msgid, location_t *locus) return; /* Hard register variables get their initial value from the ether. */ - if (DECL_HARD_REGISTER (var)) + if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var)) return; /* TREE_NO_WARNING either means we already warned, or the front end @@ -1279,10 +1326,10 @@ warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data) /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */ if (TREE_CODE (t) == SSA_NAME) { - warn_uninit (t, "%H'%D' is used uninitialized in this function", locus); + warn_uninit (t, "%H%qD is used uninitialized in this function", locus); *walk_subtrees = 0; } - else if (DECL_P (t) || TYPE_P (t)) + else if (IS_TYPE_OR_DECL_P (t)) *walk_subtrees = 0; return NULL_TREE; @@ -1304,7 +1351,7 @@ warn_uninitialized_phi (tree phi) { tree op = PHI_ARG_DEF (phi, i); if (TREE_CODE (op) == SSA_NAME) - warn_uninit (op, "%H'%D' may be used uninitialized in this function", + warn_uninit (op, "%H%qD may be used uninitialized in this function", NULL); } } @@ -1356,7 +1403,8 @@ struct tree_opt_pass pass_early_warn_uninitialized = 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - 0 /* todo_flags_finish */ + 0, /* todo_flags_finish */ + 0 /* letter */ }; struct tree_opt_pass pass_late_warn_uninitialized = @@ -1372,5 +1420,7 @@ struct tree_opt_pass pass_late_warn_uninitialized = 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - 0 /* todo_flags_finish */ + 0, /* todo_flags_finish */ + 0 /* letter */ }; +