[Bug target/101523] Huge number of combine attempts

["rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101523

--- Comment #48 from Richard Biener <rguenth at gcc dot gnu.org> ---
So another "simple" way is to keep the redundant insn walking ("it's O(1)") but
remember processsed insns and only re-process those we mark as such.

There might be a free "visited" bit on rtx_insn, who knows, the following uses
a bitmap to track this.  Likely where we set/update added_links_insn we
should mark insns for re-processing.

A worklist, if it were to be processed in instruction order, would need to
be kept ordered and DF docs say DF_INSN_LUID isn't to be trusted after
adding/removing insns.

diff --git a/gcc/combine.cc b/gcc/combine.cc
index a4479f8d836..c2f04e6b86e 100644
--- a/gcc/combine.cc
+++ b/gcc/combine.cc
@@ -1106,6 +1106,8 @@ insn_a_feeds_b (rtx_insn *a, rtx_insn *b)
   return false;
 }
 ^L
+static bitmap processed;
+
 /* Main entry point for combiner.  F is the first insn of the function.
    NREGS is the first unused pseudo-reg number.

@@ -1211,6 +1213,8 @@ combine_instructions (rtx_insn *f, unsigned int nregs)
   setup_incoming_promotions (first);
   last_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
   int max_combine = param_max_combine_insns;
+  processed = BITMAP_ALLOC (NULL);
+  bitmap_tree_view (processed);

   FOR_EACH_BB_FN (this_basic_block, cfun)
     {
@@ -1231,6 +1235,7 @@ combine_instructions (rtx_insn *f, unsigned int nregs)
        label_tick_ebb_start = label_tick;
       last_bb = this_basic_block;

+      bitmap_clear (processed);
       rtl_profile_for_bb (this_basic_block);
       for (insn = BB_HEAD (this_basic_block);
           insn != NEXT_INSN (BB_END (this_basic_block));
@@ -1240,6 +1245,9 @@ combine_instructions (rtx_insn *f, unsigned int nregs)
          if (!NONDEBUG_INSN_P (insn))
            continue;

+         if (!bitmap_set_bit (processed, INSN_UID (insn)))
+           continue;
+
          while (last_combined_insn
                 && (!NONDEBUG_INSN_P (last_combined_insn)
                     || last_combined_insn->deleted ()))
@@ -1427,6 +1435,7 @@ retry:
          ;
        }
     }
+  BITMAP_FREE (processed);

   default_rtl_profile ();
   clear_bb_flags ();
@@ -4758,6 +4767,14 @@ try_combine (rtx_insn *i3, rtx_insn *i2, rtx_insn *i1,
rtx_insn *i0,
   if (added_notes_insn && DF_INSN_LUID (added_notes_insn) < DF_INSN_LUID
(ret))
     ret = added_notes_insn;

+  bitmap_clear_bit (processed, INSN_UID (i3));
+  if (newi2pat)
+    bitmap_clear_bit (processed, INSN_UID (newi2pat));
+  if (added_links_insn)
+    bitmap_clear_bit (processed, INSN_UID (added_links_insn));
+  if (added_notes_insn)
+    bitmap_clear_bit (processed, INSN_UID (added_notes_insn));
+
   return ret;
 }
 ^L