From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtpbg150.qq.com (smtpbg150.qq.com [18.132.163.193]) by sourceware.org (Postfix) with ESMTPS id D55353858403 for ; Sat, 3 Feb 2024 10:50:25 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org D55353858403 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=rivai.ai Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=rivai.ai ARC-Filter: OpenARC Filter v1.0.0 sourceware.org D55353858403 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=18.132.163.193 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1706957434; cv=none; b=mLXPpkEt+TCFSHcuwwkPaj7PM+2yyZ/ksDBhw2UZgq/aVXsvcwlIcgoOSx7Nz7g11sQgwFeNai2jsJOim/yUOYMThAr0FMM18xSWHpVXw3IvKBXjX6tXVi/hTUBTuKdMJJSPG3V3c6DGdKtoyBxonse3DNdfTPCJmrDX/F+hAUg= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1706957434; c=relaxed/simple; bh=ev6qNb5tgVsQyUIG5bIYruzQaLmoRWzLVJtBFhQZlBg=; h=From:To:Subject:Date:Message-Id:MIME-Version; b=U9qGxcs/ktm9UILqwJZgEFqOOx4fIfROQbzteg2JhGIZ5YbHtSQUakSGmlGFc9mgMR261EriGmF0hMBKCUeDwAHeyFhVN6G2M7kFfD+3GBLPQPryIVNSdn91ntlhYbZ1dzQK0emkYw6+2Qwasv4bmkC8VzRg8G57WNpn24SN5aQ= ARC-Authentication-Results: i=1; server2.sourceware.org X-QQ-mid: bizesmtp72t1706957420tyqdzd1q X-QQ-Originating-IP: ybtPR720aPD5FB53dojWtxUUC8JRgj2/JO0sOeFxhEU= Received: from rios-cad5.localdomain ( [58.60.1.25]) by bizesmtp.qq.com (ESMTP) with id ; Sat, 03 Feb 2024 18:50:19 +0800 (CST) X-QQ-SSF: 01400000000000C0F000000A0000000 X-QQ-FEAT: znfcQSa1hKakNAZxXGcJO2LPD66ABXWFtc3Y3c40Fn8o/2dbTIm41MXYAFhJH IIW5gI/f04c4NEXqcKW90dkMoIV0bbg7mhbtKajZNmnio6AOLFn7vsHOunVCJXg2t6rky6Y syhd9dm6wY4HSpZbRt0qygD8BTdrqBNZhnLnUVb5aAgrEz4lH9T0zChRkwzx5IgVGNzts8B Wx1YYRg2rQKtdhSRHqTnJKsog5IZORW6H9II5zqmY0TlRQXiIViREHZyPIVsTJBpp6VrIKG fIsGIjEixoHAqIqbK6NIM9P9fK7giQOdLEFTDnWdcxQV9fS/k1szOr/f8egoPx0Xh71pV/X XKSUKNIBqHcxhPN10ncHvTsMzpOxTFY/22vE1/JQ0QvGGML2iIkGZmMMCjanfkb7ecfLgiR X-QQ-GoodBg: 2 X-BIZMAIL-ID: 1229324787317692073 From: Lehua Ding To: gcc-patches@gcc.gnu.org Cc: vmakarov@redhat.com, richard.sandiford@arm.com, juzhe.zhong@rivai.ai, lehua.ding@rivai.ai Subject: [PATCH 2/4] df: Add DF_LIVE_SUBREG problem Date: Sat, 3 Feb 2024 18:50:10 +0800 Message-Id: <20240203105012.208998-3-lehua.ding@rivai.ai> X-Mailer: git-send-email 2.36.3 In-Reply-To: <20240203105012.208998-1-lehua.ding@rivai.ai> References: <20240203105012.208998-1-lehua.ding@rivai.ai> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-QQ-SENDSIZE: 520 Feedback-ID: bizesmtp:rivai.ai:qybglogicsvrgz:qybglogicsvrgz5a-3 X-Spam-Status: No, score=-9.1 required=5.0 tests=BAYES_00,GIT_PATCH_0,KAM_ASCII_DIVIDERS,KAM_DMARC_STATUS,KAM_SHORT,RCVD_IN_BARRACUDACENTRAL,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL,SPF_HELO_PASS,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: This patch add a new DF problem, named DF_LIVE_SUBREG. This problem is extended from the DF_LR problem and support track the subreg liveness of multireg pseudo if these pseudo satisfy the following conditions: 1. the mode size greater than it's REGMODE_NATURAL_SIZE. 2. the reg is used in insns via subreg pattern. The main methods are as follows: 1. split bitmap in/out/def/use fileds to full_in/out/def/use and partial_in/out/def/use. If a pseudo need to be tracked it's subreg liveness, then it is recorded in partial_in/out/def/use fileds. Meantimes, there are range_in/out/def/use fileds which records the live range of the tracked pseudo. 2. in the df_live_subreg_finalize function, we move the tracked pseudo from the partial_in/out/def/use to full_in/out/def/use if the pseudo's live range is full. gcc/ChangeLog: * Makefile.in: Add subreg-live-range object file. * df-problems.cc (struct df_live_subreg_problem_data): Private struct for DF_LIVE_SUBREG problem. (df_live_subreg_get_bb_info): getting bb regs in/out data. (get_live_subreg_local_bb_info): getting bb regs use/def data. (multireg_p): checking is the regno a pseudo multireg. (need_track_subreg_p): checking is the regno need to be tracked. (init_range): getting the range of subreg rtx. (remove_subreg_range): removing use data for the reg/subreg rtx. (add_subreg_range): adding def/use data for the reg/subreg rtx. (df_live_subreg_free_bb_info): Free basic block df data. (df_live_subreg_alloc): Allocate and init df data. (df_live_subreg_reset): Reset the live in/out df data. (df_live_subreg_bb_local_compute): Compute basic block df data. (df_live_subreg_local_compute): Compute all basic blocks df data. (df_live_subreg_init): Init the in/out df data. (df_live_subreg_check_result): Assert the full and partial df data. (df_live_subreg_confluence_0): Confluence function for infinite loops. (df_live_subreg_confluence_n): Confluence function for normal edge. (df_live_subreg_transfer_function): Transfer function. (df_live_subreg_finalize): Finalize the all_in/all_out df data. (df_live_subreg_free): Free the df data. (df_live_subreg_top_dump): Dump top df data. (df_live_subreg_bottom_dump): Dump bottom df data. (df_live_subreg_add_problem): Add the DF_LIVE_SUBREG problem. * df.h (enum df_problem_id): Add DF_LIVE_SUBREG. (class subregs_live): Simple decalare. (class df_live_subreg_local_bb_info): New class for full/partial def/use df data. (class df_live_subreg_bb_info): New class for full/partial in/out df data. (df_live_subreg): getting the df_live_subreg data. (df_live_subreg_add_problem): Exported. (df_live_subreg_finalize): Ditto. (df_live_subreg_check_result): Ditto. (multireg_p): Ditto. (init_range): Ditto. (add_subreg_range): Ditto. (remove_subreg_range): Ditto. (df_get_subreg_live_in): Accessor the all_in df data. (df_get_subreg_live_out): Accessor the all_out df data. (df_get_subreg_live_full_in): Accessor the full_in df data. (df_get_subreg_live_full_out): Accessor the full_out df data. (df_get_subreg_live_partial_in): Accessor the partial_in df data. (df_get_subreg_live_partial_out): Accessor the partial_out df data. (df_get_subreg_live_range_in): Accessor the range_in df data. (df_get_subreg_live_range_out): Accessor the range_out df data. * regs.h (get_nblocks): Get the blocks of mode. * sbitmap.cc (bitmap_full_p): sbitmap predicator. (bitmap_same_p): sbitmap predicator. (test_full): test bitmap_full_p. (test_same): test bitmap_same_p. (sbitmap_cc_tests): Add test_full and test_same. * sbitmap.h (bitmap_full_p): Exported. (bitmap_same_p): Ditto. * timevar.def (TV_DF_LIVE_SUBREG): add DF_LIVE_SUBREG timevar. * subreg-live-range.cc: New file. * subreg-live-range.h: New file. --- gcc/Makefile.in | 1 + gcc/df-problems.cc | 855 ++++++++++++++++++++++++++++++++++++++- gcc/df.h | 155 +++++++ gcc/regs.h | 5 + gcc/sbitmap.cc | 98 +++++ gcc/sbitmap.h | 2 + gcc/subreg-live-range.cc | 53 +++ gcc/subreg-live-range.h | 206 ++++++++++ gcc/timevar.def | 1 + 9 files changed, 1375 insertions(+), 1 deletion(-) create mode 100644 gcc/subreg-live-range.cc create mode 100644 gcc/subreg-live-range.h diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 95caa54a52b..c30ea333736 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1684,6 +1684,7 @@ OBJS = \ store-motion.o \ streamer-hooks.o \ stringpool.o \ + subreg-live-range.o \ substring-locations.o \ target-globals.o \ targhooks.o \ diff --git a/gcc/df-problems.cc b/gcc/df-problems.cc index 88ee0dd67fc..703c7f914a4 100644 --- a/gcc/df-problems.cc +++ b/gcc/df-problems.cc @@ -28,6 +28,7 @@ along with GCC; see the file COPYING3. If not see #include "target.h" #include "rtl.h" #include "df.h" +#include "subreg-live-range.h" #include "memmodel.h" #include "tm_p.h" #include "insn-config.h" @@ -1344,8 +1345,860 @@ df_lr_verify_transfer_functions (void) bitmap_clear (&all_blocks); } +/*---------------------------------------------------------------------------- + REGISTER AND SUBREGS LIVES + Like DF_LR, but include tracking subreg liveness. Currently used to provide + subreg liveness related information to the register allocator. The subreg + information is currently tracked for registers that satisfy the following + conditions: + 1. REG is a pseudo register + 2. MODE_SIZE > UNIT_SIZE + 3. MODE_SIZE is a multiple of UNIT_SIZE + 4. REG is used via subreg pattern + Assuming: MODE = the machine mode of the REG + MODE_SIZE = GET_MODE_SIZE (MODE) + UNIT_SIZE = REGMODE_NATURAL_SIZE (MODE) + Condition 3 is currently strict, maybe it can be removed in the future, but + for now it is sufficient. + ----------------------------------------------------------------------------*/ + +/* These two empty data are used as default data in case the user does not turn + * on the track-subreg-liveness feature. */ +bitmap_head empty_bitmap; +subregs_live empty_live; + +/* Private data for live_subreg problem. */ +struct df_live_subreg_problem_data +{ + /* Record registers that need to track subreg liveness. */ + bitmap_head tracked_regs; + /* An obstack for the bitmaps we need for this problem. */ + bitmap_obstack live_subreg_bitmaps; +}; + +/* Helper functions */ + +static df_live_subreg_bb_info * +df_live_subreg_get_bb_info (unsigned int index) +{ + if (index < df_live_subreg->block_info_size) + return &( + (class df_live_subreg_bb_info *) df_live_subreg->block_info)[index]; + else + return NULL; +} + +static df_live_subreg_local_bb_info * +get_live_subreg_local_bb_info (unsigned int bb_index) +{ + return df_live_subreg_get_bb_info (bb_index); +} + +/* Return true if regno is a multireg. */ +bool +multireg_p (int regno) +{ + if (regno < FIRST_PSEUDO_REGISTER) + return false; + rtx regno_rtx = regno_reg_rtx[regno]; + machine_mode reg_mode = GET_MODE (regno_rtx); + poly_int64 total_size = GET_MODE_SIZE (reg_mode); + poly_int64 natural_size = REGMODE_NATURAL_SIZE (reg_mode); + return maybe_gt (total_size, natural_size) + && multiple_p (total_size, natural_size); +} + +/* Return true if the REGNO need be track with subreg liveness. */ + +static bool +need_track_subreg_p (unsigned regno) +{ + struct df_live_subreg_problem_data *problem_data + = (struct df_live_subreg_problem_data *) df_live_subreg->problem_data; + return bitmap_bit_p (&problem_data->tracked_regs, regno); +} + +/* Return the subreg_range of REF. */ +void +init_range (rtx op, sbitmap range) +{ + rtx reg = SUBREG_P (op) ? SUBREG_REG (op) : op; + machine_mode reg_mode = GET_MODE (reg); + + if (!read_modify_subreg_p (op)) + { + bitmap_set_range (range, 0, get_nblocks (reg_mode)); + return; + } + + rtx subreg = op; + machine_mode subreg_mode = GET_MODE (subreg); + poly_int64 offset = SUBREG_BYTE (subreg); + int nblocks = get_nblocks (reg_mode); + poly_int64 unit_size = REGMODE_NATURAL_SIZE (reg_mode); + poly_int64 subreg_size = GET_MODE_SIZE (subreg_mode); + poly_int64 left = offset + subreg_size; + + int subreg_start = -1; + int subreg_nblocks = -1; + for (int i = 0; i < nblocks; i += 1) + { + poly_int64 right = unit_size * (i + 1); + if (subreg_start < 0 && maybe_lt (offset, right)) + subreg_start = i; + if (subreg_nblocks < 0 && maybe_le (left, right)) + { + subreg_nblocks = i + 1 - subreg_start; + break; + } + } + gcc_assert (subreg_start >= 0 && subreg_nblocks > 0); + + bitmap_set_range (range, subreg_start, subreg_nblocks); +} + +/* Remove RANGE from BB_INFO's use data. */ +void +remove_subreg_range (df_live_subreg_local_bb_info *bb_info, unsigned int regno, + const_sbitmap range) +{ + bitmap partial = &bb_info->partial_use; + + bb_info->range_use->remove_range (regno, range); + if (bb_info->range_use->empty_p (regno)) + bitmap_clear_bit (partial, regno); +} + +/* Remove RANGE of REF from BB_INFO's use data. */ +static void +remove_subreg_range (df_live_subreg_local_bb_info *bb_info, df_ref ref) +{ + unsigned int regno = DF_REF_REGNO (ref); + machine_mode reg_mode = GET_MODE (DF_REF_REAL_REG (ref)); + + if (need_track_subreg_p (regno)) + { + auto_sbitmap range (get_nblocks (reg_mode)); + init_range (DF_REF_REG (ref), range); + remove_subreg_range (bb_info, regno, range); + } + else + { + bitmap_clear_bit (&bb_info->full_use, regno); + gcc_assert (!bitmap_bit_p (&bb_info->partial_use, regno)); + gcc_assert (!bitmap_bit_p (&bb_info->partial_def, regno)); + } +} + +/* add RANGE to BB_INFO's def/use. If is_def is true, means for BB_INFO's def, + otherwise for BB_INFO's use. */ +void +add_subreg_range (df_live_subreg_local_bb_info *bb_info, unsigned int regno, + const_sbitmap range, bool is_def) +{ + bitmap partial = is_def ? &bb_info->partial_def : &bb_info->partial_use; + subregs_live *range_live = is_def ? bb_info->range_def : bb_info->range_use; + + bitmap_set_bit (partial, regno); + range_live->add_range (regno, range); +} + +/* add RANGE of REF to BB_INFO def/use. If is_def is true, means for BB_INFO's + def, otherwise for BB_INFO's use. */ +static void +add_subreg_range (df_live_subreg_local_bb_info *bb_info, df_ref ref, + bool is_def) +{ + unsigned int regno = DF_REF_REGNO (ref); + machine_mode reg_mode = GET_MODE (DF_REF_REAL_REG (ref)); + + if (need_track_subreg_p (regno)) + { + auto_sbitmap range (get_nblocks (reg_mode)); + init_range (DF_REF_REG (ref), range); + add_subreg_range (bb_info, regno, range, is_def); + } + else + { + bitmap full = is_def ? &bb_info->full_def : &bb_info->full_use; + bitmap partial = is_def ? &bb_info->partial_def : &bb_info->partial_use; + bitmap_set_bit (full, regno); + gcc_assert (!bitmap_bit_p (partial, regno)); + } +} + +/* Free basic block info. */ + +static void +df_live_subreg_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, void *vbb_info) +{ + df_live_subreg_bb_info *bb_info = (df_live_subreg_bb_info *) vbb_info; + if (bb_info) + { + delete bb_info->range_in; + bb_info->range_in = NULL; + delete bb_info->range_out; + bb_info->range_out = NULL; + + bitmap_clear (&bb_info->all_in); + bitmap_clear (&bb_info->full_in); + bitmap_clear (&bb_info->partial_in); + bitmap_clear (&bb_info->all_out); + bitmap_clear (&bb_info->full_out); + bitmap_clear (&bb_info->partial_out); + } +} + +/* Allocate or reset bitmaps for DF_LIVE_SUBREG blocks. The solution bits are + not touched unless the block is new. */ + +static void +df_live_subreg_alloc (bitmap all_blocks ATTRIBUTE_UNUSED) +{ + struct df_live_subreg_problem_data *problem_data; + df_grow_bb_info (df_live_subreg); + if (df_live_subreg->problem_data) + problem_data + = (struct df_live_subreg_problem_data *) df_live_subreg->problem_data; + else + { + problem_data = XNEW (struct df_live_subreg_problem_data); + df_live_subreg->problem_data = problem_data; + + bitmap_obstack_initialize (&problem_data->live_subreg_bitmaps); + bitmap_initialize (&problem_data->tracked_regs, + &problem_data->live_subreg_bitmaps); + } + + bitmap_clear (&problem_data->tracked_regs); + + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + bitmap_set_bit (df_live_subreg->out_of_date_transfer_functions, bb->index); + + bitmap_set_bit (df_live_subreg->out_of_date_transfer_functions, ENTRY_BLOCK); + bitmap_set_bit (df_live_subreg->out_of_date_transfer_functions, EXIT_BLOCK); + + unsigned int bb_index; + bitmap_iterator bi; + EXECUTE_IF_SET_IN_BITMAP (df_live_subreg->out_of_date_transfer_functions, 0, + bb_index, bi) + { + /* Find the regs which we need to track it's subreg liveness. */ + rtx_insn *insn; + df_ref use; + FOR_BB_INSNS (bb, insn) + { + if (!NONDEBUG_INSN_P (insn)) + continue; + + df_insn_info *insn_info = DF_INSN_INFO_GET (insn); + + FOR_EACH_INSN_INFO_USE (use, insn_info) + { + unsigned int regno = DF_REF_REGNO (use); + /* A multireg which is used via subreg pattern. */ + if (multireg_p (regno) + && DF_REF_FLAGS (use) & (DF_REF_SUBREG)) + bitmap_set_bit (&problem_data->tracked_regs, regno); + } + } + } + + if (dump_file) + { + fprintf (dump_file, ";; regs need to be tracked subreg liveness: "); + df_print_regset (dump_file, &problem_data->tracked_regs); + } + + size_t n = bitmap_count_bits (&problem_data->tracked_regs); + + EXECUTE_IF_SET_IN_BITMAP (df_live_subreg->out_of_date_transfer_functions, 0, + bb_index, bi) + { + /* Clean global infos. */ + df_live_subreg_bb_info *bb_info = df_live_subreg_get_bb_info (bb_index); + + /* When bitmaps are already initialized, just clear them. */ + if (bb_info->all_in.obstack) + { + bitmap_clear (&bb_info->all_in); + bitmap_clear (&bb_info->full_in); + bitmap_clear (&bb_info->partial_in); + bitmap_clear (&bb_info->all_out); + bitmap_clear (&bb_info->full_out); + bitmap_clear (&bb_info->partial_out); + } + else + { + bitmap_initialize (&bb_info->all_in, + &problem_data->live_subreg_bitmaps); + bitmap_initialize (&bb_info->full_in, + &problem_data->live_subreg_bitmaps); + bitmap_initialize (&bb_info->partial_in, + &problem_data->live_subreg_bitmaps); + bitmap_initialize (&bb_info->all_out, + &problem_data->live_subreg_bitmaps); + bitmap_initialize (&bb_info->full_out, + &problem_data->live_subreg_bitmaps); + bitmap_initialize (&bb_info->partial_out, + &problem_data->live_subreg_bitmaps); + } + + if (bb_info->range_in) + { + bb_info->range_in->clear (n); + bb_info->range_out->clear (n); + } + else + { + bb_info->range_in = new subregs_live (n); + bb_info->range_out = new subregs_live (n); + } + + /* Clean local infos. */ + df_live_subreg_local_bb_info *local_bb_info + = get_live_subreg_local_bb_info (bb_index); + + /* When bitmaps are already initialized, just clear them. */ + if (local_bb_info->full_use.obstack) + { + bitmap_clear (&local_bb_info->full_def); + bitmap_clear (&local_bb_info->partial_def); + bitmap_clear (&local_bb_info->full_use); + bitmap_clear (&local_bb_info->partial_use); + } + else + { + bitmap_initialize (&local_bb_info->full_def, + &problem_data->live_subreg_bitmaps); + bitmap_initialize (&local_bb_info->partial_def, + &problem_data->live_subreg_bitmaps); + bitmap_initialize (&local_bb_info->full_use, + &problem_data->live_subreg_bitmaps); + bitmap_initialize (&local_bb_info->partial_use, + &problem_data->live_subreg_bitmaps); + } + + if (local_bb_info->range_def) + { + local_bb_info->range_def->clear (n); + local_bb_info->range_use->clear (n); + } + else + { + local_bb_info->range_def = new subregs_live (n); + local_bb_info->range_use = new subregs_live (n); + } + } + + df_live_subreg->optional_p = true; +} + +/* Reset the global solution for recalculation. */ + +static void +df_live_subreg_reset (bitmap all_blocks) +{ + unsigned int bb_index; + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) + { + df_live_subreg_bb_info *bb_info = df_live_subreg_get_bb_info (bb_index); + gcc_assert (bb_info); + bitmap_clear (&bb_info->all_in); + bitmap_clear (&bb_info->full_in); + bitmap_clear (&bb_info->partial_in); + bitmap_clear (&bb_info->all_out); + bitmap_clear (&bb_info->full_out); + bitmap_clear (&bb_info->partial_out); + bb_info->range_in->clear (); + bb_info->range_out->clear (); + } +} + +/* Compute local live register info for basic block BB. */ + +static void +df_live_subreg_bb_local_compute (unsigned int bb_index) +{ + basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index); + df_live_subreg_local_bb_info *local_bb_info + = get_live_subreg_local_bb_info (bb_index); + + rtx_insn *insn; + df_ref def, use; + + /* Process the registers set in an exception handler. */ + FOR_EACH_ARTIFICIAL_DEF (def, bb_index) + if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0) + { + add_subreg_range (local_bb_info, def, true); + remove_subreg_range (local_bb_info, def); + } + + /* Process the hardware registers that are always live. */ + FOR_EACH_ARTIFICIAL_USE (use, bb_index) + if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0) + add_subreg_range (local_bb_info, use, false); + + FOR_BB_INSNS_REVERSE (bb, insn) + { + if (!NONDEBUG_INSN_P (insn)) + continue; + + df_insn_info *insn_info = DF_INSN_INFO_GET (insn); + FOR_EACH_INSN_INFO_DEF (def, insn_info) + { + remove_subreg_range (local_bb_info, def); + add_subreg_range (local_bb_info, def, true); + } + + FOR_EACH_INSN_INFO_USE (use, insn_info) + { + unsigned int regno = DF_REF_REGNO (use); + /* Ignore the use of subreg which is used as dest operand. */ + if (need_track_subreg_p (regno) + && DF_REF_FLAGS (use) & (DF_REF_READ_WRITE | DF_REF_SUBREG)) + continue; + add_subreg_range (local_bb_info, use, false); + } + } + + /* Process the registers set in an exception handler or the hard + frame pointer if this block is the target of a non local + goto. */ + FOR_EACH_ARTIFICIAL_DEF (def, bb_index) + if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) + { + add_subreg_range (local_bb_info, def, true); + remove_subreg_range (local_bb_info, def); + } + +#ifdef EH_USES + /* Process the uses that are live into an exception handler. */ + FOR_EACH_ARTIFICIAL_USE (use, bb_index) + /* Add use to set of uses in this BB. */ + if (DF_REF_FLAGS (use) & DF_REF_AT_TOP) + add_subreg_range (local_bb_info, use, false); +#endif +} + +/* Compute local live register info for each basic block within BLOCKS. */ + +static void +df_live_subreg_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED) +{ + unsigned int bb_index, i; + bitmap_iterator bi; + + bitmap_clear (&df->hardware_regs_used); + + /* The all-important stack pointer must always be live. */ + bitmap_set_bit (&df->hardware_regs_used, STACK_POINTER_REGNUM); + + /* Global regs are always live, too. */ + for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) + if (global_regs[i]) + bitmap_set_bit (&df->hardware_regs_used, i); + + /* Before reload, there are a few registers that must be forced + live everywhere -- which might not already be the case for + blocks within infinite loops. */ + if (!reload_completed) + { + unsigned int pic_offset_table_regnum = PIC_OFFSET_TABLE_REGNUM; + /* Any reference to any pseudo before reload is a potential + reference of the frame pointer. */ + bitmap_set_bit (&df->hardware_regs_used, FRAME_POINTER_REGNUM); + + /* Pseudos with argument area equivalences may require + reloading via the argument pointer. */ + if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM + && fixed_regs[ARG_POINTER_REGNUM]) + bitmap_set_bit (&df->hardware_regs_used, ARG_POINTER_REGNUM); + + /* Any constant, or pseudo with constant equivalences, may + require reloading from memory using the pic register. */ + if (pic_offset_table_regnum != INVALID_REGNUM + && fixed_regs[pic_offset_table_regnum]) + bitmap_set_bit (&df->hardware_regs_used, pic_offset_table_regnum); + } + + EXECUTE_IF_SET_IN_BITMAP (df_live_subreg->out_of_date_transfer_functions, 0, + bb_index, bi) + { + if (bb_index == EXIT_BLOCK) + { + /* The exit block is special for this problem and its bits are + computed from thin air. */ + df_live_subreg_local_bb_info *local_bb_info + = get_live_subreg_local_bb_info (EXIT_BLOCK); + bitmap_copy (&local_bb_info->full_use, df->exit_block_uses); + } + else + df_live_subreg_bb_local_compute (bb_index); + } + + bitmap_clear (df_live_subreg->out_of_date_transfer_functions); +} + +/* Initialize the solution vectors. */ + +static void +df_live_subreg_init (bitmap all_blocks) +{ + unsigned int bb_index; + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) + { + df_live_subreg_bb_info *bb_info = df_live_subreg_get_bb_info (bb_index); + df_live_subreg_local_bb_info *local_bb_info + = get_live_subreg_local_bb_info (bb_index); + bitmap_copy (&bb_info->full_in, &local_bb_info->full_use); + bitmap_copy (&bb_info->partial_in, &local_bb_info->partial_use); + bb_info->range_in->copy_lives (*local_bb_info->range_use); + bitmap_clear (&bb_info->full_out); + bitmap_clear (&bb_info->partial_out); + bb_info->range_out->clear (); + } +} + +/* Check that the status of the final result is correct. */ + +void +df_live_subreg_check_result (bitmap full, bitmap partial, + subregs_live *partial_live) +{ + unsigned int regno; + bitmap_iterator bi; + /* Make sure that full and partial do not overlap. */ + gcc_assert (!bitmap_intersect_p (full, partial)); + /* Ensure that registers belonging to full are not partially live. */ + EXECUTE_IF_SET_IN_BITMAP (full, 0, regno, bi) + gcc_assert (partial_live->empty_p (regno)); + /* Ensure that registers belonging to partial are partially live. */ + EXECUTE_IF_SET_IN_BITMAP (partial, 0, regno, bi) + gcc_assert (!partial_live->empty_p (regno)); +} + +/* Confluence function that processes infinite loops. This might be a + noreturn function that throws. And even if it isn't, getting the + unwind info right helps debugging. */ +static void +df_live_subreg_confluence_0 (basic_block bb) +{ + bitmap full_out = &df_live_subreg_get_bb_info (bb->index)->full_out; + if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)) + bitmap_copy (full_out, &df->hardware_regs_used); +} + +/* Confluence function that ignores fake edges. */ + +static bool +df_live_subreg_confluence_n (edge e) +{ + class df_live_subreg_bb_info *src_bb_info + = df_live_subreg_get_bb_info (e->src->index); + class df_live_subreg_bb_info *dest_bb_info + = df_live_subreg_get_bb_info (e->dest->index); + + bool changed = false; + + /* Call-clobbered registers die across exception and call edges. + Conservatively treat partially-clobbered registers as surviving + across the edges; they might or might not, depending on what + mode they have. */ + /* ??? Abnormal call edges ignored for the moment, as this gets + confused by sibling call edges, which crashes reg-stack. */ + if (e->flags & EDGE_EH) + { + bitmap_view eh_kills (eh_edge_abi.full_reg_clobbers ()); + changed = bitmap_ior_and_compl_into (&src_bb_info->full_out, + &dest_bb_info->full_in, eh_kills); + } + else + changed = bitmap_ior_into (&src_bb_info->full_out, &dest_bb_info->full_in); + + changed |= bitmap_ior_into (&src_bb_info->full_out, &df->hardware_regs_used); + + /* Handle partial live case. */ + if (!bitmap_empty_p (&dest_bb_info->partial_in)) + { + unsigned int regno; + bitmap_iterator bi; + EXECUTE_IF_SET_IN_BITMAP (&dest_bb_info->partial_in, + FIRST_PSEUDO_REGISTER, regno, bi) + { + sbitmap dest_range = dest_bb_info->range_in->get_range (regno); + changed |= src_bb_info->range_out->add_range (regno, dest_range); + } + changed |= bitmap_ior_into (&src_bb_info->partial_out, + &dest_bb_info->partial_in); + + df_live_subreg_check_result (&src_bb_info->full_out, + &src_bb_info->partial_out, + src_bb_info->range_out); + } + + return changed; +} + +/* Transfer function. IN = USE | (OUT & ~DEF). */ + +static bool +df_live_subreg_transfer_function (int bb_index) +{ + class df_live_subreg_bb_info *bb_info = df_live_subreg_get_bb_info (bb_index); + class df_live_subreg_local_bb_info *local_bb_info + = get_live_subreg_local_bb_info (bb_index); + + bool changed = false; + + changed + |= bitmap_ior_and_compl (&bb_info->full_in, &local_bb_info->full_use, + &bb_info->full_out, &local_bb_info->full_def); + + /* Handle partial live case. */ + if (!bitmap_empty_p (&bb_info->partial_out) + || !bitmap_empty_p (&local_bb_info->partial_use)) + { + unsigned int regno; + bitmap_iterator bi; + bitmap_head temp_partial_out; + subregs_live temp_range_out; + + /* TEMP = (OUT & ~DEF) */ + bitmap_initialize (&temp_partial_out, &bitmap_default_obstack); + EXECUTE_IF_SET_IN_BITMAP (&bb_info->partial_out, FIRST_PSEUDO_REGISTER, + regno, bi) + { + sbitmap out_range = bb_info->range_out->get_range (regno); + temp_range_out.add_range (regno, out_range); + if (bitmap_bit_p (&local_bb_info->partial_def, regno)) + { + sbitmap def_range = local_bb_info->range_def->get_range (regno); + temp_range_out.remove_range (regno, def_range); + if (!temp_range_out.empty_p (regno)) + bitmap_set_bit (&temp_partial_out, regno); + } + else + bitmap_set_bit (&temp_partial_out, regno); + } + + /* TEMP = USE | TEMP */ + EXECUTE_IF_SET_IN_BITMAP (&local_bb_info->partial_use, + FIRST_PSEUDO_REGISTER, regno, bi) + { + sbitmap use_range = local_bb_info->range_use->get_range (regno); + temp_range_out.add_range (regno, use_range); + } + bitmap_ior_into (&temp_partial_out, &local_bb_info->partial_use); + + /* IN = TEMP */ + changed |= bb_info->range_in->copy_lives (temp_range_out); + bitmap_copy (&bb_info->partial_in, &temp_partial_out); + df_live_subreg_check_result (&bb_info->full_in, &bb_info->partial_in, + bb_info->range_in); + } + else if (!bitmap_empty_p (&bb_info->partial_in)) + { + changed = true; + bitmap_clear (&bb_info->partial_in); + bb_info->range_in->clear (); + } + + return changed; +} + +/* Calculating ALL_IN from FULL_IN and PARTIAL_IN + and ALL_OUT from FULL_OUT and PARTIAL_OUT. */ + +void +df_live_subreg_finalize (bitmap all_blocks) +{ + unsigned int bb_index; + bitmap_iterator bi; + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) + { + class df_live_subreg_bb_info *bb_info + = df_live_subreg_get_bb_info (bb_index); + gcc_assert (bb_info); + bitmap_ior (&bb_info->all_in, &bb_info->full_in, &bb_info->partial_in); + bitmap_ior (&bb_info->all_out, &bb_info->full_out, &bb_info->partial_out); + + /* Move full live reg in partial_in/partial_out to full_in/full_out. */ + unsigned int regno; + bitmap_iterator ri; + bool changed = false; + EXECUTE_IF_SET_IN_BITMAP (&bb_info->partial_in, FIRST_PSEUDO_REGISTER, + regno, ri) + { + if (bb_info->range_in->full_p (regno)) + { + bitmap_set_bit (&bb_info->full_in, regno); + bb_info->range_in->remove_range (regno); + changed = true; + } + } + if (changed) + bitmap_and_compl_into (&bb_info->partial_in, &bb_info->full_in); + + changed = false; + EXECUTE_IF_SET_IN_BITMAP (&bb_info->partial_out, FIRST_PSEUDO_REGISTER, + regno, ri) + { + if (bb_info->range_out->full_p (regno)) + { + bitmap_set_bit (&bb_info->full_out, regno); + bb_info->range_out->remove_range (regno); + changed = true; + } + } + if (changed) + bitmap_and_compl_into (&bb_info->partial_out, &bb_info->full_out); + } +} + +/* Free all storage associated with the problem. */ + +static void +df_live_subreg_free (void) +{ + df_live_subreg_problem_data *problem_data + = (df_live_subreg_problem_data *) df_live_subreg->problem_data; + if (df_live_subreg->block_info) + { + bitmap_obstack_release (&problem_data->live_subreg_bitmaps); + basic_block bb; + FOR_ALL_BB_FN (bb, cfun) + { + df_live_subreg_bb_info *bb_info + = df_live_subreg_get_bb_info (bb->index); + df_live_subreg_local_bb_info *local_bb_info + = get_live_subreg_local_bb_info (bb->index); + delete bb_info->range_in; + delete bb_info->range_out; + delete local_bb_info->range_def; + delete local_bb_info->range_use; + } + free (problem_data); + df_live_subreg->problem_data = NULL; + + df_live_subreg->block_info_size = 0; + free (df_live_subreg->block_info); + df_live_subreg->block_info = NULL; + } + + BITMAP_FREE (df_live_subreg->out_of_date_transfer_functions); + free (df_live_subreg); +} + +/* Debugging info at top of bb. */ + +static void +df_live_subreg_top_dump (basic_block bb, FILE *file) +{ + df_live_subreg_bb_info *bb_info = df_live_subreg_get_bb_info (bb->index); + df_live_subreg_local_bb_info *local_bb_info + = get_live_subreg_local_bb_info (bb->index); + + if (!bb_info) + return; + + fprintf (file, ";; subreg live all in \t"); + df_print_regset (file, &bb_info->all_in); + fprintf (file, ";; subreg live full in \t"); + df_print_regset (file, &bb_info->full_in); + fprintf (file, ";; subreg live partial in \t"); + df_print_regset (file, &bb_info->partial_in); + fprintf (file, ";; subreg live range in \t"); + bb_info->range_in->dump (file, ""); + + fprintf (file, "\n;; subreg live full use \t"); + df_print_regset (file, &local_bb_info->full_use); + fprintf (file, ";; subreg live partial use \t"); + df_print_regset (file, &local_bb_info->partial_use); + fprintf (file, ";; subreg live range use \t"); + local_bb_info->range_use->dump (file, ""); + + fprintf (file, "\n;; subreg live full def \t"); + df_print_regset (file, &local_bb_info->full_def); + fprintf (file, ";; subreg live partial def \t"); + df_print_regset (file, &local_bb_info->partial_def); + fprintf (file, ";; subreg live range def \t"); + local_bb_info->range_def->dump (file, ""); +} + +/* Debugging info at bottom of bb. */ + +static void +df_live_subreg_bottom_dump (basic_block bb, FILE *file) +{ + df_live_subreg_bb_info *bb_info = df_live_subreg_get_bb_info (bb->index); + if (!bb_info) + return; + + fprintf (file, ";; subreg live all out \t"); + df_print_regset (file, &bb_info->all_out); + fprintf (file, ";; subreg live full out \t"); + df_print_regset (file, &bb_info->full_out); + fprintf (file, ";; subreg live partial out \t"); + df_print_regset (file, &bb_info->partial_out); + fprintf (file, ";; subreg live range out \t"); + bb_info->range_out->dump (file, ""); +} + +/* All of the information associated with every instance of the problem. */ + +static const struct df_problem problem_LIVE_SUBREG = { + DF_LIVE_SUBREG, /* Problem id. */ + DF_BACKWARD, /* Direction. */ + df_live_subreg_alloc, /* Allocate the problem specific data. */ + df_live_subreg_reset, /* Reset global information. */ + df_live_subreg_free_bb_info, /* Free basic block info. */ + df_live_subreg_local_compute, /* Local compute function. */ + df_live_subreg_init, /* Init the solution specific data. */ + df_worklist_dataflow, /* Worklist solver. */ + df_live_subreg_confluence_0, /* Confluence operator 0. */ + df_live_subreg_confluence_n, /* Confluence operator n. */ + df_live_subreg_transfer_function, /* Transfer function. */ + df_live_subreg_finalize, /* Finalize function. */ + df_live_subreg_free, /* Free all of the problem information. */ + df_live_subreg_free, /* Remove this problem from the stack of dataflow + problems. */ + NULL, /* Debugging. */ + df_live_subreg_top_dump, /* Debugging start block. */ + df_live_subreg_bottom_dump, /* Debugging end block. */ + NULL, /* Debugging start insn. */ + NULL, /* Debugging end insn. */ + NULL, /* Incremental solution verify start. */ + NULL, /* Incremental solution verify end. */ + &problem_LR, /* Dependent problem. */ + sizeof (df_live_subreg_bb_info), /* Size of entry of block_info array. */ + TV_DF_LIVE_SUBREG, /* Timing variable. */ + false /* Reset blocks on dropping out of blocks_to_analyze. */ +}; + +/* Create a new DATAFLOW instance and add it to an existing instance + of DF. The returned structure is what is used to get at the + solution. */ + +void +df_live_subreg_add_problem (void) +{ + gcc_assert (flag_track_subreg_liveness); + + df_add_problem (&problem_LIVE_SUBREG); + + /* These will be initialized when df_scan_blocks processes each + block. */ + df_live_subreg->out_of_date_transfer_functions + = BITMAP_ALLOC (&df_bitmap_obstack); +} - /*---------------------------------------------------------------------------- LIVE AND MAY-INITIALIZED REGISTERS. diff --git a/gcc/df.h b/gcc/df.h index 84e5aa8b524..78c57273cf1 100644 --- a/gcc/df.h +++ b/gcc/df.h @@ -47,6 +47,7 @@ enum df_problem_id { DF_SCAN, DF_LR, /* Live Registers backward. */ + DF_LIVE_SUBREG, /* Live Regs and Subregs */ DF_LIVE, /* Live Registers & Uninitialized Registers */ DF_RD, /* Reaching Defs. */ DF_CHAIN, /* Def-Use and/or Use-Def Chains. */ @@ -878,6 +879,33 @@ public: bitmap_head out; /* At the bottom of the block. */ }; +class subregs_live; /* Defined in subreg-range.{h,cc} */ + +/* Local live info in basic block. Use by live_subreg problem and LRA pass. */ +class df_live_subreg_local_bb_info +{ +public: + bitmap_head full_def; + bitmap_head full_use; + /* Only for pseudo registers. */ + bitmap_head partial_def; + bitmap_head partial_use; + subregs_live *range_def = nullptr; + subregs_live *range_use = nullptr; +}; + +/* Live in/out infos of each basic. */ +class df_live_subreg_bb_info : public df_live_subreg_local_bb_info +{ +public: + bitmap_head all_in, full_in; + bitmap_head all_out, full_out; + /* Only for pseudo registers. */ + bitmap_head partial_in; + bitmap_head partial_out; + subregs_live *range_in = nullptr; + subregs_live *range_out = nullptr; +}; /* Uninitialized registers. All bitmaps are referenced by the register number. Anded results of the forwards and backward live @@ -940,6 +968,7 @@ extern class df_d *df; #define df_scan (df->problems_by_index[DF_SCAN]) #define df_rd (df->problems_by_index[DF_RD]) #define df_lr (df->problems_by_index[DF_LR]) +#define df_live_subreg (df->problems_by_index[DF_LIVE_SUBREG]) #define df_live (df->problems_by_index[DF_LIVE]) #define df_chain (df->problems_by_index[DF_CHAIN]) #define df_word_lr (df->problems_by_index[DF_WORD_LR]) @@ -1031,6 +1060,8 @@ extern void df_lr_add_problem (void); extern void df_lr_verify_transfer_functions (void); extern void df_live_verify_transfer_functions (void); extern void df_live_add_problem (void); +extern void df_live_subreg_add_problem (); +extern void df_live_subreg_finalize (bitmap all_blocks); extern void df_live_set_all_dirty (void); extern void df_chain_add_problem (unsigned int); extern void df_word_lr_add_problem (void); @@ -1059,6 +1090,16 @@ extern bool can_move_insns_across (rtx_insn *, rtx_insn *, rtx_insn *, rtx_insn *, basic_block, regset, regset, rtx_insn **); +extern void +df_live_subreg_check_result (bitmap, bitmap, subregs_live *); +extern bool multireg_p (int); +extern void init_range (rtx, sbitmap); +extern void +add_subreg_range (df_live_subreg_local_bb_info *, unsigned int, const_sbitmap, + bool); +extern void +remove_subreg_range (df_live_subreg_local_bb_info *, unsigned int, + const_sbitmap); /* Functions defined in df-scan.cc. */ extern void df_scan_alloc (bitmap); @@ -1192,6 +1233,120 @@ df_get_live_in (basic_block bb) return DF_LR_IN (bb); } +/* Get the subreg live at in set for BB. The live set include full and partial + * live. we only track and use subreg liveness when -ftrack-subreg-liveness, + * otherwise use DF_LR_IN. This function is used by the register allocators. */ + +inline bitmap +df_get_subreg_live_in (basic_block bb) +{ + if (flag_track_subreg_liveness) + { + df_live_subreg_bb_info *bb_info = &( + (class df_live_subreg_bb_info *) df_live_subreg->block_info)[bb->index]; + return &(bb_info->all_in); + } + return DF_LR_IN (bb); +} + +/* Get the subreg live at out set for BB. The live set include full and + * partial live. we only track and use subreg liveness when + * -ftrack-subreg-liveness, otherwise use DF_LR_OUT. This function is used by + * the register allocators. */ + +inline bitmap +df_get_subreg_live_out (basic_block bb) +{ + if (flag_track_subreg_liveness) + { + df_live_subreg_bb_info *bb_info = &( + (class df_live_subreg_bb_info *) df_live_subreg->block_info)[bb->index]; + return &(bb_info->all_out); + } + return DF_LR_OUT (bb); +} + +/* Get the subreg live at in set for BB. The live set only include full and + * partial live. we only track and use subreg liveness when + * -ftrack-subreg-liveness, otherwise use DF_LR_OUT. This function is used by + * the register allocators. */ + +inline bitmap +df_get_subreg_live_full_in (basic_block bb) +{ + if (flag_track_subreg_liveness) + { + df_live_subreg_bb_info *bb_info = &( + (class df_live_subreg_bb_info *) df_live_subreg->block_info)[bb->index]; + return &(bb_info->full_in); + } + return DF_LR_IN (bb); +} + +inline bitmap +df_get_subreg_live_full_out (basic_block bb) +{ + if (flag_track_subreg_liveness) + { + df_live_subreg_bb_info *bb_info = &( + (class df_live_subreg_bb_info *) df_live_subreg->block_info)[bb->index]; + return &(bb_info->full_out); + } + return DF_LR_OUT (bb); +} + +/* Define in df-problems.cc, used when disable track-subreg-liveness. */ +extern bitmap_head empty_bitmap; +extern subregs_live empty_live; + +inline bitmap +df_get_subreg_live_partial_in (basic_block bb) +{ + if (flag_track_subreg_liveness) + { + df_live_subreg_bb_info *bb_info = &( + (class df_live_subreg_bb_info *) df_live_subreg->block_info)[bb->index]; + return &(bb_info->partial_in); + } + return &empty_bitmap; +} + +inline bitmap +df_get_subreg_live_partial_out (basic_block bb) +{ + if (flag_track_subreg_liveness) + { + df_live_subreg_bb_info *bb_info = &( + (class df_live_subreg_bb_info *) df_live_subreg->block_info)[bb->index]; + return &(bb_info->partial_out); + } + return &empty_bitmap; +} + +inline subregs_live * +df_get_subreg_live_range_in (basic_block bb) +{ + if (flag_track_subreg_liveness) + { + df_live_subreg_bb_info *bb_info = &( + (class df_live_subreg_bb_info *) df_live_subreg->block_info)[bb->index]; + return bb_info->range_in; + } + return &empty_live; +} + +inline subregs_live * +df_get_subreg_live_range_out (basic_block bb) +{ + if (flag_track_subreg_liveness) + { + df_live_subreg_bb_info *bb_info = &( + (class df_live_subreg_bb_info *) df_live_subreg->block_info)[bb->index]; + return bb_info->range_out; + } + return &empty_live; +} + /* Get basic block info. */ /* Get the artificial defs for a basic block. */ diff --git a/gcc/regs.h b/gcc/regs.h index 16189c58fd1..3b524096533 100644 --- a/gcc/regs.h +++ b/gcc/regs.h @@ -389,4 +389,9 @@ range_in_hard_reg_set_p (const_hard_reg_set set, unsigned regno, int nregs) return true; } +/* Return the number of blocks the MODE overlap. One block equal to mode's + natural size. */ +#define get_nblocks(mode) \ + (exact_div (GET_MODE_SIZE (mode), REGMODE_NATURAL_SIZE (mode)).to_constant ()) + #endif /* GCC_REGS_H */ diff --git a/gcc/sbitmap.cc b/gcc/sbitmap.cc index 03bb2c6d44b..5d960adcabe 100644 --- a/gcc/sbitmap.cc +++ b/gcc/sbitmap.cc @@ -208,6 +208,29 @@ bitmap_empty_p (const_sbitmap bmap) return true; } +/* Return true if the bitmap is full, i.e. all bits are set. */ + +bool +bitmap_full_p (const_sbitmap bmap) +{ + unsigned int end_word = bmap->n_bits / SBITMAP_ELT_BITS; + unsigned int i = 0; + for (; i < end_word; i++) + if (bmap->elms[i] != (SBITMAP_ELT_TYPE) -1) + return false; + + unsigned int end_bitno = bmap->n_bits % SBITMAP_ELT_BITS; + + if (end_bitno == 0) + return true; + + gcc_checking_assert (i + 1 == bmap->size); + + SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE) 1 << end_bitno) - 1; + /* Make sure the tail bits are set. */ + return (bmap->elms[i] & mask) == mask; +} + /* Clear COUNT bits from START in BMAP. */ void @@ -662,6 +685,36 @@ bitmap_subset_p (const_sbitmap a, const_sbitmap b) return true; } +/* Return true if the bits in A and B are set the same and the number of bits is + the same. */ + +bool +bitmap_same_p (const_sbitmap a, const_sbitmap b) +{ + if (a->n_bits != b->n_bits) + return false; + + gcc_checking_assert (a->size == b->size); + + unsigned int end_word = a->n_bits / SBITMAP_ELT_BITS; + unsigned int i = 0; + for (; i < end_word; i++) + if (a->elms[i] != b->elms[i]) + return false; + + unsigned int end_bitno = a->n_bits % SBITMAP_ELT_BITS; + + if (end_bitno == 0) + return true; + + gcc_checking_assert (i + 1 == a->size); + + SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE) 1 << end_bitno) - 1; + + /* Make sure the tail bits are same. */ + return (a->elms[i] & mask) == (b->elms[i] & mask); +} + /* Set DST to be (A or (B and C)). Return nonzero if any change is made. */ @@ -994,6 +1047,49 @@ test_bit_in_range () sbitmap_free (s); } +/* Verify bitmap_full_p functions for sbitmap. */ + +static void +test_full () +{ + sbitmap s = sbitmap_alloc (193); + + bitmap_clear (s); + ASSERT_FALSE (bitmap_full_p (s)); + + bitmap_ones (s); + ASSERT_TRUE (bitmap_full_p (s)); + + bitmap_clear_bit (s, 192); + ASSERT_FALSE (bitmap_full_p (s)); + + bitmap_ones (s); + bitmap_clear_bit (s, 17); + ASSERT_FALSE (bitmap_full_p (s)); +} + +/* Verify bitmap_same_p functions for sbitmap. */ + +static void +test_same () +{ + sbitmap s1 = sbitmap_alloc (193); + sbitmap s2 = sbitmap_alloc (193); + sbitmap s3 = sbitmap_alloc (192); + + ASSERT_FALSE (bitmap_same_p (s1, s3)); + + bitmap_clear (s1); + bitmap_clear (s2); + ASSERT_TRUE (bitmap_same_p (s1, s2)); + + bitmap_set_bit (s2, 192); + ASSERT_FALSE (bitmap_same_p (s1, s2)); + + bitmap_set_bit (s1, 192); + ASSERT_TRUE (bitmap_same_p (s1, s2)); +} + /* Run all of the selftests within this file. */ void @@ -1001,6 +1097,8 @@ sbitmap_cc_tests () { test_set_range (); test_bit_in_range (); + test_full (); + test_same (); } } // namespace selftest diff --git a/gcc/sbitmap.h b/gcc/sbitmap.h index da6116ce925..71cfded9fb2 100644 --- a/gcc/sbitmap.h +++ b/gcc/sbitmap.h @@ -267,6 +267,7 @@ extern void bitmap_copy (sbitmap, const_sbitmap); extern bool bitmap_equal_p (const_sbitmap, const_sbitmap); extern unsigned int bitmap_count_bits (const_sbitmap); extern bool bitmap_empty_p (const_sbitmap); +extern bool bitmap_full_p (const_sbitmap); extern void bitmap_clear (sbitmap); extern void bitmap_clear_range (sbitmap, unsigned, unsigned); extern void bitmap_set_range (sbitmap, unsigned, unsigned); @@ -287,6 +288,7 @@ extern bool bitmap_and (sbitmap, const_sbitmap, const_sbitmap); extern bool bitmap_ior (sbitmap, const_sbitmap, const_sbitmap); extern bool bitmap_xor (sbitmap, const_sbitmap, const_sbitmap); extern bool bitmap_subset_p (const_sbitmap, const_sbitmap); +extern bool bitmap_same_p (const_sbitmap, const_sbitmap); extern bool bitmap_bit_in_range_p (const_sbitmap, unsigned int, unsigned int); extern int bitmap_first_set_bit (const_sbitmap); diff --git a/gcc/subreg-live-range.cc b/gcc/subreg-live-range.cc new file mode 100644 index 00000000000..fe8d4210eb6 --- /dev/null +++ b/gcc/subreg-live-range.cc @@ -0,0 +1,53 @@ +/* SUBREG liveness tracking classes for DF & IRA & LRA. + Copyright (C) 2023 Free Software Foundation, Inc. + Contributed by Lehua Ding (lehua.ding@rivai.ai), RiVAI Technologies Ltd. + + This file is part of GCC. + + GCC 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 3, or (at your option) + any later version. + + GCC 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 GCC; see the file COPYING3. If not see + . */ + +#include "subreg-live-range.h" + +void +subregs_live::dump (FILE *file, const char *indent) const +{ + if (lives.empty ()) + { + fprintf (file, "%sempty\n", indent); + return; + } + fprintf (file, "%s", indent); + for (auto &kv : lives) + { + const_sbitmap range = kv.second; + if (bitmap_empty_p (range)) + continue; + fprintf (file, "%d: ", kv.first); + if (!bitmap_full_p (range)) + { + dump_bitmap_file (file, range); + fprintf (file, ", "); + } + else + fprintf (file, "full, "); + } + fprintf (file, "\n"); +} + +DEBUG_FUNCTION void +debug (const subregs_live &l) +{ + l.dump (stderr, ""); +} diff --git a/gcc/subreg-live-range.h b/gcc/subreg-live-range.h new file mode 100644 index 00000000000..c0b88071858 --- /dev/null +++ b/gcc/subreg-live-range.h @@ -0,0 +1,206 @@ +/* SUBREG liveness tracking classes for DF & IRA & LRA. + Copyright (C) 2023 Free Software Foundation, Inc. + Contributed by Lehua Ding (lehua.ding@rivai.ai), RiVAI Technologies Ltd. + + This file is part of GCC. + + GCC 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 3, or (at your option) + any later version. + + GCC 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 GCC; see the file COPYING3. If not see + . */ + +#ifndef GCC_SUBREG_LIVE_RANGE_H +#define GCC_SUBREG_LIVE_RANGE_H + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include +#include "sbitmap.h" + +/* class subregs_live record the live subreg_ranges of registers. */ +class subregs_live +{ +public: + /* The key is usually the register's regno. */ + std::unordered_map lives; + + subregs_live () : lives () {} + + subregs_live (size_t n) : lives (n) {} + + ~subregs_live () + { + for (auto &kv : lives) + sbitmap_free (kv.second); + } + + void clear () + { + for (auto &kv : lives) + sbitmap_free (kv.second); + lives.clear (); + } + + void clear (size_t n) + { + clear (); + lives.rehash (n); + } + + bool find_p (unsigned int regno) const + { + return lives.find (regno) != lives.end (); + } + + sbitmap get_range (unsigned int regno) + { + gcc_assert (find_p (regno)); + return lives.at (regno); + } + + const_sbitmap get_range (unsigned int regno) const + { + gcc_assert (find_p (regno)); + return lives.at (regno); + } + + /* Added RANGE to regno's ranges. Return true if leads to a change. */ + bool add_range (unsigned int regno, const_sbitmap range) + { + if (find_p (regno)) + { + sbitmap curr = get_range (regno); + gcc_assert (range->n_bits == curr->n_bits); + return bitmap_ior (curr, curr, range); + } + else + { + sbitmap a = sbitmap_alloc (range->n_bits); + lives.insert ({regno, a}); + sbitmap curr = get_range (regno); + bitmap_copy (curr, range); + return !bitmap_empty_p (range); + } + } + /* Removed RANGE from regno's ranges. Return true if leads to a change. */ + bool remove_range (unsigned int regno, const_sbitmap range) + { + if (find_p (regno)) + { + sbitmap curr = get_range (regno); + bitmap_check_sizes (curr, range); + if (bitmap_subset_p (curr, range)) + return remove_range (regno); + + auto_sbitmap a (range->n_bits); + bitmap_not (a, range); + return bitmap_and (curr, curr, a); + } + return false; + } + /* Removed the whole range of REGNO. Return true if leads to a change. */ + bool remove_range (unsigned int regno) + { + if (find_p (regno)) + { + sbitmap curr = get_range (regno); + bool changed = !bitmap_empty_p (curr); + sbitmap_free (curr); + lives.erase (regno); + return changed; + } + return false; + } + /* Replace the range of REGNO with RANGE. Return true if leads to a change. + */ + bool replace_range (unsigned int regno, const_sbitmap range) + { + if (find_p (regno)) + { + sbitmap curr = get_range (regno); + if (!bitmap_same_p (curr, range)) + { + bitmap_copy (curr, range); + return true; + } + else + return false; + } + else + return add_range (regno, range); + } + /* Copy subregs_live SL. Return true if leads to a change. */ + bool copy_lives (const subregs_live &sl) + { + bool changed = false; + for (auto &kv : sl.lives) + { + unsigned int regno = kv.first; + const_sbitmap range = kv.second; + if (bitmap_empty_p (range)) + continue; + if (find_p (regno)) + changed |= replace_range (regno, range); + else + changed |= add_range (regno, range); + } + + for (auto it = lives.cbegin (); it != lives.cend ();) + { + unsigned int regno = it->first; + auto prev_it = it; + it++; + if (sl.empty_p (regno)) + { + changed |= bitmap_empty_p (it->second); + lives.erase (prev_it); + } + } + + return changed; + } + /* Added subregs_live SL. Return true if leads to a change. */ + bool add_lives (const subregs_live &sl) + { + bool changed = false; + for (auto &kv : sl.lives) + { + unsigned int regno = kv.first; + const_sbitmap range = kv.second; + if (find_p (regno)) + { + sbitmap curr = get_range (regno); + changed |= bitmap_ior (curr, curr, range); + } + else + changed |= add_range (regno, range); + } + return changed; + } + + /* Return true if regno's live range is full. */ + bool full_p (unsigned int regno) const + { + return find_p (regno) && bitmap_full_p (get_range (regno)); + } + /* Return true if regno's live range is empty. */ + bool empty_p (unsigned int regno) const + { + return !find_p (regno) || bitmap_empty_p (get_range (regno)); + } + + /* Debug helper. */ + void dump (FILE *file, const char *indent = ";; ") const; +}; + +#endif /* GCC_SUBREG_LIVE_RANGE_H */ diff --git a/gcc/timevar.def b/gcc/timevar.def index 8e2168e0817..337a2b7225b 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -120,6 +120,7 @@ DEFTIMEVAR (TV_DF_SCAN , "df scan insns") DEFTIMEVAR (TV_DF_MD , "df multiple defs") DEFTIMEVAR (TV_DF_RD , "df reaching defs") DEFTIMEVAR (TV_DF_LR , "df live regs") +DEFTIMEVAR (TV_DF_LIVE_SUBREG , "df live subregs") DEFTIMEVAR (TV_DF_LIVE , "df live&initialized regs") DEFTIMEVAR (TV_DF_MIR , "df must-initialized regs") DEFTIMEVAR (TV_DF_CHAIN , "df use-def / def-use chains") -- 2.36.3