* [PATCH] Speed up LC SSA rewrite
@ 2022-07-07 7:05 Richard Biener
0 siblings, 0 replies; 3+ messages in thread
From: Richard Biener @ 2022-07-07 7:05 UTC (permalink / raw)
To: gcc-patches
The following avoids collecting all loops exit blocks into bitmaps
and computing the union of those up the loop tree possibly repeatedly.
Instead we make sure to do this only once for each loop with a
definition possibly requiring a LC phi node plus make sure to
leverage recorded exits to avoid the intermediate bitmap allocation.
Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.
* tree-ssa-loop-manip.cc (compute_live_loop_exits): Take
the def loop exit block bitmap as argument instead of
re-computing it here.
(add_exit_phis_var): Adjust.
(loop_name_cmp): New function.
(add_exit_phis): Sort variables to insert LC PHI nodes
after definition loop, for each definition loop compute
the exit block bitmap once.
(get_loops_exit): Remove.
(rewrite_into_loop_closed_ssa_1): Do not pre-record
all loop exit blocks into bitmaps. Record loop exits
if required.
---
gcc/tree-ssa-loop-manip.cc | 95 ++++++++++++++++++++++----------------
1 file changed, 56 insertions(+), 39 deletions(-)
diff --git a/gcc/tree-ssa-loop-manip.cc b/gcc/tree-ssa-loop-manip.cc
index 9f3b62652ea..0324ff60a0f 100644
--- a/gcc/tree-ssa-loop-manip.cc
+++ b/gcc/tree-ssa-loop-manip.cc
@@ -183,12 +183,14 @@ find_sibling_superloop (class loop *use_loop, class loop *def_loop)
/* DEF_BB is a basic block containing a DEF that needs rewriting into
loop-closed SSA form. USE_BLOCKS is the set of basic blocks containing
uses of DEF that "escape" from the loop containing DEF_BB (i.e. blocks in
- USE_BLOCKS are dominated by DEF_BB but not in the loop father of DEF_B).
+ USE_BLOCKS are dominated by DEF_BB but not in the loop father of DEF_BB).
ALL_EXITS[I] is the set of all basic blocks that exit loop I.
+ DEF_LOOP_EXITS is a bitmap of loop exit blocks that exit the loop
+ containing DEF_BB or its outer loops.
- Compute the subset of LOOP_EXITS that exit the loop containing DEF_BB
- or one of its loop fathers, in which DEF is live. This set is returned
- in the bitmap LIVE_EXITS.
+ Compute the subset of loop exit destinations that exit the loop
+ containing DEF_BB or one of its loop fathers, in which DEF is live.
+ This set is returned in the bitmap LIVE_EXITS.
Instead of computing the complete livein set of the def, we use the loop
nesting tree as a form of poor man's structure analysis. This greatly
@@ -197,18 +199,17 @@ find_sibling_superloop (class loop *use_loop, class loop *def_loop)
static void
compute_live_loop_exits (bitmap live_exits, bitmap use_blocks,
- bitmap *loop_exits, basic_block def_bb)
+ basic_block def_bb, bitmap def_loop_exits)
{
unsigned i;
bitmap_iterator bi;
class loop *def_loop = def_bb->loop_father;
unsigned def_loop_depth = loop_depth (def_loop);
- bitmap def_loop_exits;
/* Normally the work list size is bounded by the number of basic
blocks in the largest loop. We don't know this number, but we
can be fairly sure that it will be relatively small. */
- auto_vec<basic_block> worklist (MAX (8, n_basic_blocks_for_fn (cfun) / 128));
+ auto_vec<basic_block, 8> worklist (MAX (8, n_basic_blocks_for_fn (cfun) / 128));
EXECUTE_IF_SET_IN_BITMAP (use_blocks, 0, i, bi)
{
@@ -272,13 +273,7 @@ compute_live_loop_exits (bitmap live_exits, bitmap use_blocks,
}
}
- def_loop_exits = BITMAP_ALLOC (&loop_renamer_obstack);
- for (class loop *loop = def_loop;
- loop != current_loops->tree_root;
- loop = loop_outer (loop))
- bitmap_ior_into (def_loop_exits, loop_exits[loop->num]);
bitmap_and_into (live_exits, def_loop_exits);
- BITMAP_FREE (def_loop_exits);
}
/* Add a loop-closing PHI for VAR in basic block EXIT. */
@@ -322,23 +317,33 @@ add_exit_phi (basic_block exit, tree var)
Exits of the loops are stored in LOOP_EXITS. */
static void
-add_exit_phis_var (tree var, bitmap use_blocks, bitmap *loop_exits)
+add_exit_phis_var (tree var, bitmap use_blocks, bitmap def_loop_exits)
{
unsigned index;
bitmap_iterator bi;
basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
- bitmap live_exits = BITMAP_ALLOC (&loop_renamer_obstack);
gcc_checking_assert (! bitmap_bit_p (use_blocks, def_bb->index));
- compute_live_loop_exits (live_exits, use_blocks, loop_exits, def_bb);
+ auto_bitmap live_exits (&loop_renamer_obstack);
+ compute_live_loop_exits (live_exits, use_blocks, def_bb, def_loop_exits);
EXECUTE_IF_SET_IN_BITMAP (live_exits, 0, index, bi)
{
add_exit_phi (BASIC_BLOCK_FOR_FN (cfun, index), var);
}
+}
- BITMAP_FREE (live_exits);
+static int
+loop_name_cmp (const void *p1, const void *p2)
+{
+ auto l1 = (const std::pair<int, int> *)p1;
+ auto l2 = (const std::pair<int, int> *)p2;
+ if (l1->first < l2->first)
+ return -1;
+ else if (l1->first > l2->first)
+ return 1;
+ return 0;
}
/* Add exit phis for the names marked in NAMES_TO_RENAME.
@@ -346,31 +351,38 @@ add_exit_phis_var (tree var, bitmap use_blocks, bitmap *loop_exits)
names are used are stored in USE_BLOCKS. */
static void
-add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap *loop_exits)
+add_exit_phis (bitmap names_to_rename, bitmap *use_blocks)
{
unsigned i;
bitmap_iterator bi;
+ /* Sort names_to_rename after definition loop so we can avoid re-computing
+ def_loop_exits. */
+ auto_vec<std::pair<int, int> > names (bitmap_count_bits (names_to_rename));
EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
{
- add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
+ tree name = ssa_name (i);
+ loop_p def_loop = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father;
+ names.quick_push (std::make_pair (def_loop->num, i));
}
-}
+ names.qsort (loop_name_cmp);
-/* Fill the array of bitmaps LOOP_EXITS with all loop exit edge targets. */
-
-static void
-get_loops_exits (bitmap *loop_exits)
-{
- unsigned j;
- edge e;
-
- for (auto loop : loops_list (cfun, 0))
+ auto_bitmap def_loop_exits (&loop_renamer_obstack);
+ loop_p last_def_loop = NULL;
+ for (auto p : names)
{
- auto_vec<edge> exit_edges = get_loop_exit_edges (loop);
- loop_exits[loop->num] = BITMAP_ALLOC (&loop_renamer_obstack);
- FOR_EACH_VEC_ELT (exit_edges, j, e)
- bitmap_set_bit (loop_exits[loop->num], e->dest->index);
+ loop_p def_loop = get_loop (cfun, p.first);
+ if (def_loop != last_def_loop)
+ {
+ bitmap_clear (def_loop_exits);
+ last_def_loop = def_loop;
+ for (class loop *loop = def_loop; loop != current_loops->tree_root;
+ loop = loop_outer (loop))
+ for (auto exit = loop->exits->next; exit->e; exit = exit->next)
+ bitmap_set_bit (def_loop_exits, exit->e->dest->index);
+ }
+ add_exit_phis_var (ssa_name (p.second), use_blocks[p.second],
+ def_loop_exits);
}
}
@@ -566,16 +578,21 @@ rewrite_into_loop_closed_ssa_1 (bitmap changed_bbs, unsigned update_flag,
if (!bitmap_empty_p (names_to_rename))
{
- /* An array of bitmaps where LOOP_EXITS[I] is the set of basic blocks
- that are the destination of an edge exiting loop number I. */
- bitmap *loop_exits = XNEWVEC (bitmap, number_of_loops (cfun));
- get_loops_exits (loop_exits);
+ bool release_recorded_exits_p = false;
+ if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
+ {
+ /* Doing one scan over the whole function is cheaper than
+ traversing the loop tree and gathering BBs of each loop. */
+ record_loop_exits ();
+ release_recorded_exits_p = true;
+ }
/* Add the PHI nodes on exits of the loops for the names we need to
rewrite. */
- add_exit_phis (names_to_rename, use_blocks, loop_exits);
+ add_exit_phis (names_to_rename, use_blocks);
- free (loop_exits);
+ if (release_recorded_exits_p)
+ release_recorded_exits (cfun);
/* Fix up all the names found to be used outside their original
loops. */
--
2.35.3
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH] Speed up LC SSA rewrite
@ 2022-07-07 7:05 Richard Biener
0 siblings, 0 replies; 3+ messages in thread
From: Richard Biener @ 2022-07-07 7:05 UTC (permalink / raw)
To: gcc-patches
The following avoids collecting all loops exit blocks into bitmaps
and computing the union of those up the loop tree possibly repeatedly.
Instead we make sure to do this only once for each loop with a
definition possibly requiring a LC phi node plus make sure to
leverage recorded exits to avoid the intermediate bitmap allocation.
Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.
* tree-ssa-loop-manip.cc (compute_live_loop_exits): Take
the def loop exit block bitmap as argument instead of
re-computing it here.
(add_exit_phis_var): Adjust.
(loop_name_cmp): New function.
(add_exit_phis): Sort variables to insert LC PHI nodes
after definition loop, for each definition loop compute
the exit block bitmap once.
(get_loops_exit): Remove.
(rewrite_into_loop_closed_ssa_1): Do not pre-record
all loop exit blocks into bitmaps. Record loop exits
if required.
---
gcc/tree-ssa-loop-manip.cc | 95 ++++++++++++++++++++++----------------
1 file changed, 56 insertions(+), 39 deletions(-)
diff --git a/gcc/tree-ssa-loop-manip.cc b/gcc/tree-ssa-loop-manip.cc
index 9f3b62652ea..0324ff60a0f 100644
--- a/gcc/tree-ssa-loop-manip.cc
+++ b/gcc/tree-ssa-loop-manip.cc
@@ -183,12 +183,14 @@ find_sibling_superloop (class loop *use_loop, class loop *def_loop)
/* DEF_BB is a basic block containing a DEF that needs rewriting into
loop-closed SSA form. USE_BLOCKS is the set of basic blocks containing
uses of DEF that "escape" from the loop containing DEF_BB (i.e. blocks in
- USE_BLOCKS are dominated by DEF_BB but not in the loop father of DEF_B).
+ USE_BLOCKS are dominated by DEF_BB but not in the loop father of DEF_BB).
ALL_EXITS[I] is the set of all basic blocks that exit loop I.
+ DEF_LOOP_EXITS is a bitmap of loop exit blocks that exit the loop
+ containing DEF_BB or its outer loops.
- Compute the subset of LOOP_EXITS that exit the loop containing DEF_BB
- or one of its loop fathers, in which DEF is live. This set is returned
- in the bitmap LIVE_EXITS.
+ Compute the subset of loop exit destinations that exit the loop
+ containing DEF_BB or one of its loop fathers, in which DEF is live.
+ This set is returned in the bitmap LIVE_EXITS.
Instead of computing the complete livein set of the def, we use the loop
nesting tree as a form of poor man's structure analysis. This greatly
@@ -197,18 +199,17 @@ find_sibling_superloop (class loop *use_loop, class loop *def_loop)
static void
compute_live_loop_exits (bitmap live_exits, bitmap use_blocks,
- bitmap *loop_exits, basic_block def_bb)
+ basic_block def_bb, bitmap def_loop_exits)
{
unsigned i;
bitmap_iterator bi;
class loop *def_loop = def_bb->loop_father;
unsigned def_loop_depth = loop_depth (def_loop);
- bitmap def_loop_exits;
/* Normally the work list size is bounded by the number of basic
blocks in the largest loop. We don't know this number, but we
can be fairly sure that it will be relatively small. */
- auto_vec<basic_block> worklist (MAX (8, n_basic_blocks_for_fn (cfun) / 128));
+ auto_vec<basic_block, 8> worklist (MAX (8, n_basic_blocks_for_fn (cfun) / 128));
EXECUTE_IF_SET_IN_BITMAP (use_blocks, 0, i, bi)
{
@@ -272,13 +273,7 @@ compute_live_loop_exits (bitmap live_exits, bitmap use_blocks,
}
}
- def_loop_exits = BITMAP_ALLOC (&loop_renamer_obstack);
- for (class loop *loop = def_loop;
- loop != current_loops->tree_root;
- loop = loop_outer (loop))
- bitmap_ior_into (def_loop_exits, loop_exits[loop->num]);
bitmap_and_into (live_exits, def_loop_exits);
- BITMAP_FREE (def_loop_exits);
}
/* Add a loop-closing PHI for VAR in basic block EXIT. */
@@ -322,23 +317,33 @@ add_exit_phi (basic_block exit, tree var)
Exits of the loops are stored in LOOP_EXITS. */
static void
-add_exit_phis_var (tree var, bitmap use_blocks, bitmap *loop_exits)
+add_exit_phis_var (tree var, bitmap use_blocks, bitmap def_loop_exits)
{
unsigned index;
bitmap_iterator bi;
basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
- bitmap live_exits = BITMAP_ALLOC (&loop_renamer_obstack);
gcc_checking_assert (! bitmap_bit_p (use_blocks, def_bb->index));
- compute_live_loop_exits (live_exits, use_blocks, loop_exits, def_bb);
+ auto_bitmap live_exits (&loop_renamer_obstack);
+ compute_live_loop_exits (live_exits, use_blocks, def_bb, def_loop_exits);
EXECUTE_IF_SET_IN_BITMAP (live_exits, 0, index, bi)
{
add_exit_phi (BASIC_BLOCK_FOR_FN (cfun, index), var);
}
+}
- BITMAP_FREE (live_exits);
+static int
+loop_name_cmp (const void *p1, const void *p2)
+{
+ auto l1 = (const std::pair<int, int> *)p1;
+ auto l2 = (const std::pair<int, int> *)p2;
+ if (l1->first < l2->first)
+ return -1;
+ else if (l1->first > l2->first)
+ return 1;
+ return 0;
}
/* Add exit phis for the names marked in NAMES_TO_RENAME.
@@ -346,31 +351,38 @@ add_exit_phis_var (tree var, bitmap use_blocks, bitmap *loop_exits)
names are used are stored in USE_BLOCKS. */
static void
-add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap *loop_exits)
+add_exit_phis (bitmap names_to_rename, bitmap *use_blocks)
{
unsigned i;
bitmap_iterator bi;
+ /* Sort names_to_rename after definition loop so we can avoid re-computing
+ def_loop_exits. */
+ auto_vec<std::pair<int, int> > names (bitmap_count_bits (names_to_rename));
EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
{
- add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
+ tree name = ssa_name (i);
+ loop_p def_loop = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father;
+ names.quick_push (std::make_pair (def_loop->num, i));
}
-}
+ names.qsort (loop_name_cmp);
-/* Fill the array of bitmaps LOOP_EXITS with all loop exit edge targets. */
-
-static void
-get_loops_exits (bitmap *loop_exits)
-{
- unsigned j;
- edge e;
-
- for (auto loop : loops_list (cfun, 0))
+ auto_bitmap def_loop_exits (&loop_renamer_obstack);
+ loop_p last_def_loop = NULL;
+ for (auto p : names)
{
- auto_vec<edge> exit_edges = get_loop_exit_edges (loop);
- loop_exits[loop->num] = BITMAP_ALLOC (&loop_renamer_obstack);
- FOR_EACH_VEC_ELT (exit_edges, j, e)
- bitmap_set_bit (loop_exits[loop->num], e->dest->index);
+ loop_p def_loop = get_loop (cfun, p.first);
+ if (def_loop != last_def_loop)
+ {
+ bitmap_clear (def_loop_exits);
+ last_def_loop = def_loop;
+ for (class loop *loop = def_loop; loop != current_loops->tree_root;
+ loop = loop_outer (loop))
+ for (auto exit = loop->exits->next; exit->e; exit = exit->next)
+ bitmap_set_bit (def_loop_exits, exit->e->dest->index);
+ }
+ add_exit_phis_var (ssa_name (p.second), use_blocks[p.second],
+ def_loop_exits);
}
}
@@ -566,16 +578,21 @@ rewrite_into_loop_closed_ssa_1 (bitmap changed_bbs, unsigned update_flag,
if (!bitmap_empty_p (names_to_rename))
{
- /* An array of bitmaps where LOOP_EXITS[I] is the set of basic blocks
- that are the destination of an edge exiting loop number I. */
- bitmap *loop_exits = XNEWVEC (bitmap, number_of_loops (cfun));
- get_loops_exits (loop_exits);
+ bool release_recorded_exits_p = false;
+ if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
+ {
+ /* Doing one scan over the whole function is cheaper than
+ traversing the loop tree and gathering BBs of each loop. */
+ record_loop_exits ();
+ release_recorded_exits_p = true;
+ }
/* Add the PHI nodes on exits of the loops for the names we need to
rewrite. */
- add_exit_phis (names_to_rename, use_blocks, loop_exits);
+ add_exit_phis (names_to_rename, use_blocks);
- free (loop_exits);
+ if (release_recorded_exits_p)
+ release_recorded_exits (cfun);
/* Fix up all the names found to be used outside their original
loops. */
--
2.35.3
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH] Speed up LC SSA rewrite
@ 2022-07-07 7:05 Richard Biener
0 siblings, 0 replies; 3+ messages in thread
From: Richard Biener @ 2022-07-07 7:05 UTC (permalink / raw)
To: gcc-patches
The following avoids collecting all loops exit blocks into bitmaps
and computing the union of those up the loop tree possibly repeatedly.
Instead we make sure to do this only once for each loop with a
definition possibly requiring a LC phi node plus make sure to
leverage recorded exits to avoid the intermediate bitmap allocation.
Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.
* tree-ssa-loop-manip.cc (compute_live_loop_exits): Take
the def loop exit block bitmap as argument instead of
re-computing it here.
(add_exit_phis_var): Adjust.
(loop_name_cmp): New function.
(add_exit_phis): Sort variables to insert LC PHI nodes
after definition loop, for each definition loop compute
the exit block bitmap once.
(get_loops_exit): Remove.
(rewrite_into_loop_closed_ssa_1): Do not pre-record
all loop exit blocks into bitmaps. Record loop exits
if required.
---
gcc/tree-ssa-loop-manip.cc | 95 ++++++++++++++++++++++----------------
1 file changed, 56 insertions(+), 39 deletions(-)
diff --git a/gcc/tree-ssa-loop-manip.cc b/gcc/tree-ssa-loop-manip.cc
index 9f3b62652ea..0324ff60a0f 100644
--- a/gcc/tree-ssa-loop-manip.cc
+++ b/gcc/tree-ssa-loop-manip.cc
@@ -183,12 +183,14 @@ find_sibling_superloop (class loop *use_loop, class loop *def_loop)
/* DEF_BB is a basic block containing a DEF that needs rewriting into
loop-closed SSA form. USE_BLOCKS is the set of basic blocks containing
uses of DEF that "escape" from the loop containing DEF_BB (i.e. blocks in
- USE_BLOCKS are dominated by DEF_BB but not in the loop father of DEF_B).
+ USE_BLOCKS are dominated by DEF_BB but not in the loop father of DEF_BB).
ALL_EXITS[I] is the set of all basic blocks that exit loop I.
+ DEF_LOOP_EXITS is a bitmap of loop exit blocks that exit the loop
+ containing DEF_BB or its outer loops.
- Compute the subset of LOOP_EXITS that exit the loop containing DEF_BB
- or one of its loop fathers, in which DEF is live. This set is returned
- in the bitmap LIVE_EXITS.
+ Compute the subset of loop exit destinations that exit the loop
+ containing DEF_BB or one of its loop fathers, in which DEF is live.
+ This set is returned in the bitmap LIVE_EXITS.
Instead of computing the complete livein set of the def, we use the loop
nesting tree as a form of poor man's structure analysis. This greatly
@@ -197,18 +199,17 @@ find_sibling_superloop (class loop *use_loop, class loop *def_loop)
static void
compute_live_loop_exits (bitmap live_exits, bitmap use_blocks,
- bitmap *loop_exits, basic_block def_bb)
+ basic_block def_bb, bitmap def_loop_exits)
{
unsigned i;
bitmap_iterator bi;
class loop *def_loop = def_bb->loop_father;
unsigned def_loop_depth = loop_depth (def_loop);
- bitmap def_loop_exits;
/* Normally the work list size is bounded by the number of basic
blocks in the largest loop. We don't know this number, but we
can be fairly sure that it will be relatively small. */
- auto_vec<basic_block> worklist (MAX (8, n_basic_blocks_for_fn (cfun) / 128));
+ auto_vec<basic_block, 8> worklist (MAX (8, n_basic_blocks_for_fn (cfun) / 128));
EXECUTE_IF_SET_IN_BITMAP (use_blocks, 0, i, bi)
{
@@ -272,13 +273,7 @@ compute_live_loop_exits (bitmap live_exits, bitmap use_blocks,
}
}
- def_loop_exits = BITMAP_ALLOC (&loop_renamer_obstack);
- for (class loop *loop = def_loop;
- loop != current_loops->tree_root;
- loop = loop_outer (loop))
- bitmap_ior_into (def_loop_exits, loop_exits[loop->num]);
bitmap_and_into (live_exits, def_loop_exits);
- BITMAP_FREE (def_loop_exits);
}
/* Add a loop-closing PHI for VAR in basic block EXIT. */
@@ -322,23 +317,33 @@ add_exit_phi (basic_block exit, tree var)
Exits of the loops are stored in LOOP_EXITS. */
static void
-add_exit_phis_var (tree var, bitmap use_blocks, bitmap *loop_exits)
+add_exit_phis_var (tree var, bitmap use_blocks, bitmap def_loop_exits)
{
unsigned index;
bitmap_iterator bi;
basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
- bitmap live_exits = BITMAP_ALLOC (&loop_renamer_obstack);
gcc_checking_assert (! bitmap_bit_p (use_blocks, def_bb->index));
- compute_live_loop_exits (live_exits, use_blocks, loop_exits, def_bb);
+ auto_bitmap live_exits (&loop_renamer_obstack);
+ compute_live_loop_exits (live_exits, use_blocks, def_bb, def_loop_exits);
EXECUTE_IF_SET_IN_BITMAP (live_exits, 0, index, bi)
{
add_exit_phi (BASIC_BLOCK_FOR_FN (cfun, index), var);
}
+}
- BITMAP_FREE (live_exits);
+static int
+loop_name_cmp (const void *p1, const void *p2)
+{
+ auto l1 = (const std::pair<int, int> *)p1;
+ auto l2 = (const std::pair<int, int> *)p2;
+ if (l1->first < l2->first)
+ return -1;
+ else if (l1->first > l2->first)
+ return 1;
+ return 0;
}
/* Add exit phis for the names marked in NAMES_TO_RENAME.
@@ -346,31 +351,38 @@ add_exit_phis_var (tree var, bitmap use_blocks, bitmap *loop_exits)
names are used are stored in USE_BLOCKS. */
static void
-add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap *loop_exits)
+add_exit_phis (bitmap names_to_rename, bitmap *use_blocks)
{
unsigned i;
bitmap_iterator bi;
+ /* Sort names_to_rename after definition loop so we can avoid re-computing
+ def_loop_exits. */
+ auto_vec<std::pair<int, int> > names (bitmap_count_bits (names_to_rename));
EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
{
- add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
+ tree name = ssa_name (i);
+ loop_p def_loop = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father;
+ names.quick_push (std::make_pair (def_loop->num, i));
}
-}
+ names.qsort (loop_name_cmp);
-/* Fill the array of bitmaps LOOP_EXITS with all loop exit edge targets. */
-
-static void
-get_loops_exits (bitmap *loop_exits)
-{
- unsigned j;
- edge e;
-
- for (auto loop : loops_list (cfun, 0))
+ auto_bitmap def_loop_exits (&loop_renamer_obstack);
+ loop_p last_def_loop = NULL;
+ for (auto p : names)
{
- auto_vec<edge> exit_edges = get_loop_exit_edges (loop);
- loop_exits[loop->num] = BITMAP_ALLOC (&loop_renamer_obstack);
- FOR_EACH_VEC_ELT (exit_edges, j, e)
- bitmap_set_bit (loop_exits[loop->num], e->dest->index);
+ loop_p def_loop = get_loop (cfun, p.first);
+ if (def_loop != last_def_loop)
+ {
+ bitmap_clear (def_loop_exits);
+ last_def_loop = def_loop;
+ for (class loop *loop = def_loop; loop != current_loops->tree_root;
+ loop = loop_outer (loop))
+ for (auto exit = loop->exits->next; exit->e; exit = exit->next)
+ bitmap_set_bit (def_loop_exits, exit->e->dest->index);
+ }
+ add_exit_phis_var (ssa_name (p.second), use_blocks[p.second],
+ def_loop_exits);
}
}
@@ -566,16 +578,21 @@ rewrite_into_loop_closed_ssa_1 (bitmap changed_bbs, unsigned update_flag,
if (!bitmap_empty_p (names_to_rename))
{
- /* An array of bitmaps where LOOP_EXITS[I] is the set of basic blocks
- that are the destination of an edge exiting loop number I. */
- bitmap *loop_exits = XNEWVEC (bitmap, number_of_loops (cfun));
- get_loops_exits (loop_exits);
+ bool release_recorded_exits_p = false;
+ if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
+ {
+ /* Doing one scan over the whole function is cheaper than
+ traversing the loop tree and gathering BBs of each loop. */
+ record_loop_exits ();
+ release_recorded_exits_p = true;
+ }
/* Add the PHI nodes on exits of the loops for the names we need to
rewrite. */
- add_exit_phis (names_to_rename, use_blocks, loop_exits);
+ add_exit_phis (names_to_rename, use_blocks);
- free (loop_exits);
+ if (release_recorded_exits_p)
+ release_recorded_exits (cfun);
/* Fix up all the names found to be used outside their original
loops. */
--
2.35.3
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2022-07-07 7:05 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-07-07 7:05 [PATCH] Speed up LC SSA rewrite Richard Biener
2022-07-07 7:05 Richard Biener
2022-07-07 7:05 Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).