From 076b460557487a225815e3870405e67a3f149a0c Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Mon, 18 Mar 2013 08:46:44 +0000 Subject: [PATCH] re PR c/56113 (out of memory when compiling a function with many goto labels (50k > )) 2013-03-18 Richard Biener PR middle-end/56113 * domwalk.c (bb_postorder): New global static. (cmp_bb_postorder): New function. (walk_dominator_tree): Replace scheme imposing an order for visiting dominator sons by one sorting them at the time they are pushed on the stack. From-SVN: r196769 --- gcc/ChangeLog | 9 ++++++ gcc/domwalk.c | 82 +++++++++++++++++++++++++++------------------------ 2 files changed, 52 insertions(+), 39 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 629ae5ae0fa7..631ee729e629 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,12 @@ +2013-03-18 Richard Biener + + PR middle-end/56113 + * domwalk.c (bb_postorder): New global static. + (cmp_bb_postorder): New function. + (walk_dominator_tree): Replace scheme imposing an order for + visiting dominator sons by one sorting them at the time they + are pushed on the stack. + 2013-03-18 Richard Biener PR tree-optimization/39326 diff --git a/gcc/domwalk.c b/gcc/domwalk.c index 4a8ed26d3ba5..8c1ddc694907 100644 --- a/gcc/domwalk.c +++ b/gcc/domwalk.c @@ -128,6 +128,21 @@ along with GCC; see the file COPYING3. If not see which is currently an abstraction over walking tree statements. Thus the dominator walker is currently only useful for trees. */ +static int *bb_postorder; + +static int +cmp_bb_postorder (const void *a, const void *b) +{ + basic_block bb1 = *(basic_block *)const_cast(a); + basic_block bb2 = *(basic_block *)const_cast(b); + if (bb1->index == bb2->index) + return 0; + /* Place higher completion number first (pop off lower number first). */ + if (bb_postorder[bb1->index] > bb_postorder[bb2->index]) + return -1; + return 1; +} + /* Recursively walk the dominator tree. WALK_DATA contains a set of callbacks to perform pass-specific @@ -143,9 +158,17 @@ walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb) basic_block dest; basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2); int sp = 0; - sbitmap visited = sbitmap_alloc (last_basic_block + 1); - bitmap_clear (visited); - bitmap_set_bit (visited, ENTRY_BLOCK_PTR->index); + int *postorder, postorder_num; + + if (walk_data->dom_direction == CDI_DOMINATORS) + { + postorder = XNEWVEC (int, n_basic_blocks); + postorder_num = inverted_post_order_compute (postorder); + bb_postorder = XNEWVEC (int, last_basic_block); + for (int i = 0; i < postorder_num; ++i) + bb_postorder[postorder[i]] = i; + free (postorder); + } while (true) { @@ -186,16 +209,25 @@ walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb) if (walk_data->before_dom_children) (*walk_data->before_dom_children) (walk_data, bb); - bitmap_set_bit (visited, bb->index); - /* Mark the current BB to be popped out of the recursion stack once children are processed. */ worklist[sp++] = bb; worklist[sp++] = NULL; + int saved_sp = sp; for (dest = first_dom_son (walk_data->dom_direction, bb); dest; dest = next_dom_son (walk_data->dom_direction, dest)) worklist[sp++] = dest; + if (walk_data->dom_direction == CDI_DOMINATORS) + switch (sp - saved_sp) + { + case 0: + case 1: + break; + default: + qsort (&worklist[saved_sp], sp - saved_sp, + sizeof (basic_block), cmp_bb_postorder); + } } /* NULL is used to mark pop operations in the recursion stack. */ while (sp > 0 && !worklist[sp - 1]) @@ -217,44 +249,16 @@ walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb) } } if (sp) - { - int spp; - spp = sp - 1; - if (walk_data->dom_direction == CDI_DOMINATORS) - /* Find the dominator son that has all its predecessors - visited and continue with that. */ - while (1) - { - edge_iterator ei; - edge e; - bool found = true; - bb = worklist[spp]; - FOR_EACH_EDGE (e, ei, bb->preds) - { - if (!dominated_by_p (CDI_DOMINATORS, e->src, e->dest) - && !bitmap_bit_p (visited, e->src->index)) - { - found = false; - break; - } - } - if (found) - break; - /* If we didn't find a dom child with all visited - predecessors just use the candidate we were checking. - This happens for candidates in irreducible loops. */ - if (!worklist[spp - 1]) - break; - --spp; - } - bb = worklist[spp]; - worklist[spp] = worklist[--sp]; - } + bb = worklist[--sp]; else break; } + if (walk_data->dom_direction == CDI_DOMINATORS) + { + free (bb_postorder); + bb_postorder = NULL; + } free (worklist); - sbitmap_free (visited); } void -- 2.43.5