public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH v3] combine: perform jump threading at the end
@ 2018-09-10 10:59 Ilya Leoshkevich
  2018-09-14 21:37 ` Segher Boessenkool
  0 siblings, 1 reply; 8+ messages in thread
From: Ilya Leoshkevich @ 2018-09-10 10:59 UTC (permalink / raw)
  To: gcc-patches; +Cc: krebbel, rdapp, richard.guenther, segher, Ilya Leoshkevich

Consider the following RTL:

(code_label 11 10 26 4 2 (nil) [1 uses])
(note 26 11 12 4 [bb 4] NOTE_INSN_BASIC_BLOCK)
(insn 12 26 15 4 (set (reg:SI 65)
        (if_then_else:SI (eq (reg:CCZ 33 %cc)
                (const_int 0 [0]))
            (const_int 1 [0x1])
            (const_int 0 [0]))) "pr80080-4.c":9 1674 {*movsicc})
(insn 15 12 16 4 (parallel [
            (set (reg:CCZ 33 %cc)
                (compare:CCZ (reg:SI 65)
                    (const_int 0 [0])))
            (clobber (scratch:SI))
        ]) "pr80080-4.c":9 1216 {*tstsi_cconly_extimm})
(jump_insn 16 15 17 4 (set (pc)
        (if_then_else (ne (reg:CCZ 33 %cc)
                (const_int 0 [0]))
            (label_ref:DI 23)
            (pc))) "pr80080-4.c":9 1897 {*cjump_64})

Combine simplifies this into:

(code_label 11 10 26 4 2 (nil) [1 uses])
(note 26 11 12 4 [bb 4] NOTE_INSN_BASIC_BLOCK)
(note 12 26 15 4 NOTE_INSN_DELETED)
(note 15 12 16 4 NOTE_INSN_DELETED)
(jump_insn 16 15 17 4 (set (pc)
        (if_then_else (eq (reg:CCZ 33 %cc)
                (const_int 0 [0]))
            (label_ref:DI 23)
            (pc))) "pr80080-4.c":9 1897 {*cjump_64})

opening up the possibility to perform jump threading.  Since this
happens infrequently, perform jump threading only when there is a
changed basic block, whose sole side effect is a trailing jump.

Also remove redundant usage of TV_JUMP, because rebuild_jump_labels ()
and cleanup_cfg () already have their own timevars.

gcc/ChangeLog:

2018-09-05  Ilya Leoshkevich  <iii@linux.ibm.com>

	PR target/80080
	* combine.c (is_single_jump_bb): New function.
	(struct combine_summary): New struct.
	(combine_instructions): Instead of returning
	new_direct_jump_p, fill struct combine_summary. In addition
	to the existing new_direct_jump_p, it contains a new
	new_single_jump_p field, which controls whether or not
	jump threading should be performed after combine.
	(rest_of_handle_combine): Perform jump threading if there is
	a possibility that it would be profitable.  Remove redundant
	usage of TV_JUMP.

gcc/testsuite/ChangeLog:

2018-09-05  Ilya Leoshkevich  <iii@linux.ibm.com>

	PR target/80080
	* gcc.target/s390/pr80080-4.c: New test.
---
 gcc/combine.c                             | 89 +++++++++++++++++++----
 gcc/testsuite/gcc.target/s390/pr80080-4.c | 16 ++++
 2 files changed, 89 insertions(+), 16 deletions(-)
 create mode 100644 gcc/testsuite/gcc.target/s390/pr80080-4.c

diff --git a/gcc/combine.c b/gcc/combine.c
index a2649b6d5a1..65f5d7d092b 100644
--- a/gcc/combine.c
+++ b/gcc/combine.c
@@ -1139,13 +1139,42 @@ insn_a_feeds_b (rtx_insn *a, rtx_insn *b)
   return false;
 }
 \f
+/* Return true iff the only side effect of BB is its trailing jump_insn.  */
+
+static bool
+is_single_jump_bb (basic_block bb)
+{
+  rtx_insn *end = BB_END (bb);
+  rtx_insn *insn;
+
+  if (!JUMP_P (end))
+    return false;
+
+  for (insn = BB_HEAD (bb); insn != end; insn = NEXT_INSN (insn))
+    if (INSN_P (insn) && side_effects_p (PATTERN (insn)))
+      return false;
+  return true;
+}
+
+/* Summary of changes performed by the combiner.  */
+struct combine_summary {
+  /* True if the combiner has turned an indirect jump instruction into a direct
+     jump.  */
+  bool new_direct_jump_p;
+
+  /* True if the combiner changed at least one basic block in a way that it
+     ended up containing a single jump_insn.  */
+  bool new_single_jump_p;
+};
+
 /* Main entry point for combiner.  F is the first insn of the function.
    NREGS is the first unused pseudo-reg number.
 
-   Return nonzero if the combiner has turned an indirect jump
-   instruction into a direct jump.  */
-static int
-combine_instructions (rtx_insn *f, unsigned int nregs)
+   If performed changes satisfy certain criteria, set the corresponding fields
+   of SUMMARY to true.  */
+static void
+combine_instructions (rtx_insn *f, unsigned int nregs,
+		      struct combine_summary *summary)
 {
   rtx_insn *insn, *next;
   rtx_insn *prev;
@@ -1158,7 +1187,7 @@ combine_instructions (rtx_insn *f, unsigned int nregs)
   for (first = f; first && !NONDEBUG_INSN_P (first); )
     first = NEXT_INSN (first);
   if (!first)
-    return 0;
+    return;
 
   combine_attempts = 0;
   combine_merges = 0;
@@ -1251,6 +1280,7 @@ combine_instructions (rtx_insn *f, unsigned int nregs)
   FOR_EACH_BB_FN (this_basic_block, cfun)
     {
       rtx_insn *last_combined_insn = NULL;
+      bool bb_changed = false;
 
       /* Ignore instruction combination in basic blocks that are going to
 	 be removed as unreachable anyway.  See PR82386.  */
@@ -1302,6 +1332,7 @@ combine_instructions (rtx_insn *f, unsigned int nregs)
 				     last_combined_insn)) != 0)
 	      {
 		statistics_counter_event (cfun, "two-insn combine", 1);
+		bb_changed = true;
 		goto retry;
 	      }
 
@@ -1323,6 +1354,7 @@ combine_instructions (rtx_insn *f, unsigned int nregs)
 					   last_combined_insn)) != 0)
 		    {
 		      statistics_counter_event (cfun, "three-insn combine", 1);
+		      bb_changed = true;
 		      goto retry;
 		    }
 	      }
@@ -1349,7 +1381,10 @@ combine_instructions (rtx_insn *f, unsigned int nregs)
 		  if ((next = try_combine (insn, prev, nextlinks->insn,
 					   NULL, &new_direct_jump_p,
 					   last_combined_insn)) != 0)
-		    goto retry;
+		    {
+		      bb_changed = true;
+		      goto retry;
+		    }
 	    }
 
 	  /* Do the same for an insn that explicitly references CC0.  */
@@ -1363,13 +1398,19 @@ combine_instructions (rtx_insn *f, unsigned int nregs)
 	      if ((next = try_combine (insn, prev, NULL, NULL,
 				       &new_direct_jump_p,
 				       last_combined_insn)) != 0)
-		goto retry;
+		{
+		  bb_changed = true;
+		  goto retry;
+		}
 
 	      FOR_EACH_LOG_LINK (nextlinks, prev)
 		  if ((next = try_combine (insn, prev, nextlinks->insn,
 					   NULL, &new_direct_jump_p,
 					   last_combined_insn)) != 0)
+		  {
+		    bb_changed = true;
 		    goto retry;
+		  }
 	    }
 
 	  /* Finally, see if any of the insns that this insn links to
@@ -1387,7 +1428,10 @@ combine_instructions (rtx_insn *f, unsigned int nregs)
 		    && (next = try_combine (insn, links->insn,
 					    prev, NULL, &new_direct_jump_p,
 					    last_combined_insn)) != 0)
-		  goto retry;
+		  {
+		    bb_changed = true;
+		    goto retry;
+		  }
 	    }
 
 	  /* Try combining an insn with two different insns whose results it
@@ -1403,6 +1447,7 @@ combine_instructions (rtx_insn *f, unsigned int nregs)
 
 		  {
 		    statistics_counter_event (cfun, "three-insn combine", 1);
+		    bb_changed = true;
 		    goto retry;
 		  }
 
@@ -1431,6 +1476,7 @@ combine_instructions (rtx_insn *f, unsigned int nregs)
 					       last_combined_insn)) != 0)
 			{
 			  statistics_counter_event (cfun, "four-insn combine", 1);
+			  bb_changed = true;
 			  goto retry;
 			}
 		    /* I0, I1 -> I2, I2 -> I3.  */
@@ -1442,6 +1488,7 @@ combine_instructions (rtx_insn *f, unsigned int nregs)
 					       last_combined_insn)) != 0)
 			{
 			  statistics_counter_event (cfun, "four-insn combine", 1);
+			  bb_changed = true;
 			  goto retry;
 			}
 		  }
@@ -1459,6 +1506,7 @@ combine_instructions (rtx_insn *f, unsigned int nregs)
 					       last_combined_insn)) != 0)
 			{
 			  statistics_counter_event (cfun, "four-insn combine", 1);
+			  bb_changed = true;
 			  goto retry;
 			}
 		    /* I0 -> I1; I1, I2 -> I3.  */
@@ -1469,6 +1517,7 @@ combine_instructions (rtx_insn *f, unsigned int nregs)
 					       last_combined_insn)) != 0)
 			{
 			  statistics_counter_event (cfun, "four-insn combine", 1);
+			  bb_changed = true;
 			  goto retry;
 			}
 		  }
@@ -1510,6 +1559,7 @@ combine_instructions (rtx_insn *f, unsigned int nregs)
 		  if (next)
 		    {
 		      statistics_counter_event (cfun, "insn-with-note combine", 1);
+		      bb_changed = true;
 		      goto retry;
 		    }
 		  SET_SRC (set) = orig_src;
@@ -1523,6 +1573,10 @@ combine_instructions (rtx_insn *f, unsigned int nregs)
 retry:
 	  ;
 	}
+
+      if (flag_thread_jumps)
+	summary->new_single_jump_p
+	    |= bb_changed && is_single_jump_bb (this_basic_block);
     }
 
   default_rtl_profile ();
@@ -1557,7 +1611,7 @@ retry:
   /* Make recognizer allow volatile MEMs again.  */
   init_recog ();
 
-  return new_direct_jump_p;
+  summary->new_direct_jump_p = new_direct_jump_p;
 }
 
 /* Wipe the last_xxx fields of reg_stat in preparation for another pass.  */
@@ -14939,7 +14993,7 @@ dump_combine_total_stats (FILE *file)
 static unsigned int
 rest_of_handle_combine (void)
 {
-  int rebuild_jump_labels_after_combine;
+  struct combine_summary summary;
 
   df_set_flags (DF_LR_RUN_DCE + DF_DEFER_INSN_RESCAN);
   df_note_add_problem ();
@@ -14948,22 +15002,25 @@ rest_of_handle_combine (void)
   regstat_init_n_sets_and_refs ();
   reg_n_sets_max = max_reg_num ();
 
-  rebuild_jump_labels_after_combine
-    = combine_instructions (get_insns (), max_reg_num ());
+  memset (&summary, 0, sizeof (summary));
+  combine_instructions (get_insns (), max_reg_num (), &summary);
 
   /* Combining insns may have turned an indirect jump into a
      direct jump.  Rebuild the JUMP_LABEL fields of jumping
      instructions.  */
-  if (rebuild_jump_labels_after_combine)
+  if (summary.new_direct_jump_p)
     {
       if (dom_info_available_p (CDI_DOMINATORS))
 	free_dominance_info (CDI_DOMINATORS);
-      timevar_push (TV_JUMP);
       rebuild_jump_labels (get_insns ());
-      cleanup_cfg (0);
-      timevar_pop (TV_JUMP);
     }
 
+  /* Combining insns can change basic blocks in a way that they end up
+     containing a single jump_insn.  This creates an opportunity to improve
+     code with jump threading.  */
+  if (summary.new_direct_jump_p || summary.new_single_jump_p)
+      cleanup_cfg (summary.new_single_jump_p ? CLEANUP_THREADING : 0);
+
   regstat_free_n_sets_and_refs ();
   return 0;
 }
diff --git a/gcc/testsuite/gcc.target/s390/pr80080-4.c b/gcc/testsuite/gcc.target/s390/pr80080-4.c
new file mode 100644
index 00000000000..91d31ec7845
--- /dev/null
+++ b/gcc/testsuite/gcc.target/s390/pr80080-4.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-march=z196 -O2" } */
+
+extern void bar(int *mem);
+
+void foo4(int *mem)
+{
+  int oldval = 0;
+  if (!__atomic_compare_exchange_n (mem, (void *) &oldval, 1,
+				    1, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
+    {
+      bar (mem);
+    }
+}
+
+/* { dg-final { scan-assembler "\n\tlt\t.*\n\tjne\t(\\.L\\d+)\n(.*\n)*\tcs\t.*\n\tber\t%r14\n\\1:\n\tjg\tbar\n" } } */
-- 
2.18.0

^ permalink raw reply	[flat|nested] 8+ messages in thread
end of thread, other threads:[~2018-09-18 14:31 UTC | newest]

Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-09-10 10:59 [PATCH v3] combine: perform jump threading at the end Ilya Leoshkevich
2018-09-14 21:37 ` Segher Boessenkool
2018-09-17  8:54   ` Ilya Leoshkevich
2018-09-17 17:24     ` Segher Boessenkool
2018-09-18 10:27       ` Ilya Leoshkevich
2018-09-18 14:31         ` Segher Boessenkool
2018-09-18 11:44       ` Ilya Leoshkevich
2018-09-18 14:56         ` Segher Boessenkool

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).