diff options
Diffstat (limited to 'gcc/rtl-ssa')
| -rw-r--r-- | gcc/rtl-ssa/accesses.cc | 32 | ||||
| -rw-r--r-- | gcc/rtl-ssa/accesses.h | 36 | ||||
| -rw-r--r-- | gcc/rtl-ssa/blocks.cc | 46 | ||||
| -rw-r--r-- | gcc/rtl-ssa/changes.cc | 6 | ||||
| -rw-r--r-- | gcc/rtl-ssa/functions.h | 16 | ||||
| -rw-r--r-- | gcc/rtl-ssa/member-fns.inl | 30 |
6 files changed, 159 insertions, 7 deletions
diff --git a/gcc/rtl-ssa/accesses.cc b/gcc/rtl-ssa/accesses.cc index 3d92997..0415e97 100644 --- a/gcc/rtl-ssa/accesses.cc +++ b/gcc/rtl-ssa/accesses.cc @@ -1087,6 +1087,38 @@ rtl_ssa::lookup_use (splay_tree<use_info *> &tree, insn_info *insn) return tree.lookup (compare); } +// See the comment above the declaration. +use_lookup +function_info::find_use (set_info *def, insn_info *insn) +{ + gcc_assert (!insn->is_debug_insn ()); + use_info *first = def->first_nondebug_insn_use (); + if (!first) + // There are no uses. The comparison result is pretty meaningless + // in this case. + return { nullptr, -1 }; + + // See whether the first use matches. + if (*insn <= *first->insn ()) + { + int comparison = (insn == first->insn () ? 0 : -1); + return { first, comparison }; + } + + // See whether the last use matches. + use_info *last = def->last_nondebug_insn_use (); + if (*insn >= *last->insn ()) + { + int comparison = (insn == last->insn () ? 0 : 1); + return { last, comparison }; + } + + // Resort to using a splay tree to search for the result. + need_use_splay_tree (def); + int comparison = lookup_use (def->m_use_tree, insn); + return { def->m_use_tree.root ()->value (), comparison }; +} + // Add USE to USE->def ()'s list of uses. inserting USE immediately before // BEFORE. USE is not currently in the list. // diff --git a/gcc/rtl-ssa/accesses.h b/gcc/rtl-ssa/accesses.h index 98403f7..b3a31fb 100644 --- a/gcc/rtl-ssa/accesses.h +++ b/gcc/rtl-ssa/accesses.h @@ -1044,6 +1044,42 @@ public: int comparison; }; +// This class represents the result of looking for a use of a particular +// definition at a particular point, here referred to as point P. +// There are four states: +// +// - USE is null if the definition has no uses. +// +// - Otherwise, COMPARISON is 0 if we found a definition at P. USE then +// contains this use. +// +// - Otherwise, COMPARISON is greater than 0 if we found a use that precedes P. +// USE then contains this use. +// +// - Otherwise, COMPARISON is less than zero and we found a use that follows P. +// USE then contains this use. +class use_lookup +{ +public: + // If we found a use at P, return that use, otherwise return null. + use_info *matching_use () const; + + // If we found a use at P, return that use, otherwise return prev_use (). + use_info *matching_or_prev_use () const; + + // If we found a use at P, return that use, otherwise return next_use (). + use_info *matching_or_next_use () const; + + // Return the last use that occurs before P, or null if none. + use_info *prev_use () const; + + // Return the first use that occurs after P, or null if none. + use_info *next_use () const; + + use_info *use; + int comparison; +}; + void pp_resource (pretty_printer *, resource_info); void pp_access (pretty_printer *, const access_info *, unsigned int flags = PP_ACCESS_DEFAULT); diff --git a/gcc/rtl-ssa/blocks.cc b/gcc/rtl-ssa/blocks.cc index 953fd9e..568f965 100644 --- a/gcc/rtl-ssa/blocks.cc +++ b/gcc/rtl-ssa/blocks.cc @@ -315,15 +315,14 @@ function_info::add_live_out_use (bb_info *bb, set_info *def) // If the end of the block already has an artificial use, that use // acts to make DEF live at the appropriate point. - use_info *use = def->last_nondebug_insn_use (); - if (use && use->insn () == bb->end_insn ()) + if (find_use (def, bb->end_insn ()).matching_use ()) return; // Currently there is no need to maintain a backward link from the end // instruction to the list of live-out uses. Such a list would be // expensive to update if it was represented using the usual insn_info // access arrays. - use = allocate<use_info> (bb->end_insn (), def->resource (), def); + auto *use = allocate<use_info> (bb->end_insn (), def->resource (), def); use->set_is_live_out_use (true); add_use (use); } @@ -360,6 +359,41 @@ function_info::live_out_value (bb_info *bb, set_info *set) return set; } +// Make USE's definition available at USE, if it isn't already. Assume that +// the caller has properly used make_use_available to check that this is +// possible. +void +function_info::commit_make_use_available (use_info *use) +{ + // We only need to handle single dominating definitions here. + // Other cases are handled by degenerate phis, with create_degenerate_phi + // creating any necessary live-out uses. + set_info *def = use->def (); + if (def + && use->is_reg () + && is_single_dominating_def (def) + && use->ebb () != def->ebb ()) + { + // If USE's EBB has DEF's EBB as its single predecessor, it's enough + // to add a live-out use to the former's predecessor block. Otherwise, + // conservatively add a live-out use at the end of DEF's block, so that + // DEF cannot move further down. Doing a minimal yet accurate update + // would be an O(n.log(n)) operation in the worst case. + auto ebb_cfg_bb = def->ebb ()->first_bb ()->cfg_bb (); + if (single_pred_p (ebb_cfg_bb)) + { + bb_info *pred_bb = this->bb (single_pred (ebb_cfg_bb)); + if (pred_bb->ebb () == def->ebb ()) + { + add_live_out_use (pred_bb, def); + return; + } + } + add_live_out_use (def->bb (), def); + return; + } +} + // Add PHI to EBB and enter it into the function's hash table. void function_info::append_phi (ebb_info *ebb, phi_info *phi) @@ -540,12 +574,12 @@ function_info::create_degenerate_phi (ebb_info *ebb, set_info *def) basic_block pred_cfg_bb = single_pred (ebb->first_bb ()->cfg_bb ()); bb_info *pred_bb = this->bb (pred_cfg_bb); - if (!bitmap_set_bit (DF_LR_IN (ebb->first_bb ()->cfg_bb ()), regno)) + if (bitmap_set_bit (DF_LR_IN (ebb->first_bb ()->cfg_bb ()), regno)) { // The register was not previously live on entry to EBB and // might not have been live on exit from PRED_BB either. - if (bitmap_set_bit (DF_LR_OUT (pred_cfg_bb), regno)) - add_live_out_use (pred_bb, def); + bitmap_set_bit (DF_LR_OUT (pred_cfg_bb), regno); + add_live_out_use (pred_bb, def); } else { diff --git a/gcc/rtl-ssa/changes.cc b/gcc/rtl-ssa/changes.cc index 00e6c31..f2fc982 100644 --- a/gcc/rtl-ssa/changes.cc +++ b/gcc/rtl-ssa/changes.cc @@ -713,7 +713,11 @@ function_info::apply_changes_to_insn (insn_change &change, // Add all uses, now that their position is final. for (use_info *use : change.new_uses) - add_use (use); + { + if (use->def ()) + commit_make_use_available (use); + add_use (use); + } // Copy the uses and definitions. unsigned int num_defs = change.new_defs.size (); diff --git a/gcc/rtl-ssa/functions.h b/gcc/rtl-ssa/functions.h index 2e20f5e..ba80507 100644 --- a/gcc/rtl-ssa/functions.h +++ b/gcc/rtl-ssa/functions.h @@ -131,8 +131,23 @@ public: // Look for a definition of RESOURCE at INSN. Return the result of the // search as a def_lookup; see the comments there for more details. + // + // NOTE: This is not the function to use if INSN is known to be a real + // instruction (one with an RTL pattern) and if the caller is only + // interested in definitions within INSN itself. In those cases + // it is better to use find_access. def_lookup find_def (resource_info resource, insn_info *insn); + // Search for a use of DEF around non-debug instruction INSN and return the + // result of the search as a use_lookup. See the comment above the class + // for more details about the result means. + // + // NOTE: This is not the function to use if INSN is known to be a real + // instruction (one with an RTL pattern) and if the caller is only + // interested in uses within INSN itself. In those cases it is better + // to use find_access. + use_lookup find_use (set_info *def, insn_info *insn); + // Return an RAII object that owns all temporary RTL SSA memory // allocated during a change attempt. The object should remain in // scope until the change has been aborted or successfully completed. @@ -294,6 +309,7 @@ private: void add_live_out_use (bb_info *, set_info *); set_info *live_out_value (bb_info *, set_info *); + void commit_make_use_available (use_info *); void append_phi (ebb_info *, phi_info *); void remove_phi (phi_info *); diff --git a/gcc/rtl-ssa/member-fns.inl b/gcc/rtl-ssa/member-fns.inl index 346a120..1049f61 100644 --- a/gcc/rtl-ssa/member-fns.inl +++ b/gcc/rtl-ssa/member-fns.inl @@ -478,6 +478,36 @@ def_lookup::matching_set_or_first_def_of_next_group () const return first_def_of_next_group (); } +inline use_info * +use_lookup::prev_use () const +{ + return !use || comparison > 0 ? use : use->prev_use (); +} + +inline use_info * +use_lookup::next_use () const +{ + return !use || comparison < 0 ? use : use->next_nondebug_insn_use (); +} + +inline use_info * +use_lookup::matching_use () const +{ + return comparison == 0 ? use : nullptr; +} + +inline use_info * +use_lookup::matching_or_prev_use () const +{ + return comparison == 0 ? use : prev_use (); +} + +inline use_info * +use_lookup::matching_or_next_use () const +{ + return comparison == 0 ? use : next_use (); +} + inline insn_note::insn_note (insn_note_kind kind) : m_next_note (nullptr), m_kind (kind), |