From 7b82b5da0120f0067aa5c0336cfb775798c647f4 Mon Sep 17 00:00:00 2001 From: Stan Cox Date: Wed, 5 Apr 2000 00:32:45 +0000 Subject: [PATCH] Makefile.in: Add rules for regrename.o * Makefile.in: Add rules for regrename.o * regrename.c: New file. * rtl.h (regrename_optimize): Add prototype. * toplev.c (rename_registers_dump, flag_rename_registers): New variables (compile_file, decode_d_option): Add support for -frename-registers. (rest_of_compilation): Call regrename_optimize. * config/ia64/ia64.h (HARD_REGNO_RENAME_OK, RENAME_EXTENDED_BLOCKS): New macros. From-SVN: r32916 --- gcc/ChangeLog | 11 + gcc/Makefile.in | 6 +- gcc/config/ia64/ia64.h | 19 + gcc/regrename.c | 1050 ++++++++++++++++++++++++++++++++++++++++ gcc/rtl.h | 4 + gcc/toplev.c | 20 + 6 files changed, 1109 insertions(+), 1 deletion(-) create mode 100644 gcc/regrename.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 9b8be8409f8..c6bd4dcd595 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,14 @@ +2000-04-04 Stan Cox + + * Makefile.in: Add rules for regrename.o + * regrename.c: New file. + * rtl.h (regrename_optimize): Add prototype. + * toplev.c (rename_registers_dump, flag_rename_registers): New variables + (compile_file, decode_d_option): Add support for -frename-registers. + (rest_of_compilation): Call regrename_optimize. + * config/ia64/ia64.h (HARD_REGNO_RENAME_OK, RENAME_EXTENDED_BLOCKS): + New macros. + 2000-04-04 Martin v. Löwis * Makefile (gccbug): New target. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 1ff41957de6..17271fde601 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -675,7 +675,7 @@ OBJS = diagnostic.o \ dbxout.o sdbout.o dwarfout.o dwarf2out.o xcoffout.o bitmap.o alias.o gcse.o \ integrate.o jump.o cse.o loop.o unroll.o flow.o combine.o varray.o \ regclass.o regmove.o local-alloc.o global.o reload.o reload1.o caller-save.o \ - insn-peep.o reorg.o haifa-sched.o final.o recog.o reg-stack.o \ + insn-peep.o reorg.o haifa-sched.o final.o recog.o reg-stack.o regrename.o \ insn-opinit.o insn-recog.o insn-extract.o insn-output.o insn-emit.o lcm.o \ profile.o insn-attrtab.o $(out_object_file) $(EXTRA_OBJS) convert.o \ mbchar.o dyn-string.o splay-tree.o graph.o sbitmap.o resource.o hash.o \ @@ -1653,6 +1653,10 @@ bb-reorder.o : bb-reorder.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h \ insn-config.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h \ $(RECOG_H) insn-flags.h function.h except.h $(EXPR_H) +regrename.o : regrename.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h \ + insn-config.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h \ + $(RECOG_H) function.h resource.h + $(out_object_file): $(out_file) $(CONFIG_H) $(TREE_H) ggc.h \ $(RTL_H) $(REGS_H) hard-reg-set.h real.h insn-config.h conditions.h \ insn-flags.h output.h insn-attr.h insn-codes.h system.h toplev.h function.h diff --git a/gcc/config/ia64/ia64.h b/gcc/config/ia64/ia64.h index 579cdfd5fa2..dca777477b1 100644 --- a/gcc/config/ia64/ia64.h +++ b/gcc/config/ia64/ia64.h @@ -2589,6 +2589,25 @@ do { \ /* Define to enable software floating point emulation. */ #define REAL_ARITHMETIC + +/* Register Renaming Parameters. */ + +/* A C expression that is nonzero if hard register number REGNO2 can be + considered for use as a rename register for REGNO1 */ + +#define HARD_REGNO_RENAME_OK(REGNO1,REGNO2) \ + ((! PR_REGNO_P (REGNO1) && ! PR_REGNO_P (REGNO2)) \ + ? (!call_fixed_regs [REGNO1] && !call_fixed_regs [REGNO2]) \ + ? 1 : 0 \ + : ((REGNO2) > 256 && ((REGNO2 & 1) == 0)) \ + ? 1 : 0) + +/* Define this macro if the compiler should use extended basic blocks + when renaming registers. Define this macro if the target has predicate + registers. */ + +#define RENAME_EXTENDED_BLOCKS + /* Miscellaneous Parameters. */ diff --git a/gcc/regrename.c b/gcc/regrename.c new file mode 100644 index 00000000000..816a5d262d1 --- /dev/null +++ b/gcc/regrename.c @@ -0,0 +1,1050 @@ +/* Register renaming for the GNU compiler. + Copyright (C) 2000 Free Software Foundation, Inc. + + This file is part of GNU CC. + + GNU CC is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2, or (at your option) + any later version. + + GNU CC is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with GNU CC; see the file COPYING. If not, write to + the Free Software Foundation, 59 Temple Place - Suite 330, + Boston, MA 02111-1307, USA. */ + +#include "config.h" +#include "system.h" +#include "tree.h" +#include "rtl.h" +#include "basic-block.h" +#include "insn-config.h" +#include "regs.h" +#include "hard-reg-set.h" +#include "flags.h" +#include "output.h" +#include "function.h" +#include "recog.h" +#include "resource.h" + +static const char *const reg_class_names[] = REG_CLASS_NAMES; + +/* ??? Consider a more sparse data structure? */ +typedef struct def_uses + { + /* high bound of defs and uses */ + int high_bound; + + /* 1 if insn y defines a reg whose use crosses a call + y is the ordinal position of the insn within the block */ + sbitmap require_call_save_reg; + + /* REGNO x INSN y 1 if insn y sets reg x */ + sbitmap *defs; + + /* REGNO x INSN y The register class for this def */ + enum reg_class *def_class; + + /* REGNO x INSN y 1 if insn y uses reg x */ + sbitmap *uses; + + /* REGNO x INSN y The register class for this use */ + enum reg_class *use_class; + } +def_uses; + +#define DU_REG_CLASS(rc,r,high_bound,i) (rc[r * high_bound + i]) + +typedef struct ext_basic_blocks + { + /* n_basic_blocks x n_basic_blocks y 1 if bb y is in extended bb + having entry x */ + sbitmap *basic_block; + + /* n_basic_blocks x n_basic_blocks y 1 if bb y is an exit block */ + sbitmap *exit; + } +ext_basic_blocks; + +#define UID_RUID_HIGH_BOUND 64 +#define DESTINATION 1 +#define SOURCE 2 + +static void build_def_use PARAMS ((int, ext_basic_blocks *, HARD_REG_SET *, + def_uses *, sbitmap *)); +static int replace_reg_in_block + PARAMS ((def_uses *, varray_type *, int, rtx, int)); +static int consider_def PARAMS ((rtx, int, def_uses *, int)); +static int consider_available PARAMS ((rtx, int, HARD_REG_SET *, int, def_uses *, int)); +static rtx rr_replace_reg PARAMS ((rtx, rtx, rtx, int, rtx, int *)); +static int consider_use PARAMS ((rtx, int, int, int)); +static int condmove_p PARAMS ((rtx)); +static void dump_def_use_chain PARAMS ((HARD_REG_SET *, def_uses *, + varray_type *)); +static void dump_ext_bb_info PARAMS ((int, ext_basic_blocks *)); +static void find_ext_basic_blocks PARAMS ((ext_basic_blocks *)); +static void find_one_ext_basic_block PARAMS ((int, basic_block, sbitmap *, + ext_basic_blocks *)); +static enum reg_class get_reg_class PARAMS ((rtx, rtx, int, enum reg_class)); +static rtx regno_first_use_in (int, rtx); + +void +regrename_optimize () +{ + int b, eb, i, inum, r, rc, replace_ok; + rtx insn; + def_uses def_uses; + ext_basic_blocks ext_basic_blocks; + + + /* Registers used in a given class */ + HARD_REG_SET class_regs; + + /* Registers available for use as renaming registers */ + HARD_REG_SET avail_regs; + + /* Registers used in the block */ + HARD_REG_SET regs_used; + + /* Registers which have been used as renaming registers */ + HARD_REG_SET renamed_regs; + + HARD_REG_SET global_live_at_end, global_live_at_start; + + HARD_REG_SET null_bitmap, tmp_bitmap; + + /* 1 if insn y sets a register which is live at the end of the block */ + sbitmap defs_live_exit; + + /* Mapping from insn y (ordinal position in block) to INSN_UID */ + varray_type uid_ruid; + + /* Mapping from insn y (ordinal position in block) to block id */ + varray_type uid_rbid; + + /* Ordinal position in block of defining insn */ + int *def_idx; + + VARRAY_RTX_INIT (uid_ruid, UID_RUID_HIGH_BOUND + 1, "uid_ruid"); + VARRAY_LONG_INIT (uid_rbid, UID_RUID_HIGH_BOUND + 1, "uid_rbid"); + + ext_basic_blocks.basic_block = + sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); + sbitmap_vector_zero (ext_basic_blocks.basic_block, n_basic_blocks); + ext_basic_blocks.exit = + sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); + sbitmap_vector_zero (ext_basic_blocks.exit, n_basic_blocks); + + find_ext_basic_blocks (&ext_basic_blocks); + + def_uses.def_class = def_uses.use_class = 0; + + /* Build uid_ruid and uid_rbid for this extended basic block */ + for (b = 0; b < n_basic_blocks; b++) + if (TEST_BIT (ext_basic_blocks.basic_block[b], b)) + { + for (eb = def_uses.high_bound = 0; eb < n_basic_blocks; eb++) + { + if (TEST_BIT (ext_basic_blocks.basic_block[b], eb)) + { + basic_block bb = BASIC_BLOCK (eb); + /* Calculate high bound for uid_ruid and allocate if necessary */ + for (insn = bb->head; + insn != NEXT_INSN (bb->end); + def_uses.high_bound++, insn = NEXT_INSN (insn)) + { + int uid_ruid_high_bound = VARRAY_SIZE (uid_ruid); + if (def_uses.high_bound + 4 >= uid_ruid_high_bound) + { + VARRAY_GROW (uid_ruid, uid_ruid_high_bound * 2); + VARRAY_GROW (uid_rbid, uid_ruid_high_bound * 2); + } + VARRAY_RTX (uid_ruid, def_uses.high_bound) = insn; + VARRAY_LONG (uid_rbid, def_uses.high_bound) = eb; + } + } + } + + CLEAR_HARD_REG_SET (null_bitmap); + CLEAR_HARD_REG_SET (class_regs); + CLEAR_HARD_REG_SET (regs_used); + CLEAR_HARD_REG_SET (avail_regs); + CLEAR_HARD_REG_SET (tmp_bitmap); + CLEAR_HARD_REG_SET (renamed_regs); + + def_uses.defs = + sbitmap_vector_alloc (FIRST_PSEUDO_REGISTER, def_uses.high_bound + 1); + sbitmap_vector_zero (def_uses.defs, FIRST_PSEUDO_REGISTER); + def_uses.uses = + sbitmap_vector_alloc (FIRST_PSEUDO_REGISTER, def_uses.high_bound + 1); + sbitmap_vector_zero (def_uses.uses, FIRST_PSEUDO_REGISTER); + def_uses.require_call_save_reg = sbitmap_alloc (def_uses.high_bound + 1); + sbitmap_zero (def_uses.require_call_save_reg); + defs_live_exit = sbitmap_alloc (def_uses.high_bound + 1); + sbitmap_zero (defs_live_exit); + + def_uses.def_class = xrealloc + (def_uses.def_class, + sizeof (enum reg_class) * FIRST_PSEUDO_REGISTER * def_uses.high_bound); + + def_uses.use_class = xrealloc + (def_uses.use_class, + sizeof (enum reg_class) * FIRST_PSEUDO_REGISTER * def_uses.high_bound); + + build_def_use (b, &ext_basic_blocks, ®s_used, &def_uses, + &defs_live_exit); + + if (rtl_dump_file) + { + dump_ext_bb_info (b, &ext_basic_blocks); + dump_def_use_chain (&global_live_at_end, &def_uses, &uid_ruid); + } + + /* Available registers are not: used in the block, live at the start, + live at the end, a register we've renamed to. */ + /* ??? The current algorithm is pessimistic for extended basic blocks + as it just treats them as a big basic block. */ + + COPY_HARD_REG_SET (tmp_bitmap, regs_used); + REG_SET_TO_HARD_REG_SET (global_live_at_start, BASIC_BLOCK (b)->global_live_at_start); + IOR_HARD_REG_SET (tmp_bitmap, global_live_at_start); + for (eb = 0; eb < n_basic_blocks; eb++) + { + if (TEST_BIT (ext_basic_blocks.basic_block[b], eb)) + { + basic_block bb = BASIC_BLOCK (eb); + REG_SET_TO_HARD_REG_SET (global_live_at_end, bb->global_live_at_end); + IOR_HARD_REG_SET (tmp_bitmap, global_live_at_end); + } + } + + def_idx = xcalloc (def_uses.high_bound, sizeof (int)); + + /* Only consider registers in this extended block and in this class + that are defined more than once. Replace them if permissible. */ + for (r = 0; r < FIRST_PSEUDO_REGISTER; r++) + { + int avail_reg, ar_idx, def, def_cnt = 0, use_idx, call_idx; + + if (!TEST_HARD_REG_BIT (regs_used, r) + || fixed_regs[r] + || r == FRAME_POINTER_REGNUM) + continue; + + /* Find def_idx[N] where hbound of N is the number of + definitions of this register in this block. and def_idx + is the ordinal position of this insn in the block. */ + for (i = 0, def_idx[def_cnt] = 0; + i < def_uses.high_bound; + i++) + { + if (TEST_BIT (def_uses.defs[r], i) + && consider_def (VARRAY_RTX (uid_ruid, i), r, + &def_uses, i)) + { + int first_use = 1; + def_idx[def_cnt] = i; + + /* Only consider definitions that have a use. */ + for (use_idx = i + 1; use_idx < def_uses.high_bound; + use_idx++) + { + if (TEST_BIT (def_uses.uses[r], use_idx)) + { + if (consider_use (VARRAY_RTX (uid_ruid, use_idx), r, + VARRAY_LONG (uid_rbid, i), + VARRAY_LONG (uid_rbid, use_idx))) + { + if (first_use) + { + first_use = 0; + def_cnt++; + } + } + else + { + /* Don't consider def if we don't want this use */ + if (!first_use) + def_cnt--; + break; + } + } + if (TEST_BIT (def_uses.defs[r], use_idx)) + break; + } + /* Scan until the next def to avoid renaming + parameter registers. */ + /* ??? consider using CALL_INSN_FUNCTION_USAGE */ + for (call_idx = i; call_idx <= use_idx; call_idx++) + if (VARRAY_RTX (uid_ruid, call_idx) + && GET_CODE (VARRAY_RTX (uid_ruid, call_idx)) + == CALL_INSN) + { + SET_BIT (def_uses.require_call_save_reg, i); + } + } + } + if (def_cnt < 2) + continue; + + /* We have more than one def so rename until we exhaust + renaming registers. */ + /* ??? Should we continue renaming round robin when we exhaust + renaming registers? */ + for (def = 0; def < def_cnt - 1; def++) + { + if (!TEST_BIT (defs_live_exit, def_idx[def]) + && (GET_RTX_CLASS + (GET_CODE (VARRAY_RTX (uid_ruid, + def_idx[def]))) == 'i')) + { + rtx reg_use = regno_first_use_in + (r, PATTERN (VARRAY_RTX (uid_ruid, def_idx[def]))); + + if (!reg_use) + break; +#ifdef STACK_REGS + /* Don't bother with stacked float registers */ + if (GET_MODE_CLASS (GET_MODE (reg_use)) == MODE_FLOAT) + break; +#endif + rc = (int) DU_REG_CLASS (def_uses.def_class, + r, def_uses.high_bound, def_idx[def]); + COPY_HARD_REG_SET (avail_regs, + reg_class_contents[(enum reg_class) rc]); + AND_COMPL_HARD_REG_SET (avail_regs, tmp_bitmap); + AND_COMPL_HARD_REG_SET (avail_regs, renamed_regs); + + /* No available registers in this class */ + GO_IF_HARD_REG_EQUAL (avail_regs, null_bitmap, + no_available_regs); + for (ar_idx = 0; ar_idx < FIRST_PSEUDO_REGISTER + && TEST_HARD_REG_BIT (avail_regs, ar_idx); ar_idx++) + ; + if (ar_idx == FIRST_PSEUDO_REGISTER) + goto no_available_regs; + + /* Only try register renaming if there is an available + register in this class. */ + for (ar_idx = 0; + ar_idx < FIRST_PSEUDO_REGISTER; + ar_idx++) + { + avail_reg = reg_alloc_order[ar_idx]; + if (consider_available (reg_use, avail_reg, &avail_regs, + rc, &def_uses, def_idx[def])) + break; + } + + if (ar_idx == FIRST_PSEUDO_REGISTER) + { + if (rtl_dump_file) + { + fprintf (rtl_dump_file, + "Register %s in class %s", + reg_names[r], reg_class_names[rc]); + fprintf (rtl_dump_file, + " in insn %d", + INSN_UID (VARRAY_RTX (uid_ruid, + def_idx[def]))); + + if (TEST_BIT (def_uses.require_call_save_reg, + def_idx[def])) + fprintf (rtl_dump_file, " crosses a call"); + fprintf (rtl_dump_file, ". No available registers\n"); + } + goto try_next_def; + } + + SET_HARD_REG_BIT (renamed_regs, avail_reg); + CLEAR_HARD_REG_BIT (avail_regs, avail_reg); + + /* Replace in destination. Replace in source for + remainder of block until new register is defined + again */ + replace_ok = replace_reg_in_block + (&def_uses, &uid_ruid, def_idx[def], reg_use, avail_reg); + /* Replace failed, so restore previous register */ + if (!replace_ok) + { + replace_reg_in_block (&def_uses, &uid_ruid, def_idx[def], + gen_rtx_REG (GET_MODE (reg_use), + avail_reg), + REGNO (reg_use)); + if (rtl_dump_file) + fprintf (rtl_dump_file, + "Register %s in class %s Renaming as %s would not satisfy constraints\n", + reg_names[r], reg_class_names[rc], + reg_names[avail_reg]); + } + else if (rtl_dump_file) + fprintf (rtl_dump_file, + "Register %s in class %s Renamed as %s at insn %d\n", + reg_names[r], reg_class_names[rc], + reg_names[avail_reg], + INSN_UID (VARRAY_RTX (uid_ruid, def_idx[def]))); + } + try_next_def: + continue; + } + sbitmap_zero (def_uses.defs[r]); + no_available_regs: + continue; + } + free (def_idx); + sbitmap_vector_free (def_uses.defs); + sbitmap_vector_free (def_uses.uses); + sbitmap_free (def_uses.require_call_save_reg); + sbitmap_free (defs_live_exit); + CLEAR_HARD_REG_SET (regs_used); + CLEAR_HARD_REG_SET (renamed_regs); + + for (inum = 0; inum < (int) VARRAY_SIZE (uid_ruid); inum++) + VARRAY_RTX (uid_ruid, inum) = (rtx) 0; + } + + sbitmap_vector_free (ext_basic_blocks.basic_block); + sbitmap_vector_free (ext_basic_blocks.exit); +} + +/* Build def/use chain DU for extended basic block EBB having root B. + Also determine which regs are used, REGS_USED, and which insns define + a live at exit def, DEFS_LIVE_EXIT */ + +static void +build_def_use (b, ebb, regs_used, du, defs_live_exit) + int b; + ext_basic_blocks *ebb; + HARD_REG_SET *regs_used; + def_uses *du; + sbitmap *defs_live_exit; +{ + rtx insn; + int eb, inum, r; + + inum = 0; + for (eb = 0; eb < n_basic_blocks; eb++) + { + basic_block bb = BASIC_BLOCK (eb); + + if (!TEST_BIT (ebb->basic_block[b], eb)) + continue; + + for (insn = bb->head; + insn != NEXT_INSN (bb->end); + inum++, insn = NEXT_INSN (insn)) + { + struct resources insn_res; + struct resources insn_sets; + + if (GET_RTX_CLASS (GET_CODE (insn)) != 'i') + continue; + + CLEAR_RESOURCE (&insn_sets); + mark_set_resources (insn, &insn_sets, 0, MARK_DEST); + + for (r = 0; + r < FIRST_PSEUDO_REGISTER; + r++) + { + if (!TEST_HARD_REG_BIT (insn_sets.regs, r)) + continue; + + SET_HARD_REG_BIT (*regs_used, r); + if (REGNO_REG_SET_P (bb->global_live_at_end, r)) + SET_BIT (*defs_live_exit, inum); + if (!insn_sets.memory) + SET_BIT (du->defs[r], inum); + DU_REG_CLASS (du->def_class, r, du->high_bound, inum) = get_reg_class + (insn, regno_first_use_in (r, PATTERN (insn)), + DESTINATION, NO_REGS); + } + + CLEAR_RESOURCE (&insn_res); + mark_referenced_resources (insn, &insn_res, 0); + + for (r = 0; + r < FIRST_PSEUDO_REGISTER; + r++) + { + if (!TEST_HARD_REG_BIT (insn_res.regs, r)) + continue; + + SET_HARD_REG_BIT (*regs_used, r); + SET_BIT (du->uses[r], inum); + DU_REG_CLASS (du->use_class, r, du->high_bound, inum) = get_reg_class + (insn, regno_use_in (r, PATTERN (insn)), + SOURCE, NO_REGS); + } + } + } + free_resource_info (); +} + +/* Return nonzero if regno AVAIL_REG can replace REG_DEF for insns in UID_RUID + starting at insn DEF in def/use chain DU. */ + +static int +replace_reg_in_block (du, uid_ruid, def, reg_def, avail_reg) + def_uses *du; + varray_type *uid_ruid; + int def; + rtx reg_def; + int avail_reg; +{ + int du_idx, status = 1; + int r = REGNO (reg_def); + rtx death_note; + rtx new_reg = gen_rtx_REG (GET_MODE (reg_def), avail_reg); + + + rr_replace_reg (PATTERN (VARRAY_RTX (*uid_ruid, def)), reg_def, + new_reg, DESTINATION, VARRAY_RTX (*uid_ruid, def), + &status); + if (!status) + return status; + + death_note = find_reg_note (VARRAY_RTX (*uid_ruid, def), REG_DEAD, reg_def); + if (!death_note) + death_note = find_reg_note (VARRAY_RTX (*uid_ruid, def), REG_UNUSED, reg_def); + if (death_note) + rr_replace_reg (death_note, reg_def, new_reg, 0, + VARRAY_RTX (*uid_ruid, def), &status); + + for (du_idx = def + 1; du_idx < du->high_bound; du_idx++) + { + rtx reg_use; + rtx new_reg; + if (GET_RTX_CLASS (GET_CODE (VARRAY_RTX (*uid_ruid, du_idx))) != 'i') + continue; + reg_use = regno_use_in (r, PATTERN (VARRAY_RTX (*uid_ruid, du_idx))); + + if (reg_use && TEST_BIT (du->uses[r], du_idx)) + { + new_reg = gen_rtx_REG (GET_MODE (reg_use), avail_reg); + rr_replace_reg (PATTERN (VARRAY_RTX (*uid_ruid, du_idx)), reg_use, + new_reg, SOURCE, VARRAY_RTX (*uid_ruid, du_idx), + &status); + death_note = find_reg_note (VARRAY_RTX (*uid_ruid, du_idx), + REG_DEAD, reg_use); + if (!death_note) + death_note = find_reg_note (VARRAY_RTX (*uid_ruid, du_idx), + REG_UNUSED, reg_use); + if (death_note) + rr_replace_reg (death_note, reg_use, new_reg, 0, + VARRAY_RTX (*uid_ruid, def), &status); + SET_BIT (du->uses[avail_reg], du_idx); + RESET_BIT (du->uses[r], du_idx); + if (!status) + return status; + } + if (TEST_BIT (du->defs[r], du_idx)) + break; + } + return status; +} + +/* Try to replace REG_USE in X with REG_SUB if INSN has a REPLACE_TYPE. + STATUS is zero if the resulting pattern is not valid. */ + +static rtx +rr_replace_reg (x, reg_use, reg_sub, replace_type, insn, status) + rtx x; + rtx reg_use; + rtx reg_sub; + int replace_type; + rtx insn; + int *status; +{ + enum rtx_code code; + int i; + const char *fmt; + int n; + + if (x == 0) + return x; + + code = GET_CODE (x); + switch (code) + { + case REG: + if (REGNO (x) == REGNO (reg_use)) + { + if (GET_MODE (x) == GET_MODE (reg_use)) + return reg_sub; + else + return gen_rtx_REG (GET_MODE (x), REGNO (reg_use)); + } + return x; + + case SET: + if (replace_type == DESTINATION) + SET_DEST (x) = rr_replace_reg (SET_DEST (x), reg_use, reg_sub, + replace_type, insn, status); + else if (replace_type == SOURCE) + { + int dest_subregno; + + if (GET_CODE (SET_DEST (x)) == SUBREG) + dest_subregno = REGNO (XEXP (SET_DEST (x), 0)); + else + dest_subregno = 0; + + SET_SRC (x) = rr_replace_reg (SET_SRC (x), reg_use, reg_sub, + replace_type, insn, status); + /* If the replacement register is not part of the source + then it may be part of a source mem operand. */ + if (GET_CODE (SET_DEST (x)) == MEM + || GET_CODE (SET_DEST (x)) == ZERO_EXTRACT + || GET_CODE (SET_DEST (x)) == SIGN_EXTRACT + || GET_CODE (SET_DEST (x)) == STRICT_LOW_PART) + SET_DEST (x) = rr_replace_reg (SET_DEST (x), reg_use, reg_sub, + replace_type, insn, status); + /* shared rtl sanity check */ + if (dest_subregno + && dest_subregno != REGNO (XEXP (SET_DEST (x), 0))) + { + *status = 0; + return x; + } + } + + n = recog_memoized (insn); + if (n >= 0) + { + int id; + extract_insn (insn); + + /* Any MATCH_DUP's which are REGs must still match */ + for (id = insn_data[n].n_dups - 1; id >= 0; id--) + { + int opno = recog_data.dup_num[id]; + if (GET_CODE (*recog_data.dup_loc[id]) == REG + && GET_CODE (*recog_data.operand_loc[opno]) == REG + && (REGNO (*recog_data.dup_loc[id]) != + REGNO (*recog_data.operand_loc[opno]))) + *status = 0; + } + + if (!constrain_operands (1)) + { + *status = 0; + validate_replace_rtx (reg_sub, reg_use, insn); + } + } + else + *status = 0; + + return x; + + default: + break; + } + + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + { + if (fmt[i] == 'e') + XEXP (x, i) = rr_replace_reg (XEXP (x, i), reg_use, reg_sub, + replace_type, insn, status); + if (fmt[i] == 'E') + { + register int xv; + for (xv = 0; xv < XVECLEN (x, i); xv++) + { + XVECEXP (x, i, xv) = rr_replace_reg (XVECEXP (x, i, xv), reg_use, + reg_sub, replace_type, insn, + status); + n = recog_memoized (insn); + if (n >= 0) + { + extract_insn (insn); + if (!constrain_operands (1)) + { + *status = 0; + validate_replace_rtx (reg_sub, reg_use, insn); + } + } + else + *status = 0; + } + } + } + return x; +} + +/* Can REGNO in INSN be considered for renaming, given def INUM in d/u + chain DU? */ + +static int +consider_def (insn, regno, du, inum) + rtx insn; + int regno; + def_uses *du; + int inum; +{ + /* Don't rename windowed registers across a call */ +#ifdef INCOMING_REGNO + if (TEST_BIT (du->require_call_save_reg, inum) + && INCOMING_REGNO (regno) != regno) + return 0; +#endif + + /* Don't consider conditional moves. Predicate architectures may + use two complementary conditional moves and the regno shouldn't change */ + if (condmove_p (insn)) + return 0; + + /* Don't rename call used registers across a call */ + if (!(GET_CODE (insn) == CALL_INSN + && TEST_HARD_REG_BIT (call_used_reg_set, regno))) + return 1; + else + return 0; +} + +/* Can the use of REGNO in INSN of block USE_BLOCK be considered for renaming + for a def in def_block? */ + +static int +consider_use (insn, regno, def_block, use_block) + rtx insn; + int regno; + int def_block; + int use_block; +{ + rtx reg_use; + edge e; + basic_block ub = BASIC_BLOCK (use_block); + + if (GET_RTX_CLASS (GET_CODE (insn)) != 'i') + return 0; + + /* If a use's basic block is different than the def's basic block, + then insure another predecessor does not also define this register */ + if (def_block != use_block) + for (e = ub->pred; e; e = e->pred_next) + { + if (e->src->index != def_block + && e->src->index != -1 + && REGNO_REG_SET_P (BASIC_BLOCK (e->src->index)->global_live_at_end, regno)) + return 0; + } + + /* Don't consider conditional moves. Predicate architectures may + use two complementary conditional moves and the regno shouldn't change */ + + if (condmove_p (insn)) + return 0; + + reg_use = regno_first_use_in (regno, PATTERN (insn)); + if (reg_use) + { + /* Don't consider multi-reg values. */ + if (HARD_REGNO_NREGS (regno, GET_MODE (reg_use)) != 1 + && GET_MODE (reg_use) != CCmode) + return 0; + + /* Don't consider register if the only use is in a USE */ + if (reg_mentioned_p (gen_rtx_USE (VOIDmode, reg_use), + PATTERN (insn))) + return 0; + else + return 1; + } + else + return 0; +} + +/* Can REG_USE be replaced by regno AVAIL_REG if it is in AVAIL_REGS + and it is in regclass RC, given insn INUM of def/use chain DU? */ + +static int +consider_available (reg_use, avail_reg, avail_regs, rc, du, inum) + rtx reg_use; + int avail_reg; + HARD_REG_SET *avail_regs; + int rc; + def_uses *du; + int inum; +{ + if (!TEST_HARD_REG_BIT (*avail_regs, avail_reg)) + return 0; + +#ifdef HARD_REGNO_RENAME_OK + if (!HARD_REGNO_RENAME_OK (REGNO (reg_use), avail_reg)) + return 0; +#endif + + /* Don't consider windowed leaf registers which will be renamed by + leaf_renumber_regs */ +#ifdef LEAF_REG_REMAP + if (current_function_uses_only_leaf_regs) + if (LEAF_REG_REMAP (avail_reg) < 0) + return 0; +#endif + + /* A register is considered available if it is available at the beginning of + the basic block. We may want to refine this to when a register becomes + available within the block. We don't consider multi-reg values. */ + /* ??? Consider a representation that would allow multi-reg support? */ + if (!TEST_HARD_REG_BIT (reg_class_contents[(enum reg_class) rc], avail_reg) + || !HARD_REGNO_MODE_OK (avail_reg, GET_MODE (reg_use)) + || (HARD_REGNO_NREGS (avail_reg, GET_MODE (reg_use)) != 1 + && GET_MODE (reg_use) != CCmode) + || (call_fixed_regs[avail_reg] +#ifdef HARD_REGNO_RENAME_OK + && !HARD_REGNO_RENAME_OK (REGNO (reg_use), avail_reg) +#endif + ) + || (TEST_BIT (du->require_call_save_reg, inum) + && (call_used_regs[avail_reg] || call_used_regs[REGNO (reg_use)] + ))) + return 0; + + /* If register is a callee-saved register it must be saved in the frame. + call saved registers can not be added to regs_ever_live after reload, + as it would invalidate most elimination offsets */ + if (regs_ever_live[avail_reg] || call_used_regs[avail_reg] + || (avail_reg == PIC_OFFSET_TABLE_REGNUM + && flag_pic && (current_function_uses_pic_offset_table))) + return 1; + + return 0; +} + +/* Return 1 if INSN is a conditional move */ + +static int +condmove_p (insn) + rtx insn; +{ + if (GET_CODE (insn) == INSN + && GET_CODE (PATTERN (insn)) == SET + && GET_CODE (SET_SRC (PATTERN (insn))) == IF_THEN_ELSE) + return 1; + return 0; +} + +/* Searches X for the first reference to REGNO, returning the rtx of the + reference found if any. Otherwise, returns NULL_RTX. */ + +static rtx +regno_first_use_in (regno, x) + int regno; + rtx x; +{ + register const char *fmt; + int i, j; + rtx tem; + + if (GET_CODE (x) == REG && REGNO (x) == regno) + return x; + + fmt = GET_RTX_FORMAT (GET_CODE (x)); + for (i = 0; i <= GET_RTX_LENGTH (GET_CODE (x)) - 1; i++) + { + if (fmt[i] == 'e') + { + if ((tem = regno_first_use_in (regno, XEXP (x, i)))) + return tem; + } + else if (fmt[i] == 'E') + for (j = XVECLEN (x, i) - 1; j >= 0; j--) + if ((tem = regno_first_use_in (regno, XVECEXP (x, i, j)))) + return tem; + } + + return NULL_RTX; +} + +/* Dump def/use chain DU to RTL_DUMP_FILE, given insns in UID_RUID and + which regs are live at end, GLOBAL_LIVE_AT_END */ + +static void +dump_def_use_chain (global_live_at_end, du, uid_ruid) + HARD_REG_SET *global_live_at_end; + def_uses *du; + varray_type *uid_ruid; +{ + int r, inum; + + for (r = 0; r < FIRST_PSEUDO_REGISTER; r++) + { + int set = 0; + for (inum = 0; + inum <= du->high_bound; + inum++) + { + rtx insn = VARRAY_RTX (*uid_ruid, inum); +#if 0 + if (!insn + || GET_RTX_CLASS (GET_CODE + (insn)) != 'i') + continue; + reg_use = regno_first_use_in (r, PATTERN (insn)); + if (!reg_use) + continue; +#endif + if (!set && (TEST_BIT (du->defs[r], inum) + || TEST_BIT (du->uses[r], inum))) + { + fprintf (rtl_dump_file, "Register %s: ", reg_names[r]); + if (fixed_regs[r]) + fprintf (rtl_dump_file, "Fixed "); + else if (call_fixed_regs[r]) + fprintf (rtl_dump_file, "Call Fixed "); + if (TEST_HARD_REG_BIT (*global_live_at_end, r)) + fprintf (rtl_dump_file, "Live at Exit "); + set = 1; + } + if (TEST_BIT (du->defs[r], inum)) + fprintf (rtl_dump_file, "=%d ", INSN_UID (insn)); + if (TEST_BIT (du->uses[r], inum)) + fprintf (rtl_dump_file, "%d ", INSN_UID (insn)); + } + if (set) + fprintf (rtl_dump_file, "\n"); + } +} + +/* Dump info for extended basic block EBB having root EB */ + +static void +dump_ext_bb_info (eb, ebb) + int eb; + ext_basic_blocks *ebb; +{ + int b; + + { + int have_ebb = 0; + for (b = 0; b < n_basic_blocks; b++) + { + if (TEST_BIT (ebb->basic_block[eb], b)) + { + if (!have_ebb) + { +#ifndef RENAME_EXTENDED_BLOCKS + fprintf (rtl_dump_file, "\nBasic block %d: ", b); +#else + fprintf (rtl_dump_file, "\nExtended basic block %d: ", b); +#endif + have_ebb = 1; + } + fprintf (rtl_dump_file, "%d ", b); + } + if (TEST_BIT (ebb->exit[eb], b)) + fprintf (rtl_dump_file, "(exit) "); + } + if (have_ebb) + fprintf (rtl_dump_file, "\n"); + } +} + +/* Initialize EBB with extended basic block info if RENAME_EXTENDED_BLOCKS is + defined. Otherwise just use basic blocks */ + +static void +find_ext_basic_blocks (ebb) + ext_basic_blocks *ebb; +{ + sbitmap bb_processed; + int b; + + bb_processed = sbitmap_alloc (n_basic_blocks); + sbitmap_zero (bb_processed); + +#ifndef RENAME_EXTENDED_BLOCKS + for (b = 0; b < n_basic_blocks; b++) + { + basic_block bb = BASIC_BLOCK (b); + SET_BIT (ebb->basic_block[bb->index], bb->index); + } +#else + for (b = 0; b < n_basic_blocks; b++) + { + basic_block bb = BASIC_BLOCK (b); + if (!TEST_BIT (bb_processed, b)) + { + find_one_ext_basic_block (bb->index, bb, &bb_processed, ebb); + } + } +#endif + sbitmap_free (bb_processed); +} + +/* Find one extended basic block EBB having root ENTRY containing block + BB */ + +static void +find_one_ext_basic_block (entry, bb, bb_processed, ebb) + int entry; + basic_block bb; + sbitmap *bb_processed; + ext_basic_blocks *ebb; +{ + edge e; + + if (!TEST_BIT (*bb_processed, bb->index)) + { + SET_BIT (ebb->basic_block[entry], bb->index); + SET_BIT (*bb_processed, bb->index); + } + + for (e = bb->succ; e; e = e->succ_next) + if (!TEST_BIT (*bb_processed, e->dest->index)) + { + if (!e->dest->pred->pred_next + && (!TEST_BIT (*bb_processed, e->dest->index))) + { + find_one_ext_basic_block (entry, e->dest, bb_processed, ebb); + } + else + { + SET_BIT (ebb->exit[entry], bb->index); + } + } +} + +/* Find the register class for register REG_USE having TYPE (DESTINATION or + SOURCE) in INSN. Use DEFAULT_CLASS if we cannot determine a class. */ + +static enum reg_class +get_reg_class (insn, reg_use, type, default_class) + rtx insn; + rtx reg_use; + int type; + enum reg_class default_class; +{ + int alt, id = 0; + + extract_insn (insn); + constrain_operands (1); + alt = which_alternative; + + preprocess_constraints (); + + if (type == DESTINATION) + for (id = 0; id < recog_data.n_operands; id++) + { + if (rtx_equal_p (recog_data.operand[id], reg_use)) + break; + } + else if (type == SOURCE) + for (id = recog_data.n_operands - 1; id >= 0; id--) + { + if (rtx_equal_p (recog_data.operand[id], reg_use)) + break; + } + + if (id == -1 || id == recog_data.n_operands) + return default_class; + + return recog_op_alt[id][alt].class; +} diff --git a/gcc/rtl.h b/gcc/rtl.h index ec95b4bec43..263de4e4416 100644 --- a/gcc/rtl.h +++ b/gcc/rtl.h @@ -1798,4 +1798,8 @@ extern void convert_from_ssa PARAMS ((void)); extern rtx stack_limit_rtx; +/* In regrename.c */ + +extern void regrename_optimize PARAMS ((void)); + #endif /* _RTL_H */ diff --git a/gcc/toplev.c b/gcc/toplev.c index 6d84c915c4e..920dba5df55 100644 --- a/gcc/toplev.c +++ b/gcc/toplev.c @@ -270,6 +270,7 @@ enum dump_file_index DFI_peephole2, DFI_sched2, DFI_bbro, + DFI_rnreg, DFI_jump2, DFI_mach, DFI_dbr, @@ -302,6 +303,7 @@ struct dump_file_info dump_file[DFI_MAX] = { "peephole2", 'z', 1, 0, 0 }, { "sched2", 'R', 1, 0, 0 }, { "bbro", 'B', 1, 0, 0 }, + { "rnreg", 'n', 1, 0, 0 }, { "jump2", 'J', 1, 0, 0 }, { "mach", 'M', 1, 0, 0 }, { "dbr", 'd', 0, 0, 0 }, @@ -423,6 +425,10 @@ int flag_branch_probabilities = 0; int flag_reorder_blocks = 0; +/* Nonzero if registers should be renamed */ + +int flag_rename_registers = 0; + /* Nonzero for -pedantic switch: warn about anything that standard spec forbids. */ @@ -1019,6 +1025,8 @@ lang_independent_options f_options[] = "Use profiling information for branch probabilities" }, {"reorder-blocks", &flag_reorder_blocks, 1, "Reorder basic blocks to improve code placement" }, + {"rename-registers", &flag_rename_registers, 1, + "Do the register renaming optimization pass"}, {"fast-math", &flag_fast_math, 1, "Improve FP speed by violating ANSI & IEEE rules" }, {"common", &flag_no_common, 0, @@ -1415,6 +1423,7 @@ int peephole2_time; int sched2_time; int dbr_sched_time; int reorder_blocks_time; +int rename_registers_time; int shorten_branch_time; int stack_reg_time; int final_time; @@ -2164,6 +2173,7 @@ compile_file (name) sched2_time = 0; dbr_sched_time = 0; reorder_blocks_time = 0; + rename_registers_time = 0; shorten_branch_time = 0; stack_reg_time = 0; final_time = 0; @@ -2572,6 +2582,7 @@ compile_file (name) print_time ("dbranch", dbr_sched_time); #endif print_time ("bbro", reorder_blocks_time); + print_time ("rnreg", rename_registers_time); print_time ("shorten-branch", shorten_branch_time); #ifdef STACK_REGS print_time ("stack-reg", stack_reg_time); @@ -3421,6 +3432,15 @@ rest_of_compilation (decl) close_dump_file (DFI_bbro, print_rtl_with_bb, insns); } + if (optimize > 0 && flag_rename_registers) + { + open_dump_file (DFI_rnreg, decl); + + TIMEVAR (rename_registers_time, regrename_optimize ()); + + close_dump_file (DFI_rnreg, print_rtl_with_bb, insns); + } + /* One more attempt to remove jumps to .+1 left by dead-store elimination. Also do cross-jumping this time and delete no-op move insns. */ -- 2.30.2