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);