-/* If VAR is defined in LOOP and the statement it is defined in does not belong
- to the set SEEN, add the statement to QUEUE of length IN_QUEUE and
- to the set SEEN. */
-
-static void
-maybe_queue_var (tree var, struct loop *loop,
- sbitmap seen, tree *queue, unsigned *in_queue)
-{
- tree stmt = SSA_NAME_DEF_STMT (var);
- basic_block def_bb = bb_for_stmt (stmt);
-
- if (!def_bb
- || !flow_bb_inside_loop_p (loop, def_bb)
- || TEST_BIT (seen, get_stmt_uid (stmt)))
- return;
-
- SET_BIT (seen, get_stmt_uid (stmt));
- queue[(*in_queue)++] = stmt;
-}
-
-/* If COMMON_REF is NULL, set COMMON_REF to *OP and return true.
- Otherwise return true if the memory reference *OP is equal to COMMON_REF.
- Record the reference OP to list MEM_REFS. STMT is the statement in that
- the reference occurs. */
-
-struct sra_data
-{
- struct mem_ref **mem_refs;
- tree common_ref;
- tree stmt;
-};
-
-static bool
-fem_single_reachable_address (tree *op, void *data)
-{
- struct sra_data *sra_data = data;
-
- if (sra_data->common_ref
- && !operand_equal_p (*op, sra_data->common_ref, 0))
- return false;
- sra_data->common_ref = *op;
-
- record_mem_ref (sra_data->mem_refs, sra_data->stmt, op);
- return true;
-}
-
-/* Runs CALLBACK for each operand of STMT that is a memory reference. DATA
- is passed to the CALLBACK as well. The traversal stops if CALLBACK
- returns false, for_each_memref then returns false as well. Otherwise
- for_each_memref returns true. */
-
-static bool
-for_each_memref (tree stmt, bool (*callback)(tree *, void *), void *data)
-{
- tree *op;
-
- if (TREE_CODE (stmt) == RETURN_EXPR)
- stmt = TREE_OPERAND (stmt, 1);
-
- if (TREE_CODE (stmt) == MODIFY_EXPR)
- {
- op = &TREE_OPERAND (stmt, 0);
- if (TREE_CODE (*op) != SSA_NAME
- && !callback (op, data))
- return false;
-
- op = &TREE_OPERAND (stmt, 1);
- if (TREE_CODE (*op) != SSA_NAME
- && is_gimple_lvalue (*op)
- && !callback (op, data))
- return false;
-
- stmt = TREE_OPERAND (stmt, 1);
- }
-
- if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
- stmt = TREE_OPERAND (stmt, 0);
-
- if (TREE_CODE (stmt) == CALL_EXPR)
- {
- tree args;
-
- for (args = TREE_OPERAND (stmt, 1); args; args = TREE_CHAIN (args))
- {
- op = &TREE_VALUE (args);
-
- if (TREE_CODE (*op) != SSA_NAME
- && is_gimple_lvalue (*op)
- && !callback (op, data))
- return false;
- }
- }
-
- return true;
-}
-
-/* Determine whether all memory references inside the LOOP that correspond
- to virtual ssa names defined in statement STMT are equal.
- If so, store the list of the references to MEM_REFS, and return one
- of them. Otherwise store NULL to MEM_REFS and return NULL_TREE.
- *SEEN_CALL_STMT is set to true if the virtual operands suggest
- that the reference might be clobbered by a call inside the LOOP. */
-
-static tree
-single_reachable_address (struct loop *loop, tree stmt,
- struct mem_ref **mem_refs,
- bool *seen_call_stmt)
-{
- unsigned max_uid = max_stmt_uid + num_ssa_names;
- tree *queue = xmalloc (sizeof (tree) * max_uid);
- sbitmap seen = sbitmap_alloc (max_uid);
- unsigned in_queue = 1;
- dataflow_t df;
- unsigned i, n;
- struct sra_data sra_data;
- tree call;
- tree val;
- ssa_op_iter iter;
-
- sbitmap_zero (seen);
-
- *mem_refs = NULL;
- sra_data.mem_refs = mem_refs;
- sra_data.common_ref = NULL_TREE;
-
- queue[0] = stmt;
- SET_BIT (seen, get_stmt_uid (stmt));
- *seen_call_stmt = false;
-
- while (in_queue)
- {
- stmt = queue[--in_queue];
- sra_data.stmt = stmt;
-
- if (LIM_DATA (stmt)
- && LIM_DATA (stmt)->sm_done)
- goto fail;
-
- switch (TREE_CODE (stmt))
- {
- case MODIFY_EXPR:
- case CALL_EXPR:
- case RETURN_EXPR:
- if (!for_each_memref (stmt, fem_single_reachable_address,
- &sra_data))
- goto fail;
-
- /* If this is a function that may depend on the memory location,
- record the fact. We cannot directly refuse call clobbered
- operands here, since sra_data.common_ref did not have
- to be set yet. */
- call = get_call_expr_in (stmt);
- if (call
- && !(call_expr_flags (call) & ECF_CONST))
- *seen_call_stmt = true;
-
- /* Traverse also definitions of the VUSES (there may be other
- distinct from the one we used to get to this statement). */
- FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_VIRTUAL_USES)
- maybe_queue_var (val, loop, seen, queue, &in_queue);
-
- break;
-
- case PHI_NODE:
- for (i = 0; i < (unsigned) PHI_NUM_ARGS (stmt); i++)
- if (TREE_CODE (PHI_ARG_DEF (stmt, i)) == SSA_NAME)
- maybe_queue_var (PHI_ARG_DEF (stmt, i), loop,
- seen, queue, &in_queue);
- break;
-
- default:
- goto fail;
- }
-
- /* Find uses of virtual names. */
- df = get_immediate_uses (stmt);
- n = num_immediate_uses (df);
-
- for (i = 0; i < n; i++)
- {
- stmt = immediate_use (df, i);
-
- if (!flow_bb_inside_loop_p (loop, bb_for_stmt (stmt)))
- continue;
-
- if (TEST_BIT (seen, get_stmt_uid (stmt)))
- continue;
- SET_BIT (seen, get_stmt_uid (stmt));
-
- queue[in_queue++] = stmt;
- }
- }
-
- free (queue);
- sbitmap_free (seen);
-
- return sra_data.common_ref;
-
-fail:
- free_mem_refs (*mem_refs);
- *mem_refs = NULL;
- free (queue);
- sbitmap_free (seen);
-
- return NULL;
-}
-