* [PATCH 1/2] Add virtual operand global liveness computation class
@ 2023-08-02 12:44 Richard Biener
0 siblings, 0 replies; 2+ messages in thread
From: Richard Biener @ 2023-08-02 12:44 UTC (permalink / raw)
To: gcc-patches
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(+)
diff --git a/gcc/tree-ssa-live.cc b/gcc/tree-ssa-live.cc
index 1be92956cc5..c9c2fdef0e3 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 de665d6bad0..a7604448332 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 */
--
2.35.3
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [PATCH 1/2] Add virtual operand global liveness computation class
[not found] <20230802124438.663B1385842D@sourceware.org>
@ 2023-08-03 6:04 ` Jeff Law
0 siblings, 0 replies; 2+ messages in thread
From: Jeff Law @ 2023-08-03 6:04 UTC (permalink / raw)
To: Richard Biener, gcc-patches
On 8/2/23 06:44, Richard Biener via Gcc-patches wrote:
> 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.
LGTM.
jeff
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2023-08-03 6:04 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-08-02 12:44 [PATCH 1/2] Add virtual operand global liveness computation class Richard Biener
[not found] <20230802124438.663B1385842D@sourceware.org>
2023-08-03 6:04 ` Jeff Law
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).