From: Kyrylo Tkachov <[email protected]> simplify_phi_setup calls simplify_phi_propagate for every phi. That walks the list of all phi uses of the phi, to propagate the phi's mode to the uses and to check for lower-uid users whose optimistic assumptions were wrong. The use_infos on that list belong to many different phis, so for a phi network with a large number of inputs the walk touches each use_info with poor locality. Nearly all of these uses are backedge uses whose assumptions turn out to be valid, so the walk almost never changes anything other than the use's mode.
Instead, do the set-up checks from the user side. After all phis have been set up, visit the inputs of each phi, which are allocated contiguously, and apply the checks that simplify_phi_propagate would have applied to the phi's backedge inputs. This is done by a new function simplify_phi_backedges, which shares the per-user update logic with simplify_phi_propagate through simplify_phi_update_user. Write the final phi modes to the phi uses in one pass at the end, rather than as a side effect of each propagation. The set of assumptions that is reached is the same, since the worklist phase still revisits any phi whose assumptions or mode changed. The users of RTL-SSA, such as fold-mem-offsets and the AArch64 load/store pair fusion pass, spent more than half of their time in simplify_phi_propagate when compiling POVRay fnpovfpu.cpp at -O2. On that file this patch alone reduces the compile time by 37%. On top of the previous patch, which bounds the number of dispatch copies, it removes a further 13% at -O2 and 11% at -O3, and cuts the time in each of fold-mem-offsets and machine dependent reorg by 44%. Together the two patches reduce the compile time of that file by 80% at -O2, and of the whole of 511.povray_r by 13%, leaving it within 1% of compiling with -fno-duplicate-switch-dispatch. Bootstrapped and tested on aarch64-none-linux-gnu Ok for trunk? Thanks, Kyrill Cc: Richard Sandiford <[email protected]> gcc/ChangeLog: PR target/128512 * rtl-ssa/functions.h (function_info::simplify_phi_setup): Remove the worklist parameter. (function_info::simplify_phi_update_user) (function_info::simplify_phi_backedges): Declare. * rtl-ssa/functions.cc (function_info::simplify_phi_setup): Do not call simplify_phi_propagate. (function_info::simplify_phi_update_user): New function, split out from simplify_phi_propagate. (function_info::simplify_phi_backedges): New function. (function_info::simplify_phi_propagate): Use simplify_phi_update_user. Do not update the modes of the uses. (function_info::simplify_phis): Call simplify_phi_backedges for each phi after the set-up phase. Update the modes of phi uses after the propagation phase. Signed-off-by: Kyrylo Tkachov <[email protected]> --- gcc/rtl-ssa/functions.cc | 123 +++++++++++++++++++++++---------------- gcc/rtl-ssa/functions.h | 4 +- 2 files changed, 75 insertions(+), 52 deletions(-) diff --git a/gcc/rtl-ssa/functions.cc b/gcc/rtl-ssa/functions.cc index d7b01415ebb..b943412cdd7 100644 --- a/gcc/rtl-ssa/functions.cc +++ b/gcc/rtl-ssa/functions.cc @@ -106,10 +106,9 @@ function_info::init_function_data () // This has already been done for phis with a lower uid than PHI, // initially making optimistic assumptions about backedge inputs. // Now do the same for PHI. If this might invalidate any assumptions -// made for earlier phis, add the uids of those phis to WORKLIST. +// made for earlier phis, simplify_phi_backedges detects that later. void -function_info::simplify_phi_setup (phi_info *phi, set_info **assumed_values, - bitmap worklist) +function_info::simplify_phi_setup (phi_info *phi, set_info **assumed_values) { // If all non-backedge inputs have the same value, set NEW_VALUE // to that value. Otherwise set NEW_VALUE to PHI, to indicate @@ -153,16 +152,61 @@ function_info::simplify_phi_setup (phi_info *phi, set_info **assumed_values, // entirely of backedges. gcc_checking_assert (!is_first_input); assumed_values[phi_uid] = new_value; +} + +// Update USER_PHI, which has PHI as an input. Make USER_PHI's mode at least +// as big as PHI's. If USER_PHI optimistically assumed a value other than +// PHI's, assume that USER_PHI is not simplifiable. Return true if either +// the mode or the assumed value of USER_PHI changed. +bool +function_info::simplify_phi_update_user (phi_info *user_phi, phi_info *phi, + set_info **assumed_values) +{ + bool needs_update = false; + + // Make sure that USER_PHI's mode is at least as big as PHI's. + machine_mode user_phi_mode = user_phi->mode (); + machine_mode new_mode = combine_modes (user_phi_mode, phi->mode ()); + if (user_phi_mode != new_mode) + { + user_phi->set_mode (new_mode); + needs_update = true; + } - // See whether any assumptions for earlier phis are now invalid. - simplify_phi_propagate (phi, assumed_values, nullptr, worklist); + // If USER_PHI optimistically assumed an incorrect value, adjust it now. + unsigned int user_phi_uid = user_phi->uid (); + if (assumed_values[user_phi_uid] != user_phi + && assumed_values[user_phi_uid] != assumed_values[phi->uid ()]) + { + assumed_values[user_phi_uid] = user_phi; + needs_update = true; + } + return needs_update; +} + +// The final part of the set-up phase. Backedge inputs were ignored +// when setting up PHI, so check them against the assumptions made for PHI, +// with ASSUMED_VALUES as described above simplify_phi_setup. +// If PHI needs updating, add its uid to WORKLIST. +// +// Visiting the inputs of each phi, rather than the uses of each input, +// accesses the use_infos in the order in which they were allocated. +void +function_info::simplify_phi_backedges (phi_info *phi, + set_info **assumed_values, + bitmap worklist) +{ + unsigned int phi_uid = phi->uid (); + for (use_info *input : phi->inputs ()) + if (auto *input_phi = safe_dyn_cast<phi_info *> (input->def ())) + if (phi_uid < input_phi->uid () + && simplify_phi_update_user (phi, input_phi, assumed_values)) + bitmap_set_bit (worklist, phi_uid); } // The propagation phase of the phi simplification process, with // ASSUMED_VALUES as described above simplify_phi_setup. Iteratively // update the phis that use PHI based on PHI's entry in ASSUMED_VALUES. -// If CURR_WORKLIST is null, consider only phi uses with a lower uid -// than PHI, otherwise consider all phi uses. // // If a phi with a higher uid than PHI needs updating, add its uid to // CURR_WORKLIST; if a phi with a lower uid than PHI needs updating, @@ -175,53 +219,15 @@ function_info::simplify_phi_propagate (phi_info *phi, { // Go through each phi user of PHI to see whether it needs updating. unsigned int phi_uid = phi->uid (); - machine_mode phi_mode = phi->mode (); - set_info *phi_value = assumed_values[phi_uid]; for (use_info *use : phi->phi_uses ()) { phi_info *user_phi = use->phi (); - - // Propagate the phi's new mode to all phi users. Insn uses should - // not be updated, since their modes reflect a property of the insns - // rather than the phi. - if (use->mode () != phi_mode) - use->set_mode (phi_mode); - - if (user_phi == phi) - continue; - - // If this is a phi we should be looking at, see whether it needs - // an update. - unsigned int user_phi_uid = user_phi->uid (); - if (user_phi_uid < phi_uid || curr_worklist) + if (user_phi != phi + && simplify_phi_update_user (user_phi, phi, assumed_values)) { - bool needs_update = false; - - // Make sure that USER_PHI's mode is at least as big as PHI_MODE. - machine_mode user_phi_mode = user_phi->mode (); - machine_mode new_mode = combine_modes (user_phi_mode, phi_mode); - if (user_phi_mode != new_mode) - { - user_phi->set_mode (new_mode); - needs_update = true; - } - - // If USER_PHI optimistically assumed an incorrect value, - // adjust it now. - if (assumed_values[user_phi_uid] != user_phi - && assumed_values[user_phi_uid] != phi_value) - { - assumed_values[user_phi_uid] = user_phi; - needs_update = true; - } - - if (needs_update) - { - if (user_phi_uid < phi_uid) - bitmap_set_bit (next_worklist, user_phi_uid); - else - bitmap_set_bit (curr_worklist, user_phi_uid); - } + unsigned int user_phi_uid = user_phi->uid (); + bitmap_set_bit (user_phi_uid < phi_uid + ? next_worklist : curr_worklist, user_phi_uid); } } } @@ -256,9 +262,14 @@ function_info::simplify_phis () { bitmap_set_bit (valid_phi_uids, phi->uid ()); phis[phi->uid ()] = phi; - simplify_phi_setup (phi, assumed_values, curr_worklist); + simplify_phi_setup (phi, assumed_values); } + // See whether any assumptions made during the set-up phase are invalid. + for (unsigned int i = 0; i < m_next_phi_uid; ++i) + if (bitmap_bit_p (valid_phi_uids, i)) + simplify_phi_backedges (phis[i], assumed_values, curr_worklist); + // Iteratively process any phis that need updating; see // simplify_phi_propagate for details. Using a double queue // should reduce the number of times that any given phi node @@ -276,6 +287,16 @@ function_info::simplify_phis () std::swap (next_worklist, curr_worklist); } + // Propagate the final mode of each phi to its phi uses. Insn uses + // should not be updated, since their modes reflect a property of the + // insns rather than the phi. + for (unsigned int i = 0; i < m_next_phi_uid; ++i) + if (bitmap_bit_p (valid_phi_uids, i)) + for (use_info *input : phis[i]->inputs ()) + if (auto *input_phi = safe_dyn_cast<phi_info *> (input->def ())) + if (input->mode () != input_phi->mode ()) + input->set_mode (input_phi->mode ()); + // Make sure that assumed_values is a transitive closure. This ensures // that each use_info is only updated once. if (flag_checking) diff --git a/gcc/rtl-ssa/functions.h b/gcc/rtl-ssa/functions.h index 5893b86cb1f..ef9e56c6240 100644 --- a/gcc/rtl-ssa/functions.h +++ b/gcc/rtl-ssa/functions.h @@ -345,7 +345,9 @@ private: void populate_phi_inputs (build_info &); void process_all_blocks (); - void simplify_phi_setup (phi_info *, set_info **, bitmap); + void simplify_phi_setup (phi_info *, set_info **); + bool simplify_phi_update_user (phi_info *, phi_info *, set_info **); + void simplify_phi_backedges (phi_info *, set_info **, bitmap); void simplify_phi_propagate (phi_info *, set_info **, bitmap, bitmap); void simplify_phis (); -- 2.54.0 (Apple Git-157)
