On Fri, Jan 13, 2012 at 6:18 PM, Michael Matz <m...@suse.de> wrote: > 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?
Ok. Thanks, Richard. > > 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);