This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Fix regression on PR46590 (slow compile with -O0)
- From: Michael Matz <matz at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 13 Jan 2012 18:18:48 +0100 (CET)
- Subject: Fix regression on PR46590 (slow compile with -O0)
Hi,
the stack-var conflict generation code needs 13 (out of 34) seconds, with
-O0 on the second testcase of PR46590. Most of the time is spent in
generating the same conflicts again and again at each basic block (the
time right now is O(nr-of-bbs * N^2) where the number of conflicts is
O(N^2)).
If we simply remember for which partitions we already generated the lower
triangular conflict matrix we don't have to do that again, lowering the
overall time to O(N^2).
This patch does that. Time for variable expansion now is 0.4 seconds (of
overall 22).
Regstrapping in progress on x86_64-linux, okay for trunk?
Ciao,
Michael.
* cfgexpand.c (add_scope_conflicts_1): New old_conflicts argument,
use it in remembering which conflicts we already created.
(add_scope_conflicts): Adjust call to above, (de)allocate helper
bitmap.
Index: cfgexpand.c
===================================================================
*** cfgexpand.c (revision 183155)
--- cfgexpand.c (working copy)
*************** visit_conflict (gimple stmt ATTRIBUTE_UN
*** 441,451 ****
/* Helper routine for add_scope_conflicts, calculating the active partitions
at the end of BB, leaving the result in WORK. We're called to generate
! conflicts when FOR_CONFLICT is true, otherwise we're just tracking
! liveness. */
static void
! add_scope_conflicts_1 (basic_block bb, bitmap work, bool for_conflict)
{
edge e;
edge_iterator ei;
--- 441,452 ----
/* Helper routine for add_scope_conflicts, calculating the active partitions
at the end of BB, leaving the result in WORK. We're called to generate
! conflicts when OLD_CONFLICTS is non-null, otherwise we're just tracking
! liveness. If we generate conflicts then OLD_CONFLICTS stores the bits
! for which we generated conflicts already. */
static void
! add_scope_conflicts_1 (basic_block bb, bitmap work, bitmap old_conflicts)
{
edge e;
edge_iterator ei;
*************** add_scope_conflicts_1 (basic_block bb, b
*** 482,488 ****
}
else if (!is_gimple_debug (stmt))
{
! if (for_conflict
&& visit == visit_op)
{
/* If this is the first real instruction in this BB we need
--- 483,489 ----
}
else if (!is_gimple_debug (stmt))
{
! if (old_conflicts
&& visit == visit_op)
{
/* If this is the first real instruction in this BB we need
*************** add_scope_conflicts_1 (basic_block bb, b
*** 490,505 ****
Unlike classical liveness for named objects we can't
rely on seeing a def/use of the names we're interested in.
There might merely be indirect loads/stores. We'd not add any
! conflicts for such partitions. */
bitmap_iterator bi;
unsigned i;
! EXECUTE_IF_SET_IN_BITMAP (work, 0, i, bi)
{
unsigned j;
bitmap_iterator bj;
! EXECUTE_IF_SET_IN_BITMAP (work, i + 1, j, bj)
add_stack_var_conflict (i, j);
}
visit = visit_conflict;
}
walk_stmt_load_store_addr_ops (stmt, work, visit, visit, visit);
--- 491,521 ----
Unlike classical liveness for named objects we can't
rely on seeing a def/use of the names we're interested in.
There might merely be indirect loads/stores. We'd not add any
! conflicts for such partitions. We know that we generated
! conflicts between all partitions in old_conflicts already,
! so we need to generate only the new ones, avoiding to
! repeatedly pay the O(N^2) cost for each basic block. */
bitmap_iterator bi;
unsigned i;
!
! /* First the conflicts between new and old_conflicts members. */
! EXECUTE_IF_AND_COMPL_IN_BITMAP (work, old_conflicts, 0, i, bi)
{
unsigned j;
bitmap_iterator bj;
! EXECUTE_IF_SET_IN_BITMAP (old_conflicts, 0, j, bj)
add_stack_var_conflict (i, j);
}
+ /* Then the conflicts between only the new members. */
+ EXECUTE_IF_AND_COMPL_IN_BITMAP (work, old_conflicts, 0, i, bi)
+ {
+ unsigned j;
+ bitmap_iterator bj;
+ EXECUTE_IF_AND_COMPL_IN_BITMAP (work, old_conflicts, 0, j, bj)
+ add_stack_var_conflict (i, j);
+ }
+ /* And remember for the next basic block. */
+ bitmap_ior_into (old_conflicts, work);
visit = visit_conflict;
}
walk_stmt_load_store_addr_ops (stmt, work, visit, visit, visit);
*************** add_scope_conflicts (void)
*** 516,521 ****
--- 532,538 ----
basic_block bb;
bool changed;
bitmap work = BITMAP_ALLOC (NULL);
+ bitmap old_conflicts;
/* We approximate the live range of a stack variable by taking the first
mention of its name as starting point(s), and by the end-of-scope
*************** add_scope_conflicts (void)
*** 537,551 ****
FOR_EACH_BB (bb)
{
bitmap active = (bitmap)bb->aux;
! add_scope_conflicts_1 (bb, work, false);
if (bitmap_ior_into (active, work))
changed = true;
}
}
FOR_EACH_BB (bb)
! add_scope_conflicts_1 (bb, work, true);
BITMAP_FREE (work);
FOR_ALL_BB (bb)
BITMAP_FREE (bb->aux);
--- 554,571 ----
FOR_EACH_BB (bb)
{
bitmap active = (bitmap)bb->aux;
! add_scope_conflicts_1 (bb, work, NULL);
if (bitmap_ior_into (active, work))
changed = true;
}
}
+ old_conflicts = BITMAP_ALLOC (NULL);
+
FOR_EACH_BB (bb)
! add_scope_conflicts_1 (bb, work, old_conflicts);
+ BITMAP_FREE (old_conflicts);
BITMAP_FREE (work);
FOR_ALL_BB (bb)
BITMAP_FREE (bb->aux);