Re: [PATCH 4/4] aarch64: Fix up uses of mem following stp insert [PR113070]
On 13/01/2024 15:46, Alex Coplan wrote: > As the PR shows (specifically #c7) we are missing updating uses of mem > when inserting an stp in the aarch64 load/store pair fusion pass. This > patch fixes that. > > RTL-SSA has a simple view of memory and by default doesn't allow stores > to be re-ordered w.r.t. other stores. In the ldp fusion pass, we do our > own alias analysis and so can re-order stores over other accesses when > we deem this is safe. If neither store can be re-purposed (moved into > the required position to form the stp while respecting the RTL-SSA > constraints), then we turn both the candidate stores into "tombstone" > insns (logically delete them) and insert a new stp insn. > > As it stands, we implement the insert case separately (after dealing > with the candidate stores) in fuse_pair by inserting into the middle of > the vector of changes. This is OK when we only have to insert one > change, but with this fix we would need to insert the change for the new > stp plus multiple changes to fix up uses of mem (note the number of > fix-ups is naturally bounded by the alias limit param to prevent > quadratic behaviour). If we kept the code structured as is and inserted > into the middle of the vector, that would lead to repeated moving of > elements in the vector which seems inefficient. The structure of the > code would also be a little unwieldy. > > To improve on that situation, this patch introduces a helper class, > stp_change_builder, which implements a state machine that helps to build > the required changes directly in program order. That state machine is > reponsible for deciding what changes need to be made in what order, and > the code in fuse_pair then simply follows those steps. > > Together with the fix in the previous patch for installing new defs > correctly in RTL-SSA, this fixes PR113070. > > We take the opportunity to rename the function decide_stp_strategy to > try_repurpose_store, as that seems more descriptive of what it actually > does, since stp_change_builder is now responsible for the overall change > strategy. > > Bootstrapped/regtested as a series with/without the passes enabled on > aarch64-linux-gnu, OK for trunk? > > Thanks, > Alex > > gcc/ChangeLog: > > PR target/113070 > * config/aarch64/aarch64-ldp-fusion.cc (struct stp_change_builder): New. > (decide_stp_strategy): Reanme to ... > (try_repurpose_store): ... this. > (ldp_bb_info::fuse_pair): Refactor to use stp_change_builder to > construct stp changes. Fix up uses when inserting new stp insns. > --- > gcc/config/aarch64/aarch64-ldp-fusion.cc | 248 ++- > 1 file changed, 194 insertions(+), 54 deletions(-) > > diff --git a/gcc/config/aarch64/aarch64-ldp-fusion.cc > b/gcc/config/aarch64/aarch64-ldp-fusion.cc > index 689a8c884bd..703cfb1228c 100644 > --- a/gcc/config/aarch64/aarch64-ldp-fusion.cc > +++ b/gcc/config/aarch64/aarch64-ldp-fusion.cc > @@ -844,11 +844,138 @@ def_upwards_move_range (def_info *def) >return range; > } > > +// Class that implements a state machine for building the changes needed to > form > +// a store pair instruction. This allows us to easily build the changes in > +// program order, as required by rtl-ssa. > +struct stp_change_builder > +{ > + enum class state > + { > +FIRST, > +INSERT, > +FIXUP_USE, > +LAST, > +DONE > + }; > + > + enum class action > + { > +TOMBSTONE, > +CHANGE, > +INSERT, > +FIXUP_USE > + }; > + > + struct change > + { > +action type; > +insn_info *insn; > + }; > + > + bool done () const { return m_state == state::DONE; } > + > + stp_change_builder (insn_info *insns[2], > + insn_info *repurpose, > + insn_info *dest) > +: m_state (state::FIRST), m_insns { insns[0], insns[1] }, > + m_repurpose (repurpose), m_dest (dest), m_use (nullptr) {} > + > + change get_change () const > + { > +switch (m_state) > + { > + case state::FIRST: > + return { > + m_insns[0] == m_repurpose ? action::CHANGE : action::TOMBSTONE, > + m_insns[0] > + }; > + case state::LAST: > + return { > + m_insns[1] == m_repurpose ? action::CHANGE : action::TOMBSTONE, > + m_insns[1] > + }; > + case state::INSERT: > + return { action::INSERT, m_dest }; > + case state::FIXUP_USE: > + return { action::FIXUP_USE, m_use->insn () }; > + case state::DONE: > + break; > + } > + > +gcc_unreachable (); > + } > + > + // Transition to the next state. > + void advance () > + { > +switch (m_state) > + { > + case state::FIRST: > + if (m_repurpose) > + m_state = state::LAST; > + else > + m_state = state::INSERT; > + break; > + case state::INSERT: > + { > + def_info *def = memory_access (m_insns[0]->defs ()); > + while (*def->next_def ()->insn () <= *m_dest) > + def = def->next_def (
Re: [PATCH 4/4] aarch64: Fix up uses of mem following stp insert [PR113070]
Alex Coplan writes: > As the PR shows (specifically #c7) we are missing updating uses of mem > when inserting an stp in the aarch64 load/store pair fusion pass. This > patch fixes that. > > RTL-SSA has a simple view of memory and by default doesn't allow stores > to be re-ordered w.r.t. other stores. In the ldp fusion pass, we do our > own alias analysis and so can re-order stores over other accesses when > we deem this is safe. If neither store can be re-purposed (moved into > the required position to form the stp while respecting the RTL-SSA > constraints), then we turn both the candidate stores into "tombstone" > insns (logically delete them) and insert a new stp insn. > > As it stands, we implement the insert case separately (after dealing > with the candidate stores) in fuse_pair by inserting into the middle of > the vector of changes. This is OK when we only have to insert one > change, but with this fix we would need to insert the change for the new > stp plus multiple changes to fix up uses of mem (note the number of > fix-ups is naturally bounded by the alias limit param to prevent > quadratic behaviour). If we kept the code structured as is and inserted > into the middle of the vector, that would lead to repeated moving of > elements in the vector which seems inefficient. The structure of the > code would also be a little unwieldy. > > To improve on that situation, this patch introduces a helper class, > stp_change_builder, which implements a state machine that helps to build > the required changes directly in program order. That state machine is > reponsible for deciding what changes need to be made in what order, and > the code in fuse_pair then simply follows those steps. > > Together with the fix in the previous patch for installing new defs > correctly in RTL-SSA, this fixes PR113070. > > We take the opportunity to rename the function decide_stp_strategy to > try_repurpose_store, as that seems more descriptive of what it actually > does, since stp_change_builder is now responsible for the overall change > strategy. > > Bootstrapped/regtested as a series with/without the passes enabled on > aarch64-linux-gnu, OK for trunk? > > Thanks, > Alex > > gcc/ChangeLog: > > PR target/113070 > * config/aarch64/aarch64-ldp-fusion.cc (struct stp_change_builder): New. > (decide_stp_strategy): Reanme to ... > (try_repurpose_store): ... this. > (ldp_bb_info::fuse_pair): Refactor to use stp_change_builder to > construct stp changes. Fix up uses when inserting new stp insns. > --- > gcc/config/aarch64/aarch64-ldp-fusion.cc | 248 ++- > 1 file changed, 194 insertions(+), 54 deletions(-) > > diff --git a/gcc/config/aarch64/aarch64-ldp-fusion.cc > b/gcc/config/aarch64/aarch64-ldp-fusion.cc > index 689a8c884bd..703cfb1228c 100644 > --- a/gcc/config/aarch64/aarch64-ldp-fusion.cc > +++ b/gcc/config/aarch64/aarch64-ldp-fusion.cc > @@ -844,11 +844,138 @@ def_upwards_move_range (def_info *def) >return range; > } > > +// Class that implements a state machine for building the changes needed to > form > +// a store pair instruction. This allows us to easily build the changes in > +// program order, as required by rtl-ssa. > +struct stp_change_builder > +{ > + enum class state > + { > +FIRST, > +INSERT, > +FIXUP_USE, > +LAST, > +DONE > + }; > + > + enum class action > + { > +TOMBSTONE, > +CHANGE, > +INSERT, > +FIXUP_USE > + }; > + > + struct change > + { > +action type; > +insn_info *insn; > + }; > + > + bool done () const { return m_state == state::DONE; } > + > + stp_change_builder (insn_info *insns[2], > + insn_info *repurpose, > + insn_info *dest) > +: m_state (state::FIRST), m_insns { insns[0], insns[1] }, > + m_repurpose (repurpose), m_dest (dest), m_use (nullptr) {} Just to make sure I understand: is it the case that *insns[0] <= *dest <= *insns[1] ? > + > + change get_change () const > + { > +switch (m_state) > + { > + case state::FIRST: > + return { > + m_insns[0] == m_repurpose ? action::CHANGE : action::TOMBSTONE, > + m_insns[0] > + }; > + case state::LAST: > + return { > + m_insns[1] == m_repurpose ? action::CHANGE : action::TOMBSTONE, > + m_insns[1] > + }; > + case state::INSERT: > + return { action::INSERT, m_dest }; > + case state::FIXUP_USE: > + return { action::FIXUP_USE, m_use->insn () }; > + case state::DONE: > + break; > + } > + > +gcc_unreachable (); > + } > + > + // Transition to the next state. > + void advance () > + { > +switch (m_state) > + { > + case state::FIRST: > + if (m_repurpose) > + m_state = state::LAST; > + else > + m_state = state::INSERT; > + break; > + case state::INSERT: > + { > + def_info *def = memory_access (m_insns[0]->defs ()); > + while (*def->ne
Re: [PATCH 4/4] aarch64: Fix up uses of mem following stp insert [PR113070]
On 22/01/2024 15:59, Richard Sandiford wrote: > Alex Coplan writes: > > As the PR shows (specifically #c7) we are missing updating uses of mem > > when inserting an stp in the aarch64 load/store pair fusion pass. This > > patch fixes that. > > > > RTL-SSA has a simple view of memory and by default doesn't allow stores > > to be re-ordered w.r.t. other stores. In the ldp fusion pass, we do our > > own alias analysis and so can re-order stores over other accesses when > > we deem this is safe. If neither store can be re-purposed (moved into > > the required position to form the stp while respecting the RTL-SSA > > constraints), then we turn both the candidate stores into "tombstone" > > insns (logically delete them) and insert a new stp insn. > > > > As it stands, we implement the insert case separately (after dealing > > with the candidate stores) in fuse_pair by inserting into the middle of > > the vector of changes. This is OK when we only have to insert one > > change, but with this fix we would need to insert the change for the new > > stp plus multiple changes to fix up uses of mem (note the number of > > fix-ups is naturally bounded by the alias limit param to prevent > > quadratic behaviour). If we kept the code structured as is and inserted > > into the middle of the vector, that would lead to repeated moving of > > elements in the vector which seems inefficient. The structure of the > > code would also be a little unwieldy. > > > > To improve on that situation, this patch introduces a helper class, > > stp_change_builder, which implements a state machine that helps to build > > the required changes directly in program order. That state machine is > > reponsible for deciding what changes need to be made in what order, and > > the code in fuse_pair then simply follows those steps. > > > > Together with the fix in the previous patch for installing new defs > > correctly in RTL-SSA, this fixes PR113070. > > > > We take the opportunity to rename the function decide_stp_strategy to > > try_repurpose_store, as that seems more descriptive of what it actually > > does, since stp_change_builder is now responsible for the overall change > > strategy. > > > > Bootstrapped/regtested as a series with/without the passes enabled on > > aarch64-linux-gnu, OK for trunk? > > > > Thanks, > > Alex > > > > gcc/ChangeLog: > > > > PR target/113070 > > * config/aarch64/aarch64-ldp-fusion.cc (struct stp_change_builder): New. > > (decide_stp_strategy): Reanme to ... > > (try_repurpose_store): ... this. > > (ldp_bb_info::fuse_pair): Refactor to use stp_change_builder to > > construct stp changes. Fix up uses when inserting new stp insns. > > --- > > gcc/config/aarch64/aarch64-ldp-fusion.cc | 248 ++- > > 1 file changed, 194 insertions(+), 54 deletions(-) > > > > diff --git a/gcc/config/aarch64/aarch64-ldp-fusion.cc > > b/gcc/config/aarch64/aarch64-ldp-fusion.cc > > index 689a8c884bd..703cfb1228c 100644 > > --- a/gcc/config/aarch64/aarch64-ldp-fusion.cc > > +++ b/gcc/config/aarch64/aarch64-ldp-fusion.cc > > @@ -844,11 +844,138 @@ def_upwards_move_range (def_info *def) > >return range; > > } > > > > +// Class that implements a state machine for building the changes needed > > to form > > +// a store pair instruction. This allows us to easily build the changes in > > +// program order, as required by rtl-ssa. > > +struct stp_change_builder > > +{ > > + enum class state > > + { > > +FIRST, > > +INSERT, > > +FIXUP_USE, > > +LAST, > > +DONE > > + }; > > + > > + enum class action > > + { > > +TOMBSTONE, > > +CHANGE, > > +INSERT, > > +FIXUP_USE > > + }; > > + > > + struct change > > + { > > +action type; > > +insn_info *insn; > > + }; > > + > > + bool done () const { return m_state == state::DONE; } > > + > > + stp_change_builder (insn_info *insns[2], > > + insn_info *repurpose, > > + insn_info *dest) > > +: m_state (state::FIRST), m_insns { insns[0], insns[1] }, > > + m_repurpose (repurpose), m_dest (dest), m_use (nullptr) {} > > Just to make sure I understand: is it the case that > > *insns[0] <= *dest <= *insns[1] > > ? Yes, that is my understanding. I thought about asserting it somewhere in stp_change_builder, but it seemed a bit gratuitous. > > > + > > + change get_change () const > > + { > > +switch (m_state) > > + { > > + case state::FIRST: > > + return { > > + m_insns[0] == m_repurpose ? action::CHANGE : action::TOMBSTONE, > > + m_insns[0] > > + }; > > + case state::LAST: > > + return { > > + m_insns[1] == m_repurpose ? action::CHANGE : action::TOMBSTONE, > > + m_insns[1] > > + }; > > + case state::INSERT: > > + return { action::INSERT, m_dest }; > > + case state::FIXUP_USE: > > + return { action::FIXUP_USE, m_use->insn () }; > > + case state::DONE: > > + break; > > + } > > + > > +gcc_u
Re: [PATCH 4/4] aarch64: Fix up uses of mem following stp insert [PR113070]
On 22/01/2024 21:50, Alex Coplan wrote: > On 22/01/2024 15:59, Richard Sandiford wrote: > > Alex Coplan writes: > > > As the PR shows (specifically #c7) we are missing updating uses of mem > > > when inserting an stp in the aarch64 load/store pair fusion pass. This > > > patch fixes that. > > > > > > RTL-SSA has a simple view of memory and by default doesn't allow stores > > > to be re-ordered w.r.t. other stores. In the ldp fusion pass, we do our > > > own alias analysis and so can re-order stores over other accesses when > > > we deem this is safe. If neither store can be re-purposed (moved into > > > the required position to form the stp while respecting the RTL-SSA > > > constraints), then we turn both the candidate stores into "tombstone" > > > insns (logically delete them) and insert a new stp insn. > > > > > > As it stands, we implement the insert case separately (after dealing > > > with the candidate stores) in fuse_pair by inserting into the middle of > > > the vector of changes. This is OK when we only have to insert one > > > change, but with this fix we would need to insert the change for the new > > > stp plus multiple changes to fix up uses of mem (note the number of > > > fix-ups is naturally bounded by the alias limit param to prevent > > > quadratic behaviour). If we kept the code structured as is and inserted > > > into the middle of the vector, that would lead to repeated moving of > > > elements in the vector which seems inefficient. The structure of the > > > code would also be a little unwieldy. > > > > > > To improve on that situation, this patch introduces a helper class, > > > stp_change_builder, which implements a state machine that helps to build > > > the required changes directly in program order. That state machine is > > > reponsible for deciding what changes need to be made in what order, and > > > the code in fuse_pair then simply follows those steps. > > > > > > Together with the fix in the previous patch for installing new defs > > > correctly in RTL-SSA, this fixes PR113070. > > > > > > We take the opportunity to rename the function decide_stp_strategy to > > > try_repurpose_store, as that seems more descriptive of what it actually > > > does, since stp_change_builder is now responsible for the overall change > > > strategy. > > > > > > Bootstrapped/regtested as a series with/without the passes enabled on > > > aarch64-linux-gnu, OK for trunk? > > > > > > Thanks, > > > Alex > > > > > > gcc/ChangeLog: > > > > > > PR target/113070 > > > * config/aarch64/aarch64-ldp-fusion.cc (struct stp_change_builder): New. > > > (decide_stp_strategy): Reanme to ... > > > (try_repurpose_store): ... this. > > > (ldp_bb_info::fuse_pair): Refactor to use stp_change_builder to > > > construct stp changes. Fix up uses when inserting new stp insns. > > > --- > > > gcc/config/aarch64/aarch64-ldp-fusion.cc | 248 ++- > > > 1 file changed, 194 insertions(+), 54 deletions(-) > > > > > > diff --git a/gcc/config/aarch64/aarch64-ldp-fusion.cc > > > b/gcc/config/aarch64/aarch64-ldp-fusion.cc > > > index 689a8c884bd..703cfb1228c 100644 > > > --- a/gcc/config/aarch64/aarch64-ldp-fusion.cc > > > +++ b/gcc/config/aarch64/aarch64-ldp-fusion.cc > > > @@ -844,11 +844,138 @@ def_upwards_move_range (def_info *def) > > >return range; > > > } > > > > > > +// Class that implements a state machine for building the changes needed > > > to form > > > +// a store pair instruction. This allows us to easily build the changes > > > in > > > +// program order, as required by rtl-ssa. > > > +struct stp_change_builder > > > +{ > > > + enum class state > > > + { > > > +FIRST, > > > +INSERT, > > > +FIXUP_USE, > > > +LAST, > > > +DONE > > > + }; > > > + > > > + enum class action > > > + { > > > +TOMBSTONE, > > > +CHANGE, > > > +INSERT, > > > +FIXUP_USE > > > + }; > > > + > > > + struct change > > > + { > > > +action type; > > > +insn_info *insn; > > > + }; > > > + > > > + bool done () const { return m_state == state::DONE; } > > > + > > > + stp_change_builder (insn_info *insns[2], > > > + insn_info *repurpose, > > > + insn_info *dest) > > > +: m_state (state::FIRST), m_insns { insns[0], insns[1] }, > > > + m_repurpose (repurpose), m_dest (dest), m_use (nullptr) {} > > > > Just to make sure I understand: is it the case that > > > > *insns[0] <= *dest <= *insns[1] > > > > ? > > Yes, that is my understanding. I thought about asserting it somewhere in > stp_change_builder, but it seemed a bit gratuitous. > > > > > > + > > > + change get_change () const > > > + { > > > +switch (m_state) > > > + { > > > + case state::FIRST: > > > + return { > > > + m_insns[0] == m_repurpose ? action::CHANGE : action::TOMBSTONE, > > > + m_insns[0] > > > + }; > > > + case state::LAST: > > > + return { > > > + m_insns[1] == m_repurpose ? action::CHANGE : action::TOMBSTONE,