On Mon, May 28, 2018 at 12:22 PM, Richard Biener
<richard.guent...@gmail.com> wrote:
> On Fri, May 18, 2018 at 1:57 PM Bin.Cheng <amker.ch...@gmail.com> wrote:
>
>> On Fri, May 4, 2018 at 5:23 PM, Bin Cheng <bin.ch...@arm.com> wrote:
>> > Hi,
>> > Based on previous patch, this one implements live range, reg pressure
> computation
>> > class in tree-ssa-live.c. The user would only need to instantiate the
> class and
>> > call the computation interface as in next patch.
>> > During the work, I think it's also worthwhile to classify all live
> range and coalesce
>> > data structures and algorithms in the future.
>> >
>> > Bootstrap and test on x86_64 and AArch64 ongoing. Any comments?
>
>> Updated patch in line with change of previous patch.
Thanks for reviewing.
>
> So I see you do not want to expose the magic '16' in pressure_threshold to
> the
> user because in theory the target should provide enough information. But
> why
> need it at all? Also
Typically, we consider register pressure high if it exceeds available registers,
while for extreme targets, for example, with only 4~5 available registers, do we
consider a loop region with register pressure 8 as high? It could be
a very small
loop and if we do, that would basically disable optimizations. So
here the number
is used as an absolute criteria for high register pressure. Given
max_pressure is
computed on GIMPLE and there might be scheduling issue exaggerating register
pressure, I chose this relative big number (16).
>
> + /* Calculate maximum reg pressure information for region and store it in
> + MAX_PRESSURE. Return true if the reg pressure is high. */
> + bool calculate_pressure (unsigned *max_pressure);
>
> it looks like you expect a [N_REG_CLASSES] sized output array here, that's
> not
> clear from the documentation.
>
> The output information is a little shallow - I'd be interested in the
> number of
> live through region regs being separated from live in / out. That is, can
> you
> add additional outputs to the above and thus make it more like
>
> bool calculate_pressure (unsigned max_pressure[], unsigned live_in[],
> unsigned live_out[], unsigned live_through[]);
Done.
>
> with the numbers being on the region?
>
> It also seems to be a fire-and-forget class so I wonder why liveness is not
> computed at construction
> time so intermediate data can be freed and only the results stored?
>
> stmt_lr_info -> id seems to be unused? In fact what is the point of this
> structure (and the per stmt bitmap)?
> It looks write-only to me...
Yes, this was legacy code from my draft patch where it computes live ranges
for within-block scheduling. Now it's all removed/simplified.
Any comment on this version? Also I will withhold it till ISA
interface exposing issue addressed.
Thanks,
bin
2018-05-29 Bin Cheng <bin.ch...@arm.com>
* tree-ssa-live.c (memmodel.h, ira.h, tree-ssa-coalesce.h): Include.
(lr_region::update_live_range_by_stmt): New.
(lr_region::count_pressure_for_live_ranges): New.
(lr_region::calculate_coalesced_pressure): New.
(lr_region::calculate_pressure): New.
* tree-ssa-live.h (class lr_region): New class.
From a51dc3bde02a24d4a6d17b5f14d13859a8766824 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binch...@e108451-lin.cambridge.arm.com>
Date: Fri, 4 May 2018 09:42:04 +0100
Subject: [PATCH 5/6] region-reg-pressure-20180528
---
gcc/tree-ssa-live.c | 140 ++++++++++++++++++++++++++++++++++++++++++++++++++++
gcc/tree-ssa-live.h | 84 +++++++++++++++++++++++++++++++
2 files changed, 224 insertions(+)
diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c
index 7447f7a..830b050 100644
--- a/gcc/tree-ssa-live.c
+++ b/gcc/tree-ssa-live.c
@@ -23,6 +23,8 @@ along with GCC; see the file COPYING3. If not see
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
+#include "memmodel.h"
+#include "ira.h"
#include "tree.h"
#include "gimple.h"
#include "timevar.h"
@@ -34,6 +36,7 @@ along with GCC; see the file COPYING3. If not see
#include "tree-dfa.h"
#include "dumpfile.h"
#include "tree-ssa-live.h"
+#include "tree-ssa-coalesce.h"
#include "debug.h"
#include "tree-ssa.h"
#include "ipa-utils.h"
@@ -1200,6 +1203,143 @@ calculate_live_ranges (var_map map, bool want_livein)
}
+/* Implementation for class lr_region. */
+
+void
+lr_region::update_live_range_by_stmt (gimple *stmt, bitmap live_ranges,
+ unsigned pressure[])
+{
+ int p;
+ tree var;
+ ssa_op_iter iter;
+
+ FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_DEF)
+ {
+ p = var_to_partition (m_varmap, var);
+ gcc_assert (p != NO_PARTITION);
+ if (bitmap_clear_bit (live_ranges, p))
+ pressure[ira_mode_classes[TYPE_MODE (TREE_TYPE (var))]]--;
+ }
+ FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
+ {
+ p = var_to_partition (m_varmap, var);
+ gcc_assert (p != NO_PARTITION);
+ if (bitmap_set_bit (live_ranges, p))
+ pressure[ira_mode_classes[TYPE_MODE (TREE_TYPE (var))]]++;
+ }
+}
+
+void
+lr_region::count_pressure_for_live_ranges (bitmap live_ranges,
+ unsigned pressure[])
+{
+ unsigned i, reg_class;
+ bitmap_iterator bi;
+
+ memset (pressure, 0, sizeof (unsigned) * N_REG_CLASSES);
+ EXECUTE_IF_SET_IN_BITMAP (live_ranges, 0, i, bi)
+ {
+ tree var = partition_to_var (m_varmap, i);
+ reg_class = ira_mode_classes[TYPE_MODE (TREE_TYPE (var))];
+ pressure[reg_class]++;
+ }
+}
+
+void
+lr_region::calculate_coalesced_pressure ()
+{
+ unsigned i, j, pressure[N_REG_CLASSES];
+ bitmap_iterator bi;
+ gimple_stmt_iterator bsi;
+ auto_bitmap live_ranges, live_in, live_out;
+ bitmap bbs = get_bbs ();
+
+ memset (m_pressure, 0, sizeof (unsigned) * N_REG_CLASSES);
+ EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi)
+ {
+ basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
+
+ if (m_in && is_region_entry (bb))
+ bitmap_ior_into (live_in, &m_liveinfo->livein[bb->index]);
+ if (m_out && is_region_exit (bb))
+ bitmap_ior_into (live_out, &m_liveinfo->liveout[bb->index]);
+
+ bitmap_copy (live_ranges, &m_liveinfo->liveout[bb->index]);
+ count_pressure_for_live_ranges (live_ranges, pressure);
+
+ for (bsi = gsi_last_bb (bb); !gsi_end_p (bsi); gsi_prev (&bsi))
+ {
+ gimple *stmt = gsi_stmt (bsi);
+ /* No need to compute live range information for debug stmt. */
+ if (is_gimple_debug (stmt))
+ continue;
+
+ for (j = 0; j < N_REG_CLASSES; j++)
+ if (pressure[j] > m_pressure[j])
+ m_pressure[j] = pressure[j];
+
+ update_live_range_by_stmt (stmt, live_ranges, pressure);
+ }
+ }
+
+ if (m_in)
+ count_pressure_for_live_ranges (live_in, m_in);
+ if (m_out)
+ count_pressure_for_live_ranges (live_out, m_out);
+ if (m_through)
+ {
+ bitmap_and_into (live_in, live_out);
+ count_pressure_for_live_ranges (live_in, m_through);
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Reg Pressure: \tMax.\tIn\tOut\tThrough\n");
+ for (i = 0; i < N_REG_CLASSES; ++i)
+ if (m_pressure[i] != 0)
+ fprintf (dump_file, " %s: \t%d\t%d\t%d\t%d\n",
+ reg_class_names[i], m_pressure[i],
+ (m_in != NULL) ? m_in[i] : -1,
+ (m_out != NULL) ? m_out[i] : -1,
+ (m_through != NULL) ? m_through[i] : -1);
+ }
+}
+
+bool
+lr_region::calculate_pressure ()
+{
+ /* Save flag_tree_coalesce_vars. */
+ bool saved_flag_tree_coalesce_vars = flag_tree_coalesce_vars;
+
+ m_varmap = init_var_map (num_ssa_names, m_loop);
+
+ /* Coalesce SSA variables. For computing live ranges, we do want to coalesce
+ versions of different user-defined variables. */
+ flag_tree_coalesce_vars = true;
+ coalesce_ssa_name (m_varmap);
+ /* Restore flag_tree_coalesce_vars. */
+ flag_tree_coalesce_vars = saved_flag_tree_coalesce_vars;
+
+ partition_view_normal (m_varmap);
+
+ /* Calculate live ranges for region based on coalesced variables. */
+ m_liveinfo = calculate_live_ranges (m_varmap, true);
+
+ /* Calculate register pressure. */
+ calculate_coalesced_pressure ();
+
+ delete_tree_live_info (m_liveinfo);
+ delete_var_map (m_varmap);
+
+ for (unsigned k = 0; k < N_REG_CLASSES; k++)
+ if (m_pressure[k] >= pressure_threshold ()
+ && m_pressure[k] > target_avail_regs[k])
+ return true;
+
+ return false;
+}
+
+
/* Output partition map MAP to file F. */
void
diff --git a/gcc/tree-ssa-live.h b/gcc/tree-ssa-live.h
index 9aa5418..b77d7a7 100644
--- a/gcc/tree-ssa-live.h
+++ b/gcc/tree-ssa-live.h
@@ -323,4 +323,88 @@ make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
bitmap_set_bit (live->global, p);
}
+/* Live range region class. Only loop region is supported for now. */
+class lr_region
+{
+public:
+ lr_region (struct loop *loop, unsigned pressure[], unsigned in[],
+ unsigned out[], unsigned through[])
+ : m_loop (loop), m_varmap (NULL), m_liveinfo (NULL),
+ m_pressure (pressure), m_in (in), m_out (out), m_through (through)
+ {
+ if (m_in == NULL || m_out == NULL)
+ m_through = NULL;
+ }
+ ~lr_region () { }
+
+ /* Calculate maximum reg pressure information for region. Return true if
+ the reg pressure is high. */
+ bool calculate_pressure ();
+private:
+ lr_region (const lr_region&);
+ lr_region &operator= (const lr_region&);
+
+ /* Threshold for register pressure above which is considered as high. */
+ unsigned pressure_threshold () const { return 16; }
+
+ /* Return bitmap of basic blocks in this region. */
+ bitmap get_bbs () const { return m_varmap->bmp_bbs; }
+
+ /* Return true if BB is an entry block of this region. */
+ bool is_region_entry (basic_block bb)
+ {
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (!region_contains_p (m_varmap, e->src))
+ return true;
+
+ return false;
+ }
+
+ /* Return true if BB is an exit block of this region. */
+ bool is_region_exit (basic_block bb)
+ {
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (!region_contains_p (m_varmap, e->dest))
+ return true;
+
+ return false;
+ }
+
+ /* Update LIVE_RANGES bitmap and register PRESSURE information by backward
+ executing STMT. */
+ void update_live_range_by_stmt (gimple *stmt, bitmap live_range,
+ unsigned pressure[]);
+
+ /* Count register pressure per reg_class for LIVE_RANGES and record the info
+ in array PRESSURE. */
+ void count_pressure_for_live_ranges (bitmap live_ranges, unsigned pressure[]);
+
+ /* Calculate reg pressure information for REGION. */
+ void calculate_coalesced_pressure ();
+
+ /* The loop from which this region is formed. */
+ struct loop* m_loop;
+
+ /* SSA variable map for coalescing and reg pressure computation. */
+ var_map m_varmap;
+
+ /* Live range information of this region. */
+ tree_live_info_p m_liveinfo;
+
+ /* Register pressure information for this region: Max reg pressure. */
+ unsigned *m_pressure;
+ /* Reg pressure into this region. */
+ unsigned *m_in;
+ /* Reg pressure out of this region. */
+ unsigned *m_out;
+ /* Reg pressure through this region. */
+ unsigned *m_through;
+};
+
#endif /* _TREE_SSA_LIVE_H */
--
1.9.1
