-/* Return TRUE if S1 and S2 are equivalent copies. */
-
-static inline bool
-identical_copies_p (const_tree s1, const_tree s2)
-{
-#ifdef ENABLE_CHECKING
- gcc_assert (TREE_CODE (s1) == GIMPLE_MODIFY_STMT);
- gcc_assert (TREE_CODE (s2) == GIMPLE_MODIFY_STMT);
- gcc_assert (DECL_P (GIMPLE_STMT_OPERAND (s1, 0)));
- gcc_assert (DECL_P (GIMPLE_STMT_OPERAND (s2, 0)));
-#endif
-
- if (GIMPLE_STMT_OPERAND (s1, 0) != GIMPLE_STMT_OPERAND (s2, 0))
- return false;
-
- s1 = GIMPLE_STMT_OPERAND (s1, 1);
- s2 = GIMPLE_STMT_OPERAND (s2, 1);
-
- if (s1 != s2)
- return false;
-
- return true;
-}
-
-
-/* Compare the PENDING_STMT list for edges E1 and E2. Return true if the lists
- contain the same sequence of copies. */
-
-static inline bool
-identical_stmt_lists_p (const_edge e1, const_edge e2)
-{
- tree t1 = PENDING_STMT (e1);
- tree t2 = PENDING_STMT (e2);
- tree_stmt_iterator tsi1, tsi2;
-
- gcc_assert (TREE_CODE (t1) == STATEMENT_LIST);
- gcc_assert (TREE_CODE (t2) == STATEMENT_LIST);
-
- for (tsi1 = tsi_start (t1), tsi2 = tsi_start (t2);
- !tsi_end_p (tsi1) && !tsi_end_p (tsi2);
- tsi_next (&tsi1), tsi_next (&tsi2))
- {
- if (!identical_copies_p (tsi_stmt (tsi1), tsi_stmt (tsi2)))
- break;
- }
-
- if (!tsi_end_p (tsi1) || ! tsi_end_p (tsi2))
- return false;
-
- return true;
-}
-
-
-/* Allocate data structures used in analyze_edges_for_bb. */
-
-static void
-init_analyze_edges_for_bb (void)
-{
- edge_leader = VEC_alloc (edge, heap, 25);
- stmt_list = VEC_alloc (tree, heap, 25);
- leader_has_match = BITMAP_ALLOC (NULL);
-}
-
-
-/* Free data structures used in analyze_edges_for_bb. */
-
-static void
-fini_analyze_edges_for_bb (void)
-{
- VEC_free (edge, heap, edge_leader);
- VEC_free (tree, heap, stmt_list);
- BITMAP_FREE (leader_has_match);
-}
-
-/* A helper function to be called via walk_tree. Return DATA if it is
- contained in subtree TP. */
-
-static tree
-contains_tree_r (tree * tp, int *walk_subtrees, void *data)
-{
- if (*tp == data)
- {
- *walk_subtrees = 0;
- return data;
- }
- else
- return NULL_TREE;
-}
-
-/* A threshold for the number of insns contained in the latch block.
- It is used to prevent blowing the loop with too many copies from
- the latch. */
-#define MAX_STMTS_IN_LATCH 2
-
-/* Return TRUE if the stmts on SINGLE-EDGE can be moved to the
- body of the loop. This should be permitted only if SINGLE-EDGE is a
- single-basic-block latch edge and thus cleaning the latch will help
- to create a single-basic-block loop. Otherwise return FALSE. */
-
-static bool
-process_single_block_loop_latch (edge single_edge)
-{
- tree stmts;
- basic_block b_exit, b_pheader, b_loop = single_edge->src;
- edge_iterator ei;
- edge e;
- block_stmt_iterator bsi, bsi_exit;
- tree_stmt_iterator tsi;
- tree expr, stmt;
- unsigned int count = 0;
-
- if (single_edge == NULL || (single_edge->dest != single_edge->src)
- || (EDGE_COUNT (b_loop->succs) != 2)
- || (EDGE_COUNT (b_loop->preds) != 2))
- return false;
-
- /* Get the stmts on the latch edge. */
- stmts = PENDING_STMT (single_edge);
-
- /* Find the successor edge which is not the latch edge. */
- FOR_EACH_EDGE (e, ei, b_loop->succs)
- if (e->dest != b_loop)
- break;
-
- b_exit = e->dest;
-
- /* Check that the exit block has only the loop as a predecessor,
- and that there are no pending stmts on that edge as well. */
- if (EDGE_COUNT (b_exit->preds) != 1 || PENDING_STMT (e))
- return false;
-
- /* Find the predecessor edge which is not the latch edge. */
- FOR_EACH_EDGE (e, ei, b_loop->preds)
- if (e->src != b_loop)
- break;
-
- b_pheader = e->src;
-
- if (b_exit == b_pheader || b_exit == b_loop || b_pheader == b_loop)
- return false;
-
- bsi_exit = bsi_after_labels (b_exit);
-
- /* Get the last stmt in the loop body. */
- bsi = bsi_last (single_edge->src);
- stmt = bsi_stmt (bsi);
-
- if (TREE_CODE (stmt) != COND_EXPR)
- return false;
-
- expr = COND_EXPR_COND (stmt);
- /* Iterate over the insns on the latch and count them. */
- for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi))
- {
- tree stmt1 = tsi_stmt (tsi);
- tree var;
-
- count++;
- /* Check that the condition does not contain any new definition
- created in the latch as the stmts from the latch intended
- to precede it. */
- if (TREE_CODE (stmt1) != GIMPLE_MODIFY_STMT)
- return false;
- var = GIMPLE_STMT_OPERAND (stmt1, 0);
- if (TREE_THIS_VOLATILE (var)
- || TYPE_VOLATILE (TREE_TYPE (var))
- || walk_tree (&expr, contains_tree_r, var, NULL))
- return false;
- }
- /* Check that the latch does not contain more than MAX_STMTS_IN_LATCH
- insns. The purpose of this restriction is to prevent blowing the
- loop with too many copies from the latch. */
- if (count > MAX_STMTS_IN_LATCH)
- return false;
-
- /* Apply the transformation - clean up the latch block:
-
- var = something;
- L1:
- x1 = expr;
- if (cond) goto L2 else goto L3;
- L2:
- var = x1;
- goto L1
- L3:
- ...
-
- ==>
-
- var = something;
- L1:
- x1 = expr;
- tmp_var = var;
- var = x1;
- if (cond) goto L1 else goto L2;
- L2:
- var = tmp_var;
- ...
- */
- for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi))
- {
- tree stmt1 = tsi_stmt (tsi);
- tree var, tmp_var, copy;
-
- /* Create a new variable to load back the value of var in case
- we exit the loop. */
- var = GIMPLE_STMT_OPERAND (stmt1, 0);
- tmp_var = create_temp (var);
- copy = build2 (GIMPLE_MODIFY_STMT, TREE_TYPE (tmp_var), tmp_var, var);
- set_is_used (tmp_var);
- bsi_insert_before (&bsi, copy, BSI_SAME_STMT);
- copy = build2 (GIMPLE_MODIFY_STMT, TREE_TYPE (tmp_var), var, tmp_var);
- bsi_insert_before (&bsi_exit, copy, BSI_SAME_STMT);
- }
-
- PENDING_STMT (single_edge) = 0;
- /* Insert the new stmts to the loop body. */
- bsi_insert_before (&bsi, stmts, BSI_NEW_STMT);
-
- if (dump_file)
- fprintf (dump_file,
- "\nCleaned-up latch block of loop with single BB: %d\n\n",
- single_edge->dest->index);
-
- return true;
-}
-
-/* Look at all the incoming edges to block BB, and decide where the best place
- to insert the stmts on each edge are, and perform those insertions. */
-
-static void
-analyze_edges_for_bb (basic_block bb)
-{
- edge e;
- edge_iterator ei;
- int count;
- unsigned int x;
- bool have_opportunity;
- block_stmt_iterator bsi;
- tree stmt;
- edge single_edge = NULL;
- bool is_label;
- edge leader;
-
- count = 0;
-
- /* Blocks which contain at least one abnormal edge cannot use
- make_forwarder_block. Look for these blocks, and commit any PENDING_STMTs
- found on edges in these block. */
- have_opportunity = true;
- FOR_EACH_EDGE (e, ei, bb->preds)
- if (e->flags & EDGE_ABNORMAL)
- {
- have_opportunity = false;
- break;
- }
-
- if (!have_opportunity)
- {
- FOR_EACH_EDGE (e, ei, bb->preds)
- if (PENDING_STMT (e))
- bsi_commit_one_edge_insert (e, NULL);
- return;
- }
-
- /* Find out how many edges there are with interesting pending stmts on them.
- Commit the stmts on edges we are not interested in. */
- FOR_EACH_EDGE (e, ei, bb->preds)
- {
- if (PENDING_STMT (e))
- {
- gcc_assert (!(e->flags & EDGE_ABNORMAL));
- if (e->flags & EDGE_FALLTHRU)
- {
- bsi = bsi_start (e->src);
- if (!bsi_end_p (bsi))
- {
- stmt = bsi_stmt (bsi);
- bsi_next (&bsi);
- gcc_assert (stmt != NULL_TREE);
- is_label = (TREE_CODE (stmt) == LABEL_EXPR);
- /* Punt if it has non-label stmts, or isn't local. */
- if (!is_label || DECL_NONLOCAL (TREE_OPERAND (stmt, 0))
- || !bsi_end_p (bsi))
- {
- bsi_commit_one_edge_insert (e, NULL);
- continue;
- }
- }
- }
- single_edge = e;
- count++;
- }
- }
-
- /* If there aren't at least 2 edges, no sharing will happen. */
- if (count < 2)
- {
- if (single_edge)
- {
- /* Add stmts to the edge unless processed specially as a
- single-block loop latch edge. */
- if (!process_single_block_loop_latch (single_edge))
- bsi_commit_one_edge_insert (single_edge, NULL);
- }
- return;
- }
-
- /* Ensure that we have empty worklists. */
-#ifdef ENABLE_CHECKING
- gcc_assert (VEC_length (edge, edge_leader) == 0);
- gcc_assert (VEC_length (tree, stmt_list) == 0);
- gcc_assert (bitmap_empty_p (leader_has_match));
-#endif
-
- /* Find the "leader" block for each set of unique stmt lists. Preference is
- given to FALLTHRU blocks since they would need a GOTO to arrive at another
- block. The leader edge destination is the block which all the other edges
- with the same stmt list will be redirected to. */
- have_opportunity = false;
- FOR_EACH_EDGE (e, ei, bb->preds)
- {
- if (PENDING_STMT (e))
- {
- bool found = false;
-
- /* Look for the same stmt list in edge leaders list. */
- for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
- {
- if (identical_stmt_lists_p (leader, e))
- {
- /* Give this edge the same stmt list pointer. */
- PENDING_STMT (e) = NULL;
- e->aux = leader;
- bitmap_set_bit (leader_has_match, x);
- have_opportunity = found = true;
- break;
- }
- }
-
- /* If no similar stmt list, add this edge to the leader list. */
- if (!found)
- {
- VEC_safe_push (edge, heap, edge_leader, e);
- VEC_safe_push (tree, heap, stmt_list, PENDING_STMT (e));
- }
- }
- }
-
- /* If there are no similar lists, just issue the stmts. */
- if (!have_opportunity)
- {
- for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
- bsi_commit_one_edge_insert (leader, NULL);
- VEC_truncate (edge, edge_leader, 0);
- VEC_truncate (tree, stmt_list, 0);
- bitmap_clear (leader_has_match);
- return;
- }
-
- if (dump_file)
- fprintf (dump_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
- bb->index);
-
- /* For each common list, create a forwarding block and issue the stmt's
- in that block. */
- for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
- if (bitmap_bit_p (leader_has_match, x))
- {
- edge new_edge;
- block_stmt_iterator bsi;
- tree curr_stmt_list;
-
- leader_match = leader;
-
- /* The tree_* cfg manipulation routines use the PENDING_EDGE field
- for various PHI manipulations, so it gets cleared when calls are
- made to make_forwarder_block(). So make sure the edge is clear,
- and use the saved stmt list. */
- PENDING_STMT (leader) = NULL;
- leader->aux = leader;
- curr_stmt_list = VEC_index (tree, stmt_list, x);
-
- new_edge = make_forwarder_block (leader->dest, same_stmt_list_p,
- NULL);
- bb = new_edge->dest;
- if (dump_file)
- {
- fprintf (dump_file, "Splitting BB %d for Common stmt list. ",
- leader->dest->index);
- fprintf (dump_file, "Original block is now BB%d.\n", bb->index);
- print_generic_stmt (dump_file, curr_stmt_list, TDF_VOPS);
- }
-
- FOR_EACH_EDGE (e, ei, new_edge->src->preds)
- {
- e->aux = NULL;
- if (dump_file)
- fprintf (dump_file, " Edge (%d->%d) lands here.\n",
- e->src->index, e->dest->index);
- }
-
- bsi = bsi_last (leader->dest);
- bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT);
-
- leader_match = NULL;
- /* We should never get a new block now. */
- }
- else
- {
- PENDING_STMT (leader) = VEC_index (tree, stmt_list, x);
- bsi_commit_one_edge_insert (leader, NULL);
- }
-
-
- /* Clear the working data structures. */
- VEC_truncate (edge, edge_leader, 0);
- VEC_truncate (tree, stmt_list, 0);
- bitmap_clear (leader_has_match);
-}
-
-
-/* This function will analyze the insertions which were performed on edges,
- and decide whether they should be left on that edge, or whether it is more
- efficient to emit some subset of them in a single block. All stmts are
- inserted somewhere. */
-
-static void
-perform_edge_inserts (void)