+/* qsort comparison function to sort type/name tags by DECL_UID. */
+
+static int
+sort_tags_by_id (const void *pa, const void *pb)
+{
+ tree a = *(tree *)pa;
+ tree b = *(tree *)pb;
+
+ return DECL_UID (a) - DECL_UID (b);
+}
+
+/* Initialize WORKLIST to contain those memory tags that are marked call
+ clobbered. Initialized WORKLIST2 to contain the reasons these
+ memory tags escaped. */
+
+static void
+init_transitive_clobber_worklist (VEC (tree, heap) **worklist,
+ VEC (int, heap) **worklist2)
+{
+ referenced_var_iterator rvi;
+ tree curr;
+
+ FOR_EACH_REFERENCED_VAR (curr, rvi)
+ {
+ if (MTAG_P (curr) && is_call_clobbered (curr))
+ {
+ VEC_safe_push (tree, heap, *worklist, curr);
+ VEC_safe_push (int, heap, *worklist2, var_ann (curr)->escape_mask);
+ }
+ }
+}
+
+/* Add ALIAS to WORKLIST (and the reason for escaping REASON to WORKLIST2) if
+ ALIAS is not already marked call clobbered, and is a memory
+ tag. */
+
+static void
+add_to_worklist (tree alias, VEC (tree, heap) **worklist,
+ VEC (int, heap) **worklist2,
+ int reason)
+{
+ if (MTAG_P (alias) && !is_call_clobbered (alias))
+ {
+ VEC_safe_push (tree, heap, *worklist, alias);
+ VEC_safe_push (int, heap, *worklist2, reason);
+ }
+}
+
+/* Mark aliases of TAG as call clobbered, and place any tags on the
+ alias list that were not already call clobbered on WORKLIST. */
+
+static void
+mark_aliases_call_clobbered (tree tag, VEC (tree, heap) **worklist,
+ VEC (int, heap) **worklist2)
+{
+ unsigned int i;
+ VEC (tree, gc) *ma;
+ tree entry;
+ var_ann_t ta = var_ann (tag);
+
+ if (!MTAG_P (tag))
+ return;
+ ma = may_aliases (tag);
+ if (!ma)
+ return;
+
+ for (i = 0; VEC_iterate (tree, ma, i, entry); i++)
+ {
+ if (!unmodifiable_var_p (entry))
+ {
+ add_to_worklist (entry, worklist, worklist2, ta->escape_mask);
+ mark_call_clobbered (entry, ta->escape_mask);
+ }
+ }
+}
+
+/* Tags containing global vars need to be marked as global.
+ Tags containing call clobbered vars need to be marked as call
+ clobbered. */
+
+static void
+compute_tag_properties (void)
+{
+ referenced_var_iterator rvi;
+ tree tag;
+ bool changed = true;
+ VEC (tree, heap) *taglist = NULL;
+
+ FOR_EACH_REFERENCED_VAR (tag, rvi)
+ {
+ if (!MTAG_P (tag) || TREE_CODE (tag) == STRUCT_FIELD_TAG)
+ continue;
+ VEC_safe_push (tree, heap, taglist, tag);
+ }
+
+ /* We sort the taglist by DECL_UID, for two reasons.
+ 1. To get a sequential ordering to make the bitmap accesses
+ faster.
+ 2. Because of the way we compute aliases, it's more likely that
+ an earlier tag is included in a later tag, and this will reduce
+ the number of iterations.
+
+ If we had a real tag graph, we would just topo-order it and be
+ done with it. */
+ qsort (VEC_address (tree, taglist),
+ VEC_length (tree, taglist),
+ sizeof (tree),
+ sort_tags_by_id);
+
+ /* Go through each tag not marked as global, and if it aliases
+ global vars, mark it global.
+
+ If the tag contains call clobbered vars, mark it call
+ clobbered.
+
+ This loop iterates because tags may appear in the may-aliases
+ list of other tags when we group. */
+
+ while (changed)
+ {
+ unsigned int k;
+
+ changed = false;
+ for (k = 0; VEC_iterate (tree, taglist, k, tag); k++)
+ {
+ VEC (tree, gc) *ma;
+ unsigned int i;
+ tree entry;
+ bool tagcc = is_call_clobbered (tag);
+ bool tagglobal = MTAG_GLOBAL (tag);
+
+ if (tagcc && tagglobal)
+ continue;
+
+ ma = may_aliases (tag);
+ if (!ma)
+ continue;
+
+ for (i = 0; VEC_iterate (tree, ma, i, entry); i++)
+ {
+ /* Call clobbered entries cause the tag to be marked
+ call clobbered. */
+ if (!tagcc && is_call_clobbered (entry))
+ {
+ mark_call_clobbered (tag, var_ann (entry)->escape_mask);
+ tagcc = true;
+ changed = true;
+ }
+
+ /* Global vars cause the tag to be marked global. */
+ if (!tagglobal && is_global_var (entry))
+ {
+ MTAG_GLOBAL (tag) = true;
+ changed = true;
+ tagglobal = true;
+ }
+
+ /* Early exit once both global and cc are set, since the
+ loop can't do any more than that. */
+ if (tagcc && tagglobal)
+ break;
+ }
+ }
+ }
+ VEC_free (tree, heap, taglist);
+}
+
+/* Set up the initial variable clobbers and globalness.
+ When this function completes, only tags whose aliases need to be
+ clobbered will be set clobbered. Tags clobbered because they
+ contain call clobbered vars are handled in compute_tag_properties. */
+
+static void
+set_initial_properties (struct alias_info *ai)
+{
+ unsigned int i;
+ referenced_var_iterator rvi;
+ tree var;
+ tree ptr;
+
+ FOR_EACH_REFERENCED_VAR (var, rvi)
+ {
+ if (is_global_var (var)
+ && (!var_can_have_subvars (var)
+ || get_subvars_for_var (var) == NULL))
+ {
+ if (!unmodifiable_var_p (var))
+ mark_call_clobbered (var, ESCAPE_IS_GLOBAL);
+ }
+ else if (TREE_CODE (var) == PARM_DECL
+ && default_def (var)
+ && POINTER_TYPE_P (TREE_TYPE (var)))
+ {
+ tree def = default_def (var);
+ get_ptr_info (def)->value_escapes_p = 1;
+ get_ptr_info (def)->escape_mask |= ESCAPE_IS_PARM;
+ }
+ }
+
+ for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
+ {
+ struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
+ var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr));
+
+ if (pi->value_escapes_p)
+ {
+ /* If PTR escapes then its associated memory tags and
+ pointed-to variables are call-clobbered. */
+ if (pi->name_mem_tag)
+ mark_call_clobbered (pi->name_mem_tag, pi->escape_mask);
+
+ if (v_ann->symbol_mem_tag)
+ mark_call_clobbered (v_ann->symbol_mem_tag, pi->escape_mask);
+
+ if (pi->pt_vars)
+ {
+ bitmap_iterator bi;
+ unsigned int j;
+ EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi)
+ if (!unmodifiable_var_p (referenced_var (j)))
+ mark_call_clobbered (referenced_var (j), pi->escape_mask);
+ }
+ }
+
+ /* If the name tag is call clobbered, so is the symbol tag
+ associated with the base VAR_DECL. */
+ if (pi->name_mem_tag
+ && v_ann->symbol_mem_tag
+ && is_call_clobbered (pi->name_mem_tag))
+ mark_call_clobbered (v_ann->symbol_mem_tag, pi->escape_mask);
+
+ /* Name tags and symbol tags that we don't know where they point
+ to, might point to global memory, and thus, are clobbered.
+
+ FIXME: This is not quite right. They should only be
+ clobbered if value_escapes_p is true, regardless of whether
+ they point to global memory or not.
+ So removing this code and fixing all the bugs would be nice.
+ It is the cause of a bunch of clobbering. */
+ if ((pi->pt_global_mem || pi->pt_anything)
+ && pi->is_dereferenced && pi->name_mem_tag)
+ {
+ mark_call_clobbered (pi->name_mem_tag, ESCAPE_IS_GLOBAL);
+ MTAG_GLOBAL (pi->name_mem_tag) = true;
+ }
+
+ if ((pi->pt_global_mem || pi->pt_anything)
+ && pi->is_dereferenced
+ && v_ann->symbol_mem_tag)
+ {
+ mark_call_clobbered (v_ann->symbol_mem_tag, ESCAPE_IS_GLOBAL);
+ MTAG_GLOBAL (v_ann->symbol_mem_tag) = true;
+ }
+ }
+}
+
+
+/* This variable is set to true if we are updating the used alone
+ information for SMTs, or are in a pass that is going to break it
+ temporarily. */
+bool updating_used_alone;
+
+/* Compute which variables need to be marked call clobbered because
+ their tag is call clobbered, and which tags need to be marked
+ global because they contain global variables. */
+
+static void
+compute_call_clobbered (struct alias_info *ai)
+{
+ VEC (tree, heap) *worklist = NULL;
+ VEC(int,heap) *worklist2 = NULL;
+
+ set_initial_properties (ai);
+ init_transitive_clobber_worklist (&worklist, &worklist2);
+ while (VEC_length (tree, worklist) != 0)
+ {
+ tree curr = VEC_pop (tree, worklist);
+ int reason = VEC_pop (int, worklist2);
+
+ mark_call_clobbered (curr, reason);
+ mark_aliases_call_clobbered (curr, &worklist, &worklist2);
+ }
+ VEC_free (tree, heap, worklist);
+ VEC_free (int, heap, worklist2);
+ compute_tag_properties ();
+}
+
+
+/* Helper for recalculate_used_alone. Return a conservatively correct
+ answer as to whether STMT may make a store on the LHS to SYM. */
+
+static bool
+lhs_may_store_to (tree stmt, tree sym ATTRIBUTE_UNUSED)
+{
+ tree lhs = TREE_OPERAND (stmt, 0);
+
+ lhs = get_base_address (lhs);
+
+ if (!lhs)
+ return false;
+
+ if (TREE_CODE (lhs) == SSA_NAME)
+ return false;
+ /* We could do better here by looking at the type tag of LHS, but it
+ is unclear whether this is worth it. */
+ return true;
+}
+
+/* Recalculate the used_alone information for SMTs . */
+
+void
+recalculate_used_alone (void)
+{
+ VEC (tree, heap) *calls = NULL;
+ block_stmt_iterator bsi;
+ basic_block bb;
+ tree stmt;
+ size_t i;
+ referenced_var_iterator rvi;
+ tree var;
+
+ /* First, reset all the SMT used alone bits to zero. */
+ updating_used_alone = true;
+ FOR_EACH_REFERENCED_VAR (var, rvi)
+ if (TREE_CODE (var) == SYMBOL_MEMORY_TAG)
+ {
+ SMT_OLD_USED_ALONE (var) = SMT_USED_ALONE (var);
+ SMT_USED_ALONE (var) = 0;
+ }
+
+ /* Walk all the statements.
+ Calls get put into a list of statements to update, since we will
+ need to update operands on them if we make any changes.
+ If we see a bare use of a SMT anywhere in a real virtual use or virtual
+ def, mark the SMT as used alone, and for renaming. */
+ FOR_EACH_BB (bb)
+ {
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ bool iscall = false;
+ ssa_op_iter iter;
+
+ stmt = bsi_stmt (bsi);
+
+ if (TREE_CODE (stmt) == CALL_EXPR
+ || (TREE_CODE (stmt) == MODIFY_EXPR
+ && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR))
+ {
+ iscall = true;
+ VEC_safe_push (tree, heap, calls, stmt);
+ }
+
+ FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter,
+ SSA_OP_VUSE | SSA_OP_VIRTUAL_DEFS)
+ {
+ tree svar = var;
+
+ if (TREE_CODE (var) == SSA_NAME)
+ svar = SSA_NAME_VAR (var);
+
+ if (TREE_CODE (svar) == SYMBOL_MEMORY_TAG)
+ {
+ /* We only care about the LHS on calls. */
+ if (iscall && !lhs_may_store_to (stmt, svar))
+ continue;
+
+ if (!SMT_USED_ALONE (svar))
+ {
+ SMT_USED_ALONE (svar) = true;
+
+ /* Only need to mark for renaming if it wasn't
+ used alone before. */
+ if (!SMT_OLD_USED_ALONE (svar))
+ mark_sym_for_renaming (svar);
+ }
+ }
+ }
+ }
+ }
+
+ /* Update the operands on all the calls we saw. */
+ if (calls)
+ {
+ for (i = 0; VEC_iterate (tree, calls, i, stmt); i++)
+ update_stmt (stmt);
+ }
+
+ /* We need to mark SMT's that are no longer used for renaming so the
+ symbols go away, or else verification will be angry with us, even
+ though they are dead. */
+ FOR_EACH_REFERENCED_VAR (var, rvi)
+ if (TREE_CODE (var) == SYMBOL_MEMORY_TAG)
+ {
+ if (SMT_OLD_USED_ALONE (var) && !SMT_USED_ALONE (var))
+ mark_sym_for_renaming (var);
+ }
+
+ VEC_free (tree, heap, calls);
+ updating_used_alone = false;
+}