rtl-ssa: Add missing live-out uses [PR121619]

This PR is another bug in the rtl-ssa code to manage live-out uses.
It seems that this didn't get much coverage until recently.

In the testcase, late-combine first removed a register-to-register
move by substituting into all uses, some of which were in other EBBs.
This was done after checking make_uses_available, which (as expected)
says that single dominating definitions are available everywhere
that the definition dominates.  But the update failed to add
appropriate live-out uses, so a later parallelisation attempt
tried to move the new destination into a later block.

gcc/
	PR rtl-optimization/121619
	* rtl-ssa/functions.h (function_info::commit_make_use_available):
	Declare.
	* rtl-ssa/blocks.cc (function_info::commit_make_use_available):
	New function.
	* rtl-ssa/changes.cc (function_info::apply_changes_to_insn): Use it.

gcc/testsuite/
	PR rtl-optimization/121619
	* gcc.dg/pr121619.c: New test.

4 files changed, 74 insertions, 1 deletions

diff --git a/gcc/rtl-ssa/blocks.cc b/gcc/rtl-ssa/blocks.cc
index a57b9e1..568f965 100644
--- a/gcc/rtl-ssa/blocks.cc
+++ b/gcc/rtl-ssa/blocks.cc
@@ -359,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)
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 27cbc18..ba80507 100644
--- a/gcc/rtl-ssa/functions.h
+++ b/gcc/rtl-ssa/functions.h
@@ -309,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/testsuite/gcc.dg/pr121619.c b/gcc/testsuite/gcc.dg/pr121619.c
new file mode 100644
index 0000000..a63896d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr121619.c
@@ -0,0 +1,33 @@
+/* { dg-do run } */
+/* { dg-options "-O3 -fno-gcse -fno-tree-ter -fno-guess-branch-probability -fno-forward-propagate" } */
+
+int printf(const char *, ...);
+long a, c, d;
+char b;
+int main() {
+f : {
+  short g = 100;
+  int h = 1;
+  while (1) {
+    char i = 0;
+    if (a)
+      i = h = -b;
+    short j = g;
+    c = h ^ g;
+    g = ~(-h / c + 1);
+    if (b > 6) {
+      a = g && -1;
+      goto f;
+    }
+    if (j < 100)
+      printf("%ld\n", d);
+    if (g - 1)
+      break;
+    b = i;
+  }
+  int k = 2L % g;
+  if (k)
+    goto f;
+  }
+  return 0;
+}