From patchwork Mon May 23 14:40:47 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kirill Batuzov X-Patchwork-Id: 96951 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [140.186.70.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 2BE87B6FB5 for ; Tue, 24 May 2011 00:41:47 +1000 (EST) Received: from localhost ([::1]:47953 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QOWKG-0001QI-HR for incoming@patchwork.ozlabs.org; Mon, 23 May 2011 10:41:44 -0400 Received: from eggs.gnu.org ([140.186.70.92]:46082) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QOWJp-0001M8-Hr for qemu-devel@nongnu.org; Mon, 23 May 2011 10:41:18 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1QOWJn-0001M0-MU for qemu-devel@nongnu.org; Mon, 23 May 2011 10:41:17 -0400 Received: from smtp.ispras.ru ([83.149.198.202]:37590) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QOWJn-0001Ha-6U for qemu-devel@nongnu.org; Mon, 23 May 2011 10:41:15 -0400 Received: from bulbul.intra.ispras.ru (winnie.ispras.ru [83.149.198.236]) by smtp.ispras.ru (Postfix) with ESMTP id 3E8425D40BA; Mon, 23 May 2011 18:37:20 +0400 (MSD) From: Kirill Batuzov To: qemu-devel@nongnu.org Date: Mon, 23 May 2011 18:40:47 +0400 Message-Id: <1306161654-4388-2-git-send-email-batuzovk@ispras.ru> X-Mailer: git-send-email 1.7.4.1 In-Reply-To: <1306161654-4388-1-git-send-email-batuzovk@ispras.ru> References: <1306161654-4388-1-git-send-email-batuzovk@ispras.ru> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6, seldom 2.4 (older, 4) X-Received-From: 83.149.198.202 Cc: zhur@ispras.ru Subject: [Qemu-devel] [RFC][PATCH v0 1/8] Compute additional liveness information for register allocator. X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Compute next use for each operation argument. Signed-off-by: Kirill Batuzov --- tcg/tcg.c | 73 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++----- tcg/tcg.h | 4 +++ 2 files changed, 71 insertions(+), 6 deletions(-) diff --git a/tcg/tcg.c b/tcg/tcg.c index 8748c05..821ffa7 100644 --- a/tcg/tcg.c +++ b/tcg/tcg.c @@ -24,6 +24,7 @@ /* define it to use liveness analysis (better code) */ #define USE_LIVENESS_ANALYSIS +#define USE_ADVANCED_REGALLOC #include "config.h" @@ -1177,7 +1178,8 @@ static inline void tcg_la_func_end(TCGContext *s, uint8_t *dead_temps) /* liveness analysis: end of basic block: globals are live, temps are dead, local temps are live. */ -static inline void tcg_la_bb_end(TCGContext *s, uint8_t *dead_temps) +static inline void tcg_la_bb_end(TCGContext *s, uint8_t *dead_temps, + int *temp_next_use) { int i; TCGTemp *ts; @@ -1185,10 +1187,14 @@ static inline void tcg_la_bb_end(TCGContext *s, uint8_t *dead_temps) memset(dead_temps, 0, s->nb_globals); ts = &s->temps[s->nb_globals]; for(i = s->nb_globals; i < s->nb_temps; i++) { - if (ts->temp_local) + if (ts->temp_local) { dead_temps[i] = 0; - else + } else { dead_temps[i] = 1; +#ifdef USE_ADVANCED_REGALLOC + temp_next_use[i] = -1; +#endif + } ts++; } } @@ -1201,18 +1207,30 @@ static void tcg_liveness_analysis(TCGContext *s) int i, op_index, nb_args, nb_iargs, nb_oargs, arg, nb_ops; TCGOpcode op; TCGArg *args; + int *next_use_ptr = NULL; const TCGOpDef *def; uint8_t *dead_temps; + int *temp_next_use = NULL; unsigned int dead_iargs; - + gen_opc_ptr++; /* skip end */ nb_ops = gen_opc_ptr - gen_opc_buf; s->op_dead_iargs = tcg_malloc(nb_ops * sizeof(uint16_t)); + +#ifdef USE_ADVANCED_REGALLOC + nb_args = gen_opparam_ptr - gen_opparam_buf; + s->param_next_use = tcg_malloc(nb_args * sizeof(s->param_next_use[0])); + next_use_ptr = s->param_next_use + nb_args; +#endif dead_temps = tcg_malloc(s->nb_temps); memset(dead_temps, 1, s->nb_temps); +#ifdef USE_ADVANCED_REGALLOC + temp_next_use = tcg_malloc(s->nb_temps * sizeof(temp_next_use[0])); + memset(temp_next_use, -1, s->nb_temps * sizeof(temp_next_use[0])); +#endif args = gen_opparam_ptr; op_index = nb_ops - 1; @@ -1226,9 +1244,11 @@ static void tcg_liveness_analysis(TCGContext *s) nb_args = args[-1]; args -= nb_args; + next_use_ptr -= nb_args; nb_iargs = args[0] & 0xffff; nb_oargs = args[0] >> 16; args++; + next_use_ptr++; call_flags = args[nb_oargs + nb_iargs]; /* pure functions can be removed if their result is not @@ -1244,10 +1264,23 @@ static void tcg_liveness_analysis(TCGContext *s) } else { do_not_remove_call: +#ifdef USE_ADVANCED_REGALLOC + for (i = 0; i < nb_iargs + nb_oargs; i++) { + if (!dead_temps[args[i]]) { + next_use_ptr[i] = temp_next_use[args[i]]; + } else { + next_use_ptr[i] = -1; + } + } +#endif + /* output args are dead */ for(i = 0; i < nb_oargs; i++) { arg = args[i]; dead_temps[arg] = 1; +#ifdef USE_ADVANCED_REGALLOC + temp_next_use[arg] = -1; +#endif } if (!(call_flags & TCG_CALL_CONST)) { @@ -1263,36 +1296,48 @@ static void tcg_liveness_analysis(TCGContext *s) if (dead_temps[arg]) { dead_iargs |= (1 << i); } +#ifdef USE_ADVANCED_REGALLOC + temp_next_use[arg] = op_index; +#endif dead_temps[arg] = 0; } } s->op_dead_iargs[op_index] = dead_iargs; } args--; + next_use_ptr--; } break; case INDEX_op_set_label: args--; + next_use_ptr--; /* mark end of basic block */ - tcg_la_bb_end(s, dead_temps); + tcg_la_bb_end(s, dead_temps, temp_next_use); break; case INDEX_op_debug_insn_start: args -= def->nb_args; + next_use_ptr -= def->nb_args; break; case INDEX_op_nopn: nb_args = args[-1]; args -= nb_args; + next_use_ptr -= nb_args; break; case INDEX_op_discard: args--; + next_use_ptr--; /* mark the temporary as dead */ dead_temps[args[0]] = 1; +#ifdef USE_ADVANCED_REGALLOC + temp_next_use[args[0]] = -1; +#endif break; case INDEX_op_end: break; /* XXX: optimize by hardcoding common cases (e.g. triadic ops) */ default: args -= def->nb_args; + next_use_ptr -= def->nb_args; nb_iargs = def->nb_iargs; nb_oargs = def->nb_oargs; @@ -1312,15 +1357,28 @@ static void tcg_liveness_analysis(TCGContext *s) } else { do_not_remove: +#ifdef USE_ADVANCED_REGALLOC + for (i = 0; i < nb_iargs + nb_oargs; i++) { + if (!dead_temps[args[i]]) { + next_use_ptr[i] = temp_next_use[args[i]]; + } else { + next_use_ptr[i] = -1; + } + } +#endif + /* output args are dead */ for(i = 0; i < nb_oargs; i++) { arg = args[i]; dead_temps[arg] = 1; +#ifdef USE_ADVANCED_REGALLOC + temp_next_use[arg] = -1; +#endif } /* if end of basic block, update */ if (def->flags & TCG_OPF_BB_END) { - tcg_la_bb_end(s, dead_temps); + tcg_la_bb_end(s, dead_temps, temp_next_use); } else if (def->flags & TCG_OPF_CALL_CLOBBER) { /* globals are live */ memset(dead_temps, 0, s->nb_globals); @@ -1333,6 +1391,9 @@ static void tcg_liveness_analysis(TCGContext *s) if (dead_temps[arg]) { dead_iargs |= (1 << i); } +#ifdef USE_ADVANCED_REGALLOC + temp_next_use[arg] = op_index; +#endif dead_temps[arg] = 0; } s->op_dead_iargs[op_index] = dead_iargs; diff --git a/tcg/tcg.h b/tcg/tcg.h index cecef63..d8bfa2c 100644 --- a/tcg/tcg.h +++ b/tcg/tcg.h @@ -288,10 +288,14 @@ struct TCGContext { /* liveness analysis */ uint16_t *op_dead_iargs; /* for each operation, each bit tells if the corresponding input argument is dead */ + int *param_next_use; /* for each operation argument tells where it's + next used is (USE_ADVANCED_REGALLOC only) */ /* tells in which temporary a given register is. It does not take into account fixed registers */ int reg_to_temp[TCG_TARGET_NB_REGS]; + /* tells where the next use of a given reg appears */ + int reg_next_use[TCG_TARGET_NB_REGS]; TCGRegSet reserved_regs; tcg_target_long current_frame_offset; tcg_target_long frame_start;