The following introduces a new param, max-combine-insns, to
be able to limit the work done at -Og to linear complexity
in the number of log-links (thus, two-insn combines). It
also records statistics of performed combines where for
fold-const.ii on x86_64 we see at -Og (unpatched):
208 combine "three-insn combine" 25
208 combine "two-insn combine" 14393
and patched:
208 combine "two-insn combine" 14392
Bootstrap / regtest scheduled on x86_64-unknown-linux-gnu.
Ok? (I can rip out the statistics stuff if you mind)
(the combine_insns diff is so large because of re-indenting)
Thanks,
Richard.
2014-07-15 Richard Biener <rguent...@suse.de>
* params.def (PARAM_MAX_COMBINE_INSNS): New.
* combine.c: Include statistics.h and params.h.
(combine_instructions): Guard three and four insn combines
with max-combine-insns value. Record statistics for combines
performed.
* doc/invoke.texi (max-combine-insns): Document new param.
Index: gcc/params.def
===================================================================
*** gcc/params.def (revision 212548)
--- gcc/params.def (working copy)
*************** DEFPARAM(PARAM_MAX_LAST_VALUE_RTL,
*** 673,678 ****
--- 673,683 ----
"The maximum number of RTL nodes that can be recorded as combiner's
last value",
10000, 0, 0)
+ DEFPARAM(PARAM_MAX_COMBINE_INSNS,
+ "max-combine-insns",
+ "The maximum number of insns combine tries to combine",
+ 4, 2, 4)
+
/* INTEGER_CST nodes are shared for values [{-1,0} .. N) for
{signed,unsigned} integral types. This determines N.
Experimentation shows 251 to be a good value that generates the
Index: gcc/combine.c
===================================================================
*** gcc/combine.c (revision 212548)
--- gcc/combine.c (working copy)
*************** along with GCC; see the file COPYING3.
*** 104,109 ****
--- 104,111 ----
#include "valtrack.h"
#include "cgraph.h"
#include "obstack.h"
+ #include "statistics.h"
+ #include "params.h"
/* Number of attempts to combine instructions in this function. */
*************** combine_instructions (rtx f, unsigned in
*** 1209,1214 ****
--- 1211,1217 ----
init_reg_last ();
setup_incoming_promotions (first);
last_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
+ int max_combine = PARAM_VALUE (PARAM_MAX_COMBINE_INSNS);
FOR_EACH_BB_FN (this_basic_block, cfun)
{
*************** combine_instructions (rtx f, unsigned in
*** 1229,1446 ****
insn = next ? next : NEXT_INSN (insn))
{
next = 0;
! if (NONDEBUG_INSN_P (insn))
! {
! while (last_combined_insn
! && INSN_DELETED_P (last_combined_insn))
! last_combined_insn = PREV_INSN (last_combined_insn);
! if (last_combined_insn == NULL_RTX
! || BARRIER_P (last_combined_insn)
! || BLOCK_FOR_INSN (last_combined_insn) != this_basic_block
! || DF_INSN_LUID (last_combined_insn) <= DF_INSN_LUID (insn))
! last_combined_insn = insn;
!
! /* See if we know about function return values before this
! insn based upon SUBREG flags. */
! check_promoted_subreg (insn, PATTERN (insn));
!
! /* See if we can find hardregs and subreg of pseudos in
! narrower modes. This could help turning TRUNCATEs
! into SUBREGs. */
! note_uses (&PATTERN (insn), record_truncated_values, NULL);
!
! /* Try this insn with each insn it links back to. */
!
! FOR_EACH_LOG_LINK (links, insn)
! if ((next = try_combine (insn, links->insn, NULL_RTX,
! NULL_RTX, &new_direct_jump_p,
! last_combined_insn)) != 0)
! goto retry;
!
! /* Try each sequence of three linked insns ending with this one.
*/
! FOR_EACH_LOG_LINK (links, insn)
! {
! rtx link = links->insn;
!
! /* If the linked insn has been replaced by a note, then there
! is no point in pursuing this chain any further. */
! if (NOTE_P (link))
! continue;
!
! FOR_EACH_LOG_LINK (nextlinks, link)
! if ((next = try_combine (insn, link, nextlinks->insn,
! NULL_RTX, &new_direct_jump_p,
! last_combined_insn)) != 0)
goto retry;
! }
#ifdef HAVE_cc0
! /* Try to combine a jump insn that uses CC0
! with a preceding insn that sets CC0, and maybe with its
! logical predecessor as well.
! This is how we make decrement-and-branch insns.
! We need this special code because data flow connections
! via CC0 do not get entered in LOG_LINKS. */
!
! if (JUMP_P (insn)
! && (prev = prev_nonnote_insn (insn)) != 0
! && NONJUMP_INSN_P (prev)
! && sets_cc0_p (PATTERN (prev)))
! {
! if ((next = try_combine (insn, prev, NULL_RTX, NULL_RTX,
! &new_direct_jump_p,
last_combined_insn)) != 0)
goto retry;
! FOR_EACH_LOG_LINK (nextlinks, prev)
! if ((next = try_combine (insn, prev, nextlinks->insn,
! NULL_RTX, &new_direct_jump_p,
! last_combined_insn)) != 0)
! goto retry;
! }
!
! /* Do the same for an insn that explicitly references CC0. */
! if (NONJUMP_INSN_P (insn)
! && (prev = prev_nonnote_insn (insn)) != 0
! && NONJUMP_INSN_P (prev)
! && sets_cc0_p (PATTERN (prev))
! && GET_CODE (PATTERN (insn)) == SET
! && reg_mentioned_p (cc0_rtx, SET_SRC (PATTERN (insn))))
! {
! if ((next = try_combine (insn, prev, NULL_RTX, NULL_RTX,
! &new_direct_jump_p,
last_combined_insn)) != 0)
goto retry;
! FOR_EACH_LOG_LINK (nextlinks, prev)
! if ((next = try_combine (insn, prev, nextlinks->insn,
! NULL_RTX, &new_direct_jump_p,
! last_combined_insn)) != 0)
! goto retry;
! }
!
! /* Finally, see if any of the insns that this insn links to
! explicitly references CC0. If so, try this insn, that insn,
! and its predecessor if it sets CC0. */
! FOR_EACH_LOG_LINK (links, insn)
! if (NONJUMP_INSN_P (links->insn)
! && GET_CODE (PATTERN (links->insn)) == SET
! && reg_mentioned_p (cc0_rtx, SET_SRC (PATTERN
(links->insn)))
! && (prev = prev_nonnote_insn (links->insn)) != 0
! && NONJUMP_INSN_P (prev)
! && sets_cc0_p (PATTERN (prev))
! && (next = try_combine (insn, links->insn,
! prev, NULL_RTX, &new_direct_jump_p,
! last_combined_insn)) != 0)
! goto retry;
#endif
! /* Try combining an insn with two different insns whose results it
! uses. */
! FOR_EACH_LOG_LINK (links, insn)
! for (nextlinks = links->next; nextlinks;
! nextlinks = nextlinks->next)
! if ((next = try_combine (insn, links->insn,
! nextlinks->insn, NULL_RTX,
! &new_direct_jump_p,
! last_combined_insn)) != 0)
! goto retry;
!
! /* Try four-instruction combinations. */
! FOR_EACH_LOG_LINK (links, insn)
! {
! struct insn_link *next1;
! rtx link = links->insn;
! /* If the linked insn has been replaced by a note, then there
! is no point in pursuing this chain any further. */
! if (NOTE_P (link))
! continue;
! FOR_EACH_LOG_LINK (next1, link)
! {
! rtx link1 = next1->insn;
! if (NOTE_P (link1))
! continue;
! /* I0 -> I1 -> I2 -> I3. */
! FOR_EACH_LOG_LINK (nextlinks, link1)
! if ((next = try_combine (insn, link, link1,
! nextlinks->insn,
! &new_direct_jump_p,
! last_combined_insn)) != 0)
goto retry;
! /* I0, I1 -> I2, I2 -> I3. */
! for (nextlinks = next1->next; nextlinks;
! nextlinks = nextlinks->next)
! if ((next = try_combine (insn, link, link1,
! nextlinks->insn,
! &new_direct_jump_p,
! last_combined_insn)) != 0)
goto retry;
! }
! for (next1 = links->next; next1; next1 = next1->next)
! {
! rtx link1 = next1->insn;
! if (NOTE_P (link1))
! continue;
! /* I0 -> I2; I1, I2 -> I3. */
! FOR_EACH_LOG_LINK (nextlinks, link)
! if ((next = try_combine (insn, link, link1,
! nextlinks->insn,
! &new_direct_jump_p,
! last_combined_insn)) != 0)
goto retry;
! /* I0 -> I1; I1, I2 -> I3. */
! FOR_EACH_LOG_LINK (nextlinks, link1)
! if ((next = try_combine (insn, link, link1,
! nextlinks->insn,
! &new_direct_jump_p,
! last_combined_insn)) != 0)
goto retry;
! }
! }
! /* Try this insn with each REG_EQUAL note it links back to. */
! FOR_EACH_LOG_LINK (links, insn)
{
! rtx set, note;
! rtx temp = links->insn;
! if ((set = single_set (temp)) != 0
! && (note = find_reg_equal_equiv_note (temp)) != 0
! && (note = XEXP (note, 0), GET_CODE (note)) != EXPR_LIST
! /* Avoid using a register that may already been marked
! dead by an earlier instruction. */
! && ! unmentioned_reg_p (note, SET_SRC (set))
! && (GET_MODE (note) == VOIDmode
! ? SCALAR_INT_MODE_P (GET_MODE (SET_DEST (set)))
! : GET_MODE (SET_DEST (set)) == GET_MODE (note)))
{
! /* Temporarily replace the set's source with the
! contents of the REG_EQUAL note. The insn will
! be deleted or recognized by try_combine. */
! rtx orig = SET_SRC (set);
! SET_SRC (set) = note;
! i2mod = temp;
! i2mod_old_rhs = copy_rtx (orig);
! i2mod_new_rhs = copy_rtx (note);
! next = try_combine (insn, i2mod, NULL_RTX, NULL_RTX,
! &new_direct_jump_p,
! last_combined_insn);
! i2mod = NULL_RTX;
! if (next)
! goto retry;
! SET_SRC (set) = orig;
}
}
! if (!NOTE_P (insn))
! record_dead_and_set_regs (insn);
! retry:
! ;
! }
}
}
--- 1232,1477 ----
insn = next ? next : NEXT_INSN (insn))
{
next = 0;
! if (!NONDEBUG_INSN_P (insn))
! continue;
! while (last_combined_insn
! && INSN_DELETED_P (last_combined_insn))
! last_combined_insn = PREV_INSN (last_combined_insn);
! if (last_combined_insn == NULL_RTX
! || BARRIER_P (last_combined_insn)
! || BLOCK_FOR_INSN (last_combined_insn) != this_basic_block
! || DF_INSN_LUID (last_combined_insn) <= DF_INSN_LUID (insn))
! last_combined_insn = insn;
!
! /* See if we know about function return values before this
! insn based upon SUBREG flags. */
! check_promoted_subreg (insn, PATTERN (insn));
!
! /* See if we can find hardregs and subreg of pseudos in
! narrower modes. This could help turning TRUNCATEs
! into SUBREGs. */
! note_uses (&PATTERN (insn), record_truncated_values, NULL);
!
! /* Try this insn with each insn it links back to. */
!
! FOR_EACH_LOG_LINK (links, insn)
! if ((next = try_combine (insn, links->insn, NULL_RTX,
! NULL_RTX, &new_direct_jump_p,
! last_combined_insn)) != 0)
! {
! statistics_counter_event (cfun, "two-insn combine", 1);
! goto retry;
! }
!
! /* Try each sequence of three linked insns ending with this one. */
!
! if (max_combine >= 3)
! FOR_EACH_LOG_LINK (links, insn)
! {
! rtx link = links->insn;
!
! /* If the linked insn has been replaced by a note, then there
! is no point in pursuing this chain any further. */
! if (NOTE_P (link))
! continue;
!
! FOR_EACH_LOG_LINK (nextlinks, link)
! if ((next = try_combine (insn, link, nextlinks->insn,
! NULL_RTX, &new_direct_jump_p,
! last_combined_insn)) != 0)
! {
! statistics_counter_event (cfun, "three-insn combine", 1);
goto retry;
! }
! }
#ifdef HAVE_cc0
! /* Try to combine a jump insn that uses CC0
! with a preceding insn that sets CC0, and maybe with its
! logical predecessor as well.
! This is how we make decrement-and-branch insns.
! We need this special code because data flow connections
! via CC0 do not get entered in LOG_LINKS. */
!
! if (JUMP_P (insn)
! && (prev = prev_nonnote_insn (insn)) != 0
! && NONJUMP_INSN_P (prev)
! && sets_cc0_p (PATTERN (prev)))
! {
! if ((next = try_combine (insn, prev, NULL_RTX, NULL_RTX,
! &new_direct_jump_p,
! last_combined_insn)) != 0)
! goto retry;
!
! FOR_EACH_LOG_LINK (nextlinks, prev)
! if ((next = try_combine (insn, prev, nextlinks->insn,
! NULL_RTX, &new_direct_jump_p,
last_combined_insn)) != 0)
goto retry;
+ }
! /* Do the same for an insn that explicitly references CC0. */
! if (NONJUMP_INSN_P (insn)
! && (prev = prev_nonnote_insn (insn)) != 0
! && NONJUMP_INSN_P (prev)
! && sets_cc0_p (PATTERN (prev))
! && GET_CODE (PATTERN (insn)) == SET
! && reg_mentioned_p (cc0_rtx, SET_SRC (PATTERN (insn))))
! {
! if ((next = try_combine (insn, prev, NULL_RTX, NULL_RTX,
! &new_direct_jump_p,
! last_combined_insn)) != 0)
! goto retry;
!
! FOR_EACH_LOG_LINK (nextlinks, prev)
! if ((next = try_combine (insn, prev, nextlinks->insn,
! NULL_RTX, &new_direct_jump_p,
last_combined_insn)) != 0)
goto retry;
+ }
! /* Finally, see if any of the insns that this insn links to
! explicitly references CC0. If so, try this insn, that insn,
! and its predecessor if it sets CC0. */
! FOR_EACH_LOG_LINK (links, insn)
! if (NONJUMP_INSN_P (links->insn)
! && GET_CODE (PATTERN (links->insn)) == SET
! && reg_mentioned_p (cc0_rtx, SET_SRC (PATTERN (links->insn)))
! && (prev = prev_nonnote_insn (links->insn)) != 0
! && NONJUMP_INSN_P (prev)
! && sets_cc0_p (PATTERN (prev))
! && (next = try_combine (insn, links->insn,
! prev, NULL_RTX, &new_direct_jump_p,
! last_combined_insn)) != 0)
! goto retry;
#endif
! /* Try combining an insn with two different insns whose results it
! uses. */
! if (max_combine >= 3)
! FOR_EACH_LOG_LINK (links, insn)
! for (nextlinks = links->next; nextlinks;
! nextlinks = nextlinks->next)
! if ((next = try_combine (insn, links->insn,
! nextlinks->insn, NULL_RTX,
! &new_direct_jump_p,
! last_combined_insn)) != 0)
! {
! statistics_counter_event (cfun, "three-insn combine", 1);
! goto retry;
! }
! /* Try four-instruction combinations. */
! if (max_combine >= 4)
! FOR_EACH_LOG_LINK (links, insn)
! {
! struct insn_link *next1;
! rtx link = links->insn;
!
! /* If the linked insn has been replaced by a note, then there
! is no point in pursuing this chain any further. */
! if (NOTE_P (link))
! continue;
!
! FOR_EACH_LOG_LINK (next1, link)
! {
! rtx link1 = next1->insn;
! if (NOTE_P (link1))
! continue;
! /* I0 -> I1 -> I2 -> I3. */
! FOR_EACH_LOG_LINK (nextlinks, link1)
! if ((next = try_combine (insn, link, link1,
! nextlinks->insn,
! &new_direct_jump_p,
! last_combined_insn)) != 0)
! {
! statistics_counter_event (cfun, "four-insn combine",
1);
goto retry;
! }
! /* I0, I1 -> I2, I2 -> I3. */
! for (nextlinks = next1->next; nextlinks;
! nextlinks = nextlinks->next)
! if ((next = try_combine (insn, link, link1,
! nextlinks->insn,
! &new_direct_jump_p,
! last_combined_insn)) != 0)
! {
! statistics_counter_event (cfun, "four-insn combine",
1);
goto retry;
! }
! }
! for (next1 = links->next; next1; next1 = next1->next)
! {
! rtx link1 = next1->insn;
! if (NOTE_P (link1))
! continue;
! /* I0 -> I2; I1, I2 -> I3. */
! FOR_EACH_LOG_LINK (nextlinks, link)
! if ((next = try_combine (insn, link, link1,
! nextlinks->insn,
! &new_direct_jump_p,
! last_combined_insn)) != 0)
! {
! statistics_counter_event (cfun, "four-insn combine",
1);
goto retry;
! }
! /* I0 -> I1; I1, I2 -> I3. */
! FOR_EACH_LOG_LINK (nextlinks, link1)
! if ((next = try_combine (insn, link, link1,
! nextlinks->insn,
! &new_direct_jump_p,
! last_combined_insn)) != 0)
! {
! statistics_counter_event (cfun, "four-insn combine",
1);
goto retry;
! }
! }
! }
! /* Try this insn with each REG_EQUAL note it links back to. */
! FOR_EACH_LOG_LINK (links, insn)
! {
! rtx set, note;
! rtx temp = links->insn;
! if ((set = single_set (temp)) != 0
! && (note = find_reg_equal_equiv_note (temp)) != 0
! && (note = XEXP (note, 0), GET_CODE (note)) != EXPR_LIST
! /* Avoid using a register that may already been marked
! dead by an earlier instruction. */
! && ! unmentioned_reg_p (note, SET_SRC (set))
! && (GET_MODE (note) == VOIDmode
! ? SCALAR_INT_MODE_P (GET_MODE (SET_DEST (set)))
! : GET_MODE (SET_DEST (set)) == GET_MODE (note)))
{
! /* Temporarily replace the set's source with the
! contents of the REG_EQUAL note. The insn will
! be deleted or recognized by try_combine. */
! rtx orig = SET_SRC (set);
! SET_SRC (set) = note;
! i2mod = temp;
! i2mod_old_rhs = copy_rtx (orig);
! i2mod_new_rhs = copy_rtx (note);
! next = try_combine (insn, i2mod, NULL_RTX, NULL_RTX,
! &new_direct_jump_p,
! last_combined_insn);
! i2mod = NULL_RTX;
! if (next)
{
! statistics_counter_event (cfun, "insn-with-note combine",
1);
! goto retry;
}
+ SET_SRC (set) = orig;
}
+ }
! if (!NOTE_P (insn))
! record_dead_and_set_regs (insn);
! retry:
! ;
}
}
Index: gcc/doc/invoke.texi
===================================================================
*** gcc/doc/invoke.texi (revision 212548)
--- gcc/doc/invoke.texi (working copy)
*************** The maximum size measured as number of R
*** 10006,10011 ****
--- 10006,10015 ----
in combiner for a pseudo register as last known value of that register. The
default
is 10000.
+ @item max-combine-insns
+ The maximum number of instructions the RTL combiner tries to combine.
+ The default value is 2 at @option{-Og} and 4 otherwise.
+
@item integer-share-limit
Small integer constants can use a shared data structure, reducing the
compiler's memory usage and increasing its speed. This sets the maximum
