Add virtual operand global liveness computation class

The following adds an on-demand global liveness computation class
computing and caching the live-out virtual operand of basic blocks
and answering live-out, live-in and live-on-edge queries.  The flow
is optimized for the intended use in code sinking which will query
live-in and possibly can be optimized further when the originating
query is for live-out.

The code relies on up-to-date immediate dominator information and
on an unchanging virtual operand state.

	* tree-ssa-live.h (class virtual_operand_live): New.
	* tree-ssa-live.cc (virtual_operand_live::init): New.
	(virtual_operand_live::get_live_in): Likewise.
	(virtual_operand_live::get_live_out): Likewise.

2 files changed, 102 insertions, 0 deletions

diff --git a/gcc/tree-ssa-live.cc b/gcc/tree-ssa-live.cc
index 1be9295..c9c2fde 100644
--- a/gcc/tree-ssa-live.cc
+++ b/gcc/tree-ssa-live.cc
@@ -43,6 +43,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "optinfo.h"
 #include "gimple-walk.h"
 #include "cfganal.h"
+#include "tree-cfg.h"
 
 static void verify_live_on_entry (tree_live_info_p);
 
@@ -1651,3 +1652,77 @@ verify_live_on_entry (tree_live_info_p live)
     }
   gcc_assert (num <= 0);
 }
+
+
+/* Virtual operand liveness analysis data init.  */
+
+void
+virtual_operand_live::init ()
+{
+  liveout = XCNEWVEC (tree, last_basic_block_for_fn (cfun) + 1);
+  liveout[ENTRY_BLOCK] = ssa_default_def (cfun, gimple_vop (cfun));
+}
+
+/* Compute live-in of BB from cached live-out.  */
+
+tree
+virtual_operand_live::get_live_in (basic_block bb)
+{
+  /* A virtual PHI is a convenient cache for live-in.  */
+  gphi *phi = get_virtual_phi (bb);
+  if (phi)
+    return gimple_phi_result (phi);
+
+  if (!liveout)
+    init ();
+
+  /* Since we don't have a virtual PHI we can now pick any of the
+     incoming edges liveout value.  All returns from the function have
+     a virtual use forcing generation of virtual PHIs.  */
+  edge_iterator ei;
+  edge e;
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    if (liveout[e->src->index])
+      {
+	if (EDGE_PRED (bb, 0) != e)
+	  liveout[EDGE_PRED (bb, 0)->src->index] = liveout[e->src->index];
+	return liveout[e->src->index];
+      }
+
+  /* Since virtuals are in SSA form at most the immediate dominator can
+     contain the definition of the live version.  Skipping to that deals
+     with CFG cycles as well.  */
+  return get_live_out (get_immediate_dominator (CDI_DOMINATORS, bb));
+}
+
+/* Compute live-out of BB.  */
+
+tree
+virtual_operand_live::get_live_out (basic_block bb)
+{
+  if (!liveout)
+    init ();
+
+  if (liveout[bb->index])
+    return liveout[bb->index];
+
+  tree lo = NULL_TREE;
+  for (auto gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
+    {
+      gimple *stmt = gsi_stmt (gsi);
+      if (gimple_vdef (stmt))
+	{
+	  lo = gimple_vdef (stmt);
+	  break;
+	}
+      if (gimple_vuse (stmt))
+	{
+	  lo = gimple_vuse (stmt);
+	  break;
+	}
+    }
+  if (!lo)
+    lo = get_live_in (bb);
+  liveout[bb->index] = lo;
+  return lo;
+}
diff --git a/gcc/tree-ssa-live.h b/gcc/tree-ssa-live.h
index de665d6..a760444 100644
--- a/gcc/tree-ssa-live.h
+++ b/gcc/tree-ssa-live.h
@@ -328,4 +328,31 @@ make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
   bitmap_set_bit (live->global, p);
 }
 
+
+/* On-demand virtual operand global live analysis.  There is at most
+   a single virtual operand live at a time, the following computes and
+   caches the virtual operand live at the exit of a basic block
+   supporting related live-in and live-on-edge queries.  */
+
+class virtual_operand_live
+{
+public:
+  virtual_operand_live() : liveout (nullptr) {}
+  ~virtual_operand_live()
+  {
+    if (liveout)
+      free (liveout);
+  }
+
+  tree get_live_in (basic_block bb);
+  tree get_live_out (basic_block bb);
+  tree get_live_on_edge (edge e) { return get_live_out (e->src); }
+
+private:
+  void init ();
+
+  tree *liveout;
+};
+
+
 #endif /* _TREE_SSA_LIVE_H  */