From e6a7da82a98953d0c817367d410ccb080861b7da Mon Sep 17 00:00:00 2001 From: Steven Bosscher Date: Thu, 11 Oct 2012 18:54:47 +0000 Subject: ira-build.c (ira_loop_tree_body_rev_postorder): New function. * ira-build.c (ira_loop_tree_body_rev_postorder): New function. (ira_traverse_loop_tree): Traverse a loop's basic blocks in reverse post-order of the reversed control-flow direction. * ira-conflicts.c (ira_build_conflicts): Pass add_copies as the pre-order function to ira_traverse_loop_tree to preserve the existing semantics. * ira-lives.c (remove_some_program_points_and_update_live_ranges): Squeeze out live range chain elements if their program points are connected. From-SVN: r192378 --- gcc/ira-build.c | 136 ++++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 127 insertions(+), 9 deletions(-) (limited to 'gcc/ira-build.c') diff --git a/gcc/ira-build.c b/gcc/ira-build.c index 1181813..cc4ff34 100644 --- a/gcc/ira-build.c +++ b/gcc/ira-build.c @@ -1458,6 +1458,96 @@ finish_cost_vectors (void) +/* Compute a post-ordering of the reverse control flow of the loop body + designated by the children nodes of LOOP_NODE, whose body nodes in + pre-order are input as LOOP_PREORDER. Return a VEC with a post-order + of the reverse loop body. + + For the post-order of the reverse CFG, we visit the basic blocks in + LOOP_PREORDER array in the reverse order of where they appear. + This is important: We do not just want to compute a post-order of + the reverse CFG, we want to make a best-guess for a visiting order that + minimizes the number of chain elements per allocno live range. If the + blocks would be visited in a different order, we would still compute a + correct post-ordering but it would be less likely that two nodes + connected by an edge in the CFG are neighbours in the topsort. */ + +static VEC (ira_loop_tree_node_t, heap) * +ira_loop_tree_body_rev_postorder (ira_loop_tree_node_t loop_node ATTRIBUTE_UNUSED, + VEC (ira_loop_tree_node_t, heap) *loop_preorder) +{ + VEC (ira_loop_tree_node_t, heap) *topsort_nodes = NULL; + unsigned int n_loop_preorder; + + n_loop_preorder = VEC_length (ira_loop_tree_node_t, loop_preorder); + if (n_loop_preorder != 0) + { + ira_loop_tree_node_t subloop_node; + unsigned int i; + VEC (ira_loop_tree_node_t, heap) *dfs_stack; + + /* This is a bit of strange abuse of the BB_VISITED flag: We use + the flag to mark blocks we still have to visit to add them to + our post-order. Define an alias to avoid confusion. */ +#define BB_TO_VISIT BB_VISITED + + FOR_EACH_VEC_ELT (ira_loop_tree_node_t, loop_preorder, i, subloop_node) + { + gcc_checking_assert (! (subloop_node->bb->flags & BB_TO_VISIT)); + subloop_node->bb->flags |= BB_TO_VISIT; + } + + topsort_nodes = VEC_alloc (ira_loop_tree_node_t, heap, n_loop_preorder); + dfs_stack = VEC_alloc (ira_loop_tree_node_t, heap, n_loop_preorder); + + FOR_EACH_VEC_ELT_REVERSE (ira_loop_tree_node_t, loop_preorder, + i, subloop_node) + { + if (! (subloop_node->bb->flags & BB_TO_VISIT)) + continue; + + subloop_node->bb->flags &= ~BB_TO_VISIT; + VEC_quick_push (ira_loop_tree_node_t, dfs_stack, subloop_node); + while (! VEC_empty (ira_loop_tree_node_t, dfs_stack)) + { + edge e; + edge_iterator ei; + + ira_loop_tree_node_t n = VEC_last (ira_loop_tree_node_t, + dfs_stack); + FOR_EACH_EDGE (e, ei, n->bb->preds) + { + ira_loop_tree_node_t pred_node; + basic_block pred_bb = e->src; + + if (e->src == ENTRY_BLOCK_PTR) + continue; + + pred_node = IRA_BB_NODE_BY_INDEX (pred_bb->index); + if (pred_node != n + && (pred_node->bb->flags & BB_TO_VISIT)) + { + pred_node->bb->flags &= ~BB_TO_VISIT; + VEC_quick_push (ira_loop_tree_node_t, dfs_stack, pred_node); + } + } + if (n == VEC_last (ira_loop_tree_node_t, dfs_stack)) + { + VEC_pop (ira_loop_tree_node_t, dfs_stack); + VEC_quick_push (ira_loop_tree_node_t, topsort_nodes, n); + } + } + } + +#undef BB_TO_VISIT + VEC_free (ira_loop_tree_node_t, heap, dfs_stack); + } + + gcc_assert (VEC_length (ira_loop_tree_node_t, topsort_nodes) + == n_loop_preorder); + return topsort_nodes; +} + /* The current loop tree node and its regno allocno map. */ ira_loop_tree_node_t ira_curr_loop_tree_node; ira_allocno_t *ira_curr_regno_allocno_map; @@ -1467,7 +1557,16 @@ ira_allocno_t *ira_curr_regno_allocno_map; correspondingly in preorder and postorder. The function sets up IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP. If BB_P, basic block nodes of LOOP_NODE is also processed (before its - subloop nodes). */ + subloop nodes). + + If BB_P is set and POSTORDER_FUNC is given, the basic blocks in + the loop are passed in the *reverse* post-order of the *reverse* + CFG. This is only used by ira_create_allocno_live_ranges, which + wants to visit basic blocks in this order to minimize the number + of elements per live range chain. + Note that the loop tree nodes are still visited in the normal, + forward post-order of the loop tree. */ + void ira_traverse_loop_tree (bool bb_p, ira_loop_tree_node_t loop_node, void (*preorder_func) (ira_loop_tree_node_t), @@ -1483,18 +1582,37 @@ ira_traverse_loop_tree (bool bb_p, ira_loop_tree_node_t loop_node, (*preorder_func) (loop_node); if (bb_p) - for (subloop_node = loop_node->children; - subloop_node != NULL; - subloop_node = subloop_node->next) - if (subloop_node->bb != NULL) - { - if (preorder_func != NULL) - (*preorder_func) (subloop_node); + { + VEC (ira_loop_tree_node_t, heap) *loop_preorder = NULL; + unsigned int i; + + /* Add all nodes to the set of nodes to visit. The IRA loop tree + is set up such that nodes in the loop body appear in a pre-order + of their place in the CFG. */ + for (subloop_node = loop_node->children; + subloop_node != NULL; + subloop_node = subloop_node->next) + if (subloop_node->bb != NULL) + VEC_safe_push (ira_loop_tree_node_t, heap, + loop_preorder, subloop_node); + + if (preorder_func != NULL) + FOR_EACH_VEC_ELT (ira_loop_tree_node_t, loop_preorder, i, subloop_node) + (*preorder_func) (subloop_node); - if (postorder_func != NULL) + if (postorder_func != NULL) + { + VEC (ira_loop_tree_node_t, heap) *loop_rev_postorder = + ira_loop_tree_body_rev_postorder (loop_node, loop_preorder); + FOR_EACH_VEC_ELT_REVERSE (ira_loop_tree_node_t, loop_rev_postorder, + i, subloop_node) (*postorder_func) (subloop_node); + VEC_free (ira_loop_tree_node_t, heap, loop_rev_postorder); } + VEC_free (ira_loop_tree_node_t, heap, loop_preorder); + } + for (subloop_node = loop_node->subloops; subloop_node != NULL; subloop_node = subloop_node->subloop_next) -- cgit v1.1