[1/2] Add virtual operand global liveness computation class
Checks
Commit Message
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.
Bootstrapped and tested on x86_64-unknown-linux-gnu (with 2/2).
OK?
Thanks,
Richard.
* 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.
---
gcc/tree-ssa-live.cc | 75 ++++++++++++++++++++++++++++++++++++++++++++
gcc/tree-ssa-live.h | 27 ++++++++++++++++
2 files changed, 102 insertions(+)
@@ -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;
+}
@@ -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 */