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,
bin
>
> Thanks,
> bin
> 2018-04-27 Bin Cheng <bin.ch...@arm.com>
>
> * tree-ssa-live.c (memmodel.h, ira.h, tree-ssa-coalesce.h): Include.
> (struct stmt_lr_info, free_stmt_lr_info): New.
> (lr_region::lr_region, lr_region::~lr_region): New.
> (lr_region::create_stmt_lr_info): New.
> (lr_region::update_live_range_by_stmt): New.
> (lr_region::calculate_coalesced_pressure): New.
> (lr_region::calculate_pressure): New.
> * tree-ssa-live.h (struct stmt_lr_info): New declaration.
> (class lr_region): New class.
From 98a97779ac475f89bd7f476a7c5fd045d83b79d6 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-20180504
---
gcc/tree-ssa-live.c | 167 ++++++++++++++++++++++++++++++++++++++++++++++++++++
gcc/tree-ssa-live.h | 49 +++++++++++++++
2 files changed, 216 insertions(+)
diff --git a/gcc/tree-ssa-live.c b/gcc/tree-ssa-live.c
index 7447f7a..e432bbe 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,170 @@ calculate_live_ranges (var_map map, bool want_livein)
}
+/* Live range information for a gimple stmt. */
+struct stmt_lr_info
+{
+ /* ID of the stmt. */
+ unsigned id;
+ gimple *stmt;
+ /* Live ranges after the stmt. */
+ bitmap lr_after_stmt;
+};
+
+/* Call back function to free live range INFO of gimple STMT. */
+
+bool
+free_stmt_lr_info (gimple *const & stmt, stmt_lr_info *const &info, void *)
+{
+ gcc_assert (info->stmt == stmt);
+ if (info->lr_after_stmt != NULL)
+ BITMAP_FREE (info->lr_after_stmt);
+
+ free (info);
+ return true;
+}
+
+lr_region::lr_region (struct loop *loop)
+ : m_loop (loop),
+ m_varmap (NULL),
+ m_liveinfo (NULL),
+ m_stmtmap (new hash_map<gimple *, stmt_lr_info *> (13))
+{
+ memset (m_pressure, 0, sizeof (unsigned) * N_REG_CLASSES);
+}
+
+lr_region::~lr_region ()
+{
+ m_stmtmap->traverse<void *, free_stmt_lr_info> (NULL);
+ delete m_stmtmap;
+}
+
+struct stmt_lr_info *
+lr_region::create_stmt_lr_info (gimple *stmt)
+{
+ bool exist_p;
+ struct stmt_lr_info **slot = &m_stmtmap->get_or_insert (stmt, &exist_p);
+
+ gcc_assert (!exist_p);
+ *slot = XCNEW (struct stmt_lr_info);
+ (*slot)->stmt = stmt;
+ (*slot)->lr_after_stmt = NULL;
+ return *slot;
+}
+
+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::calculate_coalesced_pressure ()
+{
+ unsigned i, j, reg_class, pressure[N_REG_CLASSES];
+ bitmap_iterator bi, bj;
+ gimple_stmt_iterator bsi;
+ auto_bitmap live_ranges;
+ bitmap bbs = get_bbs ();
+
+ EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi)
+ {
+ basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
+ bitmap_copy (live_ranges, &m_liveinfo->liveout[bb->index]);
+
+ memset (pressure, 0, sizeof (unsigned) * N_REG_CLASSES);
+ EXECUTE_IF_SET_IN_BITMAP (live_ranges, 0, j, bj)
+ {
+ tree var = partition_to_var (m_varmap, j);
+ reg_class = ira_mode_classes[TYPE_MODE (TREE_TYPE (var))];
+ pressure[reg_class]++;
+ }
+
+ for (bsi = gsi_last_bb (bb); !gsi_end_p (bsi); gsi_prev (&bsi))
+ {
+ gimple *stmt = gsi_stmt (bsi);
+ struct stmt_lr_info *stmt_info = create_stmt_lr_info (stmt);
+ /* 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];
+
+ stmt_info->lr_after_stmt = BITMAP_ALLOC (NULL);
+ bitmap_copy (stmt_info->lr_after_stmt, live_ranges);
+ update_live_range_by_stmt (stmt, live_ranges, pressure);
+ }
+ }
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Max Reg Pressure:\n");
+ for (i = 0; i < N_REG_CLASSES; ++i)
+ if (m_pressure[i] != 0)
+ fprintf (dump_file, " %s: \t%d\n",
+ reg_class_names[i], m_pressure[i]);
+ }
+}
+
+bool
+lr_region::calculate_pressure (unsigned *max_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 ();
+
+ bool high_pressure_p = false;
+ for (unsigned k = 0; k < N_REG_CLASSES; k++)
+ {
+ if (m_pressure[k] >= pressure_threshold ()
+ && m_pressure[k] > target_avail_regs[k])
+ high_pressure_p = true;
+
+ max_pressure[k] = m_pressure[k];
+ }
+
+ delete_tree_live_info (m_liveinfo);
+ delete_var_map (m_varmap);
+
+ return high_pressure_p;
+}
+
+
/* Output partition map MAP to file F. */
void
diff --git a/gcc/tree-ssa-live.h b/gcc/tree-ssa-live.h
index 9aa5418..c1840b3 100644
--- a/gcc/tree-ssa-live.h
+++ b/gcc/tree-ssa-live.h
@@ -323,4 +323,53 @@ make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
bitmap_set_bit (live->global, p);
}
+struct stmt_lr_info;
+
+/* Live range region class. Only loop region is supported for now. */
+class lr_region
+{
+public:
+ lr_region (struct loop *loop);
+ ~lr_region ();
+
+ /* Threshold for register pressure above which is considered as high. */
+ unsigned pressure_threshold () const { return 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);
+private:
+ lr_region (const lr_region&);
+ lr_region &operator= (const lr_region&);
+
+ /* Return bitmap of basic blocks in this region. */
+ bitmap get_bbs () const { return m_varmap->bmp_bbs; }
+
+ /* Create and return live range information for STMT. */
+ struct stmt_lr_info *create_stmt_lr_info (gimple *stmt);
+
+ /* 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);
+
+ /* 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;
+
+ /* Map from gimple stmt to its live range information. */
+ hash_map<gimple *, stmt_lr_info *> *m_stmtmap;
+
+ /* Register pressure information. */
+ unsigned m_pressure[N_REG_CLASSES];
+};
+
#endif /* _TREE_SSA_LIVE_H */
--
1.9.1
